Skip to content

Commit d67165c

Browse files
annamthomasannamthomas
committedJun 23, 2017
[InstCombine] Recognize and simplify three way comparison idioms
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.) We currently recognize one idiom on signed integer compare. In the future, we plan to recognize and simplify other comparison idioms on other signed/unsigned datatypes such as floats, vectors etc. This is a resurrection of Philip Reames' original patch: https://reviews.llvm.org/D19452 Reviewers: majnemer, apilipenko, reames, sanjoy, mkazantsev Reviewed by: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34278 llvm-svn: 306100
1 parent 78811c2 commit d67165c

File tree

3 files changed

+498
-4
lines changed

3 files changed

+498
-4
lines changed
 

‎llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Lines changed: 92 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2434,6 +2434,77 @@ Instruction *InstCombiner::foldICmpAddConstant(ICmpInst &Cmp,
24342434
return nullptr;
24352435
}
24362436

2437+
bool InstCombiner::matchThreeWayIntCompare(SelectInst *SI, Value *&LHS,
2438+
Value *&RHS, ConstantInt *&Less,
2439+
ConstantInt *&Equal,
2440+
ConstantInt *&Greater) {
2441+
// TODO: Generalize this to work with other comparison idioms or ensure
2442+
// they get canonicalized into this form.
2443+
2444+
// select i1 (a == b), i32 Equal, i32 (select i1 (a < b), i32 Less, i32
2445+
// Greater), where Equal, Less and Greater are placeholders for any three
2446+
// constants.
2447+
ICmpInst::Predicate PredA, PredB;
2448+
if (match(SI->getTrueValue(), m_ConstantInt(Equal)) &&
2449+
match(SI->getCondition(), m_ICmp(PredA, m_Value(LHS), m_Value(RHS))) &&
2450+
PredA == ICmpInst::ICMP_EQ &&
2451+
match(SI->getFalseValue(),
2452+
m_Select(m_ICmp(PredB, m_Specific(LHS), m_Specific(RHS)),
2453+
m_ConstantInt(Less), m_ConstantInt(Greater))) &&
2454+
PredB == ICmpInst::ICMP_SLT) {
2455+
return true;
2456+
}
2457+
return false;
2458+
}
2459+
2460+
Instruction *InstCombiner::foldICmpSelectConstant(ICmpInst &Cmp,
2461+
Instruction *Select,
2462+
ConstantInt *C) {
2463+
2464+
assert(C && "Cmp RHS should be a constant int!");
2465+
// If we're testing a constant value against the result of a three way
2466+
// comparison, the result can be expressed directly in terms of the
2467+
// original values being compared. Note: We could possibly be more
2468+
// aggressive here and remove the hasOneUse test. The original select is
2469+
// really likely to simplify or sink when we remove a test of the result.
2470+
Value *OrigLHS, *OrigRHS;
2471+
ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
2472+
if (Cmp.hasOneUse() &&
2473+
matchThreeWayIntCompare(cast<SelectInst>(Select), OrigLHS, OrigRHS,
2474+
C1LessThan, C2Equal, C3GreaterThan)) {
2475+
assert(C1LessThan && C2Equal && C3GreaterThan);
2476+
2477+
bool TrueWhenLessThan =
2478+
ConstantExpr::getCompare(Cmp.getPredicate(), C1LessThan, C)
2479+
->isAllOnesValue();
2480+
bool TrueWhenEqual =
2481+
ConstantExpr::getCompare(Cmp.getPredicate(), C2Equal, C)
2482+
->isAllOnesValue();
2483+
bool TrueWhenGreaterThan =
2484+
ConstantExpr::getCompare(Cmp.getPredicate(), C3GreaterThan, C)
2485+
->isAllOnesValue();
2486+
2487+
// This generates the new instruction that will replace the original Cmp
2488+
// Instruction. Instead of enumerating the various combinations when
2489+
// TrueWhenLessThan, TrueWhenEqual and TrueWhenGreaterThan are true versus
2490+
// false, we rely on chaining of ORs and future passes of InstCombine to
2491+
// simplify the OR further (i.e. a s< b || a == b becomes a s<= b).
2492+
2493+
// When none of the three constants satisfy the predicate for the RHS (C),
2494+
// the entire original Cmp can be simplified to a false.
2495+
Value *Cond = Builder->getFalse();
2496+
if (TrueWhenLessThan)
2497+
Cond = Builder->CreateOr(Cond, Builder->CreateICmp(ICmpInst::ICMP_SLT, OrigLHS, OrigRHS));
2498+
if (TrueWhenEqual)
2499+
Cond = Builder->CreateOr(Cond, Builder->CreateICmp(ICmpInst::ICMP_EQ, OrigLHS, OrigRHS));
2500+
if (TrueWhenGreaterThan)
2501+
Cond = Builder->CreateOr(Cond, Builder->CreateICmp(ICmpInst::ICMP_SGT, OrigLHS, OrigRHS));
2502+
2503+
return replaceInstUsesWith(Cmp, Cond);
2504+
}
2505+
return nullptr;
2506+
}
2507+
24372508
/// Try to fold integer comparisons with a constant operand: icmp Pred X, C
24382509
/// where X is some kind of instruction.
24392510
Instruction *InstCombiner::foldICmpInstWithConstant(ICmpInst &Cmp) {
@@ -2493,11 +2564,28 @@ Instruction *InstCombiner::foldICmpInstWithConstant(ICmpInst &Cmp) {
24932564
return I;
24942565
}
24952566

2567+
// Match against CmpInst LHS being instructions other than binary operators.
24962568
Instruction *LHSI;
2497-
if (match(Cmp.getOperand(0), m_Instruction(LHSI)) &&
2498-
LHSI->getOpcode() == Instruction::Trunc)
2499-
if (Instruction *I = foldICmpTruncConstant(Cmp, LHSI, C))
2500-
return I;
2569+
if (match(Cmp.getOperand(0), m_Instruction(LHSI))) {
2570+
switch (LHSI->getOpcode()) {
2571+
case Instruction::Select:
2572+
{
2573+
// For now, we only support constant integers while folding the
2574+
// ICMP(SELECT)) pattern. We can extend this to support vector of integers
2575+
// similar to the cases handled by binary ops above.
2576+
if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
2577+
if (Instruction *I = foldICmpSelectConstant(Cmp, LHSI, ConstRHS))
2578+
return I;
2579+
break;
2580+
}
2581+
case Instruction::Trunc:
2582+
if (Instruction *I = foldICmpTruncConstant(Cmp, LHSI, C))
2583+
return I;
2584+
break;
2585+
default:
2586+
break;
2587+
}
2588+
}
25012589

25022590
if (Instruction *I = foldICmpIntrinsicWithConstant(Cmp, C))
25032591
return I;

‎llvm/lib/Transforms/InstCombine/InstCombineInternal.h

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -603,6 +603,15 @@ class LLVM_LIBRARY_VISIBILITY InstCombiner
603603
Instruction::BinaryOps, Value *, Value *, Value *,
604604
Value *);
605605

606+
/// Match a select chain which produces one of three values based on whether
607+
/// the LHS is less than, equal to, or greater than RHS respectively.
608+
/// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
609+
/// Equal and Greater values are saved in the matching process and returned to
610+
/// the caller.
611+
bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
612+
ConstantInt *&Less, ConstantInt *&Equal,
613+
ConstantInt *&Greater);
614+
606615
/// \brief Attempts to replace V with a simpler value based on the demanded
607616
/// bits.
608617
Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
@@ -680,6 +689,8 @@ class LLVM_LIBRARY_VISIBILITY InstCombiner
680689
Instruction *foldICmpBinOp(ICmpInst &Cmp);
681690
Instruction *foldICmpEquality(ICmpInst &Cmp);
682691

692+
Instruction *foldICmpSelectConstant(ICmpInst &Cmp, Instruction *Select,
693+
ConstantInt *C);
683694
Instruction *foldICmpTruncConstant(ICmpInst &Cmp, Instruction *Trunc,
684695
const APInt *C);
685696
Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,

0 commit comments

Comments
 (0)