Fix for bug in indvars/ SCEV generating infinite loop (pr18886)

[dinesh.d]

Summary

Condition like SCEV{-1,+,2} != 0 will always true and ScalarEvolution::HowFarToZero was
not generating correct exit limit for such exit conditions. Indvars pass was using these to
eliminate other exit conditions resulting in infinite loop.

This patch fixes PR18886, PR19799 and similar bugs.

[atrick]

Hi Dinesh, thanks for working on this. I just started reviewing your fix right after committing r209358 as a fix for pr19799. It looks like my fix actually handles both test cases. It's really unfortunate that I did not pay attention to pr18886 which was filed much earlier.

I do approve your test case pr18886.ll, would you mind checking that in.

Now let me explain that code.

Before dividing the recurrence's distance by its step, we first check SCEV::FlagNW. This means that the recurrence cannot wrap around past its initial value. So, when we compute the ExitLimit we can assume that the test is not skipped. We do correctly set MustExit=false, which indicates that this loop exit test may be skipped. The value that we use here for ExitLimit is then the number of non-exiting iterations that may occur before exiting the loop via this specific exit. If we exit via another branch, then the value is really meaningless.

The real bug in this case was the way I was summarizing the max backedge count based on the max exit limit from multiple loop exits, which is what my checkin fixed.

[dinesh.d]

No problem :) and thanks for explaining, even your comment in commit is very informative.
I am going thorough Loop Optimization passes to understand how they change IR and there
I came accross these bugs.

I will be happy to check in test case, as you suggested. Should I check in pr18886.ll as it
is or I should put it with your test file.

[atrick]

I added a test case to ScalarEvolution/max-trip-count.ll to directly test -scalar-evolution -analyze.
You could similarly adapt your test case and add it to the same file.

+; CHECK: Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count.
+; CHECK: Loop %for.body.i: max backedge-taken count is 1

[dinesh.d]

Closed by commit rL209645 (authored by dinesh).

lib/Analysis/ScalarEvolution.cpp

#endif
   // branch. Hence MustExit=false.
   //
   // This is only valid for expressions that directly compute the loop exit. It
   // is invalid for subexpressions in which the loop may exit through this
   // branch even if this subexpression is false. In that case, the trip count
   // computed by this udiv could be smaller than the number of well-defined
   // iterations.
   if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW)) {
+    // if start and step, both constant and start % step != 0, loop will never
+    // terminate by this condition.
+    if (isa<SCEVConstant>(Start) &&
+        GetMinTrailingZeros(Start) < GetMinTrailingZeros(Step))
+      return getCouldNotCompute();
+
     const SCEV *Exact =
         getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
     return ExitLimit(Exact, Exact, /*MustExit=*/false);
   }
 
   // If Step is a power of two that evenly divides Start we know that the loop
   // will always terminate.  Start may not be a constant so we just have the
   // number of trailing zeros available.  This is safe even in presence of
   // overflow as the recurrence will overflow to exactly 0.
   const APInt &StepV = StepC->getValue()->getValue();

test/Transforms/IndVarSimplify/pr18886.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+; CHECK-LABEL: @main(
+; CHECK-NOT: br i1 false, label %return, label %for.cond
+; CHECK-NOT: br i1 true, label %for.body, label %return
+
+@a = global i64 0, align 8
+define i32 @main() {
+entry:
+  store i64 -21, i64* @a, align 8
+  br label %for.body
+
+for.body:
+  %storemerge1 = phi i64 [ -21, %entry ], [ %add, %for.cond ]
+  %tobool = icmp eq i64 %storemerge1, 0
+  %add = add nsw i64 %storemerge1, 8
+  br i1 %tobool, label %return, label %for.cond
+
+for.cond:
+  store i64 %add, i64* @a, align 8
+  %cmp = icmp slt i64 %add, 9
+  br i1 %cmp, label %for.body, label %return
+
+return:
+  %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]
+  ret i32 %retval.0
+}

test/Transforms/IndVarSimplify/pr19799.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+; CHECK-LABEL: @bar(
+; CHECK-NOT: br i1 true, label %for.body, label %return
+; CHECK-NOT: br i1 false, label %return, label %for.cond
+
+@a = global i32 0, align 8
+define i32 @bar() {
+entry:
+  store i32 -1, i32* @a, align 4
+  br label %for.body
+
+for.cond:
+  store i32 %add.i, i32* @a, align 4
+  %cmp = icmp slt i32 %storemerge1, 0
+  br i1 %cmp, label %for.body, label %return
+
+for.body:
+  %storemerge1 = phi i32 [ -1, %entry ], [ %add.i, %for.cond ]
+  %tobool = icmp eq i32 %storemerge1, 0
+  %add.i = add nsw i32 %storemerge1, 2
+  br i1 %tobool, label %return, label %for.cond
+
+return:
+  %retval.0 = phi i32 [ 0, %for.body ], [ 1, %for.cond ]
+  ret i32 %retval.0
+}