1193323Sed//===- IntervalIterator.h - Interval Iterator Declaration -------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines an iterator that enumerates the intervals in a control flow 11193323Sed// graph of some sort. This iterator is parametric, allowing iterator over the 12193323Sed// following types of graphs: 13193323Sed// 14193323Sed// 1. A Function* object, composed of BasicBlock nodes. 15193323Sed// 2. An IntervalPartition& object, composed of Interval nodes. 16193323Sed// 17193323Sed// This iterator is defined to walk the control flow graph, returning intervals 18193323Sed// in depth first order. These intervals are completely filled in except for 19193323Sed// the predecessor fields (the successor information is filled in however). 20193323Sed// 21193323Sed// By default, the intervals created by this iterator are deleted after they 22193323Sed// are no longer any use to the iterator. This behavior can be changed by 23193323Sed// passing a false value into the intervals_begin() function. This causes the 24193323Sed// IOwnMem member to be set, and the intervals to not be deleted. 25193323Sed// 26193323Sed// It is only safe to use this if all of the intervals are deleted by the caller 27193323Sed// and all of the intervals are processed. However, the user of the iterator is 28193323Sed// not allowed to modify or delete the intervals until after the iterator has 29193323Sed// been used completely. The IntervalPartition class uses this functionality. 30193323Sed// 31193323Sed//===----------------------------------------------------------------------===// 32193323Sed 33249423Sdim#ifndef LLVM_ANALYSIS_INTERVALITERATOR_H 34249423Sdim#define LLVM_ANALYSIS_INTERVALITERATOR_H 35193323Sed 36193323Sed#include "llvm/Analysis/IntervalPartition.h" 37249423Sdim#include "llvm/IR/Function.h" 38193323Sed#include "llvm/Support/CFG.h" 39210299Sed#include <algorithm> 40193323Sed#include <set> 41210299Sed#include <vector> 42193323Sed 43193323Sednamespace llvm { 44193323Sed 45193323Sed// getNodeHeader - Given a source graph node and the source graph, return the 46193323Sed// BasicBlock that is the header node. This is the opposite of 47193323Sed// getSourceGraphNode. 48193323Sed// 49193323Sedinline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; } 50193323Sedinline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); } 51193323Sed 52193323Sed// getSourceGraphNode - Given a BasicBlock and the source graph, return the 53193323Sed// source graph node that corresponds to the BasicBlock. This is the opposite 54193323Sed// of getNodeHeader. 55193323Sed// 56193323Sedinline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) { 57193323Sed return BB; 58193323Sed} 59193323Sedinline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) { 60193323Sed return IP->getBlockInterval(BB); 61193323Sed} 62193323Sed 63193323Sed// addNodeToInterval - This method exists to assist the generic ProcessNode 64193323Sed// with the task of adding a node to the new interval, depending on the 65193323Sed// type of the source node. In the case of a CFG source graph (BasicBlock 66193323Sed// case), the BasicBlock itself is added to the interval. 67193323Sed// 68193323Sedinline void addNodeToInterval(Interval *Int, BasicBlock *BB) { 69193323Sed Int->Nodes.push_back(BB); 70193323Sed} 71193323Sed 72193323Sed// addNodeToInterval - This method exists to assist the generic ProcessNode 73193323Sed// with the task of adding a node to the new interval, depending on the 74193323Sed// type of the source node. In the case of a CFG source graph (BasicBlock 75193323Sed// case), the BasicBlock itself is added to the interval. In the case of 76193323Sed// an IntervalPartition source graph (Interval case), all of the member 77193323Sed// BasicBlocks are added to the interval. 78193323Sed// 79193323Sedinline void addNodeToInterval(Interval *Int, Interval *I) { 80193323Sed // Add all of the nodes in I as new nodes in Int. 81193323Sed copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes)); 82193323Sed} 83193323Sed 84193323Sed 85193323Sed 86193323Sed 87193323Sed 88193323Sedtemplate<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy*>, 89193323Sed class IGT = GraphTraits<Inverse<NodeTy*> > > 90193323Sedclass IntervalIterator { 91210299Sed std::vector<std::pair<Interval*, typename Interval::succ_iterator> > IntStack; 92193323Sed std::set<BasicBlock*> Visited; 93193323Sed OrigContainer_t *OrigContainer; 94193323Sed bool IOwnMem; // If True, delete intervals when done with them 95193323Sed // See file header for conditions of use 96193323Sedpublic: 97193323Sed typedef IntervalIterator<NodeTy, OrigContainer_t> _Self; 98193323Sed typedef std::forward_iterator_tag iterator_category; 99193323Sed 100193323Sed IntervalIterator() {} // End iterator, empty stack 101193323Sed IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) { 102193323Sed OrigContainer = M; 103193323Sed if (!ProcessInterval(&M->front())) { 104234353Sdim llvm_unreachable("ProcessInterval should never fail for first interval!"); 105193323Sed } 106193323Sed } 107193323Sed 108193323Sed IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) { 109193323Sed OrigContainer = &IP; 110193323Sed if (!ProcessInterval(IP.getRootInterval())) { 111234353Sdim llvm_unreachable("ProcessInterval should never fail for first interval!"); 112193323Sed } 113193323Sed } 114193323Sed 115193323Sed inline ~IntervalIterator() { 116193323Sed if (IOwnMem) 117193323Sed while (!IntStack.empty()) { 118193323Sed delete operator*(); 119210299Sed IntStack.pop_back(); 120193323Sed } 121193323Sed } 122193323Sed 123193323Sed inline bool operator==(const _Self& x) const { return IntStack == x.IntStack;} 124193323Sed inline bool operator!=(const _Self& x) const { return !operator==(x); } 125193323Sed 126210299Sed inline const Interval *operator*() const { return IntStack.back().first; } 127210299Sed inline Interval *operator*() { return IntStack.back().first; } 128193323Sed inline const Interval *operator->() const { return operator*(); } 129193323Sed inline Interval *operator->() { return operator*(); } 130193323Sed 131193323Sed _Self& operator++() { // Preincrement 132193323Sed assert(!IntStack.empty() && "Attempting to use interval iterator at end!"); 133193323Sed do { 134193323Sed // All of the intervals on the stack have been visited. Try visiting 135193323Sed // their successors now. 136210299Sed Interval::succ_iterator &SuccIt = IntStack.back().second, 137210299Sed EndIt = succ_end(IntStack.back().first); 138193323Sed while (SuccIt != EndIt) { // Loop over all interval succs 139193323Sed bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt)); 140193323Sed ++SuccIt; // Increment iterator 141193323Sed if (Done) return *this; // Found a new interval! Use it! 142193323Sed } 143193323Sed 144193323Sed // Free interval memory... if necessary 145210299Sed if (IOwnMem) delete IntStack.back().first; 146193323Sed 147193323Sed // We ran out of successors for this interval... pop off the stack 148210299Sed IntStack.pop_back(); 149193323Sed } while (!IntStack.empty()); 150193323Sed 151193323Sed return *this; 152193323Sed } 153193323Sed inline _Self operator++(int) { // Postincrement 154193323Sed _Self tmp = *this; ++*this; return tmp; 155193323Sed } 156193323Sed 157193323Sedprivate: 158193323Sed // ProcessInterval - This method is used during the construction of the 159193323Sed // interval graph. It walks through the source graph, recursively creating 160249423Sdim // an interval per invocation until the entire graph is covered. This uses 161193323Sed // the ProcessNode method to add all of the nodes to the interval. 162193323Sed // 163193323Sed // This method is templated because it may operate on two different source 164193323Sed // graphs: a basic block graph, or a preexisting interval graph. 165193323Sed // 166193323Sed bool ProcessInterval(NodeTy *Node) { 167193323Sed BasicBlock *Header = getNodeHeader(Node); 168193323Sed if (Visited.count(Header)) return false; 169193323Sed 170193323Sed Interval *Int = new Interval(Header); 171193323Sed Visited.insert(Header); // The header has now been visited! 172193323Sed 173193323Sed // Check all of our successors to see if they are in the interval... 174193323Sed for (typename GT::ChildIteratorType I = GT::child_begin(Node), 175193323Sed E = GT::child_end(Node); I != E; ++I) 176193323Sed ProcessNode(Int, getSourceGraphNode(OrigContainer, *I)); 177193323Sed 178210299Sed IntStack.push_back(std::make_pair(Int, succ_begin(Int))); 179193323Sed return true; 180193323Sed } 181193323Sed 182193323Sed // ProcessNode - This method is called by ProcessInterval to add nodes to the 183193323Sed // interval being constructed, and it is also called recursively as it walks 184193323Sed // the source graph. A node is added to the current interval only if all of 185193323Sed // its predecessors are already in the graph. This also takes care of keeping 186193323Sed // the successor set of an interval up to date. 187193323Sed // 188193323Sed // This method is templated because it may operate on two different source 189193323Sed // graphs: a basic block graph, or a preexisting interval graph. 190193323Sed // 191193323Sed void ProcessNode(Interval *Int, NodeTy *Node) { 192193323Sed assert(Int && "Null interval == bad!"); 193193323Sed assert(Node && "Null Node == bad!"); 194193323Sed 195193323Sed BasicBlock *NodeHeader = getNodeHeader(Node); 196193323Sed 197193323Sed if (Visited.count(NodeHeader)) { // Node already been visited? 198193323Sed if (Int->contains(NodeHeader)) { // Already in this interval... 199193323Sed return; 200193323Sed } else { // In other interval, add as successor 201193323Sed if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set 202193323Sed Int->Successors.push_back(NodeHeader); 203193323Sed } 204193323Sed } else { // Otherwise, not in interval yet 205193323Sed for (typename IGT::ChildIteratorType I = IGT::child_begin(Node), 206193323Sed E = IGT::child_end(Node); I != E; ++I) { 207193323Sed if (!Int->contains(*I)) { // If pred not in interval, we can't be 208193323Sed if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set 209193323Sed Int->Successors.push_back(NodeHeader); 210193323Sed return; // See you later 211193323Sed } 212193323Sed } 213193323Sed 214193323Sed // If we get here, then all of the predecessors of BB are in the interval 215193323Sed // already. In this case, we must add BB to the interval! 216193323Sed addNodeToInterval(Int, Node); 217193323Sed Visited.insert(NodeHeader); // The node has now been visited! 218193323Sed 219193323Sed if (Int->isSuccessor(NodeHeader)) { 220193323Sed // If we were in the successor list from before... remove from succ list 221193323Sed Int->Successors.erase(std::remove(Int->Successors.begin(), 222193323Sed Int->Successors.end(), NodeHeader), 223193323Sed Int->Successors.end()); 224193323Sed } 225193323Sed 226193323Sed // Now that we have discovered that Node is in the interval, perhaps some 227193323Sed // of its successors are as well? 228193323Sed for (typename GT::ChildIteratorType It = GT::child_begin(Node), 229193323Sed End = GT::child_end(Node); It != End; ++It) 230193323Sed ProcessNode(Int, getSourceGraphNode(OrigContainer, *It)); 231193323Sed } 232193323Sed } 233193323Sed}; 234193323Sed 235193323Sedtypedef IntervalIterator<BasicBlock, Function> function_interval_iterator; 236198090Srdivackytypedef IntervalIterator<Interval, IntervalPartition> 237198090Srdivacky interval_part_interval_iterator; 238193323Sed 239193323Sed 240193323Sedinline function_interval_iterator intervals_begin(Function *F, 241193323Sed bool DeleteInts = true) { 242193323Sed return function_interval_iterator(F, DeleteInts); 243193323Sed} 244193323Sedinline function_interval_iterator intervals_end(Function *) { 245193323Sed return function_interval_iterator(); 246193323Sed} 247193323Sed 248193323Sedinline interval_part_interval_iterator 249193323Sed intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) { 250193323Sed return interval_part_interval_iterator(IP, DeleteIntervals); 251193323Sed} 252193323Sed 253193323Sedinline interval_part_interval_iterator intervals_end(IntervalPartition &IP) { 254193323Sed return interval_part_interval_iterator(); 255193323Sed} 256193323Sed 257193323Sed} // End llvm namespace 258193323Sed 259193323Sed#endif 260