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