Removed pattern checks in instruction simplify/ combine which are now handled in SimplifyUsingDistributiveLaws()

[dinesh.d]

Summary

This patch removed duplicate code for matching patterns which are not handled in SimplifyUsingDistributiveLaws() (after r211261)

[jingyue]

Looks good in general. I am reading this patch out of context. Are you removing these because you added similar logic in InstCombine? A further question I am curious about is what's the split between InstructionSimplify and InstCombine. Both seem to simplify instructions. What should be in one versus the other?

[dinesh.d]

Yes, With SimplifyUsingDistributiveLaws() updated in r211261, now it can handle all transforms
handled by these removed code. This patch removes code duplication. I am planning to further
analyse transform using associative, commutative and distributive laws and generalize them.

I had doubt about removing code from instruction simplify as it works as independent pass. I have
talked to Ben before submitting this patch for review.

I do have my doubts about what goes to simplify and what in combine. But from what I have read
in code and mailing list, if we can transform instruction to one of its operand or to some simple
value, it should be in simplify. Instruction combine has transforms which combine 2 or more
instruction to less instruction(s).

[jingyue]

Thanks for clarification! It makes much sense to me now. Some nits, otherwise LGTM.

test/Transforms/InstCombine/distribute.ll

36 ↗

(On Diff #10744)

Could you add a comment that translates the IR into math expressions? Just as what you did for factorize1|2|3. It would be much easier to follow. Thanks!

48 ↗

(On Diff #10744)

ditto

[dinesh.d]

Thanks :)

test/Transforms/InstCombine/distribute.ll

36 ↗

(On Diff #10744)

updated.

48 ↗

(On Diff #10744)

updated.

[dinesh.d]

Closed by commit rL211768 (authored by dinesh).

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "instsimplify"
 
 enum { RecursionLimit = 3 };
 
 STATISTIC(NumExpand,  "Number of expansions");
-STATISTIC(NumFactor , "Number of factorizations");
 STATISTIC(NumReassoc, "Number of reassociations");
 
 struct Query {
   const DataLayout *DL;
   const TargetLibraryInfo *TLI;
   const DominatorTree *DT;
 
   Query(const DataLayout *DL, const TargetLibraryInfo *tli,
if (Op1->getOpcode() == OpcodeToExpand) {
             return V;
           }
         }
     }
 
   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,
                                        const Query &Q, unsigned MaxRecurse) {
   Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc;
   assert(Instruction::isAssociative(Opcode) && "Not an associative operation!");
 
   // Recursion is always used, so bail out at once if we already hit the limit.
if (MaxRecurse && Op0->getType()->isIntegerTy(1))
     if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
       return V;
 
   // Try some generic simplifications for associative operations.
   if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
                                           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
   // only if B and C are equal.  If B and C are equal then (since we assume
   // that operands have already been simplified) "select(cond, B, C)" should
   // have been simplified to the common value of B and C already.  Analysing
   // "A+B" and "A+C" thus gains nothing, but costs compile time.  Similarly
   // for threading over phi nodes.
static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
   // X - 0 -> X
   if (match(Op1, m_Zero()))
     return Op0;
 
   // X - X -> 0
   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))
       // It does!  Now see if "X + V" simplifies.
       if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
         // It does, we successfully reassociated!
         ++NumReassoc;
         return W;
if (X->getType() == Y->getType())
           return W;
 
   // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
   if (match(Op0, m_PtrToInt(m_Value(X))) &&
       match(Op1, m_PtrToInt(m_Value(Y))))
     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))
       return V;
 
   // Threading Sub 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 (Value *V = ExpandBinOp(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))
     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))
     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
                                          MaxRecurse))
       return V;
 
   // If the operation is with the result of a phi instruction, check whether
if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
                                           MaxRecurse))
     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))
     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))
     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
                                          MaxRecurse))
       return V;
 
   // (A & C)|(B & D)
if (match(Op0, m_Not(m_Specific(Op1))) ||
       match(Op1, m_Not(m_Specific(Op0))))
     return Constant::getAllOnesValue(Op0->getType());
 
   // Try some generic simplifications for associative operations.
   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
                                           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
   // only if B and C are equal.  If B and C are equal then (since we assume
   // that operands have already been simplified) "select(cond, B, C)" should
   // have been simplified to the common value of B and C already.  Analysing
   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
   // for threading over phi nodes.

llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (LHSKnownZero != 0) {
       computeKnownBits(RHS, RHSKnownZero, RHSKnownOne);
 
       // No bits in common -> bitwise or.
       if ((LHSKnownZero|RHSKnownZero).isAllOnesValue())
         return BinaryOperator::CreateOr(LHS, RHS);
     }
   }
 
-  // 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
       return BinaryOperator::CreateSub(SubOne(CRHS), X);
   }
 
   if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
     // (X & FF00) + xx00  -> (X+xx00) & FF00
if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) &&
         match(Op0, m_Zero()))
       return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
 
     // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
     if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
       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;
     if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) ||
         match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B))))
       return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B));
 
     // X - A*CI -> X + A*-CI

llvm/trunk/test/Transforms/InstCombine/distribute.ll

+; 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
+}

llvm/trunk/test/Transforms/InstSimplify/2010-12-20-Distribute.ll

-; 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
-}