include/llvm/Analysis/IntervalIterator.h

   1 //===- IntervalIterator.h - Interval Iterator Declaration --------*- C++ -*--=//
   2 //
   3 // This file defines an iterator that enumerates the intervals in a control flow
   4 // graph of some sort.  This iterator is parametric, allowing iterator over the
   5 // following types of graphs:
   6 //
   7 //  1. A Method* object, composed of BasicBlock nodes.
   8 //  2. An IntervalPartition& object, composed of Interval nodes.
   9 //
  10 // This iterator is defined to walk the control flow graph, returning intervals
  11 // in depth first order.  These intervals are completely filled in except for
  12 // the predecessor fields (the successor information is filled in however).
  13 //
  14 // By default, the intervals created by this iterator are deleted after they
  15 // are no longer any use to the iterator.  This behavior can be changed by
  16 // passing a false value into the intervals_begin() function. This causes the
  17 // IOwnMem member to be set, and the intervals to not be deleted.
  18 //
  19 // It is only safe to use this if all of the intervals are deleted by the caller
  20 // and all of the intervals are processed.  However, the user of the iterator is
  21 // not allowed to modify or delete the intervals until after the iterator has
  22 // been used completely.  The IntervalPartition class uses this functionality.
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #ifndef LLVM_INTERVAL_ITERATOR_H
  27 #define LLVM_INTERVAL_ITERATOR_H
  28
  29 #include "llvm/Analysis/IntervalPartition.h"
  30 #include "llvm/Method.h"
  31 #include "llvm/CFG.h"
  32 #include <stack>
  33 #include <set>
  34 #include <algorithm>
  35
  36 namespace cfg {
  37
  38 // getNodeHeader - Given a source graph node and the source graph, return the
  39 // BasicBlock that is the header node.  This is the opposite of
  40 // getSourceGraphNode.
  41 //
  42 inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
  43 inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
  44
  45 // getSourceGraphNode - Given a BasicBlock and the source graph, return the
  46 // source graph node that corresponds to the BasicBlock.  This is the opposite
  47 // of getNodeHeader.
  48 //
  49 inline BasicBlock *getSourceGraphNode(Method *, BasicBlock *BB) {
  50   return BB;
  51 }
  52 inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
  53   return IP->getBlockInterval(BB);
  54 }
  55
  56 // addNodeToInterval - This method exists to assist the generic ProcessNode
  57 // with the task of adding a node to the new interval, depending on the
  58 // type of the source node.  In the case of a CFG source graph (BasicBlock
  59 // case), the BasicBlock itself is added to the interval.
  60 //
  61 inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
  62   Int->Nodes.push_back(BB);
  63 }
  64
  65 // addNodeToInterval - This method exists to assist the generic ProcessNode
  66 // with the task of adding a node to the new interval, depending on the
  67 // type of the source node.  In the case of a CFG source graph (BasicBlock
  68 // case), the BasicBlock itself is added to the interval.  In the case of
  69 // an IntervalPartition source graph (Interval case), all of the member
  70 // BasicBlocks are added to the interval.
  71 //
  72 inline void addNodeToInterval(Interval *Int, Interval *I) {
  73   // Add all of the nodes in I as new nodes in Int.
  74   copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes));
  75 }
  76
  77
  78
  79
  80
  81 template<class NodeTy, class OrigContainer_t>
  82 class IntervalIterator {
  83   stack<pair<Interval*, typename Interval::succ_iterator> > IntStack;
  84   set<BasicBlock*> Visited;
  85   OrigContainer_t *OrigContainer;
  86   bool IOwnMem;     // If True, delete intervals when done with them
  87                     // See file header for conditions of use
  88 public:
  89   typedef BasicBlock* _BB;
  90
  91   typedef IntervalIterator<NodeTy, OrigContainer_t> _Self;
  92   typedef forward_iterator_tag iterator_category;
  93
  94   IntervalIterator() {} // End iterator, empty stack
  95   IntervalIterator(Method *M, bool OwnMemory) : IOwnMem(OwnMemory) {
  96     OrigContainer = M;
  97     if (!ProcessInterval(M->getBasicBlocks().front())) {
  98       assert(0 && "ProcessInterval should never fail for first interval!");
  99     }
 100   }
 101
 102   IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
 103     OrigContainer = &IP;
 104     if (!ProcessInterval(IP.getRootInterval())) {
 105       assert(0 && "ProcessInterval should never fail for first interval!");
 106     }
 107   }
 108
 109   inline ~IntervalIterator() {
 110     if (IOwnMem)
 111       while (!IntStack.empty()) {
 112         delete operator*();
 113         IntStack.pop();
 114       }
 115   }
 116
 117   inline bool operator==(const _Self& x) const { return IntStack == x.IntStack;}
 118   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 119
 120   inline const Interval *operator*() const { return IntStack.top().first; }
 121   inline       Interval *operator*()       { return IntStack.top().first; }
 122   inline const Interval *operator->() const { return operator*(); }
 123   inline       Interval *operator->()       { return operator*(); }
 124
 125   _Self& operator++() {  // Preincrement
 126     assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
 127     do {
 128       // All of the intervals on the stack have been visited.  Try visiting
 129       // their successors now.
 130       Interval::succ_iterator &SuccIt =  IntStack.top().second,
 131                                 EndIt =  succ_end(IntStack.top().first);
 132       while (SuccIt != EndIt) {                 // Loop over all interval succs
 133         bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
 134         ++SuccIt;                               // Increment iterator
 135         if (Done) return *this;                 // Found a new interval! Use it!
 136       }
 137
 138       // Free interval memory... if neccesary
 139       if (IOwnMem) delete IntStack.top().first;
 140
 141       // We ran out of successors for this interval... pop off the stack
 142       IntStack.pop();
 143     } while (!IntStack.empty());
 144
 145     return *this;
 146   }
 147   inline _Self operator++(int) { // Postincrement
 148     _Self tmp = *this; ++*this; return tmp;
 149   }
 150
 151 private:
 152   // ProcessInterval - This method is used during the construction of the
 153   // interval graph.  It walks through the source graph, recursively creating
 154   // an interval per invokation until the entire graph is covered.  This uses
 155   // the ProcessNode method to add all of the nodes to the interval.
 156   //
 157   // This method is templated because it may operate on two different source
 158   // graphs: a basic block graph, or a preexisting interval graph.
 159   //
 160   bool ProcessInterval(NodeTy *Node) {
 161     BasicBlock *Header = getNodeHeader(Node);
 162     if (Visited.count(Header)) return false;
 163
 164     Interval *Int = new Interval(Header);
 165     Visited.insert(Header);   // The header has now been visited!
 166
 167     // Check all of our successors to see if they are in the interval...
 168     for (typename NodeTy::succ_iterator I = succ_begin(Node),E = succ_end(Node);
 169          I != E; ++I)
 170       ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
 171
 172     IntStack.push(make_pair(Int, succ_begin(Int)));
 173     return true;
 174   }
 175
 176   // ProcessNode - This method is called by ProcessInterval to add nodes to the
 177   // interval being constructed, and it is also called recursively as it walks
 178   // the source graph.  A node is added to the current interval only if all of
 179   // its predecessors are already in the graph.  This also takes care of keeping
 180   // the successor set of an interval up to date.
 181   //
 182   // This method is templated because it may operate on two different source
 183   // graphs: a basic block graph, or a preexisting interval graph.
 184   //
 185   void ProcessNode(Interval *Int, NodeTy *Node) {
 186     assert(Int && "Null interval == bad!");
 187     assert(Node && "Null Node == bad!");
 188
 189     BasicBlock *NodeHeader = getNodeHeader(Node);
 190
 191     if (Visited.count(NodeHeader)) {     // Node already been visited?
 192       if (Int->contains(NodeHeader)) {   // Already in this interval...
 193         return;
 194       } else {                           // In other interval, add as successor
 195         if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
 196           Int->Successors.push_back(NodeHeader);
 197       }
 198     } else {                             // Otherwise, not in interval yet
 199       for (typename NodeTy::pred_iterator I = pred_begin(Node),
 200                                           E = pred_end(Node); I != E; ++I) {
 201         if (!Int->contains(*I)) {        // If pred not in interval, we can't be
 202           if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
 203             Int->Successors.push_back(NodeHeader);
 204           return;                        // See you later
 205         }
 206       }
 207
 208       // If we get here, then all of the predecessors of BB are in the interval
 209       // already.  In this case, we must add BB to the interval!
 210       addNodeToInterval(Int, Node);
 211       Visited.insert(NodeHeader);     // The node has now been visited!
 212
 213       if (Int->isSuccessor(NodeHeader)) {
 214         // If we were in the successor list from before... remove from succ list
 215         Int->Successors.erase(remove(Int->Successors.begin(),
 216                                      Int->Successors.end(), NodeHeader),
 217                               Int->Successors.end());
 218       }
 219
 220       // Now that we have discovered that Node is in the interval, perhaps some
 221       // of its successors are as well?
 222       for (typename NodeTy::succ_iterator It = succ_begin(Node),
 223              End = succ_end(Node); It != End; ++It)
 224         ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
 225     }
 226   }
 227 };
 228
 229 typedef IntervalIterator<BasicBlock, Method> method_interval_iterator;
 230 typedef IntervalIterator<Interval, IntervalPartition> interval_part_interval_iterator;
 231
 232
 233 inline method_interval_iterator intervals_begin(Method *M,
 234                                                 bool DeleteInts = true) {
 235   return method_interval_iterator(M, DeleteInts);
 236 }
 237 inline method_interval_iterator intervals_end(Method *M) {
 238   return method_interval_iterator();
 239 }
 240
 241 inline interval_part_interval_iterator
 242    intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
 243   return interval_part_interval_iterator(IP, DeleteIntervals);
 244 }
 245
 246 inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
 247   return interval_part_interval_iterator();
 248 }
 249
 250 }    // End namespace cfg
 251
 252 #endif