[Refactor] Add the SchedHeuristic for Scheduler to allow platform customizing the heuristics

[qiucf]

Summary

Hi, all, I want to add a new SchedHeuristic to track all the heuristic Scheduler used basing on the follow facts.

1. It is hard for target to add new heuristic now, as the Reason and tryCandidate() are maintained by base class.
2. It is hard for target to change the priority of each heuristic(i.e. prefer cluster over stall) as it is hard code by tryCandidate.
3. We assume the value of the Reason matches the priority in the tryCandidate which is easy to be out of sync. And it is out of sync now in fact. (see Stall and TopDepthReduce, we don't know their priority as it is changed according to input)
4. The duplicated heuristic between pre-ra and post-ra scheduler. (There are many duplicate code between these two tryCandidate)

As PowerPC target want to add more and more heuristic, and we are struggling to deal with this, so, this is the motivation of this refactor and welcome for comments.

What I did now:

• Each heuristic is an instance of the SchedHeuristic
• Predefine all the heuristic we have now.
• All the active heuristics are put into a vector and its position in the vector means its priority.
• To add a new heuristic, just need to define a new instance of SchedHeuristic with Name and heuristic call back, then, call registerHeuristic() into any position of the vector.

[foad]

It is hard for target to add new heuristic now, as the Reason and tryCandidate() are maintained by base class.
It is hard for target to change the priority of each heuristic(i.e. prefer cluster over stall) as it is hard code by tryCandidate.

I agree. For the AMDGPU scheduler I am very interested in latency and register pressure, and not very interested in the other heuristics. I look forward to be being able to tweak this in the target sched strategy.

[qiucf]

llvm/include/llvm/CodeGen/MachineScheduler.h

1159

So every time we'll need to iterate over this list? Maybe we can add a field like rank in SchedHeuristic and auto-fill them in registering?

llvm/lib/CodeGen/MachineScheduler.cpp

2544

Use #define STR(X) #X?

2707

Use StringSwitch for below?

[steven.zhang]

Add helper macro to make the code more tidy and remove the tryGreater as it is not needed any more.

[steven.zhang]

Address reviewer's comments.

[steven.zhang]

In D86684#2241416, @foad wrote:

It is hard for target to add new heuristic now, as the Reason and tryCandidate() are maintained by base class.
It is hard for target to change the priority of each heuristic(i.e. prefer cluster over stall) as it is hard code by tryCandidate.

I agree. For the AMDGPU scheduler I am very interested in latency and register pressure, and not very interested in the other heuristics. I look forward to be being able to tweak this in the target sched strategy.

Yes, PowerPC also has some specific requirement on the sched strategy.

[steven.zhang]

Reimplement with class instead of object for heuristics.

[steven.zhang]

Gentle ping ...

[dmgreen]

Hello. This looks interesting. I've run into places before where we just wanted to add an extra heuristics. I think some of our downstream schedules go a bit beyond this and would still need to override tryCandidate (the merge is going to be a pain!), but I've run into situations where it would definitely be useful.

This does add some non-inlineable virtual dispatch to a rather hot part of the compiler though. Do you have compile time numbers, to make sure this isn't going to cause any problems?

llvm/include/llvm/CodeGen/MachineScheduler.h

1099

I would personally just keep everything as protected.

llvm/lib/Target/PowerPC/PPCMachineScheduler.h

56–59

None of these seems to do anything, beyond calling the base class. It's almost a shame to have to create a subclass of PostGenericScheduler just to add an extra heuristic. As opposed to being able to register them like mutations.

I imagine that a lot of the time these would end up doing something though and the scheduler would end up holding some state. That would be the case for our downstream schedulers I think. So I think this is fine as-is, but you might want to think a bit about how it would be possible to register without needing to subclass.

[steven.zhang]

Hello. This looks interesting. I've run into places before where we just wanted to add an extra heuristics. I think some of our downstream schedules go a bit beyond this and would still need to override tryCandidate (the merge is going to be a pain!), but I've run into situations where it would definitely be useful.

Yes, our downstream scheduler also has the same pain. And what we can do now is to duplicate the tryCandidate and update it, which is hard to maintain. See D86681 .

This does add some non-inlineable virtual dispatch to a rather hot part of the compiler though. Do you have compile time numbers, to make sure this isn't going to cause any problems?

I will take this concern into consideration and evaluate the compiling time.

llvm/include/llvm/CodeGen/MachineScheduler.h

1099

We have to declare the DAG as private as the subclass GenericScheduler/PostGenericScheduler both already keep it with different type. For the Heuristics, yes, we can make it as protected.

llvm/lib/Target/PowerPC/PPCMachineScheduler.h

56–59

Good suggestion. I think, we can keep the state inside the heuristic and add some necessary interface to initialize the state, update the state, and compare the candidate. Then, we can do it the same as mutation without subclass the scheduler. I will try with this direction.

[steven.zhang]

Address reviewer's comments.

The Scheduler Strategy owns the SchedHeuristics, and the PreRA/PostRA Scheduler owns the Scheduler Strategy. So, we are now registering the heuristics inside Scheduler, so that, the target don't need to subclass the Scheduler Strategy.

However, as the scheduler heuristics might change from scheduler regions(we will override the region policy before scheduling the region), we have to subclass the Scheduler to register heuristics whenever we are entering a new sched region.

Regarding to the compiling time, yes, the virtual dispatch will increase compiling time (63s ->76s) from my testing. Fix this by using function object, and I didn't see compiling time deg now.

Regarding to the PowerPC tests change, it is a known issue of our scheduler heuristic, which is addressed by D86681. I abandon D86681 and merge it into this patch. If have concern on this, I can split it. The test change in this patch is completely the same as D86681.

Add two callbacks inside SchedHeuristic for target to maintain the internal state. @dmgreen Does it work for your downstream scheduler ?

• initialize (It is called whenever we are entering a new sched region)
• update (It is called whenever an instruction is scheduled.)

This is the typical case for target to add new heuristic:

• subclass the SchedHeuristic and add private state as class member variable.
• SchedHeuristic::initialize() Reset the state
• SchedHeuristic::update() Update the state with the new DAG
• SchedHeuristic::tryCandidate() Select the instruction according to current state.

[dmgreen]

Our downstream schedulers override pickNode/pickNext and have a certain amount of lookahead. We probably wouldn't be able to make use of this. I have in the past wanted to write a heuristic that this would fit this really nicely - it needed the last scheduled instruction and would bias based on whether they could "overlap". Unfortunately I never managed to get it to actually make performance reliably better.

I am a little surprised that, if virtual dispatch was hurting performance so much, function pointer would end up being a lot better. It's still a similar indirect non inlinable/optimisable function call.

llvm/include/llvm/CodeGen/MachineScheduler.h

1428

These are lowercase because they act like functions, not like variables?

llvm/lib/CodeGen/MachineScheduler.cpp

1495

You can probably just add an extra tracePick function, removing the need for this heuristic.

[steven.zhang]

I am a little surprised that, if virtual dispatch was hurting performance so much, function pointer would end up being a lot better. It's still a similar indirect non inlinable/optimisable function call.

I think, the virtual dispatch has two memory dereference(one for vtable and another one for virtual func) while the function pointer only need one. And I am not sure if compiler can do some better optimization if there isn't any virtual function for a class. I double confirm and it indeed shows that, the new implementation didn't have any compiling time deg now.

Address other comments.

[steven.zhang]

llvm/include/llvm/CodeGen/MachineScheduler.h

1428

Yes. I add member function to avoid such confusion.

llvm/lib/CodeGen/MachineScheduler.cpp

1495

Good idea. Done.

[dmgreen]

This seems OK to me, if you can get some others to agree.

[steven.zhang]

Thank you Dave. Can someone from other target have a look at this refactor to see if there is any problems ?

[steven.zhang]

Gentle ping ...

[foad]

llvm/include/llvm/CodeGen/MachineScheduler.h

441

Typo disbaled.

[steven.zhang]

Address comments.

[steven.zhang]

Gentle ping...

[steven.zhang]

Ping ...

[steven.zhang]

Rebase the patch.

[qiucf]

I think if the intention is to re-use some generic code in tryCandidate, can we use a lighter approach? For example, make return value type of tryCandidate from void to bool, so that target override can call GenericScheduler::tryCandidate.

llvm/include/llvm/CodeGen/MachineScheduler.h

public:
   ~ScheduleDAGMILive() override;
 
   /// Return true if this DAG supports VReg liveness and RegPressure.
   bool hasVRegLiveness() const override { return true; }
 
   /// Return true if register pressure tracking is enabled.
   bool isTrackingPressure() const { return ShouldTrackPressure; }
 
   /// Get current register pressure for the top scheduled instructions.
   const IntervalPressure &getTopPressure() const { return TopPressure; }
   const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
 
   /// Get current register pressure for the bottom scheduled instructions.
   const IntervalPressure &getBotPressure() const { return BotPressure; }
   const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
 
   /// Get register pressure for the entire scheduling region before scheduling.
public:
   /// 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.
   SUnit *pickOnlyChoice();
 
   void dumpScheduledState() const;
 };
 
