[VPlan] Create header & latch blocks for plan skeleton up front (NFC).

[fhahn]

Summary

By creating the header and latch blocks up front and adding blocks and
recipes in between those 2 blocks we ensure that the entry and exits of
the plan remain valid throughout construction.

In order to avoid test changes and keep printing of the plans the same,
we use the new header block instead of creating a new block on the first
iteration of the loop traversing the original loop.

We also fold the latch into its predecessor.

This is a follow up to a post-commit suggestion in D114586.

[fhahn]

Use early_inc_range when moving recipes.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8803

Perhaps something like VPBlockUtils::insertBlockOnEdge() would help take care of ensuring single successor, disconnecting, reconnecting? Admittedly two blocks are being inserted here.

9026

Feed Entry and Exit to constructor of VPRegionBlock instead of setting them explicitly?
Feed Entry to constructor of VPlan instead of setting it explicitly?

9050

Can be simplified into:

if (FillHeaderVPBB)
  FillHeaderVPBB = false;
else {
  auto *FirstVPBBForBB = new VPBasicBlock(BB->getName());
  VPBlockUtils::insertBlockAfter(FirstVPBBForBB, VPBB);
  VPBB = FirstVPBBForBB;
}

?

(Always generating a new VPBB and fusing the empty "dummy" header later, along with fusing latch below, would be reverting D111299?)

llvm/lib/Transforms/Vectorize/VPlan.h

2363

Something early_inc_range could handle?

[fhahn]

Address comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8803

I left it as is for now, because multiple blocks are added and connected here.

9026

Thanks, updated!

9050

Simplified,thanks!

(Always generating a new VPBB and fusing the empty "dummy" header later, along with fusing latch below, would be reverting D111299?)

Perhaps partly reverting it. But in the current patch the header VPBB is actually used, whereas pre-D111299 this 'dummy pre-entry' was not used for anything.

llvm/lib/Transforms/Vectorize/VPlan.h

2363

Unfortunately I don't think early_inc_range will work here, because the successors are managed in a SmallVector, so the early incremented iterator may be invalid after disconnectBlocks removes an entry from the vector. (It *might* work when reversing the iteration order and early increment, but it seems to me that using a SMallVector here is safer for now.

I added a VPBlockBase::successors() helper that returns an iterator range, to avoid the ugly SmallVector construction. This makes some existing use also nicer.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9050

