fix a nice subtle reassociate bug which would only occur

in a very specific use pattern embodied in the carefully
reduced testcase.

llvm-svn: 97794

2 files changed, 34 insertions, 7 deletions

diff --git a/llvm/lib/Transforms/Scalar/Reassociate.cpp b/llvm/lib/Transforms/Scalar/Reassociate.cpp
index 12827b6..5aca9cd 100644
--- a/llvm/lib/Transforms/Scalar/Reassociate.cpp
+++ b/llvm/lib/Transforms/Scalar/Reassociate.cpp
@@ -597,19 +597,35 @@ Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) {
 
 /// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively
 /// add its operands as factors, otherwise add V to the list of factors.
+///
+/// Ops is the top-level list of add operands we're trying to factor.
 static void FindSingleUseMultiplyFactors(Value *V,
-                                         SmallVectorImpl<Value*> &Factors) {
+                                         SmallVectorImpl<Value*> &Factors,
+                                       const SmallVectorImpl<ValueEntry> &Ops,
+                                         bool IsRoot) {
   BinaryOperator *BO;
-  if ((!V->hasOneUse() && !V->use_empty()) ||
+  if (!(V->hasOneUse() || V->use_empty()) || // More than one use.
       !(BO = dyn_cast<BinaryOperator>(V)) ||
       BO->getOpcode() != Instruction::Mul) {
     Factors.push_back(V);
     return;
   }
   
+  // If this value has a single use because it is another input to the add
+  // tree we're reassociating and we dropped its use, it actually has two
+  // uses and we can't factor it.
+  if (!IsRoot) {
+    for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+      if (Ops[i].Op == V) {
+        Factors.push_back(V);
+        return;
+      }
+  }
+  
+  
   // Otherwise, add the LHS and RHS to the list of factors.
-  FindSingleUseMultiplyFactors(BO->getOperand(1), Factors);
-  FindSingleUseMultiplyFactors(BO->getOperand(0), Factors);
+  FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops, false);
+  FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops, false);
 }
 
 /// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor'
@@ -753,7 +769,7 @@ Value *Reassociate::OptimizeAdd(Instruction *I,
     
     // Compute all of the factors of this added value.
     SmallVector<Value*, 8> Factors;
-    FindSingleUseMultiplyFactors(BOp, Factors);
+    FindSingleUseMultiplyFactors(BOp, Factors, Ops, true);
     assert(Factors.size() > 1 && "Bad linearize!");
     
     // Add one to FactorOccurrences for each unique factor in this op.
diff --git a/llvm/test/Transforms/Reassociate/crash.ll b/llvm/test/Transforms/Reassociate/crash.ll
index 060018d..6f21b66 100644
--- a/llvm/test/Transforms/Reassociate/crash.ll
+++ b/llvm/test/Transforms/Reassociate/crash.ll
@@ -23,11 +23,22 @@ entry:
   %3 = add nsw i32 undef, %1
   %4 = add nsw i32 %3, %2
   %5 = add nsw i32 %4, 4
-  %6 = shl i32 %0, 3                              ; <i32> [#uses=1]
+  %6 = shl i32 %0, 3
   %7 = add nsw i32 %5, %6
   br label %bb4.i9
 
-bb4.i9:                                           ; preds = %bb3.i7, %bb1.i25.i
+bb4.i9:
   %8 = add nsw i32 undef, %1
   ret i32 0
 }
+
+
+define i32 @test3(i32 %Arg, i32 %x1, i32 %x2, i32 %x3) {
+ %A = mul i32 %x1, %Arg
+ %B = mul i32 %Arg, %x2 ;; Part of add operation being factored, also used by C
+ %C = mul i32 %x3, %B
+
+ %D = add i32 %A, %B
+ %E = add i32 %D, %C
+  ret i32 %E
+}