[MachineScheduler] improve reuse of 'releaseNode'method

[DoktorC]

Summary

The 'SchedBoundary::releaseNode' is merely invoked for releasing the Top/Bottom root nodes.
However, 'SchedBoundary::releasePending' uses its same logic to check if the Pending queue
has any releasable SUnit.
It is possible to slightly modify the body of the two, allowing re-use of the former ('releaseNode')
in the latter.

[fhahn]

llvm/lib/CodeGen/MachineScheduler.cpp

2111

Having the statement on the same line looks a bit unusual. Could you clang-format-diff it?

2361

The new code is is missing this condition and Available.size() may exceed ReadyListLimit I think.

[DoktorC]

As asked, the if-bodies are clang-formatted; proper formatting is applied to 'HazardDetected'
condition and 'template' specification of 'releaseNode'.

Further, a typo is fixed (From 'IsPQueue' to 'InPQueue', in MachineScheduler.cpp)

[DoktorC]

llvm/lib/CodeGen/MachineScheduler.cpp

2361

Actually, 'HazardDetected' condition in 'releaseNode' covers this case.

[DoktorC]

Ping.

[fhahn]

llvm/lib/CodeGen/MachineScheduler.cpp

2361

Right, my main concern was missing out on the early exit in the loop. I think it would still be worth keeping the early exits if Available.size() >= ReadyListLimit.

I *think* it would make sense to have the early exit at the beginning of the loop, as currently we set MinReadyCycle even if we do not add the SU to Available. IIRC, MinReadyCycle should indicate the Cycle of the soonest available instruction in Available, not pending.

[DoktorC]

Insert Available.size() >= ReadyListLimit at beginning of SchedBoundary::releasePending
loop, allowing early-exit in case of full Available queue.

Further, fix update of MinReadyCycle: it was set to SU->ReadyCycle, even if the
scheduling unit was not moved to the Available queue.
(thank @fhahn)

[fhahn]

LGTM, thanks!

llvm/lib/CodeGen/MachineScheduler.cpp

2101

nit: outermost brackets unnecessary.

2106

nit: IMO it would be slightly simpler to keep the check of Available.size() unconditional, as the runtime benefits should be very negligible

[DoktorC]

Removed useless round brackets and merged Available.size() >= ReadyListLimit with other
hazard conditions.

[DoktorC]

