[InstCombine] Combine saturating add/sub with constant operands

Combine
  sat(sat(X + C1) + C2) -> sat(X + (C1+C2))
and
  sat(sat(X - C1) - C2) -> sat(X - (C1+C2))
if the sign of C1 and C2 matches.

In the unsigned case we can compute C1+C2 with saturating arithmetic,
and InstSimplify will reduce this just to the saturation value. For
the signed case, we cannot perform the simplification if the result
of the addition overflows.

This change is part of https://reviews.llvm.org/D54534.

llvm-svn: 347773

2 files changed, 64 insertions, 52 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
index a6921d745e8..f0b09e1f0bd 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
@@ -2113,6 +2113,40 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) {
           *II, Builder.CreateBinaryIntrinsic(
               Intrinsic::sadd_sat, Arg0, NegVal));
     }
+
+    // sat(sat(X + Val2) + Val) -> sat(X + (Val+Val2))
+    // sat(sat(X - Val2) - Val) -> sat(X - (Val+Val2))
+    // if Val and Val2 have the same sign
+    if (auto *Other = dyn_cast<IntrinsicInst>(Arg0)) {
+      Value *X;
+      const APInt *Val, *Val2;
+      APInt NewVal;
+      bool IsUnsigned =
+          IID == Intrinsic::uadd_sat || IID == Intrinsic::usub_sat;
+      if (Other->getIntrinsicID() == II->getIntrinsicID() &&
+          match(Arg1, m_APInt(Val)) &&
+          match(Other->getArgOperand(0), m_Value(X)) &&
+          match(Other->getArgOperand(1), m_APInt(Val2))) {
+        if (IsUnsigned)
+          NewVal = Val->uadd_sat(*Val2);
+        else if (Val->isNonNegative() == Val2->isNonNegative()) {
+          bool Overflow;
+          NewVal = Val->sadd_ov(*Val2, Overflow);
+          if (Overflow) {
+            // Both adds together may add more than SignedMaxValue
+            // without saturating the final result.
+            break;
+          }
+        } else {
+          // Cannot fold saturated addition with different signs.
+          break;
+        }
+
+        return replaceInstUsesWith(
+            *II, Builder.CreateBinaryIntrinsic(
+                     IID, X, ConstantInt::get(II->getType(), NewVal)));
+      }
+    }
     break;
   }
 
