From 2a34ac86d3ea99f6ae8ec94935436ed0b26ddc14 Mon Sep 17 00:00:00 2001 From: Diego Caballero Date: Mon, 30 Jul 2018 21:33:31 +0000 Subject: [PATCH] [VPlan] Introduce VPlan-based dominator analysis. 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). Reviewers: fhahn, rengolin, mkuper, hfinkel, mssimpso Reviewed By: fhahn Differential Revision: https://reviews.llvm.org/D48815 llvm-svn: 338310 --- llvm/lib/Transforms/Vectorize/LoopVectorize.cpp | 4 +- llvm/lib/Transforms/Vectorize/VPlan.cpp | 5 +- llvm/lib/Transforms/Vectorize/VPlan.h | 105 +++++++++-- llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h | 41 +++++ llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp | 15 +- llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h | 23 ++- llvm/unittests/Transforms/Vectorize/CMakeLists.txt | 1 + .../Vectorize/VPlanDominatorTreeTest.cpp | 196 +++++++++++++++++++++ .../unittests/Transforms/Vectorize/VPlanTestBase.h | 15 +- 9 files changed, 382 insertions(+), 23 deletions(-) create mode 100644 llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h create mode 100644 llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp index 348d1e4..859d0c9 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -7060,8 +7060,8 @@ LoopVectorizationPlanner::buildVPlan(VFRange &Range) { auto Plan = llvm::make_unique(); // Build hierarchical CFG - VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI); - HCFGBuilder.buildHierarchicalCFG(*Plan.get()); + VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI, *Plan); + HCFGBuilder.buildHierarchicalCFG(); return Plan; } diff --git a/llvm/lib/Transforms/Vectorize/VPlan.cpp b/llvm/lib/Transforms/Vectorize/VPlan.cpp index f7b07b7..0780e70 100644 --- a/llvm/lib/Transforms/Vectorize/VPlan.cpp +++ b/llvm/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" @@ -576,3 +577,5 @@ void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, } O << "\\l\""; } + +template void DomTreeBuilder::Calculate(VPDominatorTree &DT); diff --git a/llvm/lib/Transforms/Vectorize/VPlan.h b/llvm/lib/Transforms/Vectorize/VPlan.h index 866951c..193d7a9 100644 --- a/llvm/lib/Transforms/Vectorize/VPlan.h +++ b/llvm/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 @@ public: /// 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 @@ public: 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; } @@ -1210,12 +1227,15 @@ inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan) { 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 +1267,13 @@ template <> struct GraphTraits { } }; -// 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 +1284,71 @@ template <> struct GraphTraits> { } }; +// 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); + } +}; + +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); + } +}; + +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); + } +}; + //===----------------------------------------------------------------------===// // VPlan Utilities //===----------------------------------------------------------------------===// diff --git a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h new file mode 100644 index 0000000..1b81097 --- /dev/null +++ b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h @@ -0,0 +1,41 @@ +//===-- 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; + +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 diff --git a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp index 08129b7..26e112e 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp @@ -324,13 +324,22 @@ VPRegionBlock *PlainCFGBuilder::buildPlainCFG() { 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())); } diff --git a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h index c4e6984..3f11dcb 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h +++ b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h @@ -26,14 +26,18 @@ #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; @@ -41,14 +45,27 @@ private: // 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 diff --git a/llvm/unittests/Transforms/Vectorize/CMakeLists.txt b/llvm/unittests/Transforms/Vectorize/CMakeLists.txt index 4f2b8e9..e4e8fa6 100644 --- a/llvm/unittests/Transforms/Vectorize/CMakeLists.txt +++ b/llvm/unittests/Transforms/Vectorize/CMakeLists.txt @@ -6,6 +6,7 @@ set(LLVM_LINK_COMPONENTS ) add_llvm_unittest(VectorizeTests + VPlanDominatorTreeTest.cpp VPlanTest.cpp VPlanHCFGTest.cpp ) diff --git a/llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp b/llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp new file mode 100644 index 0000000..57f0739 --- /dev/null +++ b/llvm/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 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(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 diff --git a/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h b/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h index da3b39f..0fc4a9a 100644 --- a/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h +++ b/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h @@ -50,8 +50,19 @@ protected: 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); + 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); + VPRegionBlock *TopRegion = HCFGBuilder.buildPlainCFG(); + Plan->setEntry(TopRegion); return Plan; } }; -- 2.7.4