[Reassociate] Add negated value of negative constant to the Duplicates list.

[mcrosier]

Summary

In OptimizeAdd, we scan the operand list to see if there are any common factors between operands that can be factored out to reduce the number of multiplies (e.g., 'A*A+A*B*C+D' -> 'A*(A+B*C)+D'). For each operand of the operand list, we only consider unique factors (which is tracked by the Duplicate set). Now if we find a factor that is a negative constant, we add the negated value as a factor as well because we can percolate the negate out. However, mistakenly don't add this negated constant to the Duplicates set.

Consider the expression A*2*-2 + B. Obviously, nothing to factor.

For the added value A*2*-2 we over count 2 as a factor without this patch, which causes the assert reported in PR30256.

Chad

[efriedma]

lib/Transforms/Scalar/Reassociate.cpp

1523 ↗

(On Diff #89280)

Okay, now I understand the issue: the problem is that this code is assuming that all the multiply operands of the add are already reassociated. We break that assumption with the way we optimize shl->mul: we transform the shl into a mul, and stick the mul into RedoInsts, but don't revisit it until it's "too late".

Your first two patches dance around the issue in slightly different ways; basically, you dodge the issue by changing the visitation order. This seems like a landmine, even if it does fix the immediate problem.

This patch avoids the issue by making OptimizeAdd tolerate multiplies which haven't been completely optimized; this sort of works, but we're doing wasted work: we'll end up revisiting the add later anyway.

Another possible approach would be to enforce RPO iteration order more strongly. If we have RedoInsts, we process them immediately in RPO order, rather than waiting until we've finished processing the whole function. Intuitively, it seems like the natural approach: reassociation works on expression trees, so the optimization only works in one direction. That said, I'm not sure how practical that is given the current Reassociate; the "optimal" form for an expression depends on its use list (see all the uses of "user_back()"), so Reassociate is really an iterative optimization of sorts, so any changes here would probably get messy.

[mcrosier]

lib/Transforms/Scalar/Reassociate.cpp

1523 ↗

(On Diff #89280)

Yes, this is a good synopsis of what is going on and I agree my previous two approaches (D29777 and D30223) skate around the issue. You're also correct in that this patch results in wasted work (which is pervasive throughout this pass, unfortunately), but I don't think the RPO suggestion is practical for fixing this issue for the 4.0 release.

Would you be okay accepting this patch?

[efriedma]

Yes, I'm fine with this approach for now.

test/Transforms/Reassociate/basictest.ll

235 ↗

(On Diff #89280)

Please add CHECK lines to make sure the end result is what we expect, even if that isn't really the point of the test.

[mcrosier]

Update test with CHECKs, per Eli's feedback.

[mcrosier]

In D30228#683767, @efriedma wrote:

Yes, I'm fine with this approach for now.

Accepting, per Eli's.

llvm/trunk/lib/Transforms/Scalar/Reassociate.cpp

for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
       }
 
       // If Factor is a negative constant, add the negated value as a factor
       // because we can percolate the negate out.  Watch for minint, which
       // cannot be positivified.
       if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) {
         if (CI->isNegative() && !CI->isMinValue(true)) {
           Factor = ConstantInt::get(CI->getContext(), -CI->getValue());
-          assert(!Duplicates.count(Factor) &&
-                 "Shouldn't have two constant factors, missed a canonicalize");
+          if (!Duplicates.insert(Factor).second)
+            continue;
           unsigned Occ = ++FactorOccurrences[Factor];
           if (Occ > MaxOcc) {
             MaxOcc = Occ;
             MaxOccVal = Factor;
           }
         }
       } else if (ConstantFP *CF = dyn_cast<ConstantFP>(Factor)) {
         if (CF->isNegative()) {
           APFloat F(CF->getValueAPF());
           F.changeSign();
           Factor = ConstantFP::get(CF->getContext(), F);
-          assert(!Duplicates.count(Factor) &&
-                 "Shouldn't have two constant factors, missed a canonicalize");
+          if (!Duplicates.insert(Factor).second)
+            continue;
           unsigned Occ = ++FactorOccurrences[Factor];
           if (Occ > MaxOcc) {
             MaxOcc = Occ;
             MaxOccVal = Factor;
           }
         }
       }
     }

llvm/trunk/test/Transforms/Reassociate/basictest.ll

define i32 @test15(i32 %X1, i32 %X2, i32 %X3) {
   %A = icmp ne i32 %X1, 0
   %B = icmp slt i32 %X2, %X3
   %C = and i1 %A, %B
   %D = select i1 %C, i32 %X1, i32 0
   ret i32 %D
 ; CHECK-LABEL: @test15
 ; CHECK: and i1 %A, %B
 }
+
+; PR30256 - previously this asserted.
+; CHECK-LABEL: @test16
+; CHECK: %[[FACTOR:.*]] = mul i64 %a, -4
+; CHECK-NEXT: %[[RES:.*]] = add i64 %[[FACTOR]], %b
+; CHECK-NEXT: ret i64 %[[RES]]
+define i64 @test16(i1 %cmp, i64 %a, i64 %b) {
+entry:
+  %shl = shl i64 %a, 1
+  %shl.neg = sub i64 0, %shl
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %add1 = add i64 %shl.neg, %shl.neg
+  %add2 = add i64 %add1, %b
+  ret i64 %add2
+
+if.end:                                           ; preds = %entry
+  ret i64 0
+}