[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

8672

nit: can also remove brackets

llvm/lib/Transforms/Vectorize/VPlan.cpp

284

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

40

nit: formatting fix independent of this patch

2645

May as well return to current version(?) doing

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

2651

ditto

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.cpp

269

Comment still intact?

285

remove brackets

293

} else if {

295

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

299

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

302

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(?)

313

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?

321

"NonReplicateRegion" >> "LoopRegion"?

328

ditto

345

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)?

?

946

nit: why is setting CFG.PrevBB moved?

948

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

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

77

typo: TheLoop

86

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

287

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

323

Why move?

341

Why added spaces?

360

Backedge was not connected above?

[fhahn]

Rebased and addressed comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8672

Should be fixed!

llvm/lib/Transforms/Vectorize/VPlan.cpp

269

This is not relevant any longer, removed!

284

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.

293

Simplified, thanks!

299

Added a comment, thanks!

302

Renamed and added extra assertions, thanks!

313

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

321

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

345

Should be updated in the latest version

946

Not moved in the latest version.

948

This is also gone in the latest version.

llvm/lib/Transforms/Vectorize/VPlan.h

40

Should be fixed, thanks!

2645

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

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

77

I *think* this should be fixed.

86

HeaderBB/LatchBB is gone in the latest version.

287

Why move?

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

323

Undone.

341

Should be removed.

360

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

93

Is this change needed?

119

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.

126

Deserves a separate getOrCreate[EnclosingLoop]Region()?

141

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.

274

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

284

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.

333

3. >> 2. ?

335

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)?

340–370

4. >> 3. ?

356

HeaderPred >> PreheaderVPBB?

366

LatchSucc >> ExitVPBB? Where LatchVPBB == ExitingVPBB.

374

5. >> 4.

388

Unrelated to this patch: setName under LLVM_DEBUG?

390

getVectorLoopRegion()?

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

Can explain:

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

177

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

93

Nope, removed the stray change, thanks!

119

Extended the comment, thanks!

126

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?

141

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

274

Done, thanks!

284

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.

333

Numbering updated, thanks!

340–370

Numbering updated, thanks!

356

Fixed, thanks!

366

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

374

Numbering fixed, thanks!

388

Will do separately.

390

updated, 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

Added, thanks!

177

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

126

Added comment suffices to help readability, thanks!

