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