[VPlan] Model branch cond to enter scalar epilogue in VPlan.

[fhahn]

Summary

This patch moves branch condition creation to enter the scalar epilogue
loop to VPlan. It introduces a new ICmpEQ opcode to VPInstruction and a
new live-out that just updates the branch condition with a given value.
This requires introducing subclassess for VPLiveOut.

For now this is still WIP as the ICmpEQ codegen isn't general yet and
most VPlan printing tests need updating. I'll do that once we converge
on the overall design. Also currently we keep all live-outs in a map
with phi nodes, which doesn't make sense for the new live-out.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3714

(Independent of this patch): builder insertion point should better be used for recipe execution only (and then unset), rather than passing MiddleBlock with it for live-out fixing, which should arguably take care of themselves.

3716

LiveOuts "fix" existing IR Instructions, rather than "execute" - generate new IR Instructions.

3858

(nit: LiveOuts should be a small vector of VPLiveOutPhi's in this case.)

(Independent of this patch): Above should be handled by recipe(s) and below by fixPhi().

8811

While we're here, MiddleVPBB is unused (relates to patch D123537 rather than this patch).

9075

This compare is mandatory (where needed) - should it be introduced as part of building the initial VPlan rather than here as a VPlan2VPlan transformation? In any case, probably better to outline out of the excessive tryToBuildVPlanWithVPRecipes().

9091

This is a first population of MiddleVPBB with recipes, following its introduction in D123457, right?

Presumably, all instructions of MiddleBlock should eventually be generated by VPlan recipes/VPInstructions.

The conditional branch whose condition will be backpatched to Cmp is generated by createVectorLoopSkeleton() as part of the vectorization process, rather than being an original Instruction that can be wrapped with a VPLiveOut - like the LCSSA Phi's of the Exit block.
Could this conditional branch terminating MiddleVPBB be generated as a recipe too (w/o any further live-out users), along with moving the generation of its compare from skeleton to VPlan, rather than fixing it via LiveOutBr? I.e., extend/have a forward BranchOnCond as mentioned when introduced in D126618 to represent loop/backward branches, and similar to BranchOnMask. Following VPlan's approach of rewiring branches when visiting their successors, the two successors of MiddleBlock (Exit block and ScalarPreHeader/VectorEpilogTripCountCheck) could be wrapped in VPBB's, similar to the current wrapping of MiddleVPBB (only) to rewire the vector loop latch branch. These two successors should reuse pre-built IRBB's, similar to MiddleVPBB, which in turn can have VPlan generate its IRBB instead of createVectorLoopSkeleton().

Other skeletal parts, including bypass basic blocks between Preheader and VecPreheader, will also need similar forward out-of-loop conditional branch recipes, when migrated to VPlan.

WDYT?

9092

Note that this accommodates only a single VPLiveOutBr due to insertion with null key into a unique map. Would be good to get rid of that map anyhow.

llvm/lib/Transforms/Vectorize/VPlan.cpp

358

Retain comment?

358

Worth a comment, setting builder to execute recipes at (the end of) "this" MiddleVPBB?

682

(Independent of this patch:) Note that this may be a confusing choice of names: CFG.ExitBB is set to "MiddleBlock", which is the new Exit-from-loop block, as opposed to the original Exit-from-loop-block(s), aka "Exit".

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

169

(Independent of this patch) Better to retrieve
BasicBlock *FromBB = State->CFG.VPBB2IRBB[FromVPBB];
than to rely on State.Builder to be set to MiddleBB,
where the LiveOut is initialized with FromVPBB = MiddleVPBB - conceptually as another operand, VPBB2IRBB[] analogous to State.get().

267

This ICmpEQ is designed to be placed and executed out-of-loop, assert Part is zero?

272

Builder used to indicate insertion block rather than point? Builder.CreateICmpEQ()?

[fhahn]

Address latest comments, thanks!

I reworked the patch to use a BranchOnCond VPInstruction to handle the branch in MiddleVPBB and undid the changes to live-outs. At the moment, this requires updating the branch recipe's operands after the skeleton (and the exit and scalar preheader blocks) have been created. There's FIXMEs to model creation of those blocks in VPlan directly as well.

This should compose nicely with tail-folding as VPlan-to-VPlan transform (D157713); once the transformation has been applied, the conditional branch can be replaced by an unconditional one.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3714

This can be removed after this patch lands (more specifically after the insert point is set in VPBasicBlock::execute), but reorders some extracts, so would be better as a follow-up I think.

3716

(nit: LiveOuts should be a small vector of VPLiveOutPhi's in this case.)

3858

(nit: LiveOuts should be a small vector of VPLiveOutPhi's in this case.)

Code got removed.

8811

Removed in 9ee4a740e326, thanks!

9091

Updated to use BranchOnCond; as BasicBlock is a subclass of Value it is possible to wrap them in live-in VPValues

9092

Code got removed.

llvm/lib/Transforms/Vectorize/VPlan.cpp

358

We need to set the insert point in both cases, sunk outside if.

358

Retained, thanks!

682

Yes, should be updated to MiddleBlock for now? I think once the current patch is in, we could also handle exit block and scalar.ph creation in VPlan, to remove the need to create branches up front.

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

169

Updated here ada2a455fca4 to use the middle VPBB from VPlan for now, as this is what should be used implicitly

267

The modeling here will need future refinement. At the moment all recipes are executed UF times I think. As discussed at a different patch, I am working on patches to allow explicit cloning of recipes to eliminate the implicit dependence on UF.

272

Split off refactoring to use Builder in old skeleton construction to avoid unrelated changes in the diff: the builder will simplify ICmps with constant operands D158332. Should be able to perform this simplification in VPlan directly eventually.

[fhahn]

llvm/test/Transforms/LoopVectorize/AArch64/fixed-order-recurrence.ll

54 ↗

(On Diff #551753)

Note that the final branch is now created later than before, which means the block use list order is slightly different, resulting in different order in the incoming block here (and in many other tests)

[Ayal]

Further thoughts how to best stage this.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3109

nit: LoopMiddleBlock will end with a branch to LoopScalarPreHeader, following how the latter is constructed here, so it's redundant to replace this branch below with BrInst if a scalar epilog is not required.

3124

Can this FIXME be addressed so that VPlan execution will take care of setting the successors of this branch, naturally?

In addition to moving the generation of ICmpEQ from ILV::completeLoopSkeleton() to a VPInstruction introduced in VPlan::createInitialVPlan(), can the generation of LoopMiddleBlock and LoopScalarPreHeader block move from ILV::createVectorLoopSkeleton() to VPlan? Can both be applied as a VPlan transform, perhaps alongside optimizeForVFAndUF() - knowing VF*UF may help determine if it divides TC and thus middle block should jump to exit unconditionally (or have loop latch jump to exit directly). ILV will then detect the middle block and scalar loop pre-header built by VPlan and set its LoopMiddleBlock and LoopScalarPreHeader variables.

7680

A VPBB which is invariantly associated with an existing IRBB should perhaps record this association when created, rather than via State.CFG.PrevBB/ExitBB. This includes the (pre-)pre-header, exit block, and potentially original loop blocks from header to latch. Such VPBB's facilitate hooking VPlan's boundary to existing IR, injecting recipes into existing blocks, reusing original loop for default and/or remainder loops, and as a basis to clone and optimize it. Such VPBB's may contain an "in-place" recipe that represents the existing IR Instructions (w/o generating them/anything during execute()), to model their live-ins and live-outs, and as a placeholder for injecting other recipes before/after. The existence of such a recipe implies that its VPBB is "in-place", so the associated IRBB could be retrieved from it.

8887

Here 2) conceptually includes both "tail is to be folded" and "there is no tail", i.e., when VF*UF is known to divide TC.
Can start with one "canonical" form, for arbitrary VF,UF and un/folded tail, and later revise VPlan when fixing VF,UF and (un)folding tail.

The three cases of (1) jump to scalar preheader, (2) jump to exit, (3) jump to either scalar preheader or exit, are compressed here into a single boolean RequiresScalarEpilogueCheck?

9091

Better take care of branches as recipes along with taking care of their destinations as VPBB's, consistently, even if it's possible to smuggle IRBB destinations as underlying values of live-in VPValues.

llvm/lib/Transforms/Vectorize/VPlan.cpp

302

Could the following logic of hooking up forwards branches when executing their target basic blocks be employed to backpatch the successors of the Middle block's branch targeting the exit block and/or scalar preheader? Or rather the complementary logic in VPBB::execute for IR BB's that are reused (and rewire branches to them there) instead of created here.

489

The term Exiting block typically means the first case only, i.e., a block inside a loop which can exit the loop (to an Exit block). The proposed change effectively checks if this VPBB has no successors?

llvm/lib/Transforms/Vectorize/VPlan.h

1113

nit: try to keep in lex order?

Should the various condition bit Predicates be provided by VPRecipeWithIRFlags as yet another set of flags, having a derived VPInstructions with ICmp and FCmp opcodes?

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

270

nit: ICmpEQ, and ICmpULE above, should name their operands A and B as in BinOp, rather than IV and TC.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3124

Yes I think so, but it will possibly require some extra logic to update the dominator tree. In terms of ordering of changes, I think we would need to first move out the branch to be modeled in VPlan, before moving the block creating itself.

7680

PrevBB is used during execution to figure out if blocks can be re-used (mostly around replicate regions now we have VPlan based merging).

For the others, recording the association explicitly sounds good, but maybe even better to try to replace their uses by moving the logic to VPlan explicitly (e.g how to connect them).

An in-place recipe could also help gradually moving parts of the skeleton into VPlan. IIUC this is mostly a. suggestion for future improvements correct?

8887

This initially tries to just follow the existing logic, but can be broken down further in future patches.

llvm/lib/Transforms/Vectorize/VPlan.cpp

302

Hmm, one issue is that we would need to rely on the IR to figure that out, which means we need to rely on the branch in the middle block implicitly here. The back-patching shouldn't be needed once the successors are also modeled in VPlan (and middle-block is created directly in VPlan). WDYT?

489

I think this check is currently only used to check if the block is supposed to have a conditional terminator, so maybe the function should be renamed to reflect that?

llvm/lib/Transforms/Vectorize/VPlan.h

1113

Yes I have been thinking something along the same lines. It might stretch the IRFlags a bit but should work.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3124

Moving out the branch first, requires a distinct way of hooking up the successors. Moving out the blocks first - even if disconnected at first - as in the pre-pre-header case, could potentially be done initially while keeping the branch creation outside VPlan - as a post-processing, followed by moving out the branch to a recipe - which would be simpler having prepared its successors?

7680

PrevBB is used during execution to figure out if blocks can be re-used (mostly around replicate regions now we have VPlan based merging).

Agreed, and once replicate regions get unrolled as a VPlan-to-VPlan transform, their entry and exit VPBB's should be merged in VPlan as well.

For the others, recording the association explicitly sounds good, but maybe even better to try to replace their uses by moving the logic to VPlan explicitly (e.g how to connect them).

Hmm, intrigued by an even better option - when a VPBB executes it needs to figure out whether to create a new IRBB for its recipes or whether the latter are to populate an existing IRBB?

An in-place recipe could also help gradually moving parts of the skeleton into VPlan. IIUC this is mostly a. suggestion for future improvements correct?

Yes, possibly. Raised here to consider various pieces in order to help converge on an appropriate order of introducing them.

8887

Following existing logic first is fine. Complement the above explanation about the three options with how they relate to the boolean flag below, for now?

llvm/lib/Transforms/Vectorize/VPlan.cpp

302

By backpatching I meant VPlan's existing mechanism of first generating the forward IR branch (before its IR successors are generated/visited) and then revisit the branch to set its destinations once the IR successors are generated/visited. Suggestion is indeed to model the successors in VPlan so that this mechanism could be employed.

489

If this is the desired semantics, naming should indeed reflect it, but BranchOnCond implies a conditional terminator. Question is if a destination goes backwards - in which case it is hooked up when the branch is generated, or goes forwards - in which case it is hooked up when the destination is processed (after processing the branch). Currently BranchOnCond's that have backwards destinations are loop control branches having a backwards destination targeting the header block and a forwards destination targeting the exit/middle block.

682

Or perhaps handle these blocks as VPBB's first, as discussed in other comments here.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::createVectorLoopSkeleton(StringRef Prefix) {
   assert((LoopExitBlock || Cost->requiresScalarEpilogue(VF)) &&
          "multiple exit loop without required epilogue?");
 
   LoopMiddleBlock =
       SplitBlock(LoopVectorPreHeader, LoopVectorPreHeader->getTerminator(), DT,
                  LI, nullptr, Twine(Prefix) + "middle.block");
   LoopScalarPreHeader =
       SplitBlock(LoopMiddleBlock, LoopMiddleBlock->getTerminator(), DT, LI,
                  nullptr, Twine(Prefix) + "scalar.ph");
 
   auto *ScalarLatchTerm = OrigLoop->getLoopLatch()->getTerminator();
 
   // Set up the middle block terminator.  Two cases:
   // 1) If we know that we must execute the scalar epilogue, emit an
   //    unconditional branch.
   // 2) Otherwise, we must have a single unique exit block (due to how we
   //    implement the multiple exit case).  In this case, set up a conditional
   //    branch from the middle block to the loop scalar preheader, and the
   //    exit block.  completeLoopSkeleton will update the condition to use an
   //    iteration check, if required to decide whether to execute the remainder.
   BranchInst *BrInst = Cost->requiresScalarEpilogue(VF) ?
     BranchInst::Create(LoopScalarPreHeader) :
     BranchInst::Create(LoopExitBlock, LoopScalarPreHeader,
                        Builder.getTrue());
   BrInst->setDebugLoc(ScalarLatchTerm->getDebugLoc());
   ReplaceInstWithInst(LoopMiddleBlock->getTerminator(), BrInst);
 
   // Update dominator for loop exit. During skeleton creation, only the vector
   // pre-header and the middle block are created. The vector loop is entirely
   // created during VPlan exection.
   if (!Cost->requiresScalarEpilogue(VF))
     // If there is an epilogue which must run, there's no edge from the
for (const auto &InductionEntry : Legal->getInductionVars()) {
     PHINode *BCResumeVal = createInductionResumeValue(
         OrigPhi, II, getExpandedStep(II, ExpandedSCEVs), LoopBypassBlocks,
         AdditionalBypass);
     OrigPhi->setIncomingValueForBlock(LoopScalarPreHeader, BCResumeVal);
   }
 }
 
 BasicBlock *InnerLoopVectorizer::completeLoopSkeleton() {
-  // The trip counts should be cached by now.
-  Value *Count = getTripCount();
-  Value *VectorTripCount = getOrCreateVectorTripCount(LoopVectorPreHeader);
-
-  auto *ScalarLatchTerm = OrigLoop->getLoopLatch()->getTerminator();
-
-  // Add a check in the middle block to see if we have completed
-  // all of the iterations in the first vector loop.  Three cases:
-  // 1) If we require a scalar epilogue, there is no conditional branch as
-  //    we unconditionally branch to the scalar preheader.  Do nothing.
-  // 2) If (N - N%VF) == N, then we *don't* need to run the remainder.
-  //    Thus if tail is to be folded, we know we don't need to run the
-  //    remainder and we can use the previous value for the condition (true).
-  // 3) Otherwise, construct a runtime check.
-  if (!Cost->requiresScalarEpilogue(VF) && !Cost->foldTailByMasking()) {
-    Instruction *CmpN = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ,
-                                        Count, VectorTripCount, "cmp.n",
-                                        LoopMiddleBlock->getTerminator());
-
-    // Here we use the same DebugLoc as the scalar loop latch terminator instead
-    // of the corresponding compare because they may have ended up with
-    // different line numbers and we want to avoid awkward line stepping while
-    // debugging. Eg. if the compare has got a line number inside the loop.
-    CmpN->setDebugLoc(ScalarLatchTerm->getDebugLoc());
-    cast<BranchInst>(LoopMiddleBlock->getTerminator())->setCondition(CmpN);
-  }
-
 #ifdef EXPENSIVE_CHECKS
   assert(DT->verify(DominatorTree::VerificationLevel::Fast));
 #endif
 
   return LoopVectorPreHeader;
 }
 
 std::pair<BasicBlock *, Value *>
for (const auto &Entry : Legal->getInductionVars())
       fixupIVUsers(Entry.first, Entry.second,
                    getOrCreateVectorTripCount(VectorLoop->getLoopPreheader()),
                    IVEndValues[Entry.first], LoopMiddleBlock,
                    VectorLoop->getHeader(), Plan, State);
   }
 
   // Fix LCSSA phis not already fixed earlier. Extracts may need to be generated
   // in the exit block, so update the builder.
   State.Builder.SetInsertPoint(State.CFG.ExitBB->getFirstNonPHI());
   for (const auto &KV : Plan.getLiveOuts())
