Experimental post-pass scheduling support. Post-pass scheduling

is currently off by default, and can be enabled with
-disable-post-RA-scheduler=false.

This doesn't have a significant impact on most code yet because it doesn't
yet do anything to address anti-dependencies and it doesn't attempt to
disambiguate memory references. Also, several popular targets
don't have pipeline descriptions yet.

The majority of the changes here are splitting the SelectionDAG-specific
code out of ScheduleDAG, so that ScheduleDAG can be moved to
libLLVMCodeGen.a. The interface between ScheduleDAG-using code and
the rest of the scheduling code is somewhat rough and will evolve.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59676 91177308-0d34-0410-b5e6-96231b3b80d8

17 files changed, 1012 insertions, 824 deletions

diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt
index a7aad33..fed3237 100644
--- a/lib/CodeGen/CMakeLists.txt
+++ b/lib/CodeGen/CMakeLists.txt
@@ -8,6 +8,7 @@ add_llvm_library(LLVMCodeGen
   IfConversion.cpp
   IntrinsicLowering.cpp
   LLVMTargetMachine.cpp
+  LatencyPriorityQueue.cpp
   LiveInterval.cpp
   LiveIntervalAnalysis.cpp
   LiveStackAnalysis.cpp
@@ -40,6 +41,10 @@ add_llvm_library(LLVMCodeGen
   RegAllocSimple.cpp
   RegisterCoalescer.cpp
   RegisterScavenging.cpp
+  ScheduleDAG.cpp
+  ScheduleDAGEmit.cpp
+  ScheduleDAGInstrs.cpp
+  ScheduleDAGPrinter.cpp
   ShadowStackGC.cpp
   SimpleRegisterCoalescing.cpp
   StackProtector.cpp
diff --git a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp b/lib/CodeGen/LatencyPriorityQueue.cpp
index ae73f20..70b6574 100644
--- a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp
+++ b/lib/CodeGen/LatencyPriorityQueue.cpp
@@ -14,7 +14,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "scheduler"
-#include "LatencyPriorityQueue.h"
+#include "llvm/CodeGen/LatencyPriorityQueue.h"
 #include "llvm/Support/Debug.h"
 using namespace llvm;
 
diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp
index 41981d3..3a31eaa 100644
--- a/lib/CodeGen/PostRASchedulerList.cpp
+++ b/lib/CodeGen/PostRASchedulerList.cpp
@@ -20,47 +20,234 @@
 
 #define DEBUG_TYPE "post-RA-sched"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/ScheduleDAGInstrs.h"
+#include "llvm/CodeGen/LatencyPriorityQueue.h"
+#include "llvm/CodeGen/SchedulerRegistry.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
 using namespace llvm;
 
+STATISTIC(NumStalls, "Number of pipeline stalls");
+
 namespace {
-  class VISIBILITY_HIDDEN SchedulePostRATDList : public MachineFunctionPass {
+  class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass {
   public:
     static char ID;
-    SchedulePostRATDList() : MachineFunctionPass(&ID) {}
+    PostRAScheduler() : MachineFunctionPass(&ID) {}
+  private:
+    MachineFunction *MF;
+    const TargetMachine *TM;
+  public:
+    const char *getPassName() const {
+      return "Post RA top-down list latency scheduler (STUB)";
+    }
+
+    bool runOnMachineFunction(MachineFunction &Fn);
+  };
+  char PostRAScheduler::ID = 0;
+
+  class VISIBILITY_HIDDEN SchedulePostRATDList : public ScheduleDAGInstrs {
+  public:
+    SchedulePostRATDList(MachineBasicBlock *mbb, const TargetMachine &tm)
+      : ScheduleDAGInstrs(mbb, tm) {}
   private:
     MachineFunction *MF;
     const TargetMachine *TM;
+
+    /// AvailableQueue - The priority queue to use for the available SUnits.
+    ///
+    LatencyPriorityQueue AvailableQueue;
+  
+    /// PendingQueue - This contains all of the instructions whose operands have
+    /// been issued, but their results are not ready yet (due to the latency of
+    /// the operation).  Once the operands becomes available, the instruction is
+    /// added to the AvailableQueue.
+    std::vector<SUnit*> PendingQueue;
+
   public:
     const char *getPassName() const {
       return "Post RA top-down list latency scheduler (STUB)";
     }
 
     bool runOnMachineFunction(MachineFunction &Fn);
+
+    void Schedule();
+
+  private:
+    void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
+    void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
+    void ListScheduleTopDown();
   };
-  char SchedulePostRATDList::ID = 0;
 }
 
-bool SchedulePostRATDList::runOnMachineFunction(MachineFunction &Fn) {
-  DOUT << "SchedulePostRATDList\n";
+bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
+  DOUT << "PostRAScheduler\n";
   MF = &Fn;
   TM = &MF->getTarget();
 
   // Loop over all of the basic blocks
   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
-       MBB != MBBe; ++MBB)
-    ;
+       MBB != MBBe; ++MBB) {
+
+    SchedulePostRATDList Scheduler(MBB, *TM);
+
+    Scheduler.Run();
+
+    Scheduler.EmitSchedule();
+  }
 
   return true;
 }
   
+/// Schedule - Schedule the DAG using list scheduling.
+void SchedulePostRATDList::Schedule() {
+  DOUT << "********** List Scheduling **********\n";
+  
+  // Build scheduling units.
+  BuildSchedUnits();
+
+  AvailableQueue.initNodes(SUnits);
+  
+  ListScheduleTopDown();
+  
+  AvailableQueue.releaseState();
+}
+
+//===----------------------------------------------------------------------===//
+//  Top-Down Scheduling
+//===----------------------------------------------------------------------===//
+
+/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
+/// the PendingQueue if the count reaches zero. Also update its cycle bound.
+void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+  --SuccSU->NumPredsLeft;
+  
+#ifndef NDEBUG
+  if (SuccSU->NumPredsLeft < 0) {
+    cerr << "*** Scheduling failed! ***\n";
+    SuccSU->dump(this);
+    cerr << " has been released too many times!\n";
+    assert(0);
+  }
+#endif
+  
+  // Compute how many cycles it will be before this actually becomes
+  // available.  This is the max of the start time of all predecessors plus
+  // their latencies.
+  // If this is a token edge, we don't need to wait for the latency of the
+  // preceeding instruction (e.g. a long-latency load) unless there is also
+  // some other data dependence.
+  unsigned PredDoneCycle = SU->Cycle;
+  if (!isChain)
+    PredDoneCycle += SU->Latency;
+  else if (SU->Latency)
+    PredDoneCycle += 1;
+  SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle);
+  
+  if (SuccSU->NumPredsLeft == 0) {
+    PendingQueue.push_back(SuccSU);
+  }
+}
+
+/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
+/// count of its successors. If a successor pending count is zero, add it to
+/// the Available queue.
+void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
+  DOUT << "*** Scheduling [" << CurCycle << "]: ";
+  DEBUG(SU->dump(this));
+  
+  Sequence.push_back(SU);
+  SU->Cycle = CurCycle;
+
+  // Top down: release successors.
+  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+       I != E; ++I)
+    ReleaseSucc(SU, I->Dep, I->isCtrl);
+
+  SU->isScheduled = true;
+  AvailableQueue.ScheduledNode(SU);
+}
+
+/// ListScheduleTopDown - The main loop of list scheduling for top-down
+/// schedulers.
+void SchedulePostRATDList::ListScheduleTopDown() {
+  unsigned CurCycle = 0;
+
+  // All leaves to Available queue.
+  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
+    // It is available if it has no predecessors.
+    if (SUnits[i].Preds.empty()) {
+      AvailableQueue.push(&SUnits[i]);
+      SUnits[i].isAvailable = true;
+    }
+  }
+  
+  // While Available queue is not empty, grab the node with the highest
+  // priority. If it is not ready put it back.  Schedule the node.
+  Sequence.reserve(SUnits.size());
+  while (!AvailableQueue.empty() || !PendingQueue.empty()) {
+    // Check to see if any of the pending instructions are ready to issue.  If
+    // so, add them to the available queue.
+    for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
+      if (PendingQueue[i]->CycleBound == CurCycle) {
+        AvailableQueue.push(PendingQueue[i]);
+        PendingQueue[i]->isAvailable = true;
+        PendingQueue[i] = PendingQueue.back();
+        PendingQueue.pop_back();
+        --i; --e;
+      } else {
+        assert(PendingQueue[i]->CycleBound > CurCycle && "Negative latency?");
+      }
+    }
+    
+    // If there are no instructions available, don't try to issue anything, and
+    // don't advance the hazard recognizer.
+    if (AvailableQueue.empty()) {
+      ++CurCycle;
+      continue;
+    }
+
+    SUnit *FoundSUnit = AvailableQueue.pop();
+    
+    // If we found a node to schedule, do it now.
+    if (FoundSUnit) {
+      ScheduleNodeTopDown(FoundSUnit, CurCycle);
+
+      // If this is a pseudo-op node, we don't want to increment the current
+      // cycle.
+      if (FoundSUnit->Latency)  // Don't increment CurCycle for pseudo-ops!
+        ++CurCycle;        
+    } else {
+      // Otherwise, we have a pipeline stall, but no other problem, just advance
+      // the current cycle and try again.
+      DOUT << "*** Advancing cycle, no work to do\n";
+      ++NumStalls;
+      ++CurCycle;
+    }
+  }
+
+#ifndef NDEBUG
+  // Verify that all SUnits were scheduled.
+  bool AnyNotSched = false;
+  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
+    if (SUnits[i].NumPredsLeft != 0) {
+      if (!AnyNotSched)
+        cerr << "*** List scheduling failed! ***\n";
+      SUnits[i].dump(this);
+      cerr << "has not been scheduled!\n";
+      AnyNotSched = true;
+    }
+  }
+  assert(!AnyNotSched);
+#endif
+}
 
 //===----------------------------------------------------------------------===//
 //                         Public Constructor Functions
 //===----------------------------------------------------------------------===//
 
 FunctionPass *llvm::createPostRAScheduler() {
-  return new SchedulePostRATDList();
+  return new PostRAScheduler();
 }
