[NFC][Scheduler] Refactor tryCandidate to return boolean

[qiucf]

Summary

This patch changes return type of tryCandidate from void to bool. Because:

• Method in some targets already follows this convention. (SIMachineScheduler)
• This will help if some target wants to re-use generic code. (see PowerPC change part)
• This looks more intuitive - why tryLess/tryGreater returns bool while tryCandidate returns nothing?

Here all branches simply return true if they got compared. We may change this logic further: return true only if TopCand.Reason is set (not NoCand anymore), so that we can:

if (tryCandidate(Cand, TopCand, nullptr)) {
  Cand.setBest(TopCand);
  // ...
}

Any comments are welcome. Thanks.

[rampitec]

We may change this logic further: return true only if TopCand.Reason is set (not NoCand anymore)

This seems to be better. Returning true with NoCand is misleading to me.

[foad]

llvm/lib/CodeGen/MachineScheduler.cpp

3179

Update the comment to explain what the return value means. Why don't you return true when you set the reason to NodeOrder?

llvm/lib/Target/PowerPC/PPCMachineScheduler.cpp

54–56

Couldn't you do this refactoring anyway, even without changing the return type? E.g.

GenericScheduler::tryCandidate(Cand, TryCand, Zone);
if (TryCand.Reason != NodeOrder && TryCand.Reason != NoCand)
  return;

[qiucf]

Return false only if TryCand is NoCand

[rampitec]

I have no objections.

[foad]

llvm/lib/CodeGen/MachineScheduler.cpp

3191

Surely all of these "try" functions should consistently only return true when they set Reason to something useful? So all these clauses should just be:

if (trySomething(...))
  return true;

[qiucf]

llvm/lib/CodeGen/MachineScheduler.cpp

3191

I think current implementation is for saving compilation time (tryCandidate should be very hot):

• If TryCand is better than Cand, return true;
• If Cand is better than TryCand, it also returns true, since there's no need to execute comparisons below;
• Only if we don't know which is better, go next check.

/// Return true if this heuristic determines order.
bool tryLess(int, int, SchedCandidate, SchedCandidate, CandReason);

(return true if order determined vs. return true if TryCand is better)

So the proposed change looks better, but seems it'll increase compilation time.

[foad]

llvm/lib/CodeGen/MachineScheduler.cpp

3191

Thanks for explaining. My suggestion wouldn't just increase compilation time, it would be incorrect, because if this call to tryGreater decided that Cand is better than tryCand, we would ignore that and allow a later (lower priority) heuristic to make the decision instead.

So I think your patch is OK but I still find these APIs confusing. Maybe as a future change, tryLess and tryGreater could return -1, 0 or 1 like operator<=> does.

[qiucf]

llvm/lib/CodeGen/MachineScheduler.cpp

3191

Yes. Maybe like:

enum TryResult {
  CandBetter = -1,
  Equal = 0,
  TryCandBetter = 1,
};

TryResult tryLess(...) {}

So we can write like this:

TryResult tryCandidate(...) {
  if (auto result = tryLess(...))
    return result;
  // ...
}

if (tryCandidate(...) == TryCandBetter) {
  // ...
}

llvm/include/llvm/CodeGen/MachineScheduler.h

   SchedCandidate BotCand;
 
   void checkAcyclicLatency();
 
   void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
                      const RegPressureTracker &RPTracker,
                      RegPressureTracker &TempTracker);
 
-  virtual void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
+  virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
                             SchedBoundary *Zone) const;
 
   SUnit *pickNodeBidirectional(bool &IsTopNode);
 
   void pickNodeFromQueue(SchedBoundary &Zone,
                          const CandPolicy &ZonePolicy,
                          const RegPressureTracker &RPTracker,
                          SchedCandidate &Candidate);

   }
 
   // Only called for roots.
   void releaseBottomNode(SUnit *SU) override {
     BotRoots.push_back(SU);
   }
 
 protected:
-  virtual void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
+  virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
 
   void pickNodeFromQueue(SchedCandidate &Cand);
 };
 
 /// 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);

llvm/lib/CodeGen/MachineScheduler.cpp

 /// 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,
+bool GenericScheduler::tryCandidate(SchedCandidate &Cand,
                                     SchedCandidate &TryCand,
                                     SchedBoundary *Zone) const {
   // Initialize the candidate if needed.
   if (!Cand.isValid()) {
     TryCand.Reason = NodeOrder;
-    return;
+    return true;
   }
 
   // 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;
+    return true;
 
   // Avoid exceeding the target's limit.
   if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess,
                                                Cand.RPDelta.Excess,
                                                TryCand, Cand, RegExcess, TRI,
                                                DAG->MF))
-    return;
+    return true;
 
   // 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;
+    return true;
 
   // 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;
+      return true;
 
     // Prioritize instructions that read unbuffered resources by stall cycles.
     if (tryLess(Zone->getLatencyStallCycles(TryCand.SU),
                 Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
-      return;
+      return true;
   }
 
   // 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;
+    return true;
 
   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;
+      return true;
   }
 
   // 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;
+    return true;
 
   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;
+      return true;
     if (tryGreater(TryCand.ResDelta.DemandedResources,
                    Cand.ResDelta.DemandedResources,
                    TryCand, Cand, ResourceDemand))
-      return;
+      return true;
 
     // 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;
+      return true;
 
     // 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;
     }
   }
+
+  return false;
 }
 
 /// 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,

     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,