-    KV.second->fixPhi(Plan, State);
+    KV.second->execute(Plan, State);
 
   for (Instruction *PI : PredicatedInstructions)
     sinkScalarOperands(&*PI);
 
   // Remove redundant induction instructions.
   cse(VectorLoop->getHeader());
 
   // Set/update profile weights for the vector and remainder loops as original
void InnerLoopVectorizer::fixFixedOrderRecurrence(
 
   auto RecurSplice = cast<VPInstruction>(*PhiR->user_begin());
   assert(PhiR->getNumUsers() == 1 &&
          RecurSplice->getOpcode() ==
              VPInstruction::FirstOrderRecurrenceSplice &&
          "recurrence phi must have a single user: FirstOrderRecurrenceSplice");
   SmallVector<VPLiveOut *> LiveOuts;
   for (VPUser *U : RecurSplice->users())
-    if (auto *LiveOut = dyn_cast<VPLiveOut>(U))
+    if (auto *LiveOut = dyn_cast<VPLiveOutPhi>(U))
       LiveOuts.push_back(LiveOut);
 
   if (!LiveOuts.empty()) {
     // Extract the second last element in the middle block if the
     // Phi is used outside the loop. We need to extract the phi itself
     // and not the last element (the phi update in the current iteration). This
     // will be the value when jumping to the exit block from the
     // LoopMiddleBlock, when the scalar loop is not run at all.
     Value *ExtractForPhiUsedOutsideLoop = nullptr;
     if (VF.isVector()) {
       auto *Idx = Builder.CreateSub(RuntimeVF, ConstantInt::get(IdxTy, 2));
       ExtractForPhiUsedOutsideLoop = Builder.CreateExtractElement(
           Incoming, Idx, "vector.recur.extract.for.phi");
     } else {
       assert(UF > 1 && "VF and UF cannot both be 1");
       // When loop is unrolled without vectorizing, initialize
       // ExtractForPhiUsedOutsideLoop with the value just prior to unrolled
       // value of `Incoming`. This is analogous to the vectorized case above:
       // extracting the second last element when VF > 1.
       ExtractForPhiUsedOutsideLoop = State.get(PreviousDef, UF - 2);
     }
 
     for (VPLiveOut *LiveOut : LiveOuts) {
       assert(!Cost->requiresScalarEpilogue(VF));
-      PHINode *LCSSAPhi = LiveOut->getPhi();
+      PHINode *LCSSAPhi = cast<VPLiveOutPhi>(LiveOut)->getPhi();
       LCSSAPhi->addIncoming(ExtractForPhiUsedOutsideLoop, LoopMiddleBlock);
       State.Plan->removeLiveOut(LCSSAPhi);
     }
   }
 
   // Fix the initial value of the original recurrence in the scalar loop.
   Builder.SetInsertPoint(&*LoopScalarPreHeader->begin());
   PHINode *Phi = cast<PHINode>(PhiR->getUnderlyingValue());
if (!IsEpilogueVectorization)
     VPlanTransforms::optimizeForVFAndUF(BestVPlan, BestVF, BestUF, PSE);
 
   // Perform the actual loop transformation.
   VPTransformState State{BestVF, BestUF, LI, DT, ILV.Builder, &ILV, &BestVPlan};
 
   // 0. Generate SCEV-dependent code into the preheader, including TripCount,
   // before making any changes to the CFG.
   if (!BestVPlan.getPreheader()->empty()) {
     State.CFG.PrevBB = OrigLoop->getLoopPreheader();
     State.Builder.SetInsertPoint(OrigLoop->getLoopPreheader()->getTerminator());
     BestVPlan.getPreheader()->execute(&State);
   }
   if (!ILV.getTripCount())
     ILV.setTripCount(State.get(BestVPlan.getTripCount(), {0, 0}));
   else
     assert(IsEpilogueVectorization && "should only re-use the existing trip "
                                       "count during epilogue vectorization");
VPInstruction *BranchBack = new VPInstruction(
         {CanonicalIVIncrement, &Plan.getVectorTripCount()}, DL);
     EB->appendRecipe(BranchBack);
   }
 }
 
 // Add exit values to \p Plan. VPLiveOuts are added for each LCSSA phi in the
 // original exit block.
 static void addUsersInExitBlock(VPBasicBlock *HeaderVPBB,
                                 VPBasicBlock *MiddleVPBB, Loop *OrigLoop,
                                 VPlan &Plan) {
   BasicBlock *ExitBB = OrigLoop->getUniqueExitBlock();
   BasicBlock *ExitingBB = OrigLoop->getExitingBlock();
   // Only handle single-exit loops with unique exit blocks for now.
   if (!ExitBB || !ExitBB->getSinglePredecessor() || !ExitingBB)
     return;
 
   // Introduce VPUsers modeling the exit values.
   for (PHINode &ExitPhi : ExitBB->phis()) {
     Value *IncomingValue =
         ExitPhi.getIncomingValueForBlock(ExitingBB);
     VPValue *V = Plan.getVPValueOrAddLiveIn(IncomingValue);
-    Plan.addLiveOut(&ExitPhi, V);
+    Plan.addLiveOut(&ExitPhi, new VPLiveOutPhi(&ExitPhi, V));
   }
 }
 
 std::optional<VPlanPtr> LoopVectorizationPlanner::tryToBuildVPlanWithVPRecipes(
     VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions) {
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
 
std::optional<VPlanPtr> LoopVectorizationPlanner::tryToBuildVPlanWithVPRecipes(
   // ---------------------------------------------------------------------------
 
   // Create initial VPlan skeleton, having a basic block for the pre-header
   // which contains SCEV expansions that need to happen before the CFG is
   // modified; a basic block for the vector pre-header, followed by a region for
   // the vector loop, followed by the middle basic block. The skeleton vector
   // loop region contains a header and latch basic blocks.
   VPlanPtr Plan = VPlan::createInitialVPlan(
       createTripCountSCEV(Legal->getWidestInductionType(), PSE, OrigLoop),
       *PSE.getSE());
   VPBasicBlock *HeaderVPBB = new VPBasicBlock("vector.body");
   VPBasicBlock *LatchVPBB = new VPBasicBlock("vector.latch");
   VPBlockUtils::insertBlockAfter(LatchVPBB, HeaderVPBB);
   auto *TopRegion = new VPRegionBlock(HeaderVPBB, LatchVPBB, "vector loop");
   VPBlockUtils::insertBlockAfter(TopRegion, Plan->getEntry());
   VPBasicBlock *MiddleVPBB = new VPBasicBlock("middle.block");
   VPBlockUtils::insertBlockAfter(MiddleVPBB, TopRegion);
std::optional<VPlanPtr> LoopVectorizationPlanner::tryToBuildVPlanWithVPRecipes(
   VPlanTransforms::optimizeInductions(*Plan, *PSE.getSE());
   VPlanTransforms::removeDeadRecipes(*Plan);
 
   VPlanTransforms::createAndOptimizeReplicateRegions(*Plan);
 
   VPlanTransforms::removeRedundantExpandSCEVRecipes(*Plan);
   VPlanTransforms::mergeBlocksIntoPredecessors(*Plan);
 
+  // Add a check in the middle block to see if we have completed
+  // all of the iterations in the first vector loop.  Three cases:
+  // 1) If we require a scalar epilogue, there is no conditional branch as
+  //    we unconditionally branch to the scalar preheader.  Do nothing.
+  // 2) If (N - N%VF) == N, then we *don't* need to run the remainder.
+  //    Thus if tail is to be folded, we know we don't need to run the
+  //    remainder and we can use the previous value for the condition (true).
+  // 3) Otherwise, construct a runtime check.
+  if (LoopVectorizationPlanner::getDecisionAndClampRange(
+          [this](ElementCount VF) { return !CM.requiresScalarEpilogue(VF); },
+          Range) &&
+      !CM.foldTailByMasking()) {
+    auto *VPBB =
+        cast<VPBasicBlock>(Plan->getVectorLoopRegion()->getSingleSuccessor());
+
+    auto *ScalarLatchTerm = OrigLoop->getLoopLatch()->getTerminator();
+    // Here we use the same DebugLoc as the scalar loop latch terminator instead
+    // of the corresponding compare because they may have ended up with
+    // different line numbers and we want to avoid awkward line stepping while
+    // debugging. Eg. if the compare has got a line number inside the loop.
+    auto *Cmp =
+        new VPInstruction(VPInstruction::ICmpEQ,
+                          {Plan->getTripCount(), &Plan->getVectorTripCount()},
+                          ScalarLatchTerm->getDebugLoc());
+    VPBB->appendRecipe(Cmp);
+    Plan->addLiveOut(nullptr, new VPLiveOutBr(Cmp));
+  }
+
   assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");
   return std::make_optional(std::move(Plan));
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // Outer loop handling: They may require CFG and instruction level
   // transformations before even evaluating whether vectorization is profitable.
   // Since we cannot modify the incoming IR, we need to build VPlan upfront in
VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // Remove the existing terminator of the exiting block of the top-most region.
   // A BranchOnCount will be added instead when adding the canonical IV recipes.
   auto *Term =
       Plan->getVectorLoopRegion()->getExitingBasicBlock()->getTerminator();
   Term->eraseFromParent();
 
   addCanonicalIVRecipes(*Plan, Legal->getWidestInductionType(), DebugLoc(),
                         CM.getTailFoldingStyle());
+
+  auto *Cmp =
+      new VPInstruction(VPInstruction::ICmpEQ,
+                        {Plan->getTripCount(), &Plan->getVectorTripCount()});
+  auto *VPBB =
+      cast<VPBasicBlock>(Plan->getVectorLoopRegion()->getSingleSuccessor());
+  VPBB->appendRecipe(Cmp);
+  Plan->addLiveOut(nullptr, new VPLiveOutBr(Cmp));
   return Plan;
 }
 
 // Adjust the recipes for reductions. For in-loop reductions the chain of
 // instructions leading from the loop exit instr to the phi need to be converted
 // to reductions, with one operand being vector and the other being the scalar
 // reduction chain. For other reductions, a select is introduced between the phi
 // and live-out recipes when folding the tail.

llvm/lib/Transforms/Vectorize/VPlan.h

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Indent.
   void printSuccessors(raw_ostream &O, const Twine &Indent) const;
 
   /// Dump this VPBlockBase to dbgs().
   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
 };
 
-/// A value that is used outside the VPlan. The operand of the user needs to be
-/// added to the associated LCSSA phi node.
+/// A value that is used outside the VPlan.
 class VPLiveOut : public VPUser {
-  PHINode *Phi;
+protected:
+  VPLiveOut(VPValue *Op, VPUser::VPUserID ID) : VPUser({Op}, ID) {}
 
 public:
-  VPLiveOut(PHINode *Phi, VPValue *Op)
-      : VPUser({Op}, VPUser::VPUserID::LiveOut), Phi(Phi) {}
+  VPLiveOut(VPValue *Op) : VPLiveOut(Op, VPUser::VPUserID::LiveOut) {}
 
   static inline bool classof(const VPUser *U) {
     return U->getVPUserID() == VPUser::VPUserID::LiveOut;
   }
 
-  /// Fixup the wrapped LCSSA phi node in the unique exit block.  This simply
-  /// means we need to add the appropriate incoming value from the middle
-  /// block as exiting edges from the scalar epilogue loop (if present) are
-  /// already in place, and we exit the vector loop exclusively to the middle
-  /// block.
-  void fixPhi(VPlan &Plan, VPTransformState &State);
+  virtual void execute(VPlan &Plan, VPTransformState &State) = 0;
 
   /// Returns true if the VPLiveOut uses scalars of operand \p Op.
   bool usesScalars(const VPValue *Op) const override {
     assert(is_contained(operands(), Op) &&
            "Op must be an operand of the recipe");
     return true;
   }
 
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  virtual void print(raw_ostream &O, VPSlotTracker &SlotTracker) const = 0;
+#endif
+};
+
+/// A value that is used outside the VPlan. The operand of the user needs to be
+/// added to the associated LCSSA phi node.
+class VPLiveOutPhi : public VPLiveOut {
+  PHINode *Phi;
+
+public:
+  VPLiveOutPhi(PHINode *Phi, VPValue *Op)
+      : VPLiveOut(Op, VPUser::VPUserID::LiveOutPhi), Phi(Phi) {}
+
+  static inline bool classof(const VPUser *U) {
+    return U->getVPUserID() == VPUser::VPUserID::LiveOutPhi;
+  }
+
+  /// Fixup the wrapped LCSSA phi node in the unique exit block.  This simply
+  /// means we need to add the appropriate incoming value from the middle
+  /// block as exiting edges from the scalar epilogue loop (if present) are
+  /// already in place, and we exit the vector loop exclusively to the middle
+  /// block.
+  void execute(VPlan &Plan, VPTransformState &State) override;
+
   PHINode *getPhi() const { return Phi; }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-  /// Print the VPLiveOut to \p O.
+  virtual void print(raw_ostream &O, VPSlotTracker &SlotTracker) const override;
+#endif
+};
+
+struct VPLiveOutBr : public VPLiveOut {
+  VPLiveOutBr(VPValue *Op) : VPLiveOut(Op) {}
+
+  void execute(VPlan &Plan, VPTransformState &State) override;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void print(raw_ostream &O, VPSlotTracker &SlotTracker) const override;
 #endif
 };
 
 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
 /// instructions. VPRecipeBase owns the the VPValues it defines through VPDef
 /// and is responsible for deleting its defined values. Single-value
 /// VPRecipeBases that also inherit from VPValue must make sure to inherit from

 public:
   /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
   enum {
     FirstOrderRecurrenceSplice =
         Instruction::OtherOpsEnd + 1, // Combines the incoming and previous
                                       // values of a first-order recurrence.
     Not,
     ICmpULE,
+    ICmpEQ,
     SLPLoad,
     SLPStore,
     ActiveLaneMask,
     CalculateTripCountMinusVF,
     CanonicalIVIncrement,
     CanonicalIVIncrementNUW,
     // The next two are similar to the above, but instead increment the
     // canonical IV separately for each unrolled part.
void setFlags(Instruction *I) const {
     }
   }
 
   bool isInBounds() const {
     assert(OpType == OperationType::GEPOp &&
            "recipe doesn't have inbounds flag");
     return GEPFlags.IsInBounds;
   }
 };
 
 /// VPWidenRecipe is a recipe for producing a copy of vector type its
 /// ingredient. This recipe covers most of the traditional vectorization cases
 /// where each ingredient transforms into a vectorized version of itself.
 class VPWidenRecipe : public VPRecipeWithIRFlags, public VPValue {
 
 public:
   template <typename IterT>
VPCanonicalIVPHIRecipe *getCanonicalIV() {
     }
     return cast<VPCanonicalIVPHIRecipe>(&*EntryVPBB->begin());
   }
 
   /// Find and return the VPActiveLaneMaskPHIRecipe from the header - there
   /// be only one at most. If there isn't one, then return nullptr.
   VPActiveLaneMaskPHIRecipe *getActiveLaneMaskPhi();
 
