LCOV - code coverage report
Current view: top level - include/llvm/Analysis - RegionIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 56 60 93.3 %
Date: 2017-09-14 15:23:50 Functions: 11 18 61.1 %
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             : /// @brief 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       27822 :     Node.setInt(ItRgEnd);
      74             :   }
      75             : 
      76      496008 :   NodeRef getNode() const { return Node.getPointer(); }
      77             : 
      78             :   // isRegionMode - Is the current iterator in region mode?
      79      803652 :   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       65716 :     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       53750 :     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       97720 :     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             :   /// @brief Create begin iterator of a RegionNode.
     106       70876 :   inline RNSuccIterator(NodeRef node)
     107      141752 :       : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
     108      354380 :         BItor(BlockTraits::child_begin(node->getEntry())) {
     109             :     // Skip the exit block
     110       70876 :     if (!isRegionMode())
     111      392358 :       while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
     112       10962 :         ++BItor;
     113             : 
     114       98698 :     if (isRegionMode() && isExit(getRegionSucc()))
     115             :       advanceRegionSucc();
     116       70876 :   }
     117             : 
     118             :   /// @brief Create an end iterator.
     119      133942 :   inline RNSuccIterator(NodeRef node, bool)
     120      267884 :       : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
     121      669710 :         BItor(BlockTraits::child_end(node->getEntry())) {}
     122             : 
     123             :   inline bool operator==(const Self& x) const {
     124             :     assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
     125      133942 :     if (isRegionMode())
     126       77337 :       return Node.getInt() == x.Node.getInt();
     127             :     else
     128      108163 :       return BItor == x.BItor;
     129             :   }
     130             : 
     131      133942 :   inline bool operator!=(const Self& x) const { return !operator==(x); }
     132             : 
     133       63066 :   inline value_type operator*() const {
     134      138000 :     BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
     135             :     assert(!isExit(BB) && "Iterator out of range!");
     136       63066 :     return getISucc(BB);
     137             :   }
     138             : 
     139       63066 :   inline Self& operator++() {
     140       63066 :     if(isRegionMode()) {
     141             :       // The Region only has 1 successor.
     142             :       advanceRegionSucc();
     143             :     } else {
     144             :       // Skip the exit.
     145             :       do
     146      134286 :         ++BItor;
     147      268572 :       while (BItor != BlockTraits::child_end(getNode()->getEntry())
     148      102703 :           && isExit(*BItor));
     149             :     }
     150       63066 :     return *this;
     151             :   }
     152             : 
     153             :   inline Self operator++(int) {
     154       63066 :     Self tmp = *this;
     155       63066 :     ++*this;
     156             :     return tmp;
     157             :   }
     158             : };
     159             : 
     160             : //===----------------------------------------------------------------------===//
     161             : /// @brief Flat RegionNode iterator.
     162             : ///
     163             : /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
     164             : /// are contained in the Region and its subregions. This is close to a virtual
     165             : /// control flow graph of the Region.
     166             : template <class NodeRef, class BlockT, class RegionT>
     167             : class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
     168             :     : public std::iterator<std::forward_iterator_tag, NodeRef> {
     169             :   using super = std::iterator<std::forward_iterator_tag, NodeRef>;
     170             :   using BlockTraits = GraphTraits<BlockT *>;
     171             :   using SuccIterTy = typename BlockTraits::ChildIteratorType;
     172             : 
     173             :   NodeRef Node;
     174             :   SuccIterTy Itor;
     175             : 
     176             : public:
     177             :   using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;
     178             :   using value_type = typename super::value_type;
     179             : 
     180             :   /// @brief Create the iterator from a RegionNode.
     181             :   ///
     182             :   /// 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         162 :       : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
     186             :     assert(!Node->isSubRegion() &&
     187             :            "Subregion node not allowed in flat iterating mode!");
     188             :     assert(Node->getParent() && "A BB node must have a parent!");
     189             : 
     190             :     // Skip the exit block of the iterating region.
     191         264 :     while (BlockTraits::child_end(Node->getEntry()) != Itor &&
     192          48 :            Node->getParent()->getExit() == *Itor)
     193           0 :       ++Itor;
     194          54 :   }
     195             : 
     196             :   /// @brief Create an end iterator
     197             :   inline RNSuccIterator(NodeRef node, bool)
     198         222 :       : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
     199             :     assert(!Node->isSubRegion() &&
     200             :            "Subregion node not allowed in flat iterating mode!");
     201             :   }
     202             : 
     203             :   inline bool operator==(const Self& x) const {
     204             :     assert(Node->getParent() == x.Node->getParent()
     205             :            && "Cannot compare iterators of different regions!");
     206             : 
     207         168 :     return Itor == x.Itor && Node == x.Node;
     208             :   }
     209             : 
     210          96 :   inline bool operator!=(const Self& x) const { return !operator==(x); }
     211             : 
     212          80 :   inline value_type operator*() const {
     213         160 :     BlockT *BB = *Itor;
     214             : 
     215             :     // Get the iterating region.
     216          80 :     RegionT *Parent = Node->getParent();
     217             : 
     218             :     // The only case that the successor reaches out of the region is it reaches
     219             :     // the exit of the region.
     220             :     assert(Parent->getExit() != BB && "iterator out of range!");
     221             : 
     222          80 :     return Parent->getBBNode(BB);
     223             :   }
     224             : 
     225          60 :   inline Self& operator++() {
     226             :     // Skip the exit block of the iterating region.
     227             :     do
     228         120 :       ++Itor;
     229         180 :     while (Itor != succ_end(Node->getEntry())
     230          72 :         && Node->getParent()->getExit() == *Itor);
     231             : 
     232          60 :     return *this;
     233             :   }
     234             : 
     235             :   inline Self operator++(int) {
     236          20 :     Self tmp = *this;
     237          20 :     ++*this;
     238             :     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      204926 : RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
     315          20 : RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
     316             : 
     317       60072 : RegionGraphTraits(Region, RegionNode);
     318          16 : 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           8 :     return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
     328             :   }
     329             : 
     330             :   static nodes_iterator nodes_begin(RegionInfo* RI) {
     331           0 :     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