Fixes applied.
@fhahn, could I ask you to commit the patch? I do not have commit-access :(

[fhahn]

In D65506#1634086, @DoktorC wrote:

Further, fix update of MinReadyCycle: it was set to SU->ReadyCycle, even if the
scheduling unit was not moved to the Available queue.
(thank @fhahn)

This change causes a crash, because MinReadyCycle is not properly initialised when going through pickOnlyChoice. I think we should address that separately and I'll commit the version with setting MinReadyCycle at the original position.

[fhahn]

Even with moving setting the MinReadyCycle back, it fails the following tests. Could you take a look?

Failing Tests (3):

LLVM :: CodeGen/PowerPC/build-vector-tests.ll
LLVM :: CodeGen/PowerPC/vec_conv_fp32_to_i64_elts.ll
LLVM :: CodeGen/PowerPC/vec_conv_i16_to_fp64_elts.ll

[DoktorC]

In D65506#1639640, @fhahn wrote:

This change causes a crash, because MinReadyCycle is not properly initialised when going through pickOnlyChoice. I think we should address that separately and I'll commit the version with setting MinReadyCycle at the original position.

I beg your pardon, I ran only the unit-tests and forgot the regression ones.
Yes, I agree with you.

In D65506#1639686, @fhahn wrote:

Even with moving setting the MinReadyCycle back, it fails the following tests. Could you take a look?

Failing Tests (3):

LLVM :: CodeGen/PowerPC/build-vector-tests.ll
LLVM :: CodeGen/PowerPC/vec_conv_fp32_to_i64_elts.ll
LLVM :: CodeGen/PowerPC/vec_conv_i16_to_fp64_elts.ll

Checked. By my side, regression tests (I didn't forget them this time) and unit tests are all passed.

UPDATE
My llvm's configuration targeted only some architectures (ARM, Mips and X86). Again, sorry.
I re-configured the project to target all the supported archs, executed the tests and confirm the above
three failing.

I'll try to figure out why they're not passing.

[fhahn]

In D65506#1640190, @DoktorC wrote:

UPDATE
My llvm's configuration targeted only some architectures (ARM, Mips and X86). Again, sorry.
I re-configured the project to target all the supported archs, executed the tests and confirm the above
three failing.

I'll try to figure out why they're not passing.

Great, thanks!

BTW, it is better to respond with a new comment instead of updating existing ones, as it seems like Phabricator does not send emails for edited comments.

[DoktorC]

Hi @fhahn ,
sorry for the long silence period.

I tracked down the problem: it is how the Pending queue is explored with this patch (from the end).
Clearly, this affects which nodes move first from pending to available state; this is critical when
the Available queue reaches the maximum size.

I can re-write the queue exploration to match the pre-patch behaviour.
However, I'm wondering if it is a sign of "bad" design: shouldn't the pending queue explore the best
candidates to move in the available queue?

[DoktorC]

Up.

[DoktorC]

Up.

[DoktorC]

Up.

[fhahn]

In D65506#1719962, @DoktorC wrote:

Hi @fhahn ,
sorry for the long silence period.

I tracked down the problem: it is how the Pending queue is explored with this patch (from the end).
Clearly, this affects which nodes move first from pending to available state; this is critical when
the Available queue reaches the maximum size.

I can re-write the queue exploration to match the pre-patch behaviour.
However, I'm wondering if it is a sign of "bad" design: shouldn't the pending queue explore the best
candidates to move in the available queue?

I think it would be best keep the old behavior in this patch and potentially fix the iteration order in a follow up. Changes to the scheduler can lead to subtle regressions, so it's best to keep the changes isolated.

[DoktorC]

• Revert Pending queue exploration to pre-patch behavior (from the beginning). It was source of failure for 3 tests:

LLVM :: CodeGen/PowerPC/build-vector-tests.ll
LLVM :: CodeGen/PowerPC/vec_conv_fp32_to_i64_elts.ll
LLVM :: CodeGen/PowerPC/vec_conv_i16_to_fp64_elts.ll

• Fix missing MinReadyCycle assignment in releaseNode. It was source of MinReadyCycle uninitialized assertion error.

[DoktorC]

up!

[DoktorC]

Up.

[DoktorC]

up

[fhahn]

LGTM, thanks! And sorry for the delay! Please let me know if I should commit this change for you.

[DoktorC]

Thank you for the patience and helping me!
Still lacking of commit-access; hence, yes: you can commit for me as

• Name, Surname: Lorenzo Casalino
• Email: [e-mail]

Thank you again, and happy new year :) !

[fhahn]

In D65506#1799804, @DoktorC wrote:

Thank you for the patience and helping me!
Still lacking of commit-access; hence, yes: you can commit for me as

• Name, Surname: Lorenzo Casalino
• Email: [e-mail]

Thank you again, and happy new year :) !

Happy new year!

I've committed it with you as the author, please let me know in case you get emails about build failures.

[DoktorC]

Hi,

bad luck, got a build failure.
Link to the report: http://lab [.] llvm [.] org:8011/builders/clang-ppc64be-linux-lnt/builds/33875

Build Reason: scheduler
Build Source Stamp: [branch master] f9f78cf6ac73d9148be9b626f418bf6770e512f6
Blamelist: Lorenzo Casalino <[e-mail]>

BUILD FAILED: failed test-suite

[qiucf]

In D65506#1800633, @DoktorC wrote:

Hi,

bad luck, got a build failure.
Link to the report: http://lab [.] llvm [.] org:8011/builders/clang-ppc64be-linux-lnt/builds/33875

Build Reason: scheduler
Build Source Stamp: [branch master] f9f78cf6ac73d9148be9b626f418bf6770e512f6
Blamelist: Lorenzo Casalino <[e-mail]>

BUILD FAILED: failed test-suite

I created a patch for a build failure on GCC: https://reviews.llvm.org/D72069. Would you like to help review it? Thanks.

[steven.zhang]

In D65506#1800633, @DoktorC wrote:

Hi,

bad luck, got a build failure.
Link to the report: http://lab [.] llvm [.] org:8011/builders/clang-ppc64be-linux-lnt/builds/33875

Build Reason: scheduler
Build Source Stamp: [branch master] f9f78cf6ac73d9148be9b626f418bf6770e512f6
Blamelist: Lorenzo Casalino <[e-mail]>

BUILD FAILED: failed test-suite

I guess the failure is caused by PowerPC backend.

