This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Try to prove predicates by splitting them.
ClosedPublic

Authored by sanjoy on Sep 21 2015, 6:26 PM.

Details

Summary

This change teaches SCEV that to prove A u< B it is sufficient to
prove each of these facts individually:

  • B >= 0
  • A s< B
  • A >= 0

In practice, SCEV sometimes finds it easier to prove these facts
individually than to prove A u< B as one atomic step.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 35336.Sep 21 2015, 6:26 PM
sanjoy retitled this revision from to [SCEV] Try to prove predicates by splitting them..
sanjoy updated this object.
sanjoy added reviewers: reames, atrick, hfinkel, nlewycky.
sanjoy added a subscriber: llvm-commits.
sanjoy updated this object.Sep 22 2015, 1:51 PM
hfinkel added inline comments.Sep 27 2015, 2:47 PM
lib/Analysis/ScalarEvolution.cpp
6987

Why do you use isKnownNonNegative(RHS) but not isKnownNonNegative(LHS)?

sanjoy added inline comments.Sep 27 2015, 3:04 PM
lib/Analysis/ScalarEvolution.cpp
6987

isKnownNonNegative is less powerful than isKnownPredicate. isKnownPredicate does a control dependence analysis while isKnownNonNegative just looks at getSignedRange which does not take most control dependence into account (it does take some control dependence into account indirectly, by leveraging the no-wrap flags on SCEV instructions).

The cases we're looking to optimize are of the form %iv ult %length. Here %length is a load instruction with !range metadata that lets us directly prove that %length is positive without control dependence, and %iv is an induction variable which takes some control dependence analysis to prove as being always positive.

I cannot try this out before tomorrow, but I think using isKnownPredicate to prove RHS is positive as well should work (except we'll be burning more compile time). Another possibility is to keep the code as is, and add what I said here as a comment.

hfinkel added inline comments.Sep 28 2015, 2:21 PM
lib/Analysis/ScalarEvolution.cpp
6987

I'd only recommend doing the more expensive thing if you can construct a test case where it helps, and that test case is in canonical form (i.e. IndVarSimplify would not change it to make the simpler version work). Otherwise, just adding what you have here as a comment should be fine.

sanjoy updated this revision to Diff 35926.Sep 28 2015, 4:39 PM
  • rebase + add comment suggested by Hal
hfinkel accepted this revision.Oct 2 2015, 10:49 AM
hfinkel edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Oct 2 2015, 10:49 AM
This revision was automatically updated to reflect the committed changes.