diff options
Diffstat (limited to 'include/llvm/Analysis/RegionIterator.h')
-rw-r--r-- | include/llvm/Analysis/RegionIterator.h | 119 |
1 files changed, 71 insertions, 48 deletions
diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h index ab4d0e0..0daff58 100644 --- a/include/llvm/Analysis/RegionIterator.h +++ b/include/llvm/Analysis/RegionIterator.h @@ -30,13 +30,16 @@ namespace llvm { /// /// For a subregion RegionNode there is just one successor. The RegionNode /// representing the exit of the subregion. -template<class NodeType> +template<class NodeType, class BlockT, class RegionT> class RNSuccIterator : public std::iterator<std::forward_iterator_tag, - NodeType, ptrdiff_t> -{ + NodeType, ptrdiff_t> { typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; + + typedef GraphTraits<BlockT*> BlockTraits; + typedef typename BlockTraits::ChildIteratorType SuccIterTy; + // The iterator works in two modes, bb mode or region mode. - enum ItMode{ + enum ItMode { // In BB mode it returns all successors of this BasicBlock as its // successors. ItBB, @@ -47,10 +50,10 @@ class RNSuccIterator : public std::iterator<std::forward_iterator_tag, }; // Use two bit to represent the mode iterator. - PointerIntPair<NodeType*, 2, enum ItMode> Node; + PointerIntPair<NodeType*, 2, ItMode> Node; // The block successor iterator. - succ_iterator BItor; + SuccIterTy BItor; // advanceRegionSucc - A region node has only one successor. It reaches end // once we advance it. @@ -66,37 +69,36 @@ class RNSuccIterator : public std::iterator<std::forward_iterator_tag, // Get the immediate successor. This function may return a Basic Block // RegionNode or a subregion RegionNode. - RegionNode* getISucc(BasicBlock* BB) const { - RegionNode *succ; + NodeType* getISucc(BlockT* BB) const { + NodeType *succ; succ = getNode()->getParent()->getNode(BB); assert(succ && "BB not in Region or entered subregion!"); return succ; } // getRegionSucc - Return the successor basic block of a SubRegion RegionNode. - inline BasicBlock* getRegionSucc() const { + inline BlockT* getRegionSucc() const { assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); - return getNode()->template getNodeAs<Region>()->getExit(); + return getNode()->template getNodeAs<RegionT>()->getExit(); } // isExit - Is this the exit BB of the Region? - inline bool isExit(BasicBlock* BB) const { + inline bool isExit(BlockT* BB) const { return getNode()->getParent()->getExit() == BB; } public: - typedef RNSuccIterator<NodeType> Self; + typedef RNSuccIterator<NodeType, BlockT, RegionT> Self; typedef typename super::pointer pointer; /// @brief Create begin iterator of a RegionNode. inline RNSuccIterator(NodeType* node) : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), - BItor(succ_begin(node->getEntry())) { - + BItor(BlockTraits::child_begin(node->getEntry())) { // Skip the exit block if (!isRegionMode()) - while (succ_end(node->getEntry()) != BItor && isExit(*BItor)) + while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor)) ++BItor; if (isRegionMode() && isExit(getRegionSucc())) @@ -106,7 +108,7 @@ public: /// @brief Create an end iterator. inline RNSuccIterator(NodeType* node, bool) : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), - BItor(succ_end(node->getEntry())) {} + BItor(BlockTraits::child_end(node->getEntry())) {} inline bool operator==(const Self& x) const { assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); @@ -119,7 +121,7 @@ public: inline bool operator!=(const Self& x) const { return !operator==(x); } inline pointer operator*() const { - BasicBlock* BB = isRegionMode() ? getRegionSucc() : *BItor; + BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor; assert(!isExit(BB) && "Iterator out of range!"); return getISucc(BB); } @@ -132,7 +134,7 @@ public: // Skip the exit. do ++BItor; - while (BItor != succ_end(getNode()->getEntry()) + while (BItor != BlockTraits::child_end(getNode()->getEntry()) && isExit(*BItor)); } return *this; @@ -162,36 +164,41 @@ public: /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that /// are contained in the Region and its subregions. This is close to a virtual /// control flow graph of the Region. -template<class NodeType> -class RNSuccIterator<FlatIt<NodeType> > - : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> -{ +template<class NodeType, class BlockT, class RegionT> +class RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> + : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> { typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; + typedef GraphTraits<BlockT*> BlockTraits; + typedef typename BlockTraits::ChildIteratorType SuccIterTy; + NodeType* Node; - succ_iterator Itor; + SuccIterTy Itor; public: - typedef RNSuccIterator<FlatIt<NodeType> > Self; + typedef RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> Self; typedef typename super::pointer pointer; /// @brief Create the iterator from a RegionNode. /// /// Note that the incoming node must be a bb node, otherwise it will trigger /// an assertion when we try to get a BasicBlock. - inline RNSuccIterator(NodeType* node) : Node(node), - Itor(succ_begin(node->getEntry())) { + inline RNSuccIterator(NodeType* node) : + Node(node), + Itor(BlockTraits::child_begin(node->getEntry())) { assert(!Node->isSubRegion() && "Subregion node not allowed in flat iterating mode!"); assert(Node->getParent() && "A BB node must have a parent!"); // Skip the exit block of the iterating region. - while (succ_end(Node->getEntry()) != Itor + while (BlockTraits::child_end(Node->getEntry()) != Itor && Node->getParent()->getExit() == *Itor) ++Itor; } + /// @brief Create an end iterator - inline RNSuccIterator(NodeType* node, bool) : Node(node), - Itor(succ_end(node->getEntry())) { + inline RNSuccIterator(NodeType* node, bool) : + Node(node), + Itor(BlockTraits::child_end(node->getEntry())) { assert(!Node->isSubRegion() && "Subregion node not allowed in flat iterating mode!"); } @@ -206,10 +213,10 @@ public: inline bool operator!=(const Self& x) const { return !operator==(x); } inline pointer operator*() const { - BasicBlock* BB = *Itor; + BlockT *BB = *Itor; // Get the iterating region. - Region* Parent = Node->getParent(); + RegionT *Parent = Node->getParent(); // The only case that the successor reaches out of the region is it reaches // the exit of the region. @@ -245,14 +252,14 @@ public: } }; -template<class NodeType> -inline RNSuccIterator<NodeType> succ_begin(NodeType* Node) { - return RNSuccIterator<NodeType>(Node); +template<class NodeType, class BlockT, class RegionT> +inline RNSuccIterator<NodeType, BlockT, RegionT> succ_begin(NodeType* Node) { + return RNSuccIterator<NodeType, BlockT, RegionT>(Node); } -template<class NodeType> -inline RNSuccIterator<NodeType> succ_end(NodeType* Node) { - return RNSuccIterator<NodeType>(Node, true); +template<class NodeType, class BlockT, class RegionT> +inline RNSuccIterator<NodeType, BlockT, RegionT> succ_end(NodeType* Node) { + return RNSuccIterator<NodeType, BlockT, RegionT>(Node, true); } //===--------------------------------------------------------------------===// @@ -262,27 +269,27 @@ inline RNSuccIterator<NodeType> succ_end(NodeType* Node) { // NodeT can either be region node or const region node, otherwise child_begin // and child_end fail. -#define RegionNodeGraphTraits(NodeT) \ - template<> struct GraphTraits<NodeT*> { \ +#define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \ + template<> struct GraphTraits<NodeT*> { \ typedef NodeT NodeType; \ - typedef RNSuccIterator<NodeType> ChildIteratorType; \ + typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType; \ static NodeType *getEntryNode(NodeType* N) { return N; } \ static inline ChildIteratorType child_begin(NodeType *N) { \ - return RNSuccIterator<NodeType>(N); \ + return RNSuccIterator<NodeType, BlockT, RegionT>(N); \ } \ static inline ChildIteratorType child_end(NodeType *N) { \ - return RNSuccIterator<NodeType>(N, true); \ + return RNSuccIterator<NodeType, BlockT, RegionT>(N, true); \ } \ }; \ -template<> struct GraphTraits<FlatIt<NodeT*> > { \ +template<> struct GraphTraits<FlatIt<NodeT*>> { \ typedef NodeT NodeType; \ - typedef RNSuccIterator<FlatIt<NodeT> > ChildIteratorType; \ + typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT > ChildIteratorType; \ static NodeType *getEntryNode(NodeType* N) { return N; } \ static inline ChildIteratorType child_begin(NodeType *N) { \ - return RNSuccIterator<FlatIt<NodeType> >(N); \ + return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N); \ } \ static inline ChildIteratorType child_end(NodeType *N) { \ - return RNSuccIterator<FlatIt<NodeType> >(N, true); \ + return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true); \ } \ } @@ -315,8 +322,8 @@ template<> struct GraphTraits<FlatIt<RegionT*> > \ } \ } -RegionNodeGraphTraits(RegionNode); -RegionNodeGraphTraits(const RegionNode); +RegionNodeGraphTraits(RegionNode, BasicBlock, Region); +RegionNodeGraphTraits(const RegionNode, BasicBlock, Region); RegionGraphTraits(Region, RegionNode); RegionGraphTraits(const Region, const RegionNode); @@ -337,6 +344,22 @@ template <> struct GraphTraits<RegionInfo*> } }; +template <> struct GraphTraits<RegionInfoPass*> + : public GraphTraits<RegionInfo *> { + typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, + GraphTraits<FlatIt<NodeType*> > > nodes_iterator; + + static NodeType *getEntryNode(RegionInfoPass *RI) { + return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo()); + } + static nodes_iterator nodes_begin(RegionInfoPass* RI) { + return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo()); + } + static nodes_iterator nodes_end(RegionInfoPass *RI) { + return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo()); + } +}; + } // End namespace llvm #endif |