From 37bf92b5238434b00fde79347ba5336e7554e562 Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Wed, 22 Dec 2010 13:36:08 +0000 Subject: [PATCH] Add a generic expansion transform: A op (B op' C) -> (A op B) op' (A op C) if both A op B and A op C simplify. This fires fairly often but doesn't make that much difference. On gcc-as-one-file it removes two "and"s and turns one branch into a select. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122399 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombine.h | 11 +- .../InstCombine/InstCombineAddSub.cpp | 14 +- .../InstCombine/InstCombineAndOrXor.cpp | 15 +- .../InstCombine/InstCombineMulDivRem.cpp | 3 + .../InstCombine/InstructionCombining.cpp | 168 ++++++++++++------ .../InstCombine/2010-11-23-Distributed.ll | 16 +- 6 files changed, 154 insertions(+), 73 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombine.h b/lib/Transforms/InstCombine/InstCombine.h index f89ea508d50..3a58708166d 100644 --- a/lib/Transforms/InstCombine/InstCombine.h +++ b/lib/Transforms/InstCombine/InstCombine.h @@ -290,11 +290,12 @@ private: /// operators which are associative or commutative. bool SimplifyAssociativeOrCommutative(BinaryOperator &I); - /// SimplifyByFactorizing - This tries to simplify binary operations which - /// some other binary operation distributes over by factorizing out a common - /// term (eg "(A*B)+(A*C)" -> "A*(B+C)"). Returns the simplified value, or - /// null if no simplification was performed. - Instruction *SimplifyByFactorizing(BinaryOperator &I); + /// SimplifyUsingDistributiveLaws - This tries to simplify binary operations + /// which some other binary operation distributes over either by factorizing + /// out common terms (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this + /// results in simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is + /// a win). Returns the simplified value, or null if it didn't simplify. + Value *SimplifyUsingDistributiveLaws(BinaryOperator &I); /// SimplifyDemandedUseBits - Attempts to replace V with a simpler value /// based on the demanded bits. diff --git a/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 98d65502017..c4132b2435c 100644 --- a/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -91,9 +91,10 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { I.hasNoUnsignedWrap(), TD)) return ReplaceInstUsesWith(I, V); - if (Instruction *NV = SimplifyByFactorizing(I)) // (A*B)+(A*C) -> A*(B+C) - return NV; - + // (A*B)+(A*C) -> A*(B+C) etc + if (Value *V = SimplifyUsingDistributiveLaws(I)) + return ReplaceInstUsesWith(I, V); + if (Constant *RHSC = dyn_cast(RHS)) { if (ConstantInt *CI = dyn_cast(RHSC)) { // X + (signbit) --> X ^ signbit @@ -535,9 +536,10 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { I.hasNoUnsignedWrap(), TD)) return ReplaceInstUsesWith(I, V); - if (Instruction *NV = SimplifyByFactorizing(I)) // (A*B)-(A*C) -> A*(B-C) - return NV; - + // (A*B)-(A*C) -> A*(B-C) etc + if (Value *V = SimplifyUsingDistributiveLaws(I)) + return ReplaceInstUsesWith(I, V); + // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. if (Value *V = dyn_castNegVal(Op1)) { BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 64613b186e8..ee0ce30c5a7 100644 --- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -984,8 +984,9 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) { if (Value *V = SimplifyAndInst(Op0, Op1, TD)) return ReplaceInstUsesWith(I, V); - if (Instruction *NV = SimplifyByFactorizing(I)) // (A|B)&(A|C) -> A|(B&C) - return NV; + // (A|B)&(A|C) -> A|(B&C) etc + if (Value *V = SimplifyUsingDistributiveLaws(I)) + return ReplaceInstUsesWith(I, V); // See if we can simplify any instructions used by the instruction whose sole // purpose is to compute bits we don't care about. @@ -1702,8 +1703,9 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { if (Value *V = SimplifyOrInst(Op0, Op1, TD)) return ReplaceInstUsesWith(I, V); - if (Instruction *NV = SimplifyByFactorizing(I)) // (A&B)|(A&C) -> A&(B|C) - return NV; + // (A&B)|(A&C) -> A&(B|C) etc + if (Value *V = SimplifyUsingDistributiveLaws(I)) + return ReplaceInstUsesWith(I, V); // See if we can simplify any instructions used by the instruction whose sole // purpose is to compute bits we don't care about. @@ -1973,8 +1975,9 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (Value *V = SimplifyXorInst(Op0, Op1, TD)) return ReplaceInstUsesWith(I, V); - if (Instruction *NV = SimplifyByFactorizing(I)) // (A&B)^(A&C) -> A&(B^C) - return NV; + // (A&B)^(A&C) -> A&(B^C) etc + if (Value *V = SimplifyUsingDistributiveLaws(I)) + return ReplaceInstUsesWith(I, V); // See if we can simplify any instructions used by the instruction whose sole // purpose is to compute bits we don't care about. diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index a2fe0cf659e..40b9cfd6870 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -54,6 +54,9 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { if (Value *V = SimplifyMulInst(Op0, Op1, TD)) return ReplaceInstUsesWith(I, V); + if (Value *V = SimplifyUsingDistributiveLaws(I)) + return ReplaceInstUsesWith(I, V); + // Simplify mul instructions with a constant RHS. if (Constant *Op1C = dyn_cast(Op1)) { if (ConstantInt *CI = dyn_cast(Op1C)) { diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index 84d85b73c63..1737be8f2e3 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -58,6 +58,7 @@ STATISTIC(NumCombined , "Number of insts combined"); STATISTIC(NumConstProp, "Number of constant folds"); STATISTIC(NumDeadInst , "Number of dead inst eliminated"); STATISTIC(NumSunkInst , "Number of instructions sunk"); +STATISTIC(NumExpand, "Number of expansions"); STATISTIC(NumFactor , "Number of factorizations"); STATISTIC(NumReassoc , "Number of reassociations"); @@ -294,64 +295,123 @@ static bool RightDistributesOverLeft(Instruction::BinaryOps LOp, return false; } -/// SimplifyByFactorizing - This tries to simplify binary operations which -/// some other binary operation distributes over by factorizing out a common -/// term (eg "(A*B)+(A*C)" -> "A*(B+C)"). Returns the simplified value, or -/// null if no simplification was performed. -Instruction *InstCombiner::SimplifyByFactorizing(BinaryOperator &I) { - BinaryOperator *Op0 = dyn_cast(I.getOperand(0)); - BinaryOperator *Op1 = dyn_cast(I.getOperand(1)); - if (!Op0 || !Op1 || Op0->getOpcode() != Op1->getOpcode()) - return 0; +/// SimplifyUsingDistributiveLaws - This tries to simplify binary operations +/// which some other binary operation distributes over either by factorizing +/// out common terms (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this +/// results in simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is +/// a win). Returns the simplified value, or null if it didn't simplify. +Value *InstCombiner::SimplifyUsingDistributiveLaws(BinaryOperator &I) { + Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); + BinaryOperator *Op0 = dyn_cast(LHS); + BinaryOperator *Op1 = dyn_cast(RHS); + Instruction::BinaryOps TopLevelOpcode = I.getOpcode(); // op + + // Factorization. + if (Op0 && Op1 && Op0->getOpcode() == Op1->getOpcode()) { + // The instruction has the form "(A op' B) op (C op' D)". Try to factorize + // a common term. + Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); + Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); + Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op' + + // Does "X op' Y" always equal "Y op' X"? + bool InnerCommutative = Instruction::isCommutative(InnerOpcode); + + // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"? + if (LeftDistributesOverRight(InnerOpcode, TopLevelOpcode)) + // Does the instruction have the form "(A op' B) op (A op' D)" or, in the + // commutative case, "(A op' B) op (C op' A)"? + if (A == C || (InnerCommutative && A == D)) { + if (A != C) + std::swap(C, D); + // Consider forming "A op' (B op D)". + // If "B op D" simplifies then it can be formed with no cost. + Value *V = SimplifyBinOp(TopLevelOpcode, B, D, TD); + // If "B op D" doesn't simplify then only go on if both of the existing + // operations "A op' B" and "C op' D" will be zapped as no longer used. + if (!V && Op0->hasOneUse() && Op1->hasOneUse()) + V = Builder->CreateBinOp(TopLevelOpcode, B, D, Op1->getName()); + if (V) { + ++NumFactor; + V = Builder->CreateBinOp(InnerOpcode, A, V); + V->takeName(&I); + return V; + } + } - // The instruction has the form "(A op' B) op (C op' D)". - Value *A = Op0->getOperand(0); Value *B = Op0->getOperand(1); - Value *C = Op1->getOperand(0); Value *D = Op1->getOperand(1); - Instruction::BinaryOps OuterOpcode = I.getOpcode(); // op - Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op' - - // Does "X op' Y" always equal "Y op' X"? - bool InnerCommutative = Instruction::isCommutative(InnerOpcode); - - // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"? - if (LeftDistributesOverRight(InnerOpcode, OuterOpcode)) - // Does the instruction have the form "(A op' B) op (A op' D)" or, in the - // commutative case, "(A op' B) op (C op' A)"? - if (A == C || (InnerCommutative && A == D)) { - if (A != C) - std::swap(C, D); - // Consider forming "A op' (B op D)". - // If "B op D" simplifies then it can be formed with no cost. - Value *RHS = SimplifyBinOp(OuterOpcode, B, D, TD); - // If "B op D" doesn't simplify then only proceed if both of the existing - // operations "A op' B" and "C op' D" will be zapped since no longer used. - if (!RHS && Op0->hasOneUse() && Op1->hasOneUse()) - RHS = Builder->CreateBinOp(OuterOpcode, B, D, Op1->getName()); - if (RHS) { - ++NumFactor; - return BinaryOperator::Create(InnerOpcode, A, RHS); + // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"? + if (RightDistributesOverLeft(TopLevelOpcode, InnerOpcode)) + // Does the instruction have the form "(A op' B) op (C op' B)" or, in the + // commutative case, "(A op' B) op (B op' D)"? + if (B == D || (InnerCommutative && B == C)) { + if (B != D) + std::swap(C, D); + // Consider forming "(A op C) op' B". + // If "A op C" simplifies then it can be formed with no cost. + Value *V = SimplifyBinOp(TopLevelOpcode, A, C, TD); + // If "A op C" doesn't simplify then only go on if both of the existing + // operations "A op' B" and "C op' D" will be zapped as no longer used. + if (!V && Op0->hasOneUse() && Op1->hasOneUse()) + V = Builder->CreateBinOp(TopLevelOpcode, A, C, Op0->getName()); + if (V) { + ++NumFactor; + V = Builder->CreateBinOp(InnerOpcode, V, B); + V->takeName(&I); + return V; + } } - } + } - // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"? - if (RightDistributesOverLeft(OuterOpcode, InnerOpcode)) - // Does the instruction have the form "(A op' B) op (C op' B)" or, in the - // commutative case, "(A op' B) op (B op' D)"? - if (B == D || (InnerCommutative && B == C)) { - if (B != D) - std::swap(C, D); - // Consider forming "(A op C) op' B". - // If "A op C" simplifies then it can be formed with no cost. - Value *LHS = SimplifyBinOp(OuterOpcode, A, C, TD); - // If "A op C" doesn't simplify then only proceed if both of the existing - // operations "A op' B" and "C op' D" will be zapped since no longer used. - if (!LHS && Op0->hasOneUse() && Op1->hasOneUse()) - LHS = Builder->CreateBinOp(OuterOpcode, A, C, Op0->getName()); - if (LHS) { - ++NumFactor; - return BinaryOperator::Create(InnerOpcode, LHS, B); + // Expansion. + if (Op0 && RightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) { + // The instruction has the form "(A op' B) op C". See if expanding it out + // to "(A op C) op' (B op C)" results in simplifications. + Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; + Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op' + + // Do "A op C" and "B op C" both simplify? + if (Value *L = SimplifyBinOp(TopLevelOpcode, A, C, TD)) + if (Value *R = SimplifyBinOp(TopLevelOpcode, B, C, TD)) { + // They do! Return "L op' R". + ++NumExpand; + // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. + if ((L == A && R == B) || + (Instruction::isCommutative(InnerOpcode) && L == B && R == A)) + return Op0; + // Otherwise return "L op' R" if it simplifies. + if (Value *V = SimplifyBinOp(InnerOpcode, L, R, TD)) + return V; + // Otherwise, create a new instruction. + C = Builder->CreateBinOp(InnerOpcode, L, R); + C->takeName(&I); + return C; } - } + } + + if (Op1 && LeftDistributesOverRight(TopLevelOpcode, Op1->getOpcode())) { + // The instruction has the form "A op (B op' C)". See if expanding it out + // to "(A op B) op' (A op C)" results in simplifications. + Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); + Instruction::BinaryOps InnerOpcode = Op1->getOpcode(); // op' + + // Do "A op B" and "A op C" both simplify? + if (Value *L = SimplifyBinOp(TopLevelOpcode, A, B, TD)) + if (Value *R = SimplifyBinOp(TopLevelOpcode, A, C, TD)) { + // They do! Return "L op' R". + ++NumExpand; + // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. + if ((L == B && R == C) || + (Instruction::isCommutative(InnerOpcode) && L == C && R == B)) + return Op1; + // Otherwise return "L op' R" if it simplifies. + if (Value *V = SimplifyBinOp(InnerOpcode, L, R, TD)) + return V; + // Otherwise, create a new instruction. + A = Builder->CreateBinOp(InnerOpcode, L, R); + A->takeName(&I); + return A; + } + } return 0; } diff --git a/test/Transforms/InstCombine/2010-11-23-Distributed.ll b/test/Transforms/InstCombine/2010-11-23-Distributed.ll index 13a5720dad2..4f8e8dc713b 100644 --- a/test/Transforms/InstCombine/2010-11-23-Distributed.ll +++ b/test/Transforms/InstCombine/2010-11-23-Distributed.ll @@ -5,7 +5,19 @@ define i32 @foo(i32 %x, i32 %y) { %mul = mul nsw i32 %add, %y %square = mul nsw i32 %y, %y %res = sub i32 %mul, %square -; CHECK: %res = mul i32 %x, %y ret i32 %res -; CHECK: ret i32 %res +; CHECK-NEXT: mul i32 %x, %y +; CHECK-NEXT: ret i32 +} + +define i1 @bar(i64 %x, i64 %y) { +; CHECK: @bar + %a = and i64 %y, %x +; CHECK: and +; CHECK-NOT: and + %not = xor i64 %a, -1 + %b = and i64 %y, %not + %r = icmp eq i64 %b, 0 + ret i1 %r +; CHECK: ret i1 } -- 2.34.1