include/llvm/Analysis/IntervalIterator.h

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