Refactor scheduler code. Move register-reduction list scheduler to a

separate file. Added an initial implementation of top-down register pressure
reduction list scheduler.


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

4 files changed, 1104 insertions, 932 deletions

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index f9749903a7..4a9b9c7f04 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -13,6 +13,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#define DEBUG_TYPE "sched"
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFunction.h"
@@ -20,10 +21,185 @@
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetLowering.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/MathExtras.h"
+#include <iostream>
 using namespace llvm;
 
 
+/// 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() {
+  // 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(std::distance(DAG.allnodes_begin(), DAG.allnodes_end()));
+  
+  const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
+  
+  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 (SUnitMap[NI]) 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, adding flagged preds to FlaggedNodes.
+    SDNode *N = NI;
+    while (N->getNumOperands() &&
+           N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
+      N = N->getOperand(N->getNumOperands()-1).Val;
+      NodeSUnit->FlaggedNodes.push_back(N);
+      SUnitMap[N] = NodeSUnit;
+    }
+    
+    // Scan down, adding this node and any flagged succs to FlaggedNodes if they
+    // have a user of the flag operand.
+    N = NI;
+    while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
+      SDOperand 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.isOperand(*UI)) {
+          HasFlagUse = true;
+          NodeSUnit->FlaggedNodes.push_back(N);
+          SUnitMap[N] = NodeSUnit;
+          N = *UI;
+          break;
+        }
+          if (!HasFlagUse) break;
+    }
+    
+    // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
+    // Update the SUnit
+    NodeSUnit->Node = N;
+    SUnitMap[N] = NodeSUnit;
+    
+    // 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.
+      NodeSUnit->Latency = 1;
+    } else {
+      NodeSUnit->Latency = 0;
+      if (N->isTargetOpcode()) {
+        unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode());
+        InstrStage *S = InstrItins.begin(SchedClass);
+        InstrStage *E = InstrItins.end(SchedClass);
+        for (; S != E; ++S)
+          NodeSUnit->Latency += S->Cycles;
+      }
+      for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) {
+        SDNode *FNode = NodeSUnit->FlaggedNodes[i];
+        if (FNode->isTargetOpcode()) {
+          unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode());
+          InstrStage *S = InstrItins.begin(SchedClass);
+          InstrStage *E = InstrItins.end(SchedClass);
+          for (; S != E; ++S)
+            NodeSUnit->Latency += S->Cycles;
+        }
+      }
+    }
+  }
+  
+  // Pass 2: add the preds, succs, etc.
+  for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
+    SUnit *SU = &SUnits[su];
+    SDNode *MainNode = SU->Node;
+    
+    if (MainNode->isTargetOpcode()) {
+      unsigned Opc = MainNode->getTargetOpcode();
+      if (TII->isTwoAddrInstr(Opc)) {
+        SU->isTwoAddress = true;
+        SDNode *OpN = MainNode->getOperand(0).Val;
+        SUnit *OpSU = SUnitMap[OpN];
+        if (OpSU)
+          OpSU->isDefNUseOperand = true;
+      }
+    }
+    
+    // Find all predecessors and successors of the group.
+    // Temporarily add N to make code simpler.
+    SU->FlaggedNodes.push_back(MainNode);
+    
+    for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
+      SDNode *N = SU->FlaggedNodes[n];
+      
+      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
+        SDNode *OpN = N->getOperand(i).Val;
+        if (isPassiveNode(OpN)) continue;   // Not scheduled.
+        SUnit *OpSU = SUnitMap[OpN];
+        assert(OpSU && "Node has no SUnit!");
+        if (OpSU == SU) continue;           // In the same group.
+
+        MVT::ValueType OpVT = N->getOperand(i).getValueType();
+        assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
+        bool isChain = OpVT == MVT::Other;
+        
+        if (SU->Preds.insert(std::make_pair(OpSU, isChain)).second) {
+          if (!isChain) {
+            SU->NumPreds++;
+            SU->NumPredsLeft++;
+          } else {
+            SU->NumChainPredsLeft++;
+          }
+        }
+        if (OpSU->Succs.insert(std::make_pair(SU, isChain)).second) {
+          if (!isChain) {
+            OpSU->NumSuccs++;
+            OpSU->NumSuccsLeft++;
+          } else {
+            OpSU->NumChainSuccsLeft++;
+          }
+        }
+      }
+    }
+    
+    // Remove MainNode from FlaggedNodes again.
+    SU->FlaggedNodes.pop_back();
+  }
+  
+  return;
+}
+
+static void CalculateDepths(SUnit *SU, unsigned Depth) {
+  if (Depth > SU->Depth) SU->Depth = Depth;
+  for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(),
+         E = SU->Succs.end(); I != E; ++I)
+    CalculateDepths(I->first, Depth+1);
+}
+
+void ScheduleDAG::CalculateDepths() {
+  SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
+  ::CalculateDepths(Entry, 0U);
+  for (unsigned i = 0, e = SUnits.size(); i != e; ++i)
+    if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
+      ::CalculateDepths(&SUnits[i], 0U);
+    }
+}
+
+static void CalculateHeights(SUnit *SU, unsigned Height) {
+  if (Height > SU->Height) SU->Height = Height;
+  for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
+         E = SU->Preds.end(); I != E; ++I)
+    CalculateHeights(I->first, Height+1);
+}
+void ScheduleDAG::CalculateHeights() {
+  SUnit *Root = SUnitMap[DAG.getRoot().Val];
+  ::CalculateHeights(Root, 0U);
+}
+
 /// 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 machine instrs.)