274

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,
                                   bool HasNUW, bool IsVPlanNative) {
   Value *StartIdx = ConstantInt::get(IdxTy, 0);
   auto *StartV = Plan.getOrAddVPValue(StartIdx);
 
   auto *CanonicalIVPHI = new VPCanonicalIVPHIRecipe(StartV, DL);
   VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
   VPBasicBlock *Header = TopRegion->getEntryBasicBlock();
-  if (IsVPlanNative)
-    Header = cast<VPBasicBlock>(Header->getSingleSuccessor());
   Header->insert(CanonicalIVPHI, Header->begin());
 
   auto *CanonicalIVIncrement =
       new VPInstruction(HasNUW ? VPInstruction::CanonicalIVIncrementNUW
                                : VPInstruction::CanonicalIVIncrement,
                         {CanonicalIVPHI}, DL);
   CanonicalIVPHI->addOperand(CanonicalIVIncrement);
 
   VPBasicBlock *EB = TopRegion->getExitBasicBlock();
   if (IsVPlanNative) {
-    EB = cast<VPBasicBlock>(EB->getSinglePredecessor());
     EB->setCondBit(nullptr);
   }
   EB->appendRecipe(CanonicalIVIncrement);
 
   auto *BranchOnCount =
       new VPInstruction(VPInstruction::BranchOnCount,
                         {CanonicalIVIncrement, &Plan.getVectorTripCount()}, DL);
   EB->appendRecipe(BranchOnCount);

llvm/lib/Transforms/Vectorize/VPlan.h

 #include "llvm/ADT/GraphTraits.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/VectorUtils.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() {
-    return cast<VPRegionBlock>(getEntry());
+    auto *R = dyn_cast<VPRegionBlock>(getEntry());
+    if (R)
+      return R;
+    return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
   }
   const VPRegionBlock *getVectorLoopRegion() const {
-    return cast<VPRegionBlock>(getEntry());
+    auto *R = dyn_cast<VPRegionBlock>(getEntry());
+    if (R)
+      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

for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
     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');
-    if (isa<UnreachableInst>(PredBBTerminator)) {
+    auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
+    if (isa<UnreachableInst>(PredBBTerminator) ||
+        (TermBr && !TermBr->isConditional())) {
       assert(PredVPSuccessors.size() == 1 &&
              "Predecessor ending w/o branch must have single successor.");
+      if (TermBr) {
+        TermBr->setSuccessor(0, NewBB);
+      } else {
         DebugLoc DL = PredBBTerminator->getDebugLoc();
         PredBBTerminator->eraseFromParent();
         auto *Br = BranchInst::Create(NewBB, PredBB);
         Br->setDebugLoc(DL);
+      }
     } else {
-      assert(PredVPSuccessors.size() == 2 &&
-             "Predecessor ending with branch must have two successors.");
+      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 {
+        auto *Reg = dyn_cast<VPRegionBlock>(PredVPBB->getParent());
+        assert(Reg && !Reg->isReplicator());
+        assert(this == Reg->getSingleSuccessor());
+        PredBBTerminator->setSuccessor(0, NewBB);
+        PredBBTerminator->setSuccessor(
+            1, CFG.VPBB2IRBB[Reg->getEntryBasicBlock()]);
+      }
     }
   }
   return NewBB;
 }
 
 void VPBasicBlock::execute(VPTransformState *State) {
+  if (!getParent() && getNumSuccessors() == 0)
+    return;
+
   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 GetEnclosingNonReplicateRegion = [](VPBasicBlock *VPBB) {
+    VPRegionBlock *P = VPBB->getParent();
+    if (P && P->isReplicator())
+      return P->getParent();
+    return P;
+  };
+
+  auto IsNonReplicateR = [](VPBlockBase *BB) {
+    auto *R = dyn_cast<VPRegionBlock>(BB);
+    return R && !R->isReplicator();
+  };
+
   // 1. Create an IR basic block, or reuse the last one if possible.
   // The last IR basic block is reused, as an optimization, in three cases:
   // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
   // B. when the current VPBB has a single (hierarchical) predecessor which
   //    is PrevVPBB and the latter has a single (hierarchical) successor; and
   // C. when the current VPBB is an entry of a region replica - where PrevVPBB
   //    is the exit of this region from a previous instance, or the predecessor
   //    of this region.
   if (PrevVPBB && /* A */
       !((SingleHPred = getSingleHierarchicalPredecessor()) &&
         SingleHPred->getExitBasicBlock() == PrevVPBB &&
-        PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
-      !(Replica && getPredecessors().empty())) {       /* C */
+        PrevVPBB->getSingleHierarchicalSuccessor() &&
+        (SingleHPred->getParent() == GetEnclosingNonReplicateRegion(this) &&
+         !IsNonReplicateR(SingleHPred))) &&      /* B */
+      !(Replica && getPredecessors().empty())) { /* C */
     NewBB = createEmptyBasicBlock(State->CFG);
     State->Builder.SetInsertPoint(NewBB);
     // Temporarily terminate with unreachable until CFG is rewired.
     UnreachableInst *Terminator = State->Builder.CreateUnreachable();
     State->Builder.SetInsertPoint(Terminator);
     State->CFG.PrevBB = NewBB;
   }
 
if (!isReplicator()) {
     // before calling any utilities such as SCEV that require valid LoopInfo.
     if (ParentLoop)
       ParentLoop->addChildLoop(State->CurrentVectorLoop);
     else
       State->LI->addTopLevelLoop(State->CurrentVectorLoop);
 
     // Visit the VPBlocks connected to "this", starting from it.
     for (VPBlockBase *Block : RPOT) {
-      if (EnableVPlanNativePath) {
-        // The inner loop vectorization path does not represent loop preheader
-        // and exit blocks as part of the VPlan. In the VPlan-native path, skip
-        // vectorizing loop preheader block. In future, we may replace this
-        // check with the check for loop preheader.
-        if (Block->getNumPredecessors() == 0)
-          continue;
-
-        // Skip vectorizing loop exit block. In future, we may replace this
-        // check with the check for loop exit.
-        if (Block->getNumSuccessors() == 0)
-          continue;
-      }
-
       LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
       Block->execute(State);
     }
 
     State->CurrentVectorLoop = PrevLoop;
     return;
   }
 

 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;
   BasicBlock *VectorHeaderBB = State->CFG.VectorPreHeader->getSingleSuccessor();
-  State->CFG.PrevBB = VectorHeaderBB;
   State->CFG.ExitBB = VectorHeaderBB->getSingleSuccessor();
+  State->CFG.PrevBB = VectorHeaderBB;
   State->CurrentVectorLoop = State->LI->getLoopFor(VectorHeaderBB);
 
+  if (isa<VPBasicBlock>(getEntry())) {
+    MergeBlockIntoPredecessor(VectorHeaderBB);
+    State->CFG.PrevBB = State->CFG.VectorPreHeader;
+    VectorHeaderBB = State->CFG.VectorPreHeader;
+  }
+
   // Remove the edge between Header and Latch to allow other connections.
   // Temporarily terminate with unreachable until CFG is rewired.
   // Note: this asserts the generated code's assumption that
   // getFirstInsertionPt() can be dereferenced into an Instruction.
   VectorHeaderBB->getTerminator()->eraseFromParent();
   State->Builder.SetInsertPoint(VectorHeaderBB);
   UnreachableInst *Terminator = State->Builder.CreateUnreachable();
   State->Builder.SetInsertPoint(Terminator);

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 setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB,
+                          BasicBlock *LatchBB);
   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) {
+// must have no predecessors. Skip \p HeaderBB if it is a predecessor. The
+// backedge of the loop is modeled implicitly through the containing region
+// block.
+void PlainCFGBuilder::setVPBBPredsFromBB(VPBasicBlock *VPBB, BasicBlock *BB,
+                                         BasicBlock *HeaderBB) {
   SmallVector<VPBlockBase *, 8> VPBBPreds;
   // Collect VPBB predecessors.
-  for (BasicBlock *Pred : predecessors(BB))
-    VPBBPreds.push_back(getOrCreateVPBB(Pred));
+  for (BasicBlock *Pred : predecessors(BB)) {
+    if (Pred == HeaderBB)
+      continue;
+    auto *PredVPBB = getOrCreateVPBB(Pred);
+    VPBBPreds.push_back(PredVPBB);
+  }
 
   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.
 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);
   for (auto &I : *PreheaderBB) {
     if (I.getType()->isVoidTy())
       continue;
     VPValue *VPV = new VPValue(&I);
     Plan.addExternalDef(VPV);
     IRDef2VPValue[&I] = VPV;
   }
   // Create empty VPBB for Loop H so that we can link PH->H.
   VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
-  // Preheader's predecessors will be set during the loop RPO traversal below.
-  PreheaderVPBB->setOneSuccessor(HeaderVPBB);
   HeaderVPBB->setName("vector.body");
 
+  PreheaderVPBB->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);
if (NumSuccs == 1) {
       // Get VPBB's condition bit.
       assert(isa<BranchInst>(TI) && "Unsupported terminator!");
       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];
 
