1 //===- IntervalPartition.cpp - Interval Partition module code ----*- C++ -*--=//
3 // This file contains the definition of the cfg::IntervalPartition class, which
4 // calculates and represent the interval partition of a method.
6 //===----------------------------------------------------------------------===//
8 #include "llvm/Analysis/IntervalIterator.h"
9 #include "llvm/Tools/STLExtras.h"
13 //===----------------------------------------------------------------------===//
14 // IntervalPartition Implementation
15 //===----------------------------------------------------------------------===//
17 template <class T> static inline void deleter(T *Ptr) { delete Ptr; }
19 // Destructor - Free memory
20 IntervalPartition::~IntervalPartition() {
21 for_each(begin(), end(), deleter<cfg::Interval>);
24 // addIntervalToPartition - Add an interval to the internal list of intervals,
25 // and then add mappings from all of the basic blocks in the interval to the
26 // interval itself (in the IntervalMap).
28 void IntervalPartition::addIntervalToPartition(Interval *I) {
29 IntervalList.push_back(I);
31 // Add mappings for all of the basic blocks in I to the IntervalPartition
32 for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end();
34 IntervalMap.insert(make_pair(*It, I));
37 // updatePredecessors - Interval generation only sets the successor fields of
38 // the interval data structures. After interval generation is complete,
39 // run through all of the intervals and propogate successor info as
42 void IntervalPartition::updatePredecessors(cfg::Interval *Int) {
43 BasicBlock *Header = Int->getHeaderNode();
44 for (Interval::succ_iterator I = Int->Successors.begin(),
45 E = Int->Successors.end(); I != E; ++I)
46 getBlockInterval(*I)->Predecessors.push_back(Header);
49 // IntervalPartition ctor - Build the first level interval partition for the
50 // specified method...
52 IntervalPartition::IntervalPartition(Method *M) {
53 assert(M->front() && "Cannot operate on prototypes!");
55 // Pass false to intervals_begin because we take ownership of it's memory
56 method_interval_iterator I = intervals_begin(M, false);
57 assert(I != intervals_end(M) && "No intervals in method!?!?!");
59 addIntervalToPartition(RootInterval = *I);
61 ++I; // After the first one...
63 // Add the rest of the intervals to the partition...
64 for_each(I, intervals_end(M),
65 bind_obj(this, &IntervalPartition::addIntervalToPartition));
67 // Now that we know all of the successor information, propogate this to the
68 // predecessors for each block...
69 for_each(begin(), end(),
70 bind_obj(this, &IntervalPartition::updatePredecessors));
74 // IntervalPartition ctor - Build a reduced interval partition from an
75 // existing interval graph. This takes an additional boolean parameter to
76 // distinguish it from a copy constructor. Always pass in false for now.
78 IntervalPartition::IntervalPartition(IntervalPartition &IP, bool) {
79 Interval *MethodStart = IP.getRootInterval();
80 assert(MethodStart && "Cannot operate on empty IntervalPartitions!");
82 // Pass false to intervals_begin because we take ownership of it's memory
83 interval_part_interval_iterator I = intervals_begin(IP, false);
84 assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!");
86 addIntervalToPartition(RootInterval = *I);
88 ++I; // After the first one...
90 // Add the rest of the intervals to the partition...
91 for_each(I, intervals_end(IP),
92 bind_obj(this, &IntervalPartition::addIntervalToPartition));
94 // Now that we know all of the successor information, propogate this to the
95 // predecessors for each block...
96 for_each(begin(), end(),
97 bind_obj(this, &IntervalPartition::updatePredecessors));