@@ -348,6 +524,32 @@ void ScheduleDAG::EmitNoop() {
   TII->insertNoop(*BB, BB->end());
 }
 
+/// EmitSchedule - Emit the machine code in scheduled order.
+void ScheduleDAG::EmitSchedule() {
+  std::map<SDNode*, unsigned> VRBaseMap;
+  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
+    if (SUnit *SU = Sequence[i]) {
+      for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++)
+        EmitNode(SU->FlaggedNodes[j], VRBaseMap);
+      EmitNode(SU->Node, VRBaseMap);
+    } else {
+      // Null SUnit* is a noop.
+      EmitNoop();
+    }
+  }
+}
+
+/// 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(&DAG);
+    else
+      std::cerr << "**** NOOP ****\n";
+  }
+}
+
+
 /// Run - perform scheduling.
 ///
 MachineBasicBlock *ScheduleDAG::Run() {
@@ -360,4 +562,53 @@ MachineBasicBlock *ScheduleDAG::Run() {
   return BB;
 }
 
+/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
+/// a group of nodes flagged together.
+void SUnit::dump(const SelectionDAG *G) const {
+  std::cerr << "SU(" << NodeNum << "): ";
+  Node->dump(G);
+  std::cerr << "\n";
+  if (FlaggedNodes.size() != 0) {
+    for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
+      std::cerr << "    ";
+      FlaggedNodes[i]->dump(G);
+      std::cerr << "\n";
+    }
+  }
+}
+
+void SUnit::dumpAll(const SelectionDAG *G) const {
+  dump(G);
 
+  std::cerr << "  # preds left       : " << NumPredsLeft << "\n";
+  std::cerr << "  # succs left       : " << NumSuccsLeft << "\n";
+  std::cerr << "  # chain preds left : " << NumChainPredsLeft << "\n";
+  std::cerr << "  # chain succs left : " << NumChainSuccsLeft << "\n";
+  std::cerr << "  Latency            : " << Latency << "\n";
+  std::cerr << "  Depth              : " << Depth << "\n";
+  std::cerr << "  Height             : " << Height << "\n";
+
+  if (Preds.size() != 0) {
+    std::cerr << "  Predecessors:\n";
+    for (std::set<std::pair<SUnit*,bool> >::const_iterator I = Preds.begin(),
+           E = Preds.end(); I != E; ++I) {
+      if (I->second)
+        std::cerr << "   ch  ";
+      else
+        std::cerr << "   val ";
+      I->first->dump(G);
+    }
+  }
+  if (Succs.size() != 0) {
+    std::cerr << "  Successors:\n";
+    for (std::set<std::pair<SUnit*, bool> >::const_iterator I = Succs.begin(),
+           E = Succs.end(); I != E; ++I) {
+      if (I->second)
+        std::cerr << "   ch  ";
+      else
+        std::cerr << "   val ";
+      I->first->dump(G);
+    }
+  }
+  std::cerr << "\n";
+}
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index 7e87b525a0..34136d847c 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -7,10 +7,10 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This implements bottom-up and top-down list schedulers, using standard
-// algorithms.  The basic approach uses a priority queue of available nodes to
-// schedule.  One at a time, nodes are taken from the priority queue (thus in
-// priority order), checked for legality to schedule, and emitted if legal.
+// This implements a top-down list scheduler, using standard algorithms.
+// The basic approach uses a priority queue of available nodes to schedule.
+// One at a time, nodes are taken from the priority queue (thus in priority
+// order), checked for legality to schedule, and emitted if legal.
 //
 // Nodes may not be legal to schedule either due to structural hazards (e.g.
 // pipeline or resource constraints) or because an input to the instruction has
