enum { RecursionLimit = 3 };
STATISTIC(NumExpand, "Number of expansions");
-STATISTIC(NumFactor , "Number of factorizations");
STATISTIC(NumReassoc, "Number of reassociations");
struct Query {
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<BinaryOperator>(LHS);
- BinaryOperator *Op1 = dyn_cast<BinaryOperator>(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,
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
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))
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))
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<SelectInst>(Op0) || isa<SelectInst>(Op1))
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<SelectInst>(Op0) || isa<SelectInst>(Op1))
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
}
}
- // 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<Constant>(RHS)) {
Value *X;
if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X
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<<C --> X * (1-(1<<C))
- if (match(Op1, m_Shl(m_Specific(Op0), m_Constant(CI)))) {
- Constant *One = ConstantInt::get(I.getType(), 1);
- C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI));
- return BinaryOperator::CreateMul(Op0, C);
- }
-
// X - A*-B -> X + A*B
// X - -A*B -> X + A*B
Value *A, *B;