+unsigned getWeakLeft(const SUnit *SU, bool isTop);
+
 /// Base class for GenericScheduler. This class maintains information about
 /// scheduling candidates based on TargetSchedModel making it easy to implement
 /// heuristics for either preRA or postRA scheduling.
 class GenericSchedulerBase : public MachineSchedStrategy {
 public:
-  /// Represent the type of SchedCandidate found within a single queue.
-  /// pickNodeBidirectional depends on these listed by decreasing priority.
-  enum CandReason : uint8_t {
-    NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster, Weak,
-    RegMax, ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
-    TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
-
-#ifndef NDEBUG
-  static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
-#endif
-
   /// Policy for scheduling the next instruction in the candidate's zone.
   struct CandPolicy {
     bool ReduceLatency = false;
     unsigned ReduceResIdx = 0;
     unsigned DemandResIdx = 0;
 
     CandPolicy() = default;
 
bool operator==(const SchedResourceDelta &RHS) const {
       return CritResources == RHS.CritResources
         && DemandedResources == RHS.DemandedResources;
     }
     bool operator!=(const SchedResourceDelta &RHS) const {
       return !operator==(RHS);
     }
   };
 
+  struct SchedCandidate;
+  /// Represent the heuristic we used for either PreRA or PostRA scheduling.
+  struct SchedHeuristic {
+    SchedHeuristic(StringRef Name) : Name(Name) {}
+    virtual ~SchedHeuristic() {}
+
+    // Return either the Cand or TryCand if either wins, otherwise return
+    // nullptr if none wins.
+    virtual SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                                SchedBoundary *Zone) {
+      return nullptr;
+    };
+    // Heuristic name
+    std::string Name;
+    // The priority of this heuristic. The smaller the higher priority.
+    int Priority = -1;
+  };
+
+  // Bias PhysReg Defs and copies to their uses and defined respectively.
+  struct PhysRegHeuristic : public SchedHeuristic {
+    PhysRegHeuristic() : SchedHeuristic("PYHS-REG") {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      return tryLess(biasPhysReg(TryCand.SU, TryCand.AtTop),
+                     biasPhysReg(Cand.SU, Cand.AtTop), Cand, TryCand);
+    }
+  };
+
+  // Fall through to original instruction order.
+  struct NodeOrderHeuristic : public SchedHeuristic {
+    NodeOrderHeuristic() : SchedHeuristic("ORDER") {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (Zone && ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) ||
+                   (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)))
+        return &TryCand;
+      return nullptr;
+    }
+  };
+
+  // Debug use only
+  struct Only1Heuristic : public SchedHeuristic {
+    Only1Heuristic() : SchedHeuristic("ONLY1") {}
+  };
+
+  // Weak edges are for clustering and other constraints.
+  struct WeakHeuristic : public SchedHeuristic {
+    WeakHeuristic() : SchedHeuristic("WEAK") {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone)
+        return nullptr;
+      return tryLess(getWeakLeft(TryCand.SU, TryCand.AtTop),
+                     getWeakLeft(Cand.SU, Cand.AtTop), TryCand, Cand);
+    }
+  };
+
+  // Prioritize instructions that read unbuffered resources by stall cycles.
+  struct StallHeuristic : public SchedHeuristic {
+    StallHeuristic() : SchedHeuristic("STALL") {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone)
+        return nullptr;
+      return tryLess(Zone->getLatencyStallCycles(TryCand.SU),
+                     Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand);
+    }
+  };
+
+  // Keep clustered nodes together to encourage downstream peephole
+  // optimizations which may reduce resource requirements.
+  // This is a best effort to set things up for a post-RA pass.
+  // Optimizations like generating loads of multiple registers should ideally
+  // be done within the scheduler pass by combining the loads during DAG
+  // postprocessing.
+  struct ClusterHeuristic : public SchedHeuristic {
+    ScheduleDAGMI *&DAG;
+    ClusterHeuristic(ScheduleDAGMI *&DAG)
+        : SchedHeuristic("CLUSTER"), DAG(DAG) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      const SUnit *CandNextClusterSU =
+          Cand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
+      const SUnit *TryCandNextClusterSU =
+          TryCand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
+      return tryLess(TryCand.SU == TryCandNextClusterSU,
+                     Cand.SU == CandNextClusterSU, Cand, TryCand);
+    }
+  };
+
+  // For loops that are acyclic path limited, aggressively schedule for latency.
+  // Within an single cycle, whenever CurrMOps > 0, allow normal heuristics to
+  // take precedence.
+  // Prefer the candidate with the lesser depth, but only if one of them has
+  // depth greater than the total latency scheduled so far, otherwise either of
+  // them could be scheduled now with no stall.
+  struct TopDepthReduceHeuristic : public SchedHeuristic {
+    bool AcyLimited = false;
+    SchedRemainder &Rem;
+    TopDepthReduceHeuristic(SchedRemainder &Rem, bool AcyLimited = false)
+        : SchedHeuristic("TOP-DEPTH"), AcyLimited(AcyLimited), Rem(Rem) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone || !Zone->isTop())
+        return nullptr;
+      if (AcyLimited && (!Rem.IsAcyclicLatencyLimited || Zone->getCurrMOps()))
+        return nullptr;
+      if (!AcyLimited &&
+          (!TryCand.Policy.ReduceLatency || Rem.IsAcyclicLatencyLimited))
+        return nullptr;
+      if (std::max(TryCand.SU->getDepth(), Cand.SU->getDepth()) <=
+          Zone->getScheduledLatency())
+        return nullptr;
+      return tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(), TryCand,
+                     Cand);
+    }
+  };
+
+  struct TopPathReduceHeuristic : public SchedHeuristic {
+    bool AcyLimited = false;
+    SchedRemainder &Rem;
+    TopPathReduceHeuristic(SchedRemainder &Rem, bool AcyLimited = false)
+        : SchedHeuristic("TOP-PATH"), AcyLimited(AcyLimited), Rem(Rem) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone || !Zone->isTop())
+        return nullptr;
+      if (AcyLimited && (!Rem.IsAcyclicLatencyLimited || Zone->getCurrMOps()))
+        return nullptr;
+      if (!AcyLimited &&
+          (!TryCand.Policy.ReduceLatency || Rem.IsAcyclicLatencyLimited))
+        return nullptr;
+      return tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(), Cand,
+                     TryCand);
+    }
+  };
+
+  // Prefer the candidate with the lesser height, but only if one of them
+  // has height greater than the total latency scheduled so far, otherwise
+  // either of them could be scheduled now with no stall.
+  struct BotHeightReduceHeuristic : public SchedHeuristic {
+    bool AcyLimited = false;
+    SchedRemainder &Rem;
+    BotHeightReduceHeuristic(SchedRemainder &Rem, bool AcyLimited = false)
+        : SchedHeuristic("BOT-HEIGHT"), AcyLimited(AcyLimited), Rem(Rem) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone || Zone->isTop())
+        return nullptr;
+      if (AcyLimited && (!Rem.IsAcyclicLatencyLimited || Zone->getCurrMOps()))
+        return nullptr;
+      if (!AcyLimited &&
+          (!TryCand.Policy.ReduceLatency || Rem.IsAcyclicLatencyLimited))
+        return nullptr;
+      if (std::max(TryCand.SU->getHeight(), Cand.SU->getHeight()) <=
+          Zone->getScheduledLatency())
+        return nullptr;
+      return tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(), TryCand,
+                     Cand);
+    }
+  };
+
+  struct BotPathReduceHeuristic : public SchedHeuristic {
+    bool AcyLimited = false;
+    SchedRemainder &Rem;
+    BotPathReduceHeuristic(SchedRemainder &Rem, bool AcyLimited = false)
+        : SchedHeuristic("BOT-PATH"), AcyLimited(AcyLimited), Rem(Rem) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone || Zone->isTop())
+        return nullptr;
+      if (AcyLimited && (!Rem.IsAcyclicLatencyLimited || Zone->getCurrMOps()))
+        return nullptr;
+      if (!AcyLimited &&
+          (!TryCand.Policy.ReduceLatency || Rem.IsAcyclicLatencyLimited))
+        return nullptr;
+      return tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(), Cand,
+                     TryCand);
+    }
+  };
+
+  // Avoid critical resource consumption and balance the schedule.
+  struct ResourceReduceHeuristic : public SchedHeuristic {
+    bool initResource = false;
+    ScheduleDAGMI *&DAG;
+    const TargetSchedModel *&SchedModel;
+    ResourceReduceHeuristic(ScheduleDAGMI *&DAG,
+                            const TargetSchedModel *&SchedModel,
+                            bool initResource = true)
+        : SchedHeuristic("RES-REDUCE"), initResource(initResource), DAG(DAG),
+          SchedModel(SchedModel) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone)
+        return nullptr;
+      if (initResource)
+        TryCand.initResourceDelta(DAG, SchedModel);
+      return tryLess(TryCand.ResDelta.CritResources,
+                     Cand.ResDelta.CritResources, TryCand, Cand);
+    }
+  };
+
+  struct ResourceDemandHeuristic : public SchedHeuristic {
+    ResourceDemandHeuristic() : SchedHeuristic("RES-DEMAND") {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      if (!Zone)
+        return nullptr;
+      return tryLess(TryCand.ResDelta.DemandedResources,
+                     Cand.ResDelta.DemandedResources, Cand, TryCand);
+    }
+  };
+
   /// Store the state used by GenericScheduler heuristics, required for the
   /// lifetime of one invocation of pickNode().
   struct SchedCandidate {
     CandPolicy Policy;
 
     // The best SUnit candidate.
     SUnit *SU;
 
-    // The reason for this candidate.
-    CandReason Reason;
+    // The heuristic reason for this candidate.
+    const SchedHeuristic *Reason = nullptr;
 
     // Whether this candidate should be scheduled at top/bottom.
     bool AtTop;
 
     // Register pressure values for the best candidate.
     RegPressureDelta RPDelta;
 
     // Critical resource consumption of the best candidate.
     SchedResourceDelta ResDelta;
 
     SchedCandidate() { reset(CandPolicy()); }
     SchedCandidate(const CandPolicy &Policy) { reset(Policy); }
 
     void reset(const CandPolicy &NewPolicy) {
       Policy = NewPolicy;
       SU = nullptr;
-      Reason = NoCand;
+      Reason = nullptr;
       AtTop = false;
       RPDelta = RegPressureDelta();
       ResDelta = SchedResourceDelta();
     }
 
     bool isValid() const { return SU; }
 
     // Copy the status of another candidate without changing policy.
     void setBest(SchedCandidate &Best) {
-      assert(Best.Reason != NoCand && "uninitialized Sched candidate");
+      assert(Best.Reason && "uninitialized Sched candidate");
       SU = Best.SU;
       Reason = Best.Reason;
       AtTop = Best.AtTop;
       RPDelta = Best.RPDelta;
       ResDelta = Best.ResDelta;
     }
 
     void initResourceDelta(const ScheduleDAGMI *DAG,
                            const TargetSchedModel *SchedModel);
   };
 