diff --git a/lib/CodeGen/ScheduleDAG.cpp b/lib/CodeGen/ScheduleDAG.cpp
new file mode 100644
index 0000000..e6a8d13
--- /dev/null
+++ b/lib/CodeGen/ScheduleDAG.cpp
@@ -0,0 +1,210 @@
+//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This implements the ScheduleDAG class, which is a base class used by
+// scheduling implementation classes.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "pre-RA-sched"
+#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+using namespace llvm;
+
+ScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
+                         const TargetMachine &tm)
+  : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) {
+  TII = TM.getInstrInfo();
+  MF  = BB->getParent();
+  TRI = TM.getRegisterInfo();
+  TLI = TM.getTargetLowering();
+  ConstPool = MF->getConstantPool();
+}
+
+ScheduleDAG::~ScheduleDAG() {}
+
+/// CalculateDepths - compute depths using algorithms for the longest
+/// paths in the DAG
+void ScheduleDAG::CalculateDepths() {
+  unsigned DAGSize = SUnits.size();
+  std::vector<SUnit*> WorkList;
+  WorkList.reserve(DAGSize);
+
+  // Initialize the data structures
+  for (unsigned i = 0, e = DAGSize; i != e; ++i) {
+    SUnit *SU = &SUnits[i];
+    unsigned Degree = SU->Preds.size();
+    // Temporarily use the Depth field as scratch space for the degree count.
+    SU->Depth = Degree;
+
+    // Is it a node without dependencies?
+    if (Degree == 0) {
+        assert(SU->Preds.empty() && "SUnit should have no predecessors");
+        // Collect leaf nodes
+        WorkList.push_back(SU);
+    }
+  }
+
+  // Process nodes in the topological order
+  while (!WorkList.empty()) {
+    SUnit *SU = WorkList.back();
+    WorkList.pop_back();
+    unsigned SUDepth = 0;
+
+    // Use dynamic programming:
+    // When current node is being processed, all of its dependencies
+    // are already processed.
+    // So, just iterate over all predecessors and take the longest path
+    for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+         I != E; ++I) {
+      unsigned PredDepth = I->Dep->Depth;
+      if (PredDepth+1 > SUDepth) {
+          SUDepth = PredDepth + 1;
+      }
+    }
+
+    SU->Depth = SUDepth;
+
+    // Update degrees of all nodes depending on current SUnit
+    for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+         I != E; ++I) {
+      SUnit *SU = I->Dep;
+      if (!--SU->Depth)
+        // If all dependencies of the node are processed already,
+        // then the longest path for the node can be computed now
+        WorkList.push_back(SU);
+    }
+  }
+}
+
+/// CalculateHeights - compute heights using algorithms for the longest
+/// paths in the DAG
+void ScheduleDAG::CalculateHeights() {
+  unsigned DAGSize = SUnits.size();
+  std::vector<SUnit*> WorkList;
+  WorkList.reserve(DAGSize);
+
+  // Initialize the data structures
+  for (unsigned i = 0, e = DAGSize; i != e; ++i) {
+    SUnit *SU = &SUnits[i];
+    unsigned Degree = SU->Succs.size();
+    // Temporarily use the Height field as scratch space for the degree count.
+    SU->Height = Degree;
+
+    // Is it a node without dependencies?
+    if (Degree == 0) {
+        assert(SU->Succs.empty() && "Something wrong");
+        assert(WorkList.empty() && "Should be empty");
+        // Collect leaf nodes
+        WorkList.push_back(SU);
+    }
+  }
+
+  // Process nodes in the topological order
+  while (!WorkList.empty()) {
+    SUnit *SU = WorkList.back();
+    WorkList.pop_back();
+    unsigned SUHeight = 0;
+
+    // Use dynamic programming:
+    // When current node is being processed, all of its dependencies
+    // are already processed.
+    // So, just iterate over all successors and take the longest path
+    for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+         I != E; ++I) {
+      unsigned SuccHeight = I->Dep->Height;
+      if (SuccHeight+1 > SUHeight) {
+          SUHeight = SuccHeight + 1;
+      }
+    }
+
+    SU->Height = SUHeight;
+
+    // Update degrees of all nodes depending on current SUnit
+    for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+         I != E; ++I) {
+      SUnit *SU = I->Dep;
+      if (!--SU->Height)
+        // If all dependencies of the node are processed already,
+        // then the longest path for the node can be computed now
+        WorkList.push_back(SU);
+    }
+  }
+}
+
+/// dump - dump the schedule.
+void ScheduleDAG::dumpSchedule() const {
+  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
+    if (SUnit *SU = Sequence[i])
+      SU->dump(this);
+    else
+      cerr << "**** NOOP ****\n";
+  }
+}
+
+
+/// Run - perform scheduling.
+///
+void ScheduleDAG::Run() {
+  Schedule();
+  
+  DOUT << "*** Final schedule ***\n";
+  DEBUG(dumpSchedule());
+  DOUT << "\n";
+}
+
+/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
+/// a group of nodes flagged together.
+void SUnit::dump(const ScheduleDAG *G) const {
+  cerr << "SU(" << NodeNum << "): ";
+  G->dumpNode(this);
+}
+
+void SUnit::dumpAll(const ScheduleDAG *G) const {
+  dump(G);
+
+  cerr << "  # preds left       : " << NumPredsLeft << "\n";
+  cerr << "  # succs left       : " << NumSuccsLeft << "\n";
+  cerr << "  Latency            : " << Latency << "\n";
+  cerr << "  Depth              : " << Depth << "\n";
+  cerr << "  Height             : " << Height << "\n";
+
+  if (Preds.size() != 0) {
+    cerr << "  Predecessors:\n";
+    for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
+         I != E; ++I) {
+      if (I->isCtrl)
+        cerr << "   ch  #";
+      else
+        cerr << "   val #";
+      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+      if (I->isSpecial)
+        cerr << " *";
+      cerr << "\n";
+    }
+  }
+  if (Succs.size() != 0) {
+    cerr << "  Successors:\n";
+    for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
+         I != E; ++I) {
+      if (I->isCtrl)
+        cerr << "   ch  #";
+      else
+        cerr << "   val #";
+      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+      if (I->isSpecial)
+        cerr << " *";
+      cerr << "\n";
+    }
+  }
+  cerr << "\n";
+}
diff --git a/lib/CodeGen/ScheduleDAGEmit.cpp b/lib/CodeGen/ScheduleDAGEmit.cpp
new file mode 100644
index 0000000..ce3283d
--- /dev/null
+++ b/lib/CodeGen/ScheduleDAGEmit.cpp
@@ -0,0 +1,72 @@
+//===---- ScheduleDAGEmit.cpp - Emit routines for the ScheduleDAG class ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This implements the Emit routines for the ScheduleDAG class, which creates
+// MachineInstrs according to the computed schedule.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "pre-RA-sched"
+#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/MachineConstantPool.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Target/TargetData.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetLowering.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/MathExtras.h"
+using namespace llvm;
+
+void ScheduleDAG::AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO) {
+  MI->addMemOperand(*MF, MO);
+}
+
+void ScheduleDAG::EmitNoop() {
+  TII->insertNoop(*BB, BB->end());
+}
+
+void ScheduleDAG::EmitCrossRCCopy(SUnit *SU,
+                                  DenseMap<SUnit*, unsigned> &VRBaseMap) {
+  for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+       I != E; ++I) {
+    if (I->isCtrl) continue;  // ignore chain preds
+    if (I->Dep->CopyDstRC) {
+      // Copy to physical register.
+      DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep);
+      assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
+      // Find the destination physical register.
+      unsigned Reg = 0;
+      for (SUnit::const_succ_iterator II = SU->Succs.begin(),
+             EE = SU->Succs.end(); II != EE; ++II) {
+        if (I->Reg) {
+          Reg = I->Reg;
+          break;
+        }
+      }
+      assert(I->Reg && "Unknown physical register!");
+      TII->copyRegToReg(*BB, BB->end(), Reg, VRI->second,
+                        SU->CopyDstRC, SU->CopySrcRC);
+    } else {
+      // Copy from physical register.
+      assert(I->Reg && "Unknown physical register!");
+      unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
+      bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
+      isNew = isNew; // Silence compiler warning.
+      assert(isNew && "Node emitted out of order - early");
+      TII->copyRegToReg(*BB, BB->end(), VRBase, I->Reg,
+                        SU->CopyDstRC, SU->CopySrcRC);
+    }
+    break;
+  }
+}
diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp
new file mode 100644
index 0000000..72008c9
--- /dev/null
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -0,0 +1,135 @@
+//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This implements the ScheduleDAG class, which is a base class used by
+// scheduling implementation classes.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "sched-instrs"
+#include "llvm/CodeGen/ScheduleDAGInstrs.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb,
+                                     const TargetMachine &tm)
+  : ScheduleDAG(0, bb, tm) {}
+
+void ScheduleDAGInstrs::BuildSchedUnits() {
+  SUnits.clear();
+  SUnits.reserve(BB->size());
+
+  std::vector<SUnit *> PendingLoads;
+  SUnit *Terminator = 0;
+  SUnit *Chain = 0;
+  SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {};
+  std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {};
+  int Cost = 1; // FIXME
+
+  for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin();
+       MII != MIE; --MII) {
+    MachineInstr *MI = prior(MII);
+    SUnit *SU = NewSUnit(MI);
+
+    for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
+      const MachineOperand &MO = MI->getOperand(j);
+      if (!MO.isReg()) continue;
+      unsigned Reg = MO.getReg();
+      if (Reg == 0) continue;
+
+      assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
+      std::vector<SUnit *> &UseList = Uses[Reg];
+      SUnit *&Def = Defs[Reg];
+      // Optionally add output and anti dependences
+      if (Def && Def != SU)
+        Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false,
+                     /*PhyReg=*/Reg, Cost);
+      for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
+        SUnit *&Def = Defs[*Alias];
+        if (Def && Def != SU)
+          Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false,
+                       /*PhyReg=*/*Alias, Cost);
+      }
+
+      if (MO.isDef()) {
+        // Add any data dependencies.
+        for (unsigned i = 0, e = UseList.size(); i != e; ++i)
+          if (UseList[i] != SU)
+            UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false,
+                                /*PhysReg=*/Reg, Cost);
+        for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
+          std::vector<SUnit *> &UseList = Uses[*Alias];
+          for (unsigned i = 0, e = UseList.size(); i != e; ++i)
+            if (UseList[i] != SU)
+              UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false,
+                                  /*PhysReg=*/*Alias, Cost);
+        }
+
+        UseList.clear();
+        Def = SU;
+      } else {
+        UseList.push_back(SU);
+      }
+    }
+    bool False = false;
+    bool True = true;
+    if (!MI->isSafeToMove(TII, False)) {
+      if (Chain)
+        Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
+      for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
+        PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
+      PendingLoads.clear();
+      Chain = SU;
+    } else if (!MI->isSafeToMove(TII, True)) {
+      if (Chain)
+        Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
+      PendingLoads.push_back(SU);
+    }
+    if (Terminator && SU->Succs.empty())
+      Terminator->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
+    if (MI->getDesc().isTerminator())
+      Terminator = SU;
+  }
+}
+
+void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
+  SU->getInstr()->dump();
+}
+
+std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
+  std::string s;
+  raw_string_ostream oss(s);
+  SU->getInstr()->print(oss);
+  return oss.str();
+}
+
+// EmitSchedule - Emit the machine code in scheduled order.
+MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
+  // For MachineInstr-based scheduling, we're rescheduling the instructions in
+  // the block, so start by removing them from the block.
+  while (!BB->empty())
+    BB->remove(BB->begin());
+
+  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
+    SUnit *SU = Sequence[i];
+    if (!SU) {
+      // Null SUnit* is a noop.
+      EmitNoop();
+      continue;
+    }
+
+    BB->push_back(SU->getInstr());
+  }
+
+  return BB;
+}
diff --git a/lib/CodeGen/ScheduleDAGPrinter.cpp b/lib/CodeGen/ScheduleDAGPrinter.cpp
new file mode 100644
index 0000000..b5d030c
--- /dev/null
+++ b/lib/CodeGen/ScheduleDAGPrinter.cpp
@@ -0,0 +1,93 @@
+//===-- ScheduleDAGPrinter.cpp - Implement ScheduleDAG::viewGraph() -------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This implements the ScheduleDAG::viewGraph method.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Constants.h"
+#include "llvm/Function.h"
+#include "llvm/Assembly/Writer.h"
+#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/MachineConstantPool.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/PseudoSourceValue.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/GraphWriter.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Config/config.h"
+#include <fstream>
+using namespace llvm;
+
+namespace llvm {
+  template<>
+  struct DOTGraphTraits<ScheduleDAG*> : public DefaultDOTGraphTraits {
+    static std::string getGraphName(const ScheduleDAG *G) {
+      return G->MF->getFunction()->getName();
+    }
+
+    static bool renderGraphFromBottomUp() {
+      return true;
+    }
+    
+    static bool hasNodeAddressLabel(const SUnit *Node,
+                                    const ScheduleDAG *Graph) {
+      return true;
+    }
+    
+    /// If you want to override the dot attributes printed for a particular
+    /// edge, override this method.
+    template<typename EdgeIter>
+    static std::string getEdgeAttributes(const void *Node, EdgeIter EI) {
+      if (EI.isSpecialDep())
+        return "color=cyan,style=dashed";
+      if (EI.isCtrlDep())
+        return "color=blue,style=dashed";
+      return "";
+    }
+    
+
+    static std::string getNodeLabel(const SUnit *Node,
+                                    const ScheduleDAG *Graph);
+    static std::string getNodeAttributes(const SUnit *N,
+                                         const ScheduleDAG *Graph) {
+      return "shape=Mrecord";
+    }
+
+    static void addCustomGraphFeatures(ScheduleDAG *G,
+                                       GraphWriter<ScheduleDAG*> &GW) {
+      return G->addCustomGraphFeatures(GW);
+    }
+  };
+}
+
+std::string DOTGraphTraits<ScheduleDAG*>::getNodeLabel(const SUnit *SU,
+                                                       const ScheduleDAG *G) {
+  return G->getGraphNodeLabel(SU);
+}
+
+/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG
+/// rendered using 'dot'.
+///
+void ScheduleDAG::viewGraph() {
+// This code is only for debugging!
+#ifndef NDEBUG
+  ViewGraph(this, "dag." + MF->getFunction()->getName(),
+            "Scheduling-Units Graph for " + MF->getFunction()->getName() + ':' +
+            BB->getBasicBlock()->getName());
+#else
+  cerr << "ScheduleDAG::viewGraph is only available in debug builds on "
+       << "systems with Graphviz or gv!\n";
+#endif  // NDEBUG
+}
diff --git a/lib/CodeGen/SelectionDAG/CMakeLists.txt b/lib/CodeGen/SelectionDAG/CMakeLists.txt
index a3654c2..186e3d1 100644
--- a/lib/CodeGen/SelectionDAG/CMakeLists.txt
+++ b/lib/CodeGen/SelectionDAG/CMakeLists.txt
@@ -2,15 +2,14 @@ add_llvm_library(LLVMSelectionDAG
   CallingConvLower.cpp
   DAGCombiner.cpp
   FastISel.cpp
-  LatencyPriorityQueue.cpp
   LegalizeDAG.cpp
   LegalizeFloatTypes.cpp
   LegalizeIntegerTypes.cpp
   LegalizeTypes.cpp
   LegalizeTypesGeneric.cpp
   LegalizeVectorTypes.cpp
-  ScheduleDAG.cpp
-  ScheduleDAGEmit.cpp
+  ScheduleDAGSDNodes.cpp
+  ScheduleDAGSDNodesEmit.cpp
   ScheduleDAGFast.cpp
   ScheduleDAGList.cpp
   ScheduleDAGRRList.cpp
diff --git a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h b/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h
deleted file mode 100644
index 5b2b02b..0000000
--- a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h
+++ /dev/null
@@ -1,124 +0,0 @@
-//===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file declares the LatencyPriorityQueue class, which is a
-// SchedulingPriorityQueue that schedules using latency information to
-// reduce the length of the critical path through the basic block.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LATENCY_PRIORITY_QUEUE_H
-#define LATENCY_PRIORITY_QUEUE_H
-
-#include "llvm/CodeGen/ScheduleDAG.h"
-#include "llvm/ADT/PriorityQueue.h"
-
-namespace llvm {
-  class LatencyPriorityQueue;
-  
-  /// Sorting functions for the Available queue.
-  struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> {
-    LatencyPriorityQueue *PQ;
-    explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
-    
-    bool operator()(const SUnit* left, const SUnit* right) const;
-  };
-
-  class LatencyPriorityQueue : public SchedulingPriorityQueue {
-    // SUnits - The SUnits for the current graph.
-    std::vector<SUnit> *SUnits;
-    
-    // Latencies - The latency (max of latency from this node to the bb exit)
-    // for each node.
-    std::vector<int> Latencies;
-
-    /// NumNodesSolelyBlocking - This vector contains, for every node in the
-    /// Queue, the number of nodes that the node is the sole unscheduled
-    /// predecessor for.  This is used as a tie-breaker heuristic for better
-    /// mobility.
-    std::vector<unsigned> NumNodesSolelyBlocking;
-
-    PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
-  public:
-    LatencyPriorityQueue() : Queue(latency_sort(this)) {
-    }
-    
-    void initNodes(std::vector<SUnit> &sunits) {
-      SUnits = &sunits;
-      // Calculate node priorities.
-      CalculatePriorities();
-    }
-
-    void addNode(const SUnit *SU) {
-      Latencies.resize(SUnits->size(), -1);
-      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
-      CalcLatency(*SU);
-    }
-
-    void updateNode(const SUnit *SU) {
-      Latencies[SU->NodeNum] = -1;
-      CalcLatency(*SU);
-    }
-
-    void releaseState() {
-      SUnits = 0;
-      Latencies.clear();
-    }
-    
-    unsigned getLatency(unsigned NodeNum) const {
-      assert(NodeNum < Latencies.size());
-      return Latencies[NodeNum];
-    }
-    
-    unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
-      assert(NodeNum < NumNodesSolelyBlocking.size());
-      return NumNodesSolelyBlocking[NodeNum];
-    }
-    
-    unsigned size() const { return Queue.size(); }
-
-    bool empty() const { return Queue.empty(); }
-    
-    virtual void push(SUnit *U) {
-      push_impl(U);
-    }
-    void push_impl(SUnit *U);
-    
-    void push_all(const std::vector<SUnit *> &Nodes) {
-      for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
-        push_impl(Nodes[i]);
-    }
-    
-    SUnit *pop() {
-      if (empty()) return NULL;
-      SUnit *V = Queue.top();
-      Queue.pop();
-      return V;
-    }
-
-    void remove(SUnit *SU) {
-      assert(!Queue.empty() && "Not in queue!");
-      Queue.erase_one(SU);
-    }
-
-    // ScheduledNode - As nodes are scheduled, we look to see if there are any
-    // successor nodes that have a single unscheduled predecessor.  If so, that
-    // single predecessor has a higher priority, since scheduling it will make
-    // the node available.
-    void ScheduledNode(SUnit *Node);
-
-  private:
-    void CalculatePriorities();
-    int CalcLatency(const SUnit &SU);
-    void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
-    SUnit *getSingleUnscheduledPred(SUnit *SU);
-  };
-}
-
-#endif
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
deleted file mode 100644
index c2e2175..0000000
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ /dev/null
@@ -1,522 +0,0 @@
-//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This implements the ScheduleDAG class, which is a base class used by
-// scheduling implementation classes.
-//
-//===----------------------------------------------------------------------===//
-
-#define DEBUG_TYPE "pre-RA-sched"
-#include "llvm/CodeGen/ScheduleDAG.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-using namespace llvm;
-
-ScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
-                         const TargetMachine &tm)
-  : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) {
-  TII = TM.getInstrInfo();
-  MF  = BB->getParent();
-  TRI = TM.getRegisterInfo();
-  TLI = TM.getTargetLowering();
-  ConstPool = MF->getConstantPool();
-}
-
-/// CheckForPhysRegDependency - Check if the dependency between def and use of
-/// a specified operand is a physical register dependency. If so, returns the
-/// register and the cost of copying the register.
-static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
-                                      const TargetRegisterInfo *TRI, 
-                                      const TargetInstrInfo *TII,
-                                      unsigned &PhysReg, int &Cost) {
-  if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
-    return;
-
-  unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
-  if (TargetRegisterInfo::isVirtualRegister(Reg))
-    return;
-
-  unsigned ResNo = User->getOperand(2).getResNo();
-  if (Def->isMachineOpcode()) {
-    const TargetInstrDesc &II = TII->get(Def->getMachineOpcode());
-    if (ResNo >= II.getNumDefs() &&
-        II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) {
-      PhysReg = Reg;
-      const TargetRegisterClass *RC =
-        TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo));
-      Cost = RC->getCopyCost();
-    }
-  }
-}
-
-SUnit *ScheduleDAG::Clone(SUnit *Old) {
-  SUnit *SU = NewSUnit(Old->getNode());
-  SU->OrigNode = Old->OrigNode;
-  SU->Latency = Old->Latency;
-  SU->isTwoAddress = Old->isTwoAddress;
-  SU->isCommutable = Old->isCommutable;
-  SU->hasPhysRegDefs = Old->hasPhysRegDefs;
-  return SU;
-}
-
-
-/// BuildSchedUnits - Build SUnits from the selection dag that we are input.
-/// This SUnit graph is similar to the SelectionDAG, but represents flagged
-/// together nodes with a single SUnit.
-void ScheduleDAG::BuildSchedUnits() {
-  // For post-regalloc scheduling, build the SUnits from the MachineInstrs
-  // in the MachineBasicBlock.
-  if (!DAG) {
-    BuildSchedUnitsFromMBB();
-    return;
-  }
-
-  // Reserve entries in the vector for each of the SUnits we are creating.  This
-  // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
-  // invalidated.
-  SUnits.reserve(DAG->allnodes_size());
-  
-  // During scheduling, the NodeId field of SDNode is used to map SDNodes
-  // to their associated SUnits by holding SUnits table indices. A value
-  // of -1 means the SDNode does not yet have an associated SUnit.
-  for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
-       E = DAG->allnodes_end(); NI != E; ++NI)
-    NI->setNodeId(-1);
-
-  for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
-       E = DAG->allnodes_end(); NI != E; ++NI) {
-    if (isPassiveNode(NI))  // Leaf node, e.g. a TargetImmediate.
-      continue;
-    
-    // If this node has already been processed, stop now.
-    if (NI->getNodeId() != -1) continue;
-    
-    SUnit *NodeSUnit = NewSUnit(NI);
-    
-    // See if anything is flagged to this node, if so, add them to flagged
-    // nodes.  Nodes can have at most one flag input and one flag output.  Flags
-    // are required the be the last operand and result of a node.
-    
-    // Scan up to find flagged preds.
-    SDNode *N = NI;
-    if (N->getNumOperands() &&
-        N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
-      do {
-        N = N->getOperand(N->getNumOperands()-1).getNode();
-        assert(N->getNodeId() == -1 && "Node already inserted!");
-        N->setNodeId(NodeSUnit->NodeNum);
-      } while (N->getNumOperands() &&
-               N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
-    }
-    
-    // Scan down to find any flagged succs.
-    N = NI;
-    while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
-      SDValue FlagVal(N, N->getNumValues()-1);
-      
-      // There are either zero or one users of the Flag result.
-      bool HasFlagUse = false;
-      for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 
-           UI != E; ++UI)
-        if (FlagVal.isOperandOf(*UI)) {
-          HasFlagUse = true;
-          assert(N->getNodeId() == -1 && "Node already inserted!");
-          N->setNodeId(NodeSUnit->NodeNum);
-          N = *UI;
-          break;
-        }
-      if (!HasFlagUse) break;
-    }
-    
-    // If there are flag operands involved, N is now the bottom-most node
-    // of the sequence of nodes that are flagged together.
-    // Update the SUnit.
-    NodeSUnit->setNode(N);
-    assert(N->getNodeId() == -1 && "Node already inserted!");
-    N->setNodeId(NodeSUnit->NodeNum);
-
-    ComputeLatency(NodeSUnit);
-  }
-  
-  // Pass 2: add the preds, succs, etc.
-  for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
-    SUnit *SU = &SUnits[su];
-    SDNode *MainNode = SU->getNode();
-    
-    if (MainNode->isMachineOpcode()) {
-      unsigned Opc = MainNode->getMachineOpcode();
-      const TargetInstrDesc &TID = TII->get(Opc);
-      for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
-        if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
-          SU->isTwoAddress = true;
-          break;
-        }
-      }
-      if (TID.isCommutable())
-        SU->isCommutable = true;
-    }
-    
-    // Find all predecessors and successors of the group.
-    for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
-      if (N->isMachineOpcode() &&
-          TII->get(N->getMachineOpcode()).getImplicitDefs() &&
-          CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs())
-        SU->hasPhysRegDefs = true;
-      
-      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
-        SDNode *OpN = N->getOperand(i).getNode();
-        if (isPassiveNode(OpN)) continue;   // Not scheduled.
-        SUnit *OpSU = &SUnits[OpN->getNodeId()];
-        assert(OpSU && "Node has no SUnit!");
-        if (OpSU == SU) continue;           // In the same group.
-
-        MVT OpVT = N->getOperand(i).getValueType();
-        assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
-        bool isChain = OpVT == MVT::Other;
-
-        unsigned PhysReg = 0;
-        int Cost = 1;
-        // Determine if this is a physical register dependency.
-        CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
-        SU->addPred(OpSU, isChain, false, PhysReg, Cost);
-      }
-    }
-  }
-}
-
-void ScheduleDAG::BuildSchedUnitsFromMBB() {
-  SUnits.clear();
-  SUnits.reserve(BB->size());
-
-  std::vector<SUnit *> PendingLoads;
-  SUnit *Terminator = 0;
-  SUnit *Chain = 0;
-  SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {};
-  std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {};
-  int Cost = 1; // FIXME
-
-  for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin();
-       MII != MIE; --MII) {
-    MachineInstr *MI = prior(MII);
-    SUnit *SU = NewSUnit(MI);
-
-    for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
-      const MachineOperand &MO = MI->getOperand(j);
-      if (!MO.isReg()) continue;
-      unsigned Reg = MO.getReg();
-      if (Reg == 0) continue;
-
-      assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
-      std::vector<SUnit *> &UseList = Uses[Reg];
-      SUnit *&Def = Defs[Reg];
-      // Optionally add output and anti dependences
-      if (Def && Def != SU)
-        Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false,
-                     /*PhyReg=*/Reg, Cost);
-      for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
-        SUnit *&Def = Defs[*Alias];
-        if (Def && Def != SU)
-          Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false,
-                       /*PhyReg=*/*Alias, Cost);
-      }
-
-      if (MO.isDef()) {
-        // Add any data dependencies.
-        for (unsigned i = 0, e = UseList.size(); i != e; ++i)
-          if (UseList[i] != SU)
-            UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false,
-                                /*PhysReg=*/Reg, Cost);
-        for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
-          std::vector<SUnit *> &UseList = Uses[*Alias];
-          for (unsigned i = 0, e = UseList.size(); i != e; ++i)
-            if (UseList[i] != SU)
-              UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false,
-                                  /*PhysReg=*/*Alias, Cost);
-        }
-
-        UseList.clear();
-        Def = SU;
-      } else {
-        UseList.push_back(SU);
-      }
-    }
-    bool False = false;
-    bool True = true;
-    if (!MI->isSafeToMove(TII, False)) {
-      if (Chain)
-        Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
-      for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
-        PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
-      PendingLoads.clear();
-      Chain = SU;
-    } else if (!MI->isSafeToMove(TII, True)) {
-      if (Chain)
-        Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
-      PendingLoads.push_back(SU);
-    }
-    if (Terminator && SU->Succs.empty())
-      Terminator->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
-    if (MI->getDesc().isTerminator())
-      Terminator = SU;
-  }
-}
-
-void ScheduleDAG::ComputeLatency(SUnit *SU) {
-  const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
-  
-  // Compute the latency for the node.  We use the sum of the latencies for
-  // all nodes flagged together into this SUnit.
-  if (InstrItins.isEmpty()) {
-    // No latency information.
-    SU->Latency = 1;
-    return;
-  }
-
-  SU->Latency = 0;
-  for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
-    if (N->isMachineOpcode()) {
-      unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass();
-      const InstrStage *S = InstrItins.begin(SchedClass);
-      const InstrStage *E = InstrItins.end(SchedClass);
-      for (; S != E; ++S)
-        SU->Latency += S->Cycles;
-    }
-  }
-}
-
-/// CalculateDepths - compute depths using algorithms for the longest
-/// paths in the DAG
-void ScheduleDAG::CalculateDepths() {
-  unsigned DAGSize = SUnits.size();
-  std::vector<SUnit*> WorkList;
-  WorkList.reserve(DAGSize);
-
-  // Initialize the data structures
-  for (unsigned i = 0, e = DAGSize; i != e; ++i) {
-    SUnit *SU = &SUnits[i];
-    unsigned Degree = SU->Preds.size();
-    // Temporarily use the Depth field as scratch space for the degree count.
-    SU->Depth = Degree;
-
-    // Is it a node without dependencies?
-    if (Degree == 0) {
-        assert(SU->Preds.empty() && "SUnit should have no predecessors");
-        // Collect leaf nodes
-        WorkList.push_back(SU);
-    }
-  }
-
-  // Process nodes in the topological order
-  while (!WorkList.empty()) {
-    SUnit *SU = WorkList.back();
-    WorkList.pop_back();
-    unsigned SUDepth = 0;
-
-    // Use dynamic programming:
-    // When current node is being processed, all of its dependencies
-    // are already processed.
-    // So, just iterate over all predecessors and take the longest path
-    for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
-         I != E; ++I) {
-      unsigned PredDepth = I->Dep->Depth;
-      if (PredDepth+1 > SUDepth) {
-          SUDepth = PredDepth + 1;
-      }
-    }
-
-    SU->Depth = SUDepth;
-
-    // Update degrees of all nodes depending on current SUnit
-    for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
-         I != E; ++I) {
-      SUnit *SU = I->Dep;
-      if (!--SU->Depth)
-        // If all dependencies of the node are processed already,
-        // then the longest path for the node can be computed now
-        WorkList.push_back(SU);
-    }
-  }
-}
-
-/// CalculateHeights - compute heights using algorithms for the longest
-/// paths in the DAG
-void ScheduleDAG::CalculateHeights() {
-  unsigned DAGSize = SUnits.size();
-  std::vector<SUnit*> WorkList;
-  WorkList.reserve(DAGSize);
-
-  // Initialize the data structures
-  for (unsigned i = 0, e = DAGSize; i != e; ++i) {
-    SUnit *SU = &SUnits[i];
-    unsigned Degree = SU->Succs.size();
-    // Temporarily use the Height field as scratch space for the degree count.
-    SU->Height = Degree;
-
-    // Is it a node without dependencies?
-    if (Degree == 0) {
-        assert(SU->Succs.empty() && "Something wrong");
-        assert(WorkList.empty() && "Should be empty");
-        // Collect leaf nodes
-        WorkList.push_back(SU);
-    }
-  }
-
-  // Process nodes in the topological order
-  while (!WorkList.empty()) {
-    SUnit *SU = WorkList.back();
-    WorkList.pop_back();
-    unsigned SUHeight = 0;
-
-    // Use dynamic programming:
-    // When current node is being processed, all of its dependencies
-    // are already processed.
-    // So, just iterate over all successors and take the longest path
-    for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
-         I != E; ++I) {
-      unsigned SuccHeight = I->Dep->Height;
-      if (SuccHeight+1 > SUHeight) {
-          SUHeight = SuccHeight + 1;
-      }
-    }
-
-    SU->Height = SUHeight;
-
-    // Update degrees of all nodes depending on current SUnit
-    for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
-         I != E; ++I) {
-      SUnit *SU = I->Dep;
-      if (!--SU->Height)
-        // If all dependencies of the node are processed already,
-        // then the longest path for the node can be computed now
-        WorkList.push_back(SU);
-    }
-  }
-}
-
-/// CountResults - The results of target nodes have register or immediate
-/// operands first, then an optional chain, and optional flag operands (which do
-/// not go into the resulting MachineInstr).
-unsigned ScheduleDAG::CountResults(SDNode *Node) {
-  unsigned N = Node->getNumValues();
-  while (N && Node->getValueType(N - 1) == MVT::Flag)
-    --N;
-  if (N && Node->getValueType(N - 1) == MVT::Other)
-    --N;    // Skip over chain result.
-  return N;
-}
-
-/// CountOperands - The inputs to target nodes have any actual inputs first,
-/// followed by special operands that describe memory references, then an
-/// optional chain operand, then an optional flag operand.  Compute the number
-/// of actual operands that will go into the resulting MachineInstr.
-unsigned ScheduleDAG::CountOperands(SDNode *Node) {
-  unsigned N = ComputeMemOperandsEnd(Node);
-  while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode()))
-    --N; // Ignore MEMOPERAND nodes
-  return N;
-}
-
-/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode
-/// operand
-unsigned ScheduleDAG::ComputeMemOperandsEnd(SDNode *Node) {
-  unsigned N = Node->getNumOperands();
-  while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
-    --N;
-  if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
-    --N; // Ignore chain if it exists.
-  return N;
-}
-
-
-/// dump - dump the schedule.
-void ScheduleDAG::dumpSchedule() const {
-  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
-    if (SUnit *SU = Sequence[i])
-      SU->dump(this);
-    else
-      cerr << "**** NOOP ****\n";
-  }
-}
-
-
-/// Run - perform scheduling.
-///
-void ScheduleDAG::Run() {
-  Schedule();
-  
-  DOUT << "*** Final schedule ***\n";
-  DEBUG(dumpSchedule());
-  DOUT << "\n";
-}
-
-/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
-/// a group of nodes flagged together.
-void SUnit::print(raw_ostream &O, const ScheduleDAG *G) const {
-  O << "SU(" << NodeNum << "): ";
-  if (getNode()) {
-    SmallVector<SDNode *, 4> FlaggedNodes;
-    for (SDNode *N = getNode(); N; N = N->getFlaggedNode())
-      FlaggedNodes.push_back(N);
-    while (!FlaggedNodes.empty()) {
-      O << "    ";
-      FlaggedNodes.back()->print(O, G->DAG);
-      O << "\n";
-      FlaggedNodes.pop_back();
-    }
-  } else {
-    O << "CROSS RC COPY\n";
-  }
-}
-
-void SUnit::dump(const ScheduleDAG *G) const {
-  print(errs(), G);
-}
-
-void SUnit::dumpAll(const ScheduleDAG *G) const {
-  dump(G);
-
-  cerr << "  # preds left       : " << NumPredsLeft << "\n";
-  cerr << "  # succs left       : " << NumSuccsLeft << "\n";
-  cerr << "  Latency            : " << Latency << "\n";
-  cerr << "  Depth              : " << Depth << "\n";
-  cerr << "  Height             : " << Height << "\n";
-
-  if (Preds.size() != 0) {
-    cerr << "  Predecessors:\n";
-    for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
-         I != E; ++I) {
-      if (I->isCtrl)
-        cerr << "   ch  #";
-      else
-        cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
-      if (I->isSpecial)
-        cerr << " *";
-      cerr << "\n";
-    }
-  }
-  if (Succs.size() != 0) {
-    cerr << "  Successors:\n";
-    for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
-         I != E; ++I) {
-      if (I->isCtrl)
-        cerr << "   ch  #";
-      else
-        cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
-      if (I->isSpecial)
-        cerr << " *";
-      cerr << "\n";
-    }
-  }
-  cerr << "\n";
-}
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp
index 0af0358..8f3198e 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp
@@ -12,7 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "pre-RA-sched"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
 #include "llvm/CodeGen/SchedulerRegistry.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetData.h"
