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

llvm/trunk/test/Analysis/ScalarEvolution/max-trip-count.ll

for.cond.i:                                       ; preds = %for.body.i
   store i32 %add.i.i, i32* @a, align 4
   %cmp.i = icmp slt i32 %storemerge1.i, 0
   br i1 %cmp.i, label %for.body.i, label %bar.exit
 
 bar.exit:                                         ; preds = %for.cond.i, %for.body.i
   ret i32 0
 }
 
+; PR18886: Indvars miscompile due to an incorrect max backedge taken count from SCEV.
+; CHECK-LABEL: @pr18886
+; CHECK: Loop %for.body: <multiple exits> Unpredictable backedge-taken count. 
+; CHECK: Loop %for.body: max backedge-taken count is 3
+@aa = global i64 0, align 8
+
+define i32 @pr18886() {
+entry:
+  store i64 -21, i64* @aa, 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* @aa, 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
+}
+
 ; Here we have a must-exit loop latch that is not computable and a
 ; may-exit early exit that can only have one non-exiting iteration
 ; before the check is forever skipped.
 ;
 ; CHECK-LABEL: @cannot_compute_mustexit
 ; CHECK: Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count. 
 ; CHECK: Loop %for.body.i: Unpredictable max backedge-taken count. 
 @b = common global i32 0, align 4