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