[SCEV] Compute exit count from overflow test

[reames]

Summary

If we have an exit test in a loop which is controlled by the overflow flag on an add.with.overflow intrinsic, we can possible compute which iteration would cause overflow. Knowing an exit count for the loop, then drives LFTR which is then able to rewrite the check in the form which eliminates the need for the overflow check entirely.

(Noticed while looking at the output of the PoisonChecking tool, but unrelated.)

[shchenz]

Thanks very much for doing this, this is exactly what I want to do as a follow-up patch for https://reviews.llvm.org/D64422.

This patch looks most good to me except one PowerPC test case.

With this patch, we can get loop exit for more loops, so we get also get more hardware loops in HardwareLoops pass.
As I tested, one PowerPC FIXME test (main1) llvm/test/CodeGen/PowerPC/negctr.ll fails if accept this patch. Not sure why this is not showed in your patch. Could you help to have a look? Thanks.

llc < test/CodeGen/PowerPC/negctr.ll -mcpu=a2 -verify-machineinstrs | FileCheck test/CodeGen/PowerPC/negctr.ll

[nikic]

lib/Analysis/ScalarEvolution.cpp

7308

It's not wrong, but unnecessarily restrictive and a bit confusing to do the isKnownPositive check for an unsigned addition.

It might make sense to handle the negative stride case right away with a code structure like this:

const SCEV *MaxValue = nullptr, *MinValue = nullptr;
if (WO->getBinaryOp() == Instruction::Add) {
  if (!Signed)
    MaxValue = getMinusSCEV(
        getConstant(APInt::getNullValue(BitWidth)), RHSSCEV);
  else if (isKnownPositive(RHSSCEV))
    MaxValue = getMinusSCEV(
        getConstant(APInt::getSignedMinValue(BitWidth)), RHSSCEV);
  else if (isKnownNegative(RHSSCEV))
    MinValue = getAddExpr(
        getConstant(APInt::getSignedMaxValue(BitWidth)), RHSSCEV);
}
if (MaxValue) { ... howManyLessThans ... }
else if (MinValue) { ... howManyGreaterThans ... }

This should make it easy to extend to Sub as well.

7316

nit: Stray semicolon.

[reames]

Just indicating in the review state that the next action item here is mine. Probably not going to get back to this for a bit, so want that to be clear to reviewers.

[lebedev.ri]

In D64509#1606782, @reames wrote:

Just indicating in the review state that the next action item here is mine. Probably not going to get back to this for a bit, so want that to be clear to reviewers.

@nikic ping?

[reames]

Abandoning an old review I'm not going to return to any time soon.

lib/Analysis/ScalarEvolution.cpp

if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) {
     if (EL.hasFullInfo() || !AllowPredicates)
       return EL;
 
     // Try again, but use SCEV predicates this time.
     return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsExit,
                                     /*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
   // in place.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
     if (ExitIfTrue == !CI->getZExtValue())
       // The backedge is always taken.
       return getCouldNotCompute();

test/Transforms/IndVarSimplify/lftr-overflow.ll

+; 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)