This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Fix sorting order for AddRecExprs
ClosedPublic

Authored by mkazantsev on May 12 2017, 2:35 AM.

Details

Summary

The existing sorting order in defined CompareSCEVComplexity sorts AddRecExprs by loop depth, but does not pay attention to dominance of loops. This can lead us to the following buggy situation:

for (...) { // loop1
  op1 = {A,+,B}
}
for (...) { // loop2
  op2 = {A,+,B}
  s = add op1, op2
}

In this case there is no guarantee that in operand list of s op2 comes before op1 (loop depth is the same, so they will be sorted just lexicographically), so we can incorrectly treat s as a recurrence of loop1, which is wrong.

This patch changes the sorting logic so that it places the dominated recs before the dominating recs. This ensures that when we pick the first recurrency in the operands order, it will be the bottom-most in terms of domination tree. The attached test set includes some tests that produce incorrect SCEV estimations and crashes with oldlogic.

Diff Detail

Event Timeline

mkazantsev created this revision.May 12 2017, 2:35 AM
sanjoy edited edge metadata.May 12 2017, 11:41 AM

Hi Max,

I'm not sure if such a large change is necessary. Why not do something surgical like this:

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index d712063..054571f 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -2448,6 +2448,15 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
     // Scan all of the other operands to this add and add them to the vector if
     // they are loop invariant w.r.t. the recurrence.
     SmallVector<const SCEV *, 8> LIOps;
+    int BotIdx = Idx;
+    for (int I = Idx + 1; I < Ops.size() && isa<SCEVAddRecExpr>(Ops[I]); ++I)
+      if (DT.dominates(
+              cast<SCEVAddRecExpr>(Ops[BotIdx])->getLoop()->getHeader(),
+              cast<SCEVAddRecExpr>(Ops[I])->getLoop()->getHeader()))
+        BotIdx = I;
+
+    std::swap(Ops[Idx], Ops[BotIdx]);
+
     const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
     const Loop *AddRecLoop = AddRec->getLoop();
     for (unsigned i = 0, e = Ops.size(); i != e; ++i)

that uses the Ops array as a scratch space to get the invariant you need?

The other option (that I like more) is to change CompareSCEVComplexity to get this invariant directly from GroupByComplexity. After that, we can have an assert in getAddExpr to check that GroupByComplexity did what we wanted.

mkazantsev retitled this revision from [SCEV] Fix getAddExpr for recurrencies from different loops to [SCEV] Fix sorting order for AddRecExprs.
mkazantsev edited the summary of this revision. (Show Details)

Thanks Sanjoy, it seems that the approach with sorting order works well. I followed this approach and also added 2 more tests with nested loops.

sanjoy accepted this revision.May 15 2017, 6:05 PM

lgtm with one comment.

lib/Analysis/ScalarEvolution.cpp
638

Can we assert DT.dominates(LHead, RHead) || DT.dominates(RHead, LHead) here?

This revision is now accepted and ready to land.May 15 2017, 6:05 PM
mkazantsev added inline comments.May 15 2017, 10:13 PM
lib/Analysis/ScalarEvolution.cpp
638

Yes, I thought of that. It should be true as long as we only use this method to compare operands of one instruction. I propose to land this as is, and then I'll make a follow-up patch with this change. This will allow us to separate the potential problems (if any of these changes can bring them).

I have two more comments:

  • Can you also add an assert in getAddExpr checking that the expressions are sorted like we expected?
  • Can you please add a comment in CompareSCEVComplexity on why the ordering is needed? A one-liner that "we need this in getAddExpr" is sufficient.

Addressed the last comment.

This revision was automatically updated to reflect the committed changes.