[VPlan] Introduce VPlan-based dominator analysis.

[dcaballe]

Summary

Context: Patch Series #1 for outer loop vectorization support in LV
using VPlan. (RFC: http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html).

The patch introduces dominator analysis for VPBlockBases and extend
VPlan's GraphTraits specialization with the required interfaces. Dominator
analysis will be necessary to perform some H-CFG transformations and
to introduce VPLoopInfo (LoopInfo analysis on top of the VPlan representation).

[fhahn]

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

20 ↗

(On Diff #153666)

I've put up D49032 for review, which adds a VPlanTestBase class which can be re-used by different tests to construct modules & VPlans. What do you think? I can adjust the interface so it matches the one described here. What do you think? :)

[dcaballe]

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

20 ↗

(On Diff #153666)

It sounds pretty good! Much cleaner! I approved it but feel free to change it to match the interfaces here. I'll have a look at it again.
I'll rebase this patch on top of that once it's ready.

[dcaballe]

lib/Transforms/Vectorize/VPlan.cpp

198 ↗

(On Diff #153666)

I'd like to hear your feedback on this. Internally, we started with an 'unsigned size' class member that we tried to maintain transformation after transformation. However, there are many cases where a simple size update is not possible and you need some kind of CFG traversal (sometimes a full region's traversal, such as in this code). For example, when you wrap part of a CFG with a region, when you insert or remove part of a CFG into/from a region, etc. Since 'getSize' is only used by GraphTraits and it's not a highly used interface, I though it could be cleaner to just compute the size when needed instead of trying to store and maintain it. However, if you think this is an overkill, we could give it a try to the latter approach.

[dcaballe]

Rebasing this patch on top of D49032.

[fhahn]

lib/Transforms/Vectorize/VPlan.cpp

198 ↗

(On Diff #153666)

It looks like is is not used for building a dominator tree. Maybe we should only add once it's needed?

Storing the size and updating it in the transformations would be better IMO and with an assertion here that checks the stored size matches the computed size it should be easy to track down cases where it is not updated properly.

592 ↗

(On Diff #155230)

Use VPDominatorTree defined in VPlanDominatorTree.h?

lib/Transforms/Vectorize/VPlan.h

1319 ↗

(On Diff #155230)

The only difference to the non-const VPRegionBlock* is the type parameter, right? It's not a lot of code, but would it make sense to add a templated implementation which we then can instantiate with both <VPRegionBlock*> and <const VPRegionBlock*>?

1340 ↗

(On Diff #155230)

If we implement GraphTraits<const VPRegionBlock*>, should we also implement to const variant here?

lib/Transforms/Vectorize/VPlanDominatorTree.h

27 ↗

(On Diff #155230)

can we just use using VPDominatorTree = DomTreeBase<VPBlockBase>; here?

34 ↗

(On Diff #155230)

same as for VPDominatorTree

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

59 ↗

(On Diff #155230)

I am wondering if we could use a mapping from IR BBs to VPBBs and just match if the DT and VPDT agree on all cases. So instead testing everything manually, we rely on the DT to be correct.

[dcaballe]

Thanks for the comments, Florian! Addressing your comments.

[dcaballe]

lib/Transforms/Vectorize/VPlan.cpp

198 ↗

(On Diff #153666)

It looks like is is not used for building a dominator tree. Maybe we should only add once it's needed?

Weird... now I can't find the patch that needed this code. Hopefully, this code is no longer needed!

Storing the size and updating it in the transformations would be better IMO and with an assertion here that checks the stored size matches the computed size it should be easy to track down cases where it is not updated properly.

OK. if needed, let's try but I would leave the assertion for VPlanVerifier. We may want to incrementally update the size even when the region is inconsistent (e.g., region's entry and exit are not reachable from each other). We may also need a 'recomputeSize' for those cases where we cannot do an incremental update and a full recomputation is needed.

592 ↗

(On Diff #155230)

OK. However, this only compiles if VPlanDominatorTree is a typedef. If VPDominatorTree turns into a derived class in the future, this won't compile (trying to use a protected class member). Hopefully, it will be easy to deduce that the error is coming from here.

lib/Transforms/Vectorize/VPlan.h

1319 ↗

(On Diff #155230)

Well, lines 1299 and 1329 are explicit template specializations. I found this way to do it by using an extra level of inheritance but I'm not sure if the proposed solutions is worth the complexity. Deciphering an error message on these classes could be more challenging that desired :)

1340 ↗

(On Diff #155230)

We are introducing GraphTraits on demand and the const variant of Inverse<VPRegionBlock*> doesn't seem to be needed at this point. Same happens for Inverse<VPBasicBlock *>

lib/Transforms/Vectorize/VPlanDominatorTree.h

27 ↗

(On Diff #155230)

Ok, we can turn it into a class when specific extensions are needed.

34 ↗

(On Diff #155230)

Sorry, I'll remove VPPostDominatorTree since it's not being used currently.

lib/Transforms/Vectorize/VPlanHCFGBuilder.h

64 ↗

(On Diff #155230)

I'm not too happy with making this interface public just for unittesting. Are there any examples of unittest for private member functions? Could friendship be applied here in a clean way?

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

59 ↗

(On Diff #155230)

Let me think about it but I'm not sure. Wouldn't that hide bugs in the main algorithm that could be caught otherwise here?

[fhahn]

lib/Transforms/Vectorize/VPlan.h

1319 ↗

(On Diff #155230)

Thanks, I think either way is fine and I suppose simpler error messages trump the slightly more compact code :)

1340 ↗

(On Diff #155230)

Sounds good to me!

lib/Transforms/Vectorize/VPlanHCFGBuilder.h

64 ↗

(On Diff #155230)

A friend class could work, if a forward declaration is enough (I don't think we want to include the unit test file here). googletest also ships a FRIEND_TEST macro (https://github.com/google/googletest/blob/master/googletest/include/gtest/gtest_prod.h) and from that I think the name of the friend class should have the following format: `
#define FRIEND_TEST(test_case_name, test_name)\
friend class test_case_name_test_name##_Test`

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

59 ↗

(On Diff #155230)

I don't think it's worth spending too much time on that, I just thought it might be a slightly more compact way to write the checks (DTs are widely used and *heavily* tested :))

[dcaballe]

lib/Transforms/Vectorize/VPlan.h

1319 ↗

(On Diff #155230)

Ok, I'll revert it then.

lib/Transforms/Vectorize/VPlanHCFGBuilder.h

64 ↗

(On Diff #155230)

Thanks a lot. I thought the friendship would be more problematic. Done!

unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

59 ↗

(On Diff #155230)

Ok, let's go with this. More than an exhaustive testing of VPDT, what I want to test here is the new GraphTraits code and this should be enough for that.

[dcaballe]

Reverting GraphTraits changes and adding VPlanTestBase as friend of VPlanHCFGBuilder.

[fhahn]

LGTM, thanks! Please hold off committing a few days, in case other people have additional comments.

lib/Transforms/Vectorize/LoopVectorize.cpp

7062 ↗

(On Diff #156007)

nit: Just *Plan should be enough.

unittests/Transforms/Vectorize/VPlanTestBase.h

54 ↗

(On Diff #156007)

nit: just *Plan should work

65 ↗

(On Diff #156007)

nit: just *Plan

[dcaballe]

Thanks, Florian! I'll go ahead with the commit!

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // the vectorization pipeline.
   assert(!OrigLoop->empty());
   assert(EnableVPlanNativePath && "VPlan-native path is not enabled.");
 
   // Create new empty VPlan
   auto Plan = llvm::make_unique<VPlan>();
 
   // Build hierarchical CFG
-  VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI);
-  HCFGBuilder.buildHierarchicalCFG(*Plan.get());
+  VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI, *Plan);
+  HCFGBuilder.buildHierarchicalCFG();
 
   return Plan;
 }
 
 Value* LoopVectorizationPlanner::VPCallbackILV::
 getOrCreateVectorValues(Value *V, unsigned Part) {
       return ILV.getOrCreateVectorValue(V, Part);
 }

llvm/trunk/lib/Transforms/Vectorize/VPlan.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
 
 #include "VPlanValue.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
public:
   }
 
   /// The method which generates the output IR that correspond to this
   /// VPBlockBase, thereby "executing" the VPlan.
   virtual void execute(struct VPTransformState *State) = 0;
 
   /// Delete all blocks reachable from a given VPBlockBase, inclusive.
   static void deleteCFG(VPBlockBase *Entry);
+
+  void printAsOperand(raw_ostream &OS, bool PrintType) const {
+    OS << getName();
+  }
+
+  void print(raw_ostream &OS) const {
+    // TODO: Only printing VPBB name for now since we only have dot printing
+    // support for VPInstructions/Recipes.
+    printAsOperand(OS, false);
+  }
 };
 
 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
 /// instructions.
 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
   friend VPBasicBlock;
 
 private:
public:
   /// EntryBlock must have no predecessors.
   void setEntry(VPBlockBase *EntryBlock) {
     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 *getExit() const { return Exit; }
   VPBlockBase *getExit() { return Exit; }
 
   /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p
   /// ExitBlock must have no successors.
   void setExit(VPBlockBase *ExitBlock) {
     assert(ExitBlock->getSuccessors().empty() &&
            "Exit block cannot have successors.");

 }
 
 inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan) {
   VPlanPrinter Printer(OS, Plan);
   Printer.dump();
   return OS;
 }
 
-//===--------------------------------------------------------------------===//
-// GraphTraits specializations for VPlan/VPRegionBlock Control-Flow Graphs  //
-//===--------------------------------------------------------------------===//
+//===----------------------------------------------------------------------===//
+// GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs     //
+//===----------------------------------------------------------------------===//
 
-// Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
-// graph of VPBlockBase nodes...
+// 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) {
static inline ChildIteratorType child_begin(NodeRef N) {
     return N->getSuccessors().begin();
   }
 
   static inline ChildIteratorType child_end(NodeRef N) {
     return N->getSuccessors().end();
   }
 };
 
-// Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
-// graph of VPBlockBase nodes... and to walk it in inverse order. Inverse order
-// for a VPBlockBase is considered to be when traversing the predecessors of a
-// VPBlockBase instead of its successors.
+// 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 Inverse<VPBlockBase *> getEntryNode(Inverse<VPBlockBase *> B) {
-    return B;
-  }
+  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->getExit();
+  }
+
+  static nodes_iterator nodes_begin(GraphRef N) {
+    return nodes_iterator::begin(N->getExit());
+  }
+
+  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);
+  }
+};
+
 //===----------------------------------------------------------------------===//
 // VPlan Utilities
 //===----------------------------------------------------------------------===//
 
 /// Class that provides utilities for VPBlockBases in VPlan.
 class VPBlockUtils {
 public:
   VPBlockUtils() = delete;

llvm/trunk/lib/Transforms/Vectorize/VPlan.cpp

 /// before generating LLVM-IR.
 /// The vectorizer uses vectorization plans to estimate the costs of potential
 /// candidates and if profitable to execute the desired plan, generating vector
 /// LLVM-IR code.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "VPlan.h"
+#include "VPlanDominatorTree.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
-#include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/GenericDomTreeConstruction.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include <cassert>
 #include <iterator>
 #include <string>
 #include <vector>
 
void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
                                            const Twine &Indent) const {
   O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
   if (User) {
     O << ", ";
     User->getOperand(0)->printAsOperand(O);
   }
   O << "\\l\"";
 }
+
+template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);

llvm/trunk/lib/Transforms/Vectorize/VPlanDominatorTree.h

+//===-- VPlanDominatorTree.h ------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file implements dominator tree analysis for a single level of a VPlan's
+/// H-CFG.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
+#define LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
+
+#include "VPlan.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/IR/Dominators.h"
+
+namespace llvm {
+
+/// Template specialization of the standard LLVM dominator tree utility for
+/// VPBlockBases.
+using VPDominatorTree = DomTreeBase<VPBlockBase>;
+
+using VPDomTreeNode = DomTreeNodeBase<VPBlockBase>;
+
+/// Template specializations of GraphTraits for VPDomTreeNode.
+template <>
+struct GraphTraits<VPDomTreeNode *>
+    : public DomTreeGraphTraitsBase<VPDomTreeNode, VPDomTreeNode::iterator> {};
+
+template <>
+struct GraphTraits<const VPDomTreeNode *>
+    : public DomTreeGraphTraitsBase<const VPDomTreeNode,
+                                    VPDomTreeNode::const_iterator> {};
+} // namespace llvm
+#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H

llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGBuilder.h

 /// reduction epilogue).
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_VPLANHCFGBUILDER_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VPLANHCFGBUILDER_H
 
 #include "VPlan.h"
+#include "VPlanDominatorTree.h"
 #include "VPlanVerifier.h"
 
 namespace llvm {
 
 class Loop;
+class VPlanTestBase;
 
 /// Main class to build the VPlan H-CFG for an incoming IR.
 class VPlanHCFGBuilder {
+  friend VPlanTestBase;
+
 private:
   // The outermost loop of the input loop nest considered for vectorization.
   Loop *TheLoop;
 
   // Loop Info analysis.
   LoopInfo *LI;
 
+  // The VPlan that will contain the H-CFG we are building.
+  VPlan &Plan;
+
   // 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();
+
 public:
-  VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI) : TheLoop(Lp), LI(LI) {}
+  VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
+      : TheLoop(Lp), LI(LI), Plan(P) {}
 
-  /// Build H-CFG for TheLoop and update \p Plan accordingly.
-  void buildHierarchicalCFG(VPlan &Plan);
+  /// Build H-CFG for TheLoop and update Plan accordingly.
+  void buildHierarchicalCFG();
 };
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VPLANHCFGBUILDER_H

llvm/trunk/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
 
   // 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;
 }
 
+VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() {
+  PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
+  return PCFGBuilder.buildPlainCFG();
+}
+
 // Public interface to build a H-CFG.
-void VPlanHCFGBuilder::buildHierarchicalCFG(VPlan &Plan) {
+void VPlanHCFGBuilder::buildHierarchicalCFG() {
   // Build Top Region enclosing the plain CFG and set it as VPlan entry.
-  PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
-  VPRegionBlock *TopRegion = PCFGBuilder.buildPlainCFG();
+  VPRegionBlock *TopRegion = buildPlainCFG();
   Plan.setEntry(TopRegion);
   LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
 
   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/trunk/unittests/Transforms/Vectorize/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   Core
   Vectorize
   AsmParser
   )
 
 add_llvm_unittest(VectorizeTests
+  VPlanDominatorTreeTest.cpp
   VPlanTest.cpp
   VPlanHCFGTest.cpp
   )

llvm/trunk/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

+//===- llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../lib/Transforms/Vectorize/VPlanHCFGBuilder.h"
+#include "VPlanTestBase.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+class VPlanDominatorTreeTest : public VPlanTestBase {};
+
+TEST_F(VPlanDominatorTreeTest, BasicVPBBDomination) {
+  const char *ModuleString =
+      "define void @f(i32* %a, i32* %b, i32* %c, i32 %N, i32 %M, i32 %K) {\n"
+      "entry:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.inc ]\n"
+      "  br i1 true, label %if.then, label %if.else\n"
+      "if.then:\n"
+      "  br label %for.inc\n"
+      "if.else:\n"
+      "  br label %for.inc\n"
+      "for.inc:\n"
+      "  %iv.next = add nuw nsw i64 %iv, 1\n"
+      "  %exitcond = icmp eq i64 %iv.next, 300\n"
+      "  br i1 %exitcond, label %for.end, label %for.body\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n";
+
+  Module &M = parseModule(ModuleString);
+
+  Function *F = M.getFunction("f");
+  BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
+  auto Plan = buildPlainCFG(LoopHeader);
+
+  // Build VPlan domination tree analysis.
+  VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
+  VPDominatorTree VPDT;
+  VPDT.recalculate(*TopRegion);
+
+  VPBlockBase *PH = TopRegion->getEntry();
+  VPBlockBase *H = PH->getSingleSuccessor();
+  VPBlockBase *IfThen = H->getSuccessors()[0];
+  VPBlockBase *IfElse = H->getSuccessors()[1];
+  VPBlockBase *Latch = IfThen->getSingleSuccessor();
+  VPBlockBase *Exit = Latch->getSuccessors()[0] != H
+                          ? Latch->getSuccessors()[0]
+                          : Latch->getSuccessors()[1];
+  // Reachability.
+  EXPECT_TRUE(VPDT.isReachableFromEntry(PH));
+  EXPECT_TRUE(VPDT.isReachableFromEntry(H));
+  EXPECT_TRUE(VPDT.isReachableFromEntry(IfThen));
+  EXPECT_TRUE(VPDT.isReachableFromEntry(IfElse));
+  EXPECT_TRUE(VPDT.isReachableFromEntry(Latch));
+  EXPECT_TRUE(VPDT.isReachableFromEntry(Exit));
+
+  // VPBB dominance.
+  EXPECT_TRUE(VPDT.dominates(PH, PH));
+  EXPECT_TRUE(VPDT.dominates(PH, H));
+  EXPECT_TRUE(VPDT.dominates(PH, IfThen));
+  EXPECT_TRUE(VPDT.dominates(PH, IfElse));
+  EXPECT_TRUE(VPDT.dominates(PH, Latch));
+  EXPECT_TRUE(VPDT.dominates(PH, Exit));
+
+  EXPECT_FALSE(VPDT.dominates(H, PH));
+  EXPECT_TRUE(VPDT.dominates(H, H));
+  EXPECT_TRUE(VPDT.dominates(H, IfThen));
+  EXPECT_TRUE(VPDT.dominates(H, IfElse));
+  EXPECT_TRUE(VPDT.dominates(H, Latch));
+  EXPECT_TRUE(VPDT.dominates(H, Exit));
+
+  EXPECT_FALSE(VPDT.dominates(IfThen, PH));
+  EXPECT_FALSE(VPDT.dominates(IfThen, H));
+  EXPECT_TRUE(VPDT.dominates(IfThen, IfThen));
+  EXPECT_FALSE(VPDT.dominates(IfThen, IfElse));
+  EXPECT_FALSE(VPDT.dominates(IfThen, Latch));
+  EXPECT_FALSE(VPDT.dominates(IfThen, Exit));
+
+  EXPECT_FALSE(VPDT.dominates(IfElse, PH));
+  EXPECT_FALSE(VPDT.dominates(IfElse, H));
+  EXPECT_FALSE(VPDT.dominates(IfElse, IfThen));
+  EXPECT_TRUE(VPDT.dominates(IfElse, IfElse));
+  EXPECT_FALSE(VPDT.dominates(IfElse, Latch));
+  EXPECT_FALSE(VPDT.dominates(IfElse, Exit));
+
+  EXPECT_FALSE(VPDT.dominates(Latch, PH));
+  EXPECT_FALSE(VPDT.dominates(Latch, H));
+  EXPECT_FALSE(VPDT.dominates(Latch, IfThen));
+  EXPECT_FALSE(VPDT.dominates(Latch, IfElse));
+  EXPECT_TRUE(VPDT.dominates(Latch, Latch));
+  EXPECT_TRUE(VPDT.dominates(Latch, Exit));
+
+  EXPECT_FALSE(VPDT.dominates(Exit, PH));
+  EXPECT_FALSE(VPDT.dominates(Exit, H));
+  EXPECT_FALSE(VPDT.dominates(Exit, IfThen));
+  EXPECT_FALSE(VPDT.dominates(Exit, IfElse));
+  EXPECT_FALSE(VPDT.dominates(Exit, Latch));
+  EXPECT_TRUE(VPDT.dominates(Exit, Exit));
+
+  // VPBB proper dominance.
+  EXPECT_FALSE(VPDT.properlyDominates(PH, PH));
+  EXPECT_TRUE(VPDT.properlyDominates(PH, H));
+  EXPECT_TRUE(VPDT.properlyDominates(PH, IfThen));
+  EXPECT_TRUE(VPDT.properlyDominates(PH, IfElse));
+  EXPECT_TRUE(VPDT.properlyDominates(PH, Latch));
+  EXPECT_TRUE(VPDT.properlyDominates(PH, Exit));
+
+  EXPECT_FALSE(VPDT.properlyDominates(H, PH));
+  EXPECT_FALSE(VPDT.properlyDominates(H, H));
+  EXPECT_TRUE(VPDT.properlyDominates(H, IfThen));
+  EXPECT_TRUE(VPDT.properlyDominates(H, IfElse));
+  EXPECT_TRUE(VPDT.properlyDominates(H, Latch));
+  EXPECT_TRUE(VPDT.properlyDominates(H, Exit));
+
+  EXPECT_FALSE(VPDT.properlyDominates(IfThen, PH));
+  EXPECT_FALSE(VPDT.properlyDominates(IfThen, H));
+  EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfThen));
+  EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfElse));
+  EXPECT_FALSE(VPDT.properlyDominates(IfThen, Latch));
+  EXPECT_FALSE(VPDT.properlyDominates(IfThen, Exit));
+
+  EXPECT_FALSE(VPDT.properlyDominates(IfElse, PH));
+  EXPECT_FALSE(VPDT.properlyDominates(IfElse, H));
+  EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfThen));
+  EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfElse));
+  EXPECT_FALSE(VPDT.properlyDominates(IfElse, Latch));
+  EXPECT_FALSE(VPDT.properlyDominates(IfElse, Exit));
+
+  EXPECT_FALSE(VPDT.properlyDominates(Latch, PH));
+  EXPECT_FALSE(VPDT.properlyDominates(Latch, H));
+  EXPECT_FALSE(VPDT.properlyDominates(Latch, IfThen));
+  EXPECT_FALSE(VPDT.properlyDominates(Latch, IfElse));
+  EXPECT_FALSE(VPDT.properlyDominates(Latch, Latch));
+  EXPECT_TRUE(VPDT.properlyDominates(Latch, Exit));
+
+  EXPECT_FALSE(VPDT.properlyDominates(Exit, PH));
+  EXPECT_FALSE(VPDT.properlyDominates(Exit, H));
+  EXPECT_FALSE(VPDT.properlyDominates(Exit, IfThen));
+  EXPECT_FALSE(VPDT.properlyDominates(Exit, IfElse));
+  EXPECT_FALSE(VPDT.properlyDominates(Exit, Latch));
+  EXPECT_FALSE(VPDT.properlyDominates(Exit, Exit));
+
+  // VPBB nearest common dominator.
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, PH));
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, H));
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfThen));
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfElse));
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Latch));
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Exit));
+
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(H, PH));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, H));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfThen));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfElse));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Latch));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Exit));
+
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfThen, PH));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, H));
+  EXPECT_EQ(IfThen, VPDT.findNearestCommonDominator(IfThen, IfThen));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, IfElse));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Latch));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Exit));
+
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfElse, PH));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, H));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, IfThen));
+  EXPECT_EQ(IfElse, VPDT.findNearestCommonDominator(IfElse, IfElse));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Latch));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Exit));
+
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Latch, PH));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, H));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfThen));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfElse));
+  EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Latch));
+  EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Exit));
+
+  EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Exit, PH));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, H));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfThen));
+  EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfElse));
+  EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Exit, Latch));
+  EXPECT_EQ(Exit, VPDT.findNearestCommonDominator(Exit, Exit));
+}
+} // namespace
+} // namespace llvm

