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   // contains - Find out if a basic block is in this interval
  57   inline bool contains(BasicBlock *BB) const {
  58     return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
  59   }
  60
  61   // isSuccessor - find out if a basic block is a successor of this Interval
  62   inline bool isSuccessor(BasicBlock *BB) const {
  63     return find(Successors.begin(), Successors.end(), BB) != Successors.end();
  64   }
  65
  66   // isLoop - Find out if there is a back edge in this interval...
  67   bool isLoop() const;
  68
  69 private:           // Only accessable by IntervalPartition class
  70   inline Interval(BasicBlock *Header) : HeaderNode(Header) {
  71     Nodes.push_back(Header);
  72   }
  73 };
  74
  75
  76 // succ_begin/succ_end - define global functions so that Intervals may be used
  77 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
  78 //
  79 inline Interval::succ_iterator succ_begin(Interval *I) {
  80   return I->Successors.begin();
  81 }
  82 inline Interval::succ_iterator succ_end(Interval *I) {
  83   return I->Successors.end();
  84 }
  85
  86 // pred_begin/pred_end - define global functions so that Intervals may be used
  87 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
  88 //
  89 inline Interval::pred_iterator pred_begin(Interval *I) {
  90   return I->Predecessors.begin();
  91 }
  92 inline Interval::pred_iterator pred_end(Interval *I) {
  93   return I->Predecessors.end();
  94 }
  95
  96
  97
  98 // IntervalPartition - This class builds and holds an "interval partition" for
  99 // a method.  This partition divides the control flow graph into a set of
 100 // maximal intervals, as defined with the properties above.  Intuitively, a
 101 // BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
 102 // nodes following it.
 103 //
 104 class IntervalPartition {
 105   typedef map<BasicBlock*, Interval*> IntervalMapTy;
 106   IntervalMapTy IntervalMap;
 107
 108   typedef vector<Interval*> IntervalListTy;
 109   IntervalListTy IntervalList;
 110   Interval *RootInterval;
 111
 112 public:
 113   typedef IntervalListTy::iterator iterator;
 114
 115 public:
 116   // IntervalPartition ctor - Build the partition for the specified method
 117   IntervalPartition(Method *M);
 118
 119   // IntervalPartition ctor - Build a reduced interval partition from an
 120   // existing interval graph.  This takes an additional boolean parameter to
 121   // distinguish it from a copy constructor.  Always pass in false for now.
 122   //
 123   IntervalPartition(IntervalPartition &I, bool);
 124
 125   // Destructor - Free memory
 126   ~IntervalPartition();
 127
 128   // getRootInterval() - Return the root interval that contains the starting
 129   // block of the method.
 130   inline Interval *getRootInterval() { return RootInterval; }
 131
 132   // isDegeneratePartition() - Returns true if the interval partition contains
 133   // a single interval, and thus cannot be simplified anymore.
 134   bool isDegeneratePartition() { return size() == 1; }
 135
 136   // TODO: isIrreducible - look for triangle graph.
 137
 138   // getBlockInterval - Return the interval that a basic block exists in.
 139   inline Interval *getBlockInterval(BasicBlock *BB) {
 140     IntervalMapTy::iterator I = IntervalMap.find(BB);
 141     return I != IntervalMap.end() ? I->second : 0;
 142   }
 143
 144   // Iterators to iterate over all of the intervals in the method
 145   inline iterator begin() { return IntervalList.begin(); }
 146   inline iterator end()   { return IntervalList.end(); }
 147   inline unsigned size()  { return IntervalList.size(); }
 148
 149 private:
 150   // ProcessInterval - This method is used during the construction of the
 151   // interval graph.  It walks through the source graph, recursively creating
 152   // an interval per invokation until the entire graph is covered.  This uses
 153   // the ProcessNode method to add all of the nodes to the interval.
 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   template<class NodeTy, class OrigContainer>
 159   void ProcessInterval(NodeTy *Node, OrigContainer *OC);
 160
 161   // ProcessNode - This method is called by ProcessInterval to add nodes to the
 162   // interval being constructed, and it is also called recursively as it walks
 163   // the source graph.  A node is added to the current interval only if all of
 164   // its predecessors are already in the graph.  This also takes care of keeping
 165   // the successor set of an interval up to date.
 166   //
 167   // This method is templated because it may operate on two different source
 168   // graphs: a basic block graph, or a preexisting interval graph.
 169   //
 170   template<class NodeTy, class OrigContainer>
 171   void ProcessNode(Interval *Int, NodeTy *Node, OrigContainer *OC);
 172
 173   // addNodeToInterval - This method exists to assist the generic ProcessNode
 174   // with the task of adding a node to the new interval, depending on the
 175   // type of the source node.  In the case of a CFG source graph (BasicBlock
 176   // case), the BasicBlock itself is added to the interval.  In the case of
 177   // an IntervalPartition source graph (Interval case), all of the member
 178   // BasicBlocks are added to the interval.
 179   //
 180   inline void addNodeToInterval(Interval *Int, Interval *I);
 181   inline void addNodeToInterval(Interval *Int, BasicBlock *BB);
 182
 183   // updatePredecessors - Interval generation only sets the successor fields of
 184   // the interval data structures.  After interval generation is complete,
 185   // run through all of the intervals and propogate successor info as
 186   // predecessor info.
 187   //
 188   void updatePredecessors(Interval *Int);
 189 };
 190
 191 }    // End namespace cfg
 192
 193 #endif