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