Re-apply [SCEV] Fix isLoopEntryGuardedByCond usage

[skatkov]

Summary

[SCEV] Fix isLoopEntryGuardedByCond usage

ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check
that SCEV is available at entry point of the loop. It is incorrect and fixed by patch.

To bugs additionally fixed:
assert is moved after the check whether loop is not a nullptr.
Usage of isLoopEntryGuardedByCond in ScalarEvolution::isImpliedCondOperandsViaNoOverflow
is guarded by isAvailableAtLoopEntry.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

9066 ↗

(On Diff #131048)

I think this should be an assert -- if a caller is passing in unavailable SCEVs then it probably has other bugs too which this change will hide.

[skatkov]

lib/Analysis/ScalarEvolution.cpp

9066 ↗

(On Diff #131048)

Hi Sanjoy, I did first time this as an assert, see https://reviews.llvm.org/rL323077.
And I revert it due to there were a lot of buildbot failures. Adding this check to every case makes the code is not readable :)

What do you think? Does it makes sense to do it as an assert and update all invocations in spite of readability?

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

9066 ↗

(On Diff #131048)

And I revert it due to there were a lot of buildbot failures.

Can you give some examples of where this failed (i.e. from where are we passing in bogus LHS and RHS to isLoopEntryGuardedByCond)? As I said, I won't be surprised if those places are buggy due to other reasons too.

I would be fine if you added a helper function that does the availability check and then calls isLoopEntryGuardedByCond but I suspect a descriptive name of the helper will be more annoying to type out than the availability check + the call to isLoopEntryGuardedByCond.

[skatkov]

Hi Sanjoy,

The number of buildbot failures were so big but I remember the following case (if I do not miss anything):

1. All Usages in IRCE caused an assert in unit testing
2. Crash was in getSignExtendExpr: the prblem was with LHS. Might be it is the same issue as 3rd one. Example: http://lab.llvm.org:8011/builders/clang-s390x-linux/builds/14076/steps/ninja%20check%201/logs/stdio or http://lab.llvm.org:8011/builders/clang-s390x-linux-lnt/builds/4265/steps/ninja%20check%201/logs/stdio
3. Most popular ScalarEvolution::isImpliedCondOperandsViaNoOverflow (LHS). Example : http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux-perf/builds/3854/steps/test-suite/logs/test.log

I hope it helps.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9066 ↗

(On Diff #131048)

I see the asserts in the initial patch were before we check L on nullptr. I guess this is the reason why buildbots failed. I also think that these should be asserts, and in exactly that place where they are now.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9066 ↗

(On Diff #131048)

Also the initial patch lacks availability check in isImpliedViaNoOverflow. It was a real bug, I believe.

[mkazantsev]

I've revisited all usages of this method and think that https://reviews.llvm.org/rL323077 can be reapplied with two changes:

1. Asserts should be done after we check the L on nullptr;
2. In isImpliedViaNoOverflow, you should check availability of FoundRHS (which was not done in the initial patch).

Other places look good: the values coming as parameters there seem to be invariants avaliable on loop entry.

[skatkov]

Thanks to Max who found a bug in my initial patch.

[mkazantsev]

This should be fine.

[sanjoy]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

8672

I still suspect (but am not sure) that this is too "deep" in the call stack to bail out like this -- I suspect the bug is somewhere up in a caller since the query {A,+,B}<L> pred <thing not available on L's entry> seems nonsensical.

I want to throw this in a debugger and take a look, but the attached test case does not fail for me on rL324202 (with opt -indvars inner-loop.ll). Can you please verify that the test case fails for you without the SCEV changes?

[skatkov]

Doing right now.. building will take some time.

When I created this test and debugged it, it really failed and isLoopEntryGuardedByCond returned true and select simplified...

[skatkov]

As I remember the story was as follows:
LHS was based on %j which is LAR for inner loop.
RHS was a sign or zero ext of AddRec for %i which is not AddRec itself.

L was outer loop.

Something like this but I need to check...

[skatkov]

Hi Sanjoy, I took the fresh llvm rL324205, revert this commit (rL324204) and:
$ opt -indvars ./inner-loop.ll -S | grep select

%s = select i1 true, i32 %0, i32 %j

[skatkov]

$ ~/work/llvm/build/buildDA/bin/opt -indvars ./inner-loop.ll -S | ~/work/llvm/build/buildDA/bin/FileCheck ./inner-loop.ll
<stdin>:28:2: error: CHECK-NOT: string occurred!
%s = select i1 true, i32 %0, i32 %j
^
./inner-loop.ll:39:14: note: CHECK-NOT: pattern specified here
; CHECK-NOT: %s = select i1 true

^

[sanjoy]

Sorry, I incorrectly assumed that this was fixing a failed assert so I was looking for a crash. I am able to reproduce the crash after reverting this change but adding back the isAvailableAtLoopEntry assert only. Moreover, I think the assert is sound.

Having said that, I think this is a generic bug with how isKnownPredicate handles predicates between add recurrences. What it used to do before your change doesn't make sense to me for three reasons:

1. It tries to do this weird double induction on the two add recurrences. However, it does not check that the two add recurrences are from the same loop, and without this precondition the function is definitely buggy.
2. Even if we fix (1) we are still checking a stronger condition that necessary (and in some cases it may even be too weak a.k.a. incorrect, but I've not thought deeply about this). I think we should be invoking induction on both the add recurrences at the same time.
3. It only look at the outermost operation of LHS and RHS. It should instead by checking if the LHS and RHS are *functions* of add recurrences.

So I think the right fix involves doing the following:

1. Add the isAvailableAtLoopEntry assert to isLoopEntryGuardedByCond. I think that assert is sound.
2. In isKnownPredicate, find the deepest loops in LHS and RHS. Call then L_L and L_R. The invariant is that one's header has to dominate the other, or L_R == L_L.
   1. If L_R == L_L then check if entry to L_L is guarded by First(LHS, L_L) pred First(RHS, L_R) and backedge is guarded by PostInc(LHS, L_L) pred PostInc(RHS, L_R).
   2. If L_L dominates L_R then check if entry to L_R is guarded by L_L pred First(L_R) and if backedge is guarded by L_R pred PostInc(RHS, L_R) [i.e. treat RHS as an induction variable, and LHS as a loop invariant value].
   3. Symmetric clause as (B) if L_R dominates L_L.

Where First(X, L) is defined as "in X replace all add recs with loop L with their initial value" and PostInc(X, L) is defined as "in X replace all add recs with loop L with their post-inc value". We may already have SCEV rewriters that do this.

What do you think?

[mkazantsev]

I agree in general, just few notions.

It only look at the outermost operation of LHS and RHS. It should instead by checking if the LHS and RHS are *functions* of add recurrences.

Even more, I think it's useful to have a helper function that returns the set of loops on which the current SCEV may depend. These are loops on which its SCEVAddRecs depend on.

In isKnownPredicate, find the deepest loops in LHS and RHS. Call then L_L and L_R. The invariant is that one's header has to dominate the other, or L_R == L_L.

It should not be deepest loops, but lowest by domination. For example:

for (i1 = 0; i1 != e1; i1++) // L1
  for (i2 = 0; i2 != e2; i2++) // L2
    ...
for (i3 = 0; i3 != e3; i3++) // L3
  ...

If LHS depends on i1, i2 and i3 then L_L should be the loop of i3 (while the deepest is the loop of i2).

I think this is how implementation of this method should look like:

isKnownPredicate(Pred, LHS, RHS) {
  1. Collect set S all loops on which either LHS or RHS depend.
  2. If S is non-empty
    a. Let PD be the element of S which is dominated by all other elements of S
    b. Let E(LHS) be value of LHS on entry of PD.
       To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values.
       Define E(RHS) in the same way.
    c. Let B(LHS) be value of L on backedge of PD.
       To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values.
       Define B(RHS) in the same way.
    d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that.
    e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
  3. Return true if Pred, L, R is known from ranges, splitting etc.
}

For my code example above, we have three loops L1, L2, L3 with AddRecs {0,+,1}<L1>, {0,+,1}<L2>, {0,+,1}<L3>. Let for example LHS = {0,+,1}<L1> + {0,+,1}<L3> and RHS = {0,+,1}<L2> + {0,+,1}<L3>. Accodring to the algorithm:

isKnownPredicate(Pred, LHS, RHS) {
  1. Set S consists of loops L1, L2, L3.
  2. S is non-empty.
    a. PD is a loop of S which is dominated by all other loops, which happens to be L3.
    b. E(LHS) = E({0,+1}<L1> + {0,+,1}<L3>) = ({0,+,1}<L1> + 0. E(RHS) = E({0,+,1}<L2> + {0,+,1}<L3>) = {0,+,1}<L2> + 0.
        Hint: We've taken entry value of {0,+1}<L3> because it is depends on L3, and we took all other AddRecs as is because they do not.

    c.  B(LHS) = B({0,+1}<L1> + {0,+,1}<L3>) = {0,+,1}<L1> + {1,+,1}<L3>. B(RHS) = B({0,+,1}<L2> + {0,+,1}<L3>) = {0,+1}<L2>+ {1,+,1}<L3>.
       Hint: We've taken backedge value of {0,+,1}<L3> because it is depends on L3, and we took all other AddRecs as is because they do not.

    d. Assert that E(LHS) and E(RHS) are available at entry of L3.
    e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
  e. Check ranges etc.

How does it sound to you?

[sanjoy]

In D42417#998618, @mkazantsev wrote:

I agree in general, just few notions.

It only look at the outermost operation of LHS and RHS. It should instead by checking if the LHS and RHS are *functions* of add recurrences.

Even more, I think it's useful to have a helper function that returns the set of loops on which the current SCEV may depend. These are loops on which its SCEVAddRecs depend on.

There already is SCEVInitRewriter. There may a SCEVPostIncRewriter too, but I'm not sure. In any case, it should be easy to write.

In isKnownPredicate, find the deepest loops in LHS and RHS. Call then L_L and L_R. The invariant is that one's header has to dominate the other, or L_R == L_L.

It should not be deepest loops, but lowest by domination. For example:

for (i1 = 0; i1 != e1; i1++) // L1
  for (i2 = 0; i2 != e2; i2++) // L2
    ...
for (i3 = 0; i3 != e3; i3++) // L3
  ...

If LHS depends on i1, i2 and i3 then L_L should be the loop of i3 (while the deepest is the loop of i2).

Yes, should have been "most dominated". And we can assert that the dominates relation forms a total order on the loops.

I think this is how implementation of this method should look like:

isKnownPredicate(Pred, LHS, RHS) {
  1. Collect set S all loops on which either LHS or RHS depend.
  2. If S is non-empty
    a. Let PD be the element of S which is dominated by all other elements of S
    b. Let E(LHS) be value of LHS on entry of PD.
       To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values.
       Define E(RHS) in the same way.
    c. Let B(LHS) be value of L on backedge of PD.
       To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values.
       Define B(RHS) in the same way.
    d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that.
    e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
  3. Return true if Pred, L, R is known from ranges, splitting etc.
}

SGTM.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
   // If LHS and RHS are both addrec, both conditions must be true in
   // every iteration of the loop.
   const SCEVAddRecExpr *LAR = dyn_cast<SCEVAddRecExpr>(LHS);
   const SCEVAddRecExpr *RAR = dyn_cast<SCEVAddRecExpr>(RHS);
   bool LeftGuarded = false;
   bool RightGuarded = false;
   if (LAR) {
     const Loop *L = LAR->getLoop();
-    if (isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) &&
+    if (isAvailableAtLoopEntry(RHS, L) &&
+        isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) &&
         isLoopBackedgeGuardedByCond(L, Pred, LAR->getPostIncExpr(*this), RHS)) {
       if (!RAR) return true;
       LeftGuarded = true;
     }
   }
   if (RAR) {
     const Loop *L = RAR->getLoop();
-    if (isLoopEntryGuardedByCond(L, Pred, LHS, RAR->getStart()) &&
+    if (isAvailableAtLoopEntry(LHS, L) &&
+        isLoopEntryGuardedByCond(L, Pred, LHS, RAR->getStart()) &&
         isLoopBackedgeGuardedByCond(L, Pred, LHS, RAR->getPostIncExpr(*this))) {
       if (!LAR) return true;
       RightGuarded = true;
     }
   }
   if (LeftGuarded && RightGuarded)
     return true;
 

 bool
 ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
                                           ICmpInst::Predicate Pred,
                                           const SCEV *LHS, const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard
   // (interprocedural conditions notwithstanding).
   if (!L) return false;
 
+  // Both LHS and RHS must be available at loop entry.
+  assert(isAvailableAtLoopEntry(LHS, L) &&
+         "LHS is not available at Loop Entry");
+  assert(isAvailableAtLoopEntry(RHS, L) &&
+         "RHS is not available at Loop Entry");
+
   if (isKnownPredicateViaConstantRanges(Pred, LHS, RHS))
     return true;
 
   // Starting at the loop predecessor, climb up the predecessor chain, as long
   // as there are predecessors that can be found that have unique successors
   // leading to the original header.
   for (std::pair<BasicBlock *, BasicBlock *>
          Pair(L->getLoopPredecessor(), L->getHeader());
bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
   if (Pred == CmpInst::ICMP_ULT) {
     FoundRHSLimit = -(*RDiff);
   } else {
     assert(Pred == CmpInst::ICMP_SLT && "Checked above!");
     FoundRHSLimit = APInt::getSignedMinValue(getTypeSizeInBits(RHS->getType())) - *RDiff;
   }
 
   // Try to prove (1) or (2), as needed.
-  return isLoopEntryGuardedByCond(L, Pred, FoundRHS,
+  return isAvailableAtLoopEntry(FoundRHS, L) &&
+         isLoopEntryGuardedByCond(L, Pred, FoundRHS,
                                   getConstant(FoundRHSLimit));
 }
 
 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
                                             const SCEV *LHS, const SCEV *RHS,
                                             const SCEV *FoundLHS,
                                             const SCEV *FoundRHS) {
   if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundLHS, FoundRHS))

llvm/trunk/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

if (LatchBrExitIdx == 0) {
                                                  SE.getOne(Step->getType()));
       if (SumCanReachMax(SE, RightSCEV, StepMinusOne, IsSignedPredicate)) {
         // TODO: this restriction is easily removable -- we just have to
         // remember that the icmp was an slt and not an sle.
         FailureReason = "limit may overflow when coercing le to lt";
         return None;
       }
 
-      if (!SE.isLoopEntryGuardedByCond(
-              &L, BoundPred, IndVarStart,
+      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
+          !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart,
                                        SE.getAddExpr(RightSCEV, Step))) {
         FailureReason = "Induction variable start not bounded by upper limit";
         return None;
       }
 
       // We need to increase the right value unless we have already decreased
       // it virtually when we replaced EQ with SGT.
       if (!DecreasedRightValueByOne) {
         IRBuilder<> B(Preheader->getTerminator());
         RightValue = B.CreateAdd(RightValue, One);
       }
     } else {
-      if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
+      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
+          !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
         FailureReason = "Induction variable start not bounded by upper limit";
         return None;
       }
       assert(!DecreasedRightValueByOne &&
              "Right value can be decreased only for LatchBrExitIdx == 0!");
     }
   } else {
     bool IncreasedRightValueByOne = false;
if (LatchBrExitIdx == 0) {
       const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
       if (SumCanReachMin(SE, RightSCEV, StepPlusOne, IsSignedPredicate)) {
         // TODO: this restriction is easily removable -- we just have to
         // remember that the icmp was an sgt and not an sge.
         FailureReason = "limit may overflow when coercing ge to gt";
         return None;
       }
 
-      if (!SE.isLoopEntryGuardedByCond(
+      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
+          !SE.isLoopEntryGuardedByCond(
                &L, BoundPred, IndVarStart,
                SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())))) {
         FailureReason = "Induction variable start not bounded by lower limit";
         return None;
       }
 
       // We need to decrease the right value unless we have already increased
       // it virtually when we replaced EQ with SLT.
       if (!IncreasedRightValueByOne) {
         IRBuilder<> B(Preheader->getTerminator());
         RightValue = B.CreateSub(RightValue, One);
       }
     } else {
-      if (!SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
+      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
+          !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
         FailureReason = "Induction variable start not bounded by lower limit";
         return None;
       }
       assert(!IncreasedRightValueByOne &&
              "Right value can be increased only for LatchBrExitIdx == 0!");
     }
   }
   BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);

llvm/trunk/test/Transforms/IndVarSimplify/inner-loop.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+; This is regression test for the bug in ScalarEvolution::isKnownPredicate.
+; It does not check whether SCEV is available at loop entry before invoking
+; and utility function isLoopEntryGuardedByCond and that leads to miscompile.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @foo(i64)
+declare void @bar(i32)
+
+define void @test(i8* %arr) {
+entry:
+  br label %outer_header
+
+outer_header:
+  %i = phi i32 [40, %entry], [%i.next, %outer_latch]
+  %i.64 = sext i32 %i to i64
+  br label %inner_header
+
+inner_header:
+  %j = phi i32 [27, %outer_header], [%j.next, %inner_backedge]
+  %j1 = zext i32 %j to i64
+; The next 4 lines are required for avoid widening of %j and
+; SCEV at %cmp would not be AddRec.
+  %gep = getelementptr inbounds i8, i8*  %arr, i64 %j1
+  %ld = load i8, i8* %gep
+  %ec = icmp eq i8 %ld, 0
+  br i1 %ec, label %return, label %inner_backedge
+
+inner_backedge:
+  %cmp = icmp ult i32 %j, %i
+  %s = select i1 %cmp, i32 %i, i32 %j
+; Select should not be simplified because if
+; %i == 26 and %j == 27, %s should be equal to %j.
+; In case of a bug the instruction is simplified to
+; %s = select i1 true, i32 %0, i32 %j
+; CHECK-NOT: %s = select i1 true
+  call void @bar(i32 %s)
+  %j.next = add nsw i32 %j, -2
+  %cond = icmp ult i32 %j, 3
+  br i1 %cond, label %outer_latch, label %inner_header
+
+outer_latch:
+  %i.next = add i32 %i, -1
+  %cond2 = icmp sgt i32 %i.next, 13
+; This line is just for forcing widening of %i
+  call void @foo(i64 %i.64)
+  br i1 %cond2, label %outer_header, label %return
+
+return:
+  ret void
+}