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