[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428).

[timshen]

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.

[timshen]

Update more tests.

[sanjoy]

lgtm

llvm/lib/Analysis/ScalarEvolution.cpp

StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type,
   };
 
   if (SignOrUnsignWrap == SCEV::FlagNSW && all_of(Ops, IsKnownNonNegative))
     Flags =
         ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
 
   SignOrUnsignWrap = ScalarEvolution::maskFlags(Flags, SignOrUnsignMask);
 
-  if (SignOrUnsignWrap != SignOrUnsignMask && Type == scAddExpr &&
-      Ops.size() == 2 && isa<SCEVConstant>(Ops[0])) {
+  if (SignOrUnsignWrap != SignOrUnsignMask &&
+      (Type == scAddExpr || Type == scMulExpr) && Ops.size() == 2 &&
+      isa<SCEVConstant>(Ops[0])) {
 
-    // (A + C) --> (A + C)<nsw> if the addition does not sign overflow
-    // (A + C) --> (A + C)<nuw> if the addition does not unsign overflow
+    auto Opcode = [&] {
+      switch (Type) {
+      case scAddExpr:
+        return Instruction::Add;
+      case scMulExpr:
+        return Instruction::Mul;
+      default:
+        llvm_unreachable("Unexpected SCEV op.");
+      }
+    }();
 
     const APInt &C = cast<SCEVConstant>(Ops[0])->getAPInt();
+
+    // (A <opcode> C) --> (A <opcode> C)<nsw> if the op doesn't sign overflow.
     if (!(SignOrUnsignWrap & SCEV::FlagNSW)) {
       auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
-          Instruction::Add, C, OBO::NoSignedWrap);
+          Opcode, C, OBO::NoSignedWrap);
       if (NSWRegion.contains(SE->getSignedRange(Ops[1])))
         Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
     }
+
+    // (A <opcode> C) --> (A <opcode> C)<nuw> if the op doesn't unsign overflow.
     if (!(SignOrUnsignWrap & SCEV::FlagNUW)) {
       auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
-          Instruction::Add, C, OBO::NoUnsignedWrap);
+          Opcode, C, OBO::NoUnsignedWrap);
       if (NUWRegion.contains(SE->getUnsignedRange(Ops[1])))
         Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
     }
   }
 
   return Flags;
 }
 

