From 096aa79276b8527a3cbbb3691e40e729dea09523 Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Sat, 13 Nov 2010 15:10:37 +0000 Subject: Generalize the reassociation transform in SimplifyCommutative (now renamed to SimplifyAssociativeOrCommutative) "(A op C1) op C2" -> "A op (C1 op C2)", which previously was only done if C1 and C2 were constants, to occur whenever "C1 op C2" simplifies (a la InstructionSimplify). Since the simplifying operand combination can no longer be assumed to be the right-hand terms, consider all of the possible permutations. When compiling "gcc as one big file", transform 2 (i.e. using right-hand operands) fires about 4000 times but it has to be said that most of the time the simplifying operands are both constants. Transforms 3, 4 and 5 each fired once. Transform 6, which is an existing transform that I didn't change, never fired. With this change, the testcase is now optimized perfectly with one run of instcombine (previously it required instcombine + reassociate + instcombine, and it may just have been luck that this worked). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119002 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstructionCombining.cpp | 154 ++++++++++++++++----- 1 file changed, 118 insertions(+), 36 deletions(-) (limited to 'lib/Transforms/InstCombine/InstructionCombining.cpp') diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index de409d1..61676f8 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -106,53 +106,135 @@ bool InstCombiner::ShouldChangeType(const Type *From, const Type *To) const { } -// SimplifyCommutative - This performs a few simplifications for commutative -// operators: +/// SimplifyAssociativeOrCommutative - This performs a few simplifications for +/// operators which are associative or commutative: +// +// Commutative operators: // // 1. Order operands such that they are listed from right (least complex) to // left (most complex). This puts constants before unary operators before // binary operators. // -// 2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2)) -// 3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2)) +// Associative operators: +// +// 2. Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies. +// 3. Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies. +// +// Associative and commutative operators: +// +// 4. Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies. +// 5. Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies. +// 6. Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)" +// if C1 and C2 are constants. // -bool InstCombiner::SimplifyCommutative(BinaryOperator &I) { +bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) { + Instruction::BinaryOps Opcode = I.getOpcode(); bool Changed = false; - if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1))) - Changed = !I.swapOperands(); - if (!I.isAssociative()) return Changed; - - Instruction::BinaryOps Opcode = I.getOpcode(); - if (BinaryOperator *Op = dyn_cast(I.getOperand(0))) - if (Op->getOpcode() == Opcode && isa(Op->getOperand(1))) { - if (isa(I.getOperand(1))) { - Constant *Folded = ConstantExpr::get(I.getOpcode(), - cast(I.getOperand(1)), - cast(Op->getOperand(1))); - I.setOperand(0, Op->getOperand(0)); - I.setOperand(1, Folded); - return true; + do { + // Order operands such that they are listed from right (least complex) to + // left (most complex). This puts constants before unary operators before + // binary operators. + if (I.isCommutative() && getComplexity(I.getOperand(0)) < + getComplexity(I.getOperand(1))) + Changed = !I.swapOperands(); + + BinaryOperator *Op0 = dyn_cast(I.getOperand(0)); + BinaryOperator *Op1 = dyn_cast(I.getOperand(1)); + + if (I.isAssociative()) { + // Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies. + if (Op0 && Op0->getOpcode() == Opcode) { + Value *A = Op0->getOperand(0); + Value *B = Op0->getOperand(1); + Value *C = I.getOperand(1); + + // Does "B op C" simplify? + if (Value *V = SimplifyBinOp(Opcode, B, C, TD)) { + // It simplifies to V. Form "A op V". + I.setOperand(0, A); + I.setOperand(1, V); + Changed = true; + continue; + } } - - if (BinaryOperator *Op1 = dyn_cast(I.getOperand(1))) - if (Op1->getOpcode() == Opcode && isa(Op1->getOperand(1)) && - Op->hasOneUse() && Op1->hasOneUse()) { - Constant *C1 = cast(Op->getOperand(1)); - Constant *C2 = cast(Op1->getOperand(1)); - - // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2)) - Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2); - Instruction *New = BinaryOperator::Create(Opcode, Op->getOperand(0), - Op1->getOperand(0), - Op1->getName(), &I); - Worklist.Add(New); - I.setOperand(0, New); - I.setOperand(1, Folded); - return true; + + // Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies. + if (Op1 && Op1->getOpcode() == Opcode) { + Value *A = I.getOperand(0); + Value *B = Op1->getOperand(0); + Value *C = Op1->getOperand(1); + + // Does "A op B" simplify? + if (Value *V = SimplifyBinOp(Opcode, A, B, TD)) { + // It simplifies to V. Form "V op C". + I.setOperand(0, V); + I.setOperand(1, C); + Changed = true; + continue; } + } } - return Changed; + + if (I.isAssociative() && I.isCommutative()) { + // Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies. + if (Op0 && Op0->getOpcode() == Opcode) { + Value *A = Op0->getOperand(0); + Value *B = Op0->getOperand(1); + Value *C = I.getOperand(1); + + // Does "C op A" simplify? + if (Value *V = SimplifyBinOp(Opcode, C, A, TD)) { + // It simplifies to V. Form "V op B". + I.setOperand(0, V); + I.setOperand(1, B); + Changed = true; + continue; + } + } + + // Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies. + if (Op1 && Op1->getOpcode() == Opcode) { + Value *A = I.getOperand(0); + Value *B = Op1->getOperand(0); + Value *C = Op1->getOperand(1); + + // Does "C op A" simplify? + if (Value *V = SimplifyBinOp(Opcode, C, A, TD)) { + // It simplifies to V. Form "B op V". + I.setOperand(0, B); + I.setOperand(1, V); + Changed = true; + continue; + } + } + + // Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)" + // if C1 and C2 are constants. + if (Op0 && Op1 && + Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode && + isa(Op0->getOperand(1)) && + isa(Op1->getOperand(1)) && + Op0->hasOneUse() && Op1->hasOneUse()) { + Value *A = Op0->getOperand(0); + Constant *C1 = cast(Op0->getOperand(1)); + Value *B = Op1->getOperand(0); + Constant *C2 = cast(Op1->getOperand(1)); + + Constant *Folded = ConstantExpr::get(Opcode, C1, C2); + Instruction *New = BinaryOperator::Create(Opcode, A, B, Op1->getName(), + &I); + Worklist.Add(New); + I.setOperand(0, New); + I.setOperand(1, Folded); + Changed = true; + continue; + } + } + + // No further simplifications. + return Changed; + } while (1); } // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction -- cgit v1.1