@@ -29,157 +29,20 @@
 #include <climits>
 #include <iostream>
 #include <queue>
-#include <set>
-#include <vector>
-#include "llvm/Support/CommandLine.h"
 using namespace llvm;
 
 namespace {
-  cl::opt<bool> SchedVertically("sched-vertically", cl::Hidden);
-  cl::opt<bool> SchedLowerDefNUse("sched-lower-defnuse", cl::Hidden);
-}
-
-namespace {
   Statistic<> NumNoops ("scheduler", "Number of noops inserted");
   Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
-
-  /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
-  /// a group of nodes flagged together.
-  struct SUnit {
-    SDNode *Node;                       // Representative node.
-    std::vector<SDNode*> FlaggedNodes;  // All nodes flagged to Node.
-    
-    // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
-    // is true if the edge is a token chain edge, false if it is a value edge. 
-    std::set<std::pair<SUnit*,bool> > Preds;  // All sunit predecessors.
-    std::set<std::pair<SUnit*,bool> > Succs;  // All sunit successors.
-
-    short NumPredsLeft;                 // # of preds not scheduled.
-    short NumSuccsLeft;                 // # of succs not scheduled.
-    short NumChainPredsLeft;            // # of chain preds not scheduled.
-    short NumChainSuccsLeft;            // # of chain succs not scheduled.
-    bool isTwoAddress     : 1;          // Is a two-address instruction.
-    bool isDefNUseOperand : 1;          // Is a def&use operand.
-    bool isPending        : 1;          // True once pending.
-    bool isAvailable      : 1;          // True once available.
-    bool isScheduled      : 1;          // True once scheduled.
-    unsigned short Latency;             // Node latency.
-    unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
-    unsigned Cycle;                     // Once scheduled, the cycle of the op.
-    unsigned NodeNum;                   // Entry # of node in the node vector.
-    
-    SUnit(SDNode *node, unsigned nodenum)
-      : Node(node), NumPredsLeft(0), NumSuccsLeft(0),
-        NumChainPredsLeft(0), NumChainSuccsLeft(0),
-        isTwoAddress(false), isDefNUseOperand(false),
-        isPending(false), isAvailable(false), isScheduled(false),
-        Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
-    
-    void dump(const SelectionDAG *G) const;
-    void dumpAll(const SelectionDAG *G) const;
-  };
-}
-
-void SUnit::dump(const SelectionDAG *G) const {
-  std::cerr << "SU(" << NodeNum << "): ";
-  Node->dump(G);
-  std::cerr << "\n";
-  if (FlaggedNodes.size() != 0) {
-    for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
-      std::cerr << "    ";
-      FlaggedNodes[i]->dump(G);
-      std::cerr << "\n";
-    }
-  }
-}
-
-void SUnit::dumpAll(const SelectionDAG *G) const {
-  dump(G);
-
-  std::cerr << "  # preds left       : " << NumPredsLeft << "\n";
-  std::cerr << "  # succs left       : " << NumSuccsLeft << "\n";
-  std::cerr << "  # chain preds left : " << NumChainPredsLeft << "\n";
-  std::cerr << "  # chain succs left : " << NumChainSuccsLeft << "\n";
-  std::cerr << "  Latency            : " << Latency << "\n";
-
-  if (Preds.size() != 0) {
-    std::cerr << "  Predecessors:\n";
-    for (std::set<std::pair<SUnit*,bool> >::const_iterator I = Preds.begin(),
-           E = Preds.end(); I != E; ++I) {
-      if (I->second)
-        std::cerr << "   ch  ";
-      else
-        std::cerr << "   val ";
-      I->first->dump(G);
-    }
-  }
-  if (Succs.size() != 0) {
-    std::cerr << "  Successors:\n";
-    for (std::set<std::pair<SUnit*, bool> >::const_iterator I = Succs.begin(),
-           E = Succs.end(); I != E; ++I) {
-      if (I->second)
-        std::cerr << "   ch  ";
-      else
-        std::cerr << "   val ";
-      I->first->dump(G);
-    }
-  }
-  std::cerr << "\n";
-}
-
-//===----------------------------------------------------------------------===//
-/// SchedulingPriorityQueue - This interface is used to plug different
-/// priorities computation algorithms into the list scheduler. It implements the
-/// interface of a standard priority queue, where nodes are inserted in 
-/// arbitrary order and returned in priority order.  The computation of the
-/// priority and the representation of the queue are totally up to the
-/// implementation to decide.
-/// 
-namespace {
-class SchedulingPriorityQueue {
-public:
-  virtual ~SchedulingPriorityQueue() {}
-  
-  virtual void initNodes(const std::vector<SUnit> &SUnits) = 0;
-  virtual void releaseState() = 0;
-  
-  virtual bool empty() const = 0;
-  virtual void push(SUnit *U) = 0;
-  
-  virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
-  virtual SUnit *pop() = 0;
-
-  virtual void RemoveFromPriorityQueue(SUnit *SU) = 0;
-  
-  /// ScheduledNode - As each node is scheduled, this method is invoked.  This
-  /// allows the priority function to adjust the priority of node that have
-  /// already been emitted.
-  virtual void ScheduledNode(SUnit *Node) {}
-};
 }
 
