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 @@ -10,14 +10,12 @@ /// This file contains the declarations of the Vectorization Plan base classes: /// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual /// VPBlockBase, together implementing a Hierarchical CFG; -/// 2. Specializations of GraphTraits that allow VPBlockBase graphs to be -/// treated as proper graphs for generic algorithms; -/// 3. Pure virtual VPRecipeBase serving as the base class for recipes contained +/// 2. Pure virtual VPRecipeBase serving as the base class for recipes contained /// within VPBasicBlocks; -/// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned +/// 3. VPInstruction, a concrete Recipe and VPUser modeling a single planned /// instruction; -/// 5. The VPlan class holding a candidate for vectorization; -/// 6. The VPlanPrinter class providing a way to print a plan in dot format; +/// 4. The VPlan class holding a candidate for vectorization; +/// 5. The VPlanPrinter class providing a way to print a plan in dot format; /// These are documented in docs/VectorizationPlan.rst. // //===----------------------------------------------------------------------===// @@ -28,7 +26,6 @@ #include "VPlanValue.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/SmallPtrSet.h" @@ -2231,258 +2228,6 @@ #endif }; -//===----------------------------------------------------------------------===// -// 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 -/// before any blocks in a successor region when doing a reverse post-order -// traversal of the graph. -template -class VPAllSuccessorsIterator - : public iterator_facade_base, - std::forward_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 - /// used for the region's entry block, and SuccessorIdx - 1 are the indices - /// for the successor array. - size_t SuccessorIdx; - - static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) { - while (Current && Current->getNumSuccessors() == 0) - Current = Current->getParent(); - return Current; - } - - /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by - /// both the const and non-const operator* implementations. - template static T1 deref(T1 Block, unsigned SuccIdx) { - if (auto *R = dyn_cast(Block)) { - if (SuccIdx == 0) - return R->getEntry(); - SuccIdx--; - } - - // For exit blocks, use the next parent region with successors. - return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx]; - } - -public: - VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0) - : Block(Block), SuccessorIdx(Idx) {} - VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other) - : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {} - - VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) { - Block = R.Block; - SuccessorIdx = R.SuccessorIdx; - return *this; - } - - static VPAllSuccessorsIterator end(BlockPtrTy Block) { - BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block); - unsigned NumSuccessors = ParentWithSuccs - ? ParentWithSuccs->getNumSuccessors() - : Block->getNumSuccessors(); - - if (auto *R = dyn_cast(Block)) - return {R, NumSuccessors + 1}; - return {Block, NumSuccessors}; - } - - bool operator==(const VPAllSuccessorsIterator &R) const { - return Block == R.Block && SuccessorIdx == R.SuccessorIdx; - } - - const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); } - - BlockPtrTy operator*() { return deref(Block, SuccessorIdx); } - - VPAllSuccessorsIterator &operator++() { - SuccessorIdx++; - return *this; - } - - VPAllSuccessorsIterator operator++(int X) { - VPAllSuccessorsIterator Orig = *this; - SuccessorIdx++; - return Orig; - } -}; - -/// Helper for GraphTraits specialization that traverses through VPRegionBlocks. -template class VPBlockRecursiveTraversalWrapper { - BlockTy Entry; - -public: - VPBlockRecursiveTraversalWrapper(BlockTy Entry) : Entry(Entry) {} - BlockTy getEntry() { return Entry; } -}; - -/// GraphTraits specialization to recursively traverse VPBlockBase nodes, -/// including traversing through VPRegionBlocks. Exit blocks of a region -/// implicitly have their parent region's successors. This ensures all blocks in -/// a region are visited before any blocks in a successor region when doing a -/// reverse post-order traversal of the graph. -template <> -struct GraphTraits> { - using NodeRef = VPBlockBase *; - using ChildIteratorType = VPAllSuccessorsIterator; - - static NodeRef - getEntryNode(VPBlockRecursiveTraversalWrapper N) { - return N.getEntry(); - } - - 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(VPBlockRecursiveTraversalWrapper N) { - return N.getEntry(); - } - - static inline ChildIteratorType child_begin(NodeRef N) { - return ChildIteratorType(N); - } - - static inline ChildIteratorType child_end(NodeRef N) { - return ChildIteratorType::end(N); - } -}; - /// VPlan models a candidate for vectorization, encoding various decisions take /// to produce efficient output IR, including which branches, basic-blocks and /// output IR instructions to generate, and their cost. VPlan holds a @@ -2541,25 +2286,7 @@ Entry->setPlan(this); } - ~VPlan() { - clearLiveOuts(); - - if (Entry) { - VPValue DummyValue; - for (VPBlockBase *Block : depth_first(Entry)) - Block->dropAllReferences(&DummyValue); - - VPBlockBase::deleteCFG(Entry); - } - for (VPValue *VPV : VPValuesToFree) - delete VPV; - if (TripCount) - delete TripCount; - if (BackedgeTakenCount) - delete BackedgeTakenCount; - for (auto &P : VPExternalDefs) - delete P.second; - } + ~VPlan(); /// Prepare the plan for execution, setting up the required live-in values. void prepareToExecute(Value *TripCount, Value *VectorTripCount, diff --git a/llvm/lib/Transforms/Vectorize/VPlan.cpp b/llvm/lib/Transforms/Vectorize/VPlan.cpp --- a/llvm/lib/Transforms/Vectorize/VPlan.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlan.cpp @@ -17,6 +17,7 @@ //===----------------------------------------------------------------------===// #include "VPlan.h" +#include "VPlanCFG.h" #include "VPlanDominatorTree.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" @@ -576,6 +577,26 @@ } #endif +VPlan::~VPlan() { + clearLiveOuts(); + + if (Entry) { + VPValue DummyValue; + for (VPBlockBase *Block : depth_first(Entry)) + Block->dropAllReferences(&DummyValue); + + VPBlockBase::deleteCFG(Entry); + } + for (VPValue *VPV : VPValuesToFree) + delete VPV; + if (TripCount) + delete TripCount; + if (BackedgeTakenCount) + delete BackedgeTakenCount; + for (auto &P : VPExternalDefs) + delete P.second; +} + VPActiveLaneMaskPHIRecipe *VPlan::getActiveLaneMaskPhi() { VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock(); for (VPRecipeBase &R : Header->phis()) { diff --git a/llvm/lib/Transforms/Vectorize/VPlanCFG.h b/llvm/lib/Transforms/Vectorize/VPlanCFG.h new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Vectorize/VPlanCFG.h @@ -0,0 +1,275 @@ +//===- VPlanCFG.h - GraphTraits for VP blocks -------------------*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// +/// Specializations of GraphTraits that allow VPBlockBase graphs to be +/// treated as proper graphs for generic algorithms; +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H +#define LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H + +#include "VPlan.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallVector.h" + +namespace llvm { + +//===----------------------------------------------------------------------===// +// 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 +/// before any blocks in a successor region when doing a reverse post-order +// traversal of the graph. +template +class VPAllSuccessorsIterator + : public iterator_facade_base, + std::forward_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 + /// used for the region's entry block, and SuccessorIdx - 1 are the indices + /// for the successor array. + size_t SuccessorIdx; + + static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) { + while (Current && Current->getNumSuccessors() == 0) + Current = Current->getParent(); + return Current; + } + + /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by + /// both the const and non-const operator* implementations. + template static T1 deref(T1 Block, unsigned SuccIdx) { + if (auto *R = dyn_cast(Block)) { + if (SuccIdx == 0) + return R->getEntry(); + SuccIdx--; + } + + // For exit blocks, use the next parent region with successors. + return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx]; + } + +public: + VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0) + : Block(Block), SuccessorIdx(Idx) {} + VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other) + : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {} + + VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) { + Block = R.Block; + SuccessorIdx = R.SuccessorIdx; + return *this; + } + + static VPAllSuccessorsIterator end(BlockPtrTy Block) { + BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block); + unsigned NumSuccessors = ParentWithSuccs + ? ParentWithSuccs->getNumSuccessors() + : Block->getNumSuccessors(); + + if (auto *R = dyn_cast(Block)) + return {R, NumSuccessors + 1}; + return {Block, NumSuccessors}; + } + + bool operator==(const VPAllSuccessorsIterator &R) const { + return Block == R.Block && SuccessorIdx == R.SuccessorIdx; + } + + const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); } + + BlockPtrTy operator*() { return deref(Block, SuccessorIdx); } + + VPAllSuccessorsIterator &operator++() { + SuccessorIdx++; + return *this; + } + + VPAllSuccessorsIterator operator++(int X) { + VPAllSuccessorsIterator Orig = *this; + SuccessorIdx++; + return Orig; + } +}; + +/// Helper for GraphTraits specialization that traverses through VPRegionBlocks. +template class VPBlockRecursiveTraversalWrapper { + BlockTy Entry; + +public: + VPBlockRecursiveTraversalWrapper(BlockTy Entry) : Entry(Entry) {} + BlockTy getEntry() { return Entry; } +}; + +/// GraphTraits specialization to recursively traverse VPBlockBase nodes, +/// including traversing through VPRegionBlocks. Exit blocks of a region +/// implicitly have their parent region's successors. This ensures all blocks in +/// a region are visited before any blocks in a successor region when doing a +/// reverse post-order traversal of the graph. +template <> +struct GraphTraits> { + using NodeRef = VPBlockBase *; + using ChildIteratorType = VPAllSuccessorsIterator; + + static NodeRef + getEntryNode(VPBlockRecursiveTraversalWrapper N) { + return N.getEntry(); + } + + 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(VPBlockRecursiveTraversalWrapper N) { + return N.getEntry(); + } + + static inline ChildIteratorType child_begin(NodeRef N) { + return ChildIteratorType(N); + } + + static inline ChildIteratorType child_end(NodeRef N) { + return ChildIteratorType::end(N); + } +}; + +} // 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 @@ -16,6 +16,7 @@ #define LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H #include "VPlan.h" +#include "VPlanCFG.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/IR/Dominators.h" diff --git a/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp b/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp --- a/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "VPlanTransforms.h" +#include "VPlanCFG.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/Analysis/IVDescriptors.h" diff --git a/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp b/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp --- a/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp @@ -14,6 +14,7 @@ #include "VPlanVerifier.h" #include "VPlan.h" +#include "VPlanCFG.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/Support/CommandLine.h" diff --git a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp --- a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp +++ b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp @@ -8,6 +8,7 @@ //===----------------------------------------------------------------------===// #include "../lib/Transforms/Vectorize/VPlan.h" +#include "../lib/Transforms/Vectorize/VPlanCFG.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Analysis/VectorUtils.h"