Page MenuHomePhabricator

[SCEV] make SCEV smarter about proving no-wrap.
ClosedPublic

Authored by sanjoy on Feb 28 2015, 10:24 PM.

Details

Summary

Teach SCEV to prove no overflow for an add recurrence by proving
something about the range of another add recurrence a loop-invariant
distance away from it.

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 20950.Feb 28 2015, 10:24 PM
sanjoy retitled this revision from to [SCEV] make SCEV smarter about proving no-wrap..
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added reviewers: atrick, hfinkel.
sanjoy added a subscriber: Unknown Object (MLST).
atrick requested changes to this revision.Mar 3 2015, 2:24 PM
atrick edited edge metadata.

The logic is great. But we really need to determine whether computing SCEV for each recurrence 5 times is worthwhile. Please do some compile time experiments where SCEV is taking more time than usual to find out how much worse this makes it.

Why did you do this rather than checking SCEV's for existing phis? (I realize this is strictly better, but I'm curious about your motivation given that this is potentially a lot of extra work)

lib/Analysis/ScalarEvolution.cpp
1332–1333 ↗(On Diff #20950)

I would like better comments here. It should show the formula.

e.g.

{start - delta,+,step} ult (INT_MAX - delta)

This revision now requires changes to proceed.Mar 3 2015, 2:24 PM
sanjoy added a comment.Mar 3 2015, 2:44 PM

The logic is great. But we really need to determine whether computing SCEV for each recurrence 5 times is worthwhile. Please do some compile time experiments where SCEV is taking more time than usual to find out how much worse this makes it.

Sure, I'll run some experiments and measure the compile time.

Why did you do this rather than checking SCEV's for existing phis?

Do you mean just checking the folding set for an _existing_ SCEVAddRec instead of SE.getAddRecExpr(PreStart, Step, AR->getLoop(), SCEV::FlagAnyWrap)? That sounds like a very good idea, I'll try that.

sanjoy updated this revision to Diff 21165.Mar 3 2015, 6:49 PM
sanjoy edited edge metadata.

Addresses review.

When writing down a proof for proveNoWrapByVaryingStart (thanks for
prodding me to do that!) I realized that the first version had a bug

  • we need to prove (S-X)+X does not overflow for the inference to be

valid. This current version addresses that.

The current version also swaps out a full SCEVAddRecExpr construction
and just looks at the UniqueSCEVs set instead, and gives up if there
isn't a pre-existing add recurrence of the form we need. This should
address the compile time issue.

atrick requested changes to this revision.Mar 3 2015, 10:50 PM
atrick edited edge metadata.

Otherwise looks great!

lib/Analysis/ScalarEvolution.cpp
1357 ↗(On Diff #21165)

I still don't see the bug. How can (3) be false with (1) and (2)? A counter example would help.

This revision now requires changes to proceed.Mar 3 2015, 10:50 PM
sanjoy added inline comments.Mar 3 2015, 11:07 PM
lib/Analysis/ScalarEvolution.cpp
1357 ↗(On Diff #21165)

You're right, (3) is just (1) in the 0th iteration. I'll fix this.

sanjoy updated this revision to Diff 21182.Mar 4 2015, 2:07 AM
sanjoy edited edge metadata.
  • Address review
atrick accepted this revision.Mar 4 2015, 11:25 AM
atrick edited edge metadata.

LGTM

This revision is now accepted and ready to land.Mar 4 2015, 11:25 AM
This revision was automatically updated to reflect the committed changes.