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