-
-
 namespace {
 //===----------------------------------------------------------------------===//
 /// ScheduleDAGList - The actual list scheduler implementation.  This supports
-/// both top-down and bottom-up scheduling.
+/// top-down scheduling.
 ///
 class ScheduleDAGList : public ScheduleDAG {
 private:
-  // SDNode to SUnit mapping (many to one).
-  std::map<SDNode*, SUnit*> SUnitMap;
-
-  // The schedule.  Null SUnit*'s represent noop instructions.
-  std::vector<SUnit*> Sequence;
-  
-  // The scheduling units.
-  std::vector<SUnit> SUnits;
-
-  /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
-  /// it is top-down.
-  bool isBottomUp;
-  
   /// AvailableQueue - The priority queue to use for the available SUnits.
   ///
   SchedulingPriorityQueue *AvailableQueue;
@@ -194,20 +57,12 @@ private:
   /// HazardRec - The hazard recognizer to use.
   HazardRecognizer *HazardRec;
 
-  /// OpenNodes - Nodes with open live ranges, i.e. predecessors or successors
-  /// of scheduled nodes which are not themselves scheduled.
-  std::map<const TargetRegisterClass*, std::set<SUnit*> > OpenNodes;
-
-  /// RegPressureLimits - Keep track of upper limit of register pressure for
-  /// each register class that allows the scheduler to go into vertical mode.
-  std::map<const TargetRegisterClass*, unsigned> RegPressureLimits;
-
 public:
   ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
-                  const TargetMachine &tm, bool isbottomup,
+                  const TargetMachine &tm,
                   SchedulingPriorityQueue *availqueue,
                   HazardRecognizer *HR)
-    : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), 
+    : ScheduleDAG(dag, bb, tm),
       AvailableQueue(availqueue), HazardRec(HR) {
     }
 
