Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -865,30 +865,6 @@ return createFMul(OpndVal, Coeff.getValue(Instr->getType())); } -// dyn_castFoldableMul - If this value is a multiply that can be folded into -// other computations (because it has a constant operand), return the -// non-constant operand of the multiply, and set CST to point to the multiplier. -// Otherwise, return null. -// -static inline Value *dyn_castFoldableMul(Value *V, Constant *&CST) { - if (!V->hasOneUse() || !V->getType()->isIntOrIntVectorTy()) - return nullptr; - - Instruction *I = dyn_cast(V); - if (!I) return nullptr; - - if (I->getOpcode() == Instruction::Mul) - if ((CST = dyn_cast(I->getOperand(1)))) - return I->getOperand(0); - if (I->getOpcode() == Instruction::Shl) - if ((CST = dyn_cast(I->getOperand(1)))) { - // The multiplier is really 1 << CST. - CST = ConstantExpr::getShl(ConstantInt::get(V->getType(), 1), CST); - return I->getOperand(0); - } - return nullptr; -} - // If one of the operands only has one non-zero bit, and if the other // operand has a known-zero bit in a more significant place than it (not // including the sign bit) the ripple may go up to and fill the zero, but @@ -1074,24 +1050,6 @@ if (Value *V = dyn_castNegVal(RHS)) return BinaryOperator::CreateSub(LHS, V); - - { - Constant *C2; - if (Value *X = dyn_castFoldableMul(LHS, C2)) { - if (X == RHS) // X*C + X --> X * (C+1) - return BinaryOperator::CreateMul(RHS, AddOne(C2)); - - // X*C1 + X*C2 --> X * (C1+C2) - Constant *C1; - if (X == dyn_castFoldableMul(RHS, C1)) - return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2)); - } - - // X + X*C --> X * (C+1) - if (dyn_castFoldableMul(RHS, C2) == LHS) - return BinaryOperator::CreateMul(LHS, AddOne(C2)); - } - // A+B --> A|B iff A and B have no bits set in common. if (IntegerType *IT = dyn_cast(I.getType())) { APInt LHSKnownOne(IT->getBitWidth(), 0); @@ -1571,16 +1529,6 @@ } } - Constant *C1; - if (Value *X = dyn_castFoldableMul(Op0, C1)) { - if (X == Op1) // X*C - X --> X * (C-1) - return BinaryOperator::CreateMul(Op1, SubOne(C1)); - - Constant *C2; // X*C1 - X*C2 -> X * (C1-C2) - if (X == dyn_castFoldableMul(Op1, C2)) - return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2)); - } - // Optimize pointer differences into the same array into a size. Consider: // &A[10] - &A[0]: we should compile this to "10". if (DL) { Index: lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- lib/Transforms/InstCombine/InstructionCombining.cpp +++ lib/Transforms/InstCombine/InstructionCombining.cpp @@ -395,6 +395,44 @@ return false; } +// This faction factors value using identity value for given Opcode. +// e.g. (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1) +Value *FactorUsingIdentityValue(Instruction::BinaryOps OpCode, Value *V, + Value *&FoldedRHS) { + if (isa(V)) + return nullptr; + + switch (OpCode) { + default: + return nullptr; + + case Instruction::Mul: + FoldedRHS = ConstantInt::get(V->getType(), 1); + return V; + } + return nullptr; +} + +// This function factors binary ops which can be combined using distributive +// laws. This also factor SHL as MUL e.g. SHL(X, 2) ==> MUL(X, 4) +Value *FactorBinaryOps(BinaryOperator *Op, Value *&FoldedRHS, + Instruction::BinaryOps &OpCode) { + if (!Op) + return nullptr; + + if (Op->getOpcode() == Instruction::Shl) { + if (Constant *CST = dyn_cast(Op->getOperand(1))) { + FoldedRHS = ConstantExpr::getShl(ConstantInt::get(Op->getType(), 1), CST); + OpCode = Instruction::BinaryOps::Mul; + return Op->getOperand(0); + } + } + + FoldedRHS = Op->getOperand(1); + OpCode = Op->getOpcode(); + return Op->getOperand(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 @@ -402,64 +440,91 @@ /// 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); + Instruction::BinaryOps TopLevelOpcode = I.getOpcode(); // op + + Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; + Instruction::BinaryOps LHSOpcode = Instruction::BinaryOpsEnd; + Instruction::BinaryOps RHSOpcode = Instruction::BinaryOpsEnd; + BinaryOperator *Op0 = dyn_cast(LHS); BinaryOperator *Op1 = dyn_cast(RHS); - Instruction::BinaryOps TopLevelOpcode = I.getOpcode(); // op - // Factorization. - if (Op0 && Op1 && Op0->getOpcode() == Op1->getOpcode()) { + A = FactorBinaryOps(Op0, B, LHSOpcode); + C = FactorBinaryOps(Op1, D, RHSOpcode); + + if (A || C) { + if (!A && (A = FactorUsingIdentityValue(RHSOpcode, LHS, B))) + LHSOpcode = RHSOpcode; + else if (!C && (C = FactorUsingIdentityValue(LHSOpcode, RHS, D))) + RHSOpcode = LHSOpcode; + // 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, DL); - // 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; + if (A && C && LHSOpcode == RHSOpcode) { + // Does "X op' Y" always equal "Y op' X"? + bool InnerCommutative = Instruction::isCommutative(LHSOpcode); + // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"? + if (LeftDistributesOverRight(LHSOpcode, 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, DL); + // 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 && LHS->hasOneUse() && RHS->hasOneUse()) + V = Builder->CreateBinOp(TopLevelOpcode, B, D, RHS->getName()); + if (V) { + ++NumFactor; + V = Builder->CreateBinOp(LHSOpcode, A, V); + V->takeName(&I); + if (isa(V)) { + bool HasNSW = I.hasNoSignedWrap(); + if (Op0) + HasNSW &= Op0->hasNoSignedWrap(); + if (Op1) + HasNSW &= Op1->hasNoSignedWrap(); + cast(V)->setHasNoSignedWrap(HasNSW); + } + return V; + } } - } - // 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, DL); - // 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(TopLevelOpcode, LHSOpcode)) + // 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, DL); + // 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 && LHS->hasOneUse() && RHS->hasOneUse()) + V = Builder->CreateBinOp(TopLevelOpcode, A, C, LHS->getName()); + if (V) { + ++NumFactor; + V = Builder->CreateBinOp(LHSOpcode, V, B); + V->takeName(&I); + if (isa(V)) { + bool HasNSW = I.hasNoSignedWrap(); + if (Op0) + HasNSW &= Op0->hasNoSignedWrap(); + if (Op1) + HasNSW &= Op1->hasNoSignedWrap(); + cast(V)->setHasNoSignedWrap(HasNSW); + } + return V; + } } - } + } } // Expansion. Index: test/Transforms/InstCombine/add2.ll =================================================================== --- test/Transforms/InstCombine/add2.ll +++ test/Transforms/InstCombine/add2.ll @@ -86,3 +86,60 @@ ; CHECK-NEXT: %d = mul i16 %a, -32767 ; CHECK-NEXT: ret i16 %d } + +define i16 @add_nsw_mul_nsw(i16 %x) { + %add1 = add nsw i16 %x, %x + %add2 = add nsw i16 %add1, %x + ret i16 %add2 +; CHECK-LABEL: @add_nsw_mul_nsw( +; CHECK-NEXT: %add2 = mul nsw i16 %x, 3 +; CHECK-NEXT: ret i16 %add2 +} + +define i16 @mul_add_to_mul_1(i16 %x) { + %mul1 = mul nsw i16 %x, 8 + %add2 = add nsw i16 %x, %mul1 + ret i16 %add2 +; CHECK-LABEL: @mul_add_to_mul_1( +; CHECK-NEXT: %add2 = mul nsw i16 %x, 9 +; CHECK-NEXT: ret i16 %add2 +} + +define i16 @mul_add_to_mul_2(i16 %x) { + %mul1 = mul nsw i16 %x, 8 + %add2 = add nsw i16 %mul1, %x + ret i16 %add2 +; CHECK-LABEL: @mul_add_to_mul_2( +; CHECK-NEXT: %add2 = mul nsw i16 %x, 9 +; CHECK-NEXT: ret i16 %add2 +} + +define i16 @mul_add_to_mul_3(i16 %a) { + %mul1 = mul i16 %a, 2 + %mul2 = mul i16 %a, 3 + %add = add nsw i16 %mul1, %mul2 + ret i16 %add +; CHECK-LABEL: @mul_add_to_mul_3( +; CHECK-NEXT: %add = mul i16 %a, 5 +; CHECK-NEXT: ret i16 %add +} + +define i16 @mul_add_to_mul_4(i16 %a) { + %mul1 = mul nsw i16 %a, 2 + %mul2 = mul nsw i16 %a, 7 + %add = add nsw i16 %mul1, %mul2 + ret i16 %add +; CHECK-LABEL: @mul_add_to_mul_4( +; CHECK-NEXT: %add = mul nsw i16 %a, 9 +; CHECK-NEXT: ret i16 %add +} + +define i16 @mul_add_to_mul_5(i16 %a) { + %mul1 = mul nsw i16 %a, 3 + %mul2 = mul nsw i16 %a, 7 + %add = add nsw i16 %mul1, %mul2 + ret i16 %add +; CHECK-LABEL: @mul_add_to_mul_5( +; CHECK-NEXT: %add = mul nsw i16 %a, 10 +; CHECK-NEXT: ret i16 %add +} \ No newline at end of file