/opt/at12.0/lib/gcc/powerpc64le-linux-gnu/8.2.1/../../../../powerpc64le-linux-gnu/bin/ld: ../../lib/libLLVMPowerPCCodeGen.a(PPCMachineScheduler.cpp.o): in function `llvm::PostGenericScheduler::releaseTopNode(llvm::SUnit*)':
PPCMachineScheduler.cpp:(.text._ZN4llvm20PostGenericScheduler14releaseTopNodeEPNS_5SUnitE[_ZN4llvm20PostGenericScheduler14releaseTopNodeEPNS_5SUnitE]+0x2c): undefined reference to `void llvm::SchedBoundary::releaseNode<false>(llvm::SUnit*, unsigned int, unsigned int)'
/opt/at12.0/lib/gcc/powerpc64le-linux-gnu/8.2.1/../../../../powerpc64le-linux-gnu/bin/ld: ../../lib/libLLVMPowerPCCodeGen.a(PPCMachineScheduler.cpp.o): in function `llvm::GenericScheduler::releaseBottomNode(llvm::SUnit*)':
PPCMachineScheduler.cpp:(.text._ZN4llvm16GenericScheduler17releaseBottomNodeEPNS_5SUnitE[_ZN4llvm16GenericScheduler17releaseBottomNodeEPNS_5SUnitE]+0x34): undefined reference to `void llvm::SchedBoundary::releaseNode<false>(llvm::SUnit*, unsigned int, unsigned int)'
/opt/at12.0/lib/gcc/powerpc64le-linux-gnu/8.2.1/../../../../powerpc64le-linux-gnu/bin/ld: ../../lib/libLLVMPowerPCCodeGen.a(PPCMachineScheduler.cpp.o): in function `llvm::GenericScheduler::releaseTopNode(llvm::SUnit*)':
PPCMachineScheduler.cpp:(.text._ZN4llvm16GenericScheduler14releaseTopNodeEPNS_5SUnitE[_ZN4llvm16GenericScheduler14releaseTopNodeEPNS_5SUnitE]+0x34): undefined reference to `void llvm::SchedBoundary::releaseNode<false>(llvm::SUnit*, unsigned int, unsigned int)'

It is because you are splitting the template declaration and definition into header and cpp. Usually, you need to add the explicit template instantiation in the cpp. However, I am not sure if it is a good idea to use template ... BTW, it compiles clean if with clang.

[DoktorC]

It is because you are splitting the template declaration and definition into header and cpp. Usually, you need to add the explicit template instantiation in the cpp. However, I am not sure if it is a good idea to use template ... BTW, it compiles clean if with clang.

You are totally right about explicit instantiation.

Regarding the usage of a template argument, instead of a function parameter, lies in the fact that the scheduler is aware whether
a node is in the Pending queue or not, when calling releaseNode.
Indeed, such method is invoked in two occasions

• a node is scheduled: successors/predecessors are released; thus, they're known to be not in the Pending queue.
• moving nodes from pending to available state; the nodes are known to be in the Pending queue.

As a consequence, part of the operations perfomed by 'releaseNode' may be actively skipped, avoiding the
overheads of control instructions. (Yes, modern architectures are endowed with branch predictors; but I do not
think that such an argument saves us from correctly employ known invariants in the algorithms.)

[fhahn]

In D65506#1800921, @DoktorC wrote:

It is because you are splitting the template declaration and definition into header and cpp. Usually, you need to add the explicit template instantiation in the cpp. However, I am not sure if it is a good idea to use template ... BTW, it compiles clean if with clang.

You are totally right about explicit instantiation.

Regarding the usage of a template argument, instead of a function parameter, lies in the fact that the scheduler is aware whether
a node is in the Pending queue or not, when calling releaseNode.
Indeed, such method is invoked in two occasions

• a node is scheduled: successors/predecessors are released; thus, they're known to be not in the Pending queue.
• moving nodes from pending to available state; the nodes are known to be in the Pending queue.

As a consequence, part of the operations perfomed by 'releaseNode' may be actively skipped, avoiding the
overheads of control instructions. (Yes, modern architectures are endowed with branch predictors; but I do not
think that such an argument saves us from correctly employ known invariants in the algorithms.)

FWIW I think we should trust the compiler to optimize this properly and passing it as parameter should be fine. Both versions should probably compile to the same code (although I don't have time to verify that right now)

llvm/include/llvm/CodeGen/MachineScheduler.h

std::pair<unsigned, unsigned> getNextResourceCycle(unsigned PIdx,
                                                      unsigned Cycles);
 
   bool checkHazard(SUnit *SU);
 
   unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
 
   unsigned getOtherResourceCount(unsigned &OtherCritIdx);
 
-  void releaseNode(SUnit *SU, unsigned ReadyCycle);
+  template <bool InPQueue>
+  void releaseNode(SUnit *SU, unsigned ReadyCycle, unsigned Idx = 0);
 
   void bumpCycle(unsigned NextCycle);
 
   void incExecutedResources(unsigned PIdx, unsigned Count);
 
   unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle);
 
   void bumpNode(SUnit *SU);
