Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -7059,8 +7059,8 @@ auto Plan = llvm::make_unique(); // Build hierarchical CFG - VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI); - HCFGBuilder.buildHierarchicalCFG(*Plan.get()); + VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI, *Plan.get()); + HCFGBuilder.buildHierarchicalCFG(); return Plan; } Index: lib/Transforms/Vectorize/VPlan.h =================================================================== --- lib/Transforms/Vectorize/VPlan.h +++ lib/Transforms/Vectorize/VPlan.h @@ -28,6 +28,7 @@ #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" @@ -516,6 +517,16 @@ /// 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 @@ -1037,6 +1048,12 @@ 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; } @@ -1049,6 +1066,10 @@ ExitBlock->setParent(this); } + /// Return the number of VPBlockBases immediately nested in this region (i.e., + /// not including VPBlockBases from nested VPRegionBlocks). + unsigned getSize() const; + /// An indicator whether this region is to generate multiple replicated /// instances of output IR corresponding to its VPBlockBases. bool isReplicator() const { return IsReplicator; } @@ -1210,12 +1231,15 @@ 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 { using NodeRef = VPBlockBase *; @@ -1247,17 +1271,13 @@ } }; -// 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> { using NodeRef = VPBlockBase *; using ChildIteratorType = SmallVectorImpl::iterator; - static Inverse getEntryNode(Inverse B) { - return B; - } + static NodeRef getEntryNode(Inverse B) { return B.Graph; } static inline ChildIteratorType child_begin(NodeRef N) { return N->getPredecessors().begin(); @@ -1268,6 +1288,77 @@ } }; +// 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 : public GraphTraits { + using GraphRef = VPRegionBlock *; + using nodes_iterator = df_iterator; + + 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); + } + + static unsigned size(GraphRef N) { return N->getSize(); } +}; + +template <> +struct GraphTraits + : public GraphTraits { + using GraphRef = const VPRegionBlock *; + using nodes_iterator = df_iterator; + + 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); + } + + static unsigned size(GraphRef N) { return N->getSize(); } +}; + +template <> +struct GraphTraits> + : public GraphTraits> { + using GraphRef = VPRegionBlock *; + using nodes_iterator = df_iterator; + + static NodeRef getEntryNode(Inverse 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); + } + + static unsigned size(GraphRef N) { return N->getSize(); } +}; + //===----------------------------------------------------------------------===// // VPlan Utilities //===----------------------------------------------------------------------===// Index: lib/Transforms/Vectorize/VPlan.cpp =================================================================== --- lib/Transforms/Vectorize/VPlan.cpp +++ lib/Transforms/Vectorize/VPlan.cpp @@ -18,6 +18,7 @@ //===----------------------------------------------------------------------===// #include "VPlan.h" +#include "VPlanDominatorTree.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallVector.h" @@ -25,7 +26,6 @@ #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" @@ -34,6 +34,7 @@ #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" @@ -187,6 +188,16 @@ LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB); } +unsigned VPRegionBlock::getSize() const { + // This function is needed by GraphTraits for VPRegionBlock. Ideally, we + // should store the size and update it consistently instead of recomputing it + // every time. However, given the multiple ways of adding/removing a + // VPBlockBase from the H-CFG, it would be very easy to end up with a wrong + // size. + return std::distance(df_iterator::begin(Entry), + df_iterator::end(Exit)); +} + void VPRegionBlock::execute(VPTransformState *State) { ReversePostOrderTraversal RPOT(Entry); @@ -576,3 +587,6 @@ } O << "\\l\""; } + +using VPDomTree = DomTreeBase; +template void DomTreeBuilder::Calculate(VPDomTree &DT); Index: lib/Transforms/Vectorize/VPlanDominatorTree.h =================================================================== --- /dev/null +++ lib/Transforms/Vectorize/VPlanDominatorTree.h @@ -0,0 +1,51 @@ +//===-- 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. +class VPDominatorTree : public DomTreeBase { +public: + VPDominatorTree() : DomTreeBase() {} +}; + +/// Template specialization of the standard LLVM post-dominator tree utility for +/// VPBlockBases. +class VPPostDominatorTree : public PostDomTreeBase { +public: + VPPostDominatorTree() : PostDomTreeBase() {} +}; + +using VPDomTreeNode = DomTreeNodeBase; + +/// Template specializations of GraphTraits for VPDomTreeNode. +template <> +struct GraphTraits + : public DomTreeGraphTraitsBase {}; + +template <> +struct GraphTraits + : public DomTreeGraphTraitsBase {}; +} // namespace llvm +#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H Index: lib/Transforms/Vectorize/VPlanHCFGBuilder.h =================================================================== --- lib/Transforms/Vectorize/VPlanHCFGBuilder.h +++ lib/Transforms/Vectorize/VPlanHCFGBuilder.h @@ -26,6 +26,7 @@ #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VPLANHCFGBUILDER_H #include "VPlan.h" +#include "VPlanDominatorTree.h" #include "VPlanVerifier.h" namespace llvm { @@ -41,14 +42,30 @@ // 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; + public: - VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI) : TheLoop(Lp), LI(LI) {} + VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P) + : TheLoop(Lp), LI(LI), Plan(P) {} + + /// Build plain CFG for TheLoop. Return a new VPRegionBlock (TopRegion) + /// enclosing the plain CFG. + /// + /// This interface is mainly used for unittests. To build the proper VPlan + /// H-CFG, 'buildHierarchicalCFG' must be used instead. + VPRegionBlock *buildPlainCFG(); - /// 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 Index: lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp =================================================================== --- lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp +++ lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp @@ -324,13 +324,22 @@ 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())); } Index: lib/Transforms/Vectorize/VPlanVerifier.cpp =================================================================== --- lib/Transforms/Vectorize/VPlanVerifier.cpp +++ lib/Transforms/Vectorize/VPlanVerifier.cpp @@ -42,9 +42,13 @@ /// \p Region. Checks in this function are generic for VPBlockBases. They are /// not specific for VPBasicBlocks or VPRegionBlocks. static void verifyBlocksInRegion(const VPRegionBlock *Region) { + unsigned NumBlocks = 0; for (const VPBlockBase *VPB : make_range(df_iterator::begin(Region->getEntry()), df_iterator::end(Region->getExit()))) { + // Compute Region's size + ++NumBlocks; + // Check block's parent. assert(VPB->getParent() == Region && "VPBlockBase has wrong parent"); @@ -91,6 +95,8 @@ (void)PredSuccs; } } + + assert(NumBlocks == Region->getSize() && "Region size is wrong!"); } /// Verify the CFG invariants of VPRegionBlock \p Region and its nested Index: unittests/Transforms/Vectorize/CMakeLists.txt =================================================================== --- unittests/Transforms/Vectorize/CMakeLists.txt +++ unittests/Transforms/Vectorize/CMakeLists.txt @@ -6,6 +6,7 @@ ) add_llvm_unittest(VectorizeTests + VPlanDominatorTreeTest.cpp VPlanTest.cpp VPlanHCFGTest.cpp ) Index: unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp =================================================================== --- /dev/null +++ unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp @@ -0,0 +1,196 @@ +//===- 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 VPlanDominatorTree : public VPlanTestBase {}; + +TEST_F(VPlanDominatorTree, 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(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 Index: unittests/Transforms/Vectorize/VPlanTestBase.h =================================================================== --- unittests/Transforms/Vectorize/VPlanTestBase.h +++ unittests/Transforms/Vectorize/VPlanTestBase.h @@ -50,8 +50,21 @@ doAnalysis(*LoopHeader->getParent()); auto Plan = llvm::make_unique(); - VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get()); - HCFGBuilder.buildHierarchicalCFG(*Plan.get()); + VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get(), + *Plan.get()); + 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(); + VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get(), + *Plan.get()); + VPRegionBlock *TopRegion = HCFGBuilder.buildPlainCFG(); + Plan->setEntry(TopRegion); return Plan; } };