[indvars] Visit all IV users in simplifyAndExtend

[reames]

Summary

The basic idea of this patch is simple - we remove the restriction on only visiting users of addrecs from simplifyAndExtend, and instead allow users of any scevable instruction derived from an IV. Doing this exposes a couple of subtleties (explained below).

As seen in the test diffs, this does help eliminate some code which wasn't previously handled, but the primary value is making some of the code run in Scalar/IndVarSimplify.cpp after simplifyAndEtend effectively dead. (To be removed in separate patches with their own review.)

The first subtlety here is that additional simplification can actually lead to inferior results - due to missing invalidation. The case that happens is we fold an icmp in simplifyAndExtend, but leave the SCEV tripcount for that loop as an could-not-compute. Following code, specifically predicateLoops, then can't run. Without this change, we'd instead hit optimizeLoopExits which would invalidate, and thus loop predication would run.

To address this, we must invalidate when we simplify a loop exit condition. We could just always invalidate, but that could require O(LoopSize) rebuilds of SCEV for the loop. From prior work on strengthenNoWrapFlags, we know that is sometimes prohibitive. This patch only invalidates on loop exit condition changes, so the worse case should be O(LoopExits) rebuilds. In theory, you could have an adversarial loop when number exits ~= loop size, but in practice, the number of loop exits should be much smaller.

@nikic Could you confirm this doesn't have an excessive compile time?

The second subtly shows up in the loop-unroll test change. In this case, unrolling produces *worse* codegen for an up to date SCEV trip count. We have a dead exit, which was proven untaken and folded. With stale info, unroll recognizes that the cached trip count (10) is dead, and folds the branch. With up to date info (could-not-compute, e.g. never taken), unroll does not look at the actual CFG and leaves the branch unfolded. This is in my view an uninteresting quirk of the unroll implementation, and not something worth fixing.

[nikic]

The impact is pretty substantial: https://llvm-compile-time-tracker.com/compare.php?from=6b6564fcf9f5cce91630d1888d7e95b187bfc320&to=60e0c60fba7eedf3bd25f45beb980e05fd1418db&stat=instructions
Though the big increase on tramp3d-v4 seems to be due to a large code size increase: https://llvm-compile-time-tracker.com/compare.php?from=6b6564fcf9f5cce91630d1888d7e95b187bfc320&to=60e0c60fba7eedf3bd25f45beb980e05fd1418db&stat=size-text

[reames]

In D112170#3076258, @nikic wrote:

The impact is pretty substantial.

Crud. That's definitely too high for the minor code reduction benefit.

I've got one more idea on how to do coarser invalidation once after simplifyAndExtend, let me iterate on this and get a new version up. If that doesn't work, we'll have to simply drop the idea entirely.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) {
   const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
   const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
 
   // If the condition is always true or always false in the given context,
   // replace it with a constant value.
   SmallVector<Instruction *, 4> Users;
   for (auto *U : ICmp->users())
     Users.push_back(cast<Instruction>(U));
+  auto invalidateIfProfitable = [&]() {
+    // In general, we don't need to invalidate here as, at worst, we're leaving
+    // SCEV in a correct, but inprecise state.  Invalidating is expensive as
+    // it forces recomputation of potentially all SCEVs in the loop on the next
+    // instruction visited.  However, by not invalidating we can end up with
+    // very sub-optimal results.   This heuristic tries to invalidate only when
+    // we know we've discharged a loop exit condition and have thus discovered
+    // new information likely to greatly simplify SCEVs in the loop.
+    for (auto *I : Users) {
+      if (isa<BranchInst>(I) || isa<SwitchInst>(I)) {
+        if (ICmpLoop->isLoopExiting(I->getParent())) {
+          SE->forgetLoop(ICmpLoop);
+          return;
+        }
+      }
+    }
+  };
   const Instruction *CtxI = findCommonDominator(Users, *DT);
   if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {
     ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));
     DeadInsts.emplace_back(ICmp);
+    invalidateIfProfitable();
     LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
   } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
+    invalidateIfProfitable();
     // fallthrough to end of function
   } else if (ICmpInst::isSigned(OriginalPred) &&
              SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
     // If we were unable to make anything above, all we can is to canonicalize
     // the comparison hoping that it will open the doors for other
     // optimizations. If we find out that we compare two non-negative values,
     // we turn the instruction's predicate to its unsigned version. Note that
     // we cannot rely on Pred here unless we check if we have swapped it.
for (User *U : Def->users()) {
     // Do not push the same instruction more than once.
     if (!Simplified.insert(UI).second)
       continue;
 
     SimpleIVUsers.push_back(std::make_pair(UI, Def));
   }
 }
 