+bool PostGenericScheduler::tryCandidate(SchedCandidate &Cand,
                                         SchedCandidate &TryCand) {
   // Initialize the candidate if needed.
   if (!Cand.isValid()) {
     TryCand.Reason = NodeOrder;
-    return;
+    return true;
   }
 
   // Prioritize instructions that read unbuffered resources by stall cycles.
   if (tryLess(Top.getLatencyStallCycles(TryCand.SU),
               Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
-    return;
+    return true;
 
   // Keep clustered nodes together.
   if (tryGreater(TryCand.SU == DAG->getNextClusterSucc(),
                  Cand.SU == DAG->getNextClusterSucc(),
                  TryCand, Cand, Cluster))
-    return;
+    return true;
 
   // Avoid critical resource consumption and balance the schedule.
   if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
               TryCand, Cand, ResourceReduce))
-    return;
+    return true;
   if (tryGreater(TryCand.ResDelta.DemandedResources,
                  Cand.ResDelta.DemandedResources,
                  TryCand, Cand, ResourceDemand))
-    return;
+    return true;
 
   // Avoid serializing long latency dependence chains.
   if (Cand.Policy.ReduceLatency && tryLatency(TryCand, Cand, Top)) {
-    return;
+    return true;
   }
 
   // Fall through to original instruction order.
   if (TryCand.SU->NodeNum < Cand.SU->NodeNum)
     TryCand.Reason = NodeOrder;
+
+  return false;
 }
 
 void PostGenericScheduler::pickNodeFromQueue(SchedCandidate &Cand) {
   ReadyQueue &Q = Top.Available;
   for (SUnit *SU : Q) {
     SchedCandidate TryCand(Cand.Policy);
     TryCand.SU = SU;
     TryCand.AtTop = true;

llvm/lib/Target/PowerPC/PPCMachineScheduler.h

 namespace llvm {
 
 /// A MachineSchedStrategy implementation for PowerPC pre RA scheduling.
 class PPCPreRASchedStrategy : public GenericScheduler {
 public:
   PPCPreRASchedStrategy(const MachineSchedContext *C) :
     GenericScheduler(C) {}
 protected:
-  void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
+  bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
                     SchedBoundary *Zone) const override;
+
 private:
   bool biasAddiLoadCandidate(SchedCandidate &Cand,
                              SchedCandidate &TryCand,
                              SchedBoundary &Zone) const;
 };
 
 /// A MachineSchedStrategy implementation for PowerPC post RA scheduling.
 class PPCPostRASchedStrategy : public PostGenericScheduler {
 public:
   PPCPostRASchedStrategy(const MachineSchedContext *C) :
     PostGenericScheduler(C) {}
 
 protected:
   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 tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand) override;
   bool biasAddiCandidate(SchedCandidate &Cand, SchedCandidate &TryCand) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_POWERPC_POWERPCMACHINESCHEDULER_H

llvm/lib/Target/PowerPC/PPCMachineScheduler.cpp

bool PPCPreRASchedStrategy::biasAddiLoadCandidate(SchedCandidate &Cand,
   if (FirstCand.SU->getInstr()->mayLoad() && isADDIInstr(SecondCand)) {
     TryCand.Reason = NoCand;
     return true;
   }
 
   return false;
 }
 
-void PPCPreRASchedStrategy::tryCandidate(SchedCandidate &Cand,
+bool PPCPreRASchedStrategy::tryCandidate(SchedCandidate &Cand,
                                          SchedCandidate &TryCand,
                                          SchedBoundary *Zone) const {
-  // From GenericScheduler::tryCandidate
-
-  // 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;
-    }
-  }
-
-  // GenericScheduler::tryCandidate end
-
   // Add powerpc specific heuristic only when TryCand isn't selected or
   // selected as node order.
-  if (TryCand.Reason != NodeOrder && TryCand.Reason != NoCand)
-    return;
+  if (GenericScheduler::tryCandidate(Cand, TryCand, Zone) ||
+      (TryCand.Reason != NodeOrder && TryCand.Reason != NoCand))
+    return true;
 
   // 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 (SameBoundary) {
-    if (biasAddiLoadCandidate(Cand, TryCand, *Zone))
-      return;
-  }
+  if (Zone != nullptr && biasAddiLoadCandidate(Cand, TryCand, *Zone))
+    return true;
+
+  return false;
 }
 
 bool PPCPostRASchedStrategy::biasAddiCandidate(SchedCandidate &Cand,
                                                SchedCandidate &TryCand) const {
   if (!EnableAddiHeuristic)
     return false;
 
   if (isADDIInstr(TryCand) && !isADDIInstr(Cand)) {
     TryCand.Reason = Stall;
     return true;
   }
   return false;
 }
 
-void PPCPostRASchedStrategy::tryCandidate(SchedCandidate &Cand,
+bool PPCPostRASchedStrategy::tryCandidate(SchedCandidate &Cand,
                                           SchedCandidate &TryCand) {
-  // From PostGenericScheduler::tryCandidate
-
-  // 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;
-
-  // PostGenericScheduler::tryCandidate end
-
   // Add powerpc post ra specific heuristic only when TryCand isn't selected or
   // selected as node order.
-  if (TryCand.Reason != NodeOrder && TryCand.Reason != NoCand)
-    return;
+  if (PostGenericScheduler::tryCandidate(Cand, TryCand) ||
+      (TryCand.Reason != NodeOrder && TryCand.Reason != NoCand))
+    return true;
 
   // 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;
+    return true;
+
+  return false;
 }
 
 void PPCPostRASchedStrategy::enterMBB(MachineBasicBlock *MBB) {
   // Custom PPC PostRA specific behavior here.
   PostGenericScheduler::enterMBB(MBB);
 }
 
 void PPCPostRASchedStrategy::leaveMBB() {