This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Teach isImpliedCondition a new bitwise trick
ClosedPublic

Authored by sanjoy on Nov 5 2015, 1:27 PM.

Details

Summary

This change teaches isImpliedCondition to prove things like

(A | 15) < L  ==>  (A | 14) < L

if the low 4 bits of A are known to be zero.

Depends on D14391

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 39407.Nov 5 2015, 1:27 PM
sanjoy retitled this revision from to [ValueTracking] Teach isImpliedCondition a new bitwise trick.
sanjoy updated this object.
sanjoy added reviewers: majnemer, reames, hfinkel.
sanjoy added a subscriber: llvm-commits.
reames added inline comments.Nov 6 2015, 4:37 PM
lib/Analysis/ValueTracking.cpp
4123 ↗(On Diff #39407)

A cleaner way of framing this content is simply to state that X | C where X low bits are zero is equivalent to X+C.

4136 ↗(On Diff #39407)

Hm, might it be cleaner to introduce a matcher which matches both adds and adds implemented via OR? Doing so would simplify this code, but might involve recomputing known bits twice. Not sure if this is actually a good idea or not.

4143 ↗(On Diff #39407)

This is equivalent to 1 << LowZeroes right?

Might be clearer as uge(MaskOfOnesForLowZeros).

reames requested changes to this revision.Nov 6 2015, 4:37 PM
reames edited edge metadata.
This revision now requires changes to proceed.Nov 6 2015, 4:37 PM
sanjoy updated this revision to Diff 39720.Nov 9 2015, 10:44 AM
sanjoy edited edge metadata.
  • address review
reames accepted this revision.Nov 10 2015, 2:28 PM
reames edited edge metadata.

LGTM w/fix for issues in comment and test which would have caught same.

lib/Analysis/ValueTracking.cpp
4128 ↗(On Diff #39720)

match(B? You have A repeated twice.

This revision is now accepted and ready to land.Nov 10 2015, 2:28 PM
sanjoy added inline comments.Nov 10 2015, 3:32 PM
lib/Analysis/ValueTracking.cpp
4128 ↗(On Diff #39720)

Thanks for catching that!

When re-reading the code, I noticed something else -- the ULT and UGT clauses in isTruePredicate are unused / untested, since we only ever call it with ULE and UGE. Given that, I'm inclined to remove the the unused / untested clauses (in a separate change) -- what do you think?

This revision was automatically updated to reflect the committed changes.
sanjoy added inline comments.Nov 10 2015, 4:20 PM
lib/Analysis/ValueTracking.cpp
4128 ↗(On Diff #39720)

I removed the untested cases in r252676.

Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptFeb 13 2023, 9:08 AM