1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file defines the iterators to iterate over the elements of a Region. 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ANALYSIS_REGION_ITERATOR_H 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ANALYSIS_REGION_ITERATOR_H 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/GraphTraits.h" 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallPtrSet.h" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/PointerIntPair.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/RegionInfo.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CFG.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @brief Hierarchical RegionNode successor iterator. 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This iterator iterates over all successors of a RegionNode. 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the parent Region. Furthermore for BasicBlocks that start a subregion, a 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RegionNode representing the subregion is returned. 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// For a subregion RegionNode there is just one successor. The RegionNode 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// representing the exit of the subregion. 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class NodeType> 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass RNSuccIterator : public std::iterator<std::forward_iterator_tag, 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodeType, ptrdiff_t> 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The iterator works in two modes, bb mode or region mode. 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman enum ItMode{ 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In BB mode it returns all successors of this BasicBlock as its 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // successors. 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItBB, 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In region mode there is only one successor, thats the regionnode mapping 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to the exit block of the regionnode 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItRgBegin, // At the beginning of the regionnode successor. 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ItRgEnd // At the end of the regionnode successor. 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Use two bit to represent the mode iterator. 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PointerIntPair<NodeType*, 2, enum ItMode> Node; 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The block successor iterator. 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman succ_iterator BItor; 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // advanceRegionSucc - A region node has only one successor. It reaches end 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // once we advance it. 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void advanceRegionSucc() { 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!"); 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node.setInt(ItRgEnd); 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodeType* getNode() const{ return Node.getPointer(); } 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isRegionMode - Is the current iterator in region mode? 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isRegionMode() const { return Node.getInt() != ItBB; } 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Get the immediate successor. This function may return a Basic Block 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // RegionNode or a subregion RegionNode. 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionNode* getISucc(BasicBlock* BB) const { 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegionNode *succ; 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman succ = getNode()->getParent()->getNode(BB); 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(succ && "BB not in Region or entered subregion!"); 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return succ; 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // getRegionSucc - Return the successor basic block of a SubRegion RegionNode. 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline BasicBlock* getRegionSucc() const { 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getNode()->template getNodeAs<Region>()->getExit(); 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // isExit - Is this the exit BB of the Region? 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool isExit(BasicBlock* BB) const { 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getNode()->getParent()->getExit() == BB; 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef RNSuccIterator<NodeType> Self; 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename super::pointer pointer; 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Create begin iterator of a RegionNode. 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline RNSuccIterator(NodeType* node) 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BItor(succ_begin(node->getEntry())) { 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Skip the exit block 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isRegionMode()) 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (succ_end(node->getEntry()) != BItor && isExit(*BItor)) 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++BItor; 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isRegionMode() && isExit(getRegionSucc())) 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman advanceRegionSucc(); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Create an end iterator. 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline RNSuccIterator(NodeType* node, bool) 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BItor(succ_end(node->getEntry())) {} 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator==(const Self& x) const { 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isRegionMode()) 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Node.getInt() == x.Node.getInt(); 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return BItor == x.BItor; 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator!=(const Self& x) const { return !operator==(x); } 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline pointer operator*() const { 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* BB = isRegionMode() ? getRegionSucc() : *BItor; 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!isExit(BB) && "Iterator out of range!"); 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getISucc(BB); 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Self& operator++() { 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if(isRegionMode()) { 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The Region only has 1 successor. 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman advanceRegionSucc(); 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Skip the exit. 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++BItor; 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (BItor != succ_end(getNode()->getEntry()) 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && isExit(*BItor)); 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Self operator++(int) { 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Self tmp = *this; 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++*this; 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return tmp; 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const Self &operator=(const Self &I) { 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (this != &I) { 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(getNode()->getParent() == I.getNode()->getParent() 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && "Cannot assign iterators of two different regions!"); 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node = I.Node; 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BItor = I.BItor; 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// @brief Flat RegionNode iterator. 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// are contained in the Region and its subregions. This is close to a virtual 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// control flow graph of the Region. 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class NodeType> 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass RNSuccIterator<FlatIt<NodeType> > 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodeType* Node; 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman succ_iterator Itor; 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef RNSuccIterator<FlatIt<NodeType> > Self; 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename super::pointer pointer; 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Create the iterator from a RegionNode. 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Note that the incoming node must be a bb node, otherwise it will trigger 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// an assertion when we try to get a BasicBlock. 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline RNSuccIterator(NodeType* node) : Node(node), 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Itor(succ_begin(node->getEntry())) { 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!Node->isSubRegion() 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && "Subregion node not allowed in flat iterating mode!"); 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Node->getParent() && "A BB node must have a parent!"); 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Skip the exit block of the iterating region. 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (succ_end(Node->getEntry()) != Itor 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && Node->getParent()->getExit() == *Itor) 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Itor; 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// @brief Create an end iterator 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline RNSuccIterator(NodeType* node, bool) : Node(node), 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Itor(succ_end(node->getEntry())) { 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!Node->isSubRegion() 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && "Subregion node not allowed in flat iterating mode!"); 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator==(const Self& x) const { 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Node->getParent() == x.Node->getParent() 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && "Cannot compare iterators of different regions!"); 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Itor == x.Itor && Node == x.Node; 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator!=(const Self& x) const { return !operator==(x); } 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline pointer operator*() const { 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock* BB = *Itor; 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Get the iterating region. 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Region* Parent = Node->getParent(); 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The only case that the successor reaches out of the region is it reaches 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the exit of the region. 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Parent->getExit() != BB && "iterator out of range!"); 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Parent->getBBNode(BB); 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Self& operator++() { 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Skip the exit block of the iterating region. 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Itor; 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (Itor != succ_end(Node->getEntry()) 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && Node->getParent()->getExit() == *Itor); 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Self operator++(int) { 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Self tmp = *this; 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++*this; 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return tmp; 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const Self &operator=(const Self &I) { 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (this != &I) { 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Node->getParent() == I.Node->getParent() 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman && "Cannot assign iterators to two different regions!"); 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node = I.Node; 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Itor = I.Itor; 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class NodeType> 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline RNSuccIterator<NodeType> succ_begin(NodeType* Node) { 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return RNSuccIterator<NodeType>(Node); 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class NodeType> 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline RNSuccIterator<NodeType> succ_end(NodeType* Node) { 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return RNSuccIterator<NodeType>(Node, true); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===--------------------------------------------------------------------===// 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// RegionNode GraphTraits specialization so the bbs in the region can be 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// iterate by generic graph iterators. 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// NodeT can either be region node or const region node, otherwise child_begin 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// and child_end fail. 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define RegionNodeGraphTraits(NodeT) \ 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<> struct GraphTraits<NodeT*> { \ 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef NodeT NodeType; \ 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef RNSuccIterator<NodeType> ChildIteratorType; \ 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static NodeType *getEntryNode(NodeType* N) { return N; } \ 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_begin(NodeType *N) { \ 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return RNSuccIterator<NodeType>(N); \ 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_end(NodeType *N) { \ 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return RNSuccIterator<NodeType>(N, true); \ 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; \ 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<> struct GraphTraits<FlatIt<NodeT*> > { \ 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef NodeT NodeType; \ 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef RNSuccIterator<FlatIt<NodeT> > ChildIteratorType; \ 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static NodeType *getEntryNode(NodeType* N) { return N; } \ 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_begin(NodeType *N) { \ 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return RNSuccIterator<FlatIt<NodeType> >(N); \ 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_end(NodeType *N) { \ 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return RNSuccIterator<FlatIt<NodeType> >(N, true); \ 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define RegionGraphTraits(RegionT, NodeT) \ 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<> struct GraphTraits<RegionT*> \ 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : public GraphTraits<NodeT*> { \ 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef df_iterator<NodeType*> nodes_iterator; \ 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static NodeType *getEntryNode(RegionT* R) { \ 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return R->getNode(R->getEntry()); \ 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_begin(RegionT* R) { \ 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return nodes_iterator::begin(getEntryNode(R)); \ 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_end(RegionT* R) { \ 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return nodes_iterator::end(getEntryNode(R)); \ 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; \ 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<> struct GraphTraits<FlatIt<RegionT*> > \ 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : public GraphTraits<FlatIt<NodeT*> > { \ 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, \ 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \ 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static NodeType *getEntryNode(RegionT* R) { \ 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return R->getBBNode(R->getEntry()); \ 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_begin(RegionT* R) { \ 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return nodes_iterator::begin(getEntryNode(R)); \ 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_end(RegionT* R) { \ 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return nodes_iterator::end(getEntryNode(R)); \ 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } \ 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanRegionNodeGraphTraits(RegionNode); 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanRegionNodeGraphTraits(const RegionNode); 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanRegionGraphTraits(Region, RegionNode); 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanRegionGraphTraits(const Region, const RegionNode); 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <> struct GraphTraits<RegionInfo*> 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : public GraphTraits<FlatIt<RegionNode*> > { 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman GraphTraits<FlatIt<NodeType*> > > nodes_iterator; 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static NodeType *getEntryNode(RegionInfo *RI) { 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion()); 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_begin(RegionInfo* RI) { 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return nodes_iterator::begin(getEntryNode(RI)); 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_end(RegionInfo *RI) { 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return nodes_iterator::end(getEntryNode(RI)); 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End namespace llvm 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 343