Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -2340,6 +2340,20 @@
   // 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.
Index: llvm/test/Analysis/ScalarEvolution/guards.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/guards.ll
+++ llvm/test/Analysis/ScalarEvolution/guards.ll
@@ -23,7 +23,7 @@
 ; 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:%.*]]
@@ -57,7 +57,7 @@
 ; 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:
Index: llvm/test/Analysis/ScalarEvolution/pr44605.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/pr44605.ll
+++ llvm/test/Analysis/ScalarEvolution/pr44605.ll
@@ -16,10 +16,10 @@
 ; 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]]
Index: llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll
+++ llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll
@@ -17,7 +17,7 @@
 ; 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:
@@ -80,7 +80,7 @@
 ; 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:
Index: llvm/test/Transforms/IndVarSimplify/canonicalize-cmp.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/canonicalize-cmp.ll
+++ llvm/test/Transforms/IndVarSimplify/canonicalize-cmp.ll
@@ -150,7 +150,7 @@
 ; 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:
@@ -198,7 +198,7 @@
 ; 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:
Index: llvm/test/Transforms/IndVarSimplify/elim-extend.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/elim-extend.ll
+++ llvm/test/Transforms/IndVarSimplify/elim-extend.ll
@@ -115,7 +115,7 @@
 ; 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:%.*]] ]
@@ -129,7 +129,6 @@
 ; 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]] ]
@@ -138,7 +137,8 @@
 ; 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]] ]
@@ -152,8 +152,8 @@
 ; 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
 ;
Index: llvm/test/Transforms/IndVarSimplify/lftr-reuse.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/lftr-reuse.ll
+++ llvm/test/Transforms/IndVarSimplify/lftr-reuse.ll
@@ -148,7 +148,7 @@
 ; 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:%.*]]
Index: llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll
+++ llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll
@@ -19,7 +19,7 @@
 ; 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]]
@@ -68,7 +68,7 @@
 ; 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]]
Index: llvm/test/Transforms/IndVarSimplify/strengthen-overflow.ll
===================================================================
--- llvm/test/Transforms/IndVarSimplify/strengthen-overflow.ll
+++ llvm/test/Transforms/IndVarSimplify/strengthen-overflow.ll
@@ -304,7 +304,7 @@
 ; 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:
Index: llvm/test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll
===================================================================
--- llvm/test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll
+++ llvm/test/Transforms/LoopUnroll/runtime-loop-multiple-exits.ll
@@ -4729,8 +4729,8 @@
 ; 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
@@ -4872,8 +4872,8 @@
 ; 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