include/llvm/Analysis/RegionIterator.h

   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