[VPlan] Switch default graph traits to be recursive, update VPDomTree.

[fhahn]

Summary

This updates the GraphTraits specialization for VPBlockBase to recurse
through VPRegionBlocks.

This in turn enables using VPDominatorTree to query dominance between
any block in a plan. This should enable additional use cases, including
improvements to def-use verification and porting IR-based transforms
that rely on the dominator tree.

Specifically, this change means that for regions, the entry and exit
blocks dominate the successors of the region.

Depends on D140512 and D142162.

[fhahn]

Add VPDominatorTree::getParent specialization, add tests for findNearestCommonDominator.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.h

451 ↗

(On Diff #487316)

who's using ParentPtrTy? Parent itself is still a VPRegionBase*...

2172 ↗

(On Diff #487316)

Is the above FIXME related to the current changes which include front below, and/or a good time to address?

llvm/lib/Transforms/Vectorize/VPlanCFG.h

63

who's using this reference?

273

Should this inverse use something like VPAllPredecessorsIterator?

Would be good to test the order of an inverse iterator.

284

GraphTraits for Regions removed as no longer needed?

289

commented-out code to be removed?

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

62

nit: ascii art at the ends of the two lines above which represent a cycle, may look better using

     __
 \  /  \
R1BB3   |
 /  \__/

where all incoming edges appear on top and all outgoing edges appear on bottom.

(A cycle deserves a region, here and below. When all loop back arcs are captured inside loop regions the HCFG is a (hierarchical) DAG)

71

nit: // }

110

Also
EXPECT_TRUE(VPDT.dominates(R1BB4, R2BB1));
EXPECT_FALSE(VPDT.dominates(R1BB3, R2BB1));
?

160

Here's a good place to build a dominator tree and check its edges?

[fhahn]

Address comments, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

451 ↗

(On Diff #487316)

This is a workaround for the issue that the dominator tree base classes rely on NodeT::getParent() to return a container type that all nodes share, like Function for basic blocks.

But for VPBlockBase it returns the parent region which may be nullptr. To have a DT spanning all regions in a plan, the parent needs to be VPlan.

There probably are other options to address this, D141260 is just a relatively simple/non-invasive way to get things to build and work. Now that we seem to be converging on cross region DTs, we should iron out the workaround as well

2172 ↗

(On Diff #487316)

Yes, it might be good to address this FIXME now. I'll look into it.

llvm/lib/Transforms/Vectorize/VPlanCFG.h

63

It is used by iterator_facade_base with bidirectional_iterator_tag

273

I think the inverse is only needed for DT updates and post-dominators. We don't use either at the moment, I updated all implementations here to use llvm_unreachable and added a TODO. But it should not be needed for DT functionality we need to get started.

284

Yep

289

removed, thanks!

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

62

Improved the ASCII art, thanks!

(A cycle deserves a region, here and below. When all loop back arcs are captured inside loop regions the HCFG is a (hierarchical) DAG)

The intention of the test is to make sure cycles in the graph are handled. We could forbid explicit cycles in the verifier though?

71

Updated, thanks!

110

added, thanks!

160

Updated code here to check the immediate dominators, which is more compact. I retained the dominance checks above.

[Ayal]

Looks good to me, with a few minor nits.

llvm/lib/Transforms/Vectorize/VPlan.h

451 ↗

(On Diff #487316)

OK, worth leaving behind a comment?

llvm/lib/Transforms/Vectorize/VPlanCFG.h

63

OK, worth a comment?

273

Very well.

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

61

nit: this also checks the children order, in addition to dominance relation.

62

Currently cycles should be captured in regions so that, e.g., VPRegionBlock::execute() would allocate loops, and this is arguably the approach going forward. So it would probably be better to forbid explicit cycles for now.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

451 ↗

(On Diff #487316)

This has been removed in the latest version based on D142162

llvm/lib/Transforms/Vectorize/VPlanCFG.h

63

Added, thanks!

273

I missed uploading the part, should be fixed. in the latest version.

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

62

Sounds good, I can prepare a follow-up.

[fhahn]

Rebased on top of D142162 and added comment, thanks!

[fhahn]

Rebased again after changes to D142162.

[fhahn]

Rebase before landing

llvm/lib/Transforms/Vectorize/VPlanCFG.h

 #include "llvm/ADT/SmallVector.h"
 
 namespace llvm {
 
 //===----------------------------------------------------------------------===//
 // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs     //
 //===----------------------------------------------------------------------===//
 
-// The following set of template specializations implement GraphTraits to treat
-// any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
-// that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
-// VPBlockBase is a VPRegionBlock, this specialization provides access to its
-// successors/predecessors but not to the blocks inside the region.
-
-template <> struct GraphTraits<VPBlockBase *> {
-  using ParentPtrTy = VPRegionBlock *;
-  using NodeRef = VPBlockBase *;
-  using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
-
-  static NodeRef getEntryNode(NodeRef N) { return N; }
-  static NodeRef getEntryNode(VPRegionBlock *R) { return R->getEntry(); }
-
-  static inline ChildIteratorType child_begin(NodeRef N) {
-    return N->getSuccessors().begin();
-  }
-
-  static inline ChildIteratorType child_end(NodeRef N) {
-    return N->getSuccessors().end();
-  }
-};
-
-template <> struct GraphTraits<const VPBlockBase *> {
-  using NodeRef = const VPBlockBase *;
-  using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
-
-  static NodeRef getEntryNode(NodeRef N) { return N; }
-
-  static inline ChildIteratorType child_begin(NodeRef N) {
-    return N->getSuccessors().begin();
-  }
-
-  static inline ChildIteratorType child_end(NodeRef N) {
-    return N->getSuccessors().end();
-  }
-};
-
-// Inverse order specialization for VPBasicBlocks. Predecessors are used instead
-// of successors for the inverse traversal.
-template <> struct GraphTraits<Inverse<VPBlockBase *>> {
-  using NodeRef = VPBlockBase *;
-  using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
-
-  static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
-
-  static inline ChildIteratorType child_begin(NodeRef N) {
-    return N->getPredecessors().begin();
-  }
-
-  static inline ChildIteratorType child_end(NodeRef N) {
-    return N->getPredecessors().end();
-  }
-};
-
-// The following set of template specializations implement GraphTraits to
-// treat VPRegionBlock as a graph and recurse inside its nodes. It's important
-// to note that the blocks inside the VPRegionBlock are treated as VPBlockBases
-// (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so
-// there won't be automatic recursion into other VPBlockBases that turn to be
-// VPRegionBlocks.
-
-template <>
-struct GraphTraits<VPRegionBlock *> : public GraphTraits<VPBlockBase *> {
-  using GraphRef = VPRegionBlock *;
-  using nodes_iterator = df_iterator<NodeRef>;
-
-  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
-
-  static nodes_iterator nodes_begin(GraphRef N) {
-    return nodes_iterator::begin(N->getEntry());
-  }
-
-  static nodes_iterator nodes_end(GraphRef N) {
-    // df_iterator::end() returns an empty iterator so the node used doesn't
-    // matter.
-    return nodes_iterator::end(N);
-  }
-};
-
-template <>
-struct GraphTraits<const VPRegionBlock *>
-    : public GraphTraits<const VPBlockBase *> {
-  using GraphRef = const VPRegionBlock *;
-  using nodes_iterator = df_iterator<NodeRef>;
-
-  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
-
-  static nodes_iterator nodes_begin(GraphRef N) {
-    return nodes_iterator::begin(N->getEntry());
-  }
-
-  static nodes_iterator nodes_end(GraphRef N) {
-    // df_iterator::end() returns an empty iterator so the node used doesn't
-    // matter.
-    return nodes_iterator::end(N);
-  }
-};
-
-template <>
-struct GraphTraits<Inverse<VPRegionBlock *>>
-    : public GraphTraits<Inverse<VPBlockBase *>> {
-  using GraphRef = VPRegionBlock *;
-  using nodes_iterator = df_iterator<NodeRef>;
-
-  static NodeRef getEntryNode(Inverse<GraphRef> N) {
-    return N.Graph->getExiting();
-  }
-
-  static nodes_iterator nodes_begin(GraphRef N) {
-    return nodes_iterator::begin(N->getExiting());
-  }
-
-  static nodes_iterator nodes_end(GraphRef N) {
-    // df_iterator::end() returns an empty iterator so the node used doesn't
-    // matter.
-    return nodes_iterator::end(N);
-  }
-};
-
 /// Iterator to traverse all successors of a VPBlockBase node. This includes the
 /// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their
 /// parent region's successors. This ensures all blocks in a region are visited
 /// before any blocks in a successor region when doing a reverse post-order
 // traversal of the graph. Region blocks themselves traverse only their entries
 // directly and not their successors. Those will be traversed when a region's
 // exiting block is traversed
 template <typename BlockPtrTy>
 class VPAllSuccessorsIterator
     : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>,
-                                  std::forward_iterator_tag, VPBlockBase> {
+                                  std::bidirectional_iterator_tag,
+                                  VPBlockBase> {
   BlockPtrTy Block;
   /// Index of the current successor. For VPBasicBlock nodes, this simply is the
   /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
   /// used for the region's entry block, and SuccessorIdx - 1 are the indices
   /// for the successor array.
   size_t SuccessorIdx;
 
   static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) {
if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
       return R->getEntry();
     }
 
     // For exit blocks, use the next parent region with successors.
     return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx];
   }
 
 public:
+  /// Used by iterator_facade_base with bidirectional_iterator_tag.
+  using reference = BlockPtrTy;
+
   VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0)
       : Block(Block), SuccessorIdx(Idx) {}
   VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
       : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
 
   VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) {
     Block = R.Block;
     SuccessorIdx = R.SuccessorIdx;
public:
 
   BlockPtrTy operator*() { return deref(Block, SuccessorIdx); }
 
   VPAllSuccessorsIterator &operator++() {
     SuccessorIdx++;
     return *this;
   }
 
+  VPAllSuccessorsIterator &operator--() {
+    SuccessorIdx--;
+    return *this;
+  }
+
   VPAllSuccessorsIterator operator++(int X) {
     VPAllSuccessorsIterator Orig = *this;
     SuccessorIdx++;
     return Orig;
   }
 };
 
 /// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
vp_depth_first_deep(VPBlockBase *G) {
   return depth_first(VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
 }
 inline iterator_range<
     df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
 vp_depth_first_deep(const VPBlockBase *G) {
   return depth_first(VPBlockDeepTraversalWrapper<const VPBlockBase *>(G));
 }
 
+// The following set of template specializations implement GraphTraits to treat
+// any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
+// that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
+// VPBlockBase is a VPRegionBlock, this specialization provides access to its
+// successors/predecessors but not to the blocks inside the region.
+
+template <> struct GraphTraits<VPBlockBase *> {
+  using NodeRef = VPBlockBase *;
+  using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>;
+
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N);
+  }
+
+  static inline ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType::end(N);
+  }
+};
+
+template <> struct GraphTraits<const VPBlockBase *> {
+  using NodeRef = const VPBlockBase *;
+  using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
+
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N);
+  }
+
+  static inline ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType::end(N);
+  }
+};
+
+/// Inverse graph traits are not implemented yet.
+/// TODO: Implement a version of VPBlockNonRecursiveTraversalWrapper to traverse
+/// predecessors recursively through regions.
+template <> struct GraphTraits<Inverse<VPBlockBase *>> {
+  using NodeRef = VPBlockBase *;
+  using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
+
+  static NodeRef getEntryNode(Inverse<NodeRef> B) {
+    llvm_unreachable("not implemented");
+  }
+
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    llvm_unreachable("not implemented");
+  }
+
+  static inline ChildIteratorType child_end(NodeRef N) {
+    llvm_unreachable("not implemented");
+  }
+};
+
+template <> struct GraphTraits<VPlan *> {
+  using GraphRef = VPlan *;
+  using NodeRef = VPBlockBase *;
+  using nodes_iterator = df_iterator<NodeRef>;
+
+  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
+
+  static nodes_iterator nodes_begin(GraphRef N) {
+    return nodes_iterator::begin(N->getEntry());
+  }
+
+  static nodes_iterator nodes_end(GraphRef N) {
+    // df_iterator::end() returns an empty iterator so the node used doesn't
+    // matter.
+    return nodes_iterator::end(N->getEntry());
+  }
+};
+
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H

llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h

 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
 
 #include "VPlan.h"
 #include "VPlanCFG.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
 
 template <> struct DomTreeNodeTraits<VPBlockBase> {
   using NodeType = VPBlockBase;
   using NodePtr = VPBlockBase *;
-  using ParentPtr = VPRegionBlock *;
+  using ParentPtr = VPlan *;
 
   static NodePtr getEntryNode(ParentPtr Parent) { return Parent->getEntry(); }
-  static ParentPtr getParent(VPBlockBase *B) { return B->getParent(); }
+  static ParentPtr getParent(NodePtr B) { return B->getPlan(); }
 };
 
 ///
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase<VPBlockBase>;
 
 using VPDomTreeNode = DomTreeNodeBase<VPBlockBase>;

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

void VPlanHCFGBuilder::buildHierarchicalCFG() {
   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);
+  VPDomTree.recalculate(Plan);
   LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
              VPDomTree.print(dbgs()));
 }

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

TEST(VPDominatorTreeTest, DominanceNoRegionsTest) {
   VPBlockUtils::connectBlocks(VPBB1, VPBB2);
   VPBlockUtils::connectBlocks(VPBB1, VPBB3);
   VPBlockUtils::connectBlocks(VPBB2, VPBB4);
   VPBlockUtils::connectBlocks(VPBB3, VPBB4);
 
   VPlan Plan;
   Plan.setEntry(R1);
   VPDominatorTree VPDT;
-  VPDT.recalculate(*R1);
+  VPDT.recalculate(Plan);
 
   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB4));
   EXPECT_FALSE(VPDT.dominates(VPBB4, VPBB1));
 
   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB2));
   EXPECT_FALSE(VPDT.dominates(VPBB2, VPBB1));
 
   EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB3));
   EXPECT_FALSE(VPDT.dominates(VPBB3, VPBB1));
 
   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB3), VPBB1);
   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB4), VPBB1);
   EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB4, VPBB4), VPBB4);
 }
