[VPlan] Use region for each loop in native path.

[fhahn]

Summary

This patch updates the VPlan native path to use VPRegionBlocks for all
loops in a loop nest. Up to now, only the outermost loop used a region.

This is a step towards unifying both paths and keep things consistent
between them. It also prepares various code-gen parts for modeling the
pre-header in the inner loop vectorizer (D121624).

[fhahn]

Split off removal of unused utilities to D123017.

[fhahn]

Ping :)

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8666–8668

nit: can also remove brackets

llvm/lib/Transforms/Vectorize/VPlan.cpp

275–278

update error message?
Simpler to retain the "if (isa<UnreachableInst>(...)) {" and add an "else if (auto *TermBr = dyn_cast<BranchInst>(...))"?

llvm/lib/Transforms/Vectorize/VPlan.h

41

nit: formatting fix independent of this patch

2666

May as well return to current version(?) doing

if (auto *R = dyn_cast<VPRegionBlock>(getEntry()))
  return R;

2669

ditto

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.cpp

267–268

Comment still intact?

279

remove brackets

279–285

} else if {

287

(unrelated to this patch): assert PredVPSuccessors[idx] == this?

291

worth a comment?
In this case PredVPBB is the exit block of a loop region - PredVPSuccessors.size() is zero?

294

error messages? cast instead of dyn_cast?
assert PredVPSuccessors is empty and PredBBTerminator has no successors?
assert PredVPBB == Reg->getExitBasicBlock()?
Reg>>LoopRegion, as Reg may also refer to Register(?)

307

Worth a comment - why have a(n exit) block with recipes if it's execute is skipped?
This is not instead of the continues in RPOT traversal below, right?

312

"NonReplicateRegion" >> "LoopRegion"?

313

Augment explanation of case B above. The case of SingleHPred being a LoopRegion is clear, what is the other case of SingleHPred residing in same LoopRegion enclosing this VPBB?

Need the extra brackets around

SingleHPred->getParent() == GetEnclosingNonReplicateRegion(this) &&
!IsNonReplicateR(SingleHPred)?

?

319

ditto

949–950

Explanation why if entry is a VPBB (preheader?) then VectorHeaderBB is merged into its predecessor - VectorPreHeader?

950

nit: why is setting CFG.PrevBB moved?

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

76–78

typo: TheLoop

86

\p HeaderBB should be \p LatchBB in order to skip the backedge when it is a predecessor?

279

Why move?
Comment no longer true - Preheader's predecessors no longer set during RPO traversal?

314

Why move?

370

Why added spaces?

389

Backedge was not connected above?

[fhahn]

Rebased and addressed comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8666–8668

Should be fixed!

llvm/lib/Transforms/Vectorize/VPlan.cpp

267–268

This is not relevant any longer, removed!

275–278

Unfortunately the diff was showing changes that were landed as part of a different review. I applied the suggestions in e66127e69bfa. That applies for all suggestions for changes in VPlan.cpp.

279–285

Simplified, thanks!

291

Added a comment, thanks!

294

Renamed and added extra assertions, thanks!

307

After re-ordering the patches, this is not needed any longer (originally this patch was placed before introducing any recipes in the exit)

312

This has been simplified in the latest version, now there's just a single IsLoopRegion helper.

313

Should be updated in the latest version

949–950

This is also gone in the latest version.

950

Not moved in the latest version.

llvm/lib/Transforms/Vectorize/VPlan.h

41

Should be fixed, thanks!

2666

This now just does cast<VPRegionBlock>(getEntry()->getSingleSuccessor())

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

76–78

I *think* this should be fixed.

86

HeaderBB/LatchBB is gone in the latest version.

279

Why move?

The move was accidental, but the comment is not longer true because the predecessor doesn't have any predecessors.

314

Undone.

370

Should be removed.

389

In the latest version, the backedge is connect earlier and removed here.

[fhahn]

Ping :) I think all outstanding comments should have been addressed

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

90

Is this change needed?

110–113

Also comment that if \p BB belongs to a loop (except for preheader - said loop needs to be in the scope of VPlan?), then the new empty VPBB is placed in a corresponding VPRegion - if exists otherwise in a new one.

120

Deserves a separate getOrCreate[EnclosingLoop]Region()?

135

Would be good to add a test with nested loops showing how multiple regions are now being created, whereas until now only the outermost loop was region'd.

267

PreheaderVPBB >> VPlanPreheaderVPBB, to emphasize it's VPlan's outer/entry VPBB, to be returned at the end?

275

Is this change needed?

Move the comment about setting Preheader's predecessors along with setOneSuccessor? BTW, comment probably meant to refer to setting the predecessor(s) of Preheader's successor, as Preheader surely has no predecessors set, moreover during RPO traversal below.

323

3. >> 2. ?

325

createVPInstructionsForVPBB() is removed because exit BB should not be populated; is the current population simply redundant, and can be removed independent of this patch? Should LoopExitVPBB, not being part of the (the) loop, be replaced by LiveOut VPUsers (surely independent of this patch)?

369

4. >> 3. ?

385

HeaderPred >> PreheaderVPBB?

387

Unrelated to this patch: setName under LLVM_DEBUG?

389

