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 360