+
+static void
+checkDomChildren(VPDominatorTree &VPDT, VPBlockBase *Src,
+                 std::initializer_list<VPBlockBase *> ExpectedChildren) {
+  SmallVector<VPDomTreeNode *> Children(VPDT.getNode(Src)->children());
+  SmallVector<VPDomTreeNode *> ExpectedNodes;
+  for (VPBlockBase *C : ExpectedChildren)
+    ExpectedNodes.push_back(VPDT.getNode(C));
+
+  EXPECT_EQ(Children, ExpectedNodes);
+}
+
+TEST(VPDominatorTreeTest, DominanceRegionsTest) {
+  {
+    // 2 consecutive regions.
+    // R1 {
+    //     \
+    //     R1BB1     _
+    //    /     \   / \
+    //  R1BB2   R1BB3  |
+    //    \      /  \_/
+    //     R1BB4
+    //  }
+    //   |
+    // R2 {
+    //   \
+    //    R2BB1
+    //      |
+    //    R2BB2
+    // }
+    //
+    VPBasicBlock *R1BB1 = new VPBasicBlock();
+    VPBasicBlock *R1BB2 = new VPBasicBlock();
+    VPBasicBlock *R1BB3 = new VPBasicBlock();
+    VPBasicBlock *R1BB4 = new VPBasicBlock();
+    VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB4, "R1");
+    R1BB2->setParent(R1);
+    R1BB3->setParent(R1);
+    VPBlockUtils::connectBlocks(R1BB1, R1BB2);
+    VPBlockUtils::connectBlocks(R1BB1, R1BB3);
+    VPBlockUtils::connectBlocks(R1BB2, R1BB4);
+    VPBlockUtils::connectBlocks(R1BB3, R1BB4);
+    // Cycle.
+    VPBlockUtils::connectBlocks(R1BB3, R1BB3);
+
+    VPBasicBlock *R2BB1 = new VPBasicBlock();
+    VPBasicBlock *R2BB2 = new VPBasicBlock();
+    VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
+    VPBlockUtils::connectBlocks(R2BB1, R2BB2);
+    VPBlockUtils::connectBlocks(R1, R2);
+
+    VPlan Plan;
+    Plan.setEntry(R1);
+    VPDominatorTree VPDT;
+    VPDT.recalculate(Plan);
+
+    checkDomChildren(VPDT, R1, {R1BB1});
+    checkDomChildren(VPDT, R1BB1, {R1BB2, R1BB4, R1BB3});
+    checkDomChildren(VPDT, R1BB2, {});
+    checkDomChildren(VPDT, R1BB3, {});
+    checkDomChildren(VPDT, R1BB4, {R2});
+    checkDomChildren(VPDT, R2, {R2BB1});
+    checkDomChildren(VPDT, R2BB1, {R2BB2});
+
+    EXPECT_TRUE(VPDT.dominates(R1, R2));
+    EXPECT_FALSE(VPDT.dominates(R2, R1));
+
+    EXPECT_TRUE(VPDT.dominates(R1BB1, R1BB4));
+    EXPECT_FALSE(VPDT.dominates(R1BB4, R1BB1));
+
+    EXPECT_TRUE(VPDT.dominates(R2BB1, R2BB2));
+    EXPECT_FALSE(VPDT.dominates(R2BB2, R2BB1));
+
+    EXPECT_TRUE(VPDT.dominates(R1BB1, R2BB1));
+    EXPECT_FALSE(VPDT.dominates(R2BB1, R1BB1));
+
+    EXPECT_TRUE(VPDT.dominates(R1BB4, R2BB1));
+    EXPECT_FALSE(VPDT.dominates(R1BB3, R2BB1));
+
+    EXPECT_TRUE(VPDT.dominates(R1, R2BB1));
+    EXPECT_FALSE(VPDT.dominates(R2BB1, R1));
+  }
+
+  {
+    // 2 nested regions.
+    //  VPBB1
+    //    |
+    //  R1 {
+    //         R1BB1
+    //       /        \
+    //   R2 {          |
+    //     \           |
+    //     R2BB1       |
+    //       |   \    R1BB2
+    //     R2BB2-/     |
+    //        \        |
+    //         R2BB3   |
+    //   }            /
+    //      \        /
+    //        R1BB3
+    //  }
+    //   |
+    //  VPBB2
+    //
+    VPBasicBlock *R1BB1 = new VPBasicBlock("R1BB1");
+    VPBasicBlock *R1BB2 = new VPBasicBlock("R1BB2");
+    VPBasicBlock *R1BB3 = new VPBasicBlock("R1BB3");
+    VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB3, "R1");
+
+    VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
+    VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
+    VPBasicBlock *R2BB3 = new VPBasicBlock("R2BB3");
+    VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB3, "R2");
+    R2BB2->setParent(R2);
+    VPBlockUtils::connectBlocks(R2BB1, R2BB2);
+    VPBlockUtils::connectBlocks(R2BB2, R2BB1);
+    VPBlockUtils::connectBlocks(R2BB2, R2BB3);
+
+    R2->setParent(R1);
+    VPBlockUtils::connectBlocks(R1BB1, R2);
+    R1BB2->setParent(R1);
+    VPBlockUtils::connectBlocks(R1BB1, R1BB2);
+    VPBlockUtils::connectBlocks(R1BB2, R1BB3);
+    VPBlockUtils::connectBlocks(R2, R1BB3);
+
+    VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
+    VPBlockUtils::connectBlocks(VPBB1, R1);
+    VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
+    VPBlockUtils::connectBlocks(R1, VPBB2);
+
+    VPlan Plan;
+    Plan.setEntry(VPBB1);
+    VPDominatorTree VPDT;
+    VPDT.recalculate(Plan);
+
+    checkDomChildren(VPDT, VPBB1, {R1});
+    checkDomChildren(VPDT, R1, {R1BB1});
+    checkDomChildren(VPDT, R1BB1, {R2, R1BB3, R1BB2});
+    checkDomChildren(VPDT, R1BB2, {});
+    checkDomChildren(VPDT, R2, {R2BB1});
+    checkDomChildren(VPDT, R2BB1, {R2BB2});
+    checkDomChildren(VPDT, R2BB2, {R2BB3});
+    checkDomChildren(VPDT, R2BB3, {});
+    checkDomChildren(VPDT, R1BB3, {VPBB2});
+    checkDomChildren(VPDT, VPBB2, {});
+  }
+}
+
 } // namespace
 } // namespace llvm