LCOV - code coverage report
Current view: top level - include/llvm/Analysis - RegionIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 71 107 66.4 %
Date: 2018-10-20 13:21:21 Functions: 11 21 52.4 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : // This file defines the iterators to iterate over the elements of a Region.
      10             : //===----------------------------------------------------------------------===//
      11             : 
      12             : #ifndef LLVM_ANALYSIS_REGIONITERATOR_H
      13             : #define LLVM_ANALYSIS_REGIONITERATOR_H
      14             : 
      15             : #include "llvm/ADT/DepthFirstIterator.h"
      16             : #include "llvm/ADT/GraphTraits.h"
      17             : #include "llvm/ADT/PointerIntPair.h"
      18             : #include "llvm/Analysis/RegionInfo.h"
      19             : #include "llvm/IR/CFG.h"
      20             : #include <cassert>
      21             : #include <iterator>
      22             : #include <type_traits>
      23             : 
      24             : namespace llvm {
      25             : 
      26             : class BasicBlock;
      27             : 
      28             : //===----------------------------------------------------------------------===//
      29             : /// Hierarchical RegionNode successor iterator.
      30             : ///
      31             : /// This iterator iterates over all successors of a RegionNode.
      32             : ///
      33             : /// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
      34             : /// the parent Region.  Furthermore for BasicBlocks that start a subregion, a
      35             : /// RegionNode representing the subregion is returned.
      36             : ///
      37             : /// For a subregion RegionNode there is just one successor. The RegionNode
      38             : /// representing the exit of the subregion.
      39             : template <class NodeRef, class BlockT, class RegionT>
      40             : class RNSuccIterator
      41             :     : public std::iterator<std::forward_iterator_tag, NodeRef> {
      42             :   using super = std::iterator<std::forward_iterator_tag, NodeRef>;
      43             :   using BlockTraits = GraphTraits<BlockT *>;
      44             :   using SuccIterTy = typename BlockTraits::ChildIteratorType;
      45             : 
      46             :   // The iterator works in two modes, bb mode or region mode.
      47             :   enum ItMode {
      48             :     // In BB mode it returns all successors of this BasicBlock as its
      49             :     // successors.
      50             :     ItBB,
      51             :     // In region mode there is only one successor, thats the regionnode mapping
      52             :     // to the exit block of the regionnode
      53             :     ItRgBegin, // At the beginning of the regionnode successor.
      54             :     ItRgEnd    // At the end of the regionnode successor.
      55             :   };
      56             : 
      57             :   static_assert(std::is_pointer<NodeRef>::value,
      58             :                 "FIXME: Currently RNSuccIterator only supports NodeRef as "
      59             :                 "pointers due to the use of pointer-specific data structures "
      60             :                 "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
      61             :                 "it to support non-pointer types");
      62             : 
      63             :   // Use two bit to represent the mode iterator.
      64             :   PointerIntPair<NodeRef, 2, ItMode> Node;
      65             : 
      66             :   // The block successor iterator.
      67             :   SuccIterTy BItor;
      68             : 
      69             :   // advanceRegionSucc - A region node has only one successor. It reaches end
      70             :   // once we advance it.
      71             :   void advanceRegionSucc() {
      72             :     assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
      73             :     Node.setInt(ItRgEnd);
      74             :   }
      75             : 
      76      220986 :   NodeRef getNode() const { return Node.getPointer(); }
      77             : 
      78             :   // isRegionMode - Is the current iterator in region mode?
      79      218083 :   bool isRegionMode() const { return Node.getInt() != ItBB; }
      80             : 
      81             :   // Get the immediate successor. This function may return a Basic Block
      82             :   // RegionNode or a subregion RegionNode.
      83             :   NodeRef getISucc(BlockT *BB) const {
      84             :     NodeRef succ;
      85       66603 :     succ = getNode()->getParent()->getNode(BB);
      86             :     assert(succ && "BB not in Region or entered subregion!");
      87             :     return succ;
      88             :   }
      89             : 
      90             :   // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
      91             :   inline BlockT* getRegionSucc() const {
      92             :     assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
      93       12704 :     return getNode()->template getNodeAs<RegionT>()->getExit();
      94             :   }
      95             : 
      96             :   // isExit - Is this the exit BB of the Region?
      97             :   inline bool isExit(BlockT* BB) const {
      98       98425 :     return getNode()->getParent()->getExit() == BB;
      99             :   }
     100             : 
     101             : public:
     102             :   using Self = RNSuccIterator<NodeRef, BlockT, RegionT>;
     103             :   using value_type = typename super::value_type;
     104             : 
     105             :   /// Create begin iterator of a RegionNode.
     106       75756 :   inline RNSuccIterator(NodeRef node)
     107             :       : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
     108      136595 :         BItor(BlockTraits::child_begin(node->getEntry())) {
     109             :     // Skip the exit block
     110       75756 :     if (!isRegionMode())
     111       73488 :       while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
     112             :         ++BItor;
     113             : 
     114       75756 :     if (isRegionMode() && isExit(getRegionSucc()))
     115             :       advanceRegionSucc();
     116       75756 :   }
     117           8 : 
     118             :   /// Create an end iterator.
     119      142329 :   inline RNSuccIterator(NodeRef node, bool)
     120             :       : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
     121      142323 :         BItor(BlockTraits::child_end(node->getEntry())) {}
     122          10 : 
     123             :   inline bool operator==(const Self& x) const {
     124             :     assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
     125      142323 :     if (isRegionMode())
     126       55228 :       return Node.getInt() == x.Node.getInt();
     127           8 :     else
     128      114701 :       return BItor == x.BItor;
     129             :   }
     130           0 : 
     131             :   inline bool operator!=(const Self& x) const { return !operator==(x); }
     132           0 : 
     133       66599 :   inline value_type operator*() const {
     134       66599 :     BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
     135             :     assert(!isExit(BB) && "Iterator out of range!");
     136       66599 :     return getISucc(BB);
     137             :   }
     138           0 : 
     139       66599 :   inline Self& operator++() {
     140       66599 :     if(isRegionMode()) {
     141          12 :       // The Region only has 1 successor.
     142             :       advanceRegionSucc();
     143          12 :     } else {
     144          12 :       // Skip the exit.
     145             :       do
     146          12 :         ++BItor;
     147           0 :       while (BItor != BlockTraits::child_end(getNode()->getEntry())
     148       70861 :           && isExit(*BItor));
     149           0 :     }
     150       66599 :     return *this;
     151             :   }
     152             : 
     153          12 :   inline Self operator++(int) {
     154       66607 :     Self tmp = *this;
     155       66599 :     ++*this;
     156           8 :     return tmp;
     157             :   }
     158           0 : };
     159             : 
     160           0 : //===----------------------------------------------------------------------===//
     161           4 : /// Flat RegionNode iterator.
     162           4 : ///
     163           0 : /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
     164           4 : /// are contained in the Region and its subregions. This is close to a virtual
     165           0 : /// control flow graph of the Region.
     166           0 : template <class NodeRef, class BlockT, class RegionT>
     167           0 : class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
     168           0 :     : public std::iterator<std::forward_iterator_tag, NodeRef> {
     169           0 :   using super = std::iterator<std::forward_iterator_tag, NodeRef>;
     170             :   using BlockTraits = GraphTraits<BlockT *>;
     171           4 :   using SuccIterTy = typename BlockTraits::ChildIteratorType;
     172           4 : 
     173             :   NodeRef Node;
     174           4 :   SuccIterTy Itor;
     175             : 
     176             : public:
     177           4 :   using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;
     178           4 :   using value_type = typename super::value_type;
     179             : 
     180           0 :   /// Create the iterator from a RegionNode.
     181             :   ///
     182           0 :   /// Note that the incoming node must be a bb node, otherwise it will trigger
     183             :   /// an assertion when we try to get a BasicBlock.
     184          54 :   inline RNSuccIterator(NodeRef node)
     185         108 :       : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
     186           4 :     assert(!Node->isSubRegion() &&
     187             :            "Subregion node not allowed in flat iterating mode!");
     188           4 :     assert(Node->getParent() && "A BB node must have a parent!");
     189             : 
     190           0 :     // Skip the exit block of the iterating region.
     191         102 :     while (BlockTraits::child_end(Node->getEntry()) != Itor &&
     192          48 :            Node->getParent()->getExit() == *Itor)
     193           0 :       ++Itor;
     194          54 :   }
     195           0 : 
     196             :   /// Create an end iterator
     197           0 :   inline RNSuccIterator(NodeRef node, bool)
     198           0 :       : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
     199           0 :     assert(!Node->isSubRegion() &&
     200             :            "Subregion node not allowed in flat iterating mode!");
     201           0 :   }
     202             : 
     203           4 :   inline bool operator==(const Self& x) const {
     204           4 :     assert(Node->getParent() == x.Node->getParent()
     205             :            && "Cannot compare iterators of different regions!");
     206           0 : 
     207         132 :     return Itor == x.Itor && Node == x.Node;
     208           0 :   }
     209             : 
     210             :   inline bool operator!=(const Self& x) const { return !operator==(x); }
     211           0 : 
     212          84 :   inline value_type operator*() const {
     213          80 :     BlockT *BB = *Itor;
     214           4 : 
     215             :     // Get the iterating region.
     216          80 :     RegionT *Parent = Node->getParent();
     217           0 : 
     218           4 :     // The only case that the successor reaches out of the region is it reaches
     219           4 :     // the exit of the region.
     220           0 :     assert(Parent->getExit() != BB && "iterator out of range!");
     221             : 
     222          80 :     return Parent->getBBNode(BB);
     223           0 :   }
     224           0 : 
     225          60 :   inline Self& operator++() {
     226             :     // Skip the exit block of the iterating region.
     227           0 :     do
     228           0 :       ++Itor;
     229         120 :     while (Itor != succ_end(Node->getEntry())
     230          60 :         && Node->getParent()->getExit() == *Itor);
     231             : 
     232          60 :     return *this;
     233             :   }
     234             : 
     235           0 :   inline Self operator++(int) {
     236          20 :     Self tmp = *this;
     237          20 :     ++*this;
     238           0 :     return tmp;
     239             :   }
     240             : };
     241             : 
     242             : template <class NodeRef, class BlockT, class RegionT>
     243             : inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) {
     244             :   return RNSuccIterator<NodeRef, BlockT, RegionT>(Node);
     245             : }
     246             : 
     247             : template <class NodeRef, class BlockT, class RegionT>
     248             : inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
     249             :   return RNSuccIterator<NodeRef, BlockT, RegionT>(Node, true);
     250             : }
     251             : 
     252             : //===--------------------------------------------------------------------===//
     253             : // RegionNode GraphTraits specialization so the bbs in the region can be
     254             : // iterate by generic graph iterators.
     255             : //
     256             : // NodeT can either be region node or const region node, otherwise child_begin
     257             : // and child_end fail.
     258             : 
     259             : #define RegionNodeGraphTraits(NodeT, BlockT, RegionT)                          \
     260             :   template <> struct GraphTraits<NodeT *> {                                    \
     261             :     using NodeRef = NodeT *;                                                   \
     262             :     using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>;        \
     263             :     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
     264             :     static inline ChildIteratorType child_begin(NodeRef N) {                   \
     265             :       return RNSuccIterator<NodeRef, BlockT, RegionT>(N);                      \
     266             :     }                                                                          \
     267             :     static inline ChildIteratorType child_end(NodeRef N) {                     \
     268             :       return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true);                \
     269             :     }                                                                          \
     270             :   };                                                                           \
     271             :   template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
     272             :     using NodeRef = NodeT *;                                                   \
     273             :     using ChildIteratorType =                                                  \
     274             :         RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;                      \
     275             :     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
     276             :     static inline ChildIteratorType child_begin(NodeRef N) {                   \
     277             :       return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N);              \
     278             :     }                                                                          \
     279             :     static inline ChildIteratorType child_end(NodeRef N) {                     \
     280             :       return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true);        \
     281             :     }                                                                          \
     282             :   }
     283             : 
     284             : #define RegionGraphTraits(RegionT, NodeT)                                      \
     285             :   template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> {    \
     286             :     using nodes_iterator = df_iterator<NodeRef>;                               \
     287             :     static NodeRef getEntryNode(RegionT *R) {                                  \
     288             :       return R->getNode(R->getEntry());                                        \
     289             :     }                                                                          \
     290             :     static nodes_iterator nodes_begin(RegionT *R) {                            \
     291             :       return nodes_iterator::begin(getEntryNode(R));                           \
     292             :     }                                                                          \
     293             :     static nodes_iterator nodes_end(RegionT *R) {                              \
     294             :       return nodes_iterator::end(getEntryNode(R));                             \
     295             :     }                                                                          \
     296             :   };                                                                           \
     297             :   template <>                                                                  \
     298             :   struct GraphTraits<FlatIt<RegionT *>>                                        \
     299             :       : public GraphTraits<FlatIt<NodeT *>> {                                  \
     300             :     using nodes_iterator =                                                     \
     301             :         df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,          \
     302             :                     GraphTraits<FlatIt<NodeRef>>>;                             \
     303             :     static NodeRef getEntryNode(RegionT *R) {                                  \
     304             :       return R->getBBNode(R->getEntry());                                      \
     305             :     }                                                                          \
     306             :     static nodes_iterator nodes_begin(RegionT *R) {                            \
     307             :       return nodes_iterator::begin(getEntryNode(R));                           \
     308             :     }                                                                          \
     309             :     static nodes_iterator nodes_end(RegionT *R) {                              \
     310             :       return nodes_iterator::end(getEntryNode(R));                             \
     311             :     }                                                                          \
     312             :   }
     313             : 
     314      218117 : RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
     315             : RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
     316             : 
     317       39778 : RegionGraphTraits(Region, RegionNode);
     318             : RegionGraphTraits(const Region, const RegionNode);
     319             : 
     320             : template <> struct GraphTraits<RegionInfo*>
     321             :   : public GraphTraits<FlatIt<RegionNode*>> {
     322             :   using nodes_iterator =
     323             :       df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
     324             :                   GraphTraits<FlatIt<NodeRef>>>;
     325             : 
     326             :   static NodeRef getEntryNode(RegionInfo *RI) {
     327           4 :     return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
     328             :   }
     329             : 
     330             :   static nodes_iterator nodes_begin(RegionInfo* RI) {
     331             :     return nodes_iterator::begin(getEntryNode(RI));
     332             :   }
     333             : 
     334           0 :   static nodes_iterator nodes_end(RegionInfo *RI) {
     335           0 :     return nodes_iterator::end(getEntryNode(RI));
     336             :   }
     337             : };
     338             : 
     339             : template <> struct GraphTraits<RegionInfoPass*>
     340             :   : public GraphTraits<RegionInfo *> {
     341             :   using nodes_iterator =
     342             :       df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
     343             :                   GraphTraits<FlatIt<NodeRef>>>;
     344             : 
     345             :   static NodeRef getEntryNode(RegionInfoPass *RI) {
     346             :     return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
     347             :   }
     348             : 
     349             :   static nodes_iterator nodes_begin(RegionInfoPass* RI) {
     350             :     return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
     351             :   }
     352             : 
     353             :   static nodes_iterator nodes_end(RegionInfoPass *RI) {
     354             :     return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
     355             :   }
     356             : };
     357             : 
     358             : } // end namespace llvm
     359             : 
     360             : #endif // LLVM_ANALYSIS_REGIONITERATOR_H

Generated by: LCOV version 1.13