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