Page MenuHomePhabricator

Add micro-optimization for 'icmp slt (or A, B), A' to instsimplify.
ClosedPublic

Authored by nlewycky on Apr 20 2016, 2:24 PM.

Details

Reviewers
majnemer
Summary

Add optimization for 'icmp slt (or A, B), A' and some related idioms based on knowledge of the sign bit for A and B.

No matter what value you OR in to A, the result of (or A, B) is going to be UGE A. When A and B are positive, it's SGE too. If A is negative, OR'ing a value into it can't make it positive, but can increase its value closer to -1, therefore (or A, B) is SGE A. Working through all possible combinations produces this truth table:

A is
+, -, +/-
F  F   F   +    B is
T  F   ?   -
?  F   ?   +/-

The related optimizations are flipping the 'slt' for 'sge' which always NOTs the result (if the result is known), and swapping the LHS and RHS while swapping the comparison predicate.

There are more idioms left to implement (aren't there always!) but I've stopped here because any more would risk becoming unreasonable for reviewers.

Diff Detail

Event Timeline

nlewycky updated this revision to Diff 54418.Apr 20 2016, 2:24 PM
nlewycky updated this revision to Diff 54419.
nlewycky retitled this revision from to Add micro-optimization for 'icmp slt (or A, B), A' to instsimplify..
nlewycky updated this object.
nlewycky set the repository for this revision to rL LLVM.
nlewycky removed rL LLVM as the repository for this revision.
nlewycky added a subscriber: llvm-commits.

Added testcase which I forgot to include the first time.

majnemer added inline comments.
lib/Analysis/InstructionSimplify.cpp
2630–2639

If I understand correctly, you are saying that x|y < x is true if x is negative and y is not negative.
At first blush, this appears to be a specific case of a more general transform: x|y < x is true if x is negative and y has any bits set which are known not to be set in x.

majnemer added inline comments.Apr 20 2016, 2:41 PM
lib/Analysis/InstructionSimplify.cpp
2620

nullptr is preferred.

2622–2623

This can be:

if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS))))
2643–2644

Ditto.

nlewycky updated this revision to Diff 54431.Apr 20 2016, 3:04 PM

Move the m_c_Op pattern matches out of ValueTracking.cpp and into PatternMatch.h. Reuse m_c_Or to simplify the new logic in InstructionSimplify.

Swap out a 0 for nullptr when used to initialize a pointer.

nlewycky marked 3 inline comments as done.Apr 20 2016, 3:06 PM
nlewycky added inline comments.
lib/Analysis/InstructionSimplify.cpp
2630–2639

Counterexample "(-2|1)<-2" --> "-1<-2" --> "false".

To sanity-check, I wrote a program that enumerates A=[-128..127], B=[-128..127] and emits all the results. That's what convinced me that only the sign bit matters.

majnemer accepted this revision.Apr 20 2016, 5:48 PM
majnemer added a reviewer: majnemer.

LGTM

This revision is now accepted and ready to land.Apr 20 2016, 5:48 PM
Eugene.Zelenko added a subscriber: Eugene.Zelenko.

Committed in r266939.