This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Add a new predicate: isKnownNonEqual()
ClosedPublic

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

Details

Summary

isKnownNonEqual(A, B) returns true if it can be determined that A != B.

At the moment it only knows one fact, that a non-wrapping add of nonzero to a value cannot be that value:

A + B != A [where B != 0, addition is nsw or nuw]

Diff Detail

Repository
rL LLVM

Event Timeline

jmolloy updated this revision to Diff 34545.Sep 11 2015, 5:55 AM
jmolloy retitled this revision from to [ValueTracking] Add a new predicate: isKnownNonEqual().
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.
jmolloy updated this revision to Diff 34546.Sep 11 2015, 5:58 AM
sanjoy added a subscriber: sanjoy.Sep 11 2015, 9:49 AM

I don't think you need to check for no-wrap -- a non-zero B should be sufficient to prove A + B != A.

hfinkel edited edge metadata.Sep 22 2015, 1:55 PM

I like the idea of this function, but I'm somewhat nervous of adding such a generic facility with such a limited implementation. It would make me feel much better if it also had the following check: call computeKnownBits on V1 and V2, and return true if any of the bits known to be 1 in one value are known to be zero in the other. That would naturally leverage much more of the existing infrastructure.

Also, I assume you're planning on soon using this somewhere?

...

Also, I assume you're planning on soon using this somewhere?

You can ignore this; I see you're using it in D12801.

...

Also, I assume you're planning on soon using this somewhere?

You can ignore this; I see you're using it in D12801.

Err... D12802.

jmolloy updated this revision to Diff 36220.Oct 1 2015, 4:11 AM
jmolloy edited edge metadata.

Hi Hal, Sanjoy,

Thanks for the review. I've addressed both your comments, and:

  • Hooked this up to InstSimplify - it turned out Hal's idea about computeKnownBits wasn't known to it, so it learned something.
  • Switched to using a lit test, now instsimplify uses this function.
sanjoy added a comment.Oct 9 2015, 2:03 AM

Some minor comments inline.

lib/Analysis/ValueTracking.cpp
1938

Isn't this checking V1 == V2 + X? They're both equivalent though, so the answer is still okay, just mildly confusing. :)

1941

Why not use something from PatternMatch.h here, like m_Add?

1965

I'd use auto * here.

Also can this be relaxed to allow everything computeKnownBits can handle (i.e. allow pointers and vectors too)?

jmolloy updated this revision to Diff 37255.Oct 13 2015, 8:49 AM

Hi Sanjoy,

Thanks for the comments. Switching to PatternMatch was a good idea - the code is substantially more readable!

All comments acted upon.

Cheers,

James

Hi Sanjoy,

Do you have any comments on this?

Cheers,

James

sanjoy accepted this revision.Oct 22 2015, 2:10 AM
sanjoy added a reviewer: sanjoy.

Sorry for the delay, lgtm.

This revision is now accepted and ready to land.Oct 22 2015, 2:10 AM
jmolloy closed this revision.Oct 26 2015, 3:29 AM