[SCEVExpander] Increase "cheap" expansion budget for loop invariants, but not loop exit values

[lebedev.ri]

Summary

It is known that having some magical cut-off does just that,
it prevents very large regressions, but is potentially suboptimal
in certain cases.

There has been several reports that the current budget
is just a tad bit too small, and by making SCEV smarter,
e.g. teaching it to handle new IR patterns,
instead of representing them as SCEVUnknown,
makes problem worse.

This current constant, 4, was never meant
to be The One True Value, but rather it seemed like
the right choice at the time.

Currently, we use it for 3 purposes:

• loop exit value rewriting
• loop trip/exit count expansion
• loop invariant expansion

Now, the loop trip/exit count is a special case of
the loop invariant, so let's treat them as one.
Out of the three, loop exit value is the problematic one.

Let's split the budget into two, and bump the loop invariant one.

[nikic]

There has been several reports that the current budget is just a tad bit too small

At the same time, we also regularly get complaints about exit values getting expanded where just reusing the final IV value would be cheaper, and raising the expansion limit is certainly going to make that situation worse.

Raising the expansion budget will improve some cases and regress others. For a heuristic cutoff, this is expected and fine. However, I would expect some kind of supporting data that the new value is indeed, on average, an improvement and not a regression.

[lebedev.ri]

Currently, we use the budget for 3 purposes:

• loop exit value rewriting
• loop trip/exit count expansion
• loop invariant expansion

Now, the loop trip/exit count is a special case of
the loop invariant, so let's treat them as one.
Out of the three, loop exit value is indeed the problematic one.

Let's split the budget into two, and bump the loop invariant one.

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/X86/eliminate-trunc.ll

10

