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