contrib/llvm/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   inline const Self &operator=(const Self &I) {
 150     if (this != &I) {
 151       assert(getNode()->getParent() == I.getNode()->getParent()
 152              && "Cannot assign iterators of two different regions!");
 153       Node = I.Node;
 154       BItor = I.BItor;
 155     }
 156     return *this;
 157   }
 158 };
 159
 160
 161 //===----------------------------------------------------------------------===//
 162 /// @brief Flat RegionNode iterator.
 163 ///
 164 /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
 165 /// are contained in the Region and its subregions. This is close to a virtual
 166 /// control flow graph of the Region.
 167 template<class NodeType, class BlockT, class RegionT>
 168 class RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>
 169   : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> {
 170   typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
 171   typedef GraphTraits<BlockT*> BlockTraits;
 172   typedef typename BlockTraits::ChildIteratorType SuccIterTy;
 173
 174   NodeType* Node;
 175   SuccIterTy Itor;
 176
 177 public:
 178   typedef RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> Self;
 179   typedef typename super::pointer pointer;
 180
 181   /// @brief Create the iterator from a RegionNode.
 182   ///
 183   /// Note that the incoming node must be a bb node, otherwise it will trigger
 184   /// an assertion when we try to get a BasicBlock.
 185   inline RNSuccIterator(NodeType* node) :
 186     Node(node),
 187     Itor(BlockTraits::child_begin(node->getEntry())) {
 188       assert(!Node->isSubRegion()
 189              && "Subregion node not allowed in flat iterating mode!");
 190       assert(Node->getParent() && "A BB node must have a parent!");
 191
 192       // Skip the exit block of the iterating region.
 193       while (BlockTraits::child_end(Node->getEntry()) != Itor
 194           && Node->getParent()->getExit() == *Itor)
 195         ++Itor;
 196   }
 197
 198   /// @brief Create an end iterator
 199   inline RNSuccIterator(NodeType* node, bool) :
 200     Node(node),
 201     Itor(BlockTraits::child_end(node->getEntry())) {
 202       assert(!Node->isSubRegion()
 203              && "Subregion node not allowed in flat iterating mode!");
 204   }
 205
 206   inline bool operator==(const Self& x) const {
 207     assert(Node->getParent() == x.Node->getParent()
 208            && "Cannot compare iterators of different regions!");
 209
 210     return Itor == x.Itor && Node == x.Node;
 211   }
 212
 213   inline bool operator!=(const Self& x) const { return !operator==(x); }
 214
 215   inline pointer operator*() const {
 216     BlockT *BB = *Itor;
 217
 218     // Get the iterating region.
 219     RegionT *Parent = Node->getParent();
 220
 221     // The only case that the successor reaches out of the region is it reaches
 222     // the exit of the region.
 223     assert(Parent->getExit() != BB && "iterator out of range!");
 224
 225     return Parent->getBBNode(BB);
 226   }
 227
 228   inline Self& operator++() {
 229     // Skip the exit block of the iterating region.
 230     do
 231       ++Itor;
 232     while (Itor != succ_end(Node->getEntry())
 233         && Node->getParent()->getExit() == *Itor);
 234
 235     return *this;
 236   }
 237
 238   inline Self operator++(int) {
 239     Self tmp = *this;
 240     ++*this;
 241     return tmp;
 242   }
 243
 244   inline const Self &operator=(const Self &I) {
 245     if (this != &I) {
 246       assert(Node->getParent() == I.Node->getParent()
 247              && "Cannot assign iterators to two different regions!");
 248       Node = I.Node;
 249       Itor = I.Itor;
 250     }
 251     return *this;
 252   }
 253 };
 254
 255 template<class NodeType, class BlockT, class RegionT>
 256 inline RNSuccIterator<NodeType, BlockT, RegionT> succ_begin(NodeType* Node) {
 257   return RNSuccIterator<NodeType, BlockT, RegionT>(Node);
 258 }
 259
 260 template<class NodeType, class BlockT, class RegionT>
 261 inline RNSuccIterator<NodeType, BlockT, RegionT> succ_end(NodeType* Node) {
 262   return RNSuccIterator<NodeType, BlockT, RegionT>(Node, true);
 263 }
 264
 265 //===--------------------------------------------------------------------===//
 266 // RegionNode GraphTraits specialization so the bbs in the region can be
 267 // iterate by generic graph iterators.
 268 //
 269 // NodeT can either be region node or const region node, otherwise child_begin
 270 // and child_end fail.
 271
 272 #define RegionNodeGraphTraits(NodeT, BlockT, RegionT)   \
 273   template<> struct GraphTraits<NodeT*> {      \
 274   typedef NodeT NodeType; \
 275   typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType;  \
 276   static NodeType *getEntryNode(NodeType* N) { return N; } \
 277   static inline ChildIteratorType child_begin(NodeType *N) { \
 278     return RNSuccIterator<NodeType, BlockT, RegionT>(N);             \
 279   } \
 280   static inline ChildIteratorType child_end(NodeType *N) { \
 281     return RNSuccIterator<NodeType, BlockT, RegionT>(N, true);     \
 282   } \
 283 }; \
 284 template<> struct GraphTraits<FlatIt<NodeT*>> {  \
 285   typedef NodeT NodeType; \
 286   typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT > ChildIteratorType;    \
 287   static NodeType *getEntryNode(NodeType* N) { return N; } \
 288   static inline ChildIteratorType child_begin(NodeType *N) { \
 289     return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N); \
 290   } \
 291   static inline ChildIteratorType child_end(NodeType *N) { \
 292     return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true); \
 293   } \
 294 }
 295
 296 #define RegionGraphTraits(RegionT, NodeT) \
 297 template<> struct GraphTraits<RegionT*> \
 298   : public GraphTraits<NodeT*> { \
 299   typedef df_iterator<NodeType*> nodes_iterator; \
 300   static NodeType *getEntryNode(RegionT* R) { \
 301     return R->getNode(R->getEntry()); \
 302   } \
 303   static nodes_iterator nodes_begin(RegionT* R) { \
 304     return nodes_iterator::begin(getEntryNode(R)); \
 305   } \
 306   static nodes_iterator nodes_end(RegionT* R) { \
 307     return nodes_iterator::end(getEntryNode(R)); \
 308   } \
 309 }; \
 310 template<> struct GraphTraits<FlatIt<RegionT*> > \
 311   : public GraphTraits<FlatIt<NodeT*> > { \
 312   typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, \
 313   GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \
 314   static NodeType *getEntryNode(RegionT* R) { \
 315     return R->getBBNode(R->getEntry()); \
 316   } \
 317   static nodes_iterator nodes_begin(RegionT* R) { \
 318     return nodes_iterator::begin(getEntryNode(R)); \
 319   } \
 320   static nodes_iterator nodes_end(RegionT* R) { \
 321     return nodes_iterator::end(getEntryNode(R)); \
 322   } \
 323 }
 324
 325 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
 326 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
 327
 328 RegionGraphTraits(Region, RegionNode);
 329 RegionGraphTraits(const Region, const RegionNode);
 330
 331 template <> struct GraphTraits<RegionInfo*>
 332   : public GraphTraits<FlatIt<RegionNode*> > {
 333   typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
 334                       GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
 335
 336   static NodeType *getEntryNode(RegionInfo *RI) {
 337     return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
 338   }
 339   static nodes_iterator nodes_begin(RegionInfo* RI) {
 340     return nodes_iterator::begin(getEntryNode(RI));
 341   }
 342   static nodes_iterator nodes_end(RegionInfo *RI) {
 343     return nodes_iterator::end(getEntryNode(RI));
 344   }
 345 };
 346
 347 template <> struct GraphTraits<RegionInfoPass*>
 348   : public GraphTraits<RegionInfo *> {
 349   typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
 350                       GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
 351
 352   static NodeType *getEntryNode(RegionInfoPass *RI) {
 353     return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
 354   }
 355   static nodes_iterator nodes_begin(RegionInfoPass* RI) {
 356     return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
 357   }
 358   static nodes_iterator nodes_end(RegionInfoPass *RI) {
 359     return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
 360   }
 361 };
 362
 363 } // End namespace llvm
 364
 365 #endif