NFC-regenerate tests? Yes, it' extremely annoying since they've updated this script. :(

[lebedev.ri]

@mkazantsev done

[lebedev.ri]

With unchanged budget for loop exit value expansion, does anyone have any further comments here?
I'd like to add, it is unusual that unroll checks the cost of the trip count, clearly other passes don't?

[nikic]

I'd be more comfortable with this if it adjusted just the unroll limit, where a higher cost is probably justifiable relative to the cost of everything else. This change affects a lot of transforms, and from the test diffs alone, some of them look non-profitable to me, e.g. most of the changes in llvm/test/Transforms/IndVarSimplify/post-inc-range.ll due to questionable LFTR transforms.

[lebedev.ri]

In D139858#4001178, @nikic wrote:

I'd be more comfortable with this if it adjusted just the unroll limit, where a higher cost is probably justifiable relative to the cost of everything else.

This change affects a lot of transforms, and from the test diffs alone, some of them look non-profitable to me, e.g. most of the changes in llvm/test/Transforms/IndVarSimplify/post-inc-range.ll due to questionable LFTR transforms.

I'm not sure i understand. This kind of change we see in post-inc-range.ll, is exactly why i bothered to unbreak the original isHighCostExpansion originally in the first place.

[nikic]

In D139858#4001242, @lebedev.ri wrote:

In D139858#4001178, @nikic wrote:

I'd be more comfortable with this if it adjusted just the unroll limit, where a higher cost is probably justifiable relative to the cost of everything else.
This change affects a lot of transforms, and from the test diffs alone, some of them look non-profitable to me, e.g. most of the changes in llvm/test/Transforms/IndVarSimplify/post-inc-range.ll due to questionable LFTR transforms.

I'm not sure i understand. This kind of change we see in post-inc-range.ll, is exactly why i bothered to unbreak the original isHighCostExpansion originally in the first place.

I'm probably missing some subtlety of IV canonicalization here. As far as I can tell those transforms a) add more instructions outside the loop, b) add more instructions inside the loop and c) introduce a trunc inside the loop, which is an analysis blocker (ext is better than trunc) and all that to convert an slt into ne for an IV we can already analyze as-is. If there's a benefit to all this, it's not obvious to me.

[lebedev.ri]

ping

[nikic]

I don't think my previous comment on non-profitable transforms in post-inc-range.ll has been addressed.

[lebedev.ri]

D140698

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/InstructionCost.h"
 
 namespace llvm {
-extern cl::opt<unsigned> SCEVCheapExpansionBudget;
+extern cl::opt<unsigned> SCEVCheapLoopInvariantExpansionBudget;
+extern cl::opt<unsigned> SCEVCheapLoopExitValueExpansionBudget;
 
 /// struct for holding enough information to help calculate the cost of the
 /// given SCEV when expanded into IR.
 struct SCEVOperand {
   explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) :
     ParentOpcode(Opc), OperandIdx(Idx), S(S) { }
   /// LLVM instruction opcode that uses the operand.
   unsigned ParentOpcode;

llvm/lib/Target/BPF/BPFTargetTransformInfo.h

int getIntImmCost(const APInt &Imm, Type *Ty, TTI::TargetCostKind CostKind) {
     return TTI::TCC_Basic;
   }
 
   InstructionCost getCmpSelInstrCost(unsigned Opcode, Type *ValTy, Type *CondTy,
                                      CmpInst::Predicate VecPred,
                                      TTI::TargetCostKind CostKind,
                                      const llvm::Instruction *I = nullptr) {
     if (Opcode == Instruction::Select)
-      return SCEVCheapExpansionBudget.getValue();
+      return std::max(SCEVCheapLoopInvariantExpansionBudget.getValue(),
+                      SCEVCheapLoopExitValueExpansionBudget.getValue());
 
     return BaseT::getCmpSelInstrCost(Opcode, ValTy, CondTy, VecPred, CostKind,
                                      I);
   }
 
   InstructionCost getArithmeticInstrCost(
       unsigned Opcode, Type *Ty, TTI::TargetCostKind CostKind,
       TTI::OperandValueInfo Op1Info = {TTI::OK_AnyValue, TTI::OP_None},
       TTI::OperandValueInfo Op2Info = {TTI::OK_AnyValue, TTI::OP_None},
       ArrayRef<const Value *> Args = ArrayRef<const Value *>(),
       const Instruction *CxtI = nullptr) {
-      int ISD = TLI->InstructionOpcodeToISD(Opcode);
-      if (ISD == ISD::ADD && CostKind == TTI::TCK_RecipThroughput)
-        return SCEVCheapExpansionBudget.getValue() + 1;
+      return std::max(SCEVCheapLoopInvariantExpansionBudget.getValue(),
+                      SCEVCheapLoopExitValueExpansionBudget.getValue()) +
+             1;
 
-      return BaseT::getArithmeticInstrCost(Opcode, Ty, CostKind, Op1Info,
-                                           Op2Info);
   }
 
   TTI::MemCmpExpansionOptions enableMemCmpExpansion(bool OptSize,
                                                     bool IsZeroCmp) const {
     TTI::MemCmpExpansionOptions Options;
     Options.LoadSizes = {8, 4, 2, 1};
     Options.MaxNumLoads = TLI->getMaxExpandSizeMemcmp(OptSize);
     return Options;
   }
 
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_BPF_BPFTARGETTRANSFORMINFO_H

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

for (BasicBlock *ExitingBB : ExitingBlocks) {
         continue;
 
       PHINode *IndVar = FindLoopCounter(L, ExitingBB, ExitCount, SE, DT);
       if (!IndVar)
         continue;
 
       // Avoid high cost expansions.  Note: This heuristic is questionable in
       // that our definition of "high cost" is not exactly principled.
-      if (Rewriter.isHighCostExpansion(ExitCount, L, SCEVCheapExpansionBudget,
+      if (Rewriter.isHighCostExpansion(ExitCount, L,
+                                       SCEVCheapLoopInvariantExpansionBudget,
                                        TTI, PreHeader->getTerminator()))
         continue;
 
       // Check preconditions for proper SCEVExpander operation. SCEV does not
       // express SCEVExpander's dependencies, such as LoopSimplify. Instead
       // any pass that uses the SCEVExpander must do it. This does not work
       // well for loop passes because SCEVExpander makes assumptions about
       // all loops, while LoopPassManager only forces the current loop to be

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

if (isa<SCEVCouldNotCompute>(TripCountSC)) {
     return false;
   }
 
   BasicBlock *PreHeader = L->getLoopPreheader();
   BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
   const DataLayout &DL = Header->getModule()->getDataLayout();
   SCEVExpander Expander(*SE, DL, "loop-unroll");
   if (!AllowExpensiveTripCount &&
-      Expander.isHighCostExpansion(TripCountSC, L, SCEVCheapExpansionBudget,
-                                   TTI, PreHeaderBR)) {
+      Expander.isHighCostExpansion(TripCountSC, L,
+                                   SCEVCheapLoopInvariantExpansionBudget, TTI,
+                                   PreHeaderBR)) {
     LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
     return false;
   }
 
   // This constraint lets us deal with an overflowing trip count easily; see the
   // comment on ModVal below.
   if (Log2_32(Count) > BEWidth) {
     LLVM_DEBUG(

llvm/lib/Transforms/Utils/LoopUtils.cpp

while ((PN = dyn_cast<PHINode>(BBI++))) {
         // the ExitValue already. TODO: This should be merged into SCEV
         // expander to leverage its knowledge of existing expressions.
         if (ReplaceExitValue != AlwaysRepl && !isa<SCEVConstant>(ExitValue) &&
             !isa<SCEVUnknown>(ExitValue) && hasHardUserWithinLoop(L, Inst))
           continue;
 
         // Check if expansions of this SCEV would count as being high cost.
         bool HighCost = Rewriter.isHighCostExpansion(
-            ExitValue, L, SCEVCheapExpansionBudget, TTI, Inst);
+            ExitValue, L, SCEVCheapLoopExitValueExpansionBudget, TTI, Inst);
 
         // Note that we must not perform expansions until after
         // we query *all* the costs, because if we perform temporary expansion
         // inbetween, one that we might not intend to keep, said expansion
         // *may* affect cost calculation of the the next SCEV's we'll query,
         // and next SCEV may errneously get smaller cost.
 
         // Collect all the candidate PHINodes to be rewritten.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
 #define SCEV_DEBUG_WITH_TYPE(TYPE, X) DEBUG_WITH_TYPE(TYPE, X)
 #else
 #define SCEV_DEBUG_WITH_TYPE(TYPE, X)
 #endif
 
 using namespace llvm;
 
-cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(
-    "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
-    cl::desc("When performing SCEV expansion only if it is cheap to do, this "
+cl::opt<unsigned> llvm::SCEVCheapLoopInvariantExpansionBudget(
+    "scev-cheap-loop-trip-count-expansion-budget", cl::Hidden, cl::init(8),
+    cl::desc("When performing SCEV expansion of loop loop invariants "
+             "(including trip/exit counts) only if it is cheap to do, this "
+             "controls the budget that is considered cheap (default = 8)"));
+
+cl::opt<unsigned> llvm::SCEVCheapLoopExitValueExpansionBudget(
+    "scev-cheap-loop-exit-value-expansion-budget", cl::Hidden, cl::init(4),
+    cl::desc("When performing SCEV expansion of loop exit values only if it is "
+             "cheap to do, this "
              "controls the budget that is considered cheap (default = 4)"));
 
 using namespace PatternMatch;
 
 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
 /// reusing an existing cast if a suitable one (= dominating IP) exists, or
 /// creating a new one.
 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
   if (!LIP)
     return false;
   ICmpInst::Predicate InvariantPredicate = LIP->Pred;
   const SCEV *InvariantLHS = LIP->LHS;
   const SCEV *InvariantRHS = LIP->RHS;
 
   // Do not generate something ridiculous.
   auto *PHTerm = Preheader->getTerminator();
-  if (Rewriter.isHighCostExpansion({ InvariantLHS, InvariantRHS }, L,
-                                   2 * SCEVCheapExpansionBudget, TTI, PHTerm))
+  if (Rewriter.isHighCostExpansion({InvariantLHS, InvariantRHS}, L,
+                                   2 * SCEVCheapLoopInvariantExpansionBudget,
+                                   TTI, PHTerm))
     return false;
   auto *NewLHS =
       Rewriter.expandCodeFor(InvariantLHS, IVOperand->getType(), PHTerm);
   auto *NewRHS =
       Rewriter.expandCodeFor(InvariantRHS, IVOperand->getType(), PHTerm);
   LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');
   ICmp->setPredicate(InvariantPredicate);
   ICmp->setOperand(0, NewLHS);
bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {
 
   // Get the symbolic expression for this instruction.
   const SCEV *S = SE->getSCEV(I);
 
   if (!SE->isLoopInvariant(S, L))
     return false;
 
   // Do not generate something ridiculous even if S is loop invariant.
-  if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))
+  if (Rewriter.isHighCostExpansion(S, L, SCEVCheapLoopInvariantExpansionBudget,
+                                   TTI, I))
     return false;
 
   auto *IP = GetLoopInvariantInsertPosition(L, I);
 
   if (!Rewriter.isSafeToExpandAt(S, IP)) {
     LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I
                       << " with non-speculable loop invariant: " << *S << '\n');
     return false;

llvm/test/Transforms/IndVarSimplify/X86/eliminate-trunc.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=indvars -S -indvars-predicate-loops=0 < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; General case: without extra knowledge, trunc cannot be eliminated.
 define void @test_00(i64 %start, i32 %n) {
 ;
 ; CHECK-LABEL: @test_00(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 ; CHECK-NEXT:    [[NARROW_IV:%.*]] = trunc i64 [[IV]] to i32
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[NARROW_IV]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]

 exit:
   ret void
 }
 
 ; Check that we can eliminate both signed and unsigned compare.
 define void @test_08(i32 %n) {
 ; CHECK-LABEL: @test_08(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[N:%.*]] to i64
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[N]] to i64
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[N:%.*]], i32 1)
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[SMAX]], -1
+; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[N]], i32 1)
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[UMAX]], -1
+; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP0]], i32 [[TMP1]])
+; CHECK-NEXT:    [[TMP2:%.*]] = add nuw i32 [[UMIN]], 2
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP2]] to i64
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i64 [[IV]], [[SEXT]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[IV]], [[ZEXT]]
-; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[TMP0]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[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:
   %iv = phi i64 [ 1, %entry ], [ %iv.next, %loop ]
   %iv.next = add i64 %iv, 1

llvm/test/Transforms/IndVarSimplify/X86/loop-invariant-conditions.ll

 for.end:                                          ; preds = %if.end, %entry
   ret void
 }
 
 ; The branch has to exit the loop if the condition is true
 define void @test3_neg(i64 %start) {
 ; CHECK-LABEL: @test3_neg(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[START:%.*]], i64 -1)
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[SMAX]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
-; CHECK-NEXT:    br i1 [[CMP1]], label [[LOOP]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
   %indvars.iv.next = add nsw i64 %indvars.iv, 1
   %cmp1 = icmp slt i64 %indvars.iv, -1
   br i1 %cmp1, label %loop, label %for.end
 
 for.end:                                          ; preds = %if.end, %entry
   ret void
 }
 
 define void @test4_neg(i64 %start) {
 ; CHECK-LABEL: @test4_neg(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[START:%.*]], i64 0)
