[InstCombine] Don't propagate nsw for A*B+A*C => A*(B+C).

[sanjoy]

Summary

InstCombine transform A *nsw B +nsw A *nsw C to A *nsw (B + C).
This is incorrect -- e.g. if A = -1, B = 1, C = INT_SMAX. Then
nothing in the LHS overflows, but the multiplication in RHS overflows.

I'll have to admit that this proposed fix is a bit heavy-handed -- if
you think this will materially affect optimization then we can try to do
this transform for cases where we can prove correctness. For instance,
I *think* (but have not proved) that we can transform `(A +nsw A) +nsw
A` to A *nsw 3.

[majnemer]

test/Transforms/InstCombine/add2.ll

209–213 ↗

(On Diff #25386)

This transform is correct, would it be hard to keep it from breaking?

218–222 ↗

(On Diff #25386)

Yep. This transform would give us back poison if '8' were replaced with '32767'. However, it is safe to do (%x *nsw C) + %x => %x *nsw (C+1) if we know that (C != ((1 << (width(%x) - 1)) - 1))

246–261 ↗

(On Diff #25386)

A *nsw B+A *nsw C => A *nsw (B+C) is safe when ((B + C) != -(1 << (width(%a) - 1))) How hard would this be to implement?

[sanjoy]

test/Transforms/InstCombine/add2.ll

209–213 ↗

(On Diff #25386)

No, it won't be hard.

I have to admit I was lazier than usual when making this change. I'll send in a more aggressive version soon.

246–261 ↗

(On Diff #25386)

How hard would this be to implement?

I guess we can just ask ValueTracking on what the constraints on the values feeding in to the expression are. I'm not sure how effective ValueTracking will be at discovering these ranges though, in practice.

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

static Value *tryFactorization(InstCombiner::BuilderTy *Builder,
                                Instruction::BinaryOps InnerOpcode, Value *A,
                                Value *B, Value *C, Value *D) {
 
   // If any of A, B, C, D are null, we can not factor I, return early.
   // Checking A and C should be enough.
   if (!A || !C || !B || !D)
     return nullptr;
 
+  Value *V = nullptr;
   Value *SimplifiedInst = nullptr;
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
 
   // Does "X op' Y" always equal "Y op' X"?
   bool InnerCommutative = Instruction::isCommutative(InnerOpcode);
 
   // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"?
   if (LeftDistributesOverRight(InnerOpcode, TopLevelOpcode))
     // 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 *V = SimplifyBinOp(TopLevelOpcode, B, D, DL);
+      V = SimplifyBinOp(TopLevelOpcode, B, D, DL);
       // If "B op D" doesn't simplify then only go on if both of the existing
       // operations "A op' B" and "C op' D" will be zapped as no longer used.
       if (!V && LHS->hasOneUse() && RHS->hasOneUse())
         V = Builder->CreateBinOp(TopLevelOpcode, B, D, RHS->getName());
       if (V) {
         SimplifiedInst = Builder->CreateBinOp(InnerOpcode, A, V);
       }
     }
 
   // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"?
   if (!SimplifiedInst && RightDistributesOverLeft(TopLevelOpcode, InnerOpcode))
     // 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 *V = SimplifyBinOp(TopLevelOpcode, A, C, DL);
+      V = SimplifyBinOp(TopLevelOpcode, A, C, DL);
 
       // If "A op C" doesn't simplify then only go on if both of the existing
       // operations "A op' B" and "C op' D" will be zapped as no longer used.
       if (!V && LHS->hasOneUse() && RHS->hasOneUse())
         V = Builder->CreateBinOp(TopLevelOpcode, A, C, LHS->getName());
       if (V) {
         SimplifiedInst = Builder->CreateBinOp(InnerOpcode, V, B);
       }
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SimplifiedInst)) {
 
         if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
           if (isa<OverflowingBinaryOperator>(Op0))
             HasNSW &= Op0->hasNoSignedWrap();
 
         if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
           if (isa<OverflowingBinaryOperator>(Op1))
             HasNSW &= Op1->hasNoSignedWrap();
+
+        // We can propogate 'nsw' if we know that
+        //  %Y = mul nsw i16 %X, C
+        //  %Z = add nsw i16 %Y, %X
+        // =>
+        //  %Z = mul nsw i16 %X, C+1
+        //
+        // iff C+1 isn't INT_MIN
+        const APInt *CInt;
+        if (TopLevelOpcode == Instruction::Add &&
+            InnerOpcode == Instruction::Mul)
+          if (match(V, m_APInt(CInt)) && !CInt->isMinSignedValue())
             BO->setHasNoSignedWrap(HasNSW);
       }
     }
   }
   return SimplifiedInst;
 }
 
 /// SimplifyUsingDistributiveLaws - This tries to simplify binary operations
 /// which some other binary operation distributes over either by factorizing

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

