From 7485e924121b48b437fe84a5d003110cb2665aa2 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Thu, 23 Jul 2020 08:33:45 -0400 Subject: [PATCH] [InstSimplify] reduce code duplication for binop expansion; NFC D84250 proposes to extend this code, so the duplication for the commuted case would continue to grow. --- llvm/lib/Analysis/InstructionSimplify.cpp | 112 ++++++++++++++---------------- 1 file changed, 51 insertions(+), 61 deletions(-) diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp index ca60276..4934686 100644 --- a/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/llvm/lib/Analysis/InstructionSimplify.cpp @@ -228,64 +228,54 @@ static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { return false; } -/// Simplify "A op (B op' C)" by distributing op over op', turning it into -/// "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is -/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. -/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". -/// Returns the simplified value, or null if no simplification was performed. -static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS, - Instruction::BinaryOps OpcodeToExpand, +/// Try to simplify a binary operator of form "V op OtherOp" where V is +/// "(B0 opex B1)" by distributing 'op' across 'opex' as +/// "(B0 op OtherOp) opex (B1 op OtherOp)". +static Value *expandBinOp(Instruction::BinaryOps Opcode, Value *V, + Value *OtherOp, Instruction::BinaryOps OpcodeToExpand, const SimplifyQuery &Q, unsigned MaxRecurse) { - // Recursion is always used, so bail out at once if we already hit the limit. - if (!MaxRecurse--) + auto *B = dyn_cast(V); + if (!B || B->getOpcode() != OpcodeToExpand) + return nullptr; + Value *B0 = B->getOperand(0), *B1 = B->getOperand(1); + Value *L = SimplifyBinOp(Opcode, B0, OtherOp, Q, MaxRecurse); + if (!L) + return nullptr; + Value *R = SimplifyBinOp(Opcode, B1, OtherOp, Q, MaxRecurse); + if (!R) return nullptr; - // Check whether the expression has the form "(A op' B) op C". - if (BinaryOperator *Op0 = dyn_cast(LHS)) - if (Op0->getOpcode() == OpcodeToExpand) { - // It does! Try turning it into "(A op C) op' (B op C)". - Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; - // Do "A op C" and "B op C" both simplify? - if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) - if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { - // They do! Return "L op' R" if it simplifies or is already available. - // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. - if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) - && L == B && R == A)) { - ++NumExpand; - return LHS; - } - // Otherwise return "L op' R" if it simplifies. - if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { - ++NumExpand; - return V; - } - } - } + // Does the expanded pair of binops simplify to the existing binop? + if ((L == B0 && R == B1) || + (Instruction::isCommutative(OpcodeToExpand) && L == B1 && R == B0)) { + ++NumExpand; + return B; + } - // Check whether the expression has the form "A op (B op' C)". - if (BinaryOperator *Op1 = dyn_cast(RHS)) - if (Op1->getOpcode() == OpcodeToExpand) { - // It does! Try turning it into "(A op B) op' (A op C)". - Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); - // Do "A op B" and "A op C" both simplify? - if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) - if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) { - // They do! Return "L op' R" if it simplifies or is already available. - // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. - if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) - && L == C && R == B)) { - ++NumExpand; - return RHS; - } - // Otherwise return "L op' R" if it simplifies. - if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { - ++NumExpand; - return V; - } - } - } + // Otherwise, return "L op' R" if it simplifies. + Value *S = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse); + if (!S) + return nullptr; + ++NumExpand; + return S; +} + +/// Try to simplify binops of form "A op (B op' C)" or the commuted variant by +/// distributing op over op'. +static Value *expandCommutativeBinOp(Instruction::BinaryOps Opcode, + Value *L, Value *R, + Instruction::BinaryOps OpcodeToExpand, + const SimplifyQuery &Q, + unsigned MaxRecurse) { + // Recursion is always used, so bail out at once if we already hit the limit. + if (!MaxRecurse--) + return nullptr; + + if (Value *V = expandBinOp(Opcode, L, R, OpcodeToExpand, Q, MaxRecurse)) + return V; + if (Value *V = expandBinOp(Opcode, R, L, OpcodeToExpand, Q, MaxRecurse)) + return V; return nullptr; } @@ -901,8 +891,8 @@ static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, return V; // Mul distributes over Add. Try some generic simplifications based on this. - if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, - Q, MaxRecurse)) + if (Value *V = expandCommutativeBinOp(Instruction::Mul, Op0, Op1, + Instruction::Add, Q, MaxRecurse)) return V; // If the operation is with the result of a select instruction, check whether @@ -2096,13 +2086,13 @@ static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, return V; // And distributes over Or. Try some generic simplifications based on this. - if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, - Q, MaxRecurse)) + if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1, + Instruction::Or, Q, MaxRecurse)) return V; // And distributes over Xor. Try some generic simplifications based on this. - if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, - Q, MaxRecurse)) + if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1, + Instruction::Xor, Q, MaxRecurse)) return V; // If the operation is with the result of a select instruction, check whether @@ -2254,8 +2244,8 @@ static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, return V; // Or distributes over And. Try some generic simplifications based on this. - if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, - MaxRecurse)) + if (Value *V = expandCommutativeBinOp(Instruction::Or, Op0, Op1, + Instruction::And, Q, MaxRecurse)) return V; // If the operation is with the result of a select instruction, check whether -- 2.7.4