Add "blocked" heuristic to the Hexagon MI scheduler.

  Improve AQ instruction selection in the Hexagon MI scheduler.



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

2 files changed, 269 insertions, 177 deletions

diff --git a/lib/Target/Hexagon/HexagonMachineScheduler.cpp b/lib/Target/Hexagon/HexagonMachineScheduler.cpp
index 6a37639..b131a8f 100644
--- a/lib/Target/Hexagon/HexagonMachineScheduler.cpp
+++ b/lib/Target/Hexagon/HexagonMachineScheduler.cpp
@@ -190,6 +190,9 @@ void VLIWMachineScheduler::initRegPressure() {
   std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure;
   for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
     unsigned Limit = TRI->getRegPressureSetLimit(i);
+    DEBUG(dbgs() << TRI->getRegPressureSetName(i)
+          << "Limit " << Limit
+          << " Actual " << RegionPressure[i] << "\n");
     if (RegionPressure[i] > Limit)
       RegionCriticalPSets.push_back(PressureElement(i, 0));
   }
@@ -199,11 +202,6 @@ void VLIWMachineScheduler::initRegPressure() {
             RegionCriticalPSets[i].PSetID) << " ";
         dbgs() << "\n");
 
-  // Reset resource state.
-  TopResourceModel->resetPacketState();
-  TopResourceModel->resetDFA();
-  BotResourceModel->resetPacketState();
-  BotResourceModel->resetDFA();
   TotalPackets = 0;
 }
 
@@ -264,13 +262,15 @@ bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
 }
 
 /// Keep track of available resources.
-void VLIWResourceModel::reserveResources(SUnit *SU) {
+bool VLIWResourceModel::reserveResources(SUnit *SU) {
+  bool startNewCycle = false;
   // If this SU does not fit in the packet
   // start a new one.
   if (!isResourceAvailable(SU)) {
     ResourcesModel->clearResources();
     Packet.clear();
     TotalPackets++;
+    startNewCycle = true;
   }
 
   switch (SU->getInstr()->getOpcode()) {
@@ -295,7 +295,8 @@ void VLIWResourceModel::reserveResources(SUnit *SU) {
   DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
   for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
     DEBUG(dbgs() << "\t[" << i << "] SU(");
-    DEBUG(dbgs() << Packet[i]->NodeNum << ")\n");
+    DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
+    DEBUG(Packet[i]->getInstr()->dump());
   }
 #endif
 
@@ -305,7 +306,10 @@ void VLIWResourceModel::reserveResources(SUnit *SU) {
     ResourcesModel->clearResources();
     Packet.clear();
     TotalPackets++;
+    startNewCycle = true;
   }
+
+  return startNewCycle;
 }
 
 // Release all DAG roots for scheduling.
@@ -352,6 +356,17 @@ void VLIWMachineScheduler::schedule() {
   // Initialize top/bottom trackers after computing region pressure.
   initRegPressure();
 
+  // To view Height/Depth correctly, they should be accessed at least once.
+  DEBUG(unsigned maxH = 0;
+        for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
+          if (SUnits[su].getHeight() > maxH)
+            maxH = SUnits[su].getHeight();
+        dbgs() << "Max Height " << maxH << "\n";);
+  DEBUG(unsigned maxD = 0;
+        for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
+          if (SUnits[su].getDepth() > maxD)
+            maxD = SUnits[su].getDepth();
+        dbgs() << "Max Depth " << maxD << "\n";);
   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
           SUnits[su].dumpAll(this));
 
@@ -390,13 +405,9 @@ void VLIWMachineScheduler::schedule() {
       assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
       updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure);
 
-      // Update DFA state.
-      TopResourceModel->reserveResources(SU);
-
       // Release dependent instructions for scheduling.
       releaseSuccessors(SU);
-    }
-    else {
+    } else {
       assert(SU->isBottomReady() && "node still has unscheduled dependencies");
       MachineBasicBlock::iterator priorII =
         priorNonDebug(CurrentBottom, CurrentTop);
@@ -415,9 +426,6 @@ void VLIWMachineScheduler::schedule() {
       assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
       updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure);
 
-      // Update DFA state.
-      BotResourceModel->reserveResources(SU);
-
       // Release dependent instructions for scheduling.
       releasePredecessors(SU);
     }
@@ -426,9 +434,6 @@ void VLIWMachineScheduler::schedule() {
   }
   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
 
-  DEBUG(dbgs() << "Final schedule has " << TopResourceModel->getTotalPackets() +
-        BotResourceModel->getTotalPackets()<< "packets.\n");
-
   placeDebugValues();
 }
 