+      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);
+    setVPBBPredsFromBB(VPBB, BB, nullptr);
   }
 
   // 3. 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);
+  //  Loop exit was already set as successor of the loop exiting BB.
+  //  We only set its predecessor VPBB now.
+  setVPBBPredsFromBB(LoopExitVPBB, LoopExitBB, nullptr);
 
-  // 4. The whole CFG has been built at this point so all the input Values must
+  // 4. 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.
+  std::vector<Loop *> SubLoops = TheLoop->getSubLoops();
+  SubLoops.push_back(TheLoop);
+  for (auto *L : SubLoops) {
+    auto *Header = L->getHeader();
+    auto *Latch = L->getLoopLatch();
+    auto *Region = Loop2Region[L];
+    auto *HeaderVPBB = getOrCreateVPBB(Header);
+    auto *LatchVPBB = getOrCreateVPBB(Latch);
+
+    auto *HeaderPred = getOrCreateVPBB(L->getLoopPreheader());
+    VPBlockUtils::disconnectBlocks(HeaderPred, HeaderVPBB);
+    VPBlockUtils::disconnectBlocks(LatchVPBB, HeaderVPBB);
+    Region->setParent(HeaderPred->getParent());
+    Region->setEntry(HeaderVPBB);
+    VPBlockUtils::connectBlocks(HeaderPred, Region);
+
+    auto *LatchSucc = getOrCreateVPBB(L->getExitBlock());
+    VPBlockUtils::disconnectBlocks(LatchVPBB, LatchSucc);
+    Region->setExit(LatchVPBB);
+    VPBlockUtils::connectBlocks(Region, LatchSucc);
+  }
+  // 5. 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->setExit(LoopExitVPBB);
-  return TopRegion;
+  return PreheaderVPBB;
 }
 
-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);
 
+  auto *TopRegion = cast<VPRegionBlock>(EntryVPBB->getSingleSuccessor());
   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(VPBlockRecursiveTraversalWrapper<VPBlockBase *>(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->getExit()))) {
     // 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->getExitBasicBlock() == 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/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());
 
   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()->getExitBasicBlock(), 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());
 
   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()->getExitBasicBlock(), 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 "llvm/ADT/PostOrderIterator.h"
 #include "gtest/gtest.h"
 #include <string>
 
 namespace llvm {
 namespace {
 
 #define CHECK_ITERATOR(Range1, ...)                                            \
   do {                                                                         \

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