lib/Analysis/IntervalPartition.cpp

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