[SCEV] Improve willNotOverflow by checking min/max in wide range with context

[mkazantsev]

Summary

This patch adds a context-aware analysis that tris to prove that (Op, LHS, RHS) does
not overflow. The basic version of this algorithm takes wide type which is 2x wider
than the original type and tries to prove that ext(LHS + RHS) == ext(LHS) + ext(RHS),
and the context-aware analysis only works with constants and their ranges.

This one adds the following logic: we compute three values:

1. B = ext(LHS) + ext(RHS);
2. min = ext(MIN_VALUE) (i.e. min value of LHS's original type);
3. max = ext(MAX_VALUE) (i.e. max value of LHS's original type);

And if we can prove that in the given context min <= B <= max, then the computation
was without overflow (i.e. result is still in bounds in terms of original type).

There is one regression with IV widening, but this transform has long been known
for being unstable and awkwardly broken, and it needs to be fixed separately.
In most cases it allows us to infer more no-wrap flags.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/guards.ll

26

Arguably regression

llvm/test/Transforms/IndVarSimplify/elim-extend.ll

141

Regression, but apparently fix should be in other place.

[nikic]

Predictably, this is not good for compile-time: http://llvm-compile-time-tracker.com/compare.php?from=94adb39b85e069728ebdb6f31c76f98f4355f66b&to=7283c676f8f2a5a785bac67c9393aad6405a8ab9&stat=instructions:u

[mkazantsev]

Can we do it under expensive sharpening flag? It's really annoying how CT constrains cuts capabilities of SCEV to use contextual facts...

[mkazantsev]

Found a regression rebased on it.

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/strengthen-overflow.ll

307

Regression.

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/strengthen-overflow.ll

307

This regression isn't even because the analysis gives a better result. It's simply because we make a query... Weird.

[mkazantsev]

I'm going with more lightweight solution.

llvm/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
   const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
   const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
   const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0);
   if (A == B)
     return true;
   // Can we use context to prove the fact we need?
   if (!CtxI)
     return false;
+  // If result of operation in wide type is between narrow min/max extended to
+  // wide type, it means that the computation was without overflow.
+  const SCEV *NarrowMin =
+      getConstant(Signed ? APInt::getSignedMinValue(NarrowTy->getBitWidth())
+                         : APInt::getMinValue(NarrowTy->getBitWidth()));
+  const SCEV *NarrowMax =
+      getConstant(Signed ? APInt::getSignedMaxValue(NarrowTy->getBitWidth())
+                         : APInt::getMaxValue(NarrowTy->getBitWidth()));
+  const SCEV *WideMin = (this->*Extension)(NarrowMin, WideTy, 0);
+  const SCEV *WideMax = (this->*Extension)(NarrowMax, WideTy, 0);
+  ICmpInst::Predicate LEPred = Signed ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
+  if (isKnownPredicateAt(LEPred, WideMin, B, CtxI) &&
+      isKnownPredicateAt(LEPred, B, WideMax, CtxI))
+    return true;
   // We can prove that add(x, constant) doesn't wrap if isKnownPredicateAt can
   // guarantee that x <= max_int - constant at the given context.
   // TODO: Support other operations.
   if (BinOp != Instruction::Add)
     return false;
   auto *RHSC = dyn_cast<SCEVConstant>(RHS);
   // TODO: Lift this limitation.
   if (!RHSC)

llvm/test/Analysis/ScalarEvolution/guards.ll

 ; CHECK-SAME: (ptr [[COND_BUF:%.*]], ptr [[LEN_BUF:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_BUF]], align 4, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add nsw i32 [[IV]], 1
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
-; CHECK-NEXT:    [[IV_INC_CMP:%.*]] = icmp ult i32 [[IV_INC]], [[LEN]]
+; CHECK-NEXT:    [[IV_INC_CMP:%.*]] = icmp slt i32 [[IV_INC]], [[LEN]]
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[IV_INC_CMP]]) [ "deopt"() ]
 ; CHECK-NEXT:    [[BECOND:%.*]] = load volatile i1, ptr [[COND_BUF]], align 1
 ; CHECK-NEXT:    br i1 [[BECOND]], label [[LOOP]], label [[LEAVE:%.*]]
 ; CHECK:       leave:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %len = load i32, ptr %len_buf, !range !{i32 1, i32 2147483648}