llvm/trunk/unittests/Transforms/Vectorize/VPlanTestBase.h

void doAnalysis(Function &F) {
     DT.reset(new DominatorTree(F));
     LI.reset(new LoopInfo(*DT));
   }
 
   VPlanPtr buildHCFG(BasicBlock *LoopHeader) {
     doAnalysis(*LoopHeader->getParent());
 
     auto Plan = llvm::make_unique<VPlan>();
-    VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get());
-    HCFGBuilder.buildHierarchicalCFG(*Plan.get());
+    VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get(), *Plan);
+    HCFGBuilder.buildHierarchicalCFG();
+    return Plan;
+  }
+
+  /// Build the VPlan plain CFG for the loop starting from \p LoopHeader.
+  VPlanPtr buildPlainCFG(BasicBlock *LoopHeader) {
+    doAnalysis(*LoopHeader->getParent());
+
+    auto Plan = llvm::make_unique<VPlan>();
+    VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get(), *Plan);
+    VPRegionBlock *TopRegion = HCFGBuilder.buildPlainCFG();
+    Plan->setEntry(TopRegion);
     return Plan;
   }
 };
 
 } // namespace llvm
 
 #endif // LLVM_UNITTESTS_TRANSFORMS_VECTORIZE_VPLANTESTBASE_H