llvm/Analysis/RegionIterator.h

0001 //===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 // This file defines the iterators to iterate over the elements of a Region.
0009 //===----------------------------------------------------------------------===//
0010
0011 #ifndef LLVM_ANALYSIS_REGIONITERATOR_H
0012 #define LLVM_ANALYSIS_REGIONITERATOR_H
0013
0014 #include "llvm/ADT/DepthFirstIterator.h"
0015 #include "llvm/ADT/GraphTraits.h"
0016 #include "llvm/ADT/PointerIntPair.h"
0017 #include "llvm/Analysis/RegionInfo.h"
0018 #include <cassert>
0019 #include <iterator>
0020 #include <type_traits>
0021
0022 namespace llvm {
0023
0024 class BasicBlock;
0025 class RegionInfo;
0026
0027 //===----------------------------------------------------------------------===//
0028 /// Hierarchical RegionNode successor iterator.
0029 ///
0030 /// This iterator iterates over all successors of a RegionNode.
0031 ///
0032 /// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
0033 /// the parent Region.  Furthermore for BasicBlocks that start a subregion, a
0034 /// RegionNode representing the subregion is returned.
0035 ///
0036 /// For a subregion RegionNode there is just one successor. The RegionNode
0037 /// representing the exit of the subregion.
0038 template <class NodeRef, class BlockT, class RegionT> class RNSuccIterator {
0039 public:
0040   using iterator_category = std::forward_iterator_tag;
0041   using value_type = NodeRef;
0042   using difference_type = std::ptrdiff_t;
0043   using pointer = value_type *;
0044   using reference = value_type &;
0045
0046 private:
0047   using BlockTraits = GraphTraits<BlockT *>;
0048   using SuccIterTy = typename BlockTraits::ChildIteratorType;
0049
0050   // The iterator works in two modes, bb mode or region mode.
0051   enum ItMode {
0052     // In BB mode it returns all successors of this BasicBlock as its
0053     // successors.
0054     ItBB,
0055     // In region mode there is only one successor, thats the regionnode mapping
0056     // to the exit block of the regionnode
0057     ItRgBegin, // At the beginning of the regionnode successor.
0058     ItRgEnd    // At the end of the regionnode successor.
0059   };
0060
0061   static_assert(std::is_pointer<NodeRef>::value,
0062                 "FIXME: Currently RNSuccIterator only supports NodeRef as "
0063                 "pointers due to the use of pointer-specific data structures "
0064                 "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
0065                 "it to support non-pointer types");
0066
0067   // Use two bit to represent the mode iterator.
0068   PointerIntPair<NodeRef, 2, ItMode> Node;
0069
0070   // The block successor iterator.
0071   SuccIterTy BItor;
0072
0073   // advanceRegionSucc - A region node has only one successor. It reaches end
0074   // once we advance it.
0075   void advanceRegionSucc() {
0076     assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
0077     Node.setInt(ItRgEnd);
0078   }
0079
0080   NodeRef getNode() const { return Node.getPointer(); }
0081
0082   // isRegionMode - Is the current iterator in region mode?
0083   bool isRegionMode() const { return Node.getInt() != ItBB; }
0084
0085   // Get the immediate successor. This function may return a Basic Block
0086   // RegionNode or a subregion RegionNode.
0087   NodeRef getISucc(BlockT *BB) const {
0088     NodeRef succ;
0089     succ = getNode()->getParent()->getNode(BB);
0090     assert(succ && "BB not in Region or entered subregion!");
0091     return succ;
0092   }
0093
0094   // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
0095   inline BlockT* getRegionSucc() const {
0096     assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
0097     return getNode()->template getNodeAs<RegionT>()->getExit();
0098   }
0099
0100   // isExit - Is this the exit BB of the Region?
0101   inline bool isExit(BlockT* BB) const {
0102     return getNode()->getParent()->getExit() == BB;
0103   }
0104
0105 public:
0106   using Self = RNSuccIterator<NodeRef, BlockT, RegionT>;
0107
0108   /// Create begin iterator of a RegionNode.
0109   inline RNSuccIterator(NodeRef node)
0110       : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
0111         BItor(BlockTraits::child_begin(node->getEntry())) {
0112     // Skip the exit block
0113     if (!isRegionMode())
0114       while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
0115         ++BItor;
0116
0117     if (isRegionMode() && isExit(getRegionSucc()))
0118       advanceRegionSucc();
0119   }
0120
0121   /// Create an end iterator.
0122   inline RNSuccIterator(NodeRef node, bool)
0123       : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
0124         BItor(BlockTraits::child_end(node->getEntry())) {}
0125
0126   inline bool operator==(const Self& x) const {
0127     assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
0128     if (isRegionMode())
0129       return Node.getInt() == x.Node.getInt();
0130     else
0131       return BItor == x.BItor;
0132   }
0133
0134   inline bool operator!=(const Self& x) const { return !operator==(x); }
0135
0136   inline value_type operator*() const {
0137     BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
0138     assert(!isExit(BB) && "Iterator out of range!");
0139     return getISucc(BB);
0140   }
0141
0142   inline Self& operator++() {
0143     if(isRegionMode()) {
0144       // The Region only has 1 successor.
0145       advanceRegionSucc();
0146     } else {
0147       // Skip the exit.
0148       do
0149         ++BItor;
0150       while (BItor != BlockTraits::child_end(getNode()->getEntry())
0151           && isExit(*BItor));
0152     }
0153     return *this;
0154   }
0155
0156   inline Self operator++(int) {
0157     Self tmp = *this;
0158     ++*this;
0159     return tmp;
0160   }
0161 };
0162
0163 //===----------------------------------------------------------------------===//
0164 /// Flat RegionNode iterator.
0165 ///
0166 /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
0167 /// are contained in the Region and its subregions. This is close to a virtual
0168 /// control flow graph of the Region.
0169 template <class NodeRef, class BlockT, class RegionT>
0170 class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> {
0171   using BlockTraits = GraphTraits<BlockT *>;
0172   using SuccIterTy = typename BlockTraits::ChildIteratorType;
0173
0174   NodeRef Node;
0175   SuccIterTy Itor;
0176
0177 public:
0178   using iterator_category = std::forward_iterator_tag;
0179   using value_type = NodeRef;
0180   using difference_type = std::ptrdiff_t;
0181   using pointer = value_type *;
0182   using reference = value_type &;
0183
0184   using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;
0185
0186   /// Create the iterator from a RegionNode.
0187   ///
0188   /// Note that the incoming node must be a bb node, otherwise it will trigger
0189   /// an assertion when we try to get a BasicBlock.
0190   inline RNSuccIterator(NodeRef node)
0191       : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
0192     assert(!Node->isSubRegion() &&
0193            "Subregion node not allowed in flat iterating mode!");
0194     assert(Node->getParent() && "A BB node must have a parent!");
0195
0196     // Skip the exit block of the iterating region.
0197     while (BlockTraits::child_end(Node->getEntry()) != Itor &&
0198            Node->getParent()->getExit() == *Itor)
0199       ++Itor;
0200   }
0201
0202   /// Create an end iterator
0203   inline RNSuccIterator(NodeRef node, bool)
0204       : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
0205     assert(!Node->isSubRegion() &&
0206            "Subregion node not allowed in flat iterating mode!");
0207   }
0208
0209   inline bool operator==(const Self& x) const {
0210     assert(Node->getParent() == x.Node->getParent()
0211            && "Cannot compare iterators of different regions!");
0212
0213     return Itor == x.Itor && Node == x.Node;
0214   }
0215
0216   inline bool operator!=(const Self& x) const { return !operator==(x); }
0217
0218   inline value_type operator*() const {
0219     BlockT *BB = *Itor;
0220
0221     // Get the iterating region.
0222     RegionT *Parent = Node->getParent();
0223
0224     // The only case that the successor reaches out of the region is it reaches
0225     // the exit of the region.
0226     assert(Parent->getExit() != BB && "iterator out of range!");
0227
0228     return Parent->getBBNode(BB);
0229   }
0230
0231   inline Self& operator++() {
0232     // Skip the exit block of the iterating region.
0233     do
0234       ++Itor;
0235     while (Itor != succ_end(Node->getEntry())
0236         && Node->getParent()->getExit() == *Itor);
0237
0238     return *this;
0239   }
0240
0241   inline Self operator++(int) {
0242     Self tmp = *this;
0243     ++*this;
0244     return tmp;
0245   }
0246 };
0247
0248 template <class NodeRef, class BlockT, class RegionT>
0249 inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) {
0250   return RNSuccIterator<NodeRef, BlockT, RegionT>(Node);
0251 }
0252
0253 template <class NodeRef, class BlockT, class RegionT>
0254 inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
0255   return RNSuccIterator<NodeRef, BlockT, RegionT>(Node, true);
0256 }
0257
0258 //===--------------------------------------------------------------------===//
0259 // RegionNode GraphTraits specialization so the bbs in the region can be
0260 // iterate by generic graph iterators.
0261 //
0262 // NodeT can either be region node or const region node, otherwise child_begin
0263 // and child_end fail.
0264
0265 #define RegionNodeGraphTraits(NodeT, BlockT, RegionT)                          \
0266   template <> struct GraphTraits<NodeT *> {                                    \
0267     using NodeRef = NodeT *;                                                   \
0268     using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>;        \
0269     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
0270     static inline ChildIteratorType child_begin(NodeRef N) {                   \
0271       return RNSuccIterator<NodeRef, BlockT, RegionT>(N);                      \
0272     }                                                                          \
0273     static inline ChildIteratorType child_end(NodeRef N) {                     \
0274       return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true);                \
0275     }                                                                          \
0276   };                                                                           \
0277   template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
0278     using NodeRef = NodeT *;                                                   \
0279     using ChildIteratorType =                                                  \
0280         RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;                      \
0281     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
0282     static inline ChildIteratorType child_begin(NodeRef N) {                   \
0283       return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N);              \
0284     }                                                                          \
0285     static inline ChildIteratorType child_end(NodeRef N) {                     \
0286       return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true);        \
0287     }                                                                          \
0288   }
0289
0290 #define RegionGraphTraits(RegionT, NodeT)                                      \
0291   template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> {    \
0292     using nodes_iterator = df_iterator<NodeRef>;                               \
0293     static NodeRef getEntryNode(RegionT *R) {                                  \
0294       return R->getNode(R->getEntry());                                        \
0295     }                                                                          \
0296     static nodes_iterator nodes_begin(RegionT *R) {                            \
0297       return nodes_iterator::begin(getEntryNode(R));                           \
0298     }                                                                          \
0299     static nodes_iterator nodes_end(RegionT *R) {                              \
0300       return nodes_iterator::end(getEntryNode(R));                             \
0301     }                                                                          \
0302   };                                                                           \
0303   template <>                                                                  \
0304   struct GraphTraits<FlatIt<RegionT *>>                                        \
0305       : public GraphTraits<FlatIt<NodeT *>> {                                  \
0306     using nodes_iterator =                                                     \
0307         df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,          \
0308                     GraphTraits<FlatIt<NodeRef>>>;                             \
0309     static NodeRef getEntryNode(RegionT *R) {                                  \
0310       return R->getBBNode(R->getEntry());                                      \
0311     }                                                                          \
0312     static nodes_iterator nodes_begin(RegionT *R) {                            \
0313       return nodes_iterator::begin(getEntryNode(R));                           \
0314     }                                                                          \
0315     static nodes_iterator nodes_end(RegionT *R) {                              \
0316       return nodes_iterator::end(getEntryNode(R));                             \
0317     }                                                                          \
0318   }
0319
0320 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
0321 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
0322
0323 RegionGraphTraits(Region, RegionNode);
0324 RegionGraphTraits(const Region, const RegionNode);
0325
0326 template <> struct GraphTraits<RegionInfo*>
0327   : public GraphTraits<FlatIt<RegionNode*>> {
0328   using nodes_iterator =
0329       df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
0330                   GraphTraits<FlatIt<NodeRef>>>;
0331
0332   static NodeRef getEntryNode(RegionInfo *RI) {
0333     return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
0334   }
0335
0336   static nodes_iterator nodes_begin(RegionInfo* RI) {
0337     return nodes_iterator::begin(getEntryNode(RI));
0338   }
0339
0340   static nodes_iterator nodes_end(RegionInfo *RI) {
0341     return nodes_iterator::end(getEntryNode(RI));
0342   }
0343 };
0344
0345 template <> struct GraphTraits<RegionInfoPass*>
0346   : public GraphTraits<RegionInfo *> {
0347   using nodes_iterator =
0348       df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
0349                   GraphTraits<FlatIt<NodeRef>>>;
0350
0351   static NodeRef getEntryNode(RegionInfoPass *RI) {
0352     return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
0353   }
0354
0355   static nodes_iterator nodes_begin(RegionInfoPass* RI) {
0356     return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
0357   }
0358
0359   static nodes_iterator nodes_end(RegionInfoPass *RI) {
0360     return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
0361   }
0362 };
0363
0364 } // end namespace llvm
0365
0366 #endif // LLVM_ANALYSIS_REGIONITERATOR_H