-  void addLiveOut(PHINode *PN, VPValue *V);
+  void addLiveOut(PHINode *PN, VPLiveOut *V);
 
   void removeLiveOut(PHINode *PN) {
     delete LiveOuts[PN];
     LiveOuts.erase(PN);
   }
 
   const MapVector<PHINode *, VPLiveOut *> &getLiveOuts() const {
     return LiveOuts;

llvm/lib/Transforms/Vectorize/VPlan.cpp

 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
   // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
   // Pred stands for Predessor. Prev stands for Previous - last visited/created.
   BasicBlock *PrevBB = CFG.PrevBB;
   BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
                                          PrevBB->getParent(), CFG.ExitBB);
   LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
 
   // Hook up the new basic block to its predecessors.
   for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
     VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();
     auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();
     BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
 
     assert(PredBB && "Predecessor basic-block not found building successor.");
     auto *PredBBTerminator = PredBB->getTerminator();
     LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() == this) {
     State->CFG.PrevBB = NewBB;
 
     // Update the branch instruction in the predecessor to branch to ExitBB.
     VPBlockBase *PredVPB = getSingleHierarchicalPredecessor();
     VPBasicBlock *ExitingVPBB = PredVPB->getExitingBasicBlock();
     assert(PredVPB->getSingleSuccessor() == this &&
            "predecessor must have the current block as only successor");
     BasicBlock *ExitingBB = State->CFG.VPBB2IRBB[ExitingVPBB];
-    // The Exit block of a loop is always set to be successor 0 of the Exiting
-    // block.
     cast<BranchInst>(ExitingBB->getTerminator())->setSuccessor(0, NewBB);
+    State->Builder.SetInsertPoint(NewBB->getTerminator());
   } else if (PrevVPBB && /* A */
              !((SingleHPred = getSingleHierarchicalPredecessor()) &&
                SingleHPred->getExitingBasicBlock() == PrevVPBB &&
                PrevVPBB->getSingleHierarchicalSuccessor() &&
                (SingleHPred->getParent() == getEnclosingLoopRegion() &&
                 !IsLoopRegion(SingleHPred))) &&         /* B */
              !(Replica && getPredecessors().empty())) { /* C */
     // The last IR basic block is reused, as an optimization, in three cases:
const VPRecipeBase *VPBasicBlock::getTerminator() const {
   if (hasConditionalTerminator(this))
     return &back();
   return nullptr;
 }
 
 bool VPBasicBlock::isExiting() const {
   return getParent()->getExitingBasicBlock() == this;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
   if (getSuccessors().empty()) {
     O << Indent << "No successors\n";
   } else {
     O << Indent << "Successor(s): ";
     ListSeparator LS;
     for (auto *Succ : getSuccessors())

 /// additional basic-blocks as needed, and fill them all.
 void VPlan::execute(VPTransformState *State) {
   // Set the reverse mapping from VPValues to Values for code generation.
   for (auto &Entry : Value2VPValue)
     State->VPValue2Value[Entry.second] = Entry.first;
 
   // Initialize CFG state.
   State->CFG.PrevVPBB = nullptr;
   State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
   BasicBlock *VectorPreHeader = State->CFG.PrevBB;
   State->Builder.SetInsertPoint(VectorPreHeader->getTerminator());
 
   // Generate code in the loop pre-header and body.
   for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
     Block->execute(State);
 
   VPBasicBlock *LatchVPBB = getVectorLoopRegion()->getExitingBasicBlock();
void VPlan::printDOT(raw_ostream &O) const {
   VPlanPrinter Printer(O, *this);
   Printer.dump();
 }
 
 LLVM_DUMP_METHOD
 void VPlan::dump() const { print(dbgs()); }
 #endif
 
-void VPlan::addLiveOut(PHINode *PN, VPValue *V) {
+void VPlan::addLiveOut(PHINode *PN, VPLiveOut *LiveOut) {
   assert(LiveOuts.count(PN) == 0 && "an exit value for PN already exists");
-  LiveOuts.insert({PN, new VPLiveOut(PN, V)});
+  LiveOuts.insert({PN, LiveOut});
 }
 
 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopHeaderBB,
                                 BasicBlock *LoopLatchBB,
                                 BasicBlock *LoopExitBB) {
   // The vector body may be more than a single basic-block by this point.
   // Update the dominator tree information inside the vector body by propagating
   // it from header to latch, expecting only triangular control-flow, if any.

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

case VPReplicateSC: {
     auto *R = cast<VPReplicateRecipe>(this);
     return R->getUnderlyingInstr()->mayHaveSideEffects();
   }
   default:
     return true;
   }
 }
 
-void VPLiveOut::execute(VPlan &Plan, VPTransformState &State) {
+void VPLiveOutPhi::execute(VPlan &Plan, VPTransformState &State) {
   auto Lane = VPLane::getLastLaneForVF(State.VF);
   VPValue *ExitValue = getOperand(0);
   if (vputils::isUniformAfterVectorization(ExitValue))
     Lane = VPLane::getFirstLane();
   Phi->addIncoming(State.get(ExitValue, VPIteration(State.UF - 1, Lane)),
                    State.Builder.GetInsertBlock());
 }
 
-void VPLiveOut::print(raw_ostream &O, VPSlotTracker &SlotTracker) const {
+void VPLiveOutPhi::print(raw_ostream &O, VPSlotTracker &SlotTracker) const {
   O << "Live-out ";
   getPhi()->printAsOperand(O);
   O << " = ";
   getOperand(0)->printAsOperand(O, SlotTracker);
   O << "\n";
 }
 
+void VPLiveOutBr::execute(VPlan &Plan, VPTransformState &State) {
+  cast<BranchInst>(State.CFG.PrevBB->getTerminator())
+      ->setCondition(State.get(getOperand(0), 0));
+}
+
+void VPLiveOutBr::print(raw_ostream &O, VPSlotTracker &SlotTracker) const {
+  O << "Live-out exit branch ";
+  getOperand(0)->printAsOperand(O, SlotTracker);
+  O << "\n";
+}
+
 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
   assert(!Parent && "Recipe already in some VPBasicBlock");
   assert(InsertPos->getParent() &&
          "Insertion position not in any VPBasicBlock");
   Parent = InsertPos->getParent();
   Parent->getRecipeList().insert(InsertPos->getIterator(), this);
 }
 
void VPInstruction::generateInstruction(VPTransformState &State,
   }
   case VPInstruction::ICmpULE: {
     Value *IV = State.get(getOperand(0), Part);
     Value *TC = State.get(getOperand(1), Part);
     Value *V = Builder.CreateICmpULE(IV, TC, Name);
     State.set(this, V, Part);
     break;
   }
+  case VPInstruction::ICmpEQ: {
+    if (Part != 0)
+      break;
+    Value *IV = State.get(getOperand(0), {Part, 0});
+    Value *TC = State.get(getOperand(1), Part);
+    Instruction *Cmp =
+        CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, IV, TC, "",
+                        &*Builder.GetInsertBlock()->getTerminator());
+    Cmp->setDebugLoc(DL);
+    State.set(this, Cmp, Part);
+    break;
+  }
+
   case Instruction::Select: {
     Value *Cond = State.get(getOperand(0), Part);
     Value *Op1 = State.get(getOperand(1), Part);
     Value *Op2 = State.get(getOperand(2), Part);
     Value *V = Builder.CreateSelect(Cond, Op1, Op2, Name);
     State.set(this, V, Part);
     break;
   }

llvm/lib/Transforms/Vectorize/VPlanValue.h

 /// This class augments VPValue with operands which provide the inverse def-use
 /// edges from VPValue's users to their defs.
 class VPUser {
 public:
   /// Subclass identifier (for isa/dyn_cast).
   enum class VPUserID {
     Recipe,
     LiveOut,
+    LiveOutPhi,
   };
 
 private:
   SmallVector<VPValue *, 2> Operands;
 
   VPUserID ID;
 
 protected:

llvm/test/Transforms/LoopVectorize/pr59319-loop-access-info-invalidation.ll

 ; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ult ptr [[TMP1]], [[SCEVGEP3]]
 ; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
 ; CHECK-NEXT:    br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH5]], label [[VECTOR_PH7:%.*]]
 ; CHECK:       vector.ph7:
 ; CHECK-NEXT:    [[N_MOD_VF8:%.*]] = urem i64 [[TMP3]], 4
 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP3]], [[N_MOD_VF8]]
 ; CHECK-NEXT:    br label [[VECTOR_BODY11:%.*]]
