Fixing inst-combine not to drops nsw when combining adds into mul (PR19263)

[dinesh.d]

Summary

I tried to fix this but I am not sure about few things.

1. We always convert (X * C1) + (X * C2) to X *(C1 + C2) even if (C1 + C2)

overflows. e.g.

%1 = mul nsw i32 %x, 2147483647
%2 = mul nsw i32 %x, 3
%3 = add nsw i32 %1, %2

becomes

%1 = mul i32 %x, -2147483646

Is this what we want. In that case, we can blindly copy nsw from
add instruction to mul instruction. If so, I will update this patch.

2. In this patch, I have tried not to combine add to mul for above case

but that is not enough to stop this conversion (getting converted from
some other code). If above conversion is wrong, I can go through code
and fix this. For now, this patch should take care of not dropping nsw
flags.

3. I haven't added similar checks in visitSub. Actually, all c examples,

I can come up with, was not creating sub with nsw. If is it required to
add similar check, I can update this patch.

[dinesh.d]

gentle ping

[dinesh.d]

gentle ping

[dinesh.d]

gentle ping

[• rafael]

+ if (ConstantInt *CI1 = dyn_cast<ConstantInt>(LHS))
+ if (ConstantInt *CI2 = dyn_cast<ConstantInt>(RHS)) {
+ APInt ACI1 = CI1->getValue();
+ APInt ACI2 = CI2->getValue();
+ bool IsLHSNegative = ACI1.isNegative();
+ bool IsRHSNegative = ACI2.isNegative();

If both are constants, the result should have been folded before
getting here, no?

Can you rebase on trunk? WillNotOverflowSignedAdd has learned a few
extra tricks.

[dinesh.d]

rebased code on trunk

[dinesh.d]

+ if (ConstantInt *CI1 = dyn_cast<ConstantInt>(LHS))
+ if (ConstantInt *CI2 = dyn_cast<ConstantInt>(RHS)) {
+ APInt ACI1 = CI1->getValue();
+ APInt ACI2 = CI2->getValue();
+ bool IsLHSNegative = ACI1.isNegative();
+ bool IsRHSNegative = ACI2.isNegative();

If both are constants, the result should have been folded before
getting here, no?

Here both constants are from different expression, one from LHS and other
one is from RHS.

Can you rebase on trunk? WillNotOverflowSignedAdd has learned a few
extra tricks.

rebased.

[• rafael]

Here both constants are from different expression, one from LHS and other
one is from RHS.

All tests still pass if I delete the extra logic from
WillNotOverflowSignedAdd. Can you add an extra test of split this off
to an independent patch?

Cheers,
Rafael

[• rafael]

All tests still pass if I delete the extra logic from
WillNotOverflowSignedAdd. Can you add an extra test of split this off
to an independent patch?

More importantly, it looks like this misoptimizes a few cases. For example,

define i16 @f(i16 %a) {

%b = mul i16 %a, 2
%c = mul i16 %a, 3
%d = add nsw i16 %b, %c
ret i16 %d

}

this would optimize it into

define i16 @f(i16 %a) {

%d = mul nsw i16 %a, 5
ret i16 %d

}

But I think that is invalid. There are inputs where the original add
would not overflow the add but the mul will. For example:

a = 0x2aab
b = 0x5556
c = 0x8001 the computation of c has an overflow, but that is fine
since the mul is not nws
d = 0xd557 no overflow in the add

Cheers,
Rafael

[dinesh.d]

Yes, now WillNotOverflowSignedAdd can handle cases where
one of LHS and RHS is power of 2 and other has known zero
after high bit in first one. I will update test accordingly or if you
think that should go as independent patch I can surely do that.

For you other comment, I think we can not have nsw in addition
of 2 variables even if any one of them is not known to have nsw.
So I think nsw in add is wrong. But I may be wrong.

How about this input
a = 0x2aaa
b = 0x5554
c = 0x7ffe
d = 0xd552

b and c are ok here as mul instructions does not guaranty either
(overflow or no overflow) but add instruction guaranties no sign
overflow and d is overflowing.

[dinesh.d]

updated patch as per comments

[• rafael]

There is an interesting organizational problem:

Given

define i16 @f(i16 %a) {

%b = mul nsw i16 %a, 3
%c = mul nsw i16 %a, 7
%d = add nsw i16 %b, %c
ret i16 %d

}

With your patch we produce

define i16 @f(i16 %a) {

%d = mul i16 %a, 10
ret i16 %d

}

but given

define i16 @f(i16 %a) {

%b = mul nsw i16 %a, 2
%c = mul nsw i16 %a, 7
%d = add nsw i16 %b, %c
ret i16 %d

}

it produces

define i16 @f(i16 %a) {

%d = mul nsw i16 %a, 9
ret i16 %d

}

The problem comes from some cases being transformed in
SimplifyUsingDistributiveLaws before getting to your code.

Maybe what should happen is that as an early cleanup patch
dyn_castFoldableMul should be moved and used by
SimplifyUsingDistributiveLaws which would now handle all relevant
cases.

What do you think?

[• rafael]

Yet another thing to be careful about. The proposed patch would have
disable the combining in

define i16 @f(i16 %a) {

%b = mul i16 %a, 2
%c = mul i16 %a, 32767
%d = add i16 %b, %c
ret i16 %d

}

I added the testcase in r210287.

[dinesh.d]

I agree with the idea that these cases should get handled in SimplifyUsingDistributiveLaws and
I am working on generalized approach for that.

I have updated patch to just put following changes in record.
I have removed check for overflow because after analyzing few cases, I think we should not
disable transformation to pattern like this even if (2 + 32767)

%b = mul i16 %a, 2
%c = mul i16 %a, 32767
%d = add i16 %b, %c
ret i16 %d

as original case and transformed case will result in same output. When I pointed out case similar to
this, I thought that for some value of 'a', '(b+c)' might be positive but if we add constant which will become
negative due to overflow, result will mismatch.
I realized that as 'a' in integer, if a == 0, we will get 0 in any case and any value of a > 0, b and c will never
be less than 2 and 32767 respectively. so add result will always overflow.

What do you think? Should be disable above transform.

I have added a TODO to fix transform happening in SimplifyUsingDistributiveLaws and dropping nsw.
I will update it soon so that all these pattern gets handle in SimplifyUsingDistributiveLaws.

[dinesh.d]

moved dyn_castFoldableMul logic to InstructionCombining.cpp.
Now SimplifyUsingDistributiveLaws handles all relevant cases.

[dinesh.d]

gentle ping

[• rafael]

Looks a lot better, thanks.

lib/Transforms/InstCombine/InstructionCombining.cpp

400 ↗

(On Diff #10270)

Please name functions starting with a lowercase letter.
This function can be static.

418 ↗

(On Diff #10270)

lowercase, static.

It seems a bit strange to return one operand and put the other one in an out value. Also, this function doesn't do the factorization, it just splits the expression.

Also, the above function for handling 1 could be merged into this (and with that avoid the extra indentation), no? Something like

Try to split Op0 and Op1 into (A op B) and (C op D) with the same operation
in both. This handles cases like matching a shift as a mul and B or D being
// implicitly 1.
static bool matchForFactorization(const BinaryOperator *Op0,

const BinaryOperator *Op1,
Instruction::BinaryOps &OpCode, Value *&A,
Value *&B, Value *&C, Value *&D)

[jingyue]

Hi Dinesh,

It looks pretty good overall. Thanks for working on this! Please find my comments inlined.

lib/Transforms/InstCombine/InstructionCombining.cpp

445 ↗

(On Diff #10270)

I'd move these definitions closer to their uses. e.g.,

Value *B = nullptr, *D = nullptr;
Value *A = FactorBinaryOps(Op0, B, LHSOpcode);

452 ↗

(On Diff #10270)

Correct me if I'm wrong. I think the current logic seems unable to convert

%z = mul nsw i32 %x, %y
%z3 = mul nsw i32 %z, 3
%z4 = add nsw i32 %z, %z3

to

%z = mul nsw i32 %x, %y
%z4 = mul nsw i32 %z, 4

because if %z is in the format of %x * %y, you will not try the identity factorization (i.e., %z * 1).

If it is indeed a missed opportunity, it may not be too difficult to cover. For example, we can try all four combinations:

1. LHS (binary op), RHS (binary op)
2. LHS (identity), RHS (binary op)
3. LHS (binary op), RHS (identity)
4. LHS (identity), RHS (identity) // probably already handled somewhere else?

Anyway, we can do this later.

466 ↗

(On Diff #10270)

I feel the logic of this IF and next IF (if (RightDistributesOverLeft) a bit difficult to follow. There is also some copy and paste. What about extracting the check on InnerCommutative out? Something like:

try(a, b, c, d);
if (op' is commutative) {
  try(b, a, c, d);
  try(a, b, d, c);
  try(b, a, c, d);
}

By doing this, inside each "try", we don't need to think about whether op' is commutative.

What do you think?

[dinesh.d]

Update patch as per review comments

[dinesh.d]

Thanks for review. I ahve added comments inline.

lib/Transforms/InstCombine/InstructionCombining.cpp

400 ↗

(On Diff #10270)

updated.

I have kept this funtion so it can be used to get identity values
for other operations e.g. and, or etc. as well.

418 ↗

(On Diff #10270)

Update function name and added static.
I have to keep both function separate to try to explore optimization, jingyue
has mentioned in his comment.

I have changed function parameter and return value. Let me know if it looks ok.

445 ↗

(On Diff #10270)

updated.

452 ↗

(On Diff #10270)

updated. New patch takes care of all except LHS (identity), RHS (identity).
it is getting handled before SimplifyUsingDistributiveLaws called.

466 ↗

(On Diff #10270)

Updated patch to handle this. We can not just depend on isCommutative as
there are oparation which are not commutative but still can be distributed e.g.
"(X + Y) / Z = X/Z + Y/Z"

We do not handle this now but we might want to do it in future.

[jingyue]

lib/Transforms/InstCombine/InstructionCombining.cpp

466 ↗

(On Diff #10270)

I think the first "try" in my pseudo-code handle this case. Right?

While "try" doesn't swap a and b or c and d, it considers both LeftDistributesOverRight and RightDistributesOverLeft. Therefore, it is able to convert "a / b + c / d" to "(a + c) / d".

[dinesh.d]

lib/Transforms/InstCombine/InstructionCombining.cpp

466 ↗

(On Diff #10270)

Yes, if we considers both LeftDistributesOverRight and RightDistributesOverLeft, it handles all cases.
But then I think current code is handling all cases more efficiently.

If left distributes over right and inner op is commutative, then right will also distribute over left
too and vice versa. So Checking following 2 combinations if left distributes over right

try(a, b, c, d);
if (op' is commutative) {
  try(a, b, d, c);
}

and following 2 combination if right distributes ove left should be sufficient.

try(a, b, c, d);
if (op' is commutative) {
  try(a, b, d, c);
}

Because for inner commutative operation

if try(a, b, c, d) fails for LeftDistributesOverRight then try(b, a, d, c) will fail for RightDistributesOverLeft
if try(a, b, c, d) fails for RightDistributesOverLeft then try(b, a, d, c) will fail for LeftDistributesOverRight

similarly

if try(b, a, c, d) fails for LeftDistributesOverRight then try(a, b, d, c) will fail for RightDistributesOverLeft
if try(a, b, c, d) fails for RightDistributesOverLeft then try(a, b, d, c) will fail for LeftDistributesOverRight

Am I missing something?

[dinesh.d]

typo :(

lib/Transforms/InstCombine/InstructionCombining.cpp

466 ↗

(On Diff #10270)

Please read last line in previous reply as
if try(b, a, c, d) fails for RightDistributesOverLeft then try(a, b, d, c) will fail for LeftDistributesOverRight

[• rafael]

Still reading the code, just wanted to post the easy bits first.

lib/Transforms/InstCombine/InstructionCombining.cpp

398 ↗

(On Diff #10499)

Nit: don't duplicate the function name in the comment.

418 ↗

(On Diff #10499)

same

442 ↗

(On Diff #10499)

here too.

[• rafael]

Mostly nits. This is LGTM with the issues on line 552 addressed, but please wait for Jingyue Wu to confirm that he is OK with it too.

Thanks!

lib/Transforms/InstCombine/InstructionCombining.cpp

415 ↗

(On Diff #10499)

You have both a default case with a return and a return after the switch.

Given that we only handle Mul, it is probably better to write this as an if for now. When we add support for other opcodes it is easy to go back to an switch.

552 ↗

(On Diff #10499)

This should be

if (Value *V = tryFactorization(Builder, DL, I, RHSOpcode, LHS,
                                getIdentityValue(LHSOpcode, LHS), C, D))

no?

[jingyue]

lib/Transforms/InstCombine/InstructionCombining.cpp

481 ↗

(On Diff #10499)

Do we still need to try right distribution if left distribution already succeeds?

494 ↗

(On Diff #10499)

A question: any chance to preserve NSW/NUW for TopLevelOpcode?

508 ↗

(On Diff #10499)

I think it's better to write:

if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) {
  if (isa<OverflowingBinaryOperator>(Op0)) {
    HasNSW &= Op0->hasNoSignedWrap();
}

515 ↗

(On Diff #10499)

I may be over-concerned, but is this cast dangerous? CreateBinOp returns a ConstantExpr if its operands are both Constant. Note that ConstantInt op ConstantInt is not always foldable, e.g., ptrtoint (a global variable) + 5.

543 ↗

(On Diff #10499)

(A op' B) op (C)?

466 ↗

(On Diff #10270)

Good point. I agree

try(a, b, c, d);
if (op' is commutative) {
  try(a, b, d, c);
}

is enough.

[dinesh.d]

Thanks for review and comments. I have replied them inline.

lib/Transforms/InstCombine/InstructionCombining.cpp

398 ↗

(On Diff #10499)

updated.

415 ↗

(On Diff #10499)

updated.

418 ↗

(On Diff #10499)

updated.

442 ↗

(On Diff #10499)

updated.

481 ↗

(On Diff #10499)

No. We should not. I have updated code to check if left distribution already succeeds

494 ↗

(On Diff #10499)

I will try to do that in next patches.

508 ↗

(On Diff #10499)

updated.

515 ↗

(On Diff #10499)

We have already check if 'isa<OverflowingBinaryOperator>(SimplifiedInst)' so casting SimplifiedInst to BinaryOperator should be safe.

543 ↗

(On Diff #10499)

updated.

552 ↗

(On Diff #10499)

updated code. last minute copy paste issue. it should be

getIdentityValue(RHSOpcode, LHS)

I will be more carefull to avoid these mistakes.

[dinesh.d]

Updated patch as per comments. Thanks for review.

[jingyue]

Only one nit, otherwise LGTM.

lib/Transforms/InstCombine/InstructionCombining.cpp

515 ↗

(On Diff #10499)

http://llvm.org/docs/doxygen/html/classllvm_1_1OverflowingBinaryOperator.html

OverflowingBinaryOperator is not a subclass of BinaryOperator. BinaryOperator is an Instruction, but OverflowingBinaryOperator can be either an Instruction or a ConstantExpr.

I agree the naming is a little confusing :)

[dinesh.d]

Thanks for review. I have updated cast<BinaryOperator>(SimplifiedInst) to use dyn_cast.

[dinesh.d]

Closed by commit rL211261 (authored by dinesh).

lib/Transforms/InstCombine/InstCombineAddSub.cpp

 }
 
 // dyn_castFoldableMul - If this value is a multiply that can be folded into
 // other computations (because it has a constant operand), return the
 // non-constant operand of the multiply, and set CST to point to the multiplier.
 // Otherwise, return null.
 //
 static inline Value *dyn_castFoldableMul(Value *V, Constant *&CST) {
-  if (!V->hasOneUse() || !V->getType()->isIntOrIntVectorTy())
+  if (!V->getType()->isIntOrIntVectorTy())
     return nullptr;
 
-  Instruction *I = dyn_cast<Instruction>(V);
-  if (!I) return nullptr;
-
+  if (V->hasOneUse()) {
+    if (Instruction *I = dyn_cast<Instruction>(V)) {
       if (I->getOpcode() == Instruction::Mul)
         if ((CST = dyn_cast<Constant>(I->getOperand(1))))
           return I->getOperand(0);
       if (I->getOpcode() == Instruction::Shl)
         if ((CST = dyn_cast<Constant>(I->getOperand(1)))) {
           // The multiplier is really 1 << CST.
           CST = ConstantExpr::getShl(ConstantInt::get(V->getType(), 1), CST);
           return I->getOperand(0);
         }
-  return nullptr;
+    }
+  }
+
+  CST = ConstantInt::get(V->getType(), 1);
+  return V;
 }
 
 // If one of the operands only has one non-zero bit, and if the other
 // operand has a known-zero bit in a more significant place than it (not
 // including the sign bit) the ripple may go up to and fill the zero, but
 // won't change the sign. For example, (X & ~4) + 1.
 static bool checkRippleForAdd(const APInt &Op0KnownZero,
                               const APInt &Op1KnownZero) {
if (Value *LHSV = dyn_castNegVal(LHS)) {
     return BinaryOperator::CreateSub(RHS, LHSV);
   }
 
   // A + -B  -->  A - B
   if (!isa<Constant>(RHS))
     if (Value *V = dyn_castNegVal(RHS))
       return BinaryOperator::CreateSub(LHS, V);
 
-
   {
-    Constant *C2;
-    if (Value *X = dyn_castFoldableMul(LHS, C2)) {
-      if (X == RHS) // X*C + X --> X * (C+1)
-        return BinaryOperator::CreateMul(RHS, AddOne(C2));
-
-      // X*C1 + X*C2 --> X * (C1+C2)
-      Constant *C1;
-      if (X == dyn_castFoldableMul(RHS, C1))
-        return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2));
-    }
+    Constant *C1, *C2;
+    // X * C1 + X * C2 --> X * (C1 + C2)
+    if (Value *X = dyn_castFoldableMul(LHS, C1))
+      if (Value *Y = dyn_castFoldableMul(RHS, C2)) {
+        if ((X == Y) && WillNotOverflowSignedAdd(C1, C2)) {
+          if (BinaryOperator *NewInst =
+                  BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2))) {
+
+            bool hasNSW = I.hasNoSignedWrap();
+            if (BinaryOperator *LHSI = dyn_cast<BinaryOperator>(LHS))
+              hasNSW &= LHSI->hasNoSignedWrap();
+            if (BinaryOperator *RHSI = dyn_cast<BinaryOperator>(RHS))
+              hasNSW &= RHSI->hasNoSignedWrap();
 
-    // X + X*C --> X * (C+1)
-    if (dyn_castFoldableMul(RHS, C2) == LHS)
-      return BinaryOperator::CreateMul(LHS, AddOne(C2));
+            NewInst->setHasNoSignedWrap(hasNSW);
+
+            // TODO: Check for unsigned wrap
+            return NewInst;
+          }
+        }
+      }
   }
 
   // A+B --> A|B iff A and B have no bits set in common.
   if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
     APInt LHSKnownOne(IT->getBitWidth(), 0);
     APInt LHSKnownZero(IT->getBitWidth(), 0);
     computeKnownBits(LHS, LHSKnownZero, LHSKnownOne);
     if (LHSKnownZero != 0) {
if (Op1->hasOneUse()) {
     // X - CI*A -> X + A*-CI
     if (match(Op1, m_Mul(m_Value(A), m_Constant(CI))) ||
         match(Op1, m_Mul(m_Constant(CI), m_Value(A)))) {
       Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI));
       return BinaryOperator::CreateAdd(Op0, NewMul);
     }
   }
 
-  Constant *C1;
-  if (Value *X = dyn_castFoldableMul(Op0, C1)) {
-    if (X == Op1)  // X*C - X --> X * (C-1)
-      return BinaryOperator::CreateMul(Op1, SubOne(C1));
-
-    Constant *C2;   // X*C1 - X*C2 -> X * (C1-C2)
-    if (X == dyn_castFoldableMul(Op1, C2))
+  Constant *C1, *C2;
+  // X * C1 - X * C2 --> X * (C1 - C2)
+  if (Value *X = dyn_castFoldableMul(Op0, C1))
+    if (Value *Y = dyn_castFoldableMul(Op1, C2))
+      if (X == Y)
         return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2));
-  }
 
   // Optimize pointer differences into the same array into a size.  Consider:
   //  &A[10] - &A[0]: we should compile this to "10".
   if (DL) {
     Value *LHSOp, *RHSOp;
     if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
         match(Op1, m_PtrToInt(m_Value(RHSOp))))
       if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))

test/Transforms/InstCombine/add2.ll

 define <2 x i64> @test8(<2 x i64> %A) {
   %xor = xor <2 x i64> %A, <i64 -1, i64 -1>
   %add = add <2 x i64> %xor, <i64 2, i64 3>
   ret <2 x i64> %add
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT: %add = sub <2 x i64> <i64 1, i64 2>, %A
 ; CHECK-NEXT: ret <2 x i64> %add
 }
+
+define i32 @add_nsw_mul_nsw(i32 %x) {
+  %add1 = add nsw i32 %x, %x
+  %add2 = add nsw i32 %add1, %x
+  ret i32 %add2
+; CHECK-LABEL: @add_nsw_mul_nsw(
+; CHECK-NEXT: %add2 = mul nsw i32 %x, 3
+; CHECK-NEXT: ret i32 %add2
+}
+
+define i32 @mul_add_to_mul_1(i32 %x) {
+  %mul1 = mul nsw i32 %x, 8
+  %add2 = add nsw i32 %x, %mul1
+  ret i32 %add2
+; CHECK-LABEL: @mul_add_to_mul_1(
+; CHECK-NEXT: %add2 = mul nsw i32 %x, 9
+; CHECK-NEXT: ret i32 %add2
+}
+
+define i32 @mul_add_to_mul_2(i32 %x) {
+  %mul1 = mul nsw i32 %x, 8
+  %add2 = add nsw i32 %mul1, %x
+  ret i32 %add2
+; CHECK-LABEL: @mul_add_to_mul_2(
+; CHECK-NEXT: %add2 = mul nsw i32 %x, 9
+; CHECK-NEXT: ret i32 %add2
+}
+
+define i16 @mul_add_to_mul_3(i16 %a) {
+  %b = mul i16 %a, 2
+  %c = mul i16 %a, 3
+  %d = add nsw i16 %b, %c
+  ret i16 %d
+; CHECK-LABEL: @mul_add_to_mul_3(
+; CHECK-NEXT: %d = mul i16 %a, 5
+; CHECK-NEXT: ret i16 %d
+}
 No newline at end of file