1212793Sdim//===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===// 2212793Sdim// 3212793Sdim// The LLVM Compiler Infrastructure 4212793Sdim// 5212793Sdim// This file is distributed under the University of Illinois Open Source 6212793Sdim// License. See LICENSE.TXT for details. 7212793Sdim// 8212793Sdim//===----------------------------------------------------------------------===// 9212793Sdim// This file defines the iterators to iterate over the elements of a Region. 10212793Sdim//===----------------------------------------------------------------------===// 11252723Sdim#ifndef LLVM_ANALYSIS_REGIONITERATOR_H 12252723Sdim#define LLVM_ANALYSIS_REGIONITERATOR_H 13212793Sdim 14212793Sdim#include "llvm/ADT/GraphTraits.h" 15252723Sdim#include "llvm/ADT/PointerIntPair.h" 16212793Sdim#include "llvm/ADT/SmallPtrSet.h" 17212793Sdim#include "llvm/Analysis/RegionInfo.h" 18212793Sdim#include "llvm/Support/CFG.h" 19212793Sdim#include "llvm/Support/raw_ostream.h" 20212793Sdim 21212793Sdimnamespace llvm { 22212793Sdim//===----------------------------------------------------------------------===// 23221345Sdim/// @brief Hierarchical RegionNode successor iterator. 24212793Sdim/// 25212793Sdim/// This iterator iterates over all successors of a RegionNode. 26212793Sdim/// 27212793Sdim/// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of 28212793Sdim/// the parent Region. Furthermore for BasicBlocks that start a subregion, a 29212793Sdim/// RegionNode representing the subregion is returned. 30212793Sdim/// 31212793Sdim/// For a subregion RegionNode there is just one successor. The RegionNode 32212793Sdim/// representing the exit of the subregion. 33212793Sdimtemplate<class NodeType> 34212793Sdimclass RNSuccIterator : public std::iterator<std::forward_iterator_tag, 35212793Sdim NodeType, ptrdiff_t> 36212793Sdim{ 37212793Sdim typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; 38212793Sdim // The iterator works in two modes, bb mode or region mode. 39212793Sdim enum ItMode{ 40212793Sdim // In BB mode it returns all successors of this BasicBlock as its 41212793Sdim // successors. 42212793Sdim ItBB, 43212793Sdim // In region mode there is only one successor, thats the regionnode mapping 44212793Sdim // to the exit block of the regionnode 45212793Sdim ItRgBegin, // At the beginning of the regionnode successor. 46212793Sdim ItRgEnd // At the end of the regionnode successor. 47212793Sdim }; 48212793Sdim 49212793Sdim // Use two bit to represent the mode iterator. 50212793Sdim PointerIntPair<NodeType*, 2, enum ItMode> Node; 51212793Sdim 52212793Sdim // The block successor iterator. 53212793Sdim succ_iterator BItor; 54212793Sdim 55212793Sdim // advanceRegionSucc - A region node has only one successor. It reaches end 56212793Sdim // once we advance it. 57212793Sdim void advanceRegionSucc() { 58212793Sdim assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!"); 59212793Sdim Node.setInt(ItRgEnd); 60212793Sdim } 61212793Sdim 62212793Sdim NodeType* getNode() const{ return Node.getPointer(); } 63212793Sdim 64212793Sdim // isRegionMode - Is the current iterator in region mode? 65212793Sdim bool isRegionMode() const { return Node.getInt() != ItBB; } 66212793Sdim 67212793Sdim // Get the immediate successor. This function may return a Basic Block 68212793Sdim // RegionNode or a subregion RegionNode. 69212793Sdim RegionNode* getISucc(BasicBlock* BB) const { 70212793Sdim RegionNode *succ; 71212793Sdim succ = getNode()->getParent()->getNode(BB); 72212793Sdim assert(succ && "BB not in Region or entered subregion!"); 73212793Sdim return succ; 74212793Sdim } 75212793Sdim 76212793Sdim // getRegionSucc - Return the successor basic block of a SubRegion RegionNode. 77212793Sdim inline BasicBlock* getRegionSucc() const { 78212793Sdim assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); 79212793Sdim return getNode()->template getNodeAs<Region>()->getExit(); 80212793Sdim } 81212793Sdim 82212793Sdim // isExit - Is this the exit BB of the Region? 83212793Sdim inline bool isExit(BasicBlock* BB) const { 84212793Sdim return getNode()->getParent()->getExit() == BB; 85212793Sdim } 86212793Sdimpublic: 87212793Sdim typedef RNSuccIterator<NodeType> Self; 88212793Sdim 89212793Sdim typedef typename super::pointer pointer; 90212793Sdim 91212793Sdim /// @brief Create begin iterator of a RegionNode. 92212793Sdim inline RNSuccIterator(NodeType* node) 93212793Sdim : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), 94212793Sdim BItor(succ_begin(node->getEntry())) { 95212793Sdim 96212793Sdim 97212793Sdim // Skip the exit block 98212793Sdim if (!isRegionMode()) 99212793Sdim while (succ_end(node->getEntry()) != BItor && isExit(*BItor)) 100212793Sdim ++BItor; 101212793Sdim 102212793Sdim if (isRegionMode() && isExit(getRegionSucc())) 103212793Sdim advanceRegionSucc(); 104212793Sdim } 105212793Sdim 106212793Sdim /// @brief Create an end iterator. 107212793Sdim inline RNSuccIterator(NodeType* node, bool) 108212793Sdim : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), 109212793Sdim BItor(succ_end(node->getEntry())) {} 110212793Sdim 111212793Sdim inline bool operator==(const Self& x) const { 112212793Sdim assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); 113212793Sdim if (isRegionMode()) 114212793Sdim return Node.getInt() == x.Node.getInt(); 115212793Sdim else 116212793Sdim return BItor == x.BItor; 117212793Sdim } 118212793Sdim 119212793Sdim inline bool operator!=(const Self& x) const { return !operator==(x); } 120212793Sdim 121212793Sdim inline pointer operator*() const { 122212793Sdim BasicBlock* BB = isRegionMode() ? getRegionSucc() : *BItor; 123212793Sdim assert(!isExit(BB) && "Iterator out of range!"); 124212793Sdim return getISucc(BB); 125212793Sdim } 126212793Sdim 127212793Sdim inline Self& operator++() { 128212793Sdim if(isRegionMode()) { 129212793Sdim // The Region only has 1 successor. 130212793Sdim advanceRegionSucc(); 131212793Sdim } else { 132212793Sdim // Skip the exit. 133212793Sdim do 134212793Sdim ++BItor; 135212793Sdim while (BItor != succ_end(getNode()->getEntry()) 136212793Sdim && isExit(*BItor)); 137212793Sdim } 138212793Sdim return *this; 139212793Sdim } 140212793Sdim 141212793Sdim inline Self operator++(int) { 142212793Sdim Self tmp = *this; 143212793Sdim ++*this; 144212793Sdim return tmp; 145212793Sdim } 146212793Sdim 147212793Sdim inline const Self &operator=(const Self &I) { 148212793Sdim if (this != &I) { 149212793Sdim assert(getNode()->getParent() == I.getNode()->getParent() 150212793Sdim && "Cannot assign iterators of two different regions!"); 151212793Sdim Node = I.Node; 152212793Sdim BItor = I.BItor; 153212793Sdim } 154212793Sdim return *this; 155212793Sdim } 156212793Sdim}; 157212793Sdim 158212793Sdim 159212793Sdim//===----------------------------------------------------------------------===// 160212793Sdim/// @brief Flat RegionNode iterator. 161212793Sdim/// 162212793Sdim/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that 163212793Sdim/// are contained in the Region and its subregions. This is close to a virtual 164212793Sdim/// control flow graph of the Region. 165212793Sdimtemplate<class NodeType> 166212793Sdimclass RNSuccIterator<FlatIt<NodeType> > 167212793Sdim : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> 168212793Sdim{ 169212793Sdim typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; 170212793Sdim NodeType* Node; 171212793Sdim succ_iterator Itor; 172212793Sdim 173212793Sdimpublic: 174212793Sdim typedef RNSuccIterator<FlatIt<NodeType> > Self; 175212793Sdim typedef typename super::pointer pointer; 176212793Sdim 177212793Sdim /// @brief Create the iterator from a RegionNode. 178212793Sdim /// 179212793Sdim /// Note that the incoming node must be a bb node, otherwise it will trigger 180212793Sdim /// an assertion when we try to get a BasicBlock. 181212793Sdim inline RNSuccIterator(NodeType* node) : Node(node), 182212793Sdim Itor(succ_begin(node->getEntry())) { 183212793Sdim assert(!Node->isSubRegion() 184212793Sdim && "Subregion node not allowed in flat iterating mode!"); 185212793Sdim assert(Node->getParent() && "A BB node must have a parent!"); 186212793Sdim 187212793Sdim // Skip the exit block of the iterating region. 188212793Sdim while (succ_end(Node->getEntry()) != Itor 189212793Sdim && Node->getParent()->getExit() == *Itor) 190212793Sdim ++Itor; 191212793Sdim } 192212793Sdim /// @brief Create an end iterator 193212793Sdim inline RNSuccIterator(NodeType* node, bool) : Node(node), 194212793Sdim Itor(succ_end(node->getEntry())) { 195212793Sdim assert(!Node->isSubRegion() 196212793Sdim && "Subregion node not allowed in flat iterating mode!"); 197212793Sdim } 198212793Sdim 199212793Sdim inline bool operator==(const Self& x) const { 200212793Sdim assert(Node->getParent() == x.Node->getParent() 201212793Sdim && "Cannot compare iterators of different regions!"); 202212793Sdim 203212793Sdim return Itor == x.Itor && Node == x.Node; 204212793Sdim } 205212793Sdim 206212793Sdim inline bool operator!=(const Self& x) const { return !operator==(x); } 207212793Sdim 208212793Sdim inline pointer operator*() const { 209212793Sdim BasicBlock* BB = *Itor; 210212793Sdim 211212793Sdim // Get the iterating region. 212212793Sdim Region* Parent = Node->getParent(); 213212793Sdim 214212793Sdim // The only case that the successor reaches out of the region is it reaches 215212793Sdim // the exit of the region. 216212793Sdim assert(Parent->getExit() != BB && "iterator out of range!"); 217212793Sdim 218212793Sdim return Parent->getBBNode(BB); 219212793Sdim } 220212793Sdim 221212793Sdim inline Self& operator++() { 222212793Sdim // Skip the exit block of the iterating region. 223212793Sdim do 224212793Sdim ++Itor; 225212793Sdim while (Itor != succ_end(Node->getEntry()) 226212793Sdim && Node->getParent()->getExit() == *Itor); 227212793Sdim 228212793Sdim return *this; 229212793Sdim } 230212793Sdim 231212793Sdim inline Self operator++(int) { 232212793Sdim Self tmp = *this; 233212793Sdim ++*this; 234212793Sdim return tmp; 235212793Sdim } 236212793Sdim 237212793Sdim inline const Self &operator=(const Self &I) { 238212793Sdim if (this != &I) { 239212793Sdim assert(Node->getParent() == I.Node->getParent() 240212793Sdim && "Cannot assign iterators to two different regions!"); 241212793Sdim Node = I.Node; 242212793Sdim Itor = I.Itor; 243212793Sdim } 244212793Sdim return *this; 245212793Sdim } 246212793Sdim}; 247212793Sdim 248212793Sdimtemplate<class NodeType> 249212793Sdiminline RNSuccIterator<NodeType> succ_begin(NodeType* Node) { 250212793Sdim return RNSuccIterator<NodeType>(Node); 251212793Sdim} 252212793Sdim 253212793Sdimtemplate<class NodeType> 254212793Sdiminline RNSuccIterator<NodeType> succ_end(NodeType* Node) { 255212793Sdim return RNSuccIterator<NodeType>(Node, true); 256212793Sdim} 257212793Sdim 258212793Sdim//===--------------------------------------------------------------------===// 259212793Sdim// RegionNode GraphTraits specialization so the bbs in the region can be 260212793Sdim// iterate by generic graph iterators. 261212793Sdim// 262212793Sdim// NodeT can either be region node or const region node, otherwise child_begin 263212793Sdim// and child_end fail. 264212793Sdim 265212793Sdim#define RegionNodeGraphTraits(NodeT) \ 266212793Sdim template<> struct GraphTraits<NodeT*> { \ 267212793Sdim typedef NodeT NodeType; \ 268212793Sdim typedef RNSuccIterator<NodeType> ChildIteratorType; \ 269212793Sdim static NodeType *getEntryNode(NodeType* N) { return N; } \ 270212793Sdim static inline ChildIteratorType child_begin(NodeType *N) { \ 271212793Sdim return RNSuccIterator<NodeType>(N); \ 272212793Sdim } \ 273212793Sdim static inline ChildIteratorType child_end(NodeType *N) { \ 274212793Sdim return RNSuccIterator<NodeType>(N, true); \ 275212793Sdim } \ 276212793Sdim}; \ 277212793Sdimtemplate<> struct GraphTraits<FlatIt<NodeT*> > { \ 278212793Sdim typedef NodeT NodeType; \ 279212793Sdim typedef RNSuccIterator<FlatIt<NodeT> > ChildIteratorType; \ 280212793Sdim static NodeType *getEntryNode(NodeType* N) { return N; } \ 281212793Sdim static inline ChildIteratorType child_begin(NodeType *N) { \ 282212793Sdim return RNSuccIterator<FlatIt<NodeType> >(N); \ 283212793Sdim } \ 284212793Sdim static inline ChildIteratorType child_end(NodeType *N) { \ 285212793Sdim return RNSuccIterator<FlatIt<NodeType> >(N, true); \ 286212793Sdim } \ 287212793Sdim} 288212793Sdim 289212793Sdim#define RegionGraphTraits(RegionT, NodeT) \ 290212793Sdimtemplate<> struct GraphTraits<RegionT*> \ 291212793Sdim : public GraphTraits<NodeT*> { \ 292212793Sdim typedef df_iterator<NodeType*> nodes_iterator; \ 293212793Sdim static NodeType *getEntryNode(RegionT* R) { \ 294212793Sdim return R->getNode(R->getEntry()); \ 295212793Sdim } \ 296212793Sdim static nodes_iterator nodes_begin(RegionT* R) { \ 297212793Sdim return nodes_iterator::begin(getEntryNode(R)); \ 298212793Sdim } \ 299212793Sdim static nodes_iterator nodes_end(RegionT* R) { \ 300212793Sdim return nodes_iterator::end(getEntryNode(R)); \ 301212793Sdim } \ 302212793Sdim}; \ 303212793Sdimtemplate<> struct GraphTraits<FlatIt<RegionT*> > \ 304212793Sdim : public GraphTraits<FlatIt<NodeT*> > { \ 305212793Sdim typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, \ 306212793Sdim GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \ 307212793Sdim static NodeType *getEntryNode(RegionT* R) { \ 308212793Sdim return R->getBBNode(R->getEntry()); \ 309212793Sdim } \ 310212793Sdim static nodes_iterator nodes_begin(RegionT* R) { \ 311212793Sdim return nodes_iterator::begin(getEntryNode(R)); \ 312212793Sdim } \ 313212793Sdim static nodes_iterator nodes_end(RegionT* R) { \ 314212793Sdim return nodes_iterator::end(getEntryNode(R)); \ 315212793Sdim } \ 316212793Sdim} 317212793Sdim 318212793SdimRegionNodeGraphTraits(RegionNode); 319212793SdimRegionNodeGraphTraits(const RegionNode); 320212793Sdim 321212793SdimRegionGraphTraits(Region, RegionNode); 322212793SdimRegionGraphTraits(const Region, const RegionNode); 323212793Sdim 324212793Sdimtemplate <> struct GraphTraits<RegionInfo*> 325212793Sdim : public GraphTraits<FlatIt<RegionNode*> > { 326212793Sdim typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, 327212793Sdim GraphTraits<FlatIt<NodeType*> > > nodes_iterator; 328212793Sdim 329212793Sdim static NodeType *getEntryNode(RegionInfo *RI) { 330212793Sdim return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion()); 331212793Sdim } 332212793Sdim static nodes_iterator nodes_begin(RegionInfo* RI) { 333212793Sdim return nodes_iterator::begin(getEntryNode(RI)); 334212793Sdim } 335212793Sdim static nodes_iterator nodes_end(RegionInfo *RI) { 336212793Sdim return nodes_iterator::end(getEntryNode(RI)); 337212793Sdim } 338212793Sdim}; 339212793Sdim 340212793Sdim} // End namespace llvm 341212793Sdim 342212793Sdim#endif 343