lib/Analysis/Interval.cpp

   1 //===- Intervals.cpp - Interval partition Calculation ------------*- C++ -*--=//
   2 //
   3 // This file contains the declaration of the cfg::IntervalPartition class, which
   4 // calculates and represent the interval partition of a method.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/Analysis/Intervals.h"
   9 #include "llvm/Method.h"
  10 #include "llvm/BasicBlock.h"
  11 #include "llvm/CFG.h"
  12
  13 using namespace cfg;
  14
  15 //===----------------------------------------------------------------------===//
  16 // Interval Implementation
  17 //===----------------------------------------------------------------------===//
  18
  19 // isLoop - Find out if there is a back edge in this interval...
  20 //
  21 bool Interval::isLoop() const {
  22   // There is a loop in this interval iff one of the predecessors of the header
  23   // node lives in the interval.
  24   for (BasicBlock::pred_iterator I = pred_begin(HeaderNode),
  25                                  E = pred_end(HeaderNode); I != E; ++I) {
  26     if (contains(*I)) return true;
  27   }
  28   return false;
  29 }
  30
  31
  32 //===----------------------------------------------------------------------===//
  33 // IntervalPartition Implementation
  34 //===----------------------------------------------------------------------===//
  35
  36 template <class T> static inline void deleter(T *Ptr) { delete Ptr; }
  37
  38 // Destructor - Free memory
  39 IntervalPartition::~IntervalPartition() {
  40   for_each(begin(), end(), deleter<cfg::Interval>);
  41 }
  42
  43 #if 0
  44 // getNodeHeader - Given a source graph node and the source graph, return the
  45 // BasicBlock that is the header node.  This is the opposite of
  46 // getSourceGraphNode.
  47 //
  48 inline static BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
  49 inline static BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
  50
  51 // getSourceGraphNode - Given a BasicBlock and the source graph, return the
  52 // source graph node that corresponds to the BasicBlock.  This is the opposite
  53 // of getNodeHeader.
  54 //
  55 inline static BasicBlock *getSourceGraphNode(Method *, BasicBlock *BB) {
  56   return BB;
  57 }
  58 inline static Interval *getSourceGraphNode(IntervalPartition *IP,
  59                                            BasicBlock *BB) {
  60   return IP->getBlockInterval(BB);
  61 }
  62 #endif
  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.
  69 //
  70 inline void IntervalPartition::addNodeToInterval(Interval *Int, BasicBlock *BB){
  71   Int->Nodes.push_back(BB);
  72   IntervalMap.insert(make_pair(BB, Int));
  73 }
  74
  75 // addNodeToInterval - This method exists to assist the generic ProcessNode
  76 // with the task of adding a node to the new interval, depending on the
  77 // type of the source node.  In the case of a CFG source graph (BasicBlock
  78 // case), the BasicBlock itself is added to the interval.  In the case of
  79 // an IntervalPartition source graph (Interval case), all of the member
  80 // BasicBlocks are added to the interval.
  81 //
  82 inline void IntervalPartition::addNodeToInterval(Interval *Int, Interval *I) {
  83   // Add all of the nodes in I as new nodes in Int.
  84   copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes));
  85
  86   // Add mappings for all of the basic blocks in I to the IntervalPartition
  87   for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
  88        It != End; ++It)
  89     IntervalMap.insert(make_pair(*It, Int));
  90 }
  91
  92
  93 // ProcessNode - This method is called by ProcessInterval to add nodes to the
  94 // interval being constructed, and it is also called recursively as it walks
  95 // the source graph.  A node is added to the current interval only if all of
  96 // its predecessors are already in the graph.  This also takes care of keeping
  97 // the successor set of an interval up to date.
  98 //
  99 // This method is templated because it may operate on two different source
 100 // graphs: a basic block graph, or a preexisting interval graph.
 101 //
 102 template<class NodeTy, class OrigContainer>
 103 void IntervalPartition::ProcessNode(Interval *Int,
 104                                     NodeTy *Node, OrigContainer *OC) {
 105   assert(Int && "Null interval == bad!");
 106   assert(Node && "Null Node == bad!");
 107
 108   BasicBlock *NodeHeader = getNodeHeader(Node);
 109   Interval *CurInt = getBlockInterval(NodeHeader);
 110   if (CurInt == Int) {                  // Already in this interval...
 111     return;
 112   } else if (CurInt != 0) {             // In another interval, add as successor
 113     if (!Int->isSuccessor(NodeHeader))  // Add only if not already in set
 114       Int->Successors.push_back(NodeHeader);
 115   } else {                              // Otherwise, not in interval yet
 116     for (typename NodeTy::pred_iterator I = pred_begin(Node),
 117                                         E = pred_end(Node); I != E; ++I) {
 118       if (!Int->contains(*I)) {         // If pred not in interval, we can't be
 119         if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
 120           Int->Successors.push_back(NodeHeader);
 121         return;                         // See you later
 122       }
 123     }
 124
 125     // If we get here, then all of the predecessors of BB are in the interval
 126     // already.  In this case, we must add BB to the interval!
 127     addNodeToInterval(Int, Node);
 128
 129     if (Int->isSuccessor(NodeHeader)) {
 130       // If we were in the successor list from before... remove from succ list
 131       Int->Successors.erase(remove(Int->Successors.begin(),
 132                                    Int->Successors.end(), NodeHeader),
 133                             Int->Successors.end());
 134     }
 135
 136     // Now that we have discovered that Node is in the interval, perhaps some of
 137     // its successors are as well?
 138     for (typename NodeTy::succ_iterator It = succ_begin(Node),
 139                                        End = succ_end(Node); It != End; ++It)
 140       ProcessNode(Int, getSourceGraphNode(OC, *It), OC);
 141   }
 142 }
 143
 144
 145 // ProcessInterval - This method is used during the construction of the
 146 // interval graph.  It walks through the source graph, recursively creating
 147 // an interval per invokation until the entire graph is covered.  This uses
 148 // the ProcessNode method to add all of the nodes to the interval.
 149 //
 150 // This method is templated because it may operate on two different source
 151 // graphs: a basic block graph, or a preexisting interval graph.
 152 //
 153 template<class NodeTy, class OrigContainer>
 154 void IntervalPartition::ProcessInterval(NodeTy *Node, OrigContainer *OC) {
 155   BasicBlock *Header = getNodeHeader(Node);
 156   if (getBlockInterval(Header)) return;  // Interval already constructed?
 157
 158   // Create a new interval and add the interval to our current set
 159   Interval *Int = new Interval(Header);
 160   IntervalList.push_back(Int);
 161   IntervalMap.insert(make_pair(Header, Int));
 162
 163   // Check all of our successors to see if they are in the interval...
 164   for (typename NodeTy::succ_iterator I = succ_begin(Node), E = succ_end(Node);
 165        I != E; ++I)
 166     ProcessNode(Int, getSourceGraphNode(OC, *I), OC);
 167
 168   // Build all of the successor intervals of this interval now...
 169   for(Interval::succ_iterator I = Int->Successors.begin(),
 170                               E = Int->Successors.end(); I != E; ++I) {
 171     ProcessInterval(getSourceGraphNode(OC, *I), OC);
 172   }
 173 }
 174
 175
 176
 177 // updatePredecessors - Interval generation only sets the successor fields of
 178 // the interval data structures.  After interval generation is complete,
 179 // run through all of the intervals and propogate successor info as
 180 // predecessor info.
 181 //
 182 void IntervalPartition::updatePredecessors(cfg::Interval *Int) {
 183   BasicBlock *Header = Int->HeaderNode;
 184   for (Interval::succ_iterator I = Int->Successors.begin(),
 185                                E = Int->Successors.end(); I != E; ++I)
 186     getBlockInterval(*I)->Predecessors.push_back(Header);
 187 }
 188
 189
 190
 191 // IntervalPartition ctor - Build the first level interval partition for the
 192 // specified method...
 193 //
 194 IntervalPartition::IntervalPartition(Method *M) {
 195   BasicBlock *MethodStart = M->getBasicBlocks().front();
 196   assert(MethodStart && "Cannot operate on prototypes!");
 197
 198   ProcessInterval(MethodStart, M);
 199   RootInterval = getBlockInterval(MethodStart);
 200
 201   // Now that we know all of the successor information, propogate this to the
 202   // predecessors for each block...
 203   for(iterator I = begin(), E = end(); I != E; ++I)
 204     updatePredecessors(*I);
 205 }
 206
 207
 208 // IntervalPartition ctor - Build a reduced interval partition from an
 209 // existing interval graph.  This takes an additional boolean parameter to
 210 // distinguish it from a copy constructor.  Always pass in false for now.
 211 //
 212 IntervalPartition::IntervalPartition(IntervalPartition &I, bool) {
 213   Interval *MethodStart = I.getRootInterval();
 214   assert(MethodStart && "Cannot operate on empty IntervalPartitions!");
 215
 216   ProcessInterval(MethodStart, &I);
 217   RootInterval = getBlockInterval(*MethodStart->Nodes.begin());
 218
 219   // Now that we know all of the successor information, propogate this to the
 220   // predecessors for each block...
 221   for(iterator I = begin(), E = end(); I != E; ++I)
 222     updatePredecessors(*I);
 223 }