include/llvm/Analysis/Interval.h

   1 //===- llvm/Analysis/Intervals.h - Interval partition Calculation-*- C++ -*--=//
   2 //
   3 // This file contains the declaration of the cfg::IntervalPartition class, which
   4 // calculates and represents the interval partition of a method, or a
   5 // preexisting interval partition.
   6 //
   7 // In this way, the interval partition may be used to reduce a flow graph down
   8 // to its degenerate single node interval partition (unless it is irreducible).
   9 //
  10 //===----------------------------------------------------------------------===//
  11
  12 #ifndef LLVM_INTERVALS_H
  13 #define LLVM_INTERVALS_H
  14
  15 #include <vector>
  16 #include <map>
  17 #include <algorithm>
  18
  19 class Method;
  20 class BasicBlock;
  21
  22 namespace cfg {
  23
  24 class IntervalPartition;
  25
  26 // Interval Class - An Interval is a set of nodes defined such that every node
  27 // in the interval has all of its predecessors in the interval (except for the
  28 // header)
  29 class Interval {
  30   friend class IntervalPartition;
  31 public:
  32   typedef vector<BasicBlock*>::iterator succ_iterator;
  33   typedef vector<BasicBlock*>::iterator pred_iterator;
  34   typedef vector<BasicBlock*>::iterator node_iterator;
  35
  36   // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
  37   // interval.  Also, any loops in this interval must go through the HeaderNode.
  38   //
  39   BasicBlock *HeaderNode;
  40
  41   // Nodes - The basic blocks in this interval.
  42   //
  43   vector<BasicBlock*> Nodes;
  44
  45   // Successors - List of BasicBlocks that are reachable directly from nodes in
  46   // this interval, but are not in the interval themselves.
  47   // These nodes neccesarily must be header nodes for other intervals.
  48   //
  49   vector<BasicBlock*> Successors;
  50
  51   // Predecessors - List of BasicBlocks that have this Interval's header block
  52   // as one of their successors.
  53   //
  54   vector<BasicBlock*> Predecessors;
  55
  56   inline bool contains(BasicBlock *BB) {
  57     return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
  58   }
  59
  60   inline bool isSuccessor(BasicBlock *BB) {
  61     return find(Successors.begin(), Successors.end(), BB) != Successors.end();
  62   }
  63
  64 private:           // Only accessable by IntervalPartition class
  65   inline Interval(BasicBlock *Header) : HeaderNode(Header) {
  66     Nodes.push_back(Header);
  67   }
  68 };
  69
  70
  71 // succ_begin/succ_end - define global functions so that Intervals may be used
  72 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
  73 //
  74 inline Interval::succ_iterator succ_begin(Interval *I) {
  75   return I->Successors.begin();
  76 }
  77 inline Interval::succ_iterator succ_end(Interval *I) {
  78   return I->Successors.end();
  79 }
  80
  81 // pred_begin/pred_end - define global functions so that Intervals may be used
  82 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
  83 //
  84 inline Interval::pred_iterator pred_begin(Interval *I) {
  85   return I->Predecessors.begin();
  86 }
  87 inline Interval::pred_iterator pred_end(Interval *I) {
  88   return I->Predecessors.end();
  89 }
  90
  91
  92
  93 // IntervalPartition - This class builds and holds an "interval partition" for
  94 // a method.  This partition divides the control flow graph into a set of
  95 // maximal intervals, as defined with the properties above.  Intuitively, a
  96 // BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
  97 // nodes following it.
  98 //
  99 class IntervalPartition {
 100   typedef map<BasicBlock*, Interval*> IntervalMapTy;
 101   IntervalMapTy IntervalMap;
 102
 103   typedef vector<Interval*> IntervalListTy;
 104   IntervalListTy IntervalList;
 105   Interval *RootInterval;
 106
 107 public:
 108   typedef IntervalListTy::iterator iterator;
 109
 110 public:
 111   // IntervalPartition ctor - Build the partition for the specified method
 112   IntervalPartition(Method *M);
 113
 114   // IntervalPartition ctor - Build a reduced interval partition from an
 115   // existing interval graph.  This takes an additional boolean parameter to
 116   // distinguish it from a copy constructor.  Always pass in false for now.
 117   //
 118   IntervalPartition(IntervalPartition &I, bool);
 119
 120   // getRootInterval() - Return the root interval that contains the starting
 121   // block of the method
 122   inline Interval *getRootInterval() { return RootInterval; }
 123
 124   inline Interval *getBlockInterval(BasicBlock *BB) {
 125     IntervalMapTy::iterator I = IntervalMap.find(BB);
 126     if (I != IntervalMap.end())
 127       return I->second;
 128     else
 129       return 0;
 130   }
 131
 132   // Iterators to iterate over all of the intervals in the method
 133   inline iterator begin() { return IntervalList.begin(); }
 134   inline iterator end()   { return IntervalList.end(); }
 135
 136 private:
 137   // ProcessInterval - This method is used during the construction of the
 138   // interval graph.  It walks through the source graph, recursively creating
 139   // an interval per invokation until the entire graph is covered.  This uses
 140   // the ProcessNode method to add all of the nodes to the interval.
 141   //
 142   // This method is templated because it may operate on two different source
 143   // graphs: a basic block graph, or a preexisting interval graph.
 144   //
 145   template<class NodeTy, class OrigContainer>
 146   void ProcessInterval(NodeTy *Node, OrigContainer *OC);
 147
 148   // ProcessNode - This method is called by ProcessInterval to add nodes to the
 149   // interval being constructed, and it is also called recursively as it walks
 150   // the source graph.  A node is added to the current interval only if all of
 151   // its predecessors are already in the graph.  This also takes care of keeping
 152   // the successor set of an interval up to date.
 153   //
 154   // This method is templated because it may operate on two different source
 155   // graphs: a basic block graph, or a preexisting interval graph.
 156   //
 157   template<class NodeTy, class OrigContainer>
 158   void ProcessNode(Interval *Int, NodeTy *Node, OrigContainer *OC);
 159
 160   // addNodeToInterval - This method exists to assist the generic ProcessNode
 161   // with the task of adding a node to the new interval, depending on the
 162   // type of the source node.  In the case of a CFG source graph (BasicBlock
 163   // case), the BasicBlock itself is added to the interval.  In the case of
 164   // an IntervalPartition source graph (Interval case), all of the member
 165   // BasicBlocks are added to the interval.
 166   //
 167   inline void addNodeToInterval(Interval *Int, Interval *I);
 168   inline void addNodeToInterval(Interval *Int, BasicBlock *BB);
 169
 170   // updatePredecessors - Interval generation only sets the successor fields of
 171   // the interval data structures.  After interval generation is complete,
 172   // run through all of the intervals and propogate successor info as
 173   // predecessor info.
 174   //
 175   void updatePredecessors(Interval *Int);
 176 };
 177
 178 }    // End namespace cfg
 179
 180 #endif