+private:
+  // Keep all the heuristics. Notice that, the earlier it is pushed into the
+  // vector, the higher priority it has.
+  SmallVector<SchedHeuristic *, 8> Heuristics;
+  ScheduleDAGMI *DAG = nullptr;
+
 protected:
   const MachineSchedContext *Context;
   const TargetSchedModel *SchedModel = nullptr;
   const TargetRegisterInfo *TRI = nullptr;
 
   SchedRemainder Rem;
 
-  GenericSchedulerBase(const MachineSchedContext *C) : Context(C) {}
+  // Predefined heuristics
+  PhysRegHeuristic PhysReg;
+  NodeOrderHeuristic NodeOrder;
+  Only1Heuristic Only1;
+  StallHeuristic Stall;
+  ClusterHeuristic Cluster;
+  TopDepthReduceHeuristic AcyLimitedTopDepthReduce;
+  TopPathReduceHeuristic AcyLimitedTopPathReduce;
+  BotHeightReduceHeuristic AcyLimitedBotHeightReduce;
+  BotPathReduceHeuristic AcyLimitedBotPathReduce;
+  ResourceReduceHeuristic ResourceReduce;
+  ResourceDemandHeuristic ResourceDemand;
+  TopDepthReduceHeuristic TopDepthReduce;
+  TopPathReduceHeuristic TopPathReduce;
+  BotHeightReduceHeuristic BotHeightReduce;
+  BotPathReduceHeuristic BotPathReduce;
+  WeakHeuristic Weak;
+
+  GenericSchedulerBase(const MachineSchedContext *C)
+      : Context(C), Cluster(DAG), AcyLimitedTopDepthReduce(Rem, true),
+        AcyLimitedTopPathReduce(Rem, true),
+        AcyLimitedBotHeightReduce(Rem, true),
+        AcyLimitedBotPathReduce(Rem, true),
+        ResourceReduce(DAG, SchedModel, true), TopDepthReduce(Rem),
+        TopPathReduce(Rem), BotHeightReduce(Rem), BotPathReduce(Rem) {}
 
   void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone,
                  SchedBoundary *OtherZone);
 
+  void initialize(ScheduleDAGMI *Dag) override;
+
+  void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
+                    SchedBoundary *Zone) const;
+
+  bool hasHigherPriority(const SchedHeuristic *Reason1,
+                         const SchedHeuristic *Reason2) const {
+    if (!Reason1)
+      return false;
+    if (!Reason2)
+      return true;
+    assert(Reason1->Priority >= 0 && Reason2->Priority >= 0 &&
+           "Uninitialized heuristic priority");
+    return Reason1->Priority < Reason2->Priority;
+  }
+
+  void registerHeuristic(SchedHeuristic &Heuristic,
+                         SchedHeuristic *Before = nullptr) {
+    assert(!std::count(Heuristics.begin(), Heuristics.end(), &Heuristic) &&
+           "Heuristic is added multiple times");
+    if (!Before)
+      Heuristics.push_back(&Heuristic);
+    else {
+      auto Pos = std::find(Heuristics.begin(), Heuristics.end(), Before);
+      assert(Pos != Heuristics.end() &&
+             "Don't know how to register the heuristics");
+      Heuristics.insert(Pos, &Heuristic);
+    }
+  }
+
+  // Register all the heuristics.
+  virtual void registerHeuristics(){};
+
 #ifndef NDEBUG
-  void traceCandidate(const SchedCandidate &Cand);
+  virtual void traceCandidate(const SchedCandidate &Cand);
 #endif
 
+  // Utility functions used by heuristics in tryCandidate().
+  static SchedCandidate *tryLess(int TryVal, int CandVal,
+                                 SchedCandidate &TryCand, SchedCandidate &Cand);
+  static SchedCandidate *
+  tryPressure(const PressureChange &TryP, const PressureChange &CandP,
+              SchedCandidate &TryCand, SchedCandidate &Cand,
+              const TargetRegisterInfo *TRI, const MachineFunction &MF);
+  static int biasPhysReg(const SUnit *SU, bool isTop);
+
 private:
   bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone,
                            bool ComputeRemLatency, unsigned &RemLatency) const;
 };
 
-// Utility functions used by heuristics in tryCandidate().
-bool tryLess(int TryVal, int CandVal,
-             GenericSchedulerBase::SchedCandidate &TryCand,
-             GenericSchedulerBase::SchedCandidate &Cand,
-             GenericSchedulerBase::CandReason Reason);
-bool tryGreater(int TryVal, int CandVal,
-                GenericSchedulerBase::SchedCandidate &TryCand,
-                GenericSchedulerBase::SchedCandidate &Cand,
-                GenericSchedulerBase::CandReason Reason);
-bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
-                GenericSchedulerBase::SchedCandidate &Cand,
-                SchedBoundary &Zone);
-bool tryPressure(const PressureChange &TryP,
-                 const PressureChange &CandP,
-                 GenericSchedulerBase::SchedCandidate &TryCand,
-                 GenericSchedulerBase::SchedCandidate &Cand,
-                 GenericSchedulerBase::CandReason Reason,
-                 const TargetRegisterInfo *TRI,
-                 const MachineFunction &MF);
-unsigned getWeakLeft(const SUnit *SU, bool isTop);
-int biasPhysReg(const SUnit *SU, bool isTop);
-
 /// GenericScheduler shrinks the unscheduled zone using heuristics to balance
 /// the schedule.
 class GenericScheduler : public GenericSchedulerBase {
 public:
-  GenericScheduler(const MachineSchedContext *C):
-    GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
-    Bot(SchedBoundary::BotQID, "BotQ") {}
+  GenericScheduler(const MachineSchedContext *C)
+      : GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
+        Bot(SchedBoundary::BotQID, "BotQ"), RegExcess(DAG, TRI),
+        RegCritMax(DAG, TRI), RegMax(DAG, TRI) {}
 
   void initPolicy(MachineBasicBlock::iterator Begin,
                   MachineBasicBlock::iterator End,
                   unsigned NumRegionInstrs) override;
 
   void dumpPolicy() const override;
 
   bool shouldTrackPressure() const override {
if (SU->isScheduled)
       return;
 
     Bot.releaseNode(SU, SU->BotReadyCycle, false);
     BotCand.SU = nullptr;
   }
 
   void registerRoots() override;
 
+  // Avoid exceeding the target's limit.
+  struct RegExcessHeuristic : public SchedHeuristic {
+    ScheduleDAGMILive *&DAG;
+    const TargetRegisterInfo *&TRI;
+    RegExcessHeuristic(ScheduleDAGMILive *&DAG, const TargetRegisterInfo *&TRI)
+        : SchedHeuristic("REG-EXCESS"), DAG(DAG), TRI(TRI) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      return tryPressure(TryCand.RPDelta.Excess, Cand.RPDelta.Excess, TryCand,
+                         Cand, TRI, DAG->MF);
+    }
+  };
+
+  // Avoid increasing the max critical pressure in the scheduled region.
+  struct RegCritMaxHeuristic : public SchedHeuristic {
+    ScheduleDAGMILive *&DAG;
+    const TargetRegisterInfo *&TRI;
+    RegCritMaxHeuristic(ScheduleDAGMILive *&DAG, const TargetRegisterInfo *&TRI)
+        : SchedHeuristic("REG-CRIT"), DAG(DAG), TRI(TRI) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      return tryPressure(TryCand.RPDelta.CriticalMax, Cand.RPDelta.CriticalMax,
+                         TryCand, Cand, TRI, DAG->MF);
+    }
+  };
+
+  // Avoid increasing the max pressure of the entire region.
+  struct RegMaxHeuristic : public SchedHeuristic {
+    ScheduleDAGMILive *&DAG;
+    const TargetRegisterInfo *&TRI;
+    RegMaxHeuristic(ScheduleDAGMILive *&DAG, const TargetRegisterInfo *&TRI)
+        : SchedHeuristic("REG-MAX"), DAG(DAG), TRI(TRI) {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override {
+      return tryPressure(TryCand.RPDelta.CurrentMax, Cand.RPDelta.CurrentMax,
+                         TryCand, Cand, TRI, DAG->MF);
+    }
+  };
+
 protected:
   ScheduleDAGMILive *DAG = nullptr;
 
   MachineSchedPolicy RegionPolicy;
 
   // State of the top and bottom scheduled instruction boundaries.
   SchedBoundary Top;
   SchedBoundary Bot;
 
   /// Candidate last picked from Top boundary.
   SchedCandidate TopCand;
   /// Candidate last picked from Bot boundary.
   SchedCandidate BotCand;
 
+  RegExcessHeuristic RegExcess;
+  RegCritMaxHeuristic RegCritMax;
+  RegMaxHeuristic RegMax;
+
+  void registerHeuristics() override;
   void checkAcyclicLatency();
 
   void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
                      const RegPressureTracker &RPTracker,
                      RegPressureTracker &TempTracker);
 
