[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

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

2119

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?

263

Should this inverse use something like VPAllPredecessorsIterator?

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

274

GraphTraits for Regions removed as no longer needed?

279

commented-out code to be removed?

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

63

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)

72

nit: // }

111

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

161

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

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

2119

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

263

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.

274

Yep

279

removed, thanks!

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

63

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?

72

Updated, thanks!

111

added, thanks!

161

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

OK, worth leaving behind a comment?

llvm/lib/Transforms/Vectorize/VPlanCFG.h

63

OK, worth a comment?

263

Very well.

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

61

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

63

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

This has been removed in the latest version based on D142162

llvm/lib/Transforms/Vectorize/VPlanCFG.h

63

Added, thanks!

263

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

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

63

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/VPlan.h

public:
   /// An enumeration for keeping track of the concrete subclass of VPBlockBase
   /// that are actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPBlockBase objects. They are used for concrete
   /// type identification.
   using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
 
   using VPBlocksTy = SmallVectorImpl<VPBlockBase *>;
 
-  using ParentPtrTy = VPRegionBlock *;
+  using ParentPtrTy = VPlan *;
 
   virtual ~VPBlockBase() = default;
 
   const std::string &getName() const { return Name; }
 
   void setName(const Twine &newName) { Name = newName.str(); }
 
   /// \return an ID for the concrete type of this object.
assert(EntryBlock->getPredecessors().empty() &&
            "Entry block cannot have predecessors.");
     Entry = EntryBlock;
     EntryBlock->setParent(this);
   }
 
   // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a
   // specific interface of llvm::Function, instead of using
   // GraphTraints::getEntryNode. We should add a new template parameter to
   // DominatorTreeBase representing the Graph type.
   VPBlockBase &front() const { return *Entry; }
 
   const VPBlockBase *getExiting() const { return Exiting; }
   VPBlockBase *getExiting() { return Exiting; }
 
   /// Set \p ExitingBlock as the exiting VPBlockBase of this VPRegionBlock. \p
   /// ExitingBlock must have no successors.
   void setExiting(VPBlockBase *ExitingBlock) {
void prepareToExecute(Value *TripCount, Value *VectorTripCount,
                         Value *CanonicalIVStartValue, VPTransformState &State,
                         bool IsEpilogueVectorization);
 
   /// Generate the IR code for this VPlan.
   void execute(VPTransformState *State);
 
   VPBlockBase *getEntry() { return Entry; }
   const VPBlockBase *getEntry() const { return Entry; }
+  VPBlockBase &front() { return *Entry; }
 
   VPBlockBase *setEntry(VPBlockBase *Block) {
     Entry = Block;
     Block->setPlan(this);
     return Entry;
   }
 
   /// The trip count of the original loop.

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 NodeRef = VPBlockBase *;
-  using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::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();
-  }
-};
-
-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:
+  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(VPBlockRecursiveTraversalWrapper<VPBlockBase *>(G));
 }
 inline iterator_range<
     df_iterator<VPBlockRecursiveTraversalWrapper<const VPBlockBase *>>>
 vp_depth_first_deep(const VPBlockBase *G) {
   return depth_first(VPBlockRecursiveTraversalWrapper<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);
+  }
+};
+
+// 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();
+  }
+};
+
+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

 #include "llvm/IR/Dominators.h"
 
 namespace llvm {
 
 /// Template specialization of the standard LLVM dominator tree utility for
 /// VPBlockBases.
 using VPDominatorTree = DomTreeBase<VPBlockBase>;
 
+template <> inline VPlan *VPDominatorTree::getParent(VPBlockBase *B) const {
+  return B->getPlan();
+}
+
 using VPDomTreeNode = DomTreeNodeBase<VPBlockBase>;
 
 /// Template specializations of GraphTraits for VPDomTreeNode.
 template <>
 struct GraphTraits<VPDomTreeNode *>
     : public DomTreeGraphTraitsBase<VPDomTreeNode,
                                     VPDomTreeNode::const_iterator> {};
 
 template <>
 struct GraphTraits<const VPDomTreeNode *>
     : public DomTreeGraphTraitsBase<const VPDomTreeNode,
                                     VPDomTreeNode::const_iterator> {};
 } // namespace llvm
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H

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/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   Core
   Vectorize
   AsmParser
   TargetParser
   )
 
 add_llvm_unittest(VectorizeTests
   VPlanTest.cpp
+  VPDomTreeTest.cpp
   VPlanHCFGTest.cpp
   VPlanSlpTest.cpp
   )
 
 set_property(TARGET VectorizeTests PROPERTY FOLDER "Tests/UnitTests/TransformsTests")

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp

+//===- llvm/unittests/Transforms/Vectorize/VPDomTreeTests.cpp - -----------===//
+//
+//
+// 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 "../lib/Transforms/Vectorize/VPlanDominatorTree.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+TEST(VPDominatorTreeTest, DominanceNoRegionsTest) {
+  {
+    VPBasicBlock *VPBB1 = new VPBasicBlock();
+    VPBasicBlock *VPBB2 = new VPBasicBlock();
+    VPBasicBlock *VPBB3 = new VPBasicBlock();
+    VPBasicBlock *VPBB4 = new VPBasicBlock();
+
+    //     VPBB1
+    //     /   \
+    // VPBB2  VPBB3
+    //    \    /
+    //    VPBB4
+    VPBlockUtils::connectBlocks(VPBB1, VPBB2);
+    VPBlockUtils::connectBlocks(VPBB1, VPBB3);
+    VPBlockUtils::connectBlocks(VPBB2, VPBB4);
+    VPBlockUtils::connectBlocks(VPBB3, VPBB4);
+
+    VPlan Plan;
+    Plan.setEntry(VPBB1);
+
+    VPDominatorTree VPDT;
+    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