(Always generating a new VPBB and ...

On second thought, header phi recipes should be placed in the header VPBB, which may be awkward if current "VPBB" moved on.
Another alternative is mentioned below, which always generates the next new VPBB.

9115

Another alternative to FillHeaderVPBB above, is to prepare here for the next iteration by doing:

auto *NextVPBB = new VPBasicBlock();
VPBlockUtils::insertBlockAfter(NextVPBB, VPBB);
VPBB = NextVPBB;

The start of each iteration needs to only VPBB->setName(BB->getName()) which also takes care of the header block; after exiting the loop we can get rid of the last empty VPBB, possibly as part of fusing the latch.

9291

Would be good to avoid further bloating this excessive method. Could this folding be outlined, or should it be applied only to selected VPlan prior to code-gen rather than every VPlan upon construction? Doesn't VPBasicBlock::execute() effectively fold Exit into its predecessor if possible?

llvm/lib/Transforms/Vectorize/VPlan.h

2357

Would be good to update above documentation

• condition bit is propagated? to NewBlock?
• disconnects BlockPtr from all its successors and connects it with NewBlock as its successor

2360

Also assert NewBlock has no predecessors, as documented above?

2363

Very well.

2368

While we're here, connectBlocks(BlockPtr, NewBlock); ?

[fhahn]

addressed latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9115

Thanks, updated to use this approach, but with a small extra to avoid generating a redundant empty block in the last iteration.

Alternatively VPBlockUtils::tryToMergeBlockIntoPredecessor could be used, if you prefer.

9291

I added a new helper tryToMergeBlockIntoPredecessor.

. Could this folding be outlined, or should it be applied only to selected VPlan prior to code-gen rather than every VPlan upon construction? Doesn't VPBasicBlock::execute() effectively fold Exit into its predecessor if possible?

The only reason to do this here is to avoid polluting the VPlan printing with additional redundant blocks. We could keep the extra block, but it would require updating all tests that check a printed VPlan and also bloats the plans we need to check in general. WDYT?

llvm/lib/Transforms/Vectorize/VPlan.h

2357

Should be updated, cond bits are now propagated (and removed from BlockPtr ) and moving successors is mentioned.

2360

added, thanks

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9025

Note that setting the name of HeaderVPBB here became redundant. So is setting next.vpbb below.

9115

Perhaps early-exit, combine with the bump, and count backwards:

if (--NumBBsToProcess == 0)
  continue/break;
...

It seemed simpler to avoid the counting and checking by paying for a redundant empty block at the end; it indeed could be cleaned up using tryToMergeBlockIntoPredecessor (thanks for outlining!), although it needs only a disconnect and delete.
Pick whichever version you prefer.

9291

Ah, sure, let's clean up VPlans upon construction then.

llvm/lib/Transforms/Vectorize/VPlan.h

2357

Thanks!
"If \p BlockPtr has more than one successor ..."?

2375

(These condition bits seem to be poorly tested...)

2416

dyn_cast_or_null, or must Block have a single predecessor?

2426

Update Block->getParent()'s Exit if it exists and is equal to Block?

[fhahn]

Address comments and properly transfer successors from folded block.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9025

I removed it for HeaderVPBB both.

9115

updated to just fold the block afterwards.

llvm/lib/Transforms/Vectorize/VPlan.h

2375

yes, they are only used in the native path and it looks like the function is not used on blocks with condbits. Not sure if we can really improve that.

2416

updated to dyn_cast_or_null.

2426

updated, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9282

Should this folding of the latch be done right after folding the empty last VPBB above, or better do so here after dumping Plan.

llvm/lib/Transforms/Vectorize/VPlan.h

2357

Drop "If \p BlockPtr has more than one successor ..."? This method moves all successors of BlockPtr to be successors of NewBlock, also when this involves a single successor.

2418

!PredVPBB->getSingleSuccessor() - suffice to check if PredVPBB->getNumSuccessors() != 1

2424

Either cast (non-dyn) if Block must be in a Region, or check if (ParentRegion && ParentRegion->getExit() == Block)

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9282

I don't think so. I think main motivation is to have the latch/exit block separately so sink-after & other transforms have do not have to explicitly updated the exit block.

llvm/lib/Transforms/Vectorize/VPlan.h

2357

Removed, thanks!

2424

For now, it should be safe to use cast directly, Updated, thanks!

[Ayal]

Patch is ready to go in, with a comment explaining why the empty pre-latch VPBB is merged early and the latch VPBB is merged late.

Suggestions to merge both blocks early, and other comments added inline, may be further discussed in follow-up patch(es) if preferred, or in this one.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9119

Can alternatively do:

VPBlockUtils::insertBlockAfter(new VPBasicBlock(), VPBB);
VPBB = VPBB->getSingleSuccessor();

or have insertBlockAfter() return the block it inserted and have
VPBB = VPBlockUtils::insertBlockAfter(new VPBasicBlock(), VPBB);
(in this or separate patch)

9123

Perhaps tryToMergeBlockIntoPredecessor() should return the predecessor it merged into if successful (null otherwise), to support VPBB = VPBlockUtils::tryToMergeBlockIntoPredecessor(VPBB);

But probably better to avoid updating VPBB at all (tryToMerge already takes care of updating Exit if needed) - see below.

9188

This updating of VPBB is essentially trying to maintain the last BB, i.e., the Latch, i.e., Exit. Would be good to use VPBB only during initial VPlan construction, and refer to Exit instead of VPBB afterwards when seeking the latch.

9200

The use of VPBB here suggests that Exit be used instead, but does it use/rely on a BB preceding the latch?

9282

There are two motivations: (1) set the Exit when its region is created, (2) designate a unique BB for the Exit.
The first provides a stable region, allowing recipes to be placed in the latch during construction if needed, and resolves the issue of when to set Exit; we know a region must have an Exit, may as well have one at the outset.
The second facilitates introducing blocks internal to the loop, between header and latch, requiring only a disconnect and reconnects rather than splitting a block. This is most useful during initial VPlan construction, but seems useless for later transformations - which in general may need to split blocks.

Note that sink-after (splits blocks and) already explicitly updates the "last" BB, see comment above, so may as well have it update the Exit block instead. Would be good to have splitAt() update the enclosing Region's Exit if needed, as well, similar to tryToMergeBlockIntoPredecessor().

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9119

Updated to use the first alternative, thanks!

9123

But probably better to avoid updating VPBB at all (tryToMerge already takes care of updating Exit if needed) - see below.

Sounds good! The only real later use was adjustRecipesForReductions. It expects the latch block, so LatchVPBB can be passed instead. This required a fix to ensure that VPWidenCanonicalIVRecipe is always inserted in the header: 1a54889f48fa

9188

Removed!

9200

adjustRecipesForReductions expects the latch block (the argument is named accordingly), so LatchVPBB can be used directly..

9282

Note that sink-after (splits blocks and) already explicitly updates the "last" BB, see comment above, so may as well have it update the Exit block instead. Would be good to have splitAt() update the enclosing Region's Exit if needed, as well, similar to tryToMergeBlockIntoPredecessor().

Sounds like a good follow-up. I'd prefer to keep the folding late for now, as there is a verifier error when it is folded earlier and I'd prefer to fix that separately.

[Ayal]

Looks good to me!
Would be good to add some (TODO?) comment explaining why Latch is merged with its predecessor late.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9123

Good to have spotted and fixed always inserting VPWidenCanonicalIVRecipe in the header! Posted a couple of post-commit comments there. This fix led to the couple of test changes below reordering ule compares?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

VPBasicBlock *VPRecipeBuilder::handleReplication(
 
   // Finalize the recipe for Instr, first if it is not predicated.
   if (!IsPredicated) {
     LLVM_DEBUG(dbgs() << "LV: Scalarizing:" << *I << "\n");
     VPBB->appendRecipe(Recipe);
     return VPBB;
   }
   LLVM_DEBUG(dbgs() << "LV: Scalarizing and predicating:" << *I << "\n");
-  assert(VPBB->getSuccessors().empty() &&
-         "VPBB has successors when handling predicated replication.");
+
+  VPBlockBase *SingleSucc = VPBB->getSingleSuccessor();
+  assert(SingleSucc && "VPBB must have a single successor when handling "
+                       "predicated replication.");
+  VPBlockUtils::disconnectBlocks(VPBB, SingleSucc);
   // Record predicated instructions for above packing optimizations.
   VPBlockBase *Region = createReplicateRegion(I, Recipe, Plan);
   VPBlockUtils::insertBlockAfter(Region, VPBB);
   auto *RegSucc = new VPBasicBlock();
   VPBlockUtils::insertBlockAfter(RegSucc, Region);
+  VPBlockUtils::connectBlocks(RegSucc, SingleSucc);
   return RegSucc;
 }
 
 VPRegionBlock *VPRecipeBuilder::createReplicateRegion(Instruction *Instr,
                                                       VPRecipeBase *PredRecipe,
                                                       VPlanPtr &Plan) {
   // Instructions marked for predication are replicated and placed under an
   // if-then construct to prevent side-effects.
for (unsigned i = 0; i < IG->getFactor(); i++)
         RecipeBuilder.recordRecipeOf(Member);
   };
 
   // ---------------------------------------------------------------------------
   // Build initial VPlan: Scan the body of the loop in a topological order to
   // visit each basic block after having visited its predecessor basic blocks.
   // ---------------------------------------------------------------------------
 
-  auto Plan = std::make_unique<VPlan>();
+  // Create initial VPlan skeleton, with separate header and latch blocks.
+  VPBasicBlock *HeaderVPBB = new VPBasicBlock(OrigLoop->getHeader()->getName());
+  VPBasicBlock *LatchVPBB = new VPBasicBlock("vector.latch");
+  VPBlockUtils::insertBlockAfter(LatchVPBB, HeaderVPBB);
+  auto *TopRegion = new VPRegionBlock(HeaderVPBB, LatchVPBB, "vector loop");
+  auto Plan = std::make_unique<VPlan>(TopRegion);
 
   // Scan the body of the loop in a topological order to visit each basic block
   // after having visited its predecessor basic blocks.
   LoopBlocksDFS DFS(OrigLoop);
   DFS.perform(LI);
 
-  VPBasicBlock *VPBB = nullptr;
-  VPBasicBlock *HeaderVPBB = nullptr;
+  VPBasicBlock *VPBB = HeaderVPBB;
+  bool FillHeaderVPBB = true;
   SmallVector<VPWidenIntOrFpInductionRecipe *> InductionsToMove;
   for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) {
     // Relevant instructions from basic block BB will be grouped into VPRecipe
     // ingredients and fill a new VPBasicBlock.
     unsigned VPBBsForBB = 0;
+    if (FillHeaderVPBB)
+      FillHeaderVPBB = false;
+    else {
       auto *FirstVPBBForBB = new VPBasicBlock(BB->getName());
-    if (VPBB)
       VPBlockUtils::insertBlockAfter(FirstVPBBForBB, VPBB);
-    else {
-      auto *TopRegion = new VPRegionBlock("vector loop");
-      TopRegion->setEntry(FirstVPBBForBB);
-      Plan->setEntry(TopRegion);
-      HeaderVPBB = FirstVPBBForBB;
-    }
       VPBB = FirstVPBBForBB;
+    }
     Builder.setInsertPoint(VPBB);
 
     // Introduce each ingredient into VPlan.
     // TODO: Model and preserve debug instrinsics in VPlan.
     for (Instruction &I : BB->instructionsWithoutDebug()) {
       Instruction *Instr = &I;
 
       // First filter out irrelevant instructions, to ensure no recipes are
       // built for them.
for (Instruction &I : BB->instructionsWithoutDebug()) {
       // replicated. This may create a successor for VPBB.
       VPBasicBlock *NextVPBB =
           RecipeBuilder.handleReplication(Instr, Range, VPBB, Plan);
       if (NextVPBB != VPBB) {
         VPBB = NextVPBB;
         VPBB->setName(BB->hasName() ? BB->getName() + "." + Twine(VPBBsForBB++)
                                     : "");
       }
     }
   }
 
   assert(isa<VPRegionBlock>(Plan->getEntry()) &&
          !Plan->getEntry()->getEntryBasicBlock()->empty() &&
          "entry block must be set to a VPRegionBlock having a non-empty entry "
          "VPBasicBlock");
   RecipeBuilder.fixHeaderPhis();
 
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 
   // Apply Sink-After legal constraints.
   auto GetReplicateRegion = [](VPRecipeBase *R) -> VPRegionBlock * {
     auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
if (TargetRegion) {
           Target->getParent()->splitAt(std::next(Target->getIterator()));
 
       auto *SplitPred = SplitBlock->getSinglePredecessor();
 
       VPBlockUtils::disconnectBlocks(SplitPred, SplitBlock);
       VPBlockUtils::connectBlocks(SplitPred, SinkRegion);
       VPBlockUtils::connectBlocks(SinkRegion, SplitBlock);
       if (VPBB == SplitPred)
         VPBB = SplitBlock;
     }
   }
 
-  cast<VPRegionBlock>(Plan->getEntry())->setExit(VPBB);
-
   VPlanTransforms::removeRedundantInductionCasts(*Plan);
 
   // Now that sink-after is done, move induction recipes for optimized truncates
   // to the phi section of the header block.
   for (VPWidenIntOrFpInductionRecipe *Ind : InductionsToMove)
     Ind->moveBefore(*HeaderVPBB, HeaderVPBB->getFirstNonPhi());
 
   // Adjust the recipes for any inloop reductions.
   adjustRecipesForReductions(VPBB, Plan, RecipeBuilder, Range.Start);
 
   // Introduce a recipe to combine the incoming and previous values of a
   // first-order recurrence.
   for (VPRecipeBase &R : Plan->getEntry()->getEntryBasicBlock()->phis()) {
     auto *RecurPhi = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R);
     if (!RecurPhi)
       continue;
 
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   for (VF *= 2; ElementCount::isKnownLT(VF, Range.End); VF *= 2) {
     Plan->addVF(VF);
     RSO << "," << VF;
   }
   RSO << "},UF>=1";
   RSO.flush();
   Plan->setName(PlanName);
 
+  // Fold Exit block into its predecessor if possible.
+  auto *LatchPred = dyn_cast<VPBasicBlock>(LatchVPBB->getSinglePredecessor());
+  if (LatchPred) {
+    assert(LatchPred->getSingleSuccessor() == LatchVPBB &&
+           "latch must be executed unconditionally from LatchPred");
+    for (VPRecipeBase &R : make_early_inc_range(*LatchVPBB))
+      R.moveBefore(*LatchPred, LatchPred->end());
+    VPBlockUtils::disconnectBlocks(LatchPred, LatchVPBB);
+    TopRegion->setExit(LatchPred);
+    delete LatchVPBB;
+  }
+
   assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");
   return 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

llvm/lib/Transforms/Vectorize/VPlan.h

 class VPBlockUtils {
 public:
   VPBlockUtils() = delete;
 
   /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
   /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
   /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. If \p BlockPtr
   /// has more than one successor, its conditional bit is propagated to \p
   /// NewBlock. \p NewBlock must have neither successors nor predecessors.
   static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
     assert(NewBlock->getSuccessors().empty() &&
            "Can't insert new block with successors.");
-    // TODO: move successors from BlockPtr to NewBlock when this functionality
-    // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr
-    // already has successors.
+    NewBlock->setParent(BlockPtr->getParent());
+    SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
+    for (VPBlockBase *Succ : Succs) {
+      disconnectBlocks(BlockPtr, Succ);
+      connectBlocks(NewBlock, Succ);
+    }
     BlockPtr->setOneSuccessor(NewBlock);
     NewBlock->setPredecessors({BlockPtr});
-    NewBlock->setParent(BlockPtr->getParent());
   }
 
   /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
   /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
   /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
   /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor
   /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse
   /// must have neither successors nor predecessors.
   static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
                                    VPValue *Condition, VPBlockBase *BlockPtr) {
     assert(IfTrue->getSuccessors().empty() &&
            "Can't insert IfTrue with successors.");
     assert(IfFalse->getSuccessors().empty() &&
            "Can't insert IfFalse with successors.");
     BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition);
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
     To->removePredecessor(From);
   }
 
   /// Returns true if the edge \p FromBlock -> \p ToBlock is a back-edge.
   static bool isBackEdge(const VPBlockBase *FromBlock,
                          const VPBlockBase *ToBlock, const VPLoopInfo *VPLI) {
     assert(FromBlock->getParent() == ToBlock->getParent() &&
            FromBlock->getParent() && "Must be in same region");
     const VPLoop *FromLoop = VPLI->getLoopFor(FromBlock);
     const VPLoop *ToLoop = VPLI->getLoopFor(ToBlock);
     if (!FromLoop || !ToLoop || FromLoop != ToLoop)
       return false;
 
     // A back-edge is a branch from the loop latch to its header.
     return ToLoop->isLoopLatch(FromBlock) && ToBlock == ToLoop->getHeader();
   }
 
   /// Returns true if \p Block is a loop latch
   static bool blockIsLoopLatch(const VPBlockBase *Block,
                                const VPLoopInfo *VPLInfo) {
     if (const VPLoop *ParentVPL = VPLInfo->getLoopFor(Block))
       return ParentVPL->isLoopLatch(Block);
 
     return false;
   }
 
   /// Count and return the number of succesors of \p PredBlock excluding any