[InstCombine] Fold add nuw + uadd.with.overflow

[dlrobertson]

Summary

Fold add nuw and uadd.with.overflow with constants if the
addition does not overflow.

Part of https://bugs.llvm.org/show_bug.cgi?id=38146.

[dlrobertson]

D59472 has been created with the baseline tests

[lebedev.ri]

Looks reasonable, test coverage nits added.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2058–2061 ↗

(On Diff #191021)

Are these tested?

[dlrobertson]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

2058–2061 ↗

(On Diff #191021)

foldIntrinsicWithOverflowCommon is a very thin wrapper around OptimizeOverflowCheck which is tested in with_overflow.ll. I couldn't find any tests in which canonicalizeConstantArg0ToArg1 would be used. I can add a test for it in with_overflow.ll.

[dlrobertson]

Rebased on master

[lebedev.ri]

Looks reasonable, but maybe wait for @nikic / @spatel.

[spatel]

Logic looks fine, so I won't hold it up, but seems better to not duplicate code for sibling transforms?

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
index 49524d7f42e..9de4e60c1b9 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
@@ -2046,6 +2046,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) {
       return &CI;
     break;
   }
+  case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow: {
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
@@ -2053,25 +2054,28 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) {
       return I;
 
     // Given 2 constant operands whose sum does not overflow:
+    // uaddo (X +nuw C0), C1 -> uaddo X, C0 + C1
     // saddo (X +nsw C0), C1 -> saddo X, C0 + C1
+    bool IsUnsigned = II->getIntrinsicID() == Intrinsic::uadd_with_overflow;
     Value *X;
     const APInt *C0, *C1;
     Value *Arg0 = II->getArgOperand(0);
     Value *Arg1 = II->getArgOperand(1);
-    if (match(Arg0, m_NSWAdd(m_Value(X), m_APInt(C0))) &&
-        match(Arg1, m_APInt(C1))) {
+    bool HasAdd = IsUnsigned ? match(Arg0, m_NUWAdd(m_Value(X), m_APInt(C0)))
+                             : match(Arg0, m_NSWAdd(m_Value(X), m_APInt(C0)));
+    if (HasAdd && match(Arg1, m_APInt(C1))) {
       bool Overflow;
-      APInt NewC = C1->sadd_ov(*C0, Overflow);
+      APInt NewC = IsUnsigned ? C1->uadd_ov(*C0, Overflow)
+                              : C1->sadd_ov(*C0, Overflow);
       if (!Overflow)
         return replaceInstUsesWith(
             *II, Builder.CreateBinaryIntrinsic(
-                     Intrinsic::sadd_with_overflow, X,
+                     II->getIntrinsicID(), X,
                      ConstantInt::get(Arg1->getType(), NewC)));
     }
 
     break;
   }
-  case Intrinsic::uadd_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))

[lebedev.ri]

I agree, the duplication doesn't look nice.
It may indeed be better to condense the cases,
and have a standalone switch for more specific opts
that will come up in the future,

[dlrobertson]

In D59471#1435184, @spatel wrote:

Logic looks fine, so I won't hold it up, but seems better to not duplicate code for sibling transforms?

Your change looks much better. I wanted to do something like this initially, but I couldn't figure it out. I was missing getIntrinsicId. I'll update this shortly.

[dlrobertson]

Combine saddo and uaddo branch

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

case Intrinsic::fshr: {
     if (!isPowerOf2_32(BitWidth))
       break;
     APInt Op2Demanded = APInt::getLowBitsSet(BitWidth, Log2_32_Ceil(BitWidth));
     KnownBits Op2Known(BitWidth);
     if (SimplifyDemandedBits(II, 2, Op2Demanded, Op2Known))
       return &CI;
     break;
   }
