This is an archive of the discontinued LLVM Phabricator instance.

[Bug 24848] Use range metadata to constant fold comparisons between two values
ClosedPublic

Authored by chenli on Sep 25 2015, 1:17 PM.

Details

Summary

This is the second part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848.

If both operands of a comparison have range metadata, they should be used to constant fold the comparison.

Diff Detail

Event Timeline

chenli updated this revision to Diff 35762.Sep 25 2015, 1:17 PM
chenli retitled this revision from to [Bug 24848] Use range metadata to constant fold comparisons between two values.
chenli updated this object.
chenli added reviewers: sanjoy, hfinkel.
chenli added a subscriber: llvm-commits.
hfinkel accepted this revision.Sep 25 2015, 4:55 PM
hfinkel edited edge metadata.

Minor request below, otherwise, LGTM.

lib/Analysis/InstructionSimplify.cpp
2422

Move this below the check for Satisfied_CR.contains. No need to construct an object we'll never use.

This revision is now accepted and ready to land.Sep 25 2015, 4:55 PM
sanjoy added inline comments.Sep 25 2015, 5:06 PM
lib/Analysis/InstructionSimplify.cpp
2427

I don't think this second is correct. makeSatisfiedRegion returns the range of LHS values that is *guaranteed* to satisfy the predicate "Pred RHS". So if RHS's range is [2, 5) and Pred is ULT, then Satisfied_CR is [0, 2). InversedSatisfied_CR will then be [2, 0) (i.e. all integers unsigned greater than or equal to 2) and so you'll fold the equality to false if LHS_CR is [3,4), even though in that case there is a value of LHS = 3 for which the equality is true.

I think for the negative check you need to do InverseAllowed_CR.contains(LHS_CR) where InverseAllowed_CR is the inverse of what is returned by makeAllowedRegion.

hfinkel added inline comments.Sep 25 2015, 5:48 PM
lib/Analysis/InstructionSimplify.cpp
2427

I don't understand your example. If we have:

x <u 2

then Satisfied_CR is indeed [0, 2), and the inverse (x >=u 2) should indeed be [2, 0). But if LHS_CR is [3, 4), then the original predicate is false, because 3 is not less than 2.

sanjoy added inline comments.Sep 25 2015, 6:01 PM
lib/Analysis/InstructionSimplify.cpp
2427

I'm talking about a case where X u< Y and X's range is [3, 4), and Y's range is [2, 5). Then the code as it is now will fold the condition to false (because [3,4) is contained in [2, 0)) when it could be true if X is 3 and Y is 4.

This code is basically checking no X is *guaranteed* to satisfy Pred Y, i.e. there is no such X such that X Pred Y is true for *all* Y, when it should be trying to prove that there is no such X such that X Pred Y for *some* Y.

hfinkel added inline comments.Sep 25 2015, 6:30 PM
lib/Analysis/InstructionSimplify.cpp
2427

My thought had been that in this case, we have X <u Y, so the Satisfied_CR is [0, 2), and the inverse X >=u Y, has InversedSatisfied_CR of [4, 0), because only if X is >= 4 do we know it satisfies the inequality for all possible values of Y. If X is [3, 4), then it is not contained in either set.

sanjoy added inline comments.Sep 25 2015, 6:34 PM
lib/Analysis/InstructionSimplify.cpp
2427

I was misreading the code. :/ Sorry for the noise. What's here is fine.

chenli added inline comments.Sep 25 2015, 8:24 PM
lib/Analysis/InstructionSimplify.cpp
2427

@hfinkel - Thanks for explaining that for me :)

chenli closed this revision.Sep 25 2015, 8:28 PM