leave:
   ret void
 }
 
 define void @test_2(i32 %n, ptr %len_buf) {
 ; CHECK-LABEL: define void @test_2
 ; CHECK-SAME: (i32 [[N:%.*]], ptr [[LEN_BUF:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_BUF]], align 4, !range [[RNG1:![0-9]+]]
-; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[LEN]] to i64
+; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[LEN]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[N]] to i64
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    call void @use(i64 [[INDVARS_IV]])
 ; CHECK-NEXT:    [[IV_INC_CMP:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT]], [[TMP0]]
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[IV_INC_CMP]]) [ "deopt"() ]

llvm/test/Analysis/ScalarEvolution/pr44605.ll

 ; CHECK-NEXT:    [[LOCAL_6_6:%.*]] = phi i32 [ 10, [[ENTRY:%.*]] ], [ [[TMP5:%.*]], [[LATCH:%.*]] ]
 ; CHECK-NEXT:    [[LOCAL_4_5:%.*]] = phi i32 [ 56587, [[ENTRY]] ], [ 0, [[LATCH]] ]
 ; CHECK-NEXT:    [[LOCAL_3_4:%.*]] = phi i32 [ 2, [[ENTRY]] ], [ [[TMP5]], [[LATCH]] ]
 ; CHECK-NEXT:    [[DOTUDIV:%.*]] = udiv i32 [[LOCAL_6_6]], 8361
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[LOCAL_7_3:%.*]] = phi i32 [ 2, [[OUTER]] ], [ [[TMP3:%.*]], [[INNER]] ]
 ; CHECK-NEXT:    [[LOCAL_4_5_PN:%.*]] = phi i32 [ [[LOCAL_4_5]], [[OUTER]] ], [ [[TMP2:%.*]], [[INNER]] ]