llvm/test/Analysis/Delinearization/a.ll

 ; RUN: opt < %s -analyze -delinearize | FileCheck %s
 ;
 ; void foo(long n, long m, long o, int A[n][m][o]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[2*i+3][3*j-4][5*k+7] = 1;
 ; }
 
 ; AddRec: {{{(28 + (4 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(12 * %o)}<%for.j>,+,20}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 4 bytes.
-; CHECK: ArrayRef[{3,+,2}<%for.i>][{-4,+,3}<nw><%for.j>][{7,+,5}<nw><%for.k>]
+; CHECK: ArrayRef[{3,+,2}<nw><%for.i>][{-4,+,3}<nw><%for.j>][{7,+,5}<nw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, i32* nocapture %A) #0 {
 entry:
   %cmp32 = icmp sgt i64 %n, 0
   br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end17
 
 for.cond1.preheader.lr.ph:                        ; preds = %entry
   %cmp230 = icmp sgt i64 %m, 0

llvm/test/Analysis/Delinearization/iv_times_constant_in_subscript.ll

 ; RUN: opt < %s -analyze -delinearize | FileCheck %s
 
 ; Derived from the following code:
 ;
 ; void foo(long n, long m, long b, double A[n][m]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       A[2i+b][2j] = 1.0;
 ; }
 
 ; AddRec: {{((%m * %b * 8) + %A),+,(2 * %m * 8)}<%for.i>,+,(2 * 8)}<%for.j>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m] with elements of 8 bytes.
-; CHECK: ArrayRef[{%b,+,2}<nsw><%for.i>][{0,+,2}<%for.j>]
+; CHECK: ArrayRef[{%b,+,2}<nsw><%for.i>][{0,+,2}<nuw><%for.j>]
 
 
 define void @foo(i64 %n, i64 %m, i64 %b, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]

llvm/test/Analysis/IVUsers/quadradic-exit-value.ll

 ; PR15470: LSR miscompile. The test2 function should return '1'.
 ; It is illegal to fold SCEVUnknown (sext.us) into the recurrence
 ; because it is defined after the loop where this recurrence belongs.
 ;
 ; SCEV does not know how to denormalize chained recurrences, so make
 ; sure they aren't marked as post-inc users.
 ;
 ; CHECK-LABEL: IV Users for loop %test2.loop
-; CHECK-NO-LCSSA: %sub.cond.us = ((-1 * %sub.us)<nsw> + {0,+,1}<nuw><nsw><%test2.loop>) (post-inc with loop %test2.loop) in    %sext.us = mul i32 %mul.us, %sub.cond.us
+; CHECK-NO-LCSSA: %sub.cond.us = ((-1 * %sub.us)<nuw><nsw> + {0,+,1}<nuw><nsw><%test2.loop>) (post-inc with loop %test2.loop) in    %sext.us = mul i32 %mul.us, %sub.cond.us
 define i32 @test2() {
 entry:
   br label %test2.loop
 
 test2.loop:
   %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test2.loop ]
   %inc11.us = add nsw i32 %inc1115.us, 1
   %cmp.us = icmp slt i32 %inc11.us, 2

llvm/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll

 ; CHECK-NEXT:     Against group ([[TWO:.+]]):
 ; CHECK-NEXT:       %arrayidxA2 = getelementptr i16, i16* %a, i64 %ind2
 ; CHECK-NEXT:   Grouped accesses:
 ; CHECK-NEXT:     Group {{.*}}[[ZERO]]:
 ; CHECK-NEXT:       (Low: ((2 * %offset) + %a)<nsw> High: (10000 + (2 * %offset) + %a))
 ; CHECK-NEXT:         Member: {((2 * %offset) + %a)<nsw>,+,2}<nsw><%for.body>
 ; CHECK-NEXT:     Group {{.*}}[[ONE]]:
 ; CHECK-NEXT:       (Low: %a High: (10000 + %a))
-; CHECK-NEXT:         Member: {%a,+,2}<%for.body>
+; CHECK-NEXT:         Member: {%a,+,2}<nw><%for.body>
 ; CHECK-NEXT:     Group {{.*}}[[TWO]]:
 ; CHECK-NEXT:       (Low: (20000 + %a) High: (30000 + %a))
-; CHECK-NEXT:         Member: {(20000 + %a),+,2}<%for.body>
+; CHECK-NEXT:         Member: {(20000 + %a),+,2}<nw><%for.body>
 
 define void @testi(i16* %a,
                    i64 %offset) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]

llvm/test/Analysis/LoopAccessAnalysis/wrapping-pointer-versioning.ll

 ; LAA-NEXT: {%a,+,4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;    (zext i32 {0,+,2}<%for.body> to i64)
 ; We have added the nusw flag to turn this expression into the SCEV expression:
 ;    i64 {0,+,2}<%for.body>
 
 ; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
-; LAA-NEXT: ((2 * (zext i32 {0,+,2}<%for.body> to i64)) + %a)
+; LAA-NEXT: ((2 * (zext i32 {0,+,2}<%for.body> to i64))<nuw><nsw> + %a)
 ; LAA-NEXT: --> {%a,+,4}<%for.body>
 
 
 ; LV-LABEL: f1
 ; LV-LABEL: for.body.lver.check
 
 ; LV:      [[BETrunc:%[^ ]*]] = trunc i64 [[BE:%[^ ]*]] to i32
 ; LV-NEXT: [[OFMul:%[^ ]*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[BETrunc]])

 ; LAA-NEXT: {((4 * (zext i31 (trunc i64 %N to i31) to i64)) + %a),+,-4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;     (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)
 ; We have added the nusw flag to turn this expression into the following SCEV:
 ;     i64 {zext i32 (2 * (trunc i64 %N to i32)) to i64,+,-2}<%for.body>
 
 ; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
-; LAA-NEXT: ((2 * (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)) + %a)
+; LAA-NEXT: ((2 * (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64))<nuw><nsw> + %a)
 ; LAA-NEXT: --> {((4 * (zext i31 (trunc i64 %N to i31) to i64)) + %a),+,-4}<%for.body>
 
 ; LV-LABEL: f2
 ; LV-LABEL: for.body.lver.check
 
 ; LV: [[OFMul:%[^ ]*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[BETrunc:%[^ ]*]])
 ; LV-NEXT: [[OFMulResult:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 0
 ; LV-NEXT: [[OFMulOverflow:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 1

 ; LAA-NEXT: {%a,+,4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;     i64 (sext i32 {0,+,2}<%for.body> to i64)
 ; We have added the nssw flag to turn this expression into the following SCEV:
 ;     i64 {0,+,2}<%for.body>
 
 ; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
-; LAA-NEXT: ((2 * (sext i32 {0,+,2}<%for.body> to i64)) + %a)
+; LAA-NEXT: ((2 * (sext i32 {0,+,2}<%for.body> to i64))<nsw> + %a)
 ; LAA-NEXT: --> {%a,+,4}<%for.body>
 
 ; LV-LABEL: f3
 ; LV-LABEL: for.body.lver.check
 
 ; LV: [[OFMul:%[^ ]*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[BETrunc:%[^ ]*]])
 ; LV-NEXT: [[OFMulResult:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 0
 ; LV-NEXT: [[OFMulOverflow:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 1

 for.end:                                          ; preds = %for.body
   ret void
 }
 
 ; LAA-LABEL: f4
 ; LAA: Memory dependences are safe{{$}}
 ; LAA: SCEV assumptions:
 ; LAA-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nssw>
-; LAA-NEXT: {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body> Added Flags: <nusw>
+; LAA-NEXT: {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64))<nsw> + %a),+,-4}<%for.body> Added Flags: <nusw>
 
 ; The expression for %mul_ext as analyzed by SCEV is
 ;     i64  (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)
 ; We have added the nssw flag to turn this expression into the following SCEV:
 ;     i64 {sext i32 (2 * (trunc i64 %N to i32)) to i64,+,-2}<%for.body>
 
 ; LAA: [PSE]  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext:
-; LAA-NEXT: ((2 * (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)) + %a)
-; LAA-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body>
+; LAA-NEXT: ((2 * (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64))<nsw> + %a)
+; LAA-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64))<nsw> + %a),+,-4}<%for.body>
 
 ; LV-LABEL: f4
 ; LV-LABEL: for.body.lver.check
 
 ; LV: [[OFMul:%[^ ]*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[BETrunc:%[^ ]*]])
 ; LV-NEXT: [[OFMulResult:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 0
 ; LV-NEXT: [[OFMulOverflow:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 1
 ; LV-NEXT: [[AddEnd:%[^ ]*]] = add i32 [[Start:%[^ ]*]], [[OFMulResult]]

 ; a SCEV predicate to continue analysis.
 ;
 ; We can still analyze this by adding the required no wrap SCEV predicates.
 
 ; LAA-LABEL: f5
 ; LAA: Memory dependences are safe{{$}}
 ; LAA: SCEV assumptions:
 ; LAA-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nssw>
-; LAA-NEXT: {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body> Added Flags: <nusw>
+; LAA-NEXT: {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64))<nsw> + %a),+,-4}<%for.body> Added Flags: <nusw>
 
 ; LAA: [PSE]  %arrayidxA = getelementptr inbounds i16, i16* %a, i32 %mul:
 ; LAA-NEXT: ((2 * (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64))<nsw> + %a)<nsw>
-; LAA-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64)) + %a),+,-4}<%for.body>
+; LAA-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64))<nsw> + %a),+,-4}<%for.body>
 
 ; LV-LABEL: f5
 ; LV-LABEL: for.body.lver.check
 ; LV: [[OFMul:%[^ ]*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[BETrunc:%[^ ]*]])
 ; LV-NEXT: [[OFMulResult:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 0
 ; LV-NEXT: [[OFMulOverflow:%[^ ]*]] = extractvalue { i32, i1 } [[OFMul]], 1
 ; LV-NEXT: [[AddEnd:%[^ ]*]] = add i32 [[Start:%[^ ]*]], [[OFMulResult]]
 ; LV-NEXT: [[SubEnd:%[^ ]*]] = sub i32 [[Start]], [[OFMulResult]]

llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll

 ; Demonstrate a situation when we can add two recs with different degrees from
 ; the same loop.
 define void @test_05(i32 %N) {
 
 ; CHECK-LABEL: Classifying expressions for: @test_05
 ; 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>
 
 entry:
         %"alloca point" = bitcast i32 0 to i32           ; <i32> [#uses=0]
         br label %bb3
 
 bb:             ; preds = %bb3

llvm/test/Analysis/ScalarEvolution/extract-highbits-sameconstmask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -S -analyze -scalar-evolution < %s | FileCheck %s
 
 ; The obvious case.
 define i32 @div(i32 %val) nounwind {
 ; CHECK-LABEL: 'div'
 ; CHECK-NEXT:  Classifying expressions for: @div
 ; 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
   %tmp2 = mul i32 %tmp1, 16
   ret i32 %tmp2
 }
 
 define i32 @sdiv(i32 %val) nounwind {
 ; CHECK-LABEL: 'sdiv'
 ; CHECK-NEXT:  Classifying expressions for: @sdiv
 ; 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
   %tmp2 = mul i32 %tmp1, 16
   ret i32 %tmp2
 }
 
 ; Or, it could be a number of equivalent patterns with mask:
 ;   b) x &  (-1 << nbits)
 ;   d) x >> nbits << nbits
 
 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
   ret i32 %masked
 }
 
 define i32 @mask_d(i32 %val) nounwind {
 ; CHECK-LABEL: 'mask_d'
 ; CHECK-NEXT:  Classifying expressions for: @mask_d
 ; 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
   %masked = shl i32 %lowbitscleared, 4
   ret i32 %masked
 }

llvm/test/Analysis/ScalarEvolution/lshr-shl-differentconstmask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -S -analyze -scalar-evolution < %s | FileCheck %s
 
 ; The obvious case.
 define i32 @udiv_biggerLshr(i32 %val) nounwind {
 ; CHECK-LABEL: 'udiv_biggerLshr'
 ; CHECK-NEXT:  Classifying expressions for: @udiv_biggerLshr
 ; 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
   %tmp2 = mul i32 %tmp1, 16
   ret i32 %tmp2
 }
 
 define i32 @udiv_biggerShl(i32 %val) nounwind {

 ; Or, it could have been transformed to shifts
 
 define i32 @shifty_biggerLshr(i32 %val) {
 ; CHECK-LABEL: 'shifty_biggerLshr'
 ; CHECK-NEXT:  Classifying expressions for: @shifty_biggerLshr
 ; 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
   %tmp2 = shl i32 %tmp1, 4
   ret i32 %tmp2
 }
 
 define i32 @shifty_biggerLshr_lshrexact(i32 %val) {
 ; CHECK-LABEL: 'shifty_biggerLshr_lshrexact'
 ; CHECK-NEXT:  Classifying expressions for: @shifty_biggerLshr_lshrexact
 ; 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
   %tmp2 = shl i32 %tmp1, 4
   ret i32 %tmp2
 }
 
 define i32 @shifty_biggerShr(i32 %val) {

 ; Or, further folded into mask variant.
 
 define i32 @masky_biggerLshr(i32 %val) {
 ; CHECK-LABEL: 'masky_biggerLshr'
 ; CHECK-NEXT:  Classifying expressions for: @masky_biggerLshr
 ; 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
   %tmp2 = and i32 %tmp1, -16
   ret i32 %tmp2
 }
 
 define i32 @masky_biggerLshr_lshrexact(i32 %val) {
 ; CHECK-LABEL: 'masky_biggerLshr_lshrexact'
 ; CHECK-NEXT:  Classifying expressions for: @masky_biggerLshr_lshrexact
 ; CHECK-NEXT:    %tmp1 = lshr exact i32 %val, 2
 ; CHECK-NEXT:    -->  (%val /u 4) U: [0,1073741824) S: [0,1073741824)
 ; CHECK-NEXT:  Determining loop execution counts for: @masky_biggerLshr_lshrexact
 ;
   %tmp1 = lshr exact i32 %val, 2
   ret i32 %tmp1
 }
 
 define i32 @masky_biggerShr(i32 %val) {
 ; CHECK-LABEL: 'masky_biggerShr'
 ; CHECK-NEXT:  Classifying expressions for: @masky_biggerShr
 ; 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
   %tmp2 = and i32 %tmp1, -64
   ret i32 %tmp2
 }
 
 define i32 @masky_biggerShr_lshrexact(i32 %val) {

llvm/test/Analysis/ScalarEvolution/nsw-offset-assume.ll

 return:                                           ; preds = %bb1.return_crit_edge, %entry
   ret void
 }
 
 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

llvm/test/Analysis/ScalarEvolution/nsw-offset.ll

 
 bb1.return_crit_edge:                             ; preds = %bb1
   br label %return
 
 return:                                           ; preds = %bb1.return_crit_edge, %entry
   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

llvm/test/Analysis/ScalarEvolution/nsw.ll

greater:
   br label %exit
 
 exit:
   %result = phi i32 [ %a, %entry ], [ %tmp2, %greater ]
   ret i32 %result
 }
 
 ; 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
   br label %bb1
 
 bb1:                                              ; preds = %bb1, %bb
   %tmp2 = phi i32* [ %arg, %bb ], [ %tmp5, %bb1 ]
   %tmp3 = phi i32 [ 0, %bb ], [ %tmp4, %bb1 ]
   %tmp4 = add nsw i32 %tmp3, 1
   %tmp5 = getelementptr inbounds i32, i32* %tmp2, i64 1
   %tmp6 = icmp ult i32* %tmp5, %tmp
   br i1 %tmp6, label %bb1, label %bb7
 
 bb7:                                              ; preds = %bb1
   ret i32 %tmp4
 }
 
 ; 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
 
 bb2:                                              ; preds = %bb2, %bb
   %tmp = phi i32* [ %arg, %bb ], [ %tmp4, %bb2 ]
   %tmp4 = getelementptr inbounds i32, i32* %tmp, i64 1
   %tmp3 = icmp ult i32* %tmp4, %arg1

llvm/test/Analysis/ScalarEvolution/predicated-trip-count.ll

 ; true.
 
 ; CHECK: Classifying expressions for: @test2
 
 ; CHECK:      %i.0.ext = sext i16 %i.0 to i32
 ; 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>
 
 define void @test2(i32 %N, i32 %M, i16 %Start) {
 entry:
         br label %bb3
 
 bb:             ; preds = %bb3

llvm/test/Analysis/ScalarEvolution/sext-mul.ll

 ; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
 
 ; CHECK: %tmp9 = shl i64 %tmp8, 33
 ; CHECK-NEXT: --> {{.*}} Exits: (-8589934592 + (8589934592 * (zext i32 %arg2 to i64)))
 ; 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>
 
 define void @foo(i32* nocapture %arg, i32 %arg1, i32 %arg2) {
 bb:
   %tmp = icmp sgt i32 %arg2, 0
   br i1 %tmp, label %bb3, label %bb6

llvm/test/Analysis/ScalarEvolution/shl-lshr-differentconstmask.ll

 ; Or, further folded into mask variant.
 
 define i32 @masky_biggerShl(i32 %val) {
 ; CHECK-LABEL: 'masky_biggerShl'
 ; CHECK-NEXT:  Classifying expressions for: @masky_biggerShl
 ; 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
   %tmp2 = and i32 %tmp1, 268435452
   ret i32 %tmp2
 }
 
 define i32 @masky_biggerShl_shlnuw(i32 %val) {

llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll

loop:
   %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
   %i.next = add i32 %i, 32
   %t = icmp ne i32 %i.next, %s
   br i1 %t, label %loop, label %exit
 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
 }
 
 define void @test3(i32 %n) {
 entry:
   %s = mul i32 %n, 96
   br label %loop
 loop:

llvm/test/Analysis/ScalarEvolution/zext-mul.ll

define void @no_range() {
   %b = mul i32 %a, 4
   %c = zext i32 %b to i64
   ; CHECK: %c
   ; CHECK-NEXT: --> (zext i32 (4 * %a) to i64)
   ret void
 }
 
 ; 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
+}

llvm/test/Transforms/LoopVersioning/incorrect-phi.ll

 ; RUN: opt -loop-versioning -S < %s | FileCheck %s
 
 ; Make sure all PHIs are properly updated in the exit block.  Based on
 ; PR28037.
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @x = external global [2 x [3 x [5 x i16]]]
 
 ; CHECK-LABEL: @phi_with_undef
 define void @phi_with_undef() {
 bb6.lr.ph:                                        ; preds = %bb5.preheader
   br label %bb6
 
 bb6:                                              ; preds = %bb6.lr.ph, %bb6
-  %_tmp1423 = phi i16 [ undef, %bb6.lr.ph ], [ %_tmp142, %bb6 ]
+  %_tmp1423 = phi i64 [ undef, %bb6.lr.ph ], [ %_tmp142, %bb6 ]
   %_tmp123 = getelementptr [2 x [3 x [5 x i16]]], [2 x [3 x [5 x i16]]]* @x, i16 0, i64 undef
-  %_tmp125 = sext i16 %_tmp1423 to i64
-  %_tmp126 = getelementptr [3 x [5 x i16]], [3 x [5 x i16]]* %_tmp123, i16 0, i64 %_tmp125
+  %_tmp126 = getelementptr [3 x [5 x i16]], [3 x [5 x i16]]* %_tmp123, i16 0, i64 %_tmp1423
   %_tmp129 = getelementptr [5 x i16], [5 x i16]* %_tmp126, i16 0, i64 undef
   %_tmp130 = load i16, i16* %_tmp129
   store i16 undef, i16* getelementptr ([2 x [3 x [5 x i16]]], [2 x [3 x [5 x i16]]]* @x, i64 0, i64 undef, i64 undef, i64 undef)
-  %_tmp142 = add i16 %_tmp1423, 1
+  %_tmp142 = add i64 %_tmp1423, 1
   br i1 false, label %bb6, label %loop.exit
 
 loop.exit:                                ; preds = %bb6
-  %_tmp142.lcssa = phi i16 [ %_tmp142, %bb6 ]
+  %_tmp142.lcssa = phi i64 [ %_tmp142, %bb6 ]
   %split = phi i16 [ undef, %bb6 ]
 ; CHECK: %split = phi i16 [ undef, %bb6 ], [ undef, %bb6.lver.orig ]
   br label %bb9
 
 bb9:                                              ; preds = %bb9.loopexit, %bb1
   ret void
 }
 
 ; CHECK-LABEL: @phi_with_non_loop_defined_value
 define void @phi_with_non_loop_defined_value() {
 bb6.lr.ph:                                        ; preds = %bb5.preheader
   %t = add i16 1, 1
   br label %bb6
 
 bb6:                                              ; preds = %bb6.lr.ph, %bb6
-  %_tmp1423 = phi i16 [ undef, %bb6.lr.ph ], [ %_tmp142, %bb6 ]
+  %_tmp1423 = phi i64 [ undef, %bb6.lr.ph ], [ %_tmp142, %bb6 ]
   %_tmp123 = getelementptr [2 x [3 x [5 x i16]]], [2 x [3 x [5 x i16]]]* @x, i16 0, i64 undef
-  %_tmp125 = sext i16 %_tmp1423 to i64
-  %_tmp126 = getelementptr [3 x [5 x i16]], [3 x [5 x i16]]* %_tmp123, i16 0, i64 %_tmp125
+  %_tmp126 = getelementptr [3 x [5 x i16]], [3 x [5 x i16]]* %_tmp123, i16 0, i64 %_tmp1423
   %_tmp129 = getelementptr [5 x i16], [5 x i16]* %_tmp126, i16 0, i64 undef
   %_tmp130 = load i16, i16* %_tmp129
   store i16 undef, i16* getelementptr ([2 x [3 x [5 x i16]]], [2 x [3 x [5 x i16]]]* @x, i64 0, i64 undef, i64 undef, i64 undef)
-  %_tmp142 = add i16 %_tmp1423, 1
+  %_tmp142 = add i64 %_tmp1423, 1
   br i1 false, label %bb6, label %loop.exit
 
 loop.exit:                                ; preds = %bb6
-  %_tmp142.lcssa = phi i16 [ %_tmp142, %bb6 ]
+  %_tmp142.lcssa = phi i64 [ %_tmp142, %bb6 ]
   %split = phi i16 [ %t, %bb6 ]
 ; CHECK: %split = phi i16 [ %t, %bb6 ], [ %t, %bb6.lver.orig ]
   br label %bb9
 
 bb9:                                              ; preds = %bb9.loopexit, %bb1
   ret void
 }