Page MenuHomePhabricator

[ValueTracking] Teach isKnownNonZero a new trick
ClosedPublic

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

Details

Summary

If the shifter operand is a constant, and all of the bits shifted out are known to be zero, then if X is known non-zero at least one non-zero bit must remain.

Diff Detail

Repository
rL LLVM

Event Timeline

jmolloy updated this revision to Diff 34543.Sep 11 2015, 5:51 AM
jmolloy retitled this revision from to [ValueTracking] Teach isKnownNonZero a new trick.
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:14 AM
reames added inline comments.
lib/Analysis/ValueTracking.cpp
1837

This really seems like two distinct cases and the code would be clearer if organized as such.

case 1 - There's a known one bit somewhere in the portion not shifted out.

case 2 - All bits shifted out are known-zero and X is known non-zero.

I think what you have is correct, I just found the flow of the code confusing on first read.

unittests/Analysis/ValueTrackingTest.cpp
203 ↗(On Diff #34543)

I'd probably just phrase this as a normal IR test for inst combine or inst simplify. What's here is correct, just needlessly complicated.

hfinkel added inline comments.Sep 18 2015, 7:59 PM
lib/Analysis/ValueTracking.cpp
1832

I don't think this check is necessary, and you can just use Shift->getLimitedValue(BitWidth-1) below, because it is undefined behavior for the number to be larger than that regardless.

sanjoy added a subscriber: sanjoy.Sep 18 2015, 11:31 PM
sanjoy added inline comments.
lib/Analysis/ValueTracking.cpp
1837

You could also check for the exact flag here.

1837

How about if (KnownZero.countTrailingZeros() >= Shift->getLimitedValue())?

1838

I'd expect this first case to be handled by the fall through at the end. Do you have a case where it doesn't?

unittests/Analysis/ValueTrackingTest.cpp
203 ↗(On Diff #34543)

+1 to Philip's comment.

jmolloy marked 4 inline comments as done.Sep 21 2015, 2:36 PM
jmolloy added inline comments.
lib/Analysis/ValueTracking.cpp
1837

I think the exact flag is tested for just above.

1838

Nope - this was purely a compile-speed micro optimization - we've already computed known bits, so it seemed a waste to compute them again.

jmolloy updated this revision to Diff 35308.Sep 21 2015, 2:41 PM

Hi Hal, Sanjoy, Philip,

Thanks very much for the reviews - sorry it took so long to address.

The newest version should address these comments.

Cheers,

James

reames added inline comments.Sep 21 2015, 3:13 PM
lib/Analysis/ValueTracking.cpp
1841

Shouldn't this be countTrailingZeros?

test/Analysis/ValueTracking/knownzero-shift.ll
11

You could just return the i1 directly.

jmolloy marked an inline comment as done.Sep 22 2015, 8:36 AM
jmolloy added inline comments.
lib/Analysis/ValueTracking.cpp
1841

I don't think so, because bits in KnownZero are one if they are known to be zero. I agree it looks confusing though and I've made this mistake in the past.

jmolloy updated this revision to Diff 35376.Sep 22 2015, 8:48 AM
reames accepted this revision.Sep 22 2015, 12:57 PM
reames added a reviewer: reames.

LGTM

This revision is now accepted and ready to land.Sep 22 2015, 12:57 PM
jmolloy closed this revision.Sep 24 2015, 9:08 AM

Thanks Philip!

r248508.