Page MenuHomePhabricator

[SCEV] Extend mustprogress reasoning to ne exit tests
Needs RevisionPublic

Authored by reames on Jun 9 2021, 2:48 PM.

Details

Reviewers
nikic
mkazantsev
Summary

The motivation here is simple loops with unsigned induction variables w/non-one steps and inequality tests. A toy example would be:
for (unsigned i = 0; i != N; i += 2) { body; }

If body contains no side effects, and this is a mustprogress function, we can assume that this must be a finite loop and thus that the exit count is N/2.

This builds on the logic from 38540d71, and is more fully explained there. Note that we canonicalize to NE tests in LFTR, so after the previous change we'd compute an exit count, perform LFTR, and then "forget" what the exit count was again.

I plan on extending this to GT tests in a future change.

Diff Detail

Event Timeline

reames created this revision.Jun 9 2021, 2:48 PM
reames requested review of this revision.Jun 9 2021, 2:48 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 9 2021, 2:48 PM
mkazantsev requested changes to this revision.Jun 9 2021, 9:32 PM

Please add tests for this this exit doesn't dominate the latch.

llvm/lib/Analysis/ScalarEvolution.cpp
7918

It is only true if this condition dominates the latch. If not, it might exit at some point during the iteration space, but it was guarded by a volatile condition that prevented it. If my understanding is correct, please specify this requirement explicitly in function's comment.

Maybe (I'm not sure) this still holds for non-dominating exits if it is the only exit from the loop.

7931

Please add early bail if IV is not affine. This will save compile time for complex addrecs.

7933

How about negative powers of 2? I think all your reasoning validly applies for them too.

7942

This should go before anything else to save compile time.

llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
10

Please use ./utils/update_analyze_test_checks.py. It works well with SCEV.

This revision now requires changes to proceed.Jun 9 2021, 9:32 PM
reames added inline comments.Jun 11 2021, 10:12 AM
llvm/lib/Analysis/ScalarEvolution.cpp
7918

All exits being analyzed for exit counts must dominate the latch. See computeExitLimit.

I might be remembering this wrong, but I think you were even the person who added that code. :)

7931

I don't think it actually saves anything in this case. Both callers filter out non-affine ARs before calling this. I'll make it an assert though.

7933

I believe it does too. Incrementalism. And not terrible relevant for LT/EQ cases, it'll be more important when applied to GT.

7942

Er, I think you misread the code? It's at the earliest point it can legally be. It's proving no-self-wrap.

llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
10

No actually, it doesn't. It just claims to. I've tried it with other test changes recently, and been very unpleasantly surprised. It mostly just results in missing check lines.