+; CHECK-NEXT:    [[TMP0:%.*]] = add nuw i64 [[SMAX]], 1
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    call void @foo()
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i64 [[INDVARS_IV]], -1
-; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END]], label [[LOOP]]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END]], label [[LOOP]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -passes=indvars -scev-cheap-expansion-budget=1024 %s | FileCheck %s
+; RUN: opt -S -passes=indvars -scev-cheap-loop-trip-count-expansion-budget=1024 -scev-cheap-loop-exit-value-expansion-budget=1024 %s | FileCheck %s
 
 ; See https://bugs.llvm.org/show_bug.cgi?id=45360
 ; This is reduced from that (runnable) test.
 ; The remainder operation is originally guarded, it never divides by zero.
 ; Indvars should not make it execute unconditionally.
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-linux-gnu"

llvm/test/Transforms/IndVarSimplify/post-inc-range.ll

 exit:
   ret void
 }
 
 define void @test_range_metadata(ptr %array_length_ptr, ptr %base,
 ; CHECK-LABEL: @test_range_metadata(
 ; CHECK-NEXT:  for.body.lr.ph:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[START:%.*]] to i64
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[LIMIT:%.*]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[START]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT:%.*]], i32 [[TMP1]])
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_INC:%.*]] ], [ [[TMP0]], [[FOR_BODY_LR_PH:%.*]] ]
 ; CHECK-NEXT:    [[ARRAY_LENGTH:%.*]] = load i32, ptr [[ARRAY_LENGTH_PTR:%.*]], align 4, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[ARRAY_LENGTH]] to i64
 ; CHECK-NEXT:    [[WITHIN_LIMITS:%.*]] = icmp ult i64 [[INDVARS_IV]], [[TMP2]]
 ; CHECK-NEXT:    br i1 [[WITHIN_LIMITS]], label [[CONTINUE:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       continue:
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END]]
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[SMAX]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
   i32 %limit, i32 %start) {
 
 for.body.lr.ph:
exit:
   ret void
 }
 
 define void @test_transitive_use(ptr %base, i32 %limit, i32 %start) {
 ; CHECK-LABEL: @test_transitive_use(
 ; CHECK-NEXT:  for.body.lr.ph:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[START:%.*]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[LIMIT:%.*]] to i64
-; CHECK-NEXT:    [[TMP2:%.*]] = sext i32 [[LIMIT]] to i64
 ; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[START]], i32 64)
 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[UMAX]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[START]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT]], i32 [[TMP2]])
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_INC:%.*]] ], [ [[TMP0]], [[FOR_BODY_LR_PH:%.*]] ]
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV]], [[WIDE_TRIP_COUNT]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[CONTINUE:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       continue:
 ; CHECK-NEXT:    [[TMP3:%.*]] = mul nuw nsw i64 [[INDVARS_IV]], 3
 ; CHECK-NEXT:    [[MUL_WITHIN:%.*]] = icmp ult i64 [[TMP3]], 64
 ; CHECK-NEXT:    br i1 [[MUL_WITHIN]], label [[GUARDED:%.*]], label [[CONTINUE_2:%.*]]
 ; CHECK:       guarded:
 ; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[TMP3]], 1
 ; CHECK-NEXT:    [[RESULT:%.*]] = icmp slt i64 [[TMP4]], [[TMP1]]
 ; CHECK-NEXT:    br i1 [[RESULT]], label [[CONTINUE_2]], label [[FOR_END]]
 ; CHECK:       continue.2:
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT]], [[TMP2]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END]]
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND3:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[SMAX]]
+; CHECK-NEXT:    br i1 [[EXITCOND3]], label [[FOR_BODY]], label [[FOR_END]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 
 for.body.lr.ph:
   br label %for.body

 }
 
 declare void @llvm.experimental.guard(i1, ...)
 
 define void @test_guard_one_bb(ptr %base, i32 %limit, i32 %start) {
 ; CHECK-LABEL: @test_guard_one_bb(
 ; CHECK-NEXT:  for.body.lr.ph:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[START:%.*]] to i64
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[LIMIT:%.*]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[START]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT:%.*]], i32 [[TMP1]])
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ [[TMP0]], [[FOR_BODY_LR_PH:%.*]] ]
 ; CHECK-NEXT:    [[WITHIN_LIMITS:%.*]] = icmp ult i64 [[INDVARS_IV]], 64
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WITHIN_LIMITS]]) [ "deopt"() ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[SMAX]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 
 for.body.lr.ph:
   br label %for.body

 exit:
   ret void
 }
 
 define void @test_guard_in_the_same_bb(ptr %base, i32 %limit, i32 %start) {
 ; CHECK-LABEL: @test_guard_in_the_same_bb(
 ; CHECK-NEXT:  for.body.lr.ph:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[START:%.*]] to i64
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[LIMIT:%.*]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[START]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT:%.*]], i32 [[TMP1]])
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_INC:%.*]] ], [ [[TMP0]], [[FOR_BODY_LR_PH:%.*]] ]
 ; CHECK-NEXT:    [[WITHIN_LIMITS:%.*]] = icmp ult i64 [[INDVARS_IV]], 64
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WITHIN_LIMITS]]) [ "deopt"() ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[SMAX]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 
 for.body.lr.ph:
   br label %for.body

 exit:
   ret void
 }
 
 define void @test_guard_in_idom(ptr %base, i32 %limit, i32 %start) {
 ; CHECK-LABEL: @test_guard_in_idom(
 ; CHECK-NEXT:  for.body.lr.ph:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[START:%.*]] to i64
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[LIMIT:%.*]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[START]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT:%.*]], i32 [[TMP1]])
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_INC:%.*]] ], [ [[TMP0]], [[FOR_BODY_LR_PH:%.*]] ]
 ; CHECK-NEXT:    [[WITHIN_LIMITS:%.*]] = icmp ult i64 [[INDVARS_IV]], 64
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WITHIN_LIMITS]]) [ "deopt"() ]
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[SMAX]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 
 for.body.lr.ph:
   br label %for.body

 exit:
   ret void
 }
 
 define void @test_guard_merge_ranges(ptr %base, i32 %limit, i32 %start) {
 ; CHECK-LABEL: @test_guard_merge_ranges(
 ; CHECK-NEXT:  for.body.lr.ph:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[START:%.*]] to i64
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[LIMIT:%.*]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[START]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT:%.*]], i32 [[TMP1]])
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ [[TMP0]], [[FOR_BODY_LR_PH:%.*]] ]
 ; CHECK-NEXT:    [[WITHIN_LIMITS_1:%.*]] = icmp ult i64 [[INDVARS_IV]], 64
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WITHIN_LIMITS_1]]) [ "deopt"() ]
 ; CHECK-NEXT:    [[WITHIN_LIMITS_2:%.*]] = icmp ult i64 [[INDVARS_IV]], 2147483647
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WITHIN_LIMITS_2]]) [ "deopt"() ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[SMAX]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 
 for.body.lr.ph:
   br label %for.body

llvm/test/Transforms/IndVarSimplify/pr45835.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=indvars -replexitval=always -S | FileCheck %s --check-prefix=ALWAYS
 ; RUN: opt < %s -passes=indvars -replexitval=never -S | FileCheck %s --check-prefix=NEVER
-; RUN: opt < %s -passes=indvars -replexitval=cheap -scev-cheap-expansion-budget=1 -S | FileCheck %s --check-prefix=CHEAP
+; RUN: opt < %s -passes=indvars -replexitval=cheap -scev-cheap-loop-trip-count-expansion-budget=1 -scev-cheap-loop-exit-value-expansion-budget=1 -S | FileCheck %s --check-prefix=CHEAP
 
 ; rewriteLoopExitValues() must rewrite all or none of a PHI's values from a given block.
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 @a = common global i8 0, align 1
 
 define internal fastcc void @d(ptr %c) unnamed_addr #0 {

llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-values-phi.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -passes=indvars -S %s -o - | FileCheck %s
+; RUN: opt -passes=indvars -scev-cheap-loop-trip-count-expansion-budget=4 -scev-cheap-loop-exit-value-expansion-budget=4 -S %s -o - | FileCheck %s
 
 ; When bailing out in rewriteLoopExitValues() you would be left with a PHI node
 ; that was not deleted, and the IndVar pass would return an incorrect modified
 ; status. This was caught by the expensive check introduced in D86589.
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 

 ; CHECK-NEXT:    br i1 [[COND]], label [[END:%.*]], label [[INNER_PREHEADER:%.*]]
 ; CHECK:       inner.preheader:
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[INNER]] ], [ 0, [[INNER_PREHEADER]] ]
 ; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[J_NEXT:%.*]], [[INNER]] ], [ [[N]], [[INNER_PREHEADER]] ]
 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
 ; CHECK-NEXT:    [[J_NEXT]] = add nsw i64 [[J]], 1