define i32 @mul_add_to_mul_6(i32 %x, i32 %y) {
   %add = add nsw i32 %mul1, %mul2
   ret i32 %add
 ; CHECK-LABEL: @mul_add_to_mul_6(
 ; CHECK-NEXT: %mul1 = mul nsw i32 %x, %y
 ; CHECK-NEXT: %add = mul nsw i32 %mul1, 6
 ; CHECK-NEXT: ret i32 %add
 }
 
+define i16 @mul_add_to_mul_7(i16 %x) {
+  %mul1 = mul nsw i16 %x, 32767
+  %add2 = add nsw i16 %x, %mul1
+  ret i16 %add2
+; CHECK-LABEL: @mul_add_to_mul_7(
+; CHECK-NEXT: %add2 = shl i16 %x, 15
+; CHECK-NEXT: ret i16 %add2
+}
+
+define i16 @mul_add_to_mul_8(i16 %a) {
+  %mul1 = mul nsw i16 %a, 16383
+  %mul2 = mul nsw i16 %a, 16384
+  %add = add nsw i16 %mul1, %mul2
+  ret i16 %add
+; CHECK-LABEL: @mul_add_to_mul_8(
+; CHECK-NEXT: %add = mul nsw i16 %a, 32767
+; CHECK-NEXT: ret i16 %add
+}
+
+define i16 @mul_add_to_mul_9(i16 %a) {
+  %mul1 = mul nsw i16 %a, 16384
+  %mul2 = mul nsw i16 %a, 16384
+  %add = add nsw i16 %mul1, %mul2
+  ret i16 %add
+; CHECK-LABEL: @mul_add_to_mul_9(
+; CHECK-NEXT: %add = shl i16 %a, 15
+; CHECK-NEXT: ret i16 %add
+}
+
 ; This test and the next test verify that when a range metadata is attached to
 ; llvm.cttz, ValueTracking correctly intersects the range specified by the
 ; metadata and the range implied by the intrinsic.
 ;
 ; In this test, the range specified by the metadata is more strict. Therefore,
 ; ValueTracking uses that range.
 define i16 @add_cttz(i16 %a) {
 ; CHECK-LABEL: @add_cttz(
define i32 @add_nuw_nsw_or_and(i32 %x, i32 %y) {
   %or = or i32 %x, %y
   %and = and i32 %x, %y
   %add = add nsw nuw i32 %or, %and
   ret i32 %add
 ; CHECK-LABEL: @add_nuw_nsw_or_and(
 ; CHECK-NEXT: add nuw nsw i32 %x, %y
 ; CHECK-NEXT: ret i32
 }
+
+; A *nsw B + A *nsw C != A *nsw (B + C)
+; e.g. A = -1, B = 1, C = INT_SMAX
+
+define i8 @add_of_mul(i8 %x, i8 %y, i8 %z) {
+; CHECK-LABEL: @add_of_mul(
+ entry:
+  %mA = mul nsw i8 %x, %y
+  %mB = mul nsw i8 %x, %z
+; CHECK: %sum = mul i8
+  %sum = add nsw i8 %mA, %mB
+  ret i8 %sum
+}