[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428).

Summary:
Comment on Transforms/LoopVersioning/incorrect-phi.ll: With the change
SCEV is able to prove that the loop doesn't wrap-self (due to zext i16
to i64), disabling the entire loop versioning pass. Removed the zext and
just use i64.

Reviewers: sanjoy

Subscribers: jlebar, hiraditya, javed.absar, bixia, llvm-commits

Differential Revision: https://reviews.llvm.org/D48409

llvm-svn: 336140

11 files changed, 29 insertions, 25 deletions

diff --git a/llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll b/llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll
index b54baeebf37..1af50352e3f 100644
--- a/llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll
+++ b/llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll
@@ -322,7 +322,7 @@ define void @test_05(i32 %N) {
 ; CHECK:       %SQ = mul i32 %i.0, %i.0
 ; CHECK-NEXT:  -->  {4,+,5,+,2}<%bb3>
 ; CHECK:       %tmp4 = mul i32 %i.0, 2
-; CHECK-NEXT:  -->  {4,+,2}<%bb3>
+; CHECK-NEXT:  -->  {4,+,2}<nuw><nsw><%bb3>
 ; CHECK:       %tmp5 = sub i32 %SQ, %tmp4
 ; CHECK-NEXT:  -->  {0,+,3,+,2}<%bb3>
 
diff --git a/llvm/test/Analysis/ScalarEvolution/extract-highbits-sameconstmask.ll b/llvm/test/Analysis/ScalarEvolution/extract-highbits-sameconstmask.ll
index 851dce65316..6b0f8588065 100644
--- a/llvm/test/Analysis/ScalarEvolution/extract-highbits-sameconstmask.ll
+++ b/llvm/test/Analysis/ScalarEvolution/extract-highbits-sameconstmask.ll
@@ -8,7 +8,7 @@ define i32 @div(i32 %val) nounwind {
 ; CHECK-NEXT:    %tmp1 = udiv i32 %val, 16
 ; CHECK-NEXT:    -->  (%val /u 16) U: [0,268435456) S: [0,268435456)
 ; CHECK-NEXT:    %tmp2 = mul i32 %tmp1, 16
-; CHECK-NEXT:    -->  (16 * (%val /u 16)) U: [0,-15) S: [0,-15)
+; CHECK-NEXT:    -->  (16 * (%val /u 16))<nuw> U: [0,-15) S: [0,-15)
 ; CHECK-NEXT:  Determining loop execution counts for: @div
 ;
   %tmp1 = udiv i32 %val, 16
@@ -22,7 +22,7 @@ define i32 @sdiv(i32 %val) nounwind {
 ; CHECK-NEXT:    %tmp1 = sdiv i32 %val, 16
 ; CHECK-NEXT:    -->  %tmp1 U: full-set S: [-134217728,134217728)
 ; CHECK-NEXT:    %tmp2 = mul i32 %tmp1, 16
-; CHECK-NEXT:    -->  (16 * %tmp1) U: [0,-15) S: [-2147483648,2147483633)
+; CHECK-NEXT:    -->  (16 * %tmp1)<nsw> U: [0,-15) S: [-2147483648,2147483633)
 ; CHECK-NEXT:  Determining loop execution counts for: @sdiv
 ;
   %tmp1 = sdiv i32 %val, 16
@@ -38,7 +38,7 @@ define i32 @mask_b(i32 %val) nounwind {
 ; CHECK-LABEL: 'mask_b'
 ; CHECK-NEXT:  Classifying expressions for: @mask_b
 ; CHECK-NEXT:    %masked = and i32 %val, -16
-; CHECK-NEXT:    -->  (16 * (%val /u 16)) U: [0,-15) S: [0,-15)
+; CHECK-NEXT:    -->  (16 * (%val /u 16))<nuw> U: [0,-15) S: [0,-15)
 ; CHECK-NEXT:  Determining loop execution counts for: @mask_b
 ;
   %masked = and i32 %val, -16
@@ -51,7 +51,7 @@ define i32 @mask_d(i32 %val) nounwind {
 ; CHECK-NEXT:    %lowbitscleared = lshr i32 %val, 4
 ; CHECK-NEXT:    -->  (%val /u 16) U: [0,268435456) S: [0,268435456)
 ; CHECK-NEXT:    %masked = shl i32 %lowbitscleared, 4
-; CHECK-NEXT:    -->  (16 * (%val /u 16)) U: [0,-15) S: [0,-15)
+; CHECK-NEXT:    -->  (16 * (%val /u 16))<nuw> U: [0,-15) S: [0,-15)
 ; CHECK-NEXT:  Determining loop execution counts for: @mask_d
 ;
   %lowbitscleared = lshr i32 %val, 4
diff --git a/llvm/test/Analysis/ScalarEvolution/lshr-shl-differentconstmask.ll b/llvm/test/Analysis/ScalarEvolution/lshr-shl-differentconstmask.ll
index 0955d3ee3a6..89c31d12a53 100644
--- a/llvm/test/Analysis/ScalarEvolution/lshr-shl-differentconstmask.ll
+++ b/llvm/test/Analysis/ScalarEvolution/lshr-shl-differentconstmask.ll
@@ -8,7 +8,7 @@ define i32 @udiv_biggerLshr(i32 %val) nounwind {
 ; CHECK-NEXT:    %tmp1 = udiv i32 %val, 64
 ; CHECK-NEXT:    -->  (%val /u 64) U: [0,67108864) S: [0,67108864)
 ; CHECK-NEXT:    %tmp2 = mul i32 %tmp1, 16
-; CHECK-NEXT:    -->  (16 * (%val /u 64)) U: [0,1073741809) S: [0,1073741809)
+; CHECK-NEXT:    -->  (16 * (%val /u 64))<nuw><nsw> U: [0,1073741809) S: [0,1073741809)
 ; CHECK-NEXT:  Determining loop execution counts for: @udiv_biggerLshr
 ;
   %tmp1 = udiv i32 %val, 64
@@ -38,7 +38,7 @@ define i32 @shifty_biggerLshr(i32 %val) {
 ; CHECK-NEXT:    %tmp1 = lshr i32 %val, 6
 ; CHECK-NEXT:    -->  (%val /u 64) U: [0,67108864) S: [0,67108864)
 ; CHECK-NEXT:    %tmp2 = shl i32 %tmp1, 4
-; CHECK-NEXT:    -->  (16 * (%val /u 64)) U: [0,1073741809) S: [0,1073741809)
+; CHECK-NEXT:    -->  (16 * (%val /u 64))<nuw><nsw> U: [0,1073741809) S: [0,1073741809)
 ; CHECK-NEXT:  Determining loop execution counts for: @shifty_biggerLshr
 ;
   %tmp1 = lshr i32 %val, 6
@@ -52,7 +52,7 @@ define i32 @shifty_biggerLshr_lshrexact(i32 %val) {
 ; CHECK-NEXT:    %tmp1 = lshr exact i32 %val, 6
 ; CHECK-NEXT:    -->  (%val /u 64) U: [0,67108864) S: [0,67108864)
 ; CHECK-NEXT:    %tmp2 = shl i32 %tmp1, 4
-; CHECK-NEXT:    -->  (16 * (%val /u 64)) U: [0,1073741809) S: [0,1073741809)
+; CHECK-NEXT:    -->  (16 * (%val /u 64))<nuw><nsw> U: [0,1073741809) S: [0,1073741809)
 ; CHECK-NEXT:  Determining loop execution counts for: @shifty_biggerLshr_lshrexact
 ;
   %tmp1 = lshr exact i32 %val, 6
@@ -96,7 +96,7 @@ define i32 @masky_biggerLshr(i32 %val) {
 ; CHECK-NEXT:    %tmp1 = lshr i32 %val, 2
 ; CHECK-NEXT:    -->  (%val /u 4) U: [0,1073741824) S: [0,1073741824)
 ; CHECK-NEXT:    %tmp2 = and i32 %tmp1, -16
-; CHECK-NEXT:    -->  (16 * (%val /u 64)) U: [0,1073741809) S: [0,1073741809)
+; CHECK-NEXT:    -->  (16 * (%val /u 64))<nuw><nsw> U: [0,1073741809) S: [0,1073741809)
 ; CHECK-NEXT:  Determining loop execution counts for: @masky_biggerLshr
 ;
   %tmp1 = lshr i32 %val, 2
@@ -121,7 +121,7 @@ define i32 @masky_biggerShr(i32 %val) {
 ; CHECK-NEXT:    %tmp1 = shl i32 %val, 2
 ; CHECK-NEXT:    -->  (4 * %val) U: [0,-3) S: [-2147483648,2147483645)
 ; CHECK-NEXT:    %tmp2 = and i32 %tmp1, -64
-; CHECK-NEXT:    -->  (64 * (zext i26 (trunc i32 (%val /u 16) to i26) to i32)) U: [0,-63) S: [0,-63)
+; CHECK-NEXT:    -->  (64 * (zext i26 (trunc i32 (%val /u 16) to i26) to i32))<nuw> U: [0,-63) S: [0,-63)
 ; CHECK-NEXT:  Determining loop execution counts for: @masky_biggerShr
 ;
   %tmp1 = shl i32 %val, 2
diff --git a/llvm/test/Analysis/ScalarEvolution/nsw-offset-assume.ll b/llvm/test/Analysis/ScalarEvolution/nsw-offset-assume.ll
index 5413b477df5..3ef31ff5581 100644
--- a/llvm/test/Analysis/ScalarEvolution/nsw-offset-assume.ll
+++ b/llvm/test/Analysis/ScalarEvolution/nsw-offset-assume.ll
@@ -79,5 +79,5 @@ declare void @llvm.assume(i1) nounwind
 
 ; Note: Without the preheader assume, there is an 'smax' in the
 ; backedge-taken count expression:
-; CHECK: Loop %bb: backedge-taken count is ((-1 + (2 * (%no /u 2))) /u 2)
+; CHECK: Loop %bb: backedge-taken count is ((-1 + (2 * (%no /u 2))<nuw>) /u 2)
 ; CHECK: Loop %bb: max backedge-taken count is 1073741822
diff --git a/llvm/test/Analysis/ScalarEvolution/nsw-offset.ll b/llvm/test/Analysis/ScalarEvolution/nsw-offset.ll
index f8ed8f003ff..a5c4b575f13 100644
--- a/llvm/test/Analysis/ScalarEvolution/nsw-offset.ll
+++ b/llvm/test/Analysis/ScalarEvolution/nsw-offset.ll
@@ -73,5 +73,5 @@ return:                                           ; preds = %bb1.return_crit_edg
   ret void
 }
 
-; CHECK: Loop %bb: backedge-taken count is ((-1 + (2 * (%no /u 2))) /u 2)
+; CHECK: Loop %bb: backedge-taken count is ((-1 + (2 * (%no /u 2))<nuw>) /u 2)
 ; CHECK: Loop %bb: max backedge-taken count is 1073741822
diff --git a/llvm/test/Analysis/ScalarEvolution/nsw.ll b/llvm/test/Analysis/ScalarEvolution/nsw.ll
index 39b958d3ea0..ca24f9d4a04 100644
--- a/llvm/test/Analysis/ScalarEvolution/nsw.ll
+++ b/llvm/test/Analysis/ScalarEvolution/nsw.ll
@@ -126,7 +126,7 @@ exit:
 }
 
 ; CHECK-LABEL: PR12375
-; CHECK: -->  {(4 + %arg)<nsw>,+,4}<nuw><%bb1>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (4 + (4 * ((-1 + (-1 * %arg) + ((4 + %arg)<nsw> umax (8 + %arg)<nsw>)) /u 4)) + %arg)
+; CHECK: -->  {(4 + %arg)<nsw>,+,4}<nuw><%bb1>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (4 + (4 * ((-1 + (-1 * %arg) + ((4 + %arg)<nsw> umax (8 + %arg)<nsw>)) /u 4))<nuw> + %arg)
 define i32 @PR12375(i32* readnone %arg) {
 bb:
   %tmp = getelementptr inbounds i32, i32* %arg, i64 2
@@ -145,7 +145,7 @@ bb7:                                              ; preds = %bb1
 }
 
 ; CHECK-LABEL: PR12376
-; CHECK: -->  {(4 + %arg)<nsw>,+,4}<nuw><%bb2>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (4 + (4 * ((-1 + (-1 * %arg) + ((4 + %arg)<nsw> umax %arg1)) /u 4)) + %arg)
+; CHECK: -->  {(4 + %arg)<nsw>,+,4}<nuw><%bb2>{{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: (4 + (4 * ((-1 + (-1 * %arg) + ((4 + %arg)<nsw> umax %arg1)) /u 4))<nuw> + %arg)
 define void @PR12376(i32* nocapture %arg, i32* nocapture %arg1)  {
 bb:
   br label %bb2
diff --git a/llvm/test/Analysis/ScalarEvolution/predicated-trip-count.ll b/llvm/test/Analysis/ScalarEvolution/predicated-trip-count.ll
index 2db0a8b5777..a0afcf457d2 100644
--- a/llvm/test/Analysis/ScalarEvolution/predicated-trip-count.ll
+++ b/llvm/test/Analysis/ScalarEvolution/predicated-trip-count.ll
@@ -80,7 +80,7 @@ return:         ; preds = %bb5
 ; CHECK-NEXT:    -->  (sext i16 {%Start,+,-1}<%bb3> to i32)
 ; CHECK:       Loop %bb3: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %bb3: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %bb3: Predicated backedge-taken count is (2 + (sext i16 %Start to i32) + ((-2 + (-1 * (sext i16 %Start to i32))) smax (-1 + (-1 * %M))))
+; CHECK-NEXT:  Loop %bb3: Predicated backedge-taken count is (2 + (sext i16 %Start to i32) + ((-2 + (-1 * (sext i16 %Start to i32))<nsw>) smax (-1 + (-1 * %M))))
 ; CHECK-NEXT:  Predicates:
 ; CHECK-NEXT:    {%Start,+,-1}<%bb3> Added Flags: <nssw>
 
diff --git a/llvm/test/Analysis/ScalarEvolution/sext-mul.ll b/llvm/test/Analysis/ScalarEvolution/sext-mul.ll
index ca25d9e2efa..8fe22db9f1c 100644
--- a/llvm/test/Analysis/ScalarEvolution/sext-mul.ll
+++ b/llvm/test/Analysis/ScalarEvolution/sext-mul.ll
@@ -5,11 +5,11 @@
 ; CHECK: %tmp10 = ashr exact i64 %tmp9, 32
 ; CHECK-NEXT: --> {{.*}} Exits: (sext i32 (-2 + (2 * %arg2)) to i64)
 ; CHECK: %tmp11 = getelementptr inbounds i32, i32* %arg, i64 %tmp10
-; CHECK-NEXT: --> {{.*}} Exits: ((4 * (sext i32 (-2 + (2 * %arg2)) to i64)) + %arg)
+; CHECK-NEXT: --> {{.*}} Exits: ((4 * (sext i32 (-2 + (2 * %arg2)) to i64))<nsw> + %arg)
 ; CHECK:  %tmp14 = or i64 %tmp10, 1
 ; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i32 (-2 + (2 * %arg2)) to i64))<nsw>
 ; CHECK: %tmp15 = getelementptr inbounds i32, i32* %arg, i64 %tmp14
-; CHECK-NEXT: --> {{.*}} Exits: (4 + (4 * (sext i32 (-2 + (2 * %arg2)) to i64)) + %arg)
+; CHECK-NEXT: --> {{.*}} Exits: (4 + (4 * (sext i32 (-2 + (2 * %arg2)) to i64))<nsw> + %arg)
 ; CHECK:Loop %bb7: backedge-taken count is (-1 + (zext i32 %arg2 to i64))<nsw>
 ; CHECK-NEXT:Loop %bb7: max backedge-taken count is -1
 ; CHECK-NEXT:Loop %bb7: Predicated backedge-taken count is (-1 + (zext i32 %arg2 to i64))<nsw>
diff --git a/llvm/test/Analysis/ScalarEvolution/shl-lshr-differentconstmask.ll b/llvm/test/Analysis/ScalarEvolution/shl-lshr-differentconstmask.ll
index be97990e116..1886848b8be 100644
--- a/llvm/test/Analysis/ScalarEvolution/shl-lshr-differentconstmask.ll
+++ b/llvm/test/Analysis/ScalarEvolution/shl-lshr-differentconstmask.ll
@@ -96,7 +96,7 @@ define i32 @masky_biggerShl(i32 %val) {
 ; CHECK-NEXT:    %tmp1 = shl i32 %val, 2
 ; CHECK-NEXT:    -->  (4 * %val) U: [0,-3) S: [-2147483648,2147483645)
 ; CHECK-NEXT:    %tmp2 = and i32 %tmp1, 268435452
-; CHECK-NEXT:    -->  (4 * (zext i26 (trunc i32 %val to i26) to i32)) U: [0,268435453) S: [0,268435453)
+; CHECK-NEXT:    -->  (4 * (zext i26 (trunc i32 %val to i26) to i32))<nuw><nsw> U: [0,268435453) S: [0,268435453)
 ; CHECK-NEXT:  Determining loop execution counts for: @masky_biggerShl
 ;
   %tmp1 = shl i32 %val, 2
diff --git a/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll b/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll
index 04d1b9544ab..3a6f5fec2b8 100644
--- a/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll
+++ b/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll
@@ -31,7 +31,7 @@ exit:
   ret i32 %i
 
 ; CHECK-LABEL: @test2
-; CHECK: Loop %loop: backedge-taken count is ((-32 + (32 * (%n /u 32))) /u 32)
+; CHECK: Loop %loop: backedge-taken count is ((-32 + (32 * (%n /u 32))<nuw>) /u 32)
 ; CHECK: Loop %loop: max backedge-taken count is 134217727
 }
 
diff --git a/llvm/test/Analysis/ScalarEvolution/zext-mul.ll b/llvm/test/Analysis/ScalarEvolution/zext-mul.ll
index ae93a9288d8..0c0f16c1dea 100644
--- a/llvm/test/Analysis/ScalarEvolution/zext-mul.ll
+++ b/llvm/test/Analysis/ScalarEvolution/zext-mul.ll
@@ -19,16 +19,20 @@ define void @no_range() {
 }
 
 ; CHECK-LABEL: @range
-;
-; This had to be disabled when r334428 was reverted.  We should enable this test
-; when r334428 is reapplied with a fix.
 define void @range() {
-  %a = call i32 @get_int(), !range !0
+  %a = call i32 @get_int(), !range !{i32 0, i32 100}
   %b = mul i32 %a, 4
   %c = zext i32 %b to i64
   ; CHECK: %c
-  ; CHECK-NEXT: --> (zext i32 (4 * %a) to i64)
+  ; CHECK-NEXT: --> (4 * (zext i32 %a to i64))<nuw><nsw>
   ret void
 }
 
-!0 = !{i32 0, i32 100}
+; CHECK-LABEL: @no_nuw
+define void @no_nuw() {
+  %a = call i32 @get_int(), !range !{i32 0, i32 3}
+  %b = mul i32 %a, -100
+  ; CHECK: %b
+  ; CHECK-NEXT: -->  (-100 * %a)<nsw>
+  ret void
+}