-; CHECK-NEXT:    store i64 undef, i64* @ptr, align 8
+; CHECK-NEXT:    store i64 undef, ptr @ptr, align 8
 ; CHECK-NEXT:    [[COND1:%.*]] = icmp slt i64 [[J]], [[IDX]]
 ; CHECK-NEXT:    br i1 [[COND1]], label [[INNER]], label [[INNER_EXIT:%.*]]
 ; CHECK:       inner_exit:
 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ [[I_NEXT]], [[INNER]] ]
 ; CHECK-NEXT:    [[INDVAR_USE:%.*]] = add i64 [[INDVAR]], 1
 ; CHECK-NEXT:    br label [[LATCH]]
 ; CHECK:       latch:
 ; CHECK-NEXT:    [[IDX_NEXT]] = add nsw i64 [[IDX]], -1

llvm/test/Transforms/LoopUnroll/X86/high-cost-expansion.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -mtriple=x86_64-unknown-linux-gnu -passes='loop-unroll' -unroll-runtime -S < %s 2>&1 | FileCheck %s
 
 define void @mask-high(i64 %arg, ptr dereferenceable(4) %arg1) {
 ; CHECK-LABEL: @mask-high(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I:%.*]] = load i32, ptr [[ARG1:%.*]], align 4
 ; CHECK-NEXT:    [[I2:%.*]] = sext i32 [[I]] to i64
 ; CHECK-NEXT:    [[I3:%.*]] = and i64 [[ARG:%.*]], -16
 ; CHECK-NEXT:    [[I4:%.*]] = or i64 1, [[I3]]
 ; CHECK-NEXT:    [[I5:%.*]] = icmp sgt i64 [[I4]], [[I2]]
 ; CHECK-NEXT:    br i1 [[I5]], label [[BB10:%.*]], label [[BB6_PREHEADER:%.*]]
 ; CHECK:       bb6.preheader:
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[I4]], i64 [[I2]])
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i64 [[SMAX]], [[I3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[SMAX]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 [[TMP1]], [[I3]]
+; CHECK-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP0]], 7
+; CHECK-NEXT:    [[LCMP_MOD:%.*]] = icmp ne i64 [[XTRAITER]], 0
+; CHECK-NEXT:    br i1 [[LCMP_MOD]], label [[BB6_PROL_PREHEADER:%.*]], label [[BB6_PROL_LOOPEXIT:%.*]]
+; CHECK:       bb6.prol.preheader:
+; CHECK-NEXT:    br label [[BB6_PROL:%.*]]
+; CHECK:       bb6.prol:
+; CHECK-NEXT:    [[I7_PROL:%.*]] = phi i64 [ [[I8_PROL:%.*]], [[BB6_PROL]] ], [ [[I4]], [[BB6_PROL_PREHEADER]] ]
+; CHECK-NEXT:    [[PROL_ITER:%.*]] = phi i64 [ 0, [[BB6_PROL_PREHEADER]] ], [ [[PROL_ITER_NEXT:%.*]], [[BB6_PROL]] ]
+; CHECK-NEXT:    [[I8_PROL]] = add i64 [[I7_PROL]], 1
+; CHECK-NEXT:    [[I9_PROL:%.*]] = icmp slt i64 [[I7_PROL]], [[I2]]
+; CHECK-NEXT:    [[PROL_ITER_NEXT]] = add i64 [[PROL_ITER]], 1
+; CHECK-NEXT:    [[PROL_ITER_CMP:%.*]] = icmp ne i64 [[PROL_ITER_NEXT]], [[XTRAITER]]
+; CHECK-NEXT:    br i1 [[PROL_ITER_CMP]], label [[BB6_PROL]], label [[BB6_PROL_LOOPEXIT_UNR_LCSSA:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK:       bb6.prol.loopexit.unr-lcssa:
+; CHECK-NEXT:    [[I7_UNR_PH:%.*]] = phi i64 [ [[I8_PROL]], [[BB6_PROL]] ]
+; CHECK-NEXT:    br label [[BB6_PROL_LOOPEXIT]]
+; CHECK:       bb6.prol.loopexit:
+; CHECK-NEXT:    [[I7_UNR:%.*]] = phi i64 [ [[I4]], [[BB6_PREHEADER]] ], [ [[I7_UNR_PH]], [[BB6_PROL_LOOPEXIT_UNR_LCSSA]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP2]], 7
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB10_LOOPEXIT:%.*]], label [[BB6_PREHEADER_NEW:%.*]]
+; CHECK:       bb6.preheader.new:
 ; CHECK-NEXT:    br label [[BB6:%.*]]
 ; CHECK:       bb6:
-; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I8:%.*]], [[BB6]] ], [ [[I4]], [[BB6_PREHEADER]] ]
-; CHECK-NEXT:    [[I8]] = add i64 [[I7]], 1
-; CHECK-NEXT:    [[I9:%.*]] = icmp slt i64 [[I7]], [[I2]]
-; CHECK-NEXT:    br i1 [[I9]], label [[BB6]], label [[BB10_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I7_UNR]], [[BB6_PREHEADER_NEW]] ], [ [[I8_7:%.*]], [[BB6]] ]
+; CHECK-NEXT:    [[I8:%.*]] = add i64 [[I7]], 1
+; CHECK-NEXT:    [[I8_1:%.*]] = add i64 [[I8]], 1
+; CHECK-NEXT:    [[I8_2:%.*]] = add i64 [[I8_1]], 1
+; CHECK-NEXT:    [[I8_3:%.*]] = add i64 [[I8_2]], 1
+; CHECK-NEXT:    [[I8_4:%.*]] = add i64 [[I8_3]], 1
+; CHECK-NEXT:    [[I8_5:%.*]] = add i64 [[I8_4]], 1
+; CHECK-NEXT:    [[I8_6:%.*]] = add i64 [[I8_5]], 1
+; CHECK-NEXT:    [[I8_7]] = add i64 [[I8_6]], 1
+; CHECK-NEXT:    [[I9_7:%.*]] = icmp slt i64 [[I8_6]], [[I2]]
+; CHECK-NEXT:    br i1 [[I9_7]], label [[BB6]], label [[BB10_LOOPEXIT_UNR_LCSSA:%.*]]
+; CHECK:       bb10.loopexit.unr-lcssa:
+; CHECK-NEXT:    br label [[BB10_LOOPEXIT]]
 ; CHECK:       bb10.loopexit:
 ; CHECK-NEXT:    br label [[BB10]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %i = load i32, ptr %arg1, align 4
   %i2 = sext i32 %i to i64

 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I:%.*]] = load i32, ptr [[ARG1:%.*]], align 4
 ; CHECK-NEXT:    [[I2:%.*]] = sext i32 [[I]] to i64
 ; CHECK-NEXT:    [[I3:%.*]] = and i64 [[ARG:%.*]], 16
 ; CHECK-NEXT:    [[I4:%.*]] = add i64 1, [[I3]]
 ; CHECK-NEXT:    [[I5:%.*]] = icmp sgt i64 [[I4]], [[I2]]
 ; CHECK-NEXT:    br i1 [[I5]], label [[BB10:%.*]], label [[BB6_PREHEADER:%.*]]
 ; CHECK:       bb6.preheader:
+; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[I4]], i64 [[I2]])
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i64 [[SMAX]], [[I3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[SMAX]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 [[TMP1]], [[I3]]
+; CHECK-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP0]], 7
+; CHECK-NEXT:    [[LCMP_MOD:%.*]] = icmp ne i64 [[XTRAITER]], 0
+; CHECK-NEXT:    br i1 [[LCMP_MOD]], label [[BB6_PROL_PREHEADER:%.*]], label [[BB6_PROL_LOOPEXIT:%.*]]
+; CHECK:       bb6.prol.preheader:
+; CHECK-NEXT:    br label [[BB6_PROL:%.*]]
+; CHECK:       bb6.prol:
+; CHECK-NEXT:    [[I7_PROL:%.*]] = phi i64 [ [[I8_PROL:%.*]], [[BB6_PROL]] ], [ [[I4]], [[BB6_PROL_PREHEADER]] ]
+; CHECK-NEXT:    [[PROL_ITER:%.*]] = phi i64 [ 0, [[BB6_PROL_PREHEADER]] ], [ [[PROL_ITER_NEXT:%.*]], [[BB6_PROL]] ]
+; CHECK-NEXT:    [[I8_PROL]] = add i64 [[I7_PROL]], 1
+; CHECK-NEXT:    [[I9_PROL:%.*]] = icmp slt i64 [[I7_PROL]], [[I2]]
+; CHECK-NEXT:    [[PROL_ITER_NEXT]] = add i64 [[PROL_ITER]], 1
+; CHECK-NEXT:    [[PROL_ITER_CMP:%.*]] = icmp ne i64 [[PROL_ITER_NEXT]], [[XTRAITER]]
+; CHECK-NEXT:    br i1 [[PROL_ITER_CMP]], label [[BB6_PROL]], label [[BB6_PROL_LOOPEXIT_UNR_LCSSA:%.*]], !llvm.loop [[LOOP2:![0-9]+]]
+; CHECK:       bb6.prol.loopexit.unr-lcssa:
+; CHECK-NEXT:    [[I7_UNR_PH:%.*]] = phi i64 [ [[I8_PROL]], [[BB6_PROL]] ]
+; CHECK-NEXT:    br label [[BB6_PROL_LOOPEXIT]]
+; CHECK:       bb6.prol.loopexit:
+; CHECK-NEXT:    [[I7_UNR:%.*]] = phi i64 [ [[I4]], [[BB6_PREHEADER]] ], [ [[I7_UNR_PH]], [[BB6_PROL_LOOPEXIT_UNR_LCSSA]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP2]], 7
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB10_LOOPEXIT:%.*]], label [[BB6_PREHEADER_NEW:%.*]]
+; CHECK:       bb6.preheader.new:
 ; CHECK-NEXT:    br label [[BB6:%.*]]
 ; CHECK:       bb6:
-; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I8:%.*]], [[BB6]] ], [ [[I4]], [[BB6_PREHEADER]] ]
-; CHECK-NEXT:    [[I8]] = add i64 [[I7]], 1
-; CHECK-NEXT:    [[I9:%.*]] = icmp slt i64 [[I7]], [[I2]]
-; CHECK-NEXT:    br i1 [[I9]], label [[BB6]], label [[BB10_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[I7:%.*]] = phi i64 [ [[I7_UNR]], [[BB6_PREHEADER_NEW]] ], [ [[I8_7:%.*]], [[BB6]] ]
+; CHECK-NEXT:    [[I8:%.*]] = add nuw nsw i64 [[I7]], 1
+; CHECK-NEXT:    [[I8_1:%.*]] = add nuw nsw i64 [[I8]], 1
+; CHECK-NEXT:    [[I8_2:%.*]] = add nuw nsw i64 [[I8_1]], 1
+; CHECK-NEXT:    [[I8_3:%.*]] = add nuw nsw i64 [[I8_2]], 1
+; CHECK-NEXT:    [[I8_4:%.*]] = add nuw nsw i64 [[I8_3]], 1
+; CHECK-NEXT:    [[I8_5:%.*]] = add nuw nsw i64 [[I8_4]], 1
+; CHECK-NEXT:    [[I8_6:%.*]] = add nuw nsw i64 [[I8_5]], 1
+; CHECK-NEXT:    [[I8_7]] = add nuw nsw i64 [[I8_6]], 1
+; CHECK-NEXT:    [[I9_7:%.*]] = icmp slt i64 [[I8_6]], [[I2]]
+; CHECK-NEXT:    br i1 [[I9_7]], label [[BB6]], label [[BB10_LOOPEXIT_UNR_LCSSA:%.*]]
+; CHECK:       bb10.loopexit.unr-lcssa:
+; CHECK-NEXT:    br label [[BB10_LOOPEXIT]]
 ; CHECK:       bb10.loopexit:
 ; CHECK-NEXT:    br label [[BB10]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %i = load i32, ptr %arg1, align 4
   %i2 = sext i32 %i to i64