-  virtual void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
-                            SchedBoundary *Zone) const;
-
+#ifndef NDEBUG
+  void traceCandidate(const SchedCandidate &Cand) override;
+#endif
   SUnit *pickNodeBidirectional(bool &IsTopNode);
 
   void pickNodeFromQueue(SchedBoundary &Zone,
                          const CandPolicy &ZonePolicy,
                          const RegPressureTracker &RPTracker,
                          SchedCandidate &Candidate);
 
   void reschedulePhysReg(SUnit *SU, bool isTop);
 };
 
 /// PostGenericScheduler - Interface to the scheduling algorithm used by
 /// ScheduleDAGMI.
 ///
 /// Callbacks from ScheduleDAGMI:
 ///   initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
 class PostGenericScheduler : public GenericSchedulerBase {
 protected:
   ScheduleDAGMI *DAG = nullptr;
   SchedBoundary Top;
   SmallVector<SUnit*, 8> BotRoots;
 
+  ResourceReduceHeuristic ResReducePostRA;
+
 public:
-  PostGenericScheduler(const MachineSchedContext *C):
-    GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {}
+  PostGenericScheduler(const MachineSchedContext *C)
+      : GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
+        ResReducePostRA(DAG, SchedModel, false) {}
 
   ~PostGenericScheduler() override = default;
 
   void initPolicy(MachineBasicBlock::iterator Begin,
                   MachineBasicBlock::iterator End,
                   unsigned NumRegionInstrs) override {
     /* no configurable policy */
   }
public:
   }
 
   // Only called for roots.
   void releaseBottomNode(SUnit *SU) override {
     BotRoots.push_back(SU);
   }
 
 protected:
-  virtual void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
-
   void pickNodeFromQueue(SchedCandidate &Cand);
+  void registerHeuristics() override;
+#ifndef NDEBUG
+  void traceCandidate(const SchedCandidate &Cand) override;
+#endif
 };
 
 /// Create the standard converging machine scheduler. This will be used as the
 /// default scheduler if the target does not set a default.
 /// Adds default DAG mutations.
 ScheduleDAGMILive *createGenericSchedLive(MachineSchedContext *C);
 
 /// Create a generic scheduler with no vreg liveness or DAG mutation passes.
 ScheduleDAGMI *createGenericSchedPostRA(MachineSchedContext *C);
 
 std::unique_ptr<ScheduleDAGMutation>
 createLoadClusterDAGMutation(const TargetInstrInfo *TII,
                              const TargetRegisterInfo *TRI);
 
 std::unique_ptr<ScheduleDAGMutation>
 createStoreClusterDAGMutation(const TargetInstrInfo *TII,
                               const TargetRegisterInfo *TRI);
 
 std::unique_ptr<ScheduleDAGMutation>
 createCopyConstrainDAGMutation(const TargetInstrInfo *TII,
                                const TargetRegisterInfo *TRI);
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_MACHINESCHEDULER_H

llvm/lib/CodeGen/MachineScheduler.cpp

static bool Compare(const MachineOperand *const &A,
                         const MachineOperand *const &B) {
       if (A->getType() != B->getType())
         return A->getType() < B->getType();
       if (A->isReg())
         return A->getReg() < B->getReg();
       if (A->isFI()) {
         const MachineFunction &MF = *A->getParent()->getParent()->getParent();
         const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
         bool StackGrowsDown = TFI.getStackGrowthDirection() ==
                               TargetFrameLowering::StackGrowsDown;
         return StackGrowsDown ? A->getIndex() > B->getIndex()
                               : A->getIndex() < B->getIndex();
       }
 
       llvm_unreachable("MemOpClusterMutation only supports register or frame "
                        "index bases.");
     }
for (TargetSchedModel::ProcResIter
          PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
     if (PI->ProcResourceIdx == Policy.ReduceResIdx)
       ResDelta.CritResources += PI->Cycles;
     if (PI->ProcResourceIdx == Policy.DemandResIdx)
       ResDelta.DemandedResources += PI->Cycles;
   }
 }
 
+void GenericSchedulerBase::initialize(ScheduleDAGMI *Dag) {
+  DAG = Dag;
+  // Register all the heuristics.
+  Heuristics.clear();
+  registerHeuristics();
+  // Assign the priority for each heuristics.
+  for (unsigned i = 0; i < Heuristics.size(); ++i)
+    Heuristics[i]->Priority = i;
+}
+
+/// Apply a set of heuristics 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, or nullptr
+//              if Cand is from a different zone than TryCand.
+void GenericSchedulerBase::tryCandidate(SchedCandidate &Cand,
+                                        SchedCandidate &TryCand,
+                                        SchedBoundary *Zone) const {
+  // Initialize the candidate if needed.
+  if (!Cand.isValid()) {
+    TryCand.Reason = &NodeOrder;
+    return;
+  }
+
+  for (auto Reason : Heuristics) {
+    if (SchedCandidate *SC = Reason->Try(Cand, TryCand, Zone)) {
+      assert((SC == &Cand || SC == &TryCand) &&
+             "Either Cand or TryCand is expected");
+      if (SC == &TryCand || hasHigherPriority(Reason, SC->Reason))
+        SC->Reason = Reason;
+      break;
+    }
+  }
+}
+
 /// Compute remaining latency. We need this both to determine whether the
 /// overall schedule has become latency-limited and whether the instructions
 /// outside this zone are resource or latency limited.
 ///
 /// The "dependent" latency is updated incrementally during scheduling as the
 /// max height/depth of scheduled nodes minus the cycles since it was
 /// scheduled:
 ///   DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
void GenericSchedulerBase::setPolicy(CandPolicy &Policy, bool IsPostRA,
   if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx)
     Policy.ReduceResIdx = CurrZone.getZoneCritResIdx();
 
   if (OtherResLimited)
     Policy.DemandResIdx = OtherCritIdx;
 }
 
 #ifndef NDEBUG
-const char *GenericSchedulerBase::getReasonStr(
-  GenericSchedulerBase::CandReason Reason) {
-  switch (Reason) {
-  case NoCand:         return "NOCAND    ";
-  case Only1:          return "ONLY1     ";
-  case PhysReg:        return "PHYS-REG  ";
-  case RegExcess:      return "REG-EXCESS";
-  case RegCritical:    return "REG-CRIT  ";
-  case Stall:          return "STALL     ";
-  case Cluster:        return "CLUSTER   ";
-  case Weak:           return "WEAK      ";
-  case RegMax:         return "REG-MAX   ";
-  case ResourceReduce: return "RES-REDUCE";
-  case ResourceDemand: return "RES-DEMAND";
-  case TopDepthReduce: return "TOP-DEPTH ";
-  case TopPathReduce:  return "TOP-PATH  ";
-  case BotHeightReduce:return "BOT-HEIGHT";
-  case BotPathReduce:  return "BOT-PATH  ";
-  case NextDefUse:     return "DEF-USE   ";
-  case NodeOrder:      return "ORDER     ";
-  };
-  llvm_unreachable("Unknown reason!");
-}
-
 void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {
-  PressureChange P;
   unsigned ResIdx = 0;
   unsigned Latency = 0;
-  switch (Cand.Reason) {
-  default:
-    break;
-  case RegExcess:
-    P = Cand.RPDelta.Excess;
-    break;
-  case RegCritical:
-    P = Cand.RPDelta.CriticalMax;
-    break;
-  case RegMax:
-    P = Cand.RPDelta.CurrentMax;
-    break;
-  case ResourceReduce:
+
+  if (Cand.Reason == &ResourceReduce)
     ResIdx = Cand.Policy.ReduceResIdx;
-    break;
-  case ResourceDemand:
+  else if (Cand.Reason == &ResourceDemand)
     ResIdx = Cand.Policy.DemandResIdx;
-    break;
-  case TopDepthReduce:
+  else if (Cand.Reason == &AcyLimitedTopDepthReduce ||
+           Cand.Reason == &TopDepthReduce)
     Latency = Cand.SU->getDepth();
-    break;
-  case TopPathReduce:
+  else if (Cand.Reason == &AcyLimitedTopPathReduce ||
+           Cand.Reason == &TopPathReduce)
     Latency = Cand.SU->getHeight();
-    break;
-  case BotHeightReduce:
+  else if (Cand.Reason == &AcyLimitedBotHeightReduce ||
+           Cand.Reason == &BotHeightReduce)
     Latency = Cand.SU->getHeight();
-    break;
-  case BotPathReduce:
+  else if (Cand.Reason == &AcyLimitedBotPathReduce ||
+           Cand.Reason == &BotPathReduce)
     Latency = Cand.SU->getDepth();
-    break;
-  }
-  dbgs() << "  Cand SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
-  if (P.isValid())
-    dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())
-           << ":" << P.getUnitInc() << " ";
-  else
-    dbgs() << "      ";
+
+  dbgs() << "  Cand SU(" << Cand.SU->NodeNum << ") "
+         << (Cand.Reason ? Cand.Reason->Name : "NOCAND");
+
   if (ResIdx)
     dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";
   else
     dbgs() << "         ";
   if (Latency)
     dbgs() << " " << Latency << " cycles ";
   else
     dbgs() << "          ";
   dbgs() << '\n';
 }
 #endif
 
