[MachinePipeliner] Fix unscheduled instruction

[thopre]

Summary

Prior to ordering instructions to be scheduled, the machine pipeliner
update recurrence node sets in groupRemainingNodes() by adding in a
given node set any node on the dependency path from a node set with
higher priority to the given node set. The function computePath() that
determine what constitutes a path follows artificial dependencies.

However, when ordering the nodes in the resulting node sets,
computeNodeOrder() calls ignoreDependence when looking at dependencies
which ignores artificial dependencies. This can cause a node not to be
scheduled which then causes wrong code generation and in the case of a
debug build will lead to an assert failure in generatePhis() in
ModuloScheduler.cpp.

This commit adds calls to ignoreDependence() in computePath() to not add
any node in groupRemainingNodes() that would not be ordered by
computeNodeOrder().

[bcahoon]

Hi @sgundapa, just checking if you made a similar change that wasn't upstreamed?

[sgundapa]

No changes related to this @bcahoon.

[thopre]

Adjust PowerPC testcases

[thopre]

Adding @jsji to review the changes to PowerPC testcases. I've checked the MIR after the pipeliner for sms-phi-3.ll and the loop still gets pipelined (which makes sense since the modified code executes after the decision to pipeline is made) but the code gets simplified by later pass. Are you happy with the change?

[bcahoon]

llvm/lib/CodeGen/MachinePipeliner.cpp

1582

I don't think this if condition will ever be true? If PI.getKind() == SDep::Anti, then ignoreDepedendence(PI, true) will also return true, so this condition evaluates to if (true && false).

[thopre]

llvm/lib/CodeGen/MachinePipeliner.cpp

1582

Mmmh indeed. I did this because pred_L calls ignoreDependence so I wanted to be consistent. On the other hand computeNodeOrder does not call ignoreDependence in the BottomUp case. What's the reason for the inconsistency?

[dpenry]

llvm/lib/CodeGen/MachinePipeliner.cpp

1582

I've been looking at the artificial edges of late...

I suspect the inconsistency in computeNodeOrder (a check which doesn't figure into the algorithm in the literature) is there because ignoreDependence is being used beyond its stated purpose of preventing unbounded recursion when computing ALAP/ASAP/etc.

It is now also being used in computeNodeOrder, pred_L, and succ_L for its D.isArtificial() test, which is guarding against following an edge to the ExitSU (branch) node. This edge is an artificial edge for the machine-loop-branch terminated blocks that have been pipelined so far. I found for https://reviews.llvm.org/D122672 that a test for D.getSUnit()->isBoundaryNode() was also necessary -- with general branches you can have non-artificial edges to the branch -- in this function.

It may be the case that ignoreDependence shouldn't have a test for isArtificial or isBoundaryNode at all, but that computeNodeOrder and succL should check isBoundaryNode and pred_L should check isBoundaryNode and D.getKind() == Anti. Indeed, there may be other places where isArtificial is tested that D122672 adds isBoundaryNode tests that don't need isArtificial.

[bcahoon]

llvm/lib/CodeGen/MachinePipeliner.cpp

1582

Good question. I don't recall why ignoreDependence is not called in the BottomUp case. Seems like it should be there. And, yes, it may be clearer to change up ignoreDependence. Part of the confusion is because we need special processing of the anti-depenences that represent back-edges.

[thopre]

llvm/lib/CodeGen/MachinePipeliner.cpp

1582

We also added a few isBoundaryNode check in our backend so I'm looking forward for your patch to land. Why do you want to put the isBoundaryNode check outside ignoreDependence? From your comment it seems it would make more sense to just replace the isArtificial check by a boundary node check and make sure ignoreDependence is used consistently. I'm happy to rework the patch accordingly if you agree with that.

[dpenry]

llvm/lib/CodeGen/MachinePipeliner.cpp

1582

While running in BottomUp, the predecessors are being looked at, and the branch (which is ExitSU) isn't a predecessor and thus there's no "falingl off" onto a boundaryNode in predecessors, at least for the kinds of branch instructions we've seen so far.

The anti-dependence processing is definitely needed in some cases. If we dropped the Artificial check in ignoreDependence and replaced it with a test for isBoundaryNode, I think that has a good chance of working.

It would also remove some interesting "failure to pipeline" cases that I've seen when scheduling takes into account issue width and copy pseudo-ops have non-zero costs. That's another patch I'm working on, but haven't uploaded yet.

[jsji]

In D124267#3468434, @thopre wrote:

Adding @jsji to review the changes to PowerPC testcases. I've checked the MIR after the pipeliner for sms-phi-3.ll and the loop still gets pipelined (which makes sense since the modified code executes after the decision to pipeline is made) but the code gets simplified by later pass. Are you happy with the change?

Thanks for notifying me. I am OK as long as the loop still gets pipelined . We can look into why the code gets simplified by later pass and maybe improve the testcase later.
So, feel free to commit once you address the comments from Brendon.

[thopre]

• Replace isArtificial check by isBoundaryNode
• Remove call to ignoreDependence in computePath for predecessors
• remove no longer needed changes to PowerPC tests

[thopre]

• Rebase
• remove changes to ignoreDependence, it should be done in a separate commit

llvm/lib/CodeGen/MachinePipeliner.cpp

static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
   if (Exclude.contains(Cur))
     return false;
   if (DestNodes.contains(Cur))
     return true;
   if (!Visited.insert(Cur).second)
     return Path.contains(Cur);
   bool FoundPath = false;
   for (auto &SI : Cur->Succs)
-    FoundPath |= computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited);
+    if (!ignoreDependence(SI, false))
+      FoundPath |=
+          computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited);
   for (auto &PI : Cur->Preds)
-    if (PI.getKind() == SDep::Anti)
+    if (PI.getKind() == SDep::Anti && !ignoreDependence(PI, true))
       FoundPath |=
           computePath(PI.getSUnit(), Path, DestNodes, Exclude, Visited);
   if (FoundPath)
     Path.insert(Cur);
   return FoundPath;
 }
 
 /// Compute the live-out registers for the instructions in a node-set.