[SCEV] Fix isLoopEntryGuardedByCond usage

[skatkov]

Summary

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

[mkazantsev]

LGTM with nits (see comments to the test).

test/Transforms/IndVarSimplify/inner-loop.ll

3

Could you please give some more details on this bug here? It is not clear what problem are you addressing. Either a comment or a reference on bugs.llvm.com would work.

33

should be -> should not be
due to in case -> because if

35

Within a bug -> Due to the bug?
instrction -> instruction

37

Maybe add CHECK-NOT: select i1 true?

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;
 
ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
 
   return false;
 }
 
 bool
 ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
                                           ICmpInst::Predicate Pred,
                                           const SCEV *LHS, const SCEV *RHS) {
+  // 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");
+
   // Interpret a null as meaning no loop, where there is obviously no guard
   // (interprocedural conditions notwithstanding).
   if (!L) return false;
 
   if (isKnownPredicateViaConstantRanges(Pred, LHS, RHS))
     return true;
 
   // Starting at the loop predecessor, climb up the predecessor chain, as long

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);

test/Transforms/IndVarSimplify/inner-loop.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+; This is regression test for the bug in ScalarEvolution::isKnownPredicate
+
+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 be simplified due to in case
+; %i == 26 and %j == 27, %s should be equal to %j.
+; Within a bug the instrction is simplified to
+; %s = select i1 true, i32 %0, i32 %j
+; CHECK: %s = select i1 %cmp
+  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
+}