From b109b5c148ff60ea8f1105aadb2c31761ca3d445 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 21 Dec 2009 06:03:05 +0000 Subject: [PATCH] give instcombine some helper functions for matching MIN and MAX, and implement some optimizations for MIN(MIN()) and MAX(MAX()) and MIN(MAX()) etc. This substantially improves the code in PR5822 but doesn't kick in much elsewhere. 2 max's were optimized in pairlocalalign and one in smg2000. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91814 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Scalar/InstructionCombining.cpp | 128 ++++++++++++++++-- test/Transforms/InstCombine/select.ll | 40 ++++++ 2 files changed, 158 insertions(+), 10 deletions(-) diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index 9033877b454..ca60219b909 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -75,6 +75,15 @@ STATISTIC(NumDeadInst , "Number of dead inst eliminated"); STATISTIC(NumDeadStore, "Number of dead stores eliminated"); STATISTIC(NumSunkInst , "Number of instructions sunk"); +/// SelectPatternFlavor - We can match a variety of different patterns for +/// select operations. +enum SelectPatternFlavor { + SPF_UNKNOWN = 0, + SPF_SMIN, SPF_UMIN, + SPF_SMAX, SPF_UMAX + //SPF_ABS - TODO. +}; + namespace { /// InstCombineWorklist - This is the worklist management logic for /// InstCombine. @@ -281,6 +290,9 @@ namespace { Instruction *FoldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI); Instruction *FoldSelectIntoOp(SelectInst &SI, Value*, Value*); + Instruction *FoldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, + Value *A, Value *B, Instruction &Outer, + SelectPatternFlavor SPF2, Value *C); Instruction *visitSelectInst(SelectInst &SI); Instruction *visitSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI); Instruction *visitCallInst(CallInst &CI); @@ -649,6 +661,57 @@ static inline Value *dyn_castFNegVal(Value *V) { return 0; } +/// MatchSelectPattern - Pattern match integer [SU]MIN, [SU]MAX, and ABS idioms, +/// returning the kind and providing the out parameter results if we +/// successfully match. +static SelectPatternFlavor +MatchSelectPattern(Value *V, Value *&LHS, Value *&RHS) { + SelectInst *SI = dyn_cast(V); + if (SI == 0) return SPF_UNKNOWN; + + ICmpInst *ICI = dyn_cast(SI->getCondition()); + if (ICI == 0) return SPF_UNKNOWN; + + LHS = ICI->getOperand(0); + RHS = ICI->getOperand(1); + + // (icmp X, Y) ? X : Y + if (SI->getTrueValue() == ICI->getOperand(0) && + SI->getFalseValue() == ICI->getOperand(1)) { + switch (ICI->getPredicate()) { + default: return SPF_UNKNOWN; // Equality. + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_UGE: return SPF_UMAX; + case ICmpInst::ICMP_SGT: + case ICmpInst::ICMP_SGE: return SPF_SMAX; + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_ULE: return SPF_UMIN; + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_SLE: return SPF_SMIN; + } + } + + // (icmp X, Y) ? Y : X + if (SI->getTrueValue() == ICI->getOperand(1) && + SI->getFalseValue() == ICI->getOperand(0)) { + switch (ICI->getPredicate()) { + default: return SPF_UNKNOWN; // Equality. + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_UGE: return SPF_UMIN; + case ICmpInst::ICMP_SGT: + case ICmpInst::ICMP_SGE: return SPF_SMIN; + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_ULE: return SPF_UMAX; + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_SLE: return SPF_SMAX; + } + } + + // TODO: (X > 4) ? X : 5 --> (X >= 5) ? X : 5 --> MAX(X, 5) + + return SPF_UNKNOWN; +} + /// isFreeToInvert - Return true if the specified value is free to invert (apply /// ~ to). This happens in cases where the ~ can be eliminated. static inline bool isFreeToInvert(Value *V) { @@ -733,12 +796,12 @@ static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { APInt MulExt = LHSExt * RHSExt; - if (sign) { - APInt Min = APInt::getSignedMinValue(W).sext(W * 2); - APInt Max = APInt::getSignedMaxValue(W).sext(W * 2); - return MulExt.slt(Min) || MulExt.sgt(Max); - } else + if (!sign) return MulExt.ugt(APInt::getLowBitsSet(W * 2, W)); + + APInt Min = APInt::getSignedMinValue(W).sext(W * 2); + APInt Max = APInt::getSignedMaxValue(W).sext(W * 2); + return MulExt.slt(Min) || MulExt.sgt(Max); } @@ -9479,9 +9542,6 @@ Instruction *InstCombiner::visitSelectInstWithICmp(SelectInst &SI, return ReplaceInstUsesWith(SI, TrueVal); /// NOTE: if we wanted to, this is where to detect integer MIN/MAX } - - /// NOTE: if we wanted to, this is where to detect integer ABS - return Changed ? &SI : 0; } @@ -9523,6 +9583,35 @@ static bool CanSelectOperandBeMappingIntoPredBlock(const Value *V, return false; } +/// FoldSPFofSPF - We have an SPF (e.g. a min or max) of an SPF of the form: +/// SPF2(SPF1(A, B), C) +Instruction *InstCombiner::FoldSPFofSPF(Instruction *Inner, + SelectPatternFlavor SPF1, + Value *A, Value *B, + Instruction &Outer, + SelectPatternFlavor SPF2, Value *C) { + if (C == A || C == B) { + // MAX(MAX(A, B), B) -> MAX(A, B) + // MIN(MIN(a, b), a) -> MIN(a, b) + if (SPF1 == SPF2) + return ReplaceInstUsesWith(Outer, Inner); + + // MAX(MIN(a, b), a) -> a + // MIN(MAX(a, b), a) -> a + if (SPF1 == SPF_SMIN && SPF2 == SPF_SMAX || + SPF1 == SPF_SMAX && SPF2 == SPF_SMIN || + SPF1 == SPF_UMIN && SPF2 == SPF_UMAX || + SPF1 == SPF_UMAX && SPF2 == SPF_UMIN) + return ReplaceInstUsesWith(Outer, C); + } + + // TODO: MIN(MIN(A, 23), 97) + return 0; +} + + + + Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { Value *CondVal = SI.getCondition(); Value *TrueVal = SI.getTrueValue(); @@ -9729,9 +9818,28 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) { // See if we can fold the select into one of our operands. if (SI.getType()->isInteger()) { - Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal); - if (FoldI) + if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal)) return FoldI; + + // MAX(MAX(a, b), a) -> MAX(a, b) + // MIN(MIN(a, b), a) -> MIN(a, b) + // MAX(MIN(a, b), a) -> a + // MIN(MAX(a, b), a) -> a + Value *LHS, *RHS, *LHS2, *RHS2; + if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) { + if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2)) + if (Instruction *R = FoldSPFofSPF(cast(LHS),SPF2,LHS2,RHS2, + SI, SPF, RHS)) + return R; + if (SelectPatternFlavor SPF2 = MatchSelectPattern(RHS, LHS2, RHS2)) + if (Instruction *R = FoldSPFofSPF(cast(RHS),SPF2,LHS2,RHS2, + SI, SPF, LHS)) + return R; + } + + // TODO. + // ABS(-X) -> ABS(X) + // ABS(ABS(X)) -> ABS(X) } // See if we can fold the select into a phi node if the condition is a select. diff --git a/test/Transforms/InstCombine/select.ll b/test/Transforms/InstCombine/select.ll index 565cfa57ff8..7c597007c31 100644 --- a/test/Transforms/InstCombine/select.ll +++ b/test/Transforms/InstCombine/select.ll @@ -382,3 +382,43 @@ next: ; CHECK-NEXT: ret i32 %a } + +define i32 @test30(i32 %x, i32 %y) { + %cmp = icmp sgt i32 %x, %y + %cond = select i1 %cmp, i32 %x, i32 %y + %cmp5 = icmp sgt i32 %cond, %x + %retval = select i1 %cmp5, i32 %cond, i32 %x + ret i32 %retval +} + +define i32 @test31(i32 %x, i32 %y) { + %cmp = icmp ugt i32 %x, %y + %cond = select i1 %cmp, i32 %x, i32 %y + %cmp5 = icmp ugt i32 %cond, %x + %retval = select i1 %cmp5, i32 %cond, i32 %x + ret i32 %retval +} + +define i32 @test32(i32 %x, i32 %y) { + %cmp = icmp sgt i32 %x, %y + %cond = select i1 %cmp, i32 %y, i32 %x + %cmp5 = icmp sgt i32 %cond, %x + %retval = select i1 %cmp5, i32 %x, i32 %cond + ret i32 %retval +} + +define i32 @test33(i32 %x, i32 %y) { + %cmp = icmp sgt i32 %x, %y + %cond = select i1 %cmp, i32 %y, i32 %x + %cmp5 = icmp sgt i32 %cond, %x + %retval = select i1 %cmp5, i32 %cond, i32 %x + ret i32 %retval +} + +define i32 @test34(i32 %x, i32 %y) { + %cmp = icmp sgt i32 %x, %y + %cond = select i1 %cmp, i32 %x, i32 %y + %cmp5 = icmp sgt i32 %cond, %x + %retval = select i1 %cmp5, i32 %x, i32 %cond + ret i32 %retval +} -- 2.34.1