diff --git a/llvm/lib/Transforms/Vectorize/VPlanCFG.h b/llvm/lib/Transforms/Vectorize/VPlanCFG.h --- a/llvm/lib/Transforms/Vectorize/VPlanCFG.h +++ b/llvm/lib/Transforms/Vectorize/VPlanCFG.h @@ -22,126 +22,6 @@ // 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 { - using ParentPtrTy = VPRegionBlock *; - using NodeRef = VPBlockBase *; - using ChildIteratorType = SmallVectorImpl::iterator; - - static NodeRef getEntryNode(NodeRef N) { return N; } - static NodeRef getEntryNode(VPRegionBlock *R) { return R->getEntry(); } - - static inline ChildIteratorType child_begin(NodeRef N) { - return N->getSuccessors().begin(); - } - - static inline ChildIteratorType child_end(NodeRef N) { - return N->getSuccessors().end(); - } -}; - -template <> struct GraphTraits { - using NodeRef = const VPBlockBase *; - using ChildIteratorType = SmallVectorImpl::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> { - using NodeRef = VPBlockBase *; - using ChildIteratorType = SmallVectorImpl::iterator; - - static NodeRef getEntryNode(Inverse 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 : 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->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 @@ -152,7 +32,8 @@ template class VPAllSuccessorsIterator : public iterator_facade_base, - 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 @@ -179,6 +60,9 @@ } public: + /// Used by iterator_facade_base with bidirectional_iterator_tag. + using reference = BlockPtrTy; + VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0) : Block(Block), SuccessorIdx(Idx) {} VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other) @@ -214,6 +98,11 @@ return *this; } + VPAllSuccessorsIterator &operator--() { + SuccessorIdx--; + return *this; + } + VPAllSuccessorsIterator operator++(int X) { VPAllSuccessorsIterator Orig = *this; SuccessorIdx++; @@ -342,6 +231,80 @@ return depth_first(VPBlockDeepTraversalWrapper(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 { + using NodeRef = VPBlockBase *; + using ChildIteratorType = VPAllSuccessorsIterator; + + 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 { + using NodeRef = const VPBlockBase *; + using ChildIteratorType = VPAllSuccessorsIterator; + + static NodeRef getEntryNode(NodeRef N) { return N; } + + static inline ChildIteratorType child_begin(NodeRef N) { + return ChildIteratorType(N); + } + + static inline ChildIteratorType child_end(NodeRef N) { + return ChildIteratorType::end(N); + } +}; + +/// Inverse graph traits are not implemented yet. +/// TODO: Implement a version of VPBlockNonRecursiveTraversalWrapper to traverse +/// predecessors recursively through regions. +template <> struct GraphTraits> { + using NodeRef = VPBlockBase *; + using ChildIteratorType = SmallVectorImpl::iterator; + + static NodeRef getEntryNode(Inverse B) { + llvm_unreachable("not implemented"); + } + + static inline ChildIteratorType child_begin(NodeRef N) { + llvm_unreachable("not implemented"); + } + + static inline ChildIteratorType child_end(NodeRef N) { + llvm_unreachable("not implemented"); + } +}; + +template <> struct GraphTraits { + using GraphRef = VPlan *; + using NodeRef = VPBlockBase *; + 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->getEntry()); + } +}; + } // namespace llvm #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H diff --git a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h --- a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h +++ b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h @@ -19,16 +19,17 @@ #include "VPlanCFG.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/IR/Dominators.h" +#include "llvm/Support/GenericDomTree.h" namespace llvm { template <> struct DomTreeNodeTraits { using NodeType = VPBlockBase; using NodePtr = VPBlockBase *; - using ParentPtr = VPRegionBlock *; + using ParentPtr = VPlan *; static NodePtr getEntryNode(ParentPtr Parent) { return Parent->getEntry(); } - static ParentPtr getParent(VPBlockBase *B) { return B->getParent(); } + static ParentPtr getParent(NodePtr B) { return B->getPlan(); } }; /// diff --git a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp --- a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp @@ -391,7 +391,7 @@ 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())); } diff --git a/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp b/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp --- a/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp +++ b/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp @@ -38,7 +38,7 @@ VPlan Plan; Plan.setEntry(R1); VPDominatorTree VPDT; - VPDT.recalculate(*R1); + VPDT.recalculate(Plan); EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB4)); EXPECT_FALSE(VPDT.dominates(VPBB4, VPBB1)); @@ -53,5 +53,153 @@ EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB4), VPBB1); EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB4, VPBB4), VPBB4); } + +static void +checkDomChildren(VPDominatorTree &VPDT, VPBlockBase *Src, + std::initializer_list ExpectedChildren) { + SmallVector Children(VPDT.getNode(Src)->children()); + SmallVector 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