This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Don't use not expressions for implied conditions
ClosedPublic

Authored by nikic on Nov 6 2020, 3:16 AM.

Details

Summary

SCEV currently tries to prove implications of x pred y by also trying to imply ~y pred ~x. This is expensive in terms of compile-time (in fact, the vast majority of isImpliedCond compile-time is spent here) and generally not fruitful. The issue is that this also swaps the operands and thus breaks canonical ordering. If originally we were trying to prove an implication like X > C1 => Y > C2, then we'll now try to prove X > C1 => C3 > ~Y, which will not work.

The only real case where we can get some use out of this transform is if the original conditions were in the form X > C1 => Y < C2, were then swapped to X > C1 => C2 > Y and are then swapped again here to X > C1 => ~Y > C3.

As such, handle this at a higher level, where we are doing the swapping in the first place. There's four different ways that we can line up a predicate and a swapped predicate, so we use some heuristics to pick some profitable way.

Because we now try this transform at a higher level (isImpliedCondOperands rather than isImpliedCondOperandsHelper), we can also prove additional facts. Of the added tests, one was proven previously while the other wasn't.

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=40bc309911f0f92ff8b8f64d28cb13a2292695ff&to=0c2feb97b5d529f816a54418bd008fcbbf53d98a&stat=instructions

Diff Detail

Event Timeline

nikic created this revision.Nov 6 2020, 3:16 AM
nikic requested review of this revision.Nov 6 2020, 3:16 AM
nikic added inline comments.Nov 6 2020, 3:19 AM
llvm/test/Analysis/ScalarEvolution/zext-wrap.ll
18

This is a SCEV nowrap caching artifact -- the cached nowrap flags depend on which expressions get constructed. There's no actual change in which implied conditions here. I've put up D90338 as an experiment to improve handling of addrec nowrap flags.

lebedev.ri added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
10773–10775

What happens if the predicate is swapped instead of operands?

nikic updated this revision to Diff 303489.Nov 6 2020, 9:56 AM
nikic edited the summary of this revision. (Show Details)

Preserve transform at a higher level, where we are lining up swapped predicates.

nikic added inline comments.Nov 6 2020, 10:00 AM
llvm/lib/Analysis/ScalarEvolution.cpp
10773–10775

It's not possible to swap the predicate at this point, because this code already works on a single matching predicate only.

However, I think your general idea here is right. I've updated the patch to preserve this transform, but at a higher level: When we try to line up a predicate and a swapped predicate, using this approach allows us to do a "double swap" and thus avoid changing operand order. That allows us to preserve canonical operand ordering, and thus prove useful facts.

Because this is done at a higher level, we'll also try to apply more types of reasoning to the not-ed version.

nikic edited the summary of this revision. (Show Details)Mar 16 2021, 1:41 PM
nikic added reviewers: mkazantsev, reames, lebedev.ri.
nikic set the repository for this revision to rG LLVM Github Monorepo.
mkazantsev added inline comments.Mar 16 2021, 9:36 PM
llvm/lib/Analysis/ScalarEvolution.cpp
10345

nit: please replace <= with <- to make it crystal clear that it's implication and not le :)

10356

I wonder, is AddRec the only case where we expect constant to be on right hand side? I'm pretty sure we want it for most arithmetics we process. Do we regress if SCEVAddRecExpr is removed? This should give even better compile time effect.

llvm/unittests/Analysis/ScalarEvolutionTest.cpp
1405

Nit: this thing should have <nsw>, and the fact being proved is actually not true without this flag.

1411

I think it can be strengthened to {0,+,1}<nuw><nsw> > 1, no?

nikic updated this revision to Diff 332176.Mar 21 2021, 1:30 PM
nikic marked an inline comment as done.

Use different arrow for implication.

nikic added inline comments.Mar 21 2021, 1:33 PM
llvm/lib/Analysis/ScalarEvolution.cpp
10356

We canonicalize addrec to left and constant to right, so this only does the swap if *neither* is present.

llvm/unittests/Analysis/ScalarEvolutionTest.cpp
1405

The <nw> here is based on the flags present in dump(). I think it doesn't actually matter because the implication we're effectively proving is that {0,+,1}<nuw><nsw> > 0 implies {-1,+,1} > -1. And for this part, just the nowrap flag on the left addrec are sufficient, the ones on the rhs are implied.

1411

We should be able to prove that, but don't. After negation, we'll try both {0,+,-1}<nw> < -1 -> {-1,+,-1}<nw> < -2 and {-1,+,1}<nsw> > 0 -> {0,+,1}<nuw><nsw> > 1, but can't prove either.

mkazantsev accepted this revision.Mar 22 2021, 10:27 PM

LGTM, thanks!

llvm/unittests/Analysis/ScalarEvolutionTest.cpp
1411

Wow, that expands the horizons of SCEV's ignorance :)

This revision is now accepted and ready to land.Mar 22 2021, 10:27 PM
This revision was landed with ongoing or failed builds.Mar 24 2021, 1:53 PM
This revision was automatically updated to reflect the committed changes.