-; CHECK-NEXT:    [[LOCAL_3_31:%.*]] = mul i32 [[LOCAL_4_5_PN]], [[DOTUDIV]]
+; CHECK-NEXT:    [[LOCAL_3_31:%.*]] = mul nuw nsw i32 [[LOCAL_4_5_PN]], [[DOTUDIV]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw nsw i32 [[LOCAL_7_3]], [[DOTUDIV]]
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[TMP0]], [[LOCAL_3_4]]
-; CHECK-NEXT:    [[TMP2]] = add i32 [[TMP1]], [[LOCAL_3_31]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub nsw i32 [[TMP0]], [[LOCAL_3_4]]
+; CHECK-NEXT:    [[TMP2]] = add nuw nsw i32 [[TMP1]], [[LOCAL_3_31]]
 ; CHECK-NEXT:    [[TMP3]] = add nuw nsw i32 [[LOCAL_7_3]], 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i32 [[LOCAL_7_3]], 4
 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LATCH]], label [[INNER]]
 ; CHECK:       latch:
 ; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ [[TMP2]], [[INNER]] ]
 ; CHECK-NEXT:    [[TMP5]] = add nuw nsw i32 [[LOCAL_6_6]], 1
 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i32 [[LOCAL_6_6]], 276
 ; CHECK-NEXT:    br i1 [[TMP6]], label [[RETURN:%.*]], label [[OUTER]]

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 15
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]]
 ; CHECK:       general_case24:
 ; CHECK-NEXT:    br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP2_EXIT]]
 ; CHECK:       loop2.preheader:
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, ptr [[P1:%.*]] unordered, align 8
-; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], -1
+; CHECK-NEXT:    [[I6:%.*]] = sub nuw nsw i64 [[I4]], -1
 ; CHECK-NEXT:    store atomic i64 [[I6]], ptr [[P1]] unordered, align 8
 ; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:

 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LOCAL_0_]], 15
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]]
 ; CHECK:       general_case24:
 ; CHECK-NEXT:    br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP2_EXIT]]
 ; CHECK:       loop2.preheader:
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, ptr [[P1:%.*]] unordered, align 8
-; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], -1
+; CHECK-NEXT:    [[I6:%.*]] = sub nuw nsw i64 [[I4]], -1
 ; CHECK-NEXT:    store atomic i64 [[I6]], ptr [[P1]] unordered, align 8
 ; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    [[I9]] = add nuw nsw i32 [[LOCAL_0_]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:

llvm/test/Transforms/IndVarSimplify/canonicalize-cmp.ll

 define i32 @test_03(ptr %p, ptr %capacity_p, ptr %num_elements_p) {
 ; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CAPACITY:%.*]] = load i32, ptr [[CAPACITY_P:%.*]], align 4, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    [[NUM_ELEMENTS:%.*]] = load i32, ptr [[NUM_ELEMENTS_P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nsw i32 [[CAPACITY]], [[IV]]
+; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nuw nsw i32 [[CAPACITY]], [[IV]]
 ; CHECK-NEXT:    [[CAPACITY_CHECK:%.*]] = icmp slt i32 [[BYTES_TO_WRITE]], 4
 ; CHECK-NEXT:    br i1 [[CAPACITY_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P:%.*]], i32 [[IV]]
 ; CHECK-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[NUM_ELEMENTS]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]

 define i32 @test_04(ptr %p, ptr %capacity_p, ptr %num_elements_p) {
 ; CHECK-LABEL: @test_04(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CAPACITY:%.*]] = load i32, ptr [[CAPACITY_P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    [[NUM_ELEMENTS:%.*]] = load i32, ptr [[NUM_ELEMENTS_P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nsw i32 [[CAPACITY]], [[IV]]
+; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nuw nsw i32 [[CAPACITY]], [[IV]]
 ; CHECK-NEXT:    [[CAPACITY_CHECK:%.*]] = icmp sle i32 [[BYTES_TO_WRITE]], 3
 ; CHECK-NEXT:    br i1 [[CAPACITY_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P:%.*]], i32 [[IV]]
 ; CHECK-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[NUM_ELEMENTS]]
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]

llvm/test/Transforms/IndVarSimplify/elim-extend.ll

 ; %innercount is currently blocked by lcssa, so is not widened.
 ; %inneriv can be widened only after proving it has no signed-overflow
 ;   based on the loop test.
 define void @nestedIV(ptr %address, i32 %limit) nounwind {
 ; CHECK-LABEL: @nestedIV(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LIMITDEC:%.*]] = add i32 [[LIMIT:%.*]], -1
 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT]], i32 1)
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT4:%.*]] = zext i32 [[SMAX]] to i64
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[SMAX]] to i64
 ; CHECK-NEXT:    br label [[OUTERLOOP:%.*]]
 ; CHECK:       outerloop:
 ; CHECK-NEXT:    [[INDVARS_IV1:%.*]] = phi i64 [ [[INDVARS_IV_NEXT2:%.*]], [[OUTERMERGE:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[INNERCOUNT:%.*]] = phi i32 [ [[INNERCOUNT_MERGE:%.*]], [[OUTERMERGE]] ], [ 0, [[ENTRY]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[INDVARS_IV1]], -1
 ; CHECK-NEXT:    [[ADR1:%.*]] = getelementptr i8, ptr [[ADDRESS:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    store i8 0, ptr [[ADR1]], align 1
 ; CHECK-NEXT:    br label [[INNERPREHEADER:%.*]]
 ; CHECK:       innerpreheader:
 ; CHECK-NEXT:    [[INNERPRECMP:%.*]] = icmp sgt i32 [[LIMITDEC]], [[INNERCOUNT]]
 ; CHECK-NEXT:    br i1 [[INNERPRECMP]], label [[INNERLOOP_PREHEADER:%.*]], label [[OUTERMERGE]]
 ; CHECK:       innerloop.preheader:
 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[INNERCOUNT]] to i64
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = sext i32 [[LIMITDEC]] to i64
 ; CHECK-NEXT:    br label [[INNERLOOP:%.*]]
 ; CHECK:       innerloop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP1]], [[INNERLOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[INNERLOOP]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[ADR2:%.*]] = getelementptr i8, ptr [[ADDRESS]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    store i8 0, ptr [[ADR2]], align 1
 ; CHECK-NEXT:    [[ADR3:%.*]] = getelementptr i8, ptr [[ADDRESS]], i64 [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    store i8 0, ptr [[ADR3]], align 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[LIMITDEC]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[INNERLOOP]], label [[INNEREXIT:%.*]]
 ; CHECK:       innerexit:
 ; CHECK-NEXT:    [[INNERCOUNT_LCSSA_WIDE:%.*]] = phi i64 [ [[INDVARS_IV_NEXT]], [[INNERLOOP]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[INNERCOUNT_LCSSA_WIDE]] to i32
 ; CHECK-NEXT:    br label [[OUTERMERGE]]
 ; CHECK:       outermerge:
 ; CHECK-NEXT:    [[INNERCOUNT_MERGE]] = phi i32 [ [[TMP2]], [[INNEREXIT]] ], [ [[INNERCOUNT]], [[INNERPREHEADER]] ]
 ; CHECK-NEXT:    [[ADR4:%.*]] = getelementptr i8, ptr [[ADDRESS]], i64 [[INDVARS_IV1]]
 ; CHECK-NEXT:    store i8 0, ptr [[ADR4]], align 1
 ; CHECK-NEXT:    [[OFS5:%.*]] = sext i32 [[INNERCOUNT_MERGE]] to i64
 ; CHECK-NEXT:    [[ADR5:%.*]] = getelementptr i8, ptr [[ADDRESS]], i64 [[OFS5]]
 ; CHECK-NEXT:    store i8 0, ptr [[ADR5]], align 1
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], 1
-; CHECK-NEXT:    [[EXITCOND5:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT2]], [[WIDE_TRIP_COUNT4]]
-; CHECK-NEXT:    br i1 [[EXITCOND5]], label [[OUTERLOOP]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[EXITCOND4:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT2]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[EXITCOND4]], label [[OUTERLOOP]], label [[RETURN:%.*]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %limitdec = add i32 %limit, -1
   br label %outerloop
 
 ; Eliminate %ofs1 after widening outercount.

llvm/test/Transforms/IndVarSimplify/lftr-reuse.ll

 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[LOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], [[INDVARS_IV2]]
 ; CHECK-NEXT:    [[MATRIXP:%.*]] = getelementptr inbounds [0 x double], ptr [[MATRIX:%.*]], i32 0, i64 [[TMP1]]
 ; CHECK-NEXT:    [[V1:%.*]] = load double, ptr [[MATRIXP]], align 8
 ; CHECK-NEXT:    call void @use(double [[V1]])
 ; CHECK-NEXT:    [[VECTORP:%.*]] = getelementptr inbounds [0 x double], ptr [[VECTOR:%.*]], i32 0, i64 [[INDVARS_IV2]]
 ; CHECK-NEXT:    [[V2:%.*]] = load double, ptr [[VECTORP]], align 8
 ; CHECK-NEXT:    call void @use(double [[V2]])
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], [[TMP0]]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], [[TMP0]]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT3]] = add nuw nsw i64 [[INDVARS_IV2]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT3]], [[WIDE_TRIP_COUNT]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[RETURN_LOOPEXIT:%.*]]
 ; CHECK:       return.loopexit:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll

 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nsw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
 ; CHECK-NEXT:    [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void

 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
 ; CHECK:       range_check_block:
-; CHECK-NEXT:    [[IV_NEXT]] = sub i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = sub nsw i32 [[IV]], 1
 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
 ; CHECK-NEXT:    [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/IndVarSimplify/strengthen-overflow.ll

 
 define void @test_infer_nsw(ptr %p) {
 ; CHECK-LABEL: @test_infer_nsw(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[FREEZE:%.*]] = freeze i32 poison
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD:%.*]], [[BB2:%.*]] ], [ 0, [[BB:%.*]] ]
-; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[FREEZE]], [[PHI]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[FREEZE]], [[PHI]]
 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp sgt i32 [[SUB]], 1
 ; CHECK-NEXT:    br i1 [[ICMP]], label [[BB2]], label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i16 1, ptr [[P:%.*]], align 2
 ; CHECK-NEXT:    [[ADD]] = add nuw i32 [[PHI]], 2
 ; CHECK-NEXT:    br label [[BB1]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll

 ; EPILOG-BLOCK:       innerH.epil.preheader.1:
 ; EPILOG-BLOCK-NEXT:    br label %innerH.epil.1
 ; EPILOG-BLOCK:       innerH.epil.1:
 ; EPILOG-BLOCK-NEXT:    br i1 false, label %outerloop.loopexit.1, label %latch.epil
 ; EPILOG-BLOCK:       outerloop.loopexit.1:
 ; EPILOG-BLOCK-NEXT:    br label %outerloop, !llvm.loop !13
 ; EPILOG-BLOCK:       outerloop:
 ; EPILOG-BLOCK-NEXT:    %i = phi i64 [ 3, %bb ], [ 0, %outerloop.loopexit.1 ]
-; EPILOG-BLOCK-NEXT:    %0 = sub i64 100, %i
-; EPILOG-BLOCK-NEXT:    %1 = sub i64 99, %i
+; EPILOG-BLOCK-NEXT:    %0 = sub nuw nsw i64 100, %i
+; EPILOG-BLOCK-NEXT:    %1 = sub nuw nsw i64 99, %i
 ; EPILOG-BLOCK-NEXT:    %xtraiter = and i64 %0, 1
 ; EPILOG-BLOCK-NEXT:    %2 = icmp ult i64 %1, 1
 ; EPILOG-BLOCK-NEXT:    br i1 %2, label %exit.unr-lcssa, label %outerloop.new
 ; EPILOG-BLOCK:       outerloop.new:
 ; EPILOG-BLOCK-NEXT:    %unroll_iter = sub i64 %0, %xtraiter
 ; EPILOG-BLOCK-NEXT:    br label %innerH
 ; EPILOG-BLOCK:       innerH:
 ; EPILOG-BLOCK-NEXT:    %i3 = phi i64 [ %i, %outerloop.new ], [ %i4.1, %latch.1 ]

 ; PROLOG-BLOCK-NEXT:    %i6.1.1 = icmp ult i64 %i4.1.1, 100
 ; PROLOG-BLOCK-NEXT:    br i1 %i6.1.1, label %innerH.1, label %exit.unr-lcssa.loopexit3, !llvm.loop !12
 ; PROLOG-BLOCK:       outerloop.loopexit.loopexit.1:
 ; PROLOG-BLOCK-NEXT:    br label %outerloop.loopexit.1
 ; PROLOG-BLOCK:       outerloop.loopexit.1:
 ; PROLOG-BLOCK-NEXT:    br label %outerloop, !llvm.loop !13
 ; PROLOG-BLOCK:       outerloop:
 ; PROLOG-BLOCK-NEXT:    %i = phi i64 [ 3, %bb ], [ 0, %outerloop.loopexit.1 ]
-; PROLOG-BLOCK-NEXT:    %0 = sub i64 100, %i
-; PROLOG-BLOCK-NEXT:    %1 = sub i64 99, %i
+; PROLOG-BLOCK-NEXT:    %0 = sub nuw nsw i64 100, %i
+; PROLOG-BLOCK-NEXT:    %1 = sub nuw nsw i64 99, %i
 ; PROLOG-BLOCK-NEXT:    %xtraiter = and i64 %0, 1
 ; PROLOG-BLOCK-NEXT:    %lcmp.mod = icmp ne i64 %xtraiter, 0
 ; PROLOG-BLOCK-NEXT:    br i1 %lcmp.mod, label %innerH.prol.preheader, label %innerH.prol.loopexit
 ; PROLOG-BLOCK:       innerH.prol.preheader:
 ; PROLOG-BLOCK-NEXT:    br label %innerH.prol
 ; PROLOG-BLOCK:       innerH.prol:
 ; PROLOG-BLOCK-NEXT:    %i4.prol = add nuw nsw i64 %i, 1
 ; PROLOG-BLOCK-NEXT:    br i1 false, label %outerloop.loopexit, label %latch.prol