Page MenuHomePhabricator

[SCEV] Fix incorrect exit count calculated in error scope
ClosedPublic

Authored by mdchen on Dec 1 2020, 12:39 AM.

Details

Summary

In computeLoadConstantCompareExitLimit, the addrec used to compute the
exit count should be from the loop which the exiting block belongs to.

Diff Detail

Event Timeline

mdchen created this revision.Dec 1 2020, 12:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 1 2020, 12:39 AM
mdchen requested review of this revision.Dec 1 2020, 12:39 AM

This is missing a test.
Please refer to llvm-project/llvm/test/Analysis/ScalarEvolution/pr48225.ll for inspiration.

mdchen added a comment.Dec 1 2020, 1:06 AM

@lebedev.ri Thanks, will add a test. Besides, the bug fixed in ea7ab5a42cd4 seems to have the same root cause.

mdchen updated this revision to Diff 308623.Dec 1 2020, 5:37 AM

Add a test case.

Please reduce the test or give an elaborate explanation of the problem. So far it's not clear to me what was the problem and why it fixed this way.

llvm/lib/Analysis/ScalarEvolution.cpp
7849

You require the IdxExpr be from a containing loop, which automatically makes IdxExpr invariant w.r.t. L. So this whole condition is just trivially false. Is that really what you want to make?

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
1

Please commit this test separately using auto-generated checks from utils/update_analyze_test_checks.py. If you are addressing some bug from bugs.llvm.com, better name the test after this bug (like prXXXXX.ll).

Then, apply your changes and re-run utils/update_analyze_test_checks.py on it. The diff will show what your patch has changed.

This test is very big. You could also try to use bugpoint tool to reduce the test (see https://llvm.org/docs/Bugpoint.html), because now I cannot figure what's going on here. Both test reduction (if possible) and explanatory comments (which block/loop are causing the problem and why) would be extremely useful to understand your fix.

mkazantsev added inline comments.Dec 4 2020, 4:25 AM
llvm/lib/Analysis/ScalarEvolution.cpp
7849

Sorry, the whole condition is trivially true. AddRecs from containing loops are always invariant w.r.t child loops.

mdchen added inline comments.Dec 5 2020, 8:18 PM
llvm/lib/Analysis/ScalarEvolution.cpp
7849

You require the IdxExpr be from a containing loop, which automatically makes IdxExpr invariant w.r.t. L

I see...Actually what I need is IdxExpr->getLoop()==L. Though in this case it won't exceed the scope L from where Idx is computed IIUC, I admit it's incorrect. Will do the change.

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
1

I tried llvm-reduce but the output was not desirable, will add necessary comments, thanks! In short, the bug is that when computing the exit count of an outerloop's exiting block, the current computeLoadConstantCompareExitLimit method may choose an addrec of its child loop, which is incorrect.

mdchen marked 2 inline comments as not done.Dec 6 2020, 10:14 PM
mdchen updated this revision to Diff 309830.Dec 7 2020, 1:10 AM
mdchen edited the summary of this revision. (Show Details)
mkazantsev added inline comments.Dec 8 2020, 8:39 PM
llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
1

Then at least do the first step: commit this test as is with auto-generated checks, and then rebase your patch on top of that to show what has changed.

mdchen added inline comments.Dec 8 2020, 10:08 PM
llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
1

Sorry, I don't understand well. Do you mean that I should separate it into two commits or only keep those changed checks?

mkazantsev added inline comments.Jan 13 2021, 11:20 PM
llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
1

I mean two commits.

First commit: this test, with no code changes, with auto-generated checks (use utils/update_analyze_test_checks.py to generate them).
Second commit: your code changes + re-run of utils/update_analyze_test_checks.py to show what has changed.

mdchen added inline comments.Jan 14 2021, 5:25 PM
llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
1

I've submitted the test in D94657, could you review and commit it for me since I don't have the access right.

mdchen updated this revision to Diff 317847.Jan 20 2021, 5:03 AM
mkazantsev accepted this revision.Jan 25 2021, 11:15 PM

LGTM, thanks!

This revision is now accepted and ready to land.Jan 25 2021, 11:15 PM
This revision was automatically updated to reflect the committed changes.