LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

IntervalIterator.h

Go to the documentation of this file.
00001 //===- IntervalIterator.h - Interval Iterator Declaration -------*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines an iterator that enumerates the intervals in a control flow
00011 // graph of some sort.  This iterator is parametric, allowing iterator over the
00012 // following types of graphs:
00013 // 
00014 //  1. A Function* object, composed of BasicBlock nodes.
00015 //  2. An IntervalPartition& object, composed of Interval nodes.
00016 //
00017 // This iterator is defined to walk the control flow graph, returning intervals
00018 // in depth first order.  These intervals are completely filled in except for
00019 // the predecessor fields (the successor information is filled in however).
00020 //
00021 // By default, the intervals created by this iterator are deleted after they 
00022 // are no longer any use to the iterator.  This behavior can be changed by
00023 // passing a false value into the intervals_begin() function. This causes the 
00024 // IOwnMem member to be set, and the intervals to not be deleted.
00025 //
00026 // It is only safe to use this if all of the intervals are deleted by the caller
00027 // and all of the intervals are processed.  However, the user of the iterator is
00028 // not allowed to modify or delete the intervals until after the iterator has
00029 // been used completely.  The IntervalPartition class uses this functionality.
00030 //
00031 //===----------------------------------------------------------------------===//
00032 
00033 #ifndef LLVM_INTERVAL_ITERATOR_H
00034 #define LLVM_INTERVAL_ITERATOR_H
00035 
00036 #include "llvm/Analysis/IntervalPartition.h"
00037 #include "llvm/Function.h"
00038 #include "llvm/Support/CFG.h"
00039 #include <stack>
00040 #include <set>
00041 #include <algorithm>
00042 
00043 namespace llvm {
00044 
00045 // getNodeHeader - Given a source graph node and the source graph, return the 
00046 // BasicBlock that is the header node.  This is the opposite of
00047 // getSourceGraphNode.
00048 //
00049 inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
00050 inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
00051 
00052 // getSourceGraphNode - Given a BasicBlock and the source graph, return the 
00053 // source graph node that corresponds to the BasicBlock.  This is the opposite
00054 // of getNodeHeader.
00055 //
00056 inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
00057   return BB; 
00058 }
00059 inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) { 
00060   return IP->getBlockInterval(BB);
00061 }
00062 
00063 // addNodeToInterval - This method exists to assist the generic ProcessNode
00064 // with the task of adding a node to the new interval, depending on the 
00065 // type of the source node.  In the case of a CFG source graph (BasicBlock 
00066 // case), the BasicBlock itself is added to the interval.
00067 //
00068 inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
00069   Int->Nodes.push_back(BB);
00070 }
00071 
00072 // addNodeToInterval - This method exists to assist the generic ProcessNode
00073 // with the task of adding a node to the new interval, depending on the 
00074 // type of the source node.  In the case of a CFG source graph (BasicBlock 
00075 // case), the BasicBlock itself is added to the interval.  In the case of
00076 // an IntervalPartition source graph (Interval case), all of the member
00077 // BasicBlocks are added to the interval.
00078 //
00079 inline void addNodeToInterval(Interval *Int, Interval *I) {
00080   // Add all of the nodes in I as new nodes in Int.
00081   copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes));
00082 }
00083 
00084 
00085 
00086 
00087 
00088 template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy*>,
00089          class IGT = GraphTraits<Inverse<NodeTy*> > >
00090 class IntervalIterator {
00091   std::stack<std::pair<Interval*, typename Interval::succ_iterator> > IntStack;
00092   std::set<BasicBlock*> Visited;
00093   OrigContainer_t *OrigContainer;
00094   bool IOwnMem;     // If True, delete intervals when done with them
00095                     // See file header for conditions of use
00096 public:
00097   typedef IntervalIterator<NodeTy, OrigContainer_t> _Self;
00098   typedef std::forward_iterator_tag iterator_category;
00099  
00100   IntervalIterator() {} // End iterator, empty stack
00101   IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
00102     OrigContainer = M;
00103     if (!ProcessInterval(&M->front())) {
00104       assert(0 && "ProcessInterval should never fail for first interval!");
00105     }
00106   }
00107 
00108   IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
00109     OrigContainer = &IP;
00110     if (!ProcessInterval(IP.getRootInterval())) {
00111       assert(0 && "ProcessInterval should never fail for first interval!");
00112     }
00113   }
00114 
00115   inline ~IntervalIterator() {
00116     if (IOwnMem)
00117       while (!IntStack.empty()) {
00118   delete operator*();
00119   IntStack.pop();
00120       }
00121   }
00122 
00123   inline bool operator==(const _Self& x) const { return IntStack == x.IntStack;}
00124   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00125 
00126   inline const Interval *operator*() const { return IntStack.top().first; }
00127   inline       Interval *operator*()       { return IntStack.top().first; }
00128   inline const Interval *operator->() const { return operator*(); }
00129   inline       Interval *operator->()       { return operator*(); }
00130 
00131   _Self& operator++() {  // Preincrement
00132     assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
00133     do {
00134       // All of the intervals on the stack have been visited.  Try visiting
00135       // their successors now.
00136       Interval::succ_iterator &SuccIt = IntStack.top().second,
00137                           EndIt = succ_end(IntStack.top().first);
00138       while (SuccIt != EndIt) {                 // Loop over all interval succs
00139   bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
00140   ++SuccIt;                               // Increment iterator
00141   if (Done) return *this;                 // Found a new interval! Use it!
00142       }
00143 
00144       // Free interval memory... if necessary
00145       if (IOwnMem) delete IntStack.top().first;
00146 
00147       // We ran out of successors for this interval... pop off the stack
00148       IntStack.pop();
00149     } while (!IntStack.empty());
00150 
00151     return *this; 
00152   }
00153   inline _Self operator++(int) { // Postincrement
00154     _Self tmp = *this; ++*this; return tmp; 
00155   }
00156 
00157 private:
00158   // ProcessInterval - This method is used during the construction of the 
00159   // interval graph.  It walks through the source graph, recursively creating
00160   // an interval per invokation until the entire graph is covered.  This uses
00161   // the ProcessNode method to add all of the nodes to the interval.
00162   //
00163   // This method is templated because it may operate on two different source
00164   // graphs: a basic block graph, or a preexisting interval graph.
00165   //
00166   bool ProcessInterval(NodeTy *Node) {
00167     BasicBlock *Header = getNodeHeader(Node);
00168     if (Visited.count(Header)) return false;
00169 
00170     Interval *Int = new Interval(Header);
00171     Visited.insert(Header);   // The header has now been visited!
00172 
00173     // Check all of our successors to see if they are in the interval...
00174     for (typename GT::ChildIteratorType I = GT::child_begin(Node),
00175            E = GT::child_end(Node); I != E; ++I)
00176       ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
00177 
00178     IntStack.push(std::make_pair(Int, succ_begin(Int)));
00179     return true;
00180   }
00181   
00182   // ProcessNode - This method is called by ProcessInterval to add nodes to the
00183   // interval being constructed, and it is also called recursively as it walks
00184   // the source graph.  A node is added to the current interval only if all of
00185   // its predecessors are already in the graph.  This also takes care of keeping
00186   // the successor set of an interval up to date.
00187   //
00188   // This method is templated because it may operate on two different source
00189   // graphs: a basic block graph, or a preexisting interval graph.
00190   //
00191   void ProcessNode(Interval *Int, NodeTy *Node) {
00192     assert(Int && "Null interval == bad!");
00193     assert(Node && "Null Node == bad!");
00194   
00195     BasicBlock *NodeHeader = getNodeHeader(Node);
00196 
00197     if (Visited.count(NodeHeader)) {     // Node already been visited?
00198       if (Int->contains(NodeHeader)) {   // Already in this interval...
00199   return;
00200       } else {                           // In other interval, add as successor
00201   if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
00202     Int->Successors.push_back(NodeHeader);
00203       }
00204     } else {                             // Otherwise, not in interval yet
00205       for (typename IGT::ChildIteratorType I = IGT::child_begin(Node), 
00206              E = IGT::child_end(Node); I != E; ++I) {
00207   if (!Int->contains(*I)) {        // If pred not in interval, we can't be
00208     if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
00209       Int->Successors.push_back(NodeHeader);
00210     return;                        // See you later
00211   }
00212       }
00213 
00214       // If we get here, then all of the predecessors of BB are in the interval
00215       // already.  In this case, we must add BB to the interval!
00216       addNodeToInterval(Int, Node);
00217       Visited.insert(NodeHeader);     // The node has now been visited!
00218     
00219       if (Int->isSuccessor(NodeHeader)) {
00220   // If we were in the successor list from before... remove from succ list
00221   Int->Successors.erase(std::remove(Int->Successors.begin(),
00222                   Int->Successors.end(), NodeHeader), 
00223             Int->Successors.end());
00224       }
00225     
00226       // Now that we have discovered that Node is in the interval, perhaps some
00227       // of its successors are as well?
00228       for (typename GT::ChildIteratorType It = GT::child_begin(Node),
00229        End = GT::child_end(Node); It != End; ++It)
00230   ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
00231     }
00232   }
00233 };
00234 
00235 typedef IntervalIterator<BasicBlock, Function> function_interval_iterator;
00236 typedef IntervalIterator<Interval, IntervalPartition> interval_part_interval_iterator;
00237 
00238 
00239 inline function_interval_iterator intervals_begin(Function *F, 
00240                                                   bool DeleteInts = true) {
00241   return function_interval_iterator(F, DeleteInts);
00242 }
00243 inline function_interval_iterator intervals_end(Function *) {
00244   return function_interval_iterator();
00245 }
00246 
00247 inline interval_part_interval_iterator 
00248    intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
00249   return interval_part_interval_iterator(IP, DeleteIntervals);
00250 }
00251 
00252 inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
00253   return interval_part_interval_iterator();
00254 }
00255 
00256 } // End llvm namespace
00257 
00258 #endif