-; CHECK:       vector.body11:
+; CHECK:       vector.body10:
 ; CHECK-NEXT:    [[INDEX12:%.*]] = phi i64 [ 0, [[VECTOR_PH7]] ], [ [[INDEX_NEXT13:%.*]], [[VECTOR_BODY11]] ]
 ; CHECK-NEXT:    store i32 0, ptr [[TMP1]], align 4, !alias.scope !4, !noalias !7
 ; CHECK-NEXT:    [[INDEX_NEXT13]] = add nuw i64 [[INDEX12]], 4
 ; CHECK-NEXT:    [[TMP11:%.*]] = icmp eq i64 [[INDEX_NEXT13]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP11]], label [[MIDDLE_BLOCK4:%.*]], label [[VECTOR_BODY11]], !llvm.loop [[LOOP9:![0-9]+]]
 ; CHECK:       middle.block4:
 ; CHECK-NEXT:    [[CMP_N10:%.*]] = icmp eq i64 [[TMP3]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N10]], label [[LOOP_3_LR_PH:%.*]], label [[SCALAR_PH5]]

 ; CHECK-NEXT:    [[BOUND017:%.*]] = icmp ult ptr [[TMP1]], [[SCEVGEP16]]
 ; CHECK-NEXT:    [[BOUND118:%.*]] = icmp ult ptr [[ARRAYIDX_I_I62]], [[SCEVGEP15]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT19:%.*]] = and i1 [[BOUND017]], [[BOUND118]]
 ; CHECK-NEXT:    br i1 [[FOUND_CONFLICT19]], label [[SCALAR_PH21]], label [[VECTOR_PH23:%.*]]
 ; CHECK:       vector.ph23:
 ; CHECK-NEXT:    [[N_MOD_VF24:%.*]] = urem i64 [[TMP3]], 4
 ; CHECK-NEXT:    [[N_VEC25:%.*]] = sub i64 [[TMP3]], [[N_MOD_VF24]]
 ; CHECK-NEXT:    br label [[VECTOR_BODY28:%.*]]
