include/llvm/Analysis/RegionIterator.h

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