-/// Return true if this instruction generates a simple SCEV
-/// expression in terms of that IV.
-///
-/// This is similar to IVUsers' isInteresting() but processes each instruction
-/// non-recursively when the operand is already known to be a simpleIVUser.
-///
-static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
-  if (!SE->isSCEVable(I->getType()))
-    return false;
-
-  // Get the symbolic expression for this instruction.
-  const SCEV *S = SE->getSCEV(I);
-
-  // Only consider affine recurrences.
-  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
-  if (AR && AR->getLoop() == L)
-    return true;
-
-  return false;
-}
-
 /// Iteratively perform simplification on a worklist of users
 /// of the specified induction variable. Each successive simplification may push
 /// more users which may themselves be candidates for simplification.
 ///
 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
 /// instructions in-place during analysis. Rather than rewriting induction
 /// variables bottom-up from their users, it transforms a chain of IVUsers
 /// top-down, updating the IR only when it encounters a clear optimization
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
       }
     }
 
     CastInst *Cast = dyn_cast<CastInst>(UseInst);
     if (V && Cast) {
       V->visitCast(Cast);
       continue;
     }
-    if (isSimpleIVUser(UseInst, L, SE)) {
+    if (SE->isSCEVable(UseInst->getType())) {
       pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
     }
   }
 }
 
 namespace llvm {
 
 void IVVisitor::anchor() { }

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

exit:                                             ; preds = %loop2.exit, %loop1
   ret i32 0
 }
 
 define i32 @testRem(i8* %p, i64* %p1) {
 ; CHECK-LABEL: @testRem(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 ; CHECK:       loop1:
-; CHECK-NEXT:    [[LOCAL_0_:%.*]] = phi i32 [ 8, [[ENTRY:%.*]] ], [ [[I9:%.*]], [[LOOP2_EXIT:%.*]] ]
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LOCAL_0_]], 15
+; CHECK-NEXT:    [[INDVARS_IV1:%.*]] = phi i64 [ [[INDVARS_IV_NEXT2:%.*]], [[LOOP2_EXIT:%.*]] ], [ 8, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV1]], 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:    [[TMP0:%.*]] = udiv i32 14, [[LOCAL_0_]]
-; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 60392, [[TMP0]]
-; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP2]], [[TMP0]]
-; CHECK-NEXT:    [[TMP4:%.*]] = sext i32 [[TMP3]] to i64
-; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i64 [[TMP4]], 60392
+; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[INDVARS_IV1]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 14, [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = udiv i32 60392, [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP2]], -1
+; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 [[TMP3]], [[TMP1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = sext i32 [[TMP4]] to i64
+; CHECK-NEXT:    [[TMP6:%.*]] = add nsw i64 [[TMP5]], 60392
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
-; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP5]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP2]] ]
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP6]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP2]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8
 ; CHECK-NEXT:    [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    store atomic i64 [[I6]], i64* [[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:    [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br label %loop1
 
 loop1:                                            ; preds = %loop2.exit, %entry

llvm/test/Transforms/IndVarSimplify/eliminate-exit-no-dl.ll

 @global = external global [0 x i8], align 1
 
 define void @foo() {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @global, i64 0, i64 2), i64 -1
-; CHECK-NEXT:    [[TMP6:%.*]] = load i8, i8* [[TMP4]], align 1
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ugt i8* [[TMP4]], getelementptr inbounds ([0 x i8], [0 x i8]* @global, i64 0, i64 500)
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB7:%.*]], label [[BB11:%.*]]
 ; CHECK:       bb7:
-; CHECK-NEXT:    [[TMP8:%.*]] = zext i8 [[TMP6]] to i64
 ; CHECK-NEXT:    br i1 true, label [[BB11]], label [[BB3]]
 ; CHECK:       bb11:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   br label %bb3
 
 bb3:                                              ; preds = %bb7, %bb2

llvm/test/Transforms/IndVarSimplify/infer-poison-flags.ll

 define void @ashr_cr_nsw() {
 ; CHECK-LABEL: @ashr_cr_nsw(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ -1024, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[I_NEXT]] = ashr i32 [[I]], 1
 ; CHECK-NEXT:    store i32 [[I]], i32* @A, align 4
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[I_NEXT]], 1
-; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[LOOPEXIT:%.*]]
 ; CHECK:       loopexit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   %i = phi i32 [ -1024, %entry ], [ %i.next, %loop ]

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

;
   ret i32 42
 }
 
 define hidden void @test.shl.exact.equal() {
 ; CHECK-LABEL: @test.shl.exact.equal(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
-; CHECK-NEXT:    [[SHR1:%.*]] = ashr exact i32 [[SHL]], 1
-; CHECK-NEXT:    [[SHR2:%.*]] = lshr exact i32 [[SHL]], 1
-; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:
for.end:
   ret void
 }
 
 define hidden void @test.shl.exact.greater() {
 ; CHECK-LABEL: @test.shl.exact.greater(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 3, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
-; CHECK-NEXT:    [[SHR1:%.*]] = ashr exact i32 [[SHL]], 2
-; CHECK-NEXT:    [[SHR2:%.*]] = lshr exact i32 [[SHL]], 2
-; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:
for.end:
   ret void
 }
 
 define hidden void @test.shl.exact.unbound(i32 %arg) {
 ; CHECK-LABEL: @test.shl.exact.unbound(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
-; CHECK-NEXT:    [[SHR1:%.*]] = ashr exact i32 [[SHL]], 2
-; CHECK-NEXT:    [[SHR2:%.*]] = lshr exact i32 [[SHL]], 2
-; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:
for.end:
   ret void
 }
 
 define hidden void @test.shl.nonexact() {
 ; CHECK-LABEL: @test.shl.nonexact(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
-; CHECK-NEXT:    [[SHR1:%.*]] = ashr i32 [[SHL]], 3
-; CHECK-NEXT:    [[SHR2:%.*]] = lshr i32 [[SHL]], 3
-; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:

llvm/test/Transforms/IndVarSimplify/zext-nuw.ll

 ; CHECK:       .preheader4.lr.ph:
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[X4]], -1
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP1]] to i64
 ; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i64 [[TMP2]], 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = sext i8 [[J_SROA_0_0_COPYLOAD]] to i64
 ; CHECK-NEXT:    [[TMP5:%.*]] = mul i64 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    br label [[DOTPREHEADER4:%.*]]
 ; CHECK:       .preheader4:
-; CHECK-NEXT:    [[K_09:%.*]] = phi i8* [ undef, [[DOTPREHEADER4_LR_PH]] ], [ [[X25:%.*]], [[X22:%.*]] ]
+; CHECK-NEXT:    [[K_09:%.*]] = phi i8* [ undef, [[DOTPREHEADER4_LR_PH]] ], [ [[K_1_LCSSA:%.*]], [[X22:%.*]] ]
 ; CHECK-NEXT:    [[X8:%.*]] = icmp ult i32 0, 4
 ; CHECK-NEXT:    br i1 [[X8]], label [[DOTPREHEADER_LR_PH:%.*]], label [[X22]]
 ; CHECK:       .preheader.lr.ph:
 ; CHECK-NEXT:    br label [[DOTPREHEADER:%.*]]
 ; CHECK:       .preheader:
 ; CHECK-NEXT:    br label [[X17:%.*]]
 ; CHECK:       x17:
 ; CHECK-NEXT:    br i1 false, label [[DOTPREHEADER]], label [[DOT_CRIT_EDGE_8:%.*]]
 ; CHECK:       ._crit_edge.8:
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, i8* [[K_09]], i64 [[TMP5]]
 ; CHECK-NEXT:    br label [[X22]]
 ; CHECK:       x22:
-; CHECK-NEXT:    [[K_1_LCSSA:%.*]] = phi i8* [ [[SCEVGEP]], [[DOT_CRIT_EDGE_8]] ], [ [[K_09]], [[DOTPREHEADER4]] ]
-; CHECK-NEXT:    [[X25]] = getelementptr i8, i8* [[K_1_LCSSA]]
+; CHECK-NEXT:    [[K_1_LCSSA]] = phi i8* [ [[SCEVGEP]], [[DOT_CRIT_EDGE_8]] ], [ [[K_09]], [[DOTPREHEADER4]] ]
 ; CHECK-NEXT:    br label [[DOTPREHEADER4]]
 ;
   %x2 = load i32, i32* @d
   %x3 = icmp slt i32 %x2, 1
   %x4 = select i1 %x3, i32 1, i32 %x2
   %x5 = load %struct.A*, %struct.A** @c
   %j.sroa.0.0..sroa_idx = getelementptr %struct.A, %struct.A* %x5, i64 0, i32 0
   %j.sroa.0.0.copyload = load i8, i8* %j.sroa.0.0..sroa_idx

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

 ; EPILOG-BLOCK-NEXT:    br label %outerloop
 ; EPILOG-BLOCK:       outerloop.loopexit.loopexit:
 ; EPILOG-BLOCK-NEXT:    br label %outerloop.loopexit
 ; EPILOG-BLOCK:       outerloop.loopexit:
 ; EPILOG-BLOCK-NEXT:    br i1 false, label %exit.unr-lcssa.1, label %outerloop.new.1
 ; 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:    %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-NEXT:    br i1 false, 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 ]
 ; EPILOG-BLOCK-NEXT:    %niter = phi i64 [ %unroll_iter, %outerloop.new ], [ %niter.nsub.1, %latch.1 ]
 ; EPILOG-BLOCK-NEXT:    %i4 = add nuw nsw i64 %i3, 1
 ; EPILOG-BLOCK-NEXT:    br i1 false, label %outerloop.loopexit.loopexit, label %latch

 ; PROLOG-BLOCK-NEXT:    br label %outerloop
 ; PROLOG-BLOCK:       outerloop.loopexit.loopexit:
 ; PROLOG-BLOCK-NEXT:    br label %outerloop.loopexit
 ; PROLOG-BLOCK:       outerloop.loopexit:
 ; PROLOG-BLOCK-NEXT:    br i1 false, label %innerH.prol.preheader.1, label %innerH.prol.loopexit.1
 ; 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:    %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
 ; PROLOG-BLOCK:       latch.prol:
 ; PROLOG-BLOCK-NEXT:    br label %innerH.prol.loopexit
 ; PROLOG-BLOCK:       innerH.prol.loopexit:
 ; PROLOG-BLOCK-NEXT:    %i3.unr = phi i64 [ %i, %outerloop ], [ %i4.prol, %latch.prol ]
-; PROLOG-BLOCK-NEXT:    %2 = icmp ult i64 %1, 1
-; PROLOG-BLOCK-NEXT:    br i1 %2, label %exit.loopexit, label %outerloop.new
+; PROLOG-BLOCK-NEXT:    br i1 false, label %exit.loopexit, label %outerloop.new
 ; PROLOG-BLOCK:       outerloop.new:
 ; PROLOG-BLOCK-NEXT:    br label %innerH
 ; PROLOG-BLOCK:       innerH:
 ; PROLOG-BLOCK-NEXT:    %i3 = phi i64 [ %i3.unr, %outerloop.new ], [ %i4.1, %latch.1 ]
 ; PROLOG-BLOCK-NEXT:    %i4 = add nuw nsw i64 %i3, 1
 ; PROLOG-BLOCK-NEXT:    br i1 false, label %outerloop.loopexit.loopexit, label %latch
 ; PROLOG-BLOCK:       latch:
 ; PROLOG-BLOCK-NEXT:    %i4.1 = add nuw nsw i64 %i4, 1

llvm/test/Transforms/LoopUnroll/scevunroll.ll

 define i32 @multiExitIncomplete(i32* %base) nounwind {
 ; CHECK-LABEL: @multiExitIncomplete(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[L1:%.*]]
 ; CHECK:       l1:
 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, i32* [[BASE:%.*]], align 4
 ; CHECK-NEXT:    br label [[L2:%.*]]
 ; CHECK:       l2:
-; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK-NEXT:    br i1 true, label [[L3:%.*]], label [[EXIT2:%.*]]
 ; CHECK:       l3:
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[VAL]], 0
 ; CHECK-NEXT:    br i1 [[CMP3]], label [[L1_1:%.*]], label [[EXIT3:%.*]]
 ; CHECK:       exit1:
 ; CHECK-NEXT:    ret i32 1
 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret i32 2
 ; CHECK:       exit3:
 ; CHECK-NEXT:    ret i32 3
 ; CHECK:       l1.1:
 ; CHECK-NEXT:    [[ADR_1:%.*]] = getelementptr i32, i32* [[BASE]], i32 1
 ; CHECK-NEXT:    [[VAL_1:%.*]] = load i32, i32* [[ADR_1]], align 4
 ; CHECK-NEXT:    br label [[L2_1:%.*]]
 ; CHECK:       l2.1:
-; CHECK-NEXT:    br label [[L3_1:%.*]]
+; CHECK-NEXT:    br i1 true, label [[L3_1:%.*]], label [[EXIT2]]
 ; CHECK:       l3.1:
 ; CHECK-NEXT:    [[CMP3_1:%.*]] = icmp ne i32 [[VAL_1]], 0
 ; CHECK-NEXT:    br i1 [[CMP3_1]], label [[L1_2:%.*]], label [[EXIT3]]
 ; CHECK:       l1.2:
 ; CHECK-NEXT:    [[ADR_2:%.*]] = getelementptr i32, i32* [[BASE]], i32 2
 ; CHECK-NEXT:    [[VAL_2:%.*]] = load i32, i32* [[ADR_2]], align 4
 ; CHECK-NEXT:    br label [[L2_2:%.*]]
 ; CHECK:       l2.2:
-; CHECK-NEXT:    br label [[L3_2:%.*]]
+; CHECK-NEXT:    br i1 true, label [[L3_2:%.*]], label [[EXIT2]]
 ; CHECK:       l3.2:
 ; CHECK-NEXT:    [[CMP3_2:%.*]] = icmp ne i32 [[VAL_2]], 0
 ; CHECK-NEXT:    br i1 [[CMP3_2]], label [[L1_3:%.*]], label [[EXIT3]]
 ; CHECK:       l1.3:
 ; CHECK-NEXT:    [[ADR_3:%.*]] = getelementptr i32, i32* [[BASE]], i32 3
 ; CHECK-NEXT:    [[VAL_3:%.*]] = load i32, i32* [[ADR_3]], align 4
 ; CHECK-NEXT:    br label [[L2_3:%.*]]
 ; CHECK:       l2.3:
-; CHECK-NEXT:    br label [[L3_3:%.*]]
+; CHECK-NEXT:    br i1 true, label [[L3_3:%.*]], label [[EXIT2]]
 ; CHECK:       l3.3:
 ; CHECK-NEXT:    [[CMP3_3:%.*]] = icmp ne i32 [[VAL_3]], 0
 ; CHECK-NEXT:    br i1 [[CMP3_3]], label [[L1_4:%.*]], label [[EXIT3]]
 ; CHECK:       l1.4:
 ; CHECK-NEXT:    [[ADR_4:%.*]] = getelementptr i32, i32* [[BASE]], i32 4
 ; CHECK-NEXT:    [[VAL_4:%.*]] = load i32, i32* [[ADR_4]], align 4
 ; CHECK-NEXT:    br label [[L2_4:%.*]]
 ; CHECK:       l2.4:
-; CHECK-NEXT:    br label [[L3_4:%.*]]
+; CHECK-NEXT:    br i1 true, label [[L3_4:%.*]], label [[EXIT2]]
 ; CHECK:       l3.4:
 ; CHECK-NEXT:    [[CMP3_4:%.*]] = icmp ne i32 [[VAL_4]], 0
 ; CHECK-NEXT:    br i1 [[CMP3_4]], label [[L1_5:%.*]], label [[EXIT3]]
 ; CHECK:       l1.5:
 ; CHECK-NEXT:    br i1 false, label [[L2_5:%.*]], label [[EXIT1:%.*]]
 ; CHECK:       l2.5:
-; CHECK-NEXT:    br i1 true, label [[L3_5:%.*]], label [[EXIT2:%.*]]
+; CHECK-NEXT:    br i1 true, label [[L3_5:%.*]], label [[EXIT2]]
 ; CHECK:       l3.5:
 ; CHECK-NEXT:    br label [[EXIT3]]
 ;
 entry:
   br label %l1
 l1:
   %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ]
   %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ]

 ; CHECK-LABEL: @nsw_latch(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    br i1 false, label [[RETURN:%.*]], label [[FOR_BODY_1:%.*]]
 ; CHECK:       return:
-; CHECK-NEXT:    [[B_03_LCSSA:%.*]] = phi i32 [ 0, [[FOR_COND]] ], [ 8, [[FOR_BODY_1]] ], [ 0, [[FOR_COND_1:%.*]] ]
+; CHECK-NEXT:    [[B_03_LCSSA:%.*]] = phi i32 [ 8, [[FOR_COND]] ], [ 8, [[FOR_BODY_1]] ], [ 8, [[FOR_COND_1:%.*]] ]
 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ 0, [[FOR_COND]] ], [ 1, [[FOR_BODY_1]] ], [ 0, [[FOR_COND_1]] ]
 ; CHECK-NEXT:    store i32 [[B_03_LCSSA]], i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ; CHECK:       for.body.1:
 ; CHECK-NEXT:    br i1 false, label [[FOR_COND_1]], label [[RETURN]]
 ; CHECK:       for.cond.1:
 ; CHECK-NEXT:    br label [[RETURN]]
 ;