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