[SCEV] Fix predicate usage in computeExitLimitFromICmp

[mkazantsev]

Summary

In this method, we invoke SimplifyICmpOperands which takes the Cond predicate
by reference and may change it along with LHS and RHS SCEVs. But then we invoke
computeShiftCompareExitLimit with Values from which the SCEVs have been derived,
these Values have not been modified while Cond could be.

One of possible outcomes of this is that we may falsely prove that an infinite loop ends
within some finite number of iterations.

In this patch, we save the original Cond and pass it along with original operands.
This logic may be removed in future once computeShiftCompareExitLimit works
with SCEVs instead of value operands.

[sanjoy]

lgtm!

lib/Analysis/ScalarEvolution.cpp

7061

If possible, I'd suggest also cleaning this up a bit -- the variable should be called Pred and not Cond (a later NFC change is fine).

Also, how about making OriginalCond const so that it obviously can't be modified?

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

7061

Fair point, I'll do it.

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::computeExitLimitFromICmp(const Loop *L,
                                           bool ControlsExit,
                                           bool AllowPredicates) {
   // If the condition was exit on true, convert the condition to exit on false
   ICmpInst::Predicate Cond;
   if (!L->contains(FBB))
     Cond = ExitCond->getPredicate();
   else
     Cond = ExitCond->getInversePredicate();
+  ICmpInst::Predicate OriginalCond = Cond;
 
   // Handle common loops like: for (X = "string"; *X; ++X)
   if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
     if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
       ExitLimit ItCnt =
         computeLoadConstantCompareExitLimit(LI, RHS, L, Cond);
       if (ItCnt.hasAnyInfo())
         return ItCnt;
ScalarEvolution::computeExitLimitFromICmp(const Loop *L,
 
   auto *ExhaustiveCount =
       computeExitCountExhaustively(L, ExitCond, !L->contains(TBB));
 
   if (!isa<SCEVCouldNotCompute>(ExhaustiveCount))
     return ExhaustiveCount;
 
   return computeShiftCompareExitLimit(ExitCond->getOperand(0),
-                                      ExitCond->getOperand(1), L, Cond);
+                                      ExitCond->getOperand(1), L, OriginalCond);
 }
 
 ScalarEvolution::ExitLimit
 ScalarEvolution::computeExitLimitFromSingleExitSwitch(const Loop *L,
                                                       SwitchInst *Switch,
                                                       BasicBlock *ExitingBlock,
                                                       bool ControlsExit) {
   assert(!L->contains(ExitingBlock) && "Not an exiting block!");

test/Analysis/ScalarEvolution/shift-op.ll

loop:
   %iv.test = lshr i32 %iv, 1
   %exit.cond = icmp eq i32 %iv.test, -1
   br i1 %exit.cond, label %leave, label %loop
 
  leave:
   ret void
 }
 
+define void @test9() {
+; CHECK-LABEL: Determining loop execution counts for: @test9
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; This is an infinite loop, make sure that it recognized as such.
+
+entry:
+  br label %loop
+
+leave:
+  ret void
+
+loop:
+  %iv = phi i32 [ -20, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = ashr i32 %iv, 1
+  %exit.cond = icmp sgt i32 %iv, -1
+  br i1 %exit.cond, label %leave, label %loop
+}
+
 !0 = !{i32 0, i32 50000}
 !1 = !{i32 -5000, i32 -1}