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