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