Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -1731,6 +1731,34 @@ } } + { + // ~A - Min/Max(~A, O) -> Max/Min(A, ~O) - A + // So long as O here is freely invertable, this will be neutral or a win. + Value *LHS, *RHS, *A; + SelectPatternFlavor SPF = matchSelectPattern(Op1, LHS, RHS).Flavor; + if (SelectPatternResult::isMinOrMax(SPF) && match(Op0, m_Not(m_Value(A))) && + (Op0 == LHS || Op0 == RHS)) { + if (Op0 == LHS) + std::swap(LHS, RHS); + if (IsFreeToInvert(LHS, !LHS->hasNUsesOrMore(3))) { + Value *Not = Builder.CreateNot(Op1); + return BinaryOperator::CreateSub(Not, A); + } + } + + // Min/Max(~A, O) - ~A -> A - Max/Min(A, ~O) + SPF = matchSelectPattern(Op0, LHS, RHS).Flavor; + if (SelectPatternResult::isMinOrMax(SPF) && match(Op1, m_Not(m_Value(A))) && + (Op1 == LHS || Op1 == RHS)) { + if (Op1 == LHS) + std::swap(LHS, RHS); + if (IsFreeToInvert(LHS, !LHS->hasNUsesOrMore(3))) { + Value *Not = Builder.CreateNot(Op0); + return BinaryOperator::CreateSub(A, Not); + } + } + } + // Optimize pointer differences into the same array into a size. Consider: // &A[10] - &A[0]: we should compile this to "10". Value *LHSOp, *RHSOp; Index: lib/Transforms/InstCombine/InstCombineInternal.h =================================================================== --- lib/Transforms/InstCombine/InstCombineInternal.h +++ lib/Transforms/InstCombine/InstCombineInternal.h @@ -20,7 +20,6 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetFolder.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/BasicBlock.h" @@ -33,6 +32,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" +#include "llvm/IR/PatternMatch.h" #include "llvm/IR/Use.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" @@ -41,11 +41,14 @@ #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" +#include "llvm/Transforms/Utils/Local.h" #include #include #define DEBUG_TYPE "instcombine" +using namespace llvm::PatternMatch; + namespace llvm { class APInt; @@ -175,6 +178,10 @@ if (isa(BO->getOperand(0)) || isa(BO->getOperand(1))) return WillInvertAllUses; + // Selects with invertable operands are freely invertable + if (match(V, m_Select(m_Value(), m_Not(m_Value()), m_Not(m_Value())))) + return WillInvertAllUses; + return false; } Index: test/Transforms/InstCombine/max-of-nots.ll =================================================================== --- test/Transforms/InstCombine/max-of-nots.ll +++ test/Transforms/InstCombine/max-of-nots.ll @@ -63,12 +63,11 @@ define i8 @umin_not_sub(i8 %x, i8 %y) { ; CHECK-LABEL: @umin_not_sub( -; CHECK-NEXT: [[NX:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[NY:%.*]] = xor i8 [[Y:%.*]], -1 -; CHECK-NEXT: [[CMPXY:%.*]] = icmp ult i8 [[NX]], [[NY]] -; CHECK-NEXT: [[MINXY:%.*]] = select i1 [[CMPXY]], i8 [[NX]], i8 [[NY]] -; CHECK-NEXT: [[SUBX:%.*]] = sub i8 [[NX]], [[MINXY]] -; CHECK-NEXT: [[SUBY:%.*]] = sub i8 [[NY]], [[MINXY]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i8 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Y]] +; CHECK-NEXT: [[MINXY:%.*]] = xor i8 [[TMP2]], -1 +; CHECK-NEXT: [[SUBX:%.*]] = sub i8 [[TMP2]], [[X]] +; CHECK-NEXT: [[SUBY:%.*]] = sub i8 [[TMP2]], [[Y]] ; CHECK-NEXT: call void @extra_use(i8 [[SUBX]]) ; CHECK-NEXT: call void @extra_use(i8 [[SUBY]]) ; CHECK-NEXT: ret i8 [[MINXY]] @@ -86,12 +85,11 @@ define i8 @umin_not_sub_rev(i8 %x, i8 %y) { ; CHECK-LABEL: @umin_not_sub_rev( -; CHECK-NEXT: [[NX:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[NY:%.*]] = xor i8 [[Y:%.*]], -1 -; CHECK-NEXT: [[CMPXY:%.*]] = icmp ult i8 [[NX]], [[NY]] -; CHECK-NEXT: [[MINXY:%.*]] = select i1 [[CMPXY]], i8 [[NX]], i8 [[NY]] -; CHECK-NEXT: [[SUBX:%.*]] = sub i8 [[MINXY]], [[NX]] -; CHECK-NEXT: [[SUBY:%.*]] = sub i8 [[MINXY]], [[NY]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i8 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Y]] +; CHECK-NEXT: [[MINXY:%.*]] = xor i8 [[TMP2]], -1 +; CHECK-NEXT: [[SUBX:%.*]] = sub i8 [[X]], [[TMP2]] +; CHECK-NEXT: [[SUBY:%.*]] = sub i8 [[Y]], [[TMP2]] ; CHECK-NEXT: call void @extra_use(i8 [[SUBX]]) ; CHECK-NEXT: call void @extra_use(i8 [[SUBY]]) ; CHECK-NEXT: ret i8 [[MINXY]] @@ -209,17 +207,15 @@ define void @umin3_not_all_ops_extra_uses_invert_subs(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @umin3_not_all_ops_extra_uses_invert_subs( -; CHECK-NEXT: [[XN:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[YN:%.*]] = xor i8 [[Y:%.*]], -1 -; CHECK-NEXT: [[ZN:%.*]] = xor i8 [[Z:%.*]], -1 -; CHECK-NEXT: [[CMPXZ:%.*]] = icmp ult i8 [[XN]], [[ZN]] -; CHECK-NEXT: [[MINXZ:%.*]] = select i1 [[CMPXZ]], i8 [[XN]], i8 [[ZN]] -; CHECK-NEXT: [[CMPXYZ:%.*]] = icmp ult i8 [[MINXZ]], [[YN]] -; CHECK-NEXT: [[MINXYZ:%.*]] = select i1 [[CMPXYZ]], i8 [[MINXZ]], i8 [[YN]] -; CHECK-NEXT: [[XMIN:%.*]] = sub i8 [[XN]], [[MINXYZ]] -; CHECK-NEXT: [[YMIN:%.*]] = sub i8 [[YN]], [[MINXYZ]] -; CHECK-NEXT: [[ZMIN:%.*]] = sub i8 [[ZN]], [[MINXYZ]] -; CHECK-NEXT: call void @use8(i8 [[MINXYZ]]) +; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i8 [[X:%.*]], [[Z:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Z]] +; CHECK-NEXT: [[TMP3:%.*]] = icmp ugt i8 [[TMP2]], [[Y:%.*]] +; CHECK-NEXT: [[TMP4:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[Y]] +; CHECK-NEXT: [[TMP5:%.*]] = xor i8 [[TMP4]], -1 +; CHECK-NEXT: [[XMIN:%.*]] = sub i8 [[TMP4]], [[X]] +; CHECK-NEXT: [[YMIN:%.*]] = sub i8 [[TMP4]], [[Y]] +; CHECK-NEXT: [[ZMIN:%.*]] = sub i8 [[TMP4]], [[Z]] +; CHECK-NEXT: call void @use8(i8 [[TMP5]]) ; CHECK-NEXT: call void @use8(i8 [[XMIN]]) ; CHECK-NEXT: call void @use8(i8 [[YMIN]]) ; CHECK-NEXT: call void @use8(i8 [[ZMIN]])