Page MenuHomePhabricator

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

Authored by dinesh.d on May 20 2014, 4:18 AM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

dinesh.d updated this revision to Diff 9606.May 20 2014, 4:18 AM
dinesh.d retitled this revision from to Fix for bug in indvars/ SCEV generating infinite loop (pr18886).
dinesh.d updated this object.
dinesh.d edited the test plan for this revision. (Show Details)
dinesh.d added reviewers: atrick, hfinkel.
dinesh.d added a subscriber: Unknown Object (MLST).
dinesh.d updated this object.May 20 2014, 4:34 AM
atrick edited edge metadata.May 21 2014, 6:37 PM

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.

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.

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 this revision.May 26 2014, 11:52 PM
dinesh.d updated this revision to Diff 9822.

Closed by commit rL209645 (authored by dinesh).