+  case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow: {
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     if (Instruction *I = foldIntrinsicWithOverflowCommon(II))
       return I;
 
     // Given 2 constant operands whose sum does not overflow:
+    // uaddo (X +nuw C0), C1 -> uaddo X, C0 + C1
     // saddo (X +nsw C0), C1 -> saddo X, C0 + C1
     Value *X;
     const APInt *C0, *C1;
     Value *Arg0 = II->getArgOperand(0);
     Value *Arg1 = II->getArgOperand(1);
-    if (match(Arg0, m_NSWAdd(m_Value(X), m_APInt(C0))) &&
-        match(Arg1, m_APInt(C1))) {
+    bool IsSigned = II->getIntrinsicID() == Intrinsic::sadd_with_overflow;
+    bool HasNWAdd = IsSigned ? match(Arg0, m_NSWAdd(m_Value(X), m_APInt(C0)))
+                             : match(Arg0, m_NUWAdd(m_Value(X), m_APInt(C0)));
+    if (HasNWAdd && match(Arg1, m_APInt(C1))) {
       bool Overflow;
-      APInt NewC = C1->sadd_ov(*C0, Overflow);
+      APInt NewC =
+          IsSigned ? C1->sadd_ov(*C0, Overflow) : C1->uadd_ov(*C0, Overflow);
       if (!Overflow)
         return replaceInstUsesWith(
             *II, Builder.CreateBinaryIntrinsic(
-                     Intrinsic::sadd_with_overflow, X,
+                     II->getIntrinsicID(), X,
                      ConstantInt::get(Arg1->getType(), NewC)));
     }
-
     break;
   }
-  case Intrinsic::uadd_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (Instruction *I = canonicalizeConstantArg0ToArg1(CI))
       return I;
     LLVM_FALLTHROUGH;
 
   case Intrinsic::usub_with_overflow:
   case Intrinsic::ssub_with_overflow: {

llvm/trunk/test/Transforms/InstCombine/uadd-with-overflow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32>, <2 x i32>)
 
 declare { <2 x i8>, <2 x i1> } @llvm.uadd.with.overflow.v2i8(<2 x i8>, <2 x i8>)
 
 declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32)
 
 declare { i8, i1 } @llvm.uadd.with.overflow.i8(i8, i8)
 
 define { i32, i1 } @simple_fold(i32 %x) {
 ; CHECK-LABEL: @simple_fold(
-; CHECK-NEXT:    [[A:%.*]] = add nuw i32 [[X:%.*]], 7
-; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[A]], i32 13)
-; CHECK-NEXT:    ret { i32, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[X:%.*]], i32 20)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP1]]
 ;
   %a = add nuw i32 %x, 7
   %b = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %a, i32 13)
   ret { i32, i1 } %b
 }
 
 define { i8, i1 } @fold_on_constant_add_no_overflow(i8 %x) {
 ; CHECK-LABEL: @fold_on_constant_add_no_overflow(
-; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], -56
-; CHECK-NEXT:    [[B:%.*]] = tail call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[A]], i8 55)
-; CHECK-NEXT:    ret { i8, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[X:%.*]], i8 -1)
+; CHECK-NEXT:    ret { i8, i1 } [[TMP1]]
 ;
   %a = add nuw i8 %x, 200
   %b = tail call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 %a, i8 55)
   ret { i8, i1 } %b
 }
 
 define { i8, i1 } @no_fold_on_constant_add_overflow(i8 %x) {
 ; CHECK-LABEL: @no_fold_on_constant_add_overflow(

 ;
   %a = add nuw <2 x i8> %x, <i8 200, i8 201>
   %b = tail call { <2 x i8>, <2 x i1> } @llvm.uadd.with.overflow.v2i8(<2 x i8> %a, <2 x i8> <i8 55, i8 55>)
   ret { <2 x i8>, <2 x i1> } %b
 }
 
 define { <2 x i32>, <2 x i1> } @fold_simple_splat_constant(<2 x i32> %x) {
 ; CHECK-LABEL: @fold_simple_splat_constant(
-; CHECK-NEXT:    [[A:%.*]] = add nuw <2 x i32> [[X:%.*]], <i32 12, i32 12>
-; CHECK-NEXT:    [[B:%.*]] = tail call { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32> [[A]], <2 x i32> <i32 30, i32 30>)
-; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32> [[X:%.*]], <2 x i32> <i32 42, i32 42>)
+; CHECK-NEXT:    ret { <2 x i32>, <2 x i1> } [[TMP1]]
 ;
   %a = add nuw <2 x i32> %x, <i32 12, i32 12>
   %b = tail call { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32> %a, <2 x i32> <i32 30, i32 30>)
   ret { <2 x i32>, <2 x i1> } %b
 }
 
 define { <2 x i32>, <2 x i1> } @no_fold_splat_undef_constant(<2 x i32> %x) {
 ; CHECK-LABEL: @no_fold_splat_undef_constant(

 ;
   %a = add nuw <2 x i32> %x, %y
   %b = tail call { <2 x i32>, <2 x i1> } @llvm.uadd.with.overflow.v2i32(<2 x i32> %a, <2 x i32> <i32 30, i32 30>)
   ret { <2 x i32>, <2 x i1> } %b
 }
 
 define { i32, i1 } @fold_nuwnsw(i32 %x) {
 ; CHECK-LABEL: @fold_nuwnsw(
-; CHECK-NEXT:    [[A:%.*]] = add nuw nsw i32 [[X:%.*]], 12
-; CHECK-NEXT:    [[B:%.*]] = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[A]], i32 30)
-; CHECK-NEXT:    ret { i32, i1 } [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[X:%.*]], i32 42)
+; CHECK-NEXT:    ret { i32, i1 } [[TMP1]]
 ;
   %a = add nuw nsw i32 %x, 12
   %b = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %a, i32 30)
   ret { i32, i1 } %b
 }
 
 define { i32, i1 } @no_fold_nsw(i32 %x) {
 ; CHECK-LABEL: @no_fold_nsw(