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