getVectorLoopRegion()?

395

LatchSucc >> ExitVPBB? Where LatchVPBB == ExitingVPBB.

403

5. >> 4.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

27–30

Simply

ReversePostOrderTraversal<VPBlockBase *> RPOT(Plan->getEntry());

would do, or is the Wrapper needed for blocksOnly()?
Until now it works w/o the blocksOnly<VPBasicBlock>(), because TopRegion is skipped, and there were no other regions.

So now we do widen instructions in pre-header and (empty) exit/middle blocks having zero predecessors and successors respectively, right?

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

53

(To be renamed ExitingBasicBlock, which has no successors but a CondBit to denote when to exit the loop...)

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

49–51

Can explain:

// Check that the region following the preheader is a single basic-block region (loop).

178–180

ditto, outline to a common function checking for a single basic-block region (loop)?

[fhahn]

Address latest comments, thanks!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

90

Nope, removed the stray change, thanks!

110–113

Extended the comment, thanks!

120

Given that is is just used here I'm not sure if it is worth pulling this out. Could be a lambda if you think early exits would help readability?

135

Good point, looks like we are missing a VPlan printing ttest for outer loop vectorization. Added in b7d2b160c3ba

267

Done, thanks!

275

Is this change needed?

It's not needed in the latest version of the patch, changed removed, thanks!

Move the comment about setting Preheader's predecessors along with setOneSuccessor? BTW, comment probably meant to refer to setting the predecessor(s) of Preheader's successor, as Preheader surely has no predecessors set, moreover during RPO traversal below.

Yeah, I'll remove the commit.

323

Numbering updated, thanks!

369

Numbering updated, thanks!

385

Fixed, thanks!

387

Will do separately.

389

updated, thanks!

395

Done! Also Updated LatchVPBB -> ExitingVPBB, with an assertion that getLoopLatch() == getExitingBlock()

403

Numbering fixed, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

27–30

Simply
ReversePostOrderTraversal<VPBlockBase *> RPOT(Plan->getEntry());

Yes, updated, thanks!

So now we do widen instructions in pre-header and (empty) exit/middle blocks having zero predecessors and successors respectively, right?

They will be empty at the moment so nothing happens at the moment.

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

53

Updated!

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

49–51

Added, thanks!

178–180

Added, thanks!

[fhahn]

Remove some more dead code (VPBBsToFix is not needed any longer).

[Ayal]

This looks good to me, ship it!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

120

Added comment suffices to help readability, thanks!

267

nit: could alternatively use the "The" prefix to denote elements of the topmost/outer loop/region, following TheLoop: ThePreheaderBB, ThePreheaderVPBB, ...

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

static void addCanonicalIVRecipes(VPlan &Plan, Type *IdxTy, DebugLoc DL,
   VPBasicBlock *Header = TopRegion->getEntryBasicBlock();
   Header->insert(CanonicalIVPHI, Header->begin());
 
   auto *CanonicalIVIncrement =
       new VPInstruction(HasNUW ? VPInstruction::CanonicalIVIncrementNUW
                                : VPInstruction::CanonicalIVIncrement,
                         {CanonicalIVPHI}, DL);
   CanonicalIVPHI->addOperand(CanonicalIVIncrement);
 
   VPBasicBlock *EB = TopRegion->getExitingBasicBlock();
   if (IsVPlanNative)
     EB->setCondBit(nullptr);
   EB->appendRecipe(CanonicalIVIncrement);
 
   auto *BranchOnCount =
       new VPInstruction(VPInstruction::BranchOnCount,
                         {CanonicalIVIncrement, &Plan.getVectorTripCount()}, DL);
   EB->appendRecipe(BranchOnCount);
 }