public:
   SUnit *pickNode(bool &IsTopNode) override;
 
   void schedNode(SUnit *SU, bool IsTopNode) override;
 
   void releaseTopNode(SUnit *SU) override {
     if (SU->isScheduled)
       return;
 
-    Top.releaseNode(SU, SU->TopReadyCycle);
+    Top.releaseNode<false>(SU, SU->TopReadyCycle);
     TopCand.SU = nullptr;
   }
 
   void releaseBottomNode(SUnit *SU) override {
     if (SU->isScheduled)
       return;
 
-    Bot.releaseNode(SU, SU->BotReadyCycle);
+    Bot.releaseNode<false>(SU, SU->BotReadyCycle);
     BotCand.SU = nullptr;
   }
 
   void registerRoots() override;
 
 protected:
   ScheduleDAGMILive *DAG = nullptr;
 
void scheduleTree(unsigned SubtreeID) override {
     llvm_unreachable("PostRA scheduler does not support subtree analysis.");
   }
 
   void schedNode(SUnit *SU, bool IsTopNode) override;
 
   void releaseTopNode(SUnit *SU) override {
     if (SU->isScheduled)
       return;
-    Top.releaseNode(SU, SU->TopReadyCycle);
+    Top.releaseNode<false>(SU, SU->TopReadyCycle);
   }
 
   // Only called for roots.
   void releaseBottomNode(SUnit *SU) override {
     BotRoots.push_back(SU);
   }
 
 protected:

llvm/lib/CodeGen/MachineScheduler.cpp

if (OtherCritIdx) {
     LLVM_DEBUG(
         dbgs() << "  " << Available.getName() << " + Remain CritRes: "
                << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)
                << " " << SchedModel->getResourceName(OtherCritIdx) << "\n");
   }
   return OtherCritCount;
 }
 
-void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle) {
+template <bool InPQueue>
+void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle, unsigned Idx) {
   assert(SU->getInstr() && "Scheduled SUnit must have instr");
 
 #ifndef NDEBUG
   // ReadyCycle was been bumped up to the CurrCycle when this node was
   // scheduled, but CurrCycle may have been eagerly advanced immediately after
   // scheduling, so may now be greater than ReadyCycle.
   if (ReadyCycle > CurrCycle)
     MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
 #endif
 
-  if (ReadyCycle < MinReadyCycle)
-    MinReadyCycle = ReadyCycle;
-
   // Check for interlocks first. For the purpose of other heuristics, an
   // instruction that cannot issue appears as if it's not in the ReadyQueue.
   bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
-  if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU) ||
-      Available.size() >= ReadyListLimit)
-    Pending.push(SU);
-  else
+  bool HazardDetected = ((!IsBuffered && ReadyCycle > CurrCycle) ||
+                         checkHazard(SU));
+
+  // Check on Available's size already performed, if SU is in Pending queue.
+  // See 'SchedBoundary::releasePending'.
+  if (!InPQueue)
+    HazardDetected = HazardDetected || Available.size() >= ReadyListLimit;
+
+  if (!HazardDetected) {
     Available.push(SU);
+
+    if (ReadyCycle < MinReadyCycle)
+      MinReadyCycle = ReadyCycle;
+
+    if (InPQueue)
+      Pending.remove(Pending.begin() + Idx);
+    return;
+  }
+
+  if (!InPQueue)
+    Pending.push(SU);
 }
 
 /// Move the boundary of scheduled code by one cycle.
 void SchedBoundary::bumpCycle(unsigned NextCycle) {
   if (SchedModel->getMicroOpBufferSize() == 0) {
     assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
            "MinReadyCycle uninitialized");
     if (MinReadyCycle > NextCycle)

 /// visible to heuristics.
 void SchedBoundary::releasePending() {
   // If the available queue is empty, it is safe to reset MinReadyCycle.
   if (Available.empty())
     MinReadyCycle = std::numeric_limits<unsigned>::max();
 
   // Check to see if any of the pending instructions are ready to issue.  If
   // so, add them to the available queue.
-  bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
-  for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
-    SUnit *SU = *(Pending.begin()+i);
-    unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
-
-    if (ReadyCycle < MinReadyCycle)
-      MinReadyCycle = ReadyCycle;
-
-    if (!IsBuffered && ReadyCycle > CurrCycle)
-      continue;
-
-    if (checkHazard(SU))
-      continue;
-
+  for (signed E = Pending.size() - 1; E >= 0; --E) {
     if (Available.size() >= ReadyListLimit)
       break;
 
-    Available.push(SU);
-    Pending.remove(Pending.begin()+i);
-    --i; --e;
+    SUnit *SU = *(Pending.begin() + E);
+    unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
+
+    releaseNode<true>(SU, ReadyCycle, E);
   }
   CheckPending = false;
 }
 
 /// Remove SU from the ready set for this boundary.
 void SchedBoundary::removeReady(SUnit *SU) {
   if (Available.isInQueue(SU))
     Available.remove(Available.find(SU));