-namespace llvm {
-/// Return true if this heuristic determines order.
-bool tryLess(int TryVal, int CandVal,
-             GenericSchedulerBase::SchedCandidate &TryCand,
-             GenericSchedulerBase::SchedCandidate &Cand,
-             GenericSchedulerBase::CandReason Reason) {
-  if (TryVal < CandVal) {
-    TryCand.Reason = Reason;
-    return true;
-  }
-  if (TryVal > CandVal) {
-    if (Cand.Reason > Reason)
-      Cand.Reason = Reason;
-    return true;
-  }
-  return false;
-}
-
-bool tryGreater(int TryVal, int CandVal,
-                GenericSchedulerBase::SchedCandidate &TryCand,
-                GenericSchedulerBase::SchedCandidate &Cand,
-                GenericSchedulerBase::CandReason Reason) {
-  if (TryVal > CandVal) {
-    TryCand.Reason = Reason;
-    return true;
-  }
-  if (TryVal < CandVal) {
-    if (Cand.Reason > Reason)
-      Cand.Reason = Reason;
-    return true;
-  }
-  return false;
-}
-
-bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
-                GenericSchedulerBase::SchedCandidate &Cand,
-                SchedBoundary &Zone) {
-  if (Zone.isTop()) {
-    // Prefer the candidate with the lesser depth, but only if one of them has
-    // depth greater than the total latency scheduled so far, otherwise either
-    // of them could be scheduled now with no stall.
-    if (std::max(TryCand.SU->getDepth(), 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 {
-    // Prefer the candidate with the lesser height, but only if one of them has
-    // height greater than the total latency scheduled so far, otherwise either
-    // of them could be scheduled now with no stall.
-    if (std::max(TryCand.SU->getHeight(), 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;
+/// Return the candidate if this heuristic determines order.
+GenericSchedulerBase::SchedCandidate *
+GenericSchedulerBase::tryLess(int TryVal, int CandVal, SchedCandidate &TryCand,
+                              SchedCandidate &Cand) {
+  if (TryVal < CandVal)
+    return &TryCand;
+  if (TryVal > CandVal)
+    return &Cand;
+  return nullptr;
 }
-} // end namespace llvm
 
-static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop) {
+static void tracePick(const GenericSchedulerBase::SchedHeuristic *Reason,
+                      bool IsTop) {
   LLVM_DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")
-                    << GenericSchedulerBase::getReasonStr(Reason) << '\n');
+                    << (Reason ? Reason->Name : "NOCAND") << '\n');
 }
 
 static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand) {
   tracePick(Cand.Reason, Cand.AtTop);
 }
 
 void GenericScheduler::initialize(ScheduleDAGMI *dag) {
   assert(dag->hasVRegLiveness() &&
          "(PreRA)GenericScheduler needs vreg liveness");
   DAG = static_cast<ScheduleDAGMILive*>(dag);
+
   SchedModel = DAG->getSchedModel();
   TRI = DAG->TRI;
 
   if (RegionPolicy.ComputeDFSResult)
     DAG->computeDFSResult();
 
   Rem.init(DAG, SchedModel);
   Top.init(DAG, SchedModel, &Rem);
void GenericScheduler::initialize(ScheduleDAGMI *dag) {
   }
   if (!Bot.HazardRec) {
     Bot.HazardRec =
         DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
             Itin, DAG);
   }
   TopCand.SU = nullptr;
   BotCand.SU = nullptr;
+
+  GenericSchedulerBase::initialize(dag);
 }
 
 /// Initialize the per-region scheduling policy.
 void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
                                   MachineBasicBlock::iterator End,
                                   unsigned NumRegionInstrs) {
   const MachineFunction &MF = *Begin->getMF();
   const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
void GenericScheduler::registerRoots() {
   }
 
   if (EnableCyclicPath && SchedModel->getMicroOpBufferSize() > 0) {
     Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();
     checkAcyclicLatency();
   }
 }
 
-namespace llvm {
-bool tryPressure(const PressureChange &TryP,
-                 const PressureChange &CandP,
-                 GenericSchedulerBase::SchedCandidate &TryCand,
-                 GenericSchedulerBase::SchedCandidate &Cand,
-                 GenericSchedulerBase::CandReason Reason,
-                 const TargetRegisterInfo *TRI,
-                 const MachineFunction &MF) {
+GenericSchedulerBase::SchedCandidate *GenericSchedulerBase::tryPressure(
+    const PressureChange &TryP, const PressureChange &CandP,
+    SchedCandidate &TryCand, SchedCandidate &Cand,
+    const TargetRegisterInfo *TRI, const MachineFunction &MF) {
   // If one candidate decreases and the other increases, go with it.
   // Invalid candidates have UnitInc==0.
-  if (tryGreater(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, TryCand, Cand,
-                 Reason)) {
-    return true;
-  }
+  if (auto Result =
+          tryLess(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, Cand, TryCand))
+    return Result;
+
   // Do not compare the magnitude of pressure changes between top and bottom
   // boundary.
   if (Cand.AtTop != TryCand.AtTop)
-    return false;
+    return nullptr;
 
   // If both candidates affect the same set in the same boundary, go with the
   // smallest increase.
   unsigned TryPSet = TryP.getPSetOrMax();
   unsigned CandPSet = CandP.getPSetOrMax();
   if (TryPSet == CandPSet) {
-    return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand,
-                   Reason);
+    return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand);
   }
 
   int TryRank = TryP.isValid() ? TRI->getRegPressureSetScore(MF, TryPSet) :
                                  std::numeric_limits<int>::max();
 
   int CandRank = CandP.isValid() ? TRI->getRegPressureSetScore(MF, CandPSet) :
                                    std::numeric_limits<int>::max();
 
   // If the candidates are decreasing pressure, reverse priority.
   if (TryP.getUnitInc() < 0)
     std::swap(TryRank, CandRank);
-  return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
+  return tryLess(TryRank, CandRank, Cand, TryCand);
 }
 
+namespace llvm {
 unsigned getWeakLeft(const SUnit *SU, bool isTop) {
   return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;
 }
+} // end namespace llvm
 
 /// 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.
-int biasPhysReg(const SUnit *SU, bool isTop) {
+int GenericSchedulerBase::biasPhysReg(const SUnit *SU, bool isTop) {
   const MachineInstr *MI = SU->getInstr();
 
   if (MI->isCopy()) {
     unsigned ScheduledOper = isTop ? 1 : 0;
     unsigned UnscheduledOper = isTop ? 0 : 1;
     // If we have already scheduled the physreg produce/consumer, immediately
     // schedule the copy.
     if (Register::isPhysicalRegister(MI->getOperand(ScheduledOper).getReg()))
if (MI->isMoveImmediate()) {
     }
 
     if (DoBias)
       return isTop ? -1 : 1;
   }
 
   return 0;
 }
-} // end namespace llvm
+
+void GenericScheduler::registerHeuristics() {
+  registerHeuristic(PhysReg);
+
+  if (DAG->isTrackingPressure()) {
+    registerHeuristic(RegExcess);
+    registerHeuristic(RegCritMax);
+  }
+
+  registerHeuristic(AcyLimitedTopDepthReduce);
+  registerHeuristic(AcyLimitedTopPathReduce);
+  registerHeuristic(AcyLimitedBotHeightReduce);
+  registerHeuristic(AcyLimitedBotPathReduce);
+  registerHeuristic(Stall);
+  registerHeuristic(Cluster);
+  registerHeuristic(Weak);
+
+  if (DAG->isTrackingPressure())
+    registerHeuristic(RegMax);
+
+  registerHeuristic(ResourceReduce);
+  registerHeuristic(ResourceDemand);
+
+  if (!RegionPolicy.DisableLatencyHeuristic) {
+    registerHeuristic(TopDepthReduce);
+    registerHeuristic(TopPathReduce);
+    registerHeuristic(BotHeightReduce);
+    registerHeuristic(BotPathReduce);
+  }
+
+  registerHeuristic(NodeOrder);
+}
+
+#ifndef NDEBUG
+void GenericScheduler::traceCandidate(const SchedCandidate &Cand) {
+  PressureChange P;
+  if (Cand.Reason == &RegExcess)
+    P = Cand.RPDelta.Excess;
+  else if (Cand.Reason == &RegCritMax)
+    P = Cand.RPDelta.CriticalMax;
+  else if (Cand.Reason == &RegMax)
+    P = Cand.RPDelta.CurrentMax;
+
+  if (P.isValid()) {
+    dbgs() << "  Cand SU(" << Cand.SU->NodeNum << ") " << Cand.Reason->Name;
+    dbgs() << " " << TRI->getRegPressureSetName(P.getPSet()) << ":"
+           << P.getUnitInc() << " ";
+    dbgs() << '\n';
+  } else
+    GenericSchedulerBase::traceCandidate(Cand);
+}
+#endif
 
 void GenericScheduler::initCandidate(SchedCandidate &Cand, SUnit *SU,
                                      bool AtTop,
                                      const RegPressureTracker &RPTracker,
                                      RegPressureTracker &TempTracker) {
   Cand.SU = SU;
   Cand.AtTop = AtTop;
   if (DAG->isTrackingPressure()) {
if (DAG->isTrackingPressure()) {
     }
   }
   LLVM_DEBUG(if (Cand.RPDelta.Excess.isValid()) dbgs()
              << "  Try  SU(" << Cand.SU->NodeNum << ") "
              << TRI->getRegPressureSetName(Cand.RPDelta.Excess.getPSet()) << ":"
              << Cand.RPDelta.Excess.getUnitInc() << "\n");
 }
 
-/// Apply a set of heuristics 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, or nullptr
-//              if Cand is from a different zone than TryCand.
-void GenericScheduler::tryCandidate(SchedCandidate &Cand,
-                                    SchedCandidate &TryCand,
-                                    SchedBoundary *Zone) const {
-  // Initialize the candidate if needed.
-  if (!Cand.isValid()) {
-    TryCand.Reason = NodeOrder;
-    return;
-  }
-
-  // Bias PhysReg Defs and copies to their uses and defined respectively.
-  if (tryGreater(biasPhysReg(TryCand.SU, TryCand.AtTop),
-                 biasPhysReg(Cand.SU, Cand.AtTop), TryCand, Cand, PhysReg))
-    return;
-
-  // Avoid exceeding the target's limit.
-  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess,
-                                               Cand.RPDelta.Excess,
-                                               TryCand, Cand, RegExcess, TRI,
-                                               DAG->MF))
-    return;
-
-  // Avoid increasing the max critical pressure in the scheduled region.
-  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CriticalMax,
-                                               Cand.RPDelta.CriticalMax,
-                                               TryCand, Cand, RegCritical, TRI,
-                                               DAG->MF))
-    return;
-
-  // We only compare a subset of features when comparing nodes between
-  // Top and Bottom boundary. Some properties are simply incomparable, in many
-  // other instances we should only override the other boundary if something
-  // is a clear good pick on one boundary. Skip heuristics that are more
-  // "tie-breaking" in nature.
-  bool SameBoundary = Zone != nullptr;
-  if (SameBoundary) {
-    // For loops that are acyclic path limited, aggressively schedule for
-    // latency. Within an single cycle, whenever CurrMOps > 0, allow normal
-    // heuristics to take precedence.
-    if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() &&
-        tryLatency(TryCand, Cand, *Zone))
-      return;
-
-    // Prioritize instructions that read unbuffered resources by stall cycles.
-    if (tryLess(Zone->getLatencyStallCycles(TryCand.SU),
-                Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
-      return;
-  }
-
-  // Keep clustered nodes together to encourage downstream peephole
-  // optimizations which may reduce resource requirements.
-  //
-  // This is a best effort to set things up for a post-RA pass. Optimizations
-  // like generating loads of multiple registers should ideally be done within
-  // the scheduler pass by combining the loads during DAG postprocessing.
-  const SUnit *CandNextClusterSU =
-    Cand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
-  const SUnit *TryCandNextClusterSU =
-    TryCand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
-  if (tryGreater(TryCand.SU == TryCandNextClusterSU,
-                 Cand.SU == CandNextClusterSU,
-                 TryCand, Cand, Cluster))
-    return;
-
-  if (SameBoundary) {
-    // Weak edges are for clustering and other constraints.
-    if (tryLess(getWeakLeft(TryCand.SU, TryCand.AtTop),
-                getWeakLeft(Cand.SU, Cand.AtTop),
-                TryCand, Cand, Weak))
-      return;
-  }
-
-  // Avoid increasing the max pressure of the entire region.
-  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CurrentMax,
-                                               Cand.RPDelta.CurrentMax,
-                                               TryCand, Cand, RegMax, TRI,
-                                               DAG->MF))
-    return;
-
-  if (SameBoundary) {
-    // Avoid critical resource consumption and balance the schedule.
-    TryCand.initResourceDelta(DAG, SchedModel);
-    if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
-                TryCand, Cand, ResourceReduce))
-      return;
-    if (tryGreater(TryCand.ResDelta.DemandedResources,
-                   Cand.ResDelta.DemandedResources,
-                   TryCand, Cand, ResourceDemand))
-      return;
-
-    // Avoid serializing long latency dependence chains.
-    // For acyclic path limited loops, latency was already checked above.
-    if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&
-        !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, *Zone))
-      return;
-
-    // Fall through to original instruction order.
-    if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
-        || (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
-      TryCand.Reason = NodeOrder;
-    }
-  }
-}
-
 /// Pick the best candidate from the 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.
 void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
                                          const CandPolicy &ZonePolicy,
                                          const RegPressureTracker &RPTracker,
                                          SchedCandidate &Cand) {
   // getMaxPressureDelta temporarily modifies the tracker.
   RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
 
   ReadyQueue &Q = Zone.Available;
   for (SUnit *SU : Q) {
 
     SchedCandidate TryCand(ZonePolicy);
     initCandidate(TryCand, SU, Zone.isTop(), RPTracker, TempTracker);
     // Pass SchedBoundary only when comparing nodes from the same boundary.
     SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
     tryCandidate(Cand, TryCand, ZoneArg);
-    if (TryCand.Reason != NoCand) {
+    if (TryCand.Reason) {
       // Initialize resource delta if needed in case future heuristics query it.
       if (TryCand.ResDelta == SchedResourceDelta())
         TryCand.initResourceDelta(DAG, SchedModel);
       Cand.setBest(TryCand);
       LLVM_DEBUG(traceCandidate(Cand));
     }
   }
 }
 
 /// Pick the best candidate node from either the top or bottom queue.
 SUnit *GenericScheduler::pickNodeBidirectional(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 (SUnit *SU = Bot.pickOnlyChoice()) {
     IsTopNode = false;
-    tracePick(Only1, false);
+    tracePick(&Only1, false);
     return SU;
   }
   if (SUnit *SU = Top.pickOnlyChoice()) {
     IsTopNode = true;
-    tracePick(Only1, true);
+    tracePick(&Only1, true);
     return SU;
   }
   // Set the bottom-up policy based on the state of the current bottom zone and
   // the instructions outside the zone, including the top zone.
   CandPolicy BotPolicy;
   setPolicy(BotPolicy, /*IsPostRA=*/false, Bot, &Top);
   // Set the top-down policy based on the state of the current top zone and
   // the instructions outside the zone, including the bottom zone.
   CandPolicy TopPolicy;
   setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot);
 
   // See if BotCand is still valid (because we previously scheduled from Top).
   LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
   if (!BotCand.isValid() || BotCand.SU->isScheduled ||
       BotCand.Policy != BotPolicy) {
     BotCand.reset(CandPolicy());
     pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);
-    assert(BotCand.Reason != NoCand && "failed to find the first candidate");
+    assert(BotCand.Reason && "failed to find the first candidate");
   } else {
     LLVM_DEBUG(traceCandidate(BotCand));
 #ifndef NDEBUG
     if (VerifyScheduling) {
       SchedCandidate TCand;
       TCand.reset(CandPolicy());
       pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);
       assert(TCand.SU == BotCand.SU &&
              "Last pick result should correspond to re-picking right now");
     }
 #endif
   }
 
   // Check if the top Q has a better candidate.
   LLVM_DEBUG(dbgs() << "Picking from Top:\n");
   if (!TopCand.isValid() || TopCand.SU->isScheduled ||
       TopCand.Policy != TopPolicy) {
     TopCand.reset(CandPolicy());
     pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);
