This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Make isLoopEntryGuardedByCond a bit smarter
ClosedPublic

Authored by mkazantsev on Feb 2 2018, 12:39 AM.

Details

Summary

Sometimes isLoopEntryGuardedByCond cannot prove predicate a > b directly.
But it is a common situation when a >= b is known from ranges and a != b is
known from a dominating condition. Thia patch teaches SCEV to sum these facts
together and prove strict comparison via non-strict one.

Diff Detail

Event Timeline

mkazantsev created this revision.
sanjoy added inline comments.Feb 4 2018, 11:00 PM
lib/Analysis/ScalarEvolution.cpp
9159

Move this to CmpInst, it already has stuff like CmpInst::getInversePredicate.

I'd also s/Loose/NonStrict/ since folks are more likely to be familiar with "strict" than with "loose".

test/Transforms/IRCE/conjunctive-checks.ll
1

Can you please also add a direct SCEV or IndVars test?

mkazantsev marked 2 inline comments as done.

Added a test on indvars.

sanjoy accepted this revision.Feb 6 2018, 12:02 AM

LGTM with the comment addressed.

lib/Analysis/ScalarEvolution.cpp
9161

I'm sorry I didn't notice this before, but I think this is better to "fuse" this into the iteration we're already doing instead of recursing (which will walk the dominating checks again). Perhaps extract out a lambda that you call instead of isImpliedCond in this function that has this bit of logic too?

This revision is now accepted and ready to land.Feb 6 2018, 12:02 AM
mkazantsev added inline comments.Feb 6 2018, 12:36 AM
lib/Analysis/ScalarEvolution.cpp
9161

isLoopEntryGuardedByCond does traverse over dominating conditions. If we do this, we will have O(N^2) with N being number of dominating blocks.

I guess that your point here is that we can be able to prove one fact from assumption and another one from dominating guard. I'm totally fine with that, but I'd rather not fuse it into this loop. I'll give it some thought.

How about merging it as is an then making this improvement in separate patch?

sanjoy added inline comments.Feb 6 2018, 1:25 PM
lib/Analysis/ScalarEvolution.cpp
9161

I guess that your point here is that we can be able to prove one fact from assumption and another one from dominating guard. I'm totally fine with that, but I'd rather not fuse it into this loop.

Yes -- you could do something like: if you can't prove A < B but can prove A != B, simplify the predicate you're trying to prove to A <= B and continue.

How about merging it as is an then making this improvement in separate patch?

Unless you're blocked on this patch, I'd rather do the right thing now than check in something with the intent to remove it later.

mkazantsev added inline comments.Feb 6 2018, 9:14 PM
lib/Analysis/ScalarEvolution.cpp
9161

Ok, I'll remake it.

Blend-in the changes into the existing traversals.

This revision was automatically updated to reflect the committed changes.
mkazantsev added inline comments.Feb 7 2018, 2:35 AM
llvm/trunk/lib/Analysis/ScalarEvolution.cpp
9091 ↗(On Diff #133159)

This assert fails, meaning that the logic of isKnownPredicateViaConstantRanges may be somehow incomplete. We can safely return true here, though.