misched: Added 3-level regpressure back-off.

Introduce the basic strategy for register pressure scheduling.

1) Respect target limits at all times.

2) Indentify critical register classes (pressure sets).
   Track pressure within the scheduled region.
   Avoid increasing scheduled pressure for critical registers.

3) Avoid exceeding the max pressure of the region prior to scheduling.

Added logic for picking between the top and bottom ready Q's based on
regpressure heuristics.

Status: functional but needs to be asjusted to achieve good results.

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

1 files changed, 184 insertions, 36 deletions

diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp
index 1d810fdf16..57f3506d8e 100644
--- a/lib/CodeGen/MachineScheduler.cpp
+++ b/lib/CodeGen/MachineScheduler.cpp
@@ -1,4 +1,4 @@
-//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//
+//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//excess
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -326,10 +326,15 @@ class ScheduleDAGMI : public ScheduleDAGInstrs {
 
   MachineBasicBlock::iterator LiveRegionEnd;
 
-  // Register pressure in this region computed by buildSchedGraph.
+  /// Register pressure in this region computed by buildSchedGraph.
   IntervalPressure RegPressure;
   RegPressureTracker RPTracker;
 
+  /// List of pressure sets that exceed the target's pressure limit before
+  /// scheduling, listed in increasing set ID order. Each pressure set is paired
+  /// with its max pressure in the currently scheduled regions.
+  std::vector<PressureElement> RegionCriticalPSets;
+
   /// The top of the unscheduled zone.
   MachineBasicBlock::iterator CurrentTop;
   IntervalPressure TopPressure;
@@ -380,8 +385,13 @@ public:
   /// Get register pressure for the entire scheduling region before scheduling.
   const IntervalPressure &getRegPressure() const { return RegPressure; }
 
+  const std::vector<PressureElement> &getRegionCriticalPSets() const {
+    return RegionCriticalPSets;
+  }
+
 protected:
   void initRegPressure();
+  void updateScheduledPressure(std::vector<unsigned> NewMaxPressure);
 
   void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
   bool checkSchedLimit();
@@ -515,6 +525,33 @@ void ScheduleDAGMI::initRegPressure() {
     BotRPTracker.recede();
 
   assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom");
+
+  // Cache the list of excess pressure sets in this region. This will also track
+  // the max pressure in the scheduled code for these sets.
+  RegionCriticalPSets.clear();
+  std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure;
+  for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
+    unsigned Limit = TRI->getRegPressureSetLimit(i);
+    if (RegionPressure[i] > Limit)
+      RegionCriticalPSets.push_back(PressureElement(i, 0));
+  }
+  DEBUG(dbgs() << "Excess PSets: ";
+        for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i)
+          dbgs() << TRI->getRegPressureSetName(
+            RegionCriticalPSets[i].PSetID) << " ";
+        dbgs() << "\n");
+}
+
+// FIXME: When the pressure tracker deals in pressure differences then we won't
+// iterate over all RegionCriticalPSets[i].
+void ScheduleDAGMI::
+updateScheduledPressure(std::vector<unsigned> NewMaxPressure) {
+  for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) {
+    unsigned ID = RegionCriticalPSets[i].PSetID;
+    int &MaxUnits = RegionCriticalPSets[i].UnitIncrease;
+    if ((int)NewMaxPressure[ID] > MaxUnits)
+      MaxUnits = NewMaxPressure[ID];
+  }
 }
 
 /// schedule - Called back from MachineScheduler::runOnMachineFunction
@@ -581,6 +618,7 @@ void ScheduleDAGMI::schedule() {
       // Update top scheduled pressure.
       TopRPTracker.advance();
       assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
+      updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure);
 
       // Release dependent instructions for scheduling.
       releaseSuccessors(SU);
@@ -602,6 +640,7 @@ void ScheduleDAGMI::schedule() {
       // Update bottom scheduled pressure.
       BotRPTracker.recede();
       assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
+      updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure);
 
       // Release dependent instructions for scheduling.
       releasePredecessors(SU);
@@ -654,6 +693,8 @@ struct ReadyQ {
 
   bool empty() const { return Queue.empty(); }
 
+  unsigned size() const { return Queue.size(); }
+
   iterator begin() { return Queue.begin(); }
 
   iterator end() { return Queue.end(); }
@@ -689,6 +730,9 @@ class ConvergingScheduler : public MachineSchedStrategy {
 
     SchedCandidate(): SU(NULL) {}
   };
+  /// Represent the type of SchedCandidate found within a single queue.
+  enum CandResult {
+    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure };
 
   ScheduleDAGMI *DAG;
   const TargetRegisterInfo *TRI;
@@ -732,88 +776,197 @@ public:
       BotQueue.push(SU);
   }
 protected:
