[MachineScheduler] Make it easy to derive from GenericScheduler

[jonpa]

Summary

As I am working on a scheduler for SystemZ, I have found that the GenericScheduler is not giving a good performance out-of-the-box.

In order to experiment and develop a good MIScheduler for SystemZ, I found that I could not reuse the existing code easily. I therefore made some static functions member functions instead, and also some other minor changes. I wonder if this is the right way to go.

NextSUs is public to let a SchedStrategy insert a node when it is released.

updateLatencyCounters() is a new method broken out of SchedBoundary::bumpNode(), to let a SchedStrategy do this in SchedNode()

new GenericSchedulerBase member methods:
tryLess(), tryGreater(), tryLatency(), tracePic(), biasPhysRegCopy(), tryPressure()

GenericScheduler:
new method initTryCandRPDelta() broken out of GenericScheduler::tryCandidate, so that SchedStrategy can do this in its implementation of tryCandidate(), which has been made virtual.

---

[MachineScheduler] Make it easy to derive from GenericScheduler

Static methods formerly in MachineScheduler.cpp have been made member methods
in GenericSchedulerBase. Some functionality has been broken out into new
methods.

With this, it is easy to derive a new SchedStrategy and reuse these
functions.

include/llvm/CodeGen/MachineScheduler.h

public:
   const TargetSchedModel *SchedModel;
   SchedRemainder *Rem;
 
   ReadyQueue Available;
   ReadyQueue Pending;
 
   ScheduleHazardRecognizer *HazardRec;
 
+  // For heuristics, keep a list of the nodes that immediately depend on the
+  // most recently scheduled node.
+  SmallPtrSet<const SUnit*, 8> NextSUs;
+
 private:
   /// True if the pending Q should be checked/updated before scheduling another
   /// instruction.
   bool CheckPending;
 
-  // For heuristics, keep a list of the nodes that immediately depend on the
-  // most recently scheduled node.
-  SmallPtrSet<const SUnit*, 8> NextSUs;
-
   /// Number of cycles it takes to issue the instructions scheduled in this
   /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls.
   /// See getStalls().
   unsigned CurrCycle;
 
   /// Micro-ops issued in the current cycle
   unsigned CurrMOps;
 
public:
 
   void bumpCycle(unsigned NextCycle);
 
   void incExecutedResources(unsigned PIdx, unsigned Count);
 
   unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle);
 
   void bumpNode(SUnit *SU);
+  void updateLatencyCounters(SUnit *SU);
 
   void releasePending();
 
   void removeReady(SUnit *SU);
 
   /// Call this before applying any other heuristics to the Available queue.
   /// Updates the Available/Pending Q's if necessary and returns the single
   /// available instruction, or NULL if there are multiple candidates.
protected:
 
   SchedRemainder Rem;
 protected:
   GenericSchedulerBase(const MachineSchedContext *C):
     Context(C), SchedModel(nullptr), TRI(nullptr) {}
 
   void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone,
                  SchedBoundary *OtherZone);
