[InstCombine] Propagate the nuw for combine of add+mul

[Allen]

Summary

As the commit of D132658, make the 'nuw' change separately.

[spatel]

Please include a general proof link to Alive2.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

236

To be safe, use "dyn_cast" here. I don't have an example, but it is possible that the builder can constant fold the multiply, so the NewMul is not a BinaryOperator at this point.

llvm/test/Transforms/InstCombine/mul.ll

628

Do we have tests where only the add or only the mul has nuw?

[Allen]

1. add new test case with only mull or add has nuw
2. add checking dyn_cast<BinaryOperator>(NewMul)

[spatel]

LGTM - see inline comment for minor change.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

237

It is better to use the normal LLVM code pattern instead of using both dyn_cast and cast:

if (auto *NewMulBO = dyn_cast<BinaryOperator>(NewMul))
  NewMulBO->setHasNoUnsignedWrap();

[Allen]

Address comment to use the normal LLVM code pattern

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) {
 
   if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
     return FoldedMul;
 
   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
     return replaceInstUsesWith(I, FoldedMul);
 
   // Simplify mul instructions with a constant RHS.
-  if (isa<Constant>(Op1)) {
-    // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
+  Constant *MulC;
+  if (match(Op1, m_ImmConstant(MulC))) {
+    // Canonicalize (X+C1)*MulC -> X*MulC+C1*MulC.
     Value *X;
     Constant *C1;
-    if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
-      Value *Mul = Builder.CreateMul(C1, Op1);
-      // Only go forward with the transform if C1*CI simplifies to a tidier
-      // constant.
-      if (!match(Mul, m_Mul(m_Value(), m_Value())))
-        return BinaryOperator::CreateAdd(Builder.CreateMul(X, Op1), Mul);
+    if (match(Op0, m_OneUse(m_Add(m_Value(X), m_ImmConstant(C1))))) {
+      // C1*MulC simplifies to a tidier constant.
+      Value *NewC = Builder.CreateMul(C1, MulC);
+      auto *BOp0 = cast<BinaryOperator>(Op0);
+      Value *NewMul = Builder.CreateMul(X, MulC);
+      auto *BO = BinaryOperator::CreateAdd(NewMul, NewC);
+      auto *NewMulBO = dyn_cast<BinaryOperator>(NewMul);
+      if (I.hasNoUnsignedWrap() && BOp0->hasNoUnsignedWrap() && NewMulBO) {
+        NewMulBO->setHasNoUnsignedWrap();
+        BO->setHasNoUnsignedWrap();
+      }
+      return BO;
     }
   }
 
   // abs(X) * abs(X) -> X * X
   // nabs(X) * nabs(X) -> X * X
   if (Op0 == Op1) {
     Value *X, *Y;
     SelectPatternFlavor SPF = matchSelectPattern(Op0, X, Y).Flavor;

llvm/test/Transforms/InstCombine/mul.ll

 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[ADD]], ptrtoint (i32* @g to i32)
 ; CHECK-NEXT:    ret i32 [[MUL]]
 ;
   %add = add i32 %a, -1
   %mul = mul nsw i32 %add, ptrtoint (i32* @g to i32)
   ret i32 %mul
 }
 
+; Keep nuw flag in this change, https://alive2.llvm.org/ce/z/-Wowpk
+define i32 @add_mul_nuw(i32 %a) {
+; CHECK-LABEL: @add_mul_nuw(
+; CHECK-NEXT:    [[TMP1:%.*]] = mul nuw i32 [[A:%.*]], 3
+; CHECK-NEXT:    [[MUL:%.*]] = add nuw i32 [[TMP1]], 9
+; CHECK-NEXT:    ret i32 [[MUL]]
+;
+  %add = add nuw i32 %a, 3
+  %mul = mul nuw i32 %add, 3
+  ret i32 %mul
+}
+
+; Don't propagate nsw flag in this change
+define i32 @add_mul_nsw(i32 %a) {
+; CHECK-LABEL: @add_mul_nsw(
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[A:%.*]], 3
+; CHECK-NEXT:    [[MUL:%.*]] = add i32 [[TMP1]], 9
+; CHECK-NEXT:    ret i32 [[MUL]]
+;
+  %add = add nsw i32 %a, 3
+  %mul = mul nsw i32 %add, 3
+  ret i32 %mul
+}
+
+; Only the add or only the mul has nuw, https://alive2.llvm.org/ce/z/vPwbEa
+define i32 @only_add_nuw(i32 %a) {
+; CHECK-LABEL: @only_add_nuw(
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[A:%.*]], 3
+; CHECK-NEXT:    [[MUL:%.*]] = add i32 [[TMP1]], 9
+; CHECK-NEXT:    ret i32 [[MUL]]
+;
+  %add = add nuw i32 %a, 3
+  %mul = mul i32 %add, 3
+  ret i32 %mul
+}
+
+define i32 @only_mul_nuw(i32 %a) {
+; CHECK-LABEL: @only_mul_nuw(
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[A:%.*]], 3
+; CHECK-NEXT:    [[MUL:%.*]] = add i32 [[TMP1]], 9
+; CHECK-NEXT:    ret i32 [[MUL]]
+;
+  %add = add i32 %a, 3
+  %mul = mul nuw i32 %add, 3
+  ret i32 %mul
+}
+
 define <2 x i1> @test21(<2 x i1> %A, <2 x i1> %B) {
 ; CHECK-LABEL: @test21(
 ; CHECK-NEXT:    [[C:%.*]] = and <2 x i1> [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %C = mul <2 x i1> %A, %B
   ret <2 x i1> %C
 }