for (ElementCount VF = Range.Start; ElementCount::isKnownLT(VF, Range.End);
     Plan->addVF(VF);
 
   SmallPtrSet<Instruction *, 1> DeadInstructions;
   VPlanTransforms::VPInstructionsToVPRecipes(
       OrigLoop, Plan,
       [this](PHINode *P) { return Legal->getIntOrFpInductionDescriptor(P); },
       DeadInstructions, *PSE.getSE());
 
-  // Update plan to be compatible with the inner loop vectorizer for
-  // code-generation.
-  VPRegionBlock *LoopRegion = Plan->getVectorLoopRegion();
-  VPBasicBlock *Preheader = LoopRegion->getEntryBasicBlock();
-  VPBasicBlock *Exiting = LoopRegion->getExitingBasicBlock();
-  VPBlockBase *Latch = Exiting->getSinglePredecessor();
-  VPBlockBase *Header = Preheader->getSingleSuccessor();
-
-  // 1. Move preheader block out of main vector loop.
-  Preheader->setParent(LoopRegion->getParent());
-  VPBlockUtils::disconnectBlocks(Preheader, Header);
-  VPBlockUtils::connectBlocks(Preheader, LoopRegion);
-  Plan->setEntry(Preheader);
-
-  // 2. Disconnect backedge and exiting block.
-  VPBlockUtils::disconnectBlocks(Latch, Header);
-  VPBlockUtils::disconnectBlocks(Latch, Exiting);
-
-  // 3. Update entry and exiting of main vector loop region.
-  LoopRegion->setEntry(Header);
-  LoopRegion->setExiting(Latch);
-
-  // 4. Remove exiting block.
-  delete Exiting;
-
   addCanonicalIVRecipes(*Plan, Legal->getWidestInductionType(), DebugLoc(),
                         true, true);
   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

llvm/lib/Transforms/Vectorize/VPlan.h

 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/FMF.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <string>
 
 namespace llvm {
#endif
   /// Returns true if \p VPV is uniform after vectorization.
   bool isUniformAfterVectorization(VPValue *VPV) const {
     auto RepR = dyn_cast_or_null<VPReplicateRecipe>(VPV->getDef());
     return !VPV->getDef() || (RepR && RepR->isUniform());
   }
 
   /// Returns the VPRegionBlock of the vector loop.
   VPRegionBlock *getVectorLoopRegion() {
-    if (auto *R = dyn_cast<VPRegionBlock>(getEntry()))
-      return R;
     return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
   }
   const VPRegionBlock *getVectorLoopRegion() const {
-    if (auto *R = dyn_cast<VPRegionBlock>(getEntry()))
-      return R;
     return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
   }
 
   /// Returns the canonical induction recipe of the vector loop.
   VPCanonicalIVPHIRecipe *getCanonicalIV() {
     VPBasicBlock *EntryVPBB = getVectorLoopRegion()->getEntryBasicBlock();
     if (EntryVPBB->empty()) {
       // VPlan native path.
       EntryVPBB = cast<VPBasicBlock>(EntryVPBB->getSingleSuccessor());
     }

llvm/lib/Transforms/Vectorize/VPlan.cpp

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->getSuccessors();
     BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
 
-    // In outer loop vectorization scenario, the predecessor BBlock may not yet
-    // be visited(backedge). Mark the VPBasicBlock for fixup at the end of
-    // vectorization. We do not encounter this case in inner loop vectorization
-    // as we start out by building a loop skeleton with the vector loop header
-    // and latch blocks. As a result, we never enter this function for the
-    // header block in the non VPlan-native path.
-    if (!PredBB) {
-      assert(EnableVPlanNativePath &&
-             "Unexpected null predecessor in non VPlan-native path");
-      CFG.VPBBsToFix.push_back(PredVPBB);
-      continue;
-    }
-
     assert(PredBB && "Predecessor basic-block not found building successor.");
     auto *PredBBTerminator = PredBB->getTerminator();
     LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
 
     auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
     if (isa<UnreachableInst>(PredBBTerminator)) {
       assert(PredVPSuccessors.size() == 1 &&
              "Predecessor ending w/o branch must have single successor.");
       DebugLoc DL = PredBBTerminator->getDebugLoc();
       PredBBTerminator->eraseFromParent();
       auto *Br = BranchInst::Create(NewBB, PredBB);
       Br->setDebugLoc(DL);
     } else if (TermBr && !TermBr->isConditional()) {
       TermBr->setSuccessor(0, NewBB);
     } else if (PredVPSuccessors.size() == 2) {
       unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
       assert(!PredBBTerminator->getSuccessor(idx) &&
              "Trying to reset an existing successor block.");
       PredBBTerminator->setSuccessor(idx, NewBB);
     } else {
       // PredVPBB is the exiting block of a loop region. Connect its successor
       // outside the region.
       auto *LoopRegion = cast<VPRegionBlock>(PredVPBB->getParent());
       assert(!LoopRegion->isReplicator() &&
              "predecessor must be in a loop region");
       assert(PredVPSuccessors.empty() &&
              LoopRegion->getExitingBasicBlock() == PredVPBB &&
              "PredVPBB must be the exiting block of its parent region");
       assert(this == LoopRegion->getSingleSuccessor() &&
              "the current block must be the single successor of the region");
       PredBBTerminator->setSuccessor(0, NewBB);
       PredBBTerminator->setSuccessor(
           1, CFG.VPBB2IRBB[LoopRegion->getEntryBasicBlock()]);
     }
   }
   return NewBB;
 }
 
 void VPBasicBlock::execute(VPTransformState *State) {
   bool Replica = State->Instance && !State->Instance->isFirstIteration();
   VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
   VPBlockBase *SingleHPred = nullptr;
   BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
 
   auto IsLoopRegion = [](VPBlockBase *BB) {
     auto *R = dyn_cast<VPRegionBlock>(BB);
     return R && !R->isReplicator();
   };
 
   // 1. Create an IR basic block, or reuse the last one or ExitBB if possible.
   if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() == this) {
     // ExitBB can be re-used for the exit block of the Plan.
     NewBB = State->CFG.ExitBB;
     State->CFG.PrevBB = NewBB;
   } else if (PrevVPBB && /* A */
              !((SingleHPred = getSingleHierarchicalPredecessor()) &&
                SingleHPred->getExitingBasicBlock() == PrevVPBB &&
                PrevVPBB->getSingleHierarchicalSuccessor() &&
                (SingleHPred->getParent() == getEnclosingLoopRegion() &&
                 !IsLoopRegion(SingleHPred))) &&         /* B */

 /// Assumes a single pre-header basic-block was created for this. Introduce
 /// 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 : depth_first(Entry))
     Block->execute(State);
 
   // Setup branch terminator successors for VPBBs in VPBBsToFix based on

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h

private:
   // VPlan verifier utility.
   VPlanVerifier Verifier;
 
   // Dominator analysis for VPlan plain CFG to be used in the
   // construction of the H-CFG. This analysis is no longer valid once regions
   // are introduced.
   VPDominatorTree VPDomTree;
 
-  /// Build plain CFG for TheLoop. Return a new VPRegionBlock (TopRegion)
-  /// enclosing the plain CFG.
-  VPRegionBlock *buildPlainCFG();
+  /// Build plain CFG for TheLoop. Return the pre-header VPBasicBlock connected
+  /// to a new VPRegionBlock (TopRegion) enclosing the plain CFG.
+  VPBasicBlock *buildPlainCFG();
 
 public:
   VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
       : TheLoop(Lp), LI(LI), Plan(P) {}
 
   /// Build H-CFG for TheLoop and update Plan accordingly.
   void buildHierarchicalCFG();
 };
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VPLANHCFGBUILDER_H

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

private:
   Loop *TheLoop;
 
   // Loop Info analysis.
   LoopInfo *LI;
 
   // Vectorization plan that we are working on.
   VPlan &Plan;
 
-  // Output Top Region.
-  VPRegionBlock *TopRegion = nullptr;
-
   // Builder of the VPlan instruction-level representation.
   VPBuilder VPIRBuilder;
 
   // NOTE: The following maps are intentionally destroyed after the plain CFG
   // construction because subsequent VPlan-to-VPlan transformation may
   // invalidate them.
   // Map incoming BasicBlocks to their newly-created VPBasicBlocks.
   DenseMap<BasicBlock *, VPBasicBlock *> BB2VPBB;
   // Map incoming Value definitions to their newly-created VPValues.
   DenseMap<Value *, VPValue *> IRDef2VPValue;
 
   // Hold phi node's that need to be fixed once the plain CFG has been built.
   SmallVector<PHINode *, 8> PhisToFix;
 
+  /// Maps loops in the original IR to their corresponding region.
+  DenseMap<Loop *, VPRegionBlock *> Loop2Region;
+
   // Utility functions.
   void setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB);
   void fixPhiNodes();
   VPBasicBlock *getOrCreateVPBB(BasicBlock *BB);
 #ifndef NDEBUG
   bool isExternalDef(Value *Val);
 #endif
   VPValue *getOrCreateVPOperand(Value *IRVal);
   void createVPInstructionsForVPBB(VPBasicBlock *VPBB, BasicBlock *BB);
 
 public:
   PlainCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
       : TheLoop(Lp), LI(LI), Plan(P) {}
 
