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
diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp
index cfc4182..ef7430c 100644
--- a/lib/Transforms/InstCombine/InstructionCombining.cpp
+++ b/lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -237,6 +237,117 @@
} 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).
//