+  SUnit *pickNodeBidrectional(bool &IsTopNode);
+
+  CandResult pickNodeFromQueue(ReadyQ &Q, const RegPressureTracker &RPTracker,
+                               SchedCandidate &Candidate);
 #ifndef NDEBUG
   void traceCandidate(const char *Label, unsigned QID, SUnit *SU,
-                      int RPDiff, unsigned PSetID);
+                      PressureElement P = PressureElement());
 #endif
-  bool pickNodeFromQueue(ReadyQ &Q, const RegPressureTracker &RPTracker,
-                         SchedCandidate &Candidate);
 };
 } // namespace
 
 #ifndef NDEBUG
 void ConvergingScheduler::
 traceCandidate(const char *Label, unsigned QID, SUnit *SU,
-               int RPDiff, unsigned PSetID) {
+               PressureElement P) {
   dbgs() << Label << getQName(QID) << " ";
-  if (RPDiff)
-    dbgs() << TRI->getRegPressureSetName(PSetID) << ":" << RPDiff << " ";
+  if (P.isValid())
+    dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease
+           << " ";
   else
     dbgs() << "     ";
   SU->dump(DAG);
 }
 #endif
 
+/// Return true if the LHS reg pressure effect is better than RHS.
+static bool compareRPDelta(const RegPressureDelta &LHS,
+                           const RegPressureDelta &RHS) {
+  // Compare each component of pressure in decreasing order of importance
+  // without checking if any are valid. Invalid PressureElements are assumed to
+  // have UnitIncrease==0, so are neutral.
+  if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease)
+    return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease;
+
+  if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease)
+    return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease;
+
+  if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease)
+    return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease;
+
+  return false;
+}
+
+
 /// Pick the best candidate from the top queue.
 ///
 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
 /// DAG building. To adjust for the current scheduling location we need to
 /// maintain the number of vreg uses remaining to be top-scheduled.
-bool ConvergingScheduler::pickNodeFromQueue(ReadyQ &Q,
-                                            const RegPressureTracker &RPTracker,
-                                            SchedCandidate &Candidate) {
+ConvergingScheduler::CandResult ConvergingScheduler::
+pickNodeFromQueue(ReadyQ &Q, const RegPressureTracker &RPTracker,
+                  SchedCandidate &Candidate) {
+
   // getMaxPressureDelta temporarily modifies the tracker.
   RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
 
   // BestSU remains NULL if no top candidates beat the best existing candidate.
-  bool FoundCandidate = false;
+  CandResult FoundCandidate = NoCand;
   for (ReadyQ::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
 
     RegPressureDelta RPDelta;
-    TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta);
+    TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
+                                    DAG->getRegionCriticalPSets(),
+                                    DAG->getRegPressure().MaxSetPressure);
 
+    // Initialize the candidate if needed.
+    if (!Candidate.SU) {
+      Candidate.SU = *I;
+      Candidate.RPDelta = RPDelta;
+      FoundCandidate = NodeOrder;
+      continue;
+    }
     // Avoid exceeding the target's limit.
-    if (!Candidate.SU || RPDelta.ExcessUnits < Candidate.RPDelta.ExcessUnits) {
-      DEBUG(traceCandidate(Candidate.SU ? "PCAND" : "ACAND", Q.ID, *I,
-                           RPDelta.ExcessUnits, RPDelta.ExcessSetID));
+    if (RPDelta.Excess.UnitIncrease < Candidate.RPDelta.Excess.UnitIncrease) {
+      DEBUG(traceCandidate("ECAND", Q.ID, *I, RPDelta.Excess));
       Candidate.SU = *I;
       Candidate.RPDelta = RPDelta;
-      FoundCandidate = true;
+      FoundCandidate = SingleExcess;
       continue;
     }
-    if (RPDelta.ExcessUnits > Candidate.RPDelta.ExcessUnits)
+    if (RPDelta.Excess.UnitIncrease > Candidate.RPDelta.Excess.UnitIncrease)
       continue;
+    if (FoundCandidate == SingleExcess)
+      FoundCandidate = MultiPressure;
 
-    // Avoid increasing the max pressure.
-    if (RPDelta.MaxUnitIncrease < Candidate.RPDelta.MaxUnitIncrease) {
-      DEBUG(traceCandidate("MCAND", Q.ID, *I,
-                           RPDelta.ExcessUnits, RPDelta.ExcessSetID));
+    // Avoid increasing the max critical pressure in the scheduled region.
+    if (RPDelta.CriticalMax.UnitIncrease
+        < Candidate.RPDelta.CriticalMax.UnitIncrease) {
+      DEBUG(traceCandidate("PCAND", Q.ID, *I, RPDelta.CriticalMax));
       Candidate.SU = *I;
       Candidate.RPDelta = RPDelta;
-      FoundCandidate = true;
+      FoundCandidate = SingleCritical;
       continue;
     }
-    if (RPDelta.MaxUnitIncrease > Candidate.RPDelta.MaxUnitIncrease)
+    if (RPDelta.CriticalMax.UnitIncrease
+        > Candidate.RPDelta.CriticalMax.UnitIncrease)
       continue;
+    if (FoundCandidate == SingleCritical)
+      FoundCandidate = MultiPressure;
+
+    // Avoid increasing the max pressure of the entire region.
+    if (RPDelta.CurrentMax.UnitIncrease
+        < Candidate.RPDelta.CurrentMax.UnitIncrease) {
+      DEBUG(traceCandidate("MCAND", Q.ID, *I, RPDelta.CurrentMax));
+      Candidate.SU = *I;
+      Candidate.RPDelta = RPDelta;
+      FoundCandidate = SingleMax;
+      continue;
+    }
+    if (RPDelta.CurrentMax.UnitIncrease
+        > Candidate.RPDelta.CurrentMax.UnitIncrease)
+      continue;
+    if (FoundCandidate == SingleMax)
+      FoundCandidate = MultiPressure;
 
     // Fall through to original instruction order.
-    // Only consider node order if BestSU was chosen from this Q.
-    if (!FoundCandidate)
+    // Only consider node order if Candidate was chosen from this Q.
+    if (FoundCandidate == NoCand)
       continue;
 
     if ((Q.ID == TopQID && (*I)->NodeNum < Candidate.SU->NodeNum)
         || (Q.ID == BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) {
-      DEBUG(traceCandidate("NCAND", Q.ID, *I, 0, 0));
+      DEBUG(traceCandidate("NCAND", Q.ID, *I));
       Candidate.SU = *I;
       Candidate.RPDelta = RPDelta;
-      FoundCandidate = true;
+      FoundCandidate = NodeOrder;
     }
   }
   return FoundCandidate;
 }
 
-/// Pick the best node from either the top or bottom queue to balance the
-/// schedule.
+/// Pick the best candidate node from either the top or bottom queue.
+SUnit *ConvergingScheduler::pickNodeBidrectional(bool &IsTopNode) {
+  // Schedule as far as possible in the direction of no choice. This is most
+  // efficient, but also provides the best heuristics for CriticalPSets.
+  if (BotQueue.size() == 1) {
+    IsTopNode = false;
+    return *BotQueue.begin();
+  }
+  if (TopQueue.size() == 1) {
+    IsTopNode = true;
+    return *TopQueue.begin();
+  }
+  SchedCandidate BotCandidate;
+  // Prefer bottom scheduling when heuristics are silent.
+  CandResult BotResult =
+    pickNodeFromQueue(BotQueue, DAG->getBotRPTracker(), BotCandidate);
+  assert(BotResult != NoCand && "failed to find the first candidate");
+
+  // If either Q has a single candidate that provides the least increase in
+  // Excess pressure, we can immediately schedule from that Q.
+  //
+  // RegionCriticalPSets summarizes the pressure within the scheduled region and
+  // affects picking from either Q. If scheduling in one direction must
+  // increase pressure for one of the excess PSets, then schedule in that
+  // direction first to provide more freedom in the other direction.
+  if (BotResult == SingleExcess || BotResult == SingleCritical) {
+    IsTopNode = false;
+    return BotCandidate.SU;
+  }
+  // Check if the top Q has a better candidate.
+  SchedCandidate TopCandidate;
+  CandResult TopResult =
+    pickNodeFromQueue(TopQueue, DAG->getTopRPTracker(), TopCandidate);
+  assert(TopResult != NoCand && "failed to find the first candidate");
+
+  if (TopResult == SingleExcess || TopResult == SingleCritical) {
+    IsTopNode = true;
+    return TopCandidate.SU;
+  }
+  // If either Q has a single candidate that minimizes pressure above the
+  // original region's pressure pick it.
+  if (BotResult == SingleMax) {
+    IsTopNode = false;
+    return BotCandidate.SU;
+  }
+  if (TopResult == SingleMax) {
+    IsTopNode = true;
+    return TopCandidate.SU;
+  }
+  // Check for a salient pressure difference and pick the best from either side.
+  if (compareRPDelta(TopCandidate.RPDelta, BotCandidate.RPDelta)) {
+    IsTopNode = true;
+    return TopCandidate.SU;
+  }
+  // Otherwise prefer the bottom candidate in node order.
+  IsTopNode = false;
+  return BotCandidate.SU;
+}
+
+/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
 SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) {
   if (DAG->top() == DAG->bottom()) {
     assert(TopQueue.empty() && BotQueue.empty() && "ReadyQ garbage");
@@ -829,12 +982,7 @@ SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) {
     IsTopNode = false;
   }
   else {
-    SchedCandidate Candidate;
-    // Prefer picking from the bottom.
-    pickNodeFromQueue(BotQueue, DAG->getBotRPTracker(), Candidate);
-    IsTopNode =
-      pickNodeFromQueue(TopQueue, DAG->getTopRPTracker(), Candidate);
-    SU = Candidate.SU;
+    SU = pickNodeBidrectional(IsTopNode);
   }
   if (SU->isTopReady()) {
     assert(!TopQueue.empty() && "bad ready count");