-  // Build the plain CFG and return its Top Region.
-  VPRegionBlock *buildPlainCFG();
+  /// Build plain CFG for TheLoop. Return the pre-header VPBasicBlock connected
+  /// to a new VPRegionBlock (TopRegion) enclosing the plain CFG.
+  VPBasicBlock *buildPlainCFG();
 };
 } // anonymous namespace
 
 // Set predecessors of \p VPBB in the same order as they are in \p BB. \p VPBB
 // must have no predecessors.
 void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB) {
   SmallVector<VPBlockBase *, 8> VPBBPreds;
   // Collect VPBB predecessors.
   for (BasicBlock *Pred : predecessors(BB))
     VPBBPreds.push_back(getOrCreateVPBB(Pred));
 
   VPBB->setPredecessors(VPBBPreds);
 }
 
 // Add operands to VPInstructions representing phi nodes from the input IR.
 void PlainCFGBuilder::fixPhiNodes() {
   for (auto *Phi : PhisToFix) {
     assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
     VPValue *VPVal = IRDef2VPValue[Phi];
     assert(isa<VPWidenPHIRecipe>(VPVal) &&
            "Expected WidenPHIRecipe for phi node.");
     auto *VPPhi = cast<VPWidenPHIRecipe>(VPVal);
     assert(VPPhi->getNumOperands() == 0 &&
            "Expected VPInstruction with no operands.");
 
     for (unsigned I = 0; I != Phi->getNumOperands(); ++I)
       VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValue(I)),
                          BB2VPBB[Phi->getIncomingBlock(I)]);
   }
 }
 
-// Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an
-// existing one if it was already created.
+// Create a new empty VPBasicBlock for an incoming BasicBlock in the region
+// corresponding to the containing loop  or retrieve an existing one if it was
+// already created. If no region exists yet for the loop containing \p BB, a new
+// one is created.
 VPBasicBlock *PlainCFGBuilder::getOrCreateVPBB(BasicBlock *BB) {
   auto BlockIt = BB2VPBB.find(BB);
   if (BlockIt != BB2VPBB.end())
     // Retrieve existing VPBB.
     return BlockIt->second;
 
+  // Get or create a region for the loop containing BB.
+  Loop *CurrentLoop = LI->getLoopFor(BB);
+  VPRegionBlock *ParentR = nullptr;
+  if (CurrentLoop) {
+    auto Iter = Loop2Region.insert({CurrentLoop, nullptr});
+    if (Iter.second)
+      Iter.first->second = new VPRegionBlock(
+          CurrentLoop->getHeader()->getName().str(), false /*isReplicator*/);
+    ParentR = Iter.first->second;
+  }
+
   // Create new VPBB.
   LLVM_DEBUG(dbgs() << "Creating VPBasicBlock for " << BB->getName() << "\n");
   VPBasicBlock *VPBB = new VPBasicBlock(BB->getName());
   BB2VPBB[BB] = VPBB;
-  VPBB->setParent(TopRegion);
+  VPBB->setParent(ParentR);
   return VPBB;
 }
 
 #ifndef NDEBUG
 // Return true if \p Val is considered an external definition. An external
 // definition is either:
 // 1. A Value that is not an Instruction. This will be refined in the future.
 // 2. An Instruction that is outside of the CFG snippet represented in VPlan,