@@ -465,6 +470,9 @@ void ConvergingVLIWScheduler::initialize(VLIWMachineScheduler *dag) {
   Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
   Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
 
+  Top.ResourceModel = new VLIWResourceModel(TM);
+  Bot.ResourceModel = new VLIWResourceModel(TM);
+
   assert((!ForceTopDown || !ForceBottomUp) &&
          "-misched-topdown incompatible with -misched-bottomup");
 }
@@ -553,8 +561,7 @@ void ConvergingVLIWScheduler::SchedBoundary::bumpCycle() {
   if (!HazardRec->isEnabled()) {
     // Bypass HazardRec virtual calls.
     CurrCycle = NextCycle;
-  }
-  else {
+  } else {
     // Bypass getHazardType calls in case of long latency.
     for (; CurrCycle != NextCycle; ++CurrCycle) {
       if (isTop())
@@ -571,6 +578,7 @@ void ConvergingVLIWScheduler::SchedBoundary::bumpCycle() {
 
 /// Move the boundary of scheduled code by one SUnit.
 void ConvergingVLIWScheduler::SchedBoundary::bumpNode(SUnit *SU) {
+  bool startNewCycle = false;
 
   // Update the reservation table.
   if (HazardRec->isEnabled()) {
@@ -581,13 +589,20 @@ void ConvergingVLIWScheduler::SchedBoundary::bumpNode(SUnit *SU) {
     }
     HazardRec->EmitInstruction(SU);
   }
+
+  // Update DFA model.
+  startNewCycle = ResourceModel->reserveResources(SU);
+
   // Check the instruction group dispatch limit.
   // TODO: Check if this SU must end a dispatch group.
   IssueCount += DAG->getNumMicroOps(SU->getInstr());
-  if (IssueCount >= DAG->getIssueWidth()) {
+  if (startNewCycle) {
     DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
     bumpCycle();
   }
+  else
+    DEBUG(dbgs() << "*** IssueCount " << IssueCount
+          << " at cycle " << CurrCycle << '\n');
 }
 
 /// Release pending ready nodes in to the available queue. This makes them
@@ -648,8 +663,9 @@ SUnit *ConvergingVLIWScheduler::SchedBoundary::pickOnlyChoice() {
 }
 
 #ifndef NDEBUG
-void ConvergingVLIWScheduler::traceCandidate(const char *Label, const ReadyQueue &Q,
-                                         SUnit *SU, PressureElement P) {
+void ConvergingVLIWScheduler::traceCandidate(const char *Label,
+                                             const ReadyQueue &Q,
+                                             SUnit *SU, PressureElement P) {
   dbgs() << Label << " " << Q.getName() << " ";
   if (P.isValid())
     dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease
@@ -660,10 +676,48 @@ void ConvergingVLIWScheduler::traceCandidate(const char *Label, const ReadyQueue
 }
 #endif
 
+/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
+/// of SU, return it, otherwise return null.
+static SUnit *getSingleUnscheduledPred(SUnit *SU) {
+  SUnit *OnlyAvailablePred = 0;
+  for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+       I != E; ++I) {
+    SUnit &Pred = *I->getSUnit();
+    if (!Pred.isScheduled) {
+      // We found an available, but not scheduled, predecessor.  If it's the
+      // only one we have found, keep track of it... otherwise give up.
+      if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
+        return 0;
+      OnlyAvailablePred = &Pred;
+    }
+  }
+  return OnlyAvailablePred;
+}
+
+/// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
+/// of SU, return it, otherwise return null.
+static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
+  SUnit *OnlyAvailableSucc = 0;
+  for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+       I != E; ++I) {
+    SUnit &Succ = *I->getSUnit();
+    if (!Succ.isScheduled) {
+      // We found an available, but not scheduled, successor.  If it's the
+      // only one we have found, keep track of it... otherwise give up.
+      if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ)
+        return 0;
+      OnlyAvailableSucc = &Succ;
+    }
+  }
+  return OnlyAvailableSucc;
+}
+
 // Constants used to denote relative importance of
 // heuristic components for cost computation.
 static const unsigned PriorityOne = 200;
+static const unsigned PriorityTwo = 100;
 static const unsigned PriorityThree = 50;
+static const unsigned PriorityFour = 20;
 static const unsigned ScaleTwo = 10;
 static const unsigned FactorOne = 2;
 
@@ -685,19 +739,44 @@ int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
     ResCount += PriorityOne;
 
   // Critical path first.
-  if (Q.getID() == TopQID)
+  if (Q.getID() == TopQID) {
     ResCount += (SU->getHeight() * ScaleTwo);
-  else
+
+    // If resources are available for it, multiply the
+    // chance of scheduling.
+    if (Top.ResourceModel->isResourceAvailable(SU))
+      ResCount <<= FactorOne;
+  } else {
     ResCount += (SU->getDepth() * ScaleTwo);
 
-  // If resources are available for it, multiply the
-  // chance of scheduling.
-  if (DAG->getTopResourceModel()->isResourceAvailable(SU))
-    ResCount <<= FactorOne;
+    // If resources are available for it, multiply the
+    // chance of scheduling.
+    if (Bot.ResourceModel->isResourceAvailable(SU))
+      ResCount <<= FactorOne;
+  }
+
+  unsigned NumNodesBlocking = 0;
+  if (Q.getID() == TopQID) {
+    // How many SUs does it block from scheduling?
+    // Look at all of the successors of this node.
+    // Count the number of nodes that
+    // this node is the sole unscheduled node for.
+    for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+         I != E; ++I)
+      if (getSingleUnscheduledPred(I->getSUnit()) == SU)
+        ++NumNodesBlocking;
+  } else {
+    // How many unscheduled predecessors block this node?
+    for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+         I != E; ++I)
+      if (getSingleUnscheduledSucc(I->getSUnit()) == SU)
+        ++NumNodesBlocking;
+  }
+  ResCount += (NumNodesBlocking * ScaleTwo);
 
   // Factor in reg pressure as a heuristic.
-  ResCount -= (Delta.Excess.UnitIncrease * PriorityThree);
-  ResCount -= (Delta.CriticalMax.UnitIncrease * PriorityThree);
+  ResCount -= (Delta.Excess.UnitIncrease*PriorityThree);
+  ResCount -= (Delta.CriticalMax.UnitIncrease*PriorityThree);
 
   DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")");
 
