[ValueTracking] More accurate unsigned add overflow detection

Part of D58593.

Compute precise overflow conditions based on all known bits, rather
than just the sign bits. Unsigned a + b overflows iff a > ~b, and we
can determine whether this always/never happens based on the minimal
and maximal values achievable for a and ~b subject to the known bits
constraint.

llvm-svn: 355072

4 files changed, 10 insertions, 14 deletions

diff --git a/llvm/test/Transforms/InstCombine/AddOverFlow.ll b/llvm/test/Transforms/InstCombine/AddOverFlow.ll
index 52815daa415..13494206f07 100644
--- a/llvm/test/Transforms/InstCombine/AddOverFlow.ll
+++ b/llvm/test/Transforms/InstCombine/AddOverFlow.ll
@@ -107,7 +107,7 @@ define i16 @ripple_nsw1(i16 %x, i16 %y) {
 ; CHECK-LABEL: @ripple_nsw1(
 ; CHECK-NEXT:    [[A:%.*]] = and i16 [[Y:%.*]], 1
 ; CHECK-NEXT:    [[B:%.*]] = and i16 [[X:%.*]], -16385
-; CHECK-NEXT:    [[C:%.*]] = add nsw i16 [[A]], [[B]]
+; CHECK-NEXT:    [[C:%.*]] = add nuw nsw i16 [[A]], [[B]]
 ; CHECK-NEXT:    ret i16 [[C]]
 ;
   %a = and i16 %y, 1
@@ -121,7 +121,7 @@ define i16 @ripple_nsw2(i16 %x, i16 %y) {
 ; CHECK-LABEL: @ripple_nsw2(
 ; CHECK-NEXT:    [[A:%.*]] = and i16 [[Y:%.*]], 1
 ; CHECK-NEXT:    [[B:%.*]] = and i16 [[X:%.*]], -16385
-; CHECK-NEXT:    [[C:%.*]] = add nsw i16 [[B]], [[A]]
+; CHECK-NEXT:    [[C:%.*]] = add nuw nsw i16 [[B]], [[A]]
 ; CHECK-NEXT:    ret i16 [[C]]
 ;
   %a = and i16 %y, 1
@@ -134,7 +134,7 @@ define i16 @ripple_nsw3(i16 %x, i16 %y) {
 ; CHECK-LABEL: @ripple_nsw3(
 ; CHECK-NEXT:    [[A:%.*]] = and i16 [[Y:%.*]], -21845
 ; CHECK-NEXT:    [[B:%.*]] = and i16 [[X:%.*]], 21843
-; CHECK-NEXT:    [[C:%.*]] = add nsw i16 [[A]], [[B]]
+; CHECK-NEXT:    [[C:%.*]] = add nuw nsw i16 [[A]], [[B]]
 ; CHECK-NEXT:    ret i16 [[C]]
 ;
   %a = and i16 %y, 43691
@@ -148,7 +148,7 @@ define i16 @ripple_nsw4(i16 %x, i16 %y) {
 ; CHECK-LABEL: @ripple_nsw4(
 ; CHECK-NEXT:    [[A:%.*]] = and i16 [[Y:%.*]], -21845
 ; CHECK-NEXT:    [[B:%.*]] = and i16 [[X:%.*]], 21843
-; CHECK-NEXT:    [[C:%.*]] = add nsw i16 [[B]], [[A]]
+; CHECK-NEXT:    [[C:%.*]] = add nuw nsw i16 [[B]], [[A]]
 ; CHECK-NEXT:    ret i16 [[C]]
 ;
   %a = and i16 %y, 43691
diff --git a/llvm/test/Transforms/InstCombine/add.ll b/llvm/test/Transforms/InstCombine/add.ll
index f62d136ca0e..a9d614e4868 100644
--- a/llvm/test/Transforms/InstCombine/add.ll
+++ b/llvm/test/Transforms/InstCombine/add.ll
@@ -470,7 +470,7 @@ define i64 @add_nuw_zext_add_extra_use_2(i8 %x, i8* %p) {
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw i8 [[X:%.*]], 42
 ; CHECK-NEXT:    store i8 [[ADD]], i8* [[P:%.*]], align 1
 ; CHECK-NEXT:    [[EXT:%.*]] = zext i8 [[ADD]] to i64
-; CHECK-NEXT:    [[R:%.*]] = add nsw i64 [[EXT]], -356
+; CHECK-NEXT:    [[R:%.*]] = add nuw nsw i64 [[EXT]], -356
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
   %add = add nuw i8 %x, 42
diff --git a/llvm/test/Transforms/InstCombine/saturating-add-sub.ll b/llvm/test/Transforms/InstCombine/saturating-add-sub.ll
index 6f616bfe1ee..aa833f7c728 100644
--- a/llvm/test/Transforms/InstCombine/saturating-add-sub.ll
+++ b/llvm/test/Transforms/InstCombine/saturating-add-sub.ll
@@ -233,7 +233,7 @@ define <2 x i8> @test_vector_uadd_neg_nneg(<2 x i8> %a) {
 define i8 @test_scalar_uadd_never_overflows(i8 %a) {
 ; CHECK-LABEL: @test_scalar_uadd_never_overflows(
 ; CHECK-NEXT:    [[A_MASKED:%.*]] = and i8 [[A:%.*]], -127
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A_MASKED]], i8 1)
+; CHECK-NEXT:    [[R:%.*]] = add nuw nsw i8 [[A_MASKED]], 1
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a_masked = and i8 %a, 129
@@ -244,7 +244,7 @@ define i8 @test_scalar_uadd_never_overflows(i8 %a) {
 define <2 x i8> @test_vector_uadd_never_overflows(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_uadd_never_overflows(
 ; CHECK-NEXT:    [[A_MASKED:%.*]] = and <2 x i8> [[A:%.*]], <i8 -127, i8 -127>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[A_MASKED]], <2 x i8> <i8 1, i8 1>)
+; CHECK-NEXT:    [[R:%.*]] = add nuw nsw <2 x i8> [[A_MASKED]], <i8 1, i8 1>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %a_masked = and <2 x i8> %a, <i8 129, i8 129>
@@ -254,9 +254,7 @@ define <2 x i8> @test_vector_uadd_never_overflows(<2 x i8> %a) {
 
 define i8 @test_scalar_uadd_always_overflows(i8 %a) {
 ; CHECK-LABEL: @test_scalar_uadd_always_overflows(
-; CHECK-NEXT:    [[A_MASKED:%.*]] = or i8 [[A:%.*]], -64
-; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A_MASKED]], i8 64)
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 -1
 ;
   %a_masked = or i8 %a, 192
   %r = call i8 @llvm.uadd.sat.i8(i8 %a_masked, i8 64)
@@ -265,9 +263,7 @@ define i8 @test_scalar_uadd_always_overflows(i8 %a) {
 
 define <2 x i8> @test_vector_uadd_always_overflows(<2 x i8> %a) {
 ; CHECK-LABEL: @test_vector_uadd_always_overflows(
-; CHECK-NEXT:    [[A_MASKED:%.*]] = or <2 x i8> [[A:%.*]], <i8 -64, i8 -64>
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> [[A_MASKED]], <2 x i8> <i8 64, i8 64>)
-; CHECK-NEXT:    ret <2 x i8> [[R]]
+; CHECK-NEXT:    ret <2 x i8> <i8 -1, i8 -1>
 ;
   %a_masked = or <2 x i8> %a, <i8 192, i8 192>
   %r = call <2 x i8> @llvm.uadd.sat.v2i8(<2 x i8> %a_masked, <2 x i8> <i8 64, i8 64>)
diff --git a/llvm/test/Transforms/InstCombine/shuffle_select.ll b/llvm/test/Transforms/InstCombine/shuffle_select.ll
index c39237e3569..f370ad624e0 100644
--- a/llvm/test/Transforms/InstCombine/shuffle_select.ll
+++ b/llvm/test/Transforms/InstCombine/shuffle_select.ll
@@ -1397,7 +1397,7 @@ define <4 x i32> @add_or(<4 x i32> %v) {
 define <4 x i8> @or_add(<4 x i8> %v) {
 ; CHECK-LABEL: @or_add(
 ; CHECK-NEXT:    [[V0:%.*]] = lshr <4 x i8> [[V:%.*]], <i8 3, i8 3, i8 3, i8 3>
-; CHECK-NEXT:    [[T3:%.*]] = add nsw <4 x i8> [[V0]], <i8 1, i8 2, i8 -64, i8 -64>
+; CHECK-NEXT:    [[T3:%.*]] = add nuw nsw <4 x i8> [[V0]], <i8 1, i8 2, i8 -64, i8 -64>
 ; CHECK-NEXT:    ret <4 x i8> [[T3]]
 ;
   %v0 = lshr <4 x i8> %v, <i8 3, i8 3, i8 3, i8 3>          ; clear the top bits