if (auto *Phi = dyn_cast<PHINode>(Inst)) {
           VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));
     }
 
     IRDef2VPValue[Inst] = NewVPV;
   }
 }
 
 // Main interface to build the plain CFG.
-VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
-  // 1. Create the Top Region. It will be the parent of all VPBBs.
-  TopRegion = new VPRegionBlock("TopRegion", false /*isReplicator*/);
-
-  // 2. Scan the body of the loop in a topological order to visit each basic
+VPBasicBlock *PlainCFGBuilder::buildPlainCFG() {
+  // 1. Scan the body of the loop in a topological order to visit each basic
   // block after having visited its predecessor basic blocks. Create a VPBB for
   // each BB and link it to its successor and predecessor VPBBs. Note that
   // predecessors must be set in the same order as they are in the incomming IR.
   // Otherwise, there might be problems with existing phi nodes and algorithm
   // based on predecessors traversal.
 
   // Loop PH needs to be explicitly visited since it's not taken into account by
   // LoopBlocksDFS.
   BasicBlock *PreheaderBB = TheLoop->getLoopPreheader();
   assert((PreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
          "Unexpected loop preheader");
-  VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(PreheaderBB);
+  VPBasicBlock *VPlanPreheaderVPBB = getOrCreateVPBB(PreheaderBB);
   for (auto &I : *PreheaderBB) {
     if (I.getType()->isVoidTy())
       continue;
     IRDef2VPValue[&I] = Plan.getOrAddExternalDef(&I);
   }
   // Create empty VPBB for Loop H so that we can link PH->H.
   VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
   HeaderVPBB->setName("vector.body");
-  // Preheader's predecessors will be set during the loop RPO traversal below.
-  PreheaderVPBB->setOneSuccessor(HeaderVPBB);
+  VPlanPreheaderVPBB->setOneSuccessor(HeaderVPBB);
 
   LoopBlocksRPO RPO(TheLoop);
   RPO.perform(LI);
 
   for (BasicBlock *BB : RPO) {
     // Create or retrieve the VPBasicBlock for this BB and create its
     // VPInstructions.
     VPBasicBlock *VPBB = getOrCreateVPBB(BB);
     createVPInstructionsForVPBB(VPBB, BB);
 
     // Set VPBB successors. We create empty VPBBs for successors if they don't
if (NumSuccs == 1) {
       auto *Br = cast<BranchInst>(TI);
       Value *BrCond = Br->getCondition();
       // Look up the branch condition to get the corresponding VPValue
       // representing the condition bit in VPlan (which may be in another VPBB).
       assert(IRDef2VPValue.count(BrCond) &&
              "Missing condition bit in IRDef2VPValue!");
       VPValue *VPCondBit = IRDef2VPValue[BrCond];
 
       // Link successors using condition bit.
       VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1, VPCondBit);
     } else
       llvm_unreachable("Number of successors not supported.");
 
     // Set VPBB predecessors in the same order as they are in the incoming BB.
     setVPBBPredsFromBB(VPBB, BB);
   }
 
-  // 3. Process outermost loop exit. We created an empty VPBB for the loop
+  // 2. Process outermost loop exit. We created an empty VPBB for the loop
   // single exit BB during the RPO traversal of the loop body but Instructions
   // weren't visited because it's not part of the the loop.
   BasicBlock *LoopExitBB = TheLoop->getUniqueExitBlock();
   assert(LoopExitBB && "Loops with multiple exits are not supported.");
   VPBasicBlock *LoopExitVPBB = BB2VPBB[LoopExitBB];
-  createVPInstructionsForVPBB(LoopExitVPBB, LoopExitBB);
   // Loop exit was already set as successor of the loop exiting BB.
   // We only set its predecessor VPBB now.
   setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB);
 
