Index: llvm/trunk/lib/Analysis/InstructionSimplify.cpp =================================================================== --- llvm/trunk/lib/Analysis/InstructionSimplify.cpp +++ llvm/trunk/lib/Analysis/InstructionSimplify.cpp @@ -39,7 +39,6 @@ enum { RecursionLimit = 3 }; STATISTIC(NumExpand, "Number of expansions"); -STATISTIC(NumFactor , "Number of factorizations"); STATISTIC(NumReassoc, "Number of reassociations"); struct Query { @@ -183,78 +182,6 @@ return nullptr; } -/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term -/// using the operation OpCodeToExtract. For example, when Opcode is Add and -/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". -/// Returns the simplified value, or null if no simplification was performed. -static Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, - unsigned OpcToExtract, const Query &Q, - unsigned MaxRecurse) { - Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract; - // Recursion is always used, so bail out at once if we already hit the limit. - if (!MaxRecurse--) - return nullptr; - - BinaryOperator *Op0 = dyn_cast(LHS); - BinaryOperator *Op1 = dyn_cast(RHS); - - if (!Op0 || Op0->getOpcode() != OpcodeToExtract || - !Op1 || Op1->getOpcode() != OpcodeToExtract) - return nullptr; - - // The expression has the form "(A op' B) op (C op' D)". - Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); - Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); - - // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". - // 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 || (Instruction::isCommutative(OpcodeToExtract) && A == D)) { - Value *DD = A == C ? D : C; - // Form "A op' (B op DD)" if it simplifies completely. - // Does "B op DD" simplify? - if (Value *V = SimplifyBinOp(Opcode, B, DD, Q, MaxRecurse)) { - // It does! Return "A op' V" if it simplifies or is already available. - // If V equals B then "A op' V" is just the LHS. If V equals DD then - // "A op' V" is just the RHS. - if (V == B || V == DD) { - ++NumFactor; - return V == B ? LHS : RHS; - } - // Otherwise return "A op' V" if it simplifies. - if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, Q, MaxRecurse)) { - ++NumFactor; - return W; - } - } - } - - // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". - // 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 || (Instruction::isCommutative(OpcodeToExtract) && B == C)) { - Value *CC = B == D ? C : D; - // Form "(A op CC) op' B" if it simplifies completely.. - // Does "A op CC" simplify? - if (Value *V = SimplifyBinOp(Opcode, A, CC, Q, MaxRecurse)) { - // It does! Return "V op' B" if it simplifies or is already available. - // If V equals A then "V op' B" is just the LHS. If V equals CC then - // "V op' B" is just the RHS. - if (V == A || V == CC) { - ++NumFactor; - return V == A ? LHS : RHS; - } - // Otherwise return "V op' B" if it simplifies. - if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, Q, MaxRecurse)) { - ++NumFactor; - return W; - } - } - } - - return nullptr; -} - /// SimplifyAssociativeBinOp - Generic simplifications for associative binary /// operations. Returns the simpler value, or null if none was found. static Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, @@ -634,11 +561,6 @@ MaxRecurse)) return V; - // Mul distributes over Add. Try some generic simplifications based on this. - if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, - Q, MaxRecurse)) - return V; - // Threading Add over selects and phi nodes is pointless, so don't bother. // Threading over the select in "A + select(cond, B, C)" means evaluating // "A+B" and "A+C" and seeing if they are equal; but they are equal if and @@ -754,16 +676,9 @@ if (Op0 == Op1) return Constant::getNullValue(Op0->getType()); - // (X*2) - X -> X - // (X<<1) - X -> X - Value *X = nullptr; - if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) || - match(Op0, m_Shl(m_Specific(Op1), m_One()))) - return Op1; - // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. // For example, (X + Y) - Y -> X; (Y + X) - Y -> X - Value *Y = nullptr, *Z = Op1; + Value *X = nullptr, *Y = nullptr, *Z = Op1; if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z // See if "V === Y - Z" simplifies. if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) @@ -835,11 +750,6 @@ if (Constant *Result = computePointerDifference(Q.DL, X, Y)) return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); - // Mul distributes over Sub. Try some generic simplifications based on this. - if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, - Q, MaxRecurse)) - return V; - // i1 sub -> xor. if (MaxRecurse && Op0->getType()->isIntegerTy(1)) if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) @@ -1518,11 +1428,6 @@ Q, MaxRecurse)) return V; - // Or distributes over And. Try some generic simplifications based on this. - if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, - Q, MaxRecurse)) - return V; - // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) @@ -1613,11 +1518,6 @@ MaxRecurse)) return V; - // And distributes over Or. Try some generic simplifications based on this. - if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, - Q, MaxRecurse)) - return V; - // If the operation is with the result of a select instruction, check whether // operating on either branch of the select always yields the same value. if (isa(Op0) || isa(Op1)) @@ -1709,11 +1609,6 @@ MaxRecurse)) return V; - // And distributes over Xor. Try some generic simplifications based on this. - if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, - Q, MaxRecurse)) - return V; - // Threading Xor over selects and phi nodes is pointless, so don't bother. // Threading over the select in "A ^ select(cond, B, C)" means evaluating // "A^B" and "A^C" and seeing if they are equal; but they are equal if and Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -1131,29 +1131,6 @@ } } - // W*X + Y*Z --> W * (X+Z) iff W == Y - { - Value *W, *X, *Y, *Z; - if (match(LHS, m_Mul(m_Value(W), m_Value(X))) && - match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) { - if (W != Y) { - if (W == Z) { - std::swap(Y, Z); - } else if (Y == X) { - std::swap(W, X); - } else if (X == Z) { - std::swap(Y, Z); - std::swap(W, X); - } - } - - if (W == Y) { - Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName()); - return BinaryOperator::CreateMul(W, NewAdd); - } - } - } - if (Constant *CRHS = dyn_cast(RHS)) { Value *X; if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X @@ -1572,19 +1549,6 @@ if (Value *XNeg = dyn_castNegVal(X)) return BinaryOperator::CreateShl(XNeg, Y); - // X - X*C --> X * (1-C) - if (match(Op1, m_Mul(m_Specific(Op0), m_Constant(CI)))) { - Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI); - return BinaryOperator::CreateMul(Op0, CP1); - } - - // X - X< X * (1-(1< X + A*B // X - -A*B -> X + A*B Value *A, *B; Index: llvm/trunk/test/Transforms/InstCombine/distribute.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/distribute.ll +++ llvm/trunk/test/Transforms/InstCombine/distribute.ll @@ -0,0 +1,68 @@ +; RUN: opt < %s -instcombine -S | FileCheck %s + +define i32 @factorize(i32 %x, i32 %y) { +; CHECK-LABEL: @factorize( +; (X | 1) & (X | 2) -> X | (1 & 2) -> X + %l = or i32 %x, 1 + %r = or i32 %x, 2 + %z = and i32 %l, %r + ret i32 %z +; CHECK: ret i32 %x +} + +define i32 @factorize2(i32 %x) { +; CHECK-LABEL: @factorize2( +; 3*X - 2*X -> X + %l = mul i32 3, %x + %r = mul i32 2, %x + %z = sub i32 %l, %r + ret i32 %z +; CHECK: ret i32 %x +} + +define i32 @factorize3(i32 %x, i32 %a, i32 %b) { +; CHECK-LABEL: @factorize3( +; (X | (A|B)) & (X | B) -> X | ((A|B) & B) -> X | B + %aORb = or i32 %a, %b + %l = or i32 %x, %aORb + %r = or i32 %x, %b + %z = and i32 %l, %r + ret i32 %z +; CHECK: %z = or i32 %b, %x +; CHECK: ret i32 %z +} + +define i32 @factorize4(i32 %x, i32 %y) { +; CHECK-LABEL: @factorize4( +; ((Y << 1) * X) - (X * Y) -> (X * (Y * 2 - Y)) -> (X * Y) + %sh = shl i32 %y, 1 + %ml = mul i32 %sh, %x + %mr = mul i32 %x, %y + %s = sub i32 %ml, %mr + ret i32 %s +; CHECK: %s = mul i32 %y, %x +; CHECK: ret i32 %s +} + +define i32 @factorize5(i32 %x, i32 %y) { +; CHECK-LABEL: @factorize5( +; ((Y * 2) * X) - (X * Y) -> (X * Y) + %sh = mul i32 %y, 2 + %ml = mul i32 %sh, %x + %mr = mul i32 %x, %y + %s = sub i32 %ml, %mr + ret i32 %s +; CHECK: %s = mul i32 %y, %x +; CHECK: ret i32 %s +} + +define i32 @expand(i32 %x) { +; CHECK-LABEL: @expand( +; ((X & 1) | 2) & 1 -> ((X & 1) & 1) | (2 & 1) -> (X & 1) | 0 -> X & 1 + %a = and i32 %x, 1 + %b = or i32 %a, 2 + %c = and i32 %b, 1 + ret i32 %c +; CHECK: %a = and i32 %x, 1 +; CHECK: ret i32 %a +} Index: llvm/trunk/test/Transforms/InstSimplify/2010-12-20-Distribute.ll =================================================================== --- llvm/trunk/test/Transforms/InstSimplify/2010-12-20-Distribute.ll +++ llvm/trunk/test/Transforms/InstSimplify/2010-12-20-Distribute.ll @@ -1,62 +0,0 @@ -; RUN: opt < %s -instsimplify -S | FileCheck %s - -define i32 @factorize(i32 %x, i32 %y) { -; CHECK-LABEL: @factorize( -; (X | 1) & (X | 2) -> X | (1 & 2) -> X - %l = or i32 %x, 1 - %r = or i32 %x, 2 - %z = and i32 %l, %r - ret i32 %z -; CHECK: ret i32 %x -} - -define i32 @factorize2(i32 %x) { -; CHECK-LABEL: @factorize2( -; 3*X - 2*X -> X - %l = mul i32 3, %x - %r = mul i32 2, %x - %z = sub i32 %l, %r - ret i32 %z -; CHECK: ret i32 %x -} - -define i32 @factorize3(i32 %x, i32 %a, i32 %b) { -; CHECK-LABEL: @factorize3( -; (X | (A|B)) & (X | B) -> X | ((A|B) & B) -> X | B - %aORb = or i32 %a, %b - %l = or i32 %x, %aORb - %r = or i32 %x, %b - %z = and i32 %l, %r - ret i32 %z -; CHECK: ret i32 %r -} - -define i32 @factorize4(i32 %x, i32 %y) { -; CHECK-LABEL: @factorize4( - %sh = shl i32 %y, 1 - %ml = mul i32 %sh, %x - %mr = mul i32 %x, %y - %s = sub i32 %ml, %mr - ret i32 %s -; CHECK: ret i32 %mr -} - -define i32 @factorize5(i32 %x, i32 %y) { -; CHECK-LABEL: @factorize5( - %sh = mul i32 %y, 2 - %ml = mul i32 %sh, %x - %mr = mul i32 %x, %y - %s = sub i32 %ml, %mr - ret i32 %s -; CHECK: ret i32 %mr -} - -define i32 @expand(i32 %x) { -; CHECK-LABEL: @expand( -; ((X & 1) | 2) & 1 -> ((X & 1) & 1) | (2 & 1) -> (X & 1) | 0 -> X & 1 - %a = and i32 %x, 1 - %b = or i32 %a, 2 - %c = and i32 %b, 1 - ret i32 %c -; CHECK: ret i32 %a -}