Page MenuHomePhabricator

[IndVars] Use isLoopBackedgeGuardedByCond for last iteration check
ClosedPublic

Authored by mkazantsev on Nov 16 2020, 5:45 AM.

Details

Summary

Use more context to prove contextual facts about the last iteration. It is
only executed when the backedge is taken, so we can use isLoopBackedgeGuardedByCond
to make this check.

Diff Detail

Event Timeline

mkazantsev created this revision.Nov 16 2020, 5:45 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 16 2020, 5:45 AM
mkazantsev planned changes to this revision.Nov 17 2020, 1:03 AM

Marking "planned changes" until dependencies are merged.

skatkov added inline comments.Nov 18 2020, 1:13 AM
llvm/lib/Analysis/ScalarEvolution.cpp
9676

The only concern I have: whether isLoopBackedgeGuardedByCond always produces better result than isKnownPredicateAt.

mkazantsev requested review of this revision.Nov 18 2020, 8:12 PM
mkazantsev added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
9676

I ran 4077 fuzzer-generated test with assert that whenever the new condition is false, the old condition is also false. Theoretically, this might happen. But it's just a reason to make isLoopBackedgeGuardedByCond smarter.

skatkov accepted this revision.Nov 18 2020, 8:14 PM
skatkov added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
9676

I hope no one test failed :)

This revision is now accepted and ready to land.Nov 18 2020, 8:14 PM

Yes, I ran 4077 fuzz tests checking this assumption, and it seems better in every case there. There can theoretically be cases where isLoopBackedgeGuardedBy is weaker, but it's only the reason to improve it.

Eeek. I found a test where isKnownPredicateAt is more powerful. Need to use both then.

mkazantsev added a comment.EditedNov 25 2020, 7:14 PM

Actually, it only means that isLoopBackedgeGuardedByCond should directly call isKnownPredicateAt(Latch->getTerminator()) as the last resort. I will follow-up with this improvement adding relevant test.