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