-; CHECK:       vector.body28:
+; CHECK:       vector.body27:
 ; CHECK-NEXT:    [[INDEX29:%.*]] = phi i64 [ 0, [[VECTOR_PH23]] ], [ [[INDEX_NEXT30:%.*]], [[VECTOR_BODY28]] ]
 ; CHECK-NEXT:    store i32 0, ptr [[TMP1]], align 4, !alias.scope !10, !noalias !13
 ; CHECK-NEXT:    [[INDEX_NEXT30]] = add nuw i64 [[INDEX29]], 4
 ; CHECK-NEXT:    [[TMP14:%.*]] = icmp eq i64 [[INDEX_NEXT30]], [[N_VEC25]]
 ; CHECK-NEXT:    br i1 [[TMP14]], label [[MIDDLE_BLOCK20:%.*]], label [[VECTOR_BODY28]], !llvm.loop [[LOOP15:![0-9]+]]
 ; CHECK:       middle.block20:
 ; CHECK-NEXT:    [[CMP_N27:%.*]] = icmp eq i64 [[TMP3]], [[N_VEC25]]
 ; CHECK-NEXT:    br i1 [[CMP_N27]], label [[LOOP_CLEANUP:%.*]], label [[SCALAR_PH21]]

llvm/test/Transforms/LoopVectorize/vplan-iv-transforms.ll

 ; CHECK-NEXT:     WIDEN store ir<%gep>, ir<%iv>
 ; CHECK-NEXT:     EMIT vp<[[CAN_INC:%.+]]> = VF * UF +(nuw)  vp<[[CAN_IV]]>
 ; CHECK-NEXT:     EMIT branch-on-count  vp<[[CAN_INC]]> vp<[[VEC_TC]]>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 ; CHECK-NEXT: Successor(s): middle.block
 ; CHECK-EMPTY:
 ; CHECK-NEXT: middle.block:
+; CHECK-NEXT:   EMIT vp<[[EC:%.+]]> = icmp eq ir<1000> vp<%0>
 ; CHECK-NEXT: No successors
+; CHECK-EMPTY:
+; CHECK-NEXT: Live-out exit branch vp<[[EC]]>
 ; CHECK-NEXT: }
 ;
 entry:
   br label %loop.header
 
 loop.header:
   %iv = phi i64 [ 0, %entry ], [ %iv.next.p, %loop.latch ]
   %gep = getelementptr inbounds i64, ptr %dst, i64 %iv