-    assert(TopCand.Reason != NoCand && "failed to find the first candidate");
+    assert(TopCand.Reason && "failed to find the first candidate");
   } else {
     LLVM_DEBUG(traceCandidate(TopCand));
 #ifndef NDEBUG
     if (VerifyScheduling) {
       SchedCandidate TCand;
       TCand.reset(CandPolicy());
       pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);
       assert(TCand.SU == TopCand.SU &&
            "Last pick result should correspond to re-picking right now");
     }
 #endif
   }
 
   // Pick best from BotCand and TopCand.
   assert(BotCand.isValid());
   assert(TopCand.isValid());
   SchedCandidate Cand = BotCand;
-  TopCand.Reason = NoCand;
+  TopCand.Reason = nullptr;
   tryCandidate(Cand, TopCand, nullptr);
-  if (TopCand.Reason != NoCand) {
+  if (TopCand.Reason) {
     Cand.setBest(TopCand);
     LLVM_DEBUG(traceCandidate(Cand));
   }
 
   IsTopNode = Cand.AtTop;
   tracePick(Cand);
   return Cand.SU;
 }
 
 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
 SUnit *GenericScheduler::pickNode(bool &IsTopNode) {
   if (DAG->top() == DAG->bottom()) {
     assert(Top.Available.empty() && Top.Pending.empty() &&
            Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
     return nullptr;
   }
   SUnit *SU;
   do {
     if (RegionPolicy.OnlyTopDown) {
       SU = Top.pickOnlyChoice();
       if (!SU) {
         CandPolicy NoPolicy;
         TopCand.reset(NoPolicy);
         pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);
-        assert(TopCand.Reason != NoCand && "failed to find a candidate");
+        assert(TopCand.Reason && "failed to find a candidate");
         tracePick(TopCand);
         SU = TopCand.SU;
       }
       IsTopNode = true;
     } else if (RegionPolicy.OnlyBottomUp) {
       SU = Bot.pickOnlyChoice();
       if (!SU) {
         CandPolicy NoPolicy;
         BotCand.reset(NoPolicy);
         pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);
-        assert(BotCand.Reason != NoCand && "failed to find a candidate");
+        assert(BotCand.Reason && "failed to find a candidate");
         tracePick(BotCand);
         SU = BotCand.SU;
       }
       IsTopNode = false;
     } else {
       SU = pickNodeBidirectional(IsTopNode);
     }
   } while (SU->isScheduled);
