Exploit distributive laws (eg: And distributes over Or, Mul over Add, etc) in a

fairly systematic way in instcombine.  Some of these cases were already dealt
with, in which case I removed the existing code.  The case of Add has a bunch of
funky logic which covers some of this plus a few variants (considers shifts to be
a form of multiplication), which I didn't touch.  The simplification performed is:
A*B+A*C -> A*(B+C).  The improvement is to do this in cases that were not already
handled [such as A*B-A*C -> A*(B-C), which was reported on the mailing list], and
also to do it more often by not checking for "only one use" if "B+C" simplifies.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120024 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 111 insertions, 0 deletions

diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp
index cfc418256a..ef7430cd72 100644
--- a/lib/Transforms/InstCombine/InstructionCombining.cpp
+++ b/lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -237,6 +237,117 @@ bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) {
   } while (1);
 }
 
+/// LeftDistributesOverRight - Whether "X LOp (Y ROp Z)" is always equal to
+/// "(X LOp Y) ROp (Z LOp Z)".
+static bool LeftDistributesOverRight(Instruction::BinaryOps LOp,
+                                     Instruction::BinaryOps ROp) {
+  switch (LOp) {
+  default:
+    return false;
+
+  case Instruction::And:
+    // And distributes over Or and Xor.
+    switch (ROp) {
+    default:
+      return false;
+    case Instruction::Or:
+    case Instruction::Xor:
+      return true;
+    }
+
+  case Instruction::Mul:
+    // Multiplication distributes over addition and subtraction.
+    switch (ROp) {
+    default:
+      return false;
+    case Instruction::Add:
+    case Instruction::Sub:
+      return true;
+    }
+
+  case Instruction::Or:
+    // Or distributes over And.
+    switch (ROp) {
+    default:
+      return false;
+    case Instruction::And:
+      return true;
+    }
+  }
+}
+
+/// RightDistributesOverLeft - Whether "(X LOp Y) ROp Z" is always equal to
+/// "(X ROp Z) LOp (Y ROp Z)".
+static bool RightDistributesOverLeft(Instruction::BinaryOps LOp,
+                                     Instruction::BinaryOps ROp) {
+  if (Instruction::isCommutative(ROp))
+    return LeftDistributesOverRight(ROp, LOp);
+  // TODO: It would be nice to handle division, aka "(X + Y)/Z = X/Z + Y/Z",
+  // but this requires knowing that the addition does not overflow and other
+  // such subtleties.
+  return false;
+}
+
+/// SimplifyDistributed - This tries to simplify binary operations which some
+/// other binary operation distributes over (eg "A*B+A*C" -> "A*(B+C)" since
+/// addition is distributed over by multiplication).  Returns the result of
+/// the simplification, or null if no simplification was performed.
+Instruction *InstCombiner::SimplifyDistributed(BinaryOperator &I) {
+  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));
+  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));
+  if (!Op0 || !Op1 || Op0->getOpcode() != Op1->getOpcode())
+    return 0;
+
+  // The instruction has the form "(A op' B) op (C op' D)".
+  Value *A = Op0->getOperand(0); Value *B = Op0->getOperand(1);
+  Value *C = Op1->getOperand(0); Value *D = Op1->getOperand(1);
+  Instruction::BinaryOps OuterOpcode = I.getOpcode(); // op
+  Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'
+
+  // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"?
+  bool LeftDistributes = LeftDistributesOverRight(InnerOpcode, OuterOpcode);
+  // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"?
+  bool RightDistributes = RightDistributesOverLeft(OuterOpcode, InnerOpcode);
+  // Does "X op' Y" always equal "Y op' X"?
+  bool InnerCommutative = Instruction::isCommutative(InnerOpcode);
+
+  if (LeftDistributes)
+    // 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 *RHS = SimplifyBinOp(OuterOpcode, B, D, TD);
+      // If "B op D" doesn't simplify then only proceed if both of the existing
+      // operations "A op' B" and "C op' D" will be zapped since no longer used.
+      if (!RHS && Op0->hasOneUse() && Op1->hasOneUse())
+        RHS = Builder->CreateBinOp(OuterOpcode, B, D, Op1->getName());
+      if (RHS)
+        return BinaryOperator::Create(InnerOpcode, A, RHS);
+    }
+
+  if (RightDistributes)
+    // 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 *LHS = SimplifyBinOp(OuterOpcode, A, C, TD);
+      // If "A op C" doesn't simplify then only proceed if both of the existing
+      // operations "A op' B" and "C op' D" will be zapped since no longer used.
+      if (!LHS && Op0->hasOneUse() && Op1->hasOneUse())
+        LHS = Builder->CreateBinOp(OuterOpcode, A, C, Op0->getName());
+      if (LHS)
+        return BinaryOperator::Create(InnerOpcode, LHS, B);
+    }
+
+  return 0;
+}
+
 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
 // if the LHS is a constant zero (which is the 'negate' form).
 //