This is an archive of the discontinued LLVM Phabricator instance.

Teach ScalarEvolution to sharpen range information.
ClosedPublic

Authored by sanjoy on Oct 6 2014, 7:09 PM.

Details

Reviewers
atrick
Summary

This change is dependent on http://reviews.llvm.org/D5638

If x is known to have the range [a, b), in a loop predicated by (icmp ne x, a) its range can be sharpened to [a + 1, b). Get ScalarEvolution and hence IndVars to exploit this fact.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 14486.Oct 6 2014, 7:09 PM
sanjoy retitled this revision from to Teach ScalarEvolution to sharpen range information..
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added a reviewer: atrick.
sanjoy added a subscriber: Unknown Object (MLST).
hfinkel added a subscriber: hfinkel.Oct 9 2014, 4:37 PM

Full context here too please.

sanjoy updated this revision to Diff 14688.Oct 9 2014, 4:45 PM

Added full context and fixed a typo in a comment.

hfinkel added inline comments.Oct 9 2014, 5:08 PM
lib/Analysis/ScalarEvolution.cpp
6539

Don't need {} here.

sanjoy updated this revision to Diff 14691.Oct 9 2014, 5:27 PM

Address Hal's review.

atrick requested changes to this revision.Oct 14 2014, 8:24 PM
atrick edited edge metadata.

There are a couple obvious typos. Please make sure those are fixed to match your intentions.

Otherwise, I think this is fine. I have to admit I had to stare at it for quite some time to understand what's going on, but it does seem like a decent fix for your reasonable test case.

[off the subject of the review a bit]
In general, as we continue piling logic into SCEV I would encourage you to at least run some basic compile-time measurements. One way to do this is to link a bunch of IR files together and run opt -O2 -time-passes.

lib/Analysis/ScalarEvolution.cpp
6531

You mean "not equal to a"?

6552

Why is this line pasted twice?

This revision now requires changes to proceed.Oct 14 2014, 8:24 PM
In D5639#12, @atrick wrote:

There are a couple obvious typos. Please make sure those are fixed to match your intentions.

Will fix, thanks! Just to be clear -- is this okay to check in after those changes or should I re-upload for review?

Otherwise, I think this is fine. I have to admit I had to stare at it for quite some time to understand what's going on, but it does seem like a decent fix for your reasonable test case.

An interesting thing related to the test case: if you change the entry block to

entry:
  %length = load i32* %buffer ;; this line changed (!range removed)
  %entry.pred = icmp slt i32 %length, 1 ;; this line changed (eq => slt)
  br i1 %entry.pred, label %abort, label %loop.preheader

llvm TOT at -O3 will optimize away %oob.pred just fine. But adding the !range metadata makes -instcombine kick in and optimize %length slt 1 to %length eq 0 (the two are equivalent if the msb of %length is 0) clobbering the -indvars optimization. So, on llvm TOT, there is at least one case where adding a !range annotation regresses performance at -O3. This patch fixes that issue too.

[off the subject of the review a bit]
In general, as we continue piling logic into SCEV I would encourage you to at least run some basic compile-time measurements. One way to do this is to link a bunch of IR files together and run opt -O2 -time-passes.

Thanks, will keep that in mind.

atrick accepted this revision.Oct 14 2014, 11:55 PM
atrick edited edge metadata.

LGTM once the typos are fixed.

This revision is now accepted and ready to land.Oct 14 2014, 11:55 PM

This change broke the PushAndPopWithPoisoningTest asan unit test, so I reverted it. I'm looking into why it broke.

sanjoy added inline comments.Oct 20 2014, 6:42 PM
lib/Analysis/ScalarEvolution.cpp
6541

This line is incorrect -- below in the switch I've assumed that Min is the unsharpened minimum value.

sanjoy updated this revision to Diff 15161.Oct 20 2014, 6:47 PM
sanjoy edited edge metadata.

The bug was that the code in the switch...case invoking isImpliedCondOperands assumed Min was the unsharpened minimum. This version of the patch fixes the issue and adds a regression test that would've caught the bug.

The earlier patch was also needlessly complex -- I've simplified the code structure in this revision.

Sorry for the confusion!

sanjoy requested a review of this revision.Nov 3 2014, 6:36 PM
sanjoy edited edge metadata.

Ping!

Is this revised version of the change okay to land?

atrick accepted this revision.Nov 4 2014, 10:26 PM
atrick edited edge metadata.

LGTM, again.

This revision is now accepted and ready to land.Nov 4 2014, 10:26 PM
sanjoy closed this revision.Dec 11 2014, 8:20 PM