void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {
   // Initialize the HazardRecognizers. If itineraries don't exist, are empty,
   // or are disabled, then these HazardRecs will be disabled.
   const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
   if (!Top.HazardRec) {
     Top.HazardRec =
         DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
             Itin, DAG);
   }
+  GenericSchedulerBase::initialize(Dag);
+}
+
+void PostGenericScheduler::registerHeuristics() {
+  registerHeuristic(Stall);
+  registerHeuristic(Cluster);
+  registerHeuristic(ResReducePostRA);
+  registerHeuristic(ResourceDemand);
+  registerHeuristic(TopDepthReduce);
+  registerHeuristic(TopPathReduce);
+  registerHeuristic(BotHeightReduce);
+  registerHeuristic(BotPathReduce);
+  registerHeuristic(NodeOrder);
 }
 
+#ifndef NDEBUG
+void PostGenericScheduler::traceCandidate(const SchedCandidate &Cand) {
+  unsigned ResIdx = 0;
+  if (Cand.Reason == &ResReducePostRA) {
+    ResIdx = Cand.Policy.ReduceResIdx;
+    dbgs() << "  Cand SU(" << Cand.SU->NodeNum << ") " << Cand.Reason->Name;
+    dbgs() << "      ";
+    if (ResIdx)
+      dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";
+    else
+      dbgs() << "         ";
+    dbgs() << "          ";
+    dbgs() << '\n';
+  } else
+    GenericSchedulerBase::traceCandidate(Cand);
+}
+#endif
+
 void PostGenericScheduler::registerRoots() {
   Rem.CriticalPath = DAG->ExitSU.getDepth();
 
   // Some roots may not feed into ExitSU. Check all of them in case.
   for (const SUnit *SU : BotRoots) {
     if (SU->getDepth() > Rem.CriticalPath)
       Rem.CriticalPath = SU->getDepth();
   }
   LLVM_DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n');
   if (DumpCriticalPathLength) {
     errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n";
   }
 }
 
-/// Apply a set of heuristics to a new candidate for PostRA scheduling.
-///
-/// \param Cand provides the policy and current best candidate.
-/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
-void PostGenericScheduler::tryCandidate(SchedCandidate &Cand,
-                                        SchedCandidate &TryCand) {
-  // Initialize the candidate if needed.
-  if (!Cand.isValid()) {
-    TryCand.Reason = NodeOrder;
-    return;
-  }
-
-  // Prioritize instructions that read unbuffered resources by stall cycles.
-  if (tryLess(Top.getLatencyStallCycles(TryCand.SU),
-              Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
-    return;
-
-  // Keep clustered nodes together.
-  if (tryGreater(TryCand.SU == DAG->getNextClusterSucc(),
-                 Cand.SU == DAG->getNextClusterSucc(),
-                 TryCand, Cand, Cluster))
-    return;
-
-  // Avoid critical resource consumption and balance the schedule.
-  if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
-              TryCand, Cand, ResourceReduce))
-    return;
-  if (tryGreater(TryCand.ResDelta.DemandedResources,
-                 Cand.ResDelta.DemandedResources,
-                 TryCand, Cand, ResourceDemand))
-    return;
-
-  // Avoid serializing long latency dependence chains.
-  if (Cand.Policy.ReduceLatency && tryLatency(TryCand, Cand, Top)) {
-    return;
-  }
-
-  // Fall through to original instruction order.
-  if (TryCand.SU->NodeNum < Cand.SU->NodeNum)
-    TryCand.Reason = NodeOrder;
-}
-
 void PostGenericScheduler::pickNodeFromQueue(SchedCandidate &Cand) {
   ReadyQueue &Q = Top.Available;
   for (SUnit *SU : Q) {
     SchedCandidate TryCand(Cand.Policy);
     TryCand.SU = SU;
     TryCand.AtTop = true;
     TryCand.initResourceDelta(DAG, SchedModel);
-    tryCandidate(Cand, TryCand);
-    if (TryCand.Reason != NoCand) {
+    tryCandidate(Cand, TryCand, &Top);
+    if (TryCand.Reason) {
       Cand.setBest(TryCand);
       LLVM_DEBUG(traceCandidate(Cand));
     }
   }
 }
 
 /// Pick the next node to schedule.
 SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {
   if (DAG->top() == DAG->bottom()) {
     assert(Top.Available.empty() && Top.Pending.empty() && "ReadyQ garbage");
     return nullptr;
   }
   SUnit *SU;
   do {
     SU = Top.pickOnlyChoice();
     if (SU) {
-      tracePick(Only1, true);
+      tracePick(&Only1, true);
     } else {
       CandPolicy NoPolicy;
       SchedCandidate TopCand(NoPolicy);
       // Set the top-down policy based on the state of the current top zone and
       // the instructions outside the zone, including the bottom zone.
       setPolicy(TopCand.Policy, /*IsPostRA=*/true, Top, nullptr);
       pickNodeFromQueue(TopCand);
-      assert(TopCand.Reason != NoCand && "failed to find a candidate");
+      assert(TopCand.Reason && "failed to find a candidate");
       tracePick(TopCand);
       SU = TopCand.SU;
     }
   } while (SU->isScheduled);
 
   IsTopNode = true;
   Top.removeReady(SU);
 

llvm/lib/Target/AMDGPU/GCNSchedStrategy.cpp

void GCNMaxOccupancySchedStrategy::pickNodeFromQueue(SchedBoundary &Zone,
   for (SUnit *SU : Q) {
 
     SchedCandidate TryCand(ZonePolicy);
     initCandidate(TryCand, SU, Zone.isTop(), RPTracker, SRI,
                   SGPRPressure, VGPRPressure);
     // Pass SchedBoundary only when comparing nodes from the same boundary.
     SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
     GenericScheduler::tryCandidate(Cand, TryCand, ZoneArg);
-    if (TryCand.Reason != NoCand) {
+    if (TryCand.Reason) {
       // Initialize resource delta if needed in case future heuristics query it.
       if (TryCand.ResDelta == SchedResourceDelta())
         TryCand.initResourceDelta(Zone.DAG, SchedModel);
       Cand.setBest(TryCand);
       LLVM_DEBUG(traceCandidate(Cand));
     }
   }
 }
SUnit *GCNMaxOccupancySchedStrategy::pickNodeBidirectional(bool &IsTopNode) {
   setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot);
 
   // See if BotCand is still valid (because we previously scheduled from Top).
   LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
   if (!BotCand.isValid() || BotCand.SU->isScheduled ||
       BotCand.Policy != BotPolicy) {
     BotCand.reset(CandPolicy());
     pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);
-    assert(BotCand.Reason != NoCand && "failed to find the first candidate");
+    assert(BotCand.Reason && "failed to find the first candidate");
   } else {
     LLVM_DEBUG(traceCandidate(BotCand));
 #ifndef NDEBUG
     if (VerifyScheduling) {
       SchedCandidate TCand;
       TCand.reset(CandPolicy());
       pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);
       assert(TCand.SU == BotCand.SU &&
              "Last pick result should correspond to re-picking right now");
     }
 #endif
   }
 
   // Check if the top Q has a better candidate.
   LLVM_DEBUG(dbgs() << "Picking from Top:\n");
   if (!TopCand.isValid() || TopCand.SU->isScheduled ||
       TopCand.Policy != TopPolicy) {
     TopCand.reset(CandPolicy());
     pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);
-    assert(TopCand.Reason != NoCand && "failed to find the first candidate");
+    assert(TopCand.Reason && "failed to find the first candidate");
   } else {
     LLVM_DEBUG(traceCandidate(TopCand));
 #ifndef NDEBUG
     if (VerifyScheduling) {
       SchedCandidate TCand;
       TCand.reset(CandPolicy());
       pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);
       assert(TCand.SU == TopCand.SU &&
            "Last pick result should correspond to re-picking right now");
     }
 #endif
   }
 
   // Pick best from BotCand and TopCand.
   LLVM_DEBUG(dbgs() << "Top Cand: "; traceCandidate(TopCand);
              dbgs() << "Bot Cand: "; traceCandidate(BotCand););
   SchedCandidate Cand = BotCand;
-  TopCand.Reason = NoCand;
+  TopCand.Reason = nullptr;
   GenericScheduler::tryCandidate(Cand, TopCand, nullptr);
-  if (TopCand.Reason != NoCand) {
+  if (TopCand.Reason) {
     Cand.setBest(TopCand);
   }
   LLVM_DEBUG(dbgs() << "Picking: "; traceCandidate(Cand););
 
   IsTopNode = Cand.AtTop;
   return Cand.SU;
 }
 
 // This function is mostly cut and pasted from
 // GenericScheduler::pickNode()
 SUnit *GCNMaxOccupancySchedStrategy::pickNode(bool &IsTopNode) {
   if (DAG->top() == DAG->bottom()) {
     assert(Top.Available.empty() && Top.Pending.empty() &&
            Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
     return nullptr;
   }
   SUnit *SU;
   do {
     if (RegionPolicy.OnlyTopDown) {
       SU = Top.pickOnlyChoice();
       if (!SU) {
         CandPolicy NoPolicy;
         TopCand.reset(NoPolicy);
         pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);
-        assert(TopCand.Reason != NoCand && "failed to find a candidate");
+        assert(TopCand.Reason && "failed to find a candidate");
         SU = TopCand.SU;
       }
       IsTopNode = true;
     } else if (RegionPolicy.OnlyBottomUp) {
       SU = Bot.pickOnlyChoice();
       if (!SU) {
         CandPolicy NoPolicy;
         BotCand.reset(NoPolicy);
         pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);
-        assert(BotCand.Reason != NoCand && "failed to find a candidate");
+        assert(BotCand.Reason && "failed to find a candidate");
         SU = BotCand.SU;
       }
       IsTopNode = false;
     } else {
       SU = pickNodeBidirectional(IsTopNode);
     }
   } while (SU->isScheduled);
 