@@ -736,7 +815,6 @@ pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
       continue;
     }
 
-
     // Best cost.
     if (CurrentCost > Candidate.SCost) {
       DEBUG(traceCandidate("CCAND", Q, *I));
@@ -859,14 +937,14 @@ SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
 }
 
 /// Update the scheduler's state after scheduling a node. This is the same node
-/// that was just returned by pickNode(). However, VLIWMachineScheduler needs to update
-/// it's state based on the current cycle before MachineSchedStrategy does.
+/// that was just returned by pickNode(). However, VLIWMachineScheduler needs
+/// to update it's state based on the current cycle before MachineSchedStrategy
+/// does.
 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
   if (IsTopNode) {
     SU->TopReadyCycle = Top.CurrCycle;
     Top.bumpNode(SU);
-  }
-  else {
+  } else {
     SU->BotReadyCycle = Bot.CurrCycle;
     Bot.bumpNode(SU);
   }
diff --git a/lib/Target/Hexagon/HexagonMachineScheduler.h b/lib/Target/Hexagon/HexagonMachineScheduler.h
index 7d8cc3d..f3643d6 100644
--- a/lib/Target/Hexagon/HexagonMachineScheduler.h
+++ b/lib/Target/Hexagon/HexagonMachineScheduler.h
@@ -40,11 +40,10 @@ using namespace llvm;
 namespace llvm {
 class VLIWMachineScheduler;
 
-/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive the selected
-/// scheduling algorithm.
+/// MachineSchedStrategy - Interface used by VLIWMachineScheduler to drive
+/// the selected scheduling algorithm.
 ///
-/// If this works well and targets wish to reuse VLIWMachineScheduler, we may expose it
-/// in ScheduleDAGInstrs.h
+/// TODO: Move this to ScheduleDAGInstrs.h
 class MachineSchedStrategy {
 public:
   virtual ~MachineSchedStrategy() {}
@@ -57,7 +56,8 @@ public:
   /// be scheduled at the bottom.
   virtual SUnit *pickNode(bool &IsTopNode) = 0;
 
-  /// Notify MachineSchedStrategy that VLIWMachineScheduler has scheduled a node.
+  /// Notify MachineSchedStrategy that VLIWMachineScheduler has
+  /// scheduled a node.
   virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
 
   /// When all predecessor dependencies have been resolved, free this node for
@@ -69,7 +69,8 @@ public:
 };
 
 //===----------------------------------------------------------------------===//
-// ConvergingVLIWScheduler - Implementation of the standard MachineSchedStrategy.
+// ConvergingVLIWScheduler - Implementation of the standard
+// MachineSchedStrategy.
 //===----------------------------------------------------------------------===//
 
 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
@@ -123,123 +124,6 @@ public:
   }
 };
 
