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