Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -7298,6 +7298,27 @@
                                     /*AllowPredicates=*/true);
   }
 
+  // If we exit on overflow, see if we can compute when that'll happen.
+  if (auto *EVI = dyn_cast<ExtractValueInst>(ExitCond))
+    if (EVI->getType()->isIntegerTy(1) &&
+        EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1)
+      if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
+        // TODO: extend to other overflowing operators and negative strides
+        if (WO->getBinaryOp() == Instruction::Add &&
+            isKnownPositive(getSCEV(WO->getRHS()))) {
+          Value* LHS = WO->getLHS();
+          Value* RHS = WO->getRHS();
+          bool Signed = WO->isSigned();
+          unsigned BitWidth = RHS->getType()->getScalarSizeInBits();
+          const SCEV* OnOverflow =
+            getConstant((Signed ? APInt::getSignedMaxValue(BitWidth) :
+                         APInt::getMaxValue(BitWidth)) + 1);
+          const SCEV *MaxValue = getMinusSCEV(OnOverflow, getSCEV(RHS));;
+          ExitLimit EL = howManyLessThans(getSCEV(LHS), MaxValue, L, Signed,
+                                          ControlsExit, AllowPredicates);
+          if (EL.hasAnyInfo()) return EL;
+        }
+
   // Check for a constant condition. These are normally stripped out by
   // SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to
   // preserve the CFG and is temporarily leaving constant conditions
Index: test/Transforms/IndVarSimplify/lftr-overflow.ll
===================================================================
--- test/Transforms/IndVarSimplify/lftr-overflow.ll
+++ test/Transforms/IndVarSimplify/lftr-overflow.ll
@@ -0,0 +1,409 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -indvars -S | FileCheck %s
+; RUN: opt < %s -passes='indvars' -S 2>&1 | FileCheck %s
+
+; If we have an exit controlled by an overflow check, rewrite it using LFTR
+; to eliminate the overflow check within the loop.
+
+target datalayout = "n8:16:32:64"
+
+define void @sadd_positive(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @sadd_positive(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 2147483647
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[EXITCOND1:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[EXITCOND1]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %iv, i32 1)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add nuw nsw i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+; TODO: not yet handled
+define void @sadd_negative(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @sadd_negative(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
+; CHECK-NEXT:    [[ADDO:%.*]] = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP1]], i32 -2)
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[ADDO]], 1
+; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[INDVARS_IV]], 0
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ %n, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %iv, i32 -2)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add nsw i32 %iv, -1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ugt i32 %iv, 0
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+define void @sadd_zero(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @sadd_zero(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br i1 false, label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %iv, i32 0)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add nuw nsw i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+define void @sadd_unknown(i8* nocapture %base, i32 %n, i32 %stride) {
+; CHECK-LABEL: @sadd_unknown(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
+; CHECK-NEXT:    [[ADDO:%.*]] = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[TMP1]], i32 [[STRIDE:%.*]])
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[ADDO]], 1
+; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %iv, i32 %stride)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add nuw nsw i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+define void @sadd_invariant_lhs(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @sadd_invariant_lhs(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[ADDO:%.*]] = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[N]], i32 [[N]])
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[ADDO]], 1
+; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %n, i32 %n)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add nuw nsw i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+define void @uadd_positive(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @uadd_positive(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 4294967295
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND1:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND1]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %iv, i32 1)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add nuw i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+; TODO: not yet handled
+define void @uadd_negative(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @uadd_negative(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
+; CHECK-NEXT:    [[ADDO:%.*]] = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[TMP1]], i32 -2)
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[ADDO]], 1
+; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[INDVARS_IV]], 0
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ %n, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %iv, i32 -2)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add i32 %iv, -1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ugt i32 %iv, 0
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+define void @uadd_zero(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @uadd_zero(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br i1 false, label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %iv, i32 0)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+define void @uadd_unknown(i8* nocapture %base, i32 %n, i32 %stride) {
+; CHECK-LABEL: @uadd_unknown(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
+; CHECK-NEXT:    [[ADDO:%.*]] = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[TMP1]], i32 [[STRIDE:%.*]])
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[ADDO]], 1
+; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %iv, i32 %stride)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+define void @uadd_invariant_lhs(i8* nocapture %base, i32 %n) {
+; CHECK-LABEL: @uadd_invariant_lhs(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i64
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[ADDO:%.*]] = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[N]], i32 [[N]])
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[ADDO]], 1
+; CHECK-NEXT:    br i1 [[OVERFLOW]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[P:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
+  %addo = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %n, i32 %n)
+  %overflow = extractvalue { i32, i1 } %addo, 1
+  br i1 %overflow, label %exit, label %latch
+latch:
+  %iv.next = add nuw nsw i32 %iv, 1
+  %zext = zext i32 %iv to i64
+  %p = getelementptr inbounds i8, i8* %base, i64 %zext
+  store i8 0, i8* %p, align 1
+  %cmp = icmp ult i32 %iv, %n
+  br i1 %cmp, label %loop, label %exit
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32)
+declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32)