Page MenuHomePhabricator

[ValueTracking] Teach isKnownNonZero about monotonically increasing PHIs
ClosedPublic

Authored by jmolloy on Sep 11 2015, 5:54 AM.

Details

Summary

If a PHI starts at a non-negative constant, monotonically increases (only adds of a constant are supported at the moment) and that add does not wrap, then the PHI is known never to be zero.

Diff Detail

Repository
rL LLVM

Event Timeline

jmolloy updated this revision to Diff 34544.Sep 11 2015, 5:54 AM
jmolloy retitled this revision from to [ValueTracking] Teach isKnownNonZero about monotonically increasing PHIs.
jmolloy updated this object.
jmolloy added reviewers: majnemer, hfinkel.
jmolloy set the repository for this revision to rL LLVM.
jmolloy added a subscriber: llvm-commits.

Hi David, Hal,

Do either of you have any comments on this?

Cheers,

James

reames added a subscriber: reames.Sep 17 2015, 10:21 AM

A couple of meta comments:

  • This is duplicating logic in SCEV. I think that's okay in this case, but we don't want to take that to the extreme.
  • Adding the analogous case isKnownNonNegative (aka, using it to set the sign bit in computeKnownBits) would be a really good idea. An increasing induction variable starting at zero is pretty much the ideal canonical induction variable and we should exploit that.
lib/Analysis/ValueTracking.cpp
1911

I find the Op1 vs Op0 naming confusing. Given this is inherently zero based indexing, mind either using that in the Op names or picking non-index based ones?

1916

Might be time to introduce a isNonNegative on ConstantInt? Could be another patch.

1919

Given you're starting from zero, I think you only need the NSW check. Given INT_MAX is always less than UINT_MAX, I believe the former implies the later in this case. (But we might not yet have proved it.)

jmolloy updated this revision to Diff 35649.Sep 24 2015, 10:13 AM

Hi Philip,

Thanks very much for the review!

I've addressed your comments, and spent some time to convert the test into one that can run through InstSimplify.

Cheers,

James

Adding the analogous case isKnownNonNegative (aka, using it to set the sign bit in computeKnownBits) would be a really good idea. An increasing induction variable starting at zero is pretty much the ideal canonical induction variable and we should exploit that.

It looks like this should already be handled in computeKnownBits (ValueTracking.cpp:1277).

reames accepted this revision.Sep 28 2015, 6:46 PM
reames added a reviewer: reames.

LGTM

This revision is now accepted and ready to land.Sep 28 2015, 6:46 PM
jmolloy closed this revision.Sep 29 2015, 7:10 AM

Thanks Philip, r248796