lib/Analysis/IntervalPartition.cpp

   1 //===- IntervalPartition.cpp - Interval Partition module code ----*- C++ -*--=//
   2 //
   3 // This file contains the definition of the IntervalPartition class, which
   4 // calculates and represent the interval partition of a function.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/Analysis/IntervalIterator.h"
   9 #include "Support/STLExtras.h"
  10
  11 using std::make_pair;
  12
  13 static RegisterAnalysis<IntervalPartition>
  14 X("intervals", "Interval Partition Construction", true);
  15
  16 AnalysisID IntervalPartition::ID = X;
  17
  18 //===----------------------------------------------------------------------===//
  19 // IntervalPartition Implementation
  20 //===----------------------------------------------------------------------===//
  21
  22 // destroy - Reset state back to before function was analyzed
  23 void IntervalPartition::destroy() {
  24   for_each(Intervals.begin(), Intervals.end(), deleter<Interval>);
  25   IntervalMap.clear();
  26   RootInterval = 0;
  27 }
  28
  29 void IntervalPartition::print(std::ostream &O) const {
  30   std::copy(Intervals.begin(), Intervals.end(),
  31             std::ostream_iterator<const Interval *>(O, "\n"));
  32 }
  33
  34 // addIntervalToPartition - Add an interval to the internal list of intervals,
  35 // and then add mappings from all of the basic blocks in the interval to the
  36 // interval itself (in the IntervalMap).
  37 //
  38 void IntervalPartition::addIntervalToPartition(Interval *I) {
  39   Intervals.push_back(I);
  40
  41   // Add mappings for all of the basic blocks in I to the IntervalPartition
  42   for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
  43        It != End; ++It)
  44     IntervalMap.insert(make_pair(*It, I));
  45 }
  46
  47 // updatePredecessors - Interval generation only sets the successor fields of
  48 // the interval data structures.  After interval generation is complete,
  49 // run through all of the intervals and propogate successor info as
  50 // predecessor info.
  51 //
  52 void IntervalPartition::updatePredecessors(Interval *Int) {
  53   BasicBlock *Header = Int->getHeaderNode();
  54   for (Interval::succ_iterator I = Int->Successors.begin(),
  55                                E = Int->Successors.end(); I != E; ++I)
  56     getBlockInterval(*I)->Predecessors.push_back(Header);
  57 }
  58
  59 // IntervalPartition ctor - Build the first level interval partition for the
  60 // specified function...
  61 //
  62 bool IntervalPartition::runOnFunction(Function &F) {
  63   // Pass false to intervals_begin because we take ownership of it's memory
  64   function_interval_iterator I = intervals_begin(&F, false);
  65   assert(I != intervals_end(&F) && "No intervals in function!?!?!");
  66
  67   addIntervalToPartition(RootInterval = *I);
  68
  69   ++I;  // After the first one...
  70
  71   // Add the rest of the intervals to the partition...
  72   for_each(I, intervals_end(&F),
  73            bind_obj(this, &IntervalPartition::addIntervalToPartition));
  74
  75   // Now that we know all of the successor information, propogate this to the
  76   // predecessors for each block...
  77   for_each(Intervals.begin(), Intervals.end(),
  78            bind_obj(this, &IntervalPartition::updatePredecessors));
  79   return false;
  80 }
  81
  82
  83 // IntervalPartition ctor - Build a reduced interval partition from an
  84 // existing interval graph.  This takes an additional boolean parameter to
  85 // distinguish it from a copy constructor.  Always pass in false for now.
  86 //
  87 IntervalPartition::IntervalPartition(IntervalPartition &IP, bool) {
  88   Interval *FunctionStart = IP.getRootInterval();
  89   assert(FunctionStart && "Cannot operate on empty IntervalPartitions!");
  90
  91   // Pass false to intervals_begin because we take ownership of it's memory
  92   interval_part_interval_iterator I = intervals_begin(IP, false);
  93   assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!");
  94
  95   addIntervalToPartition(RootInterval = *I);
  96
  97   ++I;  // After the first one...
  98
  99   // Add the rest of the intervals to the partition...
 100   for_each(I, intervals_end(IP),
 101            bind_obj(this, &IntervalPartition::addIntervalToPartition));
 102
 103   // Now that we know all of the successor information, propogate this to the
 104   // predecessors for each block...
 105   for_each(Intervals.begin(), Intervals.end(),
 106            bind_obj(this, &IntervalPartition::updatePredecessors));
 107 }