Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -22,30 +22,12 @@ #define DEBUG_TYPE "instcombine" -/// 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) { - // ~(~(X)) -> X. - if (BinaryOperator::isNot(V)) - return true; - - // Constants can be considered to be not'ed values. - if (isa(V)) - return true; - - // Compares can be inverted if they have a single use. - if (CmpInst *CI = dyn_cast(V)) - return CI->hasOneUse(); - - return false; -} - static inline Value *dyn_castNotVal(Value *V) { // If this is not(not(x)) don't return that this is a not: we want the two // not's to be folded first. if (BinaryOperator::isNot(V)) { Value *Operand = BinaryOperator::getNotArgument(V); - if (!isFreeToInvert(Operand)) + if (!IsFreeToInvert(Operand, Operand->hasOneUse())) return Operand; } @@ -2585,8 +2567,10 @@ // ~(X & Y) --> (~X | ~Y) - De Morgan's Law // ~(X | Y) === (~X & ~Y) - De Morgan's Law - if (isFreeToInvert(Op0I->getOperand(0)) && - isFreeToInvert(Op0I->getOperand(1))) { + if (IsFreeToInvert(Op0I->getOperand(0), + Op0I->getOperand(0)->hasOneUse()) && + IsFreeToInvert(Op0I->getOperand(1), + Op0I->getOperand(1)->hasOneUse())) { Value *NotX = Builder->CreateNot(Op0I->getOperand(0), "notlhs"); Value *NotY = Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h @@ -80,6 +80,36 @@ return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1)); } +/// \brief Return true if the specified value is free to invert (apply ~ to). +/// This happens in cases where the ~ can be eliminated. If WillInvertAllUses +/// is true, work under the assumption that the caller intends to remove all +/// uses of V and only keep uses of ~V. +/// +static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) { + // ~(~(X)) -> X. + if (BinaryOperator::isNot(V)) + return true; + + // Constants can be considered to be not'ed values. + if (isa(V)) + return true; + + // Compares can be inverted if all of their uses are being modified to use the + // ~V. + if (isa(V)) + return WillInvertAllUses; + + // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1 + // - Constant) - A` if we are willing to invert all of the uses. + if (BinaryOperator *BO = dyn_cast(V)) + if (BO->getOpcode() == Instruction::Add || + BO->getOpcode() == Instruction::Sub) + if (isa(BO->getOperand(0)) || isa(BO->getOperand(1))) + return WillInvertAllUses; + + return false; +} + /// \brief An IRBuilder inserter that adds new instructions to the instcombine /// worklist. class LLVM_LIBRARY_VISIBILITY InstCombineIRInserter Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -1145,12 +1145,14 @@ if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal)) return FoldI; + Value *LHS, *RHS, *LHS2, *RHS2; + SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS); + // 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 (SPF) { if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2)) if (Instruction *R = FoldSPFofSPF(cast(LHS),SPF2,LHS2,RHS2, SI, SPF, RHS)) @@ -1161,6 +1163,33 @@ return R; } + // MAX(~a, ~b) -> ~MIN(a, b) + if (SPF == SPF_SMAX || SPF == SPF_UMAX) { + if (IsFreeToInvert(LHS, LHS->hasNUses(2)) && + IsFreeToInvert(RHS, RHS->hasNUses(2))) { + + // This transform adds a xor operation and that extra cost needs to be + // justified. We look for simplifications that will result from + // applying this rule: + + bool Profitable = + (LHS->hasNUses(2) && match(LHS, m_Not(m_Value()))) || + (RHS->hasNUses(2) && match(RHS, m_Not(m_Value()))) || + (SI.hasOneUse() && match(*SI.user_begin(), m_Not(m_Value()))); + + if (Profitable) { + Value *NewLHS = Builder->CreateNot(LHS); + Value *NewRHS = Builder->CreateNot(RHS); + Value *NewCmp = SPF == SPF_SMAX + ? Builder->CreateICmpSLT(NewLHS, NewRHS) + : Builder->CreateICmpULT(NewLHS, NewRHS); + Value *NewSI = + Builder->CreateNot(Builder->CreateSelect(NewCmp, NewLHS, NewRHS)); + return ReplaceInstUsesWith(SI, NewSI); + } + } + } + // TODO. // ABS(-X) -> ABS(X) } Index: llvm/trunk/test/Transforms/InstCombine/max-of-nots.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/max-of-nots.ll +++ llvm/trunk/test/Transforms/InstCombine/max-of-nots.ll @@ -0,0 +1,68 @@ +; RUN: opt -S -instcombine < %s | FileCheck %s + +define i32 @compute_min_2(i32 %x, i32 %y) { +; CHECK-LABEL: compute_min_2 + entry: + %not_x = sub i32 -1, %x + %not_y = sub i32 -1, %y + %cmp = icmp sgt i32 %not_x, %not_y + %not_min = select i1 %cmp, i32 %not_x, i32 %not_y + %min = sub i32 -1, %not_min + ret i32 %min + +; CHECK: %0 = icmp slt i32 %x, %y +; CHECK-NEXT: %1 = select i1 %0, i32 %x, i32 %y +; CHECK-NEXT: ret i32 %1 +} + +define i32 @compute_min_3(i32 %x, i32 %y, i32 %z) { +; CHECK-LABEL: compute_min_3 + entry: + %not_x = sub i32 -1, %x + %not_y = sub i32 -1, %y + %not_z = sub i32 -1, %z + %cmp_1 = icmp sgt i32 %not_x, %not_y + %not_min_1 = select i1 %cmp_1, i32 %not_x, i32 %not_y + %cmp_2 = icmp sgt i32 %not_min_1, %not_z + %not_min_2 = select i1 %cmp_2, i32 %not_min_1, i32 %not_z + %min = sub i32 -1, %not_min_2 + ret i32 %min + +; CHECK: %0 = icmp slt i32 %x, %y +; CHECK-NEXT: %1 = select i1 %0, i32 %x, i32 %y +; CHECK-NEXT: %2 = icmp slt i32 %1, %z +; CHECK-NEXT: %3 = select i1 %2, i32 %1, i32 %z +; CHECK-NEXT: ret i32 %3 +} + +define i32 @compute_min_arithmetic(i32 %x, i32 %y) { +; CHECK-LABEL: compute_min_arithmetic + entry: + %not_value = sub i32 3, %x + %not_y = sub i32 -1, %y + %cmp = icmp sgt i32 %not_value, %not_y + %not_min = select i1 %cmp, i32 %not_value, i32 %not_y + ret i32 %not_min + +; CHECK: %0 = add i32 %x, -4 +; CHECK-NEXT: %1 = icmp slt i32 %0, %y +; CHECK-NEXT: %2 = select i1 %1, i32 %0, i32 %y +; CHECK-NEXT: %3 = xor i32 %2, -1 +; CHECK-NEXT: ret i32 %3 +} + +declare void @fake_use(i32) + +define i32 @compute_min_pessimization(i32 %x, i32 %y) { +; CHECK-LABEL: compute_min_pessimization + entry: + %not_value = sub i32 3, %x + call void @fake_use(i32 %not_value) + %not_y = sub i32 -1, %y + %cmp = icmp sgt i32 %not_value, %not_y +; CHECK: %not_value = sub i32 3, %x +; CHECK: %cmp = icmp sgt i32 %not_value, %not_y + %not_min = select i1 %cmp, i32 %not_value, i32 %not_y + %min = sub i32 -1, %not_min + ret i32 %min +}