-/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance
-/// the schedule.
-class ConvergingVLIWScheduler : public MachineSchedStrategy {
-
-  /// Store the state used by ConvergingVLIWScheduler heuristics, required for the
-  /// lifetime of one invocation of pickNode().
-  struct SchedCandidate {
-    // The best SUnit candidate.
-    SUnit *SU;
-
-    // Register pressure values for the best candidate.
-    RegPressureDelta RPDelta;
-
-    // Best scheduling cost.
-    int SCost;
-
-    SchedCandidate(): SU(NULL), SCost(0) {}
-  };
-  /// Represent the type of SchedCandidate found within a single queue.
-  enum CandResult {
-    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
-    BestCost};
-
-  /// Each Scheduling boundary is associated with ready queues. It tracks the
-  /// current cycle in whichever direction at has moved, and maintains the state
-  /// of "hazards" and other interlocks at the current cycle.
-  struct SchedBoundary {
-    VLIWMachineScheduler *DAG;
-
-    ReadyQueue Available;
-    ReadyQueue Pending;
-    bool CheckPending;
-
-    ScheduleHazardRecognizer *HazardRec;
-
-    unsigned CurrCycle;
-    unsigned IssueCount;
-
-    /// MinReadyCycle - Cycle of the soonest available instruction.
-    unsigned MinReadyCycle;
-
-    // Remember the greatest min operand latency.
-    unsigned MaxMinLatency;
-
-    /// Pending queues extend the ready queues with the same ID and the
-    /// PendingFlag set.
-    SchedBoundary(unsigned ID, const Twine &Name):
-      DAG(0), Available(ID, Name+".A"),
-      Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
-      CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0),
-      MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
-
-    ~SchedBoundary() { delete HazardRec; }
-
-    bool isTop() const {
-      return Available.getID() == ConvergingVLIWScheduler::TopQID;
-    }
-
-    bool checkHazard(SUnit *SU);
-
-    void releaseNode(SUnit *SU, unsigned ReadyCycle);
-
-    void bumpCycle();
-
-    void bumpNode(SUnit *SU);
-
-    void releasePending();
-
-    void removeReady(SUnit *SU);
-
-    SUnit *pickOnlyChoice();
-  };
-
-  VLIWMachineScheduler *DAG;
-  const TargetRegisterInfo *TRI;
-
-  // State of the top and bottom scheduled instruction boundaries.
-  SchedBoundary Top;
-  SchedBoundary Bot;
-
-public:
-  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
-  enum {
-    TopQID = 1,
-    BotQID = 2,
-    LogMaxQID = 2
-  };
-
-  ConvergingVLIWScheduler():
-    DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
-
-  virtual void initialize(VLIWMachineScheduler *dag);
-
-  virtual SUnit *pickNode(bool &IsTopNode);
-
-  virtual void schedNode(SUnit *SU, bool IsTopNode);
-
-  virtual void releaseTopNode(SUnit *SU);
-
-  virtual void releaseBottomNode(SUnit *SU);
-
-protected:
-  SUnit *pickNodeBidrectional(bool &IsTopNode);
-
-  int SchedulingCost(ReadyQueue &Q,
-                     SUnit *SU, SchedCandidate &Candidate,
-                     RegPressureDelta &Delta, bool verbose);
-
-  CandResult pickNodeFromQueue(ReadyQueue &Q,
-                               const RegPressureTracker &RPTracker,
-                               SchedCandidate &Candidate);
-#ifndef NDEBUG
-  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
-                      PressureElement P = PressureElement());
-#endif
-};
-
 class VLIWResourceModel {
   /// ResourcesModel - Represents VLIW state.
   /// Not limited to VLIW targets per say, but assumes
@@ -261,7 +145,21 @@ public:
     const TargetMachine &TM = C->MF->getTarget();
     ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
 
-    // This hard requirement could be relaxed, but for now do not let it proceed.
+    // This hard requirement could be relaxed,
+    // but for now do not let it proceed.
+    assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
+
+    Packet.resize(InstrItins->SchedModel->IssueWidth);
+    Packet.clear();
+    ResourcesModel->clearResources();
+  }
+
+  VLIWResourceModel(const TargetMachine &TM) :
+    InstrItins(TM.getInstrItineraryData()), TotalPackets(0) {
+    ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
+
+    // This hard requirement could be relaxed,
+    // but for now do not let it proceed.
     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
 
     Packet.resize(InstrItins->SchedModel->IssueWidth);
@@ -281,8 +179,13 @@ public:
     ResourcesModel->clearResources();
   }
 