@@ -218,202 +73,16 @@ public:
 
   void Schedule();
 
-  void dumpSchedule() const;
-
 private:
-  SUnit *NewSUnit(SDNode *N);
-  void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
   void ReleaseSucc(SUnit *SuccSU, bool isChain);
-  void ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle, bool Veritical=true);
-  void ScheduleVertically(SUnit *SU, unsigned& CurCycle);
   void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
   void ListScheduleTopDown();
-  void ListScheduleBottomUp();
-  void BuildSchedUnits();
-  void EmitSchedule();
 };
 }  // end anonymous namespace
 
 HazardRecognizer::~HazardRecognizer() {}
 
 
-/// NewSUnit - Creates a new SUnit and return a ptr to it.
-SUnit *ScheduleDAGList::NewSUnit(SDNode *N) {
-  SUnits.push_back(SUnit(N, SUnits.size()));
-  return &SUnits.back();
-}
-
-/// 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 ScheduleDAGList::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(std::distance(DAG.allnodes_begin(), DAG.allnodes_end()));
-  
-  const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
-  
-  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 (SUnitMap[NI]) 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, adding flagged preds to FlaggedNodes.
-    SDNode *N = NI;
-    while (N->getNumOperands() &&
-           N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
-      N = N->getOperand(N->getNumOperands()-1).Val;
-      NodeSUnit->FlaggedNodes.push_back(N);
-      SUnitMap[N] = NodeSUnit;
-    }
-    
-    // Scan down, adding this node and any flagged succs to FlaggedNodes if they
-    // have a user of the flag operand.
-    N = NI;
-    while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
-      SDOperand 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.isOperand(*UI)) {
-          HasFlagUse = true;
-          NodeSUnit->FlaggedNodes.push_back(N);
-          SUnitMap[N] = NodeSUnit;
-          N = *UI;
-          break;
-        }
-          if (!HasFlagUse) break;
-    }
-    
-    // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
-    // Update the SUnit
-    NodeSUnit->Node = N;
-    SUnitMap[N] = NodeSUnit;
-    
-    // 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.
-      NodeSUnit->Latency = 1;
-    } else {
-      NodeSUnit->Latency = 0;
-      if (N->isTargetOpcode()) {
-        unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode());
-        InstrStage *S = InstrItins.begin(SchedClass);
-        InstrStage *E = InstrItins.end(SchedClass);
-        for (; S != E; ++S)
-          NodeSUnit->Latency += S->Cycles;
-      }
-      for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) {
-        SDNode *FNode = NodeSUnit->FlaggedNodes[i];
-        if (FNode->isTargetOpcode()) {
-          unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode());
-          InstrStage *S = InstrItins.begin(SchedClass);
-          InstrStage *E = InstrItins.end(SchedClass);
-          for (; S != E; ++S)
-            NodeSUnit->Latency += S->Cycles;
-        }
-      }
-    }
-  }
-  
-  // Pass 2: add the preds, succs, etc.
-  for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
-    SUnit *SU = &SUnits[su];
-    SDNode *MainNode = SU->Node;
-    
-    if (MainNode->isTargetOpcode()) {
-      unsigned Opc = MainNode->getTargetOpcode();
-      if (TII->isTwoAddrInstr(Opc)) {
-        SU->isTwoAddress = true;
-        SDNode *OpN = MainNode->getOperand(0).Val;
-        SUnit *OpSU = SUnitMap[OpN];
-        if (OpSU)
-          OpSU->isDefNUseOperand = true;
-      }
-    }
-    
-    // Find all predecessors and successors of the group.
-    // Temporarily add N to make code simpler.
-    SU->FlaggedNodes.push_back(MainNode);
-    
-    for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
-      SDNode *N = SU->FlaggedNodes[n];
-      
-      for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
-        SDNode *OpN = N->getOperand(i).Val;
-        if (isPassiveNode(OpN)) continue;   // Not scheduled.
-        SUnit *OpSU = SUnitMap[OpN];
-        assert(OpSU && "Node has no SUnit!");
-        if (OpSU == SU) continue;           // In the same group.
-
-        MVT::ValueType OpVT = N->getOperand(i).getValueType();
-        assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
-        bool isChain = OpVT == MVT::Other;
-        
-        if (SU->Preds.insert(std::make_pair(OpSU, isChain)).second) {
-          if (!isChain) {
-            SU->NumPredsLeft++;
-          } else {
-            SU->NumChainPredsLeft++;
-          }
-        }
-        if (OpSU->Succs.insert(std::make_pair(SU, isChain)).second) {
-          if (!isChain) {
-            OpSU->NumSuccsLeft++;
-          } else {
-            OpSU->NumChainSuccsLeft++;
-          }
-        }
-      }
-    }
-    
-    // Remove MainNode from FlaggedNodes again.
-    SU->FlaggedNodes.pop_back();
-  }
-  
-  DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
-        SUnits[su].dumpAll(&DAG));
-  return;
-}
-
-/// EmitSchedule - Emit the machine code in scheduled order.
-void ScheduleDAGList::EmitSchedule() {
-  std::map<SDNode*, unsigned> VRBaseMap;
-  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
-    if (SUnit *SU = Sequence[i]) {
-      for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++)
-        EmitNode(SU->FlaggedNodes[j], VRBaseMap);
-      EmitNode(SU->Node, VRBaseMap);
-    } else {
-      // Null SUnit* is a noop.
-      EmitNoop();
-    }
-  }
-}
-
-/// dump - dump the schedule.
-void ScheduleDAGList::dumpSchedule() const {
-  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
-    if (SUnit *SU = Sequence[i])
-      SU->dump(&DAG);
-    else
-      std::cerr << "**** NOOP ****\n";
-  }
-}
-
 /// Schedule - Schedule the DAG using list scheduling.
 void ScheduleDAGList::Schedule() {
   DEBUG(std::cerr << "********** List Scheduling **********\n");
@@ -423,11 +92,7 @@ void ScheduleDAGList::Schedule() {
 
   AvailableQueue->initNodes(SUnits);
   
-  // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
-  if (isBottomUp)
-    ListScheduleBottomUp();
-  else
-    ListScheduleTopDown();
+  ListScheduleTopDown();
   
   AvailableQueue->releaseState();
   
@@ -440,273 +105,6 @@ void ScheduleDAGList::Schedule() {
 }
 
 //===----------------------------------------------------------------------===//
-//  Bottom-Up Scheduling
-//===----------------------------------------------------------------------===//
-
-static const TargetRegisterClass *getRegClass(SUnit *SU,
-                                              const TargetInstrInfo *TII,
-                                              const MRegisterInfo *MRI,
-                                              SSARegMap *RegMap) {
-  if (SU->Node->isTargetOpcode()) {
-    unsigned Opc = SU->Node->getTargetOpcode();
-    const TargetInstrDescriptor &II = TII->get(Opc);
-    return II.OpInfo->RegClass;
-  } else {
-    assert(SU->Node->getOpcode() == ISD::CopyFromReg);
-    unsigned SrcReg = cast<RegisterSDNode>(SU->Node->getOperand(1))->getReg();
-    if (MRegisterInfo::isVirtualRegister(SrcReg))
-      return RegMap->getRegClass(SrcReg);
-    else {
-      for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
-             E = MRI->regclass_end(); I != E; ++I)
-        if ((*I)->hasType(SU->Node->getValueType(0)) &&
-            (*I)->contains(SrcReg))
-          return *I;
-      assert(false && "Couldn't find register class for reg copy!");
-    }
-    return NULL;
-  }
-}
-
-static unsigned getNumResults(SUnit *SU) {
-  unsigned NumResults = 0;
-  for (unsigned i = 0, e = SU->Node->getNumValues(); i != e; ++i) {
-    MVT::ValueType VT = SU->Node->getValueType(i);
-    if (VT != MVT::Other && VT != MVT::Flag)
-      NumResults++;
-  }
-  return NumResults;
-}
-
-/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
-/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain, 
-                                  unsigned CurCycle) {
-  // FIXME: the distance between two nodes is not always == the predecessor's
-  // latency. For example, the reader can very well read the register written
-  // by the predecessor later than the issue cycle. It also depends on the
-  // interrupt model (drain vs. freeze).
-  PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
-
-  if (!isChain)
-    PredSU->NumSuccsLeft--;
-  else
-    PredSU->NumChainSuccsLeft--;
-  
-#ifndef NDEBUG
-  if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
-    std::cerr << "*** List scheduling failed! ***\n";
-    PredSU->dump(&DAG);
-    std::cerr << " has been released too many times!\n";
-    assert(0);
-  }
-#endif
-  
-  if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
-    // EntryToken has to go last!  Special case it here.
-    if (PredSU->Node->getOpcode() != ISD::EntryToken) {
-      PredSU->isAvailable = true;
-      AvailableQueue->push(PredSU);
-    }
-  }
-
-  if (getNumResults(PredSU) > 0) {
-    const TargetRegisterClass *RegClass = getRegClass(PredSU, TII, MRI, RegMap);
-    OpenNodes[RegClass].insert(PredSU);
-  }
-}
-
-/// SharesOperandWithTwoAddr - Check if there is a unscheduled two-address node
-/// with which SU shares an operand. If so, returns the node.
-static SUnit *SharesOperandWithTwoAddr(SUnit *SU) {
-  assert(!SU->isTwoAddress && "Node cannot be two-address op");
-  for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
-         E = SU->Preds.end(); I != E; ++I) {
-    if (I->second) continue;
-    SUnit *PredSU = I->first;
-    for (std::set<std::pair<SUnit*, bool> >::iterator II =
-           PredSU->Succs.begin(), EE = PredSU->Succs.end(); II != EE; ++II) {
-      if (II->second) continue;
-      SUnit *SSU = II->first;
-      if (SSU->isTwoAddress && !SSU->isScheduled) {
-        return SSU;
-      }
-    }
-  }
-  return NULL;
-}
-
-static bool isFloater(const SUnit *SU) {
-  unsigned Opc = SU->Node->getOpcode();
-  return (Opc != ISD::CopyFromReg && SU->NumPredsLeft == 0);
-}
-
-static bool isSimpleFloaterUse(const SUnit *SU) {
-  unsigned NumOps = 0;
-  for (std::set<std::pair<SUnit*, bool> >::const_iterator I = SU->Preds.begin(),
-         E = SU->Preds.end(); I != E; ++I) {
-    if (I->second) continue;
-    if (++NumOps > 1)
-      return false;
-    if (!isFloater(I->first))
-      return false;
-  }
-  return true;
-}
-
-/// ScheduleVertically - Schedule vertically. That is, follow up the D&U chain
-/// (of two-address code) and schedule floaters aggressively.
-void ScheduleDAGList::ScheduleVertically(SUnit *SU, unsigned& CurCycle) {
-  // Try scheduling Def&Use operand if register pressure is low.
-  const TargetRegisterClass *RegClass = getRegClass(SU, TII, MRI, RegMap);
-  unsigned Pressure = OpenNodes[RegClass].size();
-  unsigned Limit = RegPressureLimits[RegClass];
-
-  // See if we can schedule any predecessor that takes no registers.
-  for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
-         E = SU->Preds.end(); I != E; ++I) {
-    if (I->second) continue;
-
-    SUnit *PredSU = I->first;
-    if (!PredSU->isAvailable || PredSU->isScheduled)
-      continue;
-
-    if (isFloater(PredSU)) {
-      DEBUG(std::cerr<<"*** Scheduling floater\n");
-      AvailableQueue->RemoveFromPriorityQueue(PredSU);
-      ScheduleNodeBottomUp(PredSU, CurCycle, false);
-    }
-  }
-
-  SUnit *DUSU = NULL;
-  if (SU->isTwoAddress && Pressure < Limit) {
-    DUSU = SUnitMap[SU->Node->getOperand(0).Val];
-    if (!DUSU->isAvailable || DUSU->isScheduled)
-      DUSU = NULL;
-    else if (!DUSU->isTwoAddress) {
-      SUnit *SSU = SharesOperandWithTwoAddr(DUSU);
-      if (SSU && SSU->isAvailable) {
-        AvailableQueue->RemoveFromPriorityQueue(SSU);
-        ScheduleNodeBottomUp(SSU, CurCycle, false);
-        Pressure = OpenNodes[RegClass].size();
-        if (Pressure >= Limit)
-          DUSU = NULL;
-      }
-    }
-  }
-
-  if (DUSU) {
-    DEBUG(std::cerr<<"*** Low register pressure: scheduling D&U operand\n");
-    AvailableQueue->RemoveFromPriorityQueue(DUSU);
-    ScheduleNodeBottomUp(DUSU, CurCycle, false);
-    Pressure = OpenNodes[RegClass].size();
-    ScheduleVertically(DUSU, CurCycle);
-  }
-}
-
-/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
-/// count of its predecessors. If a predecessor pending count is zero, add it to
-/// the Available queue.
-void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle,
-                                           bool Vertical) {
-  DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
-  DEBUG(SU->dump(&DAG));
-  SU->Cycle = CurCycle;
-
-  AvailableQueue->ScheduledNode(SU);
-  Sequence.push_back(SU);
-
-  // Bottom up: release predecessors
-  for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
-         E = SU->Preds.end(); I != E; ++I)
-    ReleasePred(I->first, I->second, CurCycle);
-  SU->isScheduled = true;
-  CurCycle++;
-
-  if (getNumResults(SU) != 0) {
-    const TargetRegisterClass *RegClass = getRegClass(SU, TII, MRI, RegMap);
-    OpenNodes[RegClass].erase(SU);
-
-    if (SchedVertically && Vertical)
-      ScheduleVertically(SU, CurCycle);
-  }
-}
-
-/// isReady - True if node's lower cycle bound is less or equal to the current
-/// scheduling cycle. Always true if all nodes have uniform latency 1.
-static inline bool isReady(SUnit *SU, unsigned CurCycle) {
-  return SU->CycleBound <= CurCycle;
-}
-
-/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
-/// schedulers.
-void ScheduleDAGList::ListScheduleBottomUp() {
-  // Determine rough register pressure limit.
-  for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
-         E = MRI->regclass_end(); RCI != E; ++RCI) {
-    const TargetRegisterClass *RC = *RCI;
-    unsigned Limit = RC->getNumRegs();
-    Limit = (Limit > 2) ? Limit - 2 : 0;
-    std::map<const TargetRegisterClass*, unsigned>::iterator RPI =
-      RegPressureLimits.find(RC);
-    if (RPI == RegPressureLimits.end())
-      RegPressureLimits[RC] = Limit;
-    else {
-      unsigned &OldLimit = RegPressureLimits[RC];
-      if (Limit < OldLimit)
-        OldLimit = Limit;
-    }
-  }
-
-  unsigned CurCycle = 0;
-  // Add root to Available queue.
-  AvailableQueue->push(SUnitMap[DAG.getRoot().Val]);
-
-  // While Available queue is not empty, grab the node with the highest
-  // priority. If it is not ready put it back. Schedule the node.
-  std::vector<SUnit*> NotReady;
-  SUnit *CurNode = NULL;
-  while (!AvailableQueue->empty()) {
-    SUnit *CurNode = AvailableQueue->pop();
-    while (!isReady(CurNode, CurCycle)) {
-      NotReady.push_back(CurNode);
-      CurNode = AvailableQueue->pop();
-    }
-    
-    // Add the nodes that aren't ready back onto the available list.
-    AvailableQueue->push_all(NotReady);
-    NotReady.clear();
-
-    ScheduleNodeBottomUp(CurNode, CurCycle);
-  }
-
-  // Add entry node last
-  if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
-    SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
-    Sequence.push_back(Entry);
-  }
-
-  // Reverse the order if it is bottom up.
-  std::reverse(Sequence.begin(