[Scheduler] Treat weak edges uniformly at entry

[Joe_Nash]

Summary

There is a bug where the assert CurCycle >= SU->getDepth() in
SchedulePostRATDList::ScheduleNodeTopDown will fire when an instruction has only
weak predecessors and would otherwise be available at the entry of a scheduling
dag. For all nodes which are not immediately available, we respect the depth
(which respects weak edges) and do not move nodes from pending to available
until the proper depth is met. This patch makes that consistent for entry
available nodes as well.

[Joe_Nash]

I would add a test case if I could, but the case I noticed the issue with is based on weak edges added by an out-of-tree pass similar to MacroFusion.

[critson]

LGTM

I agree manipulation of the available queue here needs to be made consistent with the scheduling loop below it.

I wonder whether we want to be selecting these instructions (leaf with remaining weak preds) to the pending queue at all?
For example, if the condition on line 536 was extended to exclude SUnits with weak predecessors as well?
That said, in the absence of other leaf nodes then we do want to break weak conditions and schedule these SUnits.
Otherwise we risk not being able to schedule anything, so this seems to be the correct solution.

I guess with this change, in the presence of a single leaf with weak preds then CurCycle will be progressively raised until the assertion in ScheduleNodeTopDown passes?
And such a case is relatively atypical?

[fhahn]

Is it possible to add a test case?

[Joe_Nash]

In D106176#2889686, @critson wrote:

LGTM

I agree manipulation of the available queue here needs to be made consistent with the scheduling loop below it.

I wonder whether we want to be selecting these instructions (leaf with remaining weak preds) to the pending queue at all?
For example, if the condition on line 536 was extended to exclude SUnits with weak predecessors as well?

The only time nodes are added to pending is right at the entry here, and in ReleaseSucc, which is called when strong predecessors are scheduled. So if leaves are not put onto the pending queue here they will never be scheduled

That said, in the absence of other leaf nodes then we do want to break weak conditions and schedule these SUnits.

Unfortunately, that is not what will happen. Without this change, we would get an assertion failure. With this change, we will stall.

Otherwise we risk not being able to schedule anything, so this seems to be the correct solution.

I guess with this change, in the presence of a single leaf with weak preds then CurCycle will be progressively raised until the assertion in ScheduleNodeTopDown passes?

Yes

And such a case is relatively atypical?

I would guess the incidence is zero, since it would cause an assertion failure without this patch.

Something like this patch is necessary to create consistency and avoid breakage, but I do not think it is possible to achieve good schedule results by feeding weak edges to the ListScheduler. For instance, in X86/testb-je-fusion.ll has the same results in many cases whether or not the PostRA scheduler is enabled.
@courbet

[Joe_Nash]

In D106176#2889833, @fhahn wrote:

Is it possible to add a test case?

Do you know a way to create a synthetic schedule DAG for testing? Without that, I would say no, since I don't think we want to create a new schedule mutator purely for testing purposes?

[critson]

In D106176#2890256, @Joe_Nash wrote:

In D106176#2889833, @fhahn wrote:

Is it possible to add a test case?

Do you know a way to create a synthetic schedule DAG for testing? Without that, I would say no, since I don't think we want to create a new schedule mutator purely for testing purposes?

It will be a little bit tedious, but you can create a new unittest under llvm/unittests/CodeGen.

One approach may be to parse some MIR (for an example see MI/LiveIntervalTest.cpp).
Then add a simple DAG mutation to a custom instance of the PostRA scheduler and apply it.

llvm/lib/CodeGen/PostRASchedulerList.cpp

void SchedulePostRATDList::ListScheduleTopDown() {
 
   // Release any successors of the special Entry node.
   ReleaseSuccessors(&EntrySU);
 
   // Add all leaves to Available queue.
   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     // It is available if it has no predecessors.
     if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
+      if (SUnits[i].getDepth() > 0) {
+        assert(SUnits[i].WeakPredsLeft > 0 && "Expected a weak predecessor");
+        PendingQueue.push_back(&SUnits[i]);
+      } else {
         AvailableQueue.push(&SUnits[i]);
         SUnits[i].isAvailable = true;
       }
     }
+  }
 
   // In any cycle where we can't schedule any instructions, we must
   // stall or emit a noop, depending on the target.
   bool CycleHasInsts = false;
 
   // While Available queue is not empty, grab the node with the highest
   // priority. If it is not ready put it back.  Schedule the node.
   std::vector<SUnit*> NotReady;