@@ -58,7 +58,7 @@ namespace {
 //===----------------------------------------------------------------------===//
 /// ScheduleDAGFast - The actual "fast" list scheduler implementation.
 ///
-class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAG {
+class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAGSDNodes {
 private:
   /// AvailableQueue - The priority queue to use for the available SUnits.
   FastPriorityQueue AvailableQueue;
@@ -73,7 +73,7 @@ private:
 public:
   ScheduleDAGFast(SelectionDAG *dag, MachineBasicBlock *bb,
                   const TargetMachine &tm)
-    : ScheduleDAG(dag, bb, tm) {}
+    : ScheduleDAGSDNodes(dag, bb, tm) {}
 
   void Schedule();
 
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index c2c9110..e1a24a1 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -19,7 +19,8 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "pre-RA-sched"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/LatencyPriorityQueue.h"
+#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
 #include "llvm/CodeGen/SchedulerRegistry.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/Target/TargetRegisterInfo.h"
@@ -30,7 +31,6 @@
 #include "llvm/Support/Compiler.h"
 #include "llvm/ADT/PriorityQueue.h"
 #include "llvm/ADT/Statistic.h"
-#include "LatencyPriorityQueue.h"
 #include <climits>
 using namespace llvm;
 
@@ -46,7 +46,7 @@ namespace {
 /// ScheduleDAGList - The actual list scheduler implementation.  This supports
 /// top-down scheduling.
 ///
-class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAG {
+class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAGSDNodes {
 private:
   /// AvailableQueue - The priority queue to use for the available SUnits.
   ///
@@ -66,7 +66,7 @@ public:
                   const TargetMachine &tm,
                   SchedulingPriorityQueue *availqueue,
                   HazardRecognizer *HR)
-    : ScheduleDAG(dag, bb, tm),
+    : ScheduleDAGSDNodes(dag, bb, tm),
       AvailableQueue(availqueue), HazardRec(HR) {
     }
 
@@ -212,13 +212,13 @@ void ScheduleDAGList::ListScheduleTopDown() {
         if (!N) break;
         FoundNode = N;
       }
-      
+    
       HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode);
       if (HT == HazardRecognizer::NoHazard) {
         FoundSUnit = CurSUnit;
         break;
       }
-      
+    
       // Remember if this is a noop hazard.
       HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
       
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index 7c3f6bb..45a1ca0 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -16,7 +16,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "pre-RA-sched"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
 #include "llvm/CodeGen/SchedulerRegistry.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetData.h"
@@ -53,7 +53,7 @@ namespace {
 /// ScheduleDAGRRList - The actual register reduction list scheduler
 /// implementation.  This supports both top-down and bottom-up scheduling.
 ///
-class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG {
+class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes {
 private:
   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
   /// it is top-down.
@@ -77,7 +77,7 @@ public:
   ScheduleDAGRRList(SelectionDAG *dag, MachineBasicBlock *bb,
                     const TargetMachine &tm, bool isbottomup, bool f,
                     SchedulingPriorityQueue *availqueue)
-    : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), Fast(f),
+    : ScheduleDAGSDNodes(dag, bb, tm), isBottomUp(isbottomup), Fast(f),
       AvailableQueue(availqueue) {
     }
 
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
new file mode 100644
index 0000000..9d32d9a
--- /dev/null
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
@@ -0,0 +1,257 @@
+//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This implements the ScheduleDAG class, which is a base class used by
+// scheduling implementation classes.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "pre-RA-sched"
+#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
+#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+ScheduleDAGSDNodes::ScheduleDAGSDNodes(SelectionDAG *dag, MachineBasicBlock *bb,
+                                       const TargetMachine &tm)
+  : ScheduleDAG(dag, bb, tm) {
+}
+
+SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {
+  SUnit *SU = NewSUnit(Old->getNode());
+  SU->OrigNode = Old->OrigNode;
+  SU->Latency = Old->Latency;
+  SU->isTwoAddress = Old->isTwoAddress;
+  SU->isCommutable = Old->isCommutable;
+  SU->hasPhysRegDefs = Old->hasPhysRegDefs;
+  return SU;
+}
+
+/// CheckForPhysRegDependency - Check if the dependency between def and use of
+/// a specified operand is a physical register dependency. If so, returns the
+/// register and the cost of copying the register.
+static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
+                                      const TargetRegisterInfo *TRI, 
+                                      const TargetInstrInfo *TII,
+                                      unsigned &PhysReg, int &Cost) {
+  if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
+    return;
+
+  unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
+  if (TargetRegisterInfo::isVirtualRegister(Reg))
+    return;
+
+  unsigned ResNo = User->getOperand(2).getResNo();
+  if (Def->isMachineOpcode()) {
+    const TargetInstrDesc &II = TII->get(Def->getMachineOpcode());
+    if (ResNo >= II.getNumDefs() &&
+        II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) {
+      PhysReg = Reg;
+      const TargetRegisterClass *RC =
+        TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo));
+      Cost = RC->getCopyCost();
+    }
+  }
+}
+
+/// BuildSchedUnits - Build SUnits from the selection dag that we are input.
+/// This SUnit graph is similar to the SelectionDAG, but represents flagged
+/// together nodes with a single SUnit.
+void ScheduleDAGSDNodes::BuildSchedUnits() {
+  // Reserve entries in the vector for each of the SUnits we are creating.  This
+  // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
+  // invalidated.
+  SUnits.reserve(DAG->allnodes_size());
+  
+  // During scheduling, the NodeId field of SDNode is used to map SDNodes
+  // to their associated SUnits by holding SUnits table indices. A value
+  // of -1 means the SDNode does not yet have an associated SUnit.
+  for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
+       E = DAG->allnodes_end(); NI != E; ++NI)
+    NI->setNodeId(-1);
+
+  for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
+       E = DAG->allnodes_end(); NI != E; ++NI) {
+    if (isPassiveNode(NI))  // Leaf node, e.g. a TargetImmediate.
+      continue;
+    
+    // If this node has already been processed, stop now.
+    if (NI->getNodeId() != -1) continue;
+    
+    SUnit *NodeSUnit = NewSUnit(NI);
+    
+    // See if anything is flagged to this node, if so, add them to flagged
+    // nodes.  Nodes can have at most one flag input and one flag output.  Flags
+    // are required the be the last operand and result of a node.
+    
+    // Scan up to find flagged preds.
+    SDNode *N = NI;
+    if (N->getNumOperands() &&
+        N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
+      do {
+        N = N->getOperand(N->getNumOperands()-1).getNode();
+        assert(N->getNodeId() == -1 && "Node already inserted!");
+        N->setNodeId(NodeSUnit->NodeNum);
+      } while (N->getNumOperands() &&
+               N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
+    }
+    
+    // Scan down to find any flagged succs.
+    N = NI;
+    while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
+      SDValue FlagVal(N, N->getNumValues()-1);
+      
+      // There are either zero or one users of the Flag result.
+      bool HasFlagUse = false;
+      for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 
+           UI != E; ++UI)
+        if (FlagVal.isOperandOf(*UI)) {
+          HasFlagUse = true;
+          assert(N->getNodeId() == -1 && "Node already inserted!");
+          N->setNodeId(NodeSUnit->NodeNum);
+          N = *UI;
+          break;
+        }
+      if (!HasFlagUse) break;
+    }
+    
+    // If there are flag operands involved, N is now the bottom-most node
+    // of the sequence of nodes that are flagged together.
+    // Update the SUnit.
+    NodeSUnit->setNode(N);
+    assert(N->getNodeId() == -1 && "Node already inserted!");
+    N->setNodeId(NodeSUnit->NodeNum);
+
+    ComputeLatency(NodeSUnit);
+  }
+  
+  // Pass 2: add the preds, succs, etc.
+  for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
+    SUnit *SU = &SUnits[su];
+    SDNode *MainNode = SU->getNode();
+    
+    if (MainNode->isMachineOpcode()) {
+      unsigned Opc = MainNode->getMachineOpcode();
+      const TargetInstrDesc &TID = TII->get(Opc);
+      for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
+        if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
+          SU->isTwoAddress = true;
+          break;
+        }
+      }
+      if (TID.isCommutable())
+        SU->isCommutable = true;
+    }
+    
+    // Find all predecessors and successors of the group.
+    for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
+      if (N->isMachineOpcode() &&
+          TII->get(N->getMachineOpcode()).getImplicitDefs() &&
+          CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs())
+        SU->hasPhysRegDefs = true;
+      
+      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
+        SDNode *OpN = N->getOperand(i).getNode();
+        if (isPassiveNode(OpN)) continue;   // Not scheduled.
+        SUnit *OpSU = &SUnits[OpN->getNodeId()];
+        assert(OpSU && "Node has no SUnit!");
+        if (OpSU == SU) continue;           // In the same group.
+
+        MVT OpVT = N->getOperand(i).getValueType();
+        assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
+        bool isChain = OpVT == MVT::Other;
+
+        unsigned PhysReg = 0;
+        int Cost = 1;
+        // Determine if this is a physical register dependency.
+        CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
+        SU->addPred(OpSU, isChain, false, PhysReg, Cost);
+      }
+    }
+  }
+}
+
+void ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) {
+  const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
+  
+  // Compute the latency for the node.  We use the sum of the latencies for
+  // all nodes flagged together into this SUnit.
+  if (InstrItins.isEmpty()) {
+    // No latency information.
+    SU->Latency = 1;
+    return;
+  }
+
+  SU->Latency = 0;
+  for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
+    if (N->isMachineOpcode()) {
+      unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass();
+      const InstrStage *S = InstrItins.begin(SchedClass);
+      const InstrStage *E = InstrItins.end(SchedClass);
+      for (; S != E; ++S)
+        SU->Latency += S->Cycles;
+    }
+  }
+}
+
+/// CountResults - The results of target nodes have register or immediate
+/// operands first, then an optional chain, and optional flag operands (which do
+/// not go into the resulting MachineInstr).
+unsigned ScheduleDAGSDNodes::CountResults(SDNode *Node) {
+  unsigned N = Node->getNumValues();
+  while (N && Node->getValueType(N - 1) == MVT::Flag)
+    --N;
+  if (N && Node->getValueType(N - 1) == MVT::Other)
+    --N;    // Skip over chain result.
+  return N;
+}
+
+/// CountOperands - The inputs to target nodes have any actual inputs first,
+/// followed by special operands that describe memory references, then an
+/// optional chain operand, then an optional flag operand.  Compute the number
+/// of actual operands that will go into the resulting MachineInstr.
+unsigned ScheduleDAGSDNodes::CountOperands(SDNode *Node) {
+  unsigned N = ComputeMemOperandsEnd(Node);
+  while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode()))
+    --N; // Ignore MEMOPERAND nodes
+  return N;
+}
+
+/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode
+/// operand
+unsigned ScheduleDAGSDNodes::ComputeMemOperandsEnd(SDNode *Node) {
+  unsigned N = Node->getNumOperands();
+  while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
+    --N;
+  if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
+    --N; // Ignore chain if it exists.
+  return N;
+}
+
+
+void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const {
+  if (SU->getNode())
+    SU->getNode()->dump(DAG);
+  else
+    cerr << "CROSS RC COPY ";
+  cerr << "\n";
+  SmallVector<SDNode *, 4> FlaggedNodes;
+  for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode())
+    FlaggedNodes.push_back(N);
+  while (!FlaggedNodes.empty()) {
+    cerr << "    ";
+    FlaggedNodes.back()->dump(DAG);
+    cerr << "\n";
+    FlaggedNodes.pop_back();
+  }
+}
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
index 0c67973..dc9313b 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
@@ -13,7 +13,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "pre-RA-sched"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -47,9 +47,9 @@ getInstrOperandRegClass(const TargetRegisterInfo *TRI,
 
 /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an
 /// implicit physical register output.
-void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
-                                  bool IsClone, unsigned SrcReg,
-                                  DenseMap<SDValue, unsigned> &VRBaseMap) {
+void ScheduleDAGSDNodes::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
+                                         bool IsClone, unsigned SrcReg,
+                                         DenseMap<SDValue, unsigned> &VRBaseMap) {
   unsigned VRBase = 0;
   if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
     // Just use the input register directly!
@@ -142,8 +142,8 @@ void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
 
 /// getDstOfCopyToRegUse - If the only use of the specified result number of
 /// node is a CopyToReg, return its destination register. Return 0 otherwise.
-unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node,
-                                               unsigned ResNo) const {
+unsigned ScheduleDAGSDNodes::getDstOfOnlyCopyToRegUse(SDNode *Node,
+                                                      unsigned ResNo) const {
   if (!Node->hasOneUse())
     return 0;
 
@@ -158,7 +158,7 @@ unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node,
   return 0;
 }
 
-void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
+void ScheduleDAGSDNodes::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
                                  const TargetInstrDesc &II,
                                  DenseMap<SDValue, unsigned> &VRBaseMap) {
   assert(Node->getMachineOpcode() != TargetInstrInfo::IMPLICIT_DEF &&
@@ -202,8 +202,8 @@ void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
 
 /// getVR - Return the virtual register corresponding to the specified result
 /// of the specified node.
-unsigned ScheduleDAG::getVR(SDValue Op,
-                            DenseMap<SDValue, unsigned> &VRBaseMap) {
+unsigned ScheduleDAGSDNodes::getVR(SDValue Op,
+                                   DenseMap<SDValue, unsigned> &VRBaseMap) {
   if (Op.isMachineOpcode() &&
       Op.getMachineOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
     // Add an IMPLICIT_DEF instruction before every use.
@@ -228,10 +228,10 @@ unsigned ScheduleDAG::getVR(SDValue Op,
 /// specifies the instruction information for the node, and IIOpNum is the
 /// operand number (in the II) that we are adding. IIOpNum and II are used for 
 /// assertions only.
-void ScheduleDAG::AddOperand(MachineInstr *MI, SDValue Op,
-                             unsigned IIOpNum,
-                             const TargetInstrDesc *II,
-                             DenseMap<SDValue, unsigned> &VRBaseMap) {
+void ScheduleDAGSDNodes::AddOperand(MachineInstr *MI, SDValue Op,
+                                    unsigned IIOpNum,
+                                    const TargetInstrDesc *II,
+                                    DenseMap<SDValue, unsigned> &VRBaseMap) {
   if (Op.isMachineOpcode()) {
     // Note that this case is redundant with the final else block, but we
     // include it because it is the most common and it makes the logic
@@ -328,10 +328,6 @@ void ScheduleDAG::AddOperand(MachineInstr *MI, SDValue Op,
   }  
 }
 
-void ScheduleDAG::AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO) {
-  MI->addMemOperand(*MF, MO);
-}
-
 /// getSubRegisterRegClass - Returns the register class of specified register
 /// class' "SubIdx"'th sub-register class.
 static const TargetRegisterClass*
@@ -361,8 +357,8 @@ getSuperRegisterRegClass(const TargetRegisterClass *TRC,
 
 /// EmitSubregNode - Generate machine code for subreg nodes.
 ///
-void ScheduleDAG::EmitSubregNode(SDNode *Node, 
-                           DenseMap<SDValue, unsigned> &VRBaseMap) {
+void ScheduleDAGSDNodes::EmitSubregNode(SDNode *Node, 
+                                        DenseMap<SDValue, unsigned> &VRBaseMap) {
   unsigned VRBase = 0;
   unsigned Opc = Node->getMachineOpcode();
   
@@ -456,8 +452,8 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node,
 
 /// EmitNode - Generate machine code for an node and needed dependencies.
 ///
-void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone,
-                           DenseMap<SDValue, unsigned> &VRBaseMap) {
+void ScheduleDAGSDNodes::EmitNode(SDNode *Node, bool IsClone,
+                                  DenseMap<SDValue, unsigned> &VRBaseMap) {
   // If machine instruction
   if (Node->isMachineOpcode()) {
     unsigned Opc = Node->getMachineOpcode();
@@ -634,53 +630,8 @@ void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone,
   }
 }
 
-void ScheduleDAG::EmitNoop() {
-  TII->insertNoop(*BB, BB->end());
-}
-
-void ScheduleDAG::EmitCrossRCCopy(SUnit *SU,
-                                  DenseMap<SUnit*, unsigned> &VRBaseMap) {
-  for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
-       I != E; ++I) {
-    if (I->isCtrl) continue;  // ignore chain preds
-    if (!I->Dep->getNode()) {
-      // Copy to physical register.
-      DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep);
-      assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
-      // Find the destination physical register.
-      unsigned Reg = 0;
-      for (SUnit::const_succ_iterator II = SU->Succs.begin(),
-             EE = SU->Succs.end(); II != EE; ++II) {
-        if (I->Reg) {
-          Reg = I->Reg;
-          break;
-        }
-      }
-      assert(I->Reg && "Unknown physical register!");
-      TII->copyRegToReg(*BB, BB->end(), Reg, VRI->second,
-                        SU->CopyDstRC, SU->CopySrcRC);
-    } else {
-      // Copy from physical register.
-      assert(I->Reg && "Unknown physical register!");
-      unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
-      bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
-      isNew = isNew; // Silence compiler warning.
-      assert(isNew && "Node emitted out of order - early");
-      TII->copyRegToReg(*BB, BB->end(), VRBase, I->Reg,
-                        SU->CopyDstRC, SU->CopySrcRC);
-    }
-    break;
-  }
-}
-
 /// EmitSchedule - Emit the machine code in scheduled order.
-MachineBasicBlock *ScheduleDAG::EmitSchedule() {
-  // For post-regalloc scheduling, we're rescheduling the instructions in the
-  // block, so start by removing them from the block.
-  if (!DAG)
-    while (!BB->empty())
-      BB->remove(BB->begin());
-
+MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() {
   DenseMap<SDValue, unsigned> VRBaseMap;
   DenseMap<SUnit*, unsigned> CopyVRBaseMap;
   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
@@ -691,13 +642,6 @@ MachineBasicBlock *ScheduleDAG::EmitSchedule() {
       continue;
     }
 
-    // For post-regalloc scheduling, we already have the instruction;
-    // just append it to the block.
-    if (!DAG) {
-      BB->push_back(SU->getInstr());
-      continue;
-    }
-
     // For pre-regalloc scheduling, create instructions corresponding to the
     // SDNode and any flagged SDNodes and append them to the block.
     SmallVector<SDNode *, 4> FlaggedNodes;
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 23822fa..e43b325 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -34,7 +34,7 @@
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
 #include "llvm/CodeGen/SchedulerRegistry.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/Target/TargetRegisterInfo.h"
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
index d748108..03b78c3 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
@@ -15,7 +15,7 @@
 #include "llvm/Function.h"
 #include "llvm/Assembly/Writer.h"
 #include "llvm/CodeGen/SelectionDAG.h"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
@@ -383,71 +383,7 @@ void SelectionDAG::setSubgraphColor(SDNode *N, const char *Color) {
 #endif
 }
 
-namespace llvm {
-  template<>
-  struct DOTGraphTraits<ScheduleDAG*> : public DefaultDOTGraphTraits {
-    static std::string getGraphName(const ScheduleDAG *G) {
-      return G->MF->getFunction()->getName();
-    }
-
-    static bool renderGraphFromBottomUp() {
-      return true;
-    }
-    
-    static bool hasNodeAddressLabel(const SUnit *Node,
-                                    const ScheduleDAG *Graph) {
-      return true;
-    }
-    
-    /// If you want to override the dot attributes printed for a particular
-    /// edge, override this method.
-    template<typename EdgeIter>
-    static std::string getEdgeAttributes(const void *Node, EdgeIter EI) {
-      if (EI.isSpecialDep())
-        return "color=cyan,style=dashed";
-      if (EI.isCtrlDep())
-        return "color=blue,style=dashed";
-      return "";
-    }
-    
-
-    static std::string getNodeLabel(const SUnit *Node,
-                                    const ScheduleDAG *Graph);
-    static std::string getNodeAttributes(const SUnit *N,
-                                         const ScheduleDAG *Graph) {
-      return "shape=Mrecord";
-    }
-
-    static void addCustomGraphFeatures(ScheduleDAG *G,
-                                       GraphWriter<ScheduleDAG*> &GW) {
-      // Draw a special "GraphRoot" node to indicate the root of the graph.
-      GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot");
-      if (G->DAG) {
-        // For an SDNode-based ScheduleDAG, point to the root of the ScheduleDAG.
-        const SDNode *N = G->DAG->getRoot().getNode();
-        if (N && N->getNodeId() != -1)
-          GW.emitEdge(0, -1, &G->SUnits[N->getNodeId()], -1,
-                      "color=blue,style=dashed");
-      } else {
-        // For a MachineInstr-based ScheduleDAG, find a root to point to.
-        for (unsigned i = 0, e = G->SUnits.size(); i != e; ++i) {
-          if (G->SUnits[i].Succs.empty()) {
-            GW.emitEdge(0, -1, &G->SUnits[i], -1,
-                        "color=blue,style=dashed");
-            break;
-          }
-        }
-      }
-    }
-  };
-}
-
-std::string DOTGraphTraits<ScheduleDAG*>::getNodeLabel(const SUnit *SU,
-                                                       const ScheduleDAG *G) {
-  return G->getGraphNodeLabel(SU);
-}
-
-std::string ScheduleDAG::getGraphNodeLabel(const SUnit *SU) const {
+std::string ScheduleDAGSDNodes::getGraphNodeLabel(const SUnit *SU) const {
   std::string s;
   raw_string_ostream O(s);
   O << "SU(" << SU->NodeNum << "): ";
@@ -467,17 +403,13 @@ std::string ScheduleDAG::getGraphNodeLabel(const SUnit *SU) const {
   return O.str();
 }
 
-/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG
-/// rendered using 'dot'.
-///
-void ScheduleDAG::viewGraph() {
-// This code is only for debugging!
-#ifndef NDEBUG
-  ViewGraph(this, "dag." + MF->getFunction()->getName(),
-            "Scheduling-Units Graph for " + MF->getFunction()->getName() + ':' +
-            BB->getBasicBlock()->getName());
-#else
-  cerr << "ScheduleDAG::viewGraph is only available in debug builds on "
-       << "systems with Graphviz or gv!\n";
-#endif  // NDEBUG
+void ScheduleDAGSDNodes::getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const {
+  if (DAG) {
+    // Draw a special "GraphRoot" node to indicate the root of the graph.
+    GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot");
+    const SDNode *N = DAG->getRoot().getNode();
+    if (N && N->getNodeId() != -1)
+      GW.emitEdge(0, -1, &SUnits[N->getNodeId()], -1,
+                  "color=blue,style=dashed");
+  }
 }