llvm/lib/Target/PowerPC/PPCMachineScheduler.h

 
 #include "llvm/CodeGen/MachineScheduler.h"
 
 namespace llvm {
 
 /// A MachineSchedStrategy implementation for PowerPC pre RA scheduling.
 class PPCPreRASchedStrategy : public GenericScheduler {
 public:
-  PPCPreRASchedStrategy(const MachineSchedContext *C) :
-    GenericScheduler(C) {}
+  PPCPreRASchedStrategy(const MachineSchedContext *C) : GenericScheduler(C) {}
+
 protected:
-  void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
-                    SchedBoundary *Zone) const override;
-private:
-  bool biasAddiLoadCandidate(SchedCandidate &Cand,
-                             SchedCandidate &TryCand,
-                             SchedBoundary &Zone) const;
+  // There are some benefits to schedule the ADDI before the load to hide the
+  // latency, as RA may create a true dependency between the load and addi.
+  struct BiasAddiLoadHeuristic : public SchedHeuristic {
+    BiasAddiLoadHeuristic() : SchedHeuristic("ADDI-LOAD") {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override;
+  };
+  BiasAddiLoadHeuristic BiasAddiLoad;
+
+  void registerHeuristics() override;
 };
 
 /// A MachineSchedStrategy implementation for PowerPC post RA scheduling.
 class PPCPostRASchedStrategy : public PostGenericScheduler {
 public:
-  PPCPostRASchedStrategy(const MachineSchedContext *C) :
-    PostGenericScheduler(C) {}
+  PPCPostRASchedStrategy(const MachineSchedContext *C)
+      : PostGenericScheduler(C) {}
 
 protected:
+  // There are some benefits to schedule the ADDI as early as possible post ra
+  // to avoid stalled by vector instructions which take up all the hw units.
+  // And ADDI is usually used to post inc the loop indvar, which matters the
+  // performance.
+  struct BiasAddiHeuristic : public SchedHeuristic {
+    BiasAddiHeuristic() : SchedHeuristic("BIAS-ADDI") {}
+    SchedCandidate *Try(SchedCandidate &Cand, SchedCandidate &TryCand,
+                        SchedBoundary *Zone) override;
+  };
+  BiasAddiHeuristic BiasAddi;
+
   void initialize(ScheduleDAGMI *Dag) override;
   SUnit *pickNode(bool &IsTopNode) override;
   void enterMBB(MachineBasicBlock *MBB) override;
   void leaveMBB() override;
-
-  void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand) override;
-  bool biasAddiCandidate(SchedCandidate &Cand, SchedCandidate &TryCand) const;
+  void registerHeuristics() override;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_POWERPC_POWERPCMACHINESCHEDULER_H

llvm/lib/Target/PowerPC/PPCMachineScheduler.cpp

EnableAddiHeuristic("ppc-postra-bias-addi",
                                  "as possible post ra"),
                         cl::Hidden, cl::init(true));
 
 static bool isADDIInstr(const GenericScheduler::SchedCandidate &Cand) {
   return Cand.SU->getInstr()->getOpcode() == PPC::ADDI ||
          Cand.SU->getInstr()->getOpcode() == PPC::ADDI8;
 }
 
-static void pickTryCand(GenericScheduler::SchedCandidate &Cand,
-                        GenericScheduler::SchedCandidate &TryCand) {
-  // Update the reason if we have already selected the TryCand.
-  if (TryCand.Reason != GenericScheduler::NoCand) {
-    if (TryCand.Reason > GenericScheduler::Stall)
-      TryCand.Reason = GenericScheduler::Stall;
-  } else {
-    // TryCand is not selected by heuristic and Cand is selected. If it is
-    // NodeOrder, we can still select the TryCand.
-    if (Cand.Reason == GenericScheduler::NoCand ||
-        Cand.Reason == GenericScheduler::NodeOrder)
-      TryCand.Reason = GenericScheduler::Stall;
-  }
-}
-
-static void pickCand(GenericScheduler::SchedCandidate &Cand,
-                     GenericScheduler::SchedCandidate &TryCand) {
-  if (TryCand.Reason == GenericScheduler::NoCand) {
-    // TryCand is not selected by heuristic. Update the reason for Cand.
-    if (Cand.Reason > GenericScheduler::Stall)
-      Cand.Reason = GenericScheduler::Stall;
-  } else if (TryCand.Reason == GenericScheduler::NodeOrder) {
-    // TryCand is selected but it is because of the NodeOrder heuristic. We can
-    // still select it as Cand.
-    TryCand.Reason = GenericScheduler::NoCand;
-    Cand.Reason = GenericScheduler::Stall;
-  }
-}
-
-bool PPCPreRASchedStrategy::biasAddiLoadCandidate(SchedCandidate &Cand,
+GenericScheduler::SchedCandidate *
+PPCPreRASchedStrategy::BiasAddiLoadHeuristic::Try(SchedCandidate &Cand,
                                                   SchedCandidate &TryCand,
-                                                  SchedBoundary &Zone) const {
-  if (DisableAddiLoadHeuristic)
-    return false;
-
-  SchedCandidate &FirstCand = Zone.isTop() ? TryCand : Cand;
-  SchedCandidate &SecondCand = Zone.isTop() ? Cand : TryCand;
-  if (isADDIInstr(FirstCand) && SecondCand.SU->getInstr()->mayLoad()) {
-    pickTryCand(Cand, TryCand);
-    return true;
-  }
-  if (FirstCand.SU->getInstr()->mayLoad() && isADDIInstr(SecondCand)) {
-    pickCand(Cand, TryCand);
-    return true;
-  }
-
-  return false;
+                                                  SchedBoundary *Zone) {
+  if (!Zone)
+    return nullptr;
+  SchedCandidate &FirstCand = Zone->isTop() ? TryCand : Cand;
+  SchedCandidate &SecondCand = Zone->isTop() ? Cand : TryCand;
+  if (isADDIInstr(FirstCand) && SecondCand.SU->getInstr()->mayLoad())
+    return &TryCand;
+  if (FirstCand.SU->getInstr()->mayLoad() && isADDIInstr(SecondCand))
+    return &Cand;
+  return nullptr;
+}
+
+void PPCPreRASchedStrategy::registerHeuristics() {
+  GenericScheduler::registerHeuristics();
+  if (!DisableAddiLoadHeuristic)
+    registerHeuristic(BiasAddiLoad, &NodeOrder);
 }
 
-void PPCPreRASchedStrategy::tryCandidate(SchedCandidate &Cand,
+GenericScheduler::SchedCandidate *
+PPCPostRASchedStrategy::BiasAddiHeuristic::Try(SchedCandidate &Cand,
                                                SchedCandidate &TryCand,
-                                         SchedBoundary *Zone) const {
-  GenericScheduler::tryCandidate(Cand, TryCand, Zone);
-
-  if (!Cand.isValid() || !Zone)
-    return;
-
-  // There are some benefits to schedule the ADDI before the load to hide the
-  // latency, as RA may create a true dependency between the load and addi.
-  if (biasAddiLoadCandidate(Cand, TryCand, *Zone))
-    return;
-}
-
-bool PPCPostRASchedStrategy::biasAddiCandidate(SchedCandidate &Cand,
-                                               SchedCandidate &TryCand) const {
-  if (!EnableAddiHeuristic)
-    return false;
-
-  if (isADDIInstr(TryCand) && !isADDIInstr(Cand)) {
-    pickTryCand(Cand, TryCand);
-    return true;
-  }
+                                               SchedBoundary *Zone) {
+  if (isADDIInstr(TryCand) && !isADDIInstr(Cand))
+    return &TryCand;
+  if (isADDIInstr(Cand) && !isADDIInstr(TryCand))
+    return &Cand;
+  return nullptr;
 
-  if (isADDIInstr(Cand) && !isADDIInstr(TryCand)) {
-    pickCand(Cand, TryCand);
-    return true;
-  }
-  return false;
-}
-
-void PPCPostRASchedStrategy::tryCandidate(SchedCandidate &Cand,
-                                          SchedCandidate &TryCand) {
-  PostGenericScheduler::tryCandidate(Cand, TryCand);
-
-  if (!Cand.isValid())
-    return;
-
-  // There are some benefits to schedule the ADDI as early as possible post ra
-  // to avoid stalled by vector instructions which take up all the hw units.
-  // And ADDI is usually used to post inc the loop indvar, which matters the
-  // performance.
-  if (biasAddiCandidate(Cand, TryCand))
-    return;
+void PPCPostRASchedStrategy::registerHeuristics() {
+  PostGenericScheduler::registerHeuristics();
+  if (EnableAddiHeuristic)
+    registerHeuristic(BiasAddi, &NodeOrder);
 }
 
 void PPCPostRASchedStrategy::enterMBB(MachineBasicBlock *MBB) {
   // Custom PPC PostRA specific behavior here.
   PostGenericScheduler::enterMBB(MBB);
 }
 
 void PPCPostRASchedStrategy::leaveMBB() {