diff --git a/llvm/lib/Transforms/Vectorize/VPlan.h b/llvm/lib/Transforms/Vectorize/VPlan.h --- a/llvm/lib/Transforms/Vectorize/VPlan.h +++ b/llvm/lib/Transforms/Vectorize/VPlan.h @@ -448,7 +448,7 @@ using VPBlocksTy = SmallVectorImpl; - using ParentPtrTy = VPRegionBlock *; + using ParentPtrTy = VPlan *; virtual ~VPBlockBase() = default; 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,124 +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 NodeRef = VPBlockBase *; - using ChildIteratorType = SmallVectorImpl::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 { - 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 @@ -149,7 +31,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 @@ -176,6 +59,8 @@ } public: + using reference = BlockPtrTy; + VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0) : Block(Block), SuccessorIdx(Idx) {} VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other) @@ -211,6 +96,11 @@ return *this; } + VPAllSuccessorsIterator &operator--() { + SuccessorIdx--; + return *this; + } + VPAllSuccessorsIterator operator++(int X) { VPAllSuccessorsIterator Orig = *this; SuccessorIdx++; @@ -329,6 +219,77 @@ VPBlockNonRecursiveTraversalWrapper(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); + } +}; + +// 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(); + } +}; + +template <> struct GraphTraits { + using GraphRef = VPlan *; + using NodeRef = VPBlockBase *; + // using ChildIteratorType = SmallVectorImpl::iterator; + 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/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/CMakeLists.txt b/llvm/unittests/Transforms/Vectorize/CMakeLists.txt --- a/llvm/unittests/Transforms/Vectorize/CMakeLists.txt +++ b/llvm/unittests/Transforms/Vectorize/CMakeLists.txt @@ -8,6 +8,7 @@ add_llvm_unittest(VectorizeTests VPlanTest.cpp + VPDomTreeTest.cpp VPlanHCFGTest.cpp VPlanSlpTest.cpp ) diff --git a/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp b/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp @@ -0,0 +1,167 @@ +//===- llvm/unittests/Transforms/Vectorize/VPlanTest.cpp - VPlan tests ----===// +// +// +// 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 "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/Analysis/VectorUtils.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "gtest/gtest.h" +#include + +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)); + } +} + +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); + + 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(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); + } +} + +} // namespace +} // namespace llvm