diff --git a/llvm/test/Transforms/InstCombine/saturating-add-sub.ll b/llvm/test/Transforms/InstCombine/saturating-add-sub.ll
index e91abd1446b..060ecf4077c 100644
--- a/llvm/test/Transforms/InstCombine/saturating-add-sub.ll
+++ b/llvm/test/Transforms/InstCombine/saturating-add-sub.ll
@@ -51,9 +51,8 @@ define <2 x i8> @test_vector_sadd_canonical(<2 x i8> %a) {
 ; Can combine uadds with constant operands.
 define i8 @test_scalar_uadd_combine(i8 %a) {
 ; CHECK-LABEL: @test_scalar_uadd_combine(
-; CHECK-NEXT:    [[X1:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[X2:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[X1]], i8 20)
-; CHECK-NEXT:    ret i8 [[X2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A:%.*]], i8 30)
+; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %x1 = call i8 @llvm.uadd.sat.i8(i8 %a, i8 10)
   %x2 = call i8 @llvm.uadd.sat.i8(i8 %x1, i8 20)
@@ -62,9 +61,8 @@ define i8 @test_scalar_uadd_combine(i8 %a) {
 
 define <2 x i8> @test_vector_uadd_combine(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_uadd_combine(
-; CHECK-NEXT:    [[X1:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 10, i8 10>)
-; CHECK-NEXT:    [[X2:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[X1]], <2 x i8> <i8 20, i8 20>)
-; CHECK-NEXT:    ret <2 x i8> [[X2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 30, i8 30>)
+; CHECK-NEXT:    ret <2 x i8> [[TMP1]]
 ;
   %x1 = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 10, i8 10>)
   %x2 = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> %x1, <2 x i8> <i8 20, i8 20>)
@@ -86,9 +84,7 @@ define <2 x i8> @test_vector_uadd_combine_non_splat(<2 x i8> %a) {
 ; Can combine uadds even if they overflow.
 define i8 @test_scalar_uadd_overflow(i8 %a) {
 ; CHECK-LABEL: @test_scalar_uadd_overflow(
-; CHECK-NEXT:    [[Y1:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A:%.*]], i8 100)
-; CHECK-NEXT:    [[Y2:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[Y1]], i8 -56)
-; CHECK-NEXT:    ret i8 [[Y2]]
+; CHECK-NEXT:    ret i8 -1
 ;
   %y1 = call i8 @llvm.uadd.sat.i8(i8 %a, i8 100)
   %y2 = call i8 @llvm.uadd.sat.i8(i8 %y1, i8 200)
@@ -97,9 +93,7 @@ define i8 @test_scalar_uadd_overflow(i8 %a) {
 
 define <2 x i8> @test_vector_uadd_overflow(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_uadd_overflow(
-; CHECK-NEXT:    [[Y1:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 100, i8 100>)
-; CHECK-NEXT:    [[Y2:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[Y1]], <2 x i8> <i8 -56, i8 -56>)
-; CHECK-NEXT:    ret <2 x i8> [[Y2]]
+; CHECK-NEXT:    ret <2 x i8> <i8 -1, i8 -1>
 ;
   %y1 = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 100, i8 100>)
   %y2 = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> %y1, <2 x i8> <i8 200, i8 200>)
@@ -109,9 +103,8 @@ define <2 x i8> @test_vector_uadd_overflow(<2 x i8> %a) {
 ; Can combine sadds if sign matches.
 define i8 @test_scalar_sadd_both_positive(i8 %a) {
 ; CHECK-LABEL: @test_scalar_sadd_both_positive(
-; CHECK-NEXT:    [[Z1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[Z2:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[Z1]], i8 20)
-; CHECK-NEXT:    ret i8 [[Z2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 30)
+; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %z1 = call i8 @llvm.sadd.sat.i8(i8 %a, i8 10)
   %z2 = call i8 @llvm.sadd.sat.i8(i8 %z1, i8 20)
@@ -120,9 +113,8 @@ define i8 @test_scalar_sadd_both_positive(i8 %a) {
 
 define <2 x i8> @test_vector_sadd_both_positive(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_sadd_both_positive(
-; CHECK-NEXT:    [[Z1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 10, i8 10>)
-; CHECK-NEXT:    [[Z2:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[Z1]], <2 x i8> <i8 20, i8 20>)
-; CHECK-NEXT:    ret <2 x i8> [[Z2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 30, i8 30>)
+; CHECK-NEXT:    ret <2 x i8> [[TMP1]]
 ;
   %z1 = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 10, i8 10>)
   %z2 = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> %z1, <2 x i8> <i8 20, i8 20>)
@@ -131,9 +123,8 @@ define <2 x i8> @test_vector_sadd_both_positive(<2 x i8> %a) {
 
 define i8 @test_scalar_sadd_both_negative(i8 %a) {
 ; CHECK-LABEL: @test_scalar_sadd_both_negative(
-; CHECK-NEXT:    [[U1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 -10)
-; CHECK-NEXT:    [[U2:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[U1]], i8 -20)
-; CHECK-NEXT:    ret i8 [[U2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 -30)
+; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %u1 = call i8 @llvm.sadd.sat.i8(i8 %a, i8 -10)
   %u2 = call i8 @llvm.sadd.sat.i8(i8 %u1, i8 -20)
@@ -142,9 +133,8 @@ define i8 @test_scalar_sadd_both_negative(i8 %a) {
 
 define <2 x i8> @test_vector_sadd_both_negative(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_sadd_both_negative(
-; CHECK-NEXT:    [[U1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 -10, i8 -10>)
-; CHECK-NEXT:    [[U2:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[U1]], <2 x i8> <i8 -20, i8 -20>)
-; CHECK-NEXT:    ret <2 x i8> [[U2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 -30, i8 -30>)
+; CHECK-NEXT:    ret <2 x i8> [[TMP1]]
 ;
   %u1 = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 -10, i8 -10>)
   %u2 = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> %u1, <2 x i8> <i8 -20, i8 -20>)
@@ -379,9 +369,8 @@ define <2 x i8> @test_vector_ssub_canonical_min(<2 x i8> %a) {
 ; Can combine usubs with constant operands.
 define i8 @test_scalar_usub_combine(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_combine(
-; CHECK-NEXT:    [[X1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[X2:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[X1]], i8 20)
-; CHECK-NEXT:    ret i8 [[X2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 30)
+; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %x1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 10)
   %x2 = call i8 @llvm.usub.sat.i8(i8 %x1, i8 20)
@@ -390,9 +379,8 @@ define i8 @test_scalar_usub_combine(i8 %a) {
 
 define <2 x i8> @test_vector_usub_combine(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_usub_combine(
-; CHECK-NEXT:    [[X1:%.*]] = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 10, i8 10>)
-; CHECK-NEXT:    [[X2:%.*]] = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> [[X1]], <2 x i8> <i8 20, i8 20>)
-; CHECK-NEXT:    ret <2 x i8> [[X2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 30, i8 30>)
+; CHECK-NEXT:    ret <2 x i8> [[TMP1]]
 ;
   %x1 = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 10, i8 10>)
   %x2 = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> %x1, <2 x i8> <i8 20, i8 20>)
@@ -414,9 +402,7 @@ define <2 x i8> @test_vector_usub_combine_non_splat(<2 x i8> %a) {
 ; Can combine usubs even if they overflow.
 define i8 @test_scalar_usub_overflow(i8 %a) {
 ; CHECK-LABEL: @test_scalar_usub_overflow(
-; CHECK-NEXT:    [[Y1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 100)
-; CHECK-NEXT:    [[Y2:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[Y1]], i8 -56)
-; CHECK-NEXT:    ret i8 [[Y2]]
+; CHECK-NEXT:    ret i8 0
 ;
   %y1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 100)
   %y2 = call i8 @llvm.usub.sat.i8(i8 %y1, i8 200)
@@ -425,9 +411,7 @@ define i8 @test_scalar_usub_overflow(i8 %a) {
 
 define <2 x i8> @test_vector_usub_overflow(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_usub_overflow(
-; CHECK-NEXT:    [[Y1:%.*]] = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 100, i8 100>)
-; CHECK-NEXT:    [[Y2:%.*]] = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> [[Y1]], <2 x i8> <i8 -56, i8 -56>)
-; CHECK-NEXT:    ret <2 x i8> [[Y2]]
+; CHECK-NEXT:    ret <2 x i8> zeroinitializer
 ;
   %y1 = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 100, i8 100>)
   %y2 = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> %y1, <2 x i8> <i8 200, i8 200>)
@@ -437,9 +421,8 @@ define <2 x i8> @test_vector_usub_overflow(<2 x i8> %a) {
 ; Can combine ssubs if sign matches.
 define i8 @test_scalar_ssub_both_positive(i8 %a) {
 ; CHECK-LABEL: @test_scalar_ssub_both_positive(
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 -10)
-; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[TMP1]], i8 -20)
-; CHECK-NEXT:    ret i8 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 -30)
+; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %z1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 10)
   %z2 = call i8 @llvm.ssub.sat.i8(i8 %z1, i8 20)
@@ -448,9 +431,8 @@ define i8 @test_scalar_ssub_both_positive(i8 %a) {
 
 define <2 x i8> @test_vector_ssub_both_positive(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_ssub_both_positive(
-; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 -10, i8 -10>)
-; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[TMP1]], <2 x i8> <i8 -20, i8 -20>)
-; CHECK-NEXT:    ret <2 x i8> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 -30, i8 -30>)
+; CHECK-NEXT:    ret <2 x i8> [[TMP1]]
 ;
   %z1 = call <2 x i8> @llvm.ssub.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 10, i8 10>)
   %z2 = call <2 x i8> @llvm.ssub.sat.v2i8(<2 x i8> %z1, <2 x i8> <i8 20, i8 20>)
@@ -459,9 +441,8 @@ define <2 x i8> @test_vector_ssub_both_positive(<2 x i8> %a) {
 
 define i8 @test_scalar_ssub_both_negative(i8 %a) {
 ; CHECK-LABEL: @test_scalar_ssub_both_negative(
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[TMP1]], i8 20)
-; CHECK-NEXT:    ret i8 [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 30)
+; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %u1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 -10)
   %u2 = call i8 @llvm.ssub.sat.i8(i8 %u1, i8 -20)
@@ -470,9 +451,8 @@ define i8 @test_scalar_ssub_both_negative(i8 %a) {
 
 define <2 x i8> @test_vector_ssub_both_negative(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_ssub_both_negative(
-; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 10, i8 10>)
-; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[TMP1]], <2 x i8> <i8 20, i8 20>)
-; CHECK-NEXT:    ret <2 x i8> [[TMP2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 30, i8 30>)
+; CHECK-NEXT:    ret <2 x i8> [[TMP1]]
 ;
   %u1 = call <2 x i8> @llvm.ssub.sat.v2i8(<2 x i8> %a, <2 x i8> <i8 -10, i8 -10>)
   %u2 = call <2 x i8> @llvm.ssub.sat.v2i8(<2 x i8> %u1, <2 x i8> <i8 -20, i8 -20>)
@@ -494,8 +474,7 @@ define i8 @test_scalar_ssub_different_sign(i8 %a) {
 ; Can combine sadd and ssub with appropriate signs.
 define i8 @test_scalar_sadd_ssub(i8 %a) {
 ; CHECK-LABEL: @test_scalar_sadd_ssub(
-; CHECK-NEXT:    [[V1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 10)
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[V1]], i8 20)
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 30)
 ; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %v1 = call i8 @llvm.sadd.sat.i8(i8 10, i8 %a)
@@ -505,8 +484,7 @@ define i8 @test_scalar_sadd_ssub(i8 %a) {
 
 define <2 x i8> @test_vector_sadd_ssub(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_sadd_ssub(
-; CHECK-NEXT:    [[V1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 -10, i8 -10>)
-; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[V1]], <2 x i8> <i8 -20, i8 -20>)
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 -30, i8 -30>)
 ; CHECK-NEXT:    ret <2 x i8> [[TMP1]]
 ;
   %v1 = call <2 x i8> @llvm.sadd.sat.v2i8(<2 x i8> <i8 -10, i8 -10>, <2 x i8> %a)