+  // 3. Fix up region blocks for loops. For each loop,
+  //   * use the header block as entry to the corresponding region,
+  //   * use the latch block as exit of the corresponding region,
+  //   * set the region as successor of the loop pre-header, and
+  //   * set the exit block as successor to the region.
+  SmallVector<Loop *> LoopWorkList;
+  LoopWorkList.push_back(TheLoop);
+  while (!LoopWorkList.empty()) {
+    Loop *L = LoopWorkList.pop_back_val();
+    BasicBlock *Header = L->getHeader();
+    BasicBlock *Exiting = L->getLoopLatch();
+    assert(Exiting == L->getExitingBlock() &&
+           "Latch must be the only exiting block");
+    VPRegionBlock *Region = Loop2Region[L];
+    VPBasicBlock *HeaderVPBB = getOrCreateVPBB(Header);
+    VPBasicBlock *ExitingVPBB = getOrCreateVPBB(Exiting);
+
+    // Disconnect backedge and pre-header from header.
+    VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(L->getLoopPreheader());
+    VPBlockUtils::disconnectBlocks(PreheaderVPBB, HeaderVPBB);
+    VPBlockUtils::disconnectBlocks(ExitingVPBB, HeaderVPBB);
+
+    Region->setParent(PreheaderVPBB->getParent());
+    Region->setEntry(HeaderVPBB);
+    VPBlockUtils::connectBlocks(PreheaderVPBB, Region);
+
+    // Disconnect exit block from exiting (=latch) block, set exiting block and
+    // connect region to exit block.
+    VPBasicBlock *ExitVPBB = getOrCreateVPBB(L->getExitBlock());
+    VPBlockUtils::disconnectBlocks(ExitingVPBB, ExitVPBB);
+    Region->setExiting(ExitingVPBB);
+    VPBlockUtils::connectBlocks(Region, ExitVPBB);
+
+    // Queue sub-loops for processing.
+    LoopWorkList.append(L->begin(), L->end());
+  }
   // 4. The whole CFG has been built at this point so all the input Values must
   // have a VPlan couterpart. Fix VPlan phi nodes by adding their corresponding
   // VPlan operands.
   fixPhiNodes();
 
-  // 5. Final Top Region setup. Set outermost loop pre-header and single exit as
-  // Top Region entry and exit.
-  TopRegion->setEntry(PreheaderVPBB);
-  TopRegion->setExiting(LoopExitVPBB);
-  return TopRegion;
+  return VPlanPreheaderVPBB;
 }
 
-VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() {
+VPBasicBlock *VPlanHCFGBuilder::buildPlainCFG() {
   PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
   return PCFGBuilder.buildPlainCFG();
 }
 
 // Public interface to build a H-CFG.
 void VPlanHCFGBuilder::buildHierarchicalCFG() {
   // Build Top Region enclosing the plain CFG and set it as VPlan entry.
-  VPRegionBlock *TopRegion = buildPlainCFG();
-  Plan.setEntry(TopRegion);
+  VPBasicBlock *EntryVPBB = buildPlainCFG();
+  Plan.setEntry(EntryVPBB);
   LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
 
+  VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
   Verifier.verifyHierarchicalCFG(TopRegion);
 
   // Compute plain CFG dom tree for VPLInfo.
   VPDomTree.recalculate(*TopRegion);
   LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
              VPDomTree.print(dbgs()));
 }

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

 using namespace llvm;
 
 void VPlanTransforms::VPInstructionsToVPRecipes(
     Loop *OrigLoop, VPlanPtr &Plan,
     function_ref<const InductionDescriptor *(PHINode *)>
         GetIntOrFpInductionDescriptor,
     SmallPtrSetImpl<Instruction *> &DeadInstructions, ScalarEvolution &SE) {
 
-  auto *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
-  ReversePostOrderTraversal<VPBlockBase *> RPOT(TopRegion->getEntry());
-
-  for (VPBlockBase *Base : RPOT) {
-    // Do not widen instructions in pre-header and exit blocks.
-    if (Base->getNumPredecessors() == 0 || Base->getNumSuccessors() == 0)
-      continue;
-
-    VPBasicBlock *VPBB = Base->getEntryBasicBlock();
+  ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>>
+      RPOT(Plan->getEntry());
+  for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
     // Introduce each ingredient into VPlan.
     for (VPRecipeBase &Ingredient : llvm::make_early_inc_range(*VPBB)) {
       VPValue *VPV = Ingredient.getVPSingleValue();
       Instruction *Inst = cast<Instruction>(VPV->getUnderlyingValue());
       if (DeadInstructions.count(Inst)) {
         VPValue DummyValue;
         VPV->replaceAllUsesWith(&DummyValue);
         Ingredient.eraseFromParent();
         continue;

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
   for (const VPBlockBase *VPB : make_range(
            df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
            df_iterator<const VPBlockBase *>::end(Region->getExiting()))) {
     // Check block's parent.
     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
 
     // Check block's condition bit.
-    if (VPB->getNumSuccessors() > 1)
+    if (VPB->getNumSuccessors() > 1 || Region->getExitingBasicBlock() == VPB)
       assert(VPB->getCondBit() && "Missing condition bit!");
     else
       assert(!VPB->getCondBit() && "Unexpected condition bit!");
 
     // Check block's successors.
     const auto &Successors = VPB->getSuccessors();
     // There must be only one instance of a successor in block's successor list.
     // TODO: This won't work for switch statements.

llvm/test/Transforms/LoopVectorize/vplan-printing-outer-loop.ll

 ; REQUIRES: asserts
 
 ; RUN: opt -loop-vectorize -enable-vplan-native-path -debug -disable-output %s 2>&1 | FileCheck %s
 
 @arr2 = external global [8 x i64], align 16
 @arr = external global [8 x [8 x i64]], align 16
 
 define void @foo(i64 %n) {
 ; CHECK:      VPlan 'HCFGBuilder: Plain CFG
 ; CHECK-NEXT: {
-; CHECK-NEXT: <x1> TopRegion: {
-; CHECK-NEXT:   entry:
-; CHECK-NEXT:   Successor(s): vector.body
+; CHECK-NEXT: entry:
+; CHECK-NEXT: Successor(s): outer.header
 ; CHECK-EMPTY:
+; CHECK-NEXT: <x1> outer.header: {
 ; CHECK-NEXT:   vector.body:
 ; CHECK-NEXT:     WIDEN-PHI ir<%outer.iv> = phi ir<0>, ir<%outer.iv.next>
 ; CHECK-NEXT:     EMIT ir<%gep.1> = getelementptr ir<@arr2> ir<0> ir<%outer.iv>
 ; CHECK-NEXT:     EMIT store ir<%outer.iv> ir<%gep.1>
 ; CHECK-NEXT:     EMIT ir<%add> = add ir<%outer.iv> ir<%n>
 ; CHECK-NEXT:   Successor(s): inner
 ; CHECK-EMPTY:
-; CHECK-NEXT:   inner:
-; CHECK-NEXT:     WIDEN-PHI ir<%inner.iv> = phi ir<0>, ir<%inner.iv.next>
-; CHECK-NEXT:     EMIT ir<%gep.2> = getelementptr ir<@arr> ir<0> ir<%inner.iv> ir<%outer.iv>
-; CHECK-NEXT:     EMIT store ir<%add> ir<%gep.2>
-; CHECK-NEXT:     EMIT ir<%inner.iv.next> = add ir<%inner.iv> ir<1>
-; CHECK-NEXT:     EMIT ir<%inner.ec> = icmp ir<%inner.iv.next> ir<8>
-; CHECK-NEXT:   Successor(s): outer.latch, inner
+; CHECK-NEXT:   <x1> inner: {
+; CHECK-NEXT:     inner:
+; CHECK-NEXT:       WIDEN-PHI ir<%inner.iv> = phi ir<0>, ir<%inner.iv.next>
+; CHECK-NEXT:       EMIT ir<%gep.2> = getelementptr ir<@arr> ir<0> ir<%inner.iv> ir<%outer.iv>
+; CHECK-NEXT:       EMIT store ir<%add> ir<%gep.2>
+; CHECK-NEXT:       EMIT ir<%inner.iv.next> = add ir<%inner.iv> ir<1>
+; CHECK-NEXT:       EMIT ir<%inner.ec> = icmp ir<%inner.iv.next> ir<8>
+; CHECK-NEXT:   No successors
 ; CHECK-NEXT:   CondBit: ir<%inner.ec> (inner)
+; CHECK-NEXT:  }
+; CHECK-NEXT:  Successor(s): outer.latch
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   outer.latch:
 ; CHECK-NEXT:     EMIT ir<%outer.iv.next> = add ir<%outer.iv> ir<1>
 ; CHECK-NEXT:     EMIT ir<%outer.ec> = icmp ir<%outer.iv.next> ir<8>
-; CHECK-NEXT:   Successor(s): exit, vector.body
+; CHECK-NEXT:   No successors
 ; CHECK-NEXT:   CondBit: ir<%outer.ec> (outer.latch)
+; CHECK-NEXT:  }
+; CHECK-NEXT: Successor(s): exit
 ; CHECK-EMPTY:
-; CHECK-NEXT:   exit:
-; CHECK-NEXT:     EMIT ret
-; CHECK-NEXT:   No successors
-; CHECK-NEXT: }
+; CHECK-NEXT: exit:
 ; CHECK-NEXT: No successors
 ; CHECK-NEXT: }
 entry:
   br label %outer.header
 
 outer.header:
   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
   %gep.1 = getelementptr inbounds [8 x i64], [8 x i64]* @arr2, i64 0, i64 %outer.iv

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) {
   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
   auto Plan = buildHCFG(LoopHeader);
 
   VPBasicBlock *Entry = Plan->getEntry()->getEntryBasicBlock();
   EXPECT_NE(nullptr, Entry->getSingleSuccessor());
   EXPECT_EQ(0u, Entry->getNumPredecessors());
   EXPECT_EQ(1u, Entry->getNumSuccessors());
   EXPECT_EQ(nullptr, Entry->getCondBit());
 
+  // Check that the region following the preheader is a single basic-block
+  // region (loop).
   VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock();
   EXPECT_EQ(7u, VecBB->size());
-  EXPECT_EQ(2u, VecBB->getNumPredecessors());
-  EXPECT_EQ(2u, VecBB->getNumSuccessors());
+  EXPECT_EQ(0u, VecBB->getNumPredecessors());
+  EXPECT_EQ(0u, VecBB->getNumSuccessors());
+  EXPECT_EQ(VecBB->getParent()->getEntryBasicBlock(), VecBB);
+  EXPECT_EQ(VecBB->getParent()->getExitingBasicBlock(), VecBB);
   EXPECT_EQ(&*Plan, VecBB->getPlan());
 
   auto Iter = VecBB->begin();
   VPWidenPHIRecipe *Phi = dyn_cast<VPWidenPHIRecipe>(&*Iter++);
   EXPECT_NE(nullptr, Phi);
 
   VPInstruction *Idx = dyn_cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode());
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   std::string FullDump;
   raw_string_ostream OS(FullDump);
   Plan->printDOT(OS);
   const char *ExpectedStr = R"(digraph VPlan {
 graph [labelloc=t, fontsize=30; label="Vectorization Plan"]
 node [shape=rect, fontname=Courier, fontsize=30]
 edge [fontname=Courier, fontsize=30]
 compound=true
-  subgraph cluster_N0 {
-    fontname=Courier
-    label="\<x1\> TopRegion"
-    N1 [label =
-      "entry:\l" +
-      "Successor(s): vector.body\l"
-    ]
-    N1 -> N2 [ label=""]
-    N2 [label =
+  N0 [label =
+    "Successor(s): for.body\l"
+  N0 -> N1 [ label="" lhead=cluster_N2]
+  subgraph cluster_N2 {
+    fontname=Courier
+    label="\<x1\> for.body"
+    N1 [label =
       "vector.body:\l" +
       "  WIDEN-PHI ir\<%indvars.iv\> = phi ir\<0\>, ir\<%indvars.iv.next\>\l" +
       "  EMIT ir\<%arr.idx\> = getelementptr ir\<%A\> ir\<%indvars.iv\>\l" +
       "  EMIT ir\<%l1\> = load ir\<%arr.idx\>\l" +
       "  EMIT ir\<%res\> = add ir\<%l1\> ir\<10\>\l" +
       "  EMIT store ir\<%res\> ir\<%arr.idx\>\l" +
       "  EMIT ir\<%indvars.iv.next\> = add ir\<%indvars.iv\> ir\<1\>\l" +
       "  EMIT ir\<%exitcond\> = icmp ir\<%indvars.iv.next\> ir\<%N\>\l" +
-      "Successor(s): vector.body, for.end\l" +
+      "No successors\l" +
       "CondBit: ir\<%exitcond\> (vector.body)\l"
     ]
-    N2 -> N2 [ label="T"]
-    N2 -> N3 [ label="F"]
-    N3 [label =
-      "for.end:\l" +
-      "  EMIT ret\l" +
-      "No successors\l"
-    ]
-  }
-}
+  }
+  N1 -> N3 [ label="" ltail=cluster_N2]
 )";
   EXPECT_EQ(ExpectedStr, FullDump);
 #endif
 
   SmallPtrSet<Instruction *, 1> DeadInstructions;
   VPlanTransforms::VPInstructionsToVPRecipes(
       LI->getLoopFor(LoopHeader), Plan, [](PHINode *P) { return nullptr; },
       DeadInstructions, *SE);
TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {
   VPlanTransforms::VPInstructionsToVPRecipes(
       LI->getLoopFor(LoopHeader), Plan, [](PHINode *P) { return nullptr; },
       DeadInstructions, *SE);
 
   VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock();
   EXPECT_NE(nullptr, Entry->getSingleSuccessor());
   EXPECT_EQ(0u, Entry->getNumPredecessors());
   EXPECT_EQ(1u, Entry->getNumSuccessors());
 
+  // Check that the region following the preheader is a single basic-block
+  // region (loop).
   VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock();
   EXPECT_EQ(7u, VecBB->size());
-  EXPECT_EQ(2u, VecBB->getNumPredecessors());
-  EXPECT_EQ(2u, VecBB->getNumSuccessors());
+  EXPECT_EQ(0u, VecBB->getNumPredecessors());
+  EXPECT_EQ(0u, VecBB->getNumSuccessors());
+  EXPECT_EQ(VecBB->getParent()->getEntryBasicBlock(), VecBB);
+  EXPECT_EQ(VecBB->getParent()->getExitingBasicBlock(), VecBB);
 
   auto Iter = VecBB->begin();
   EXPECT_NE(nullptr, dyn_cast<VPWidenPHIRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenGEPRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
   EXPECT_EQ(VecBB->end(), Iter);
 }
 
 } // namespace
 } // namespace llvm

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

 //===- llvm/unittests/Transforms/Vectorize/VPlanTest.cpp - VPlan tests ----===//
 //
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../lib/Transforms/Vectorize/VPlan.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "gtest/gtest.h"
 #include <string>
 
 namespace llvm {

llvm/unittests/Transforms/Vectorize/VPlanTestBase.h

protected:
   }
 
   /// Build the VPlan plain CFG for the loop starting from \p LoopHeader.
   VPlanPtr buildPlainCFG(BasicBlock *LoopHeader) {
     doAnalysis(*LoopHeader->getParent());
 
     auto Plan = std::make_unique<VPlan>();
     VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get(), *Plan);
-    VPRegionBlock *TopRegion = HCFGBuilder.buildPlainCFG();
-    Plan->setEntry(TopRegion);
+    VPBasicBlock *EntryVPBB = HCFGBuilder.buildPlainCFG();
+    Plan->setEntry(EntryVPBB);
     return Plan;
   }
 };
 
 } // namespace llvm
 
 #endif // LLVM_UNITTESTS_TRANSFORMS_VECTORIZE_VPLANTESTBASE_H