+  void reset() {
+    Packet.clear();
+    ResourcesModel->clearResources();
+  }
+
   bool isResourceAvailable(SUnit *SU);
-  void reserveResources(SUnit *SU);
+  bool reserveResources(SUnit *SU);
   unsigned getTotalPackets() const { return TotalPackets; }
 };
 
@@ -293,10 +196,6 @@ class VLIWMachineScheduler : public ScheduleDAGInstrs {
   RegisterClassInfo *RegClassInfo;
   MachineSchedStrategy *SchedImpl;
 
-  /// state separatly for top/bottom sectioins.
-  VLIWResourceModel *TopResourceModel;
-  VLIWResourceModel *BotResourceModel;
-
   MachineBasicBlock::iterator LiveRegionEnd;
 
   /// Register pressure in this region computed by buildSchedGraph.
@@ -334,10 +233,6 @@ public:
     AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S),
     RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
     CurrentBottom(), BotRPTracker(BotPressure), MLI(C->MLI) {
-
-    TopResourceModel = new VLIWResourceModel(C, InstrItins);
-    BotResourceModel = new VLIWResourceModel(C, InstrItins);
-
 #ifndef NDEBUG
     NumInstrsScheduled = 0;
 #endif
@@ -346,8 +241,6 @@ public:
 
   virtual ~VLIWMachineScheduler() {
     delete SchedImpl;
-    delete TopResourceModel;
-    delete BotResourceModel;
   }
 
   MachineBasicBlock::iterator top() const { return CurrentTop; }
@@ -382,9 +275,6 @@ public:
     return RegionCriticalPSets;
   }
 
-  VLIWResourceModel *getTopResourceModel() { return TopResourceModel; }
-  VLIWResourceModel *getBotResourceModel() { return BotResourceModel; }
-
   /// getIssueWidth - Return the max instructions per scheduling group.
   unsigned getIssueWidth() const {
     return (InstrItins && InstrItins->SchedModel)
@@ -393,9 +283,10 @@ public:
 
   /// getNumMicroOps - Return the number of issue slots required for this MI.
   unsigned getNumMicroOps(MachineInstr *MI) const {
-    if (!InstrItins) return 1;
-    int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass());
-    return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI);
+    return 1;
+    //if (!InstrItins) return 1;
+    //int UOps = InstrItins->getNumMicroOps(MI->getDesc().getSchedClass());
+    //return (UOps >= 0) ? UOps : TII->getNumMicroOps(InstrItins, MI);
   }
 
 private:
@@ -417,6 +308,129 @@ private:
 
   void placeDebugValues();
 };
+
+/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
+/// to balance the schedule.
+class ConvergingVLIWScheduler : public MachineSchedStrategy {
+
+  /// Store the state used by ConvergingVLIWScheduler heuristics, required
+  ///  for the lifetime of one invocation of pickNode().
+  struct SchedCandidate {
+    // The best SUnit candidate.
+    SUnit *SU;
+
+    // Register pressure values for the best candidate.
+    RegPressureDelta RPDelta;
+
+    // Best scheduling cost.
+    int SCost;
+
+    SchedCandidate(): SU(NULL), SCost(0) {}
+  };
+  /// Represent the type of SchedCandidate found within a single queue.
+  enum CandResult {
+    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
+    BestCost};
+
+  /// Each Scheduling boundary is associated with ready queues. It tracks the
+  /// current cycle in whichever direction at has moved, and maintains the state
+  /// of "hazards" and other interlocks at the current cycle.
+  struct SchedBoundary {
+    VLIWMachineScheduler *DAG;
+
+    ReadyQueue Available;
+    ReadyQueue Pending;
+    bool CheckPending;
+
+    ScheduleHazardRecognizer *HazardRec;
+    VLIWResourceModel *ResourceModel;
+
+    unsigned CurrCycle;
+    unsigned IssueCount;
+
+    /// MinReadyCycle - Cycle of the soonest available instruction.
+    unsigned MinReadyCycle;
+
+    // Remember the greatest min operand latency.
+    unsigned MaxMinLatency;
+
+    /// Pending queues extend the ready queues with the same ID and the
+    /// PendingFlag set.
+    SchedBoundary(unsigned ID, const Twine &Name):
+      DAG(0), Available(ID, Name+".A"),
+      Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
+      CheckPending(false), HazardRec(0), ResourceModel(0),
+      CurrCycle(0), IssueCount(0),
+      MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
+
+    ~SchedBoundary() {
+      delete ResourceModel;
+      delete HazardRec;
+    }
+
+    bool isTop() const {
+      return Available.getID() == ConvergingVLIWScheduler::TopQID;
+    }
+
+    bool checkHazard(SUnit *SU);
+
+    void releaseNode(SUnit *SU, unsigned ReadyCycle);
+
+    void bumpCycle();
+
+    void bumpNode(SUnit *SU);
+
+    void releasePending();
+
+    void removeReady(SUnit *SU);
+
+    SUnit *pickOnlyChoice();
+  };
+
+  VLIWMachineScheduler *DAG;
+  const TargetRegisterInfo *TRI;
+
+  // State of the top and bottom scheduled instruction boundaries.
+  SchedBoundary Top;
+  SchedBoundary Bot;
+
+public:
+  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
+  enum {
+    TopQID = 1,
+    BotQID = 2,
+    LogMaxQID = 2
+  };
+
+  ConvergingVLIWScheduler():
+    DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
+
+  virtual void initialize(VLIWMachineScheduler *dag);
+
+  virtual SUnit *pickNode(bool &IsTopNode);
+
+  virtual void schedNode(SUnit *SU, bool IsTopNode);
+
+  virtual void releaseTopNode(SUnit *SU);
+
+  virtual void releaseBottomNode(SUnit *SU);
+
+protected:
+  SUnit *pickNodeBidrectional(bool &IsTopNode);
+
+  int SchedulingCost(ReadyQueue &Q,
+                     SUnit *SU, SchedCandidate &Candidate,
+                     RegPressureDelta &Delta, bool verbose);
+
+  CandResult pickNodeFromQueue(ReadyQueue &Q,
+                               const RegPressureTracker &RPTracker,
+                               SchedCandidate &Candidate);
+#ifndef NDEBUG
+  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
+                      PressureElement P = PressureElement());
+#endif
+};
+
 } // namespace