+protected:
+
+  bool tryLess(int TryVal, int CandVal, SchedCandidate &TryCand,
+               SchedCandidate &Cand, CandReason Reason);
+  bool tryGreater(int TryVal, int CandVal, SchedCandidate &TryCand,
+                  SchedCandidate &Cand, CandReason Reason);
+  bool tryLatency(SchedCandidate &TryCand, SchedCandidate &Cand,
+                  SchedBoundary &Zone);
+  void tracePick(const GenericSchedulerBase::SchedCandidate &Cand,
+                 bool IsTop);
+  int biasPhysRegCopy(const SUnit *SU, bool isTop);
+  bool tryPressure(const PressureChange &TryP, const PressureChange &CandP,
+                   SchedCandidate &TryCand, SchedCandidate &Cand,
+                   CandReason Reason, const TargetRegisterInfo *TRI,
+                   const MachineFunction &MF);
 
 #ifndef NDEBUG
   void traceCandidate(const SchedCandidate &Cand);
 #endif
 };
 
 /// GenericScheduler shrinks the unscheduled zone using heuristics to balance
 /// the schedule.
 class GenericScheduler : public GenericSchedulerBase {
+protected:
   ScheduleDAGMILive *DAG;
 
   // State of the top and bottom scheduled instruction boundaries.
   SchedBoundary Top;
   SchedBoundary Bot;
 
   MachineSchedPolicy RegionPolicy;
 public:
void releaseBottomNode(SUnit *SU) override {
     Bot.releaseBottomNode(SU);
   }
 
   void registerRoots() override;
 
 protected:
   void checkAcyclicLatency();
 
-  void tryCandidate(SchedCandidate &Cand,
+  virtual void tryCandidate(SchedCandidate &Cand,
                             SchedCandidate &TryCand,
                             SchedBoundary &Zone,
                             const RegPressureTracker &RPTracker,
                             RegPressureTracker &TempTracker);
 
+  void initTryCandRPDelta(SchedCandidate &TryCand, SchedBoundary &Zone,
+                          const RegPressureTracker &RPTracker,
+                          RegPressureTracker &TempTracker);
+
   SUnit *pickNodeBidirectional(bool &IsTopNode);
 
   void pickNodeFromQueue(SchedBoundary &Zone,
                          const RegPressureTracker &RPTracker,
                          SchedCandidate &Candidate);
 
   void reschedulePhysRegCopies(SUnit *SU, bool isTop);
 };

lib/CodeGen/MachineScheduler.cpp

if (SU->hasReservedResource) {
               std::max(getNextResourceCycle(PIdx, 0), NextCycle + PI->Cycles);
           }
           else
             ReservedCycles[PIdx] = NextCycle;
         }
       }
     }
   }
-  // Update ExpectedLatency and DependentLatency.
-  unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
-  unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
-  if (SU->getDepth() > TopLatency) {
-    TopLatency = SU->getDepth();
-    DEBUG(dbgs() << "  " << Available.getName()
-          << " TopLatency SU(" << SU->NodeNum << ") " << TopLatency << "c\n");
-  }
-  if (SU->getHeight() > BotLatency) {
-    BotLatency = SU->getHeight();
-    DEBUG(dbgs() << "  " << Available.getName()
-          << " BotLatency SU(" << SU->NodeNum << ") " << BotLatency << "c\n");
-  }
+
+  updateLatencyCounters(SU);
+
   // If we stall for any reason, bump the cycle.
   if (NextCycle > CurrCycle) {
     bumpCycle(NextCycle);
   }
   else {
     // After updating ZoneCritResIdx and ExpectedLatency, check if we're
     // resource limited. If a stall occurred, bumpCycle does this.
     unsigned LFactor = SchedModel->getLatencyFactor();
void SchedBoundary::bumpNode(SUnit *SU) {
   while (CurrMOps >= SchedModel->getIssueWidth()) {
     DEBUG(dbgs() << "  *** Max MOps " << CurrMOps
           << " at cycle " << CurrCycle << '\n');
     bumpCycle(++NextCycle);
   }
   DEBUG(dumpScheduledState());
 }
 
+/// Update ExpectedLatency and DependentLatency.
+void SchedBoundary::updateLatencyCounters(SUnit *SU) {
+  unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
+  unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
+  if (SU->getDepth() > TopLatency) {
+    TopLatency = SU->getDepth();
+    DEBUG(dbgs() << "  " << Available.getName()
+          << " TopLatency SU(" << SU->NodeNum << ") " << TopLatency << "c\n");
+  }
+  if (SU->getHeight() > BotLatency) {
+    BotLatency = SU->getHeight();
+    DEBUG(dbgs() << "  " << Available.getName()
+          << " BotLatency SU(" << SU->NodeNum << ") " << BotLatency << "c\n");
+  }
+}
+
 /// Release pending ready nodes in to the available queue. This makes them
 /// visible to heuristics.
 void SchedBoundary::releasePending() {
   // If the available queue is empty, it is safe to reset MinReadyCycle.
   if (Available.empty())
     MinReadyCycle = UINT_MAX;
 
   // Check to see if any of the pending instructions are ready to issue.  If
if (Latency)
     dbgs() << " " << Latency << " cycles ";
   else
     dbgs() << "          ";
   dbgs() << '\n';
 }
 #endif
 
 /// Return true if this heuristic determines order.
-static bool tryLess(int TryVal, int CandVal,
-                    GenericSchedulerBase::SchedCandidate &TryCand,
-                    GenericSchedulerBase::SchedCandidate &Cand,
-                    GenericSchedulerBase::CandReason Reason) {
+bool GenericSchedulerBase::tryLess(int TryVal, int CandVal,
+                                   SchedCandidate &TryCand,
+                                   SchedCandidate &Cand,
+                                   CandReason Reason) {
   if (TryVal < CandVal) {
     TryCand.Reason = Reason;
     return true;
   }
   if (TryVal > CandVal) {
     if (Cand.Reason > Reason)
       Cand.Reason = Reason;
     return true;
   }
   Cand.setRepeat(Reason);
   return false;
 }
 
-static bool tryGreater(int TryVal, int CandVal,
-                       GenericSchedulerBase::SchedCandidate &TryCand,
-                       GenericSchedulerBase::SchedCandidate &Cand,
-                       GenericSchedulerBase::CandReason Reason) {
+bool GenericSchedulerBase::tryGreater(int TryVal, int CandVal,
+                                      SchedCandidate &TryCand,
+                                      SchedCandidate &Cand,
+                                      CandReason Reason) {
   if (TryVal > CandVal) {
     TryCand.Reason = Reason;
     return true;
   }
   if (TryVal < CandVal) {
     if (Cand.Reason > Reason)
       Cand.Reason = Reason;
     return true;
   }
   Cand.setRepeat(Reason);
   return false;
 }
 
-static bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
-                       GenericSchedulerBase::SchedCandidate &Cand,
+bool GenericSchedulerBase::tryLatency(SchedCandidate &TryCand,
+                                      SchedCandidate &Cand,
                                       SchedBoundary &Zone) {
   if (Zone.isTop()) {
     if (Cand.SU->getDepth() > Zone.getScheduledLatency()) {
       if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(),
                   TryCand, Cand, GenericSchedulerBase::TopDepthReduce))
         return true;
     }
     if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(),
                    TryCand, Cand, GenericSchedulerBase::TopPathReduce))
       return true;
   }
   else {
     if (Cand.SU->getHeight() > Zone.getScheduledLatency()) {
       if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(),
                   TryCand, Cand, GenericSchedulerBase::BotHeightReduce))
         return true;
     }
     if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),
                    TryCand, Cand, GenericSchedulerBase::BotPathReduce))
       return true;
   }
   return false;
 }
 
