Page MenuHomePhabricator

[instcombine] recognize three way comparison idioms
AbandonedPublic

Authored by reames on Apr 22 2016, 8:37 PM.

Details

Summary

Many languages have a three way comparison idiom where comparing two values produces not a boolean, but a tri-state value. Typical values (e.g. as used in the lcmp/fcmp bytecodes from Java) are -1 for less than, 0 for equality, and +1 for greater than.

We actually do a great job already of converting three way comparisons into binary comparisons when the result produced has one a single use. Unfortunately, such values can have more than one use, and in that case, our existing optimizations break down.

The patch adds a peephole which converts a three-way compare + test idiom into a binary comparison on the original inputs. It focused on replacing the test on the result of the three way compare and does nothing about removing the three way compare itself. That's left to other optimizations (which do actually kick in commonly.)

I specifically only matching a single select idiom at the moment. We don't need to worry about phis since we canonicalize selects into phis. We should handle (or canonicalize) a larger family of select idioms, but I wanted to start small and iterate. Similarly, the current patch only adds support for signed compare idioms. Future work could add unsigned idioms, and possibly floating point idioms. I did try to generalize over the actual values returns by the three way compare so that the transform might kick on more than just the idiomatic three way comparison.

Diff Detail

Event Timeline

reames updated this revision to Diff 54760.Apr 22 2016, 8:37 PM
reames retitled this revision from to [instcombine] recognize three way comparison idioms.
reames updated this object.
reames added reviewers: majnemer, sanjoy, igor-laevsky.
reames added a subscriber: llvm-commits.
sanjoy requested changes to this revision.May 4 2016, 2:18 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Transforms/InstCombine/InstCombineCompares.cpp
2173

Start with uppercase.

2175

I'd put this in InstCombineInternal.h, that'll make it more likely that this gets used in other parts of IC.

2183

Can you please replace -1, 0 and 1 with Less, Equal, and Greater in the comments, so that is is more in tune with the code.

2191

Minor, but I'd put the check on PredA right after you matched it, and the check on PredB after you matched it; since they're logically part of matching operation.

2210

I'd avoid the explicit combinatorial logic, but instead have:

Value *Cond = getConstant(false);
if (TrueWhenLessThan)
  Cond = CreateOr(Cond, CreateICmp(SLT, OrigLHS, OrigRHS))
if (TrueWhenEqual)
  Cond = CreateOr(Cond, CreateICmp(EQ, OrigLHS, OrigRHS))
if (TrueWhenGreater)
  Cond = CreateOr(Cond, CreateICmp(SGT, OrigLHS, OrigRHS))

And leave the rest of instcombine to combine, e.g., a s< b || a == b
into a s<= b.

2238

s/obvious/obviously/ or drop "obvious"

This revision now requires changes to proceed.May 4 2016, 2:18 PM
anna added a subscriber: anna.Jun 16 2017, 6:58 AM

This change is now resurrected as https://reviews.llvm.org/D34278

reames abandoned this revision.Aug 16 2017, 3:15 PM