-static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand,
-                      bool IsTop) {
+void GenericSchedulerBase::
+tracePick(const GenericSchedulerBase::SchedCandidate &Cand, bool IsTop) {
   DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")
         << GenericSchedulerBase::getReasonStr(Cand.Reason) << '\n');
 }
 
 void GenericScheduler::initialize(ScheduleDAGMI *dag) {
   assert(dag->hasVRegLiveness() &&
          "(PreRA)GenericScheduler needs vreg liveness");
   DAG = static_cast<ScheduleDAGMILive*>(dag);
void GenericScheduler::registerRoots() {
   }
 
   if (EnableCyclicPath) {
     Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();
     checkAcyclicLatency();
   }
 }
 
-static bool tryPressure(const PressureChange &TryP,
+bool GenericSchedulerBase::tryPressure(const PressureChange &TryP,
                                        const PressureChange &CandP,
-                        GenericSchedulerBase::SchedCandidate &TryCand,
-                        GenericSchedulerBase::SchedCandidate &Cand,
-                        GenericSchedulerBase::CandReason Reason,
+                                       SchedCandidate &TryCand,
+                                       SchedCandidate &Cand,
+                                       CandReason Reason,
                                        const TargetRegisterInfo *TRI,
                                        const MachineFunction &MF) {
   unsigned TryPSet = TryP.getPSetOrMax();
   unsigned CandPSet = CandP.getPSetOrMax();
   // If both candidates affect the same set, go with the smallest increase.
   if (TryPSet == CandPSet) {
     return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand,
                    Reason);
   }
   // If one candidate decreases and the other increases, go with it.

 
 /// Minimize physical register live ranges. Regalloc wants them adjacent to
 /// their physreg def/use.
 ///
 /// FIXME: This is an unnecessary check on the critical path. Most are root/leaf
 /// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled
 /// with the operation that produces or consumes the physreg. We'll do this when
 /// regalloc has support for parallel copies.
-static int biasPhysRegCopy(const SUnit *SU, bool isTop) {
+int GenericSchedulerBase::biasPhysRegCopy(const SUnit *SU, bool isTop) {
   const MachineInstr *MI = SU->getInstr();
   if (!MI->isCopy())
     return 0;
 
   unsigned ScheduledOper = isTop ? 1 : 0;
   unsigned UnscheduledOper = isTop ? 0 : 1;
   // If we have already scheduled the physreg produce/consumer, immediately
   // schedule the copy.
   if (TargetRegisterInfo::isPhysicalRegister(
         MI->getOperand(ScheduledOper).getReg()))
     return 1;
   // If the physreg is at the boundary, defer it. Otherwise schedule it
   // immediately to free the dependent. We can hoist the copy later.
   bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft;
   if (TargetRegisterInfo::isPhysicalRegister(
         MI->getOperand(UnscheduledOper).getReg()))
     return AtBoundary ? -1 : 1;
   return 0;
 }
 
-/// Apply a set of heursitics to a new candidate. Heuristics are currently
-/// hierarchical. This may be more efficient than a graduated cost model because
-/// we don't need to evaluate all aspects of the model for each node in the
-/// queue. But it's really done to make the heuristics easier to debug and
-/// statistically analyze.
-///
-/// \param Cand provides the policy and current best candidate.
-/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
-/// \param Zone describes the scheduled zone that we are extending.
-/// \param RPTracker describes reg pressure within the scheduled zone.
-/// \param TempTracker is a scratch pressure tracker to reuse in queries.
-void GenericScheduler::tryCandidate(SchedCandidate &Cand,
-                                    SchedCandidate &TryCand,
+void GenericScheduler::initTryCandRPDelta(SchedCandidate &TryCand,
                                           SchedBoundary &Zone,
                                           const RegPressureTracker &RPTracker,
                                           RegPressureTracker &TempTracker) {
-
   if (DAG->isTrackingPressure()) {
     // Always initialize TryCand's RPDelta.
     if (Zone.isTop()) {
       TempTracker.getMaxDownwardPressureDelta(
         TryCand.SU->getInstr(),
         TryCand.RPDelta,
         DAG->getRegionCriticalPSets(),
         DAG->getRegPressure().MaxSetPressure);
else {
           DAG->getRegPressure().MaxSetPressure);
       }
     }
   }
   DEBUG(if (TryCand.RPDelta.Excess.isValid())
           dbgs() << "  Try  SU(" << TryCand.SU->NodeNum << ") "
                  << TRI->getRegPressureSetName(TryCand.RPDelta.Excess.getPSet())
                  << ":" << TryCand.RPDelta.Excess.getUnitInc() << "\n");
+}
+
+/// Apply a set of heursitics to a new candidate. Heuristics are currently
+/// hierarchical. This may be more efficient than a graduated cost model because
+/// we don't need to evaluate all aspects of the model for each node in the
+/// queue. But it's really done to make the heuristics easier to debug and
+/// statistically analyze.
+///
+/// \param Cand provides the policy and current best candidate.
+/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
+/// \param Zone describes the scheduled zone that we are extending.
+/// \param RPTracker describes reg pressure within the scheduled zone.
+/// \param TempTracker is a scratch pressure tracker to reuse in queries.
+void GenericScheduler::tryCandidate(SchedCandidate &Cand,
+                                    SchedCandidate &TryCand,
+                                    SchedBoundary &Zone,
+                                    const RegPressureTracker &RPTracker,
+                                    RegPressureTracker &TempTracker) {
+
+  initTryCandRPDelta(TryCand, Zone, RPTracker, TempTracker);
 
   // Initialize the candidate if needed.
   if (!Cand.isValid()) {
     TryCand.Reason = NodeOrder;
     return;
   }
 
   if (tryGreater(biasPhysRegCopy(TryCand.SU, Zone.isTop()),