1193323Sed//===- IntervalPartition.cpp - Interval Partition module code -------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains the definition of the IntervalPartition class, which 11193323Sed// calculates and represent the interval partition of a function. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/Analysis/IntervalIterator.h" 16193323Sedusing namespace llvm; 17193323Sed 18193323Sedchar IntervalPartition::ID = 0; 19212904SdimINITIALIZE_PASS(IntervalPartition, "intervals", 20218893Sdim "Interval Partition Construction", true, true) 21193323Sed 22193323Sed//===----------------------------------------------------------------------===// 23193323Sed// IntervalPartition Implementation 24193323Sed//===----------------------------------------------------------------------===// 25193323Sed 26193323Sed// releaseMemory - Reset state back to before function was analyzed 27193323Sedvoid IntervalPartition::releaseMemory() { 28193323Sed for (unsigned i = 0, e = Intervals.size(); i != e; ++i) 29193323Sed delete Intervals[i]; 30193323Sed IntervalMap.clear(); 31193323Sed Intervals.clear(); 32193323Sed RootInterval = 0; 33193323Sed} 34193323Sed 35198090Srdivackyvoid IntervalPartition::print(raw_ostream &O, const Module*) const { 36193323Sed for(unsigned i = 0, e = Intervals.size(); i != e; ++i) 37193323Sed Intervals[i]->print(O); 38193323Sed} 39193323Sed 40193323Sed// addIntervalToPartition - Add an interval to the internal list of intervals, 41193323Sed// and then add mappings from all of the basic blocks in the interval to the 42193323Sed// interval itself (in the IntervalMap). 43193323Sed// 44193323Sedvoid IntervalPartition::addIntervalToPartition(Interval *I) { 45193323Sed Intervals.push_back(I); 46193323Sed 47193323Sed // Add mappings for all of the basic blocks in I to the IntervalPartition 48193323Sed for (Interval::node_iterator It = I->Nodes.begin(), End = I->Nodes.end(); 49193323Sed It != End; ++It) 50193323Sed IntervalMap.insert(std::make_pair(*It, I)); 51193323Sed} 52193323Sed 53193323Sed// updatePredecessors - Interval generation only sets the successor fields of 54193323Sed// the interval data structures. After interval generation is complete, 55193323Sed// run through all of the intervals and propagate successor info as 56193323Sed// predecessor info. 57193323Sed// 58193323Sedvoid IntervalPartition::updatePredecessors(Interval *Int) { 59193323Sed BasicBlock *Header = Int->getHeaderNode(); 60193323Sed for (Interval::succ_iterator I = Int->Successors.begin(), 61193323Sed E = Int->Successors.end(); I != E; ++I) 62193323Sed getBlockInterval(*I)->Predecessors.push_back(Header); 63193323Sed} 64193323Sed 65193323Sed// IntervalPartition ctor - Build the first level interval partition for the 66193323Sed// specified function... 67193323Sed// 68193323Sedbool IntervalPartition::runOnFunction(Function &F) { 69193323Sed // Pass false to intervals_begin because we take ownership of it's memory 70193323Sed function_interval_iterator I = intervals_begin(&F, false); 71193323Sed assert(I != intervals_end(&F) && "No intervals in function!?!?!"); 72193323Sed 73193323Sed addIntervalToPartition(RootInterval = *I); 74193323Sed 75193323Sed ++I; // After the first one... 76193323Sed 77193323Sed // Add the rest of the intervals to the partition. 78193323Sed for (function_interval_iterator E = intervals_end(&F); I != E; ++I) 79193323Sed addIntervalToPartition(*I); 80193323Sed 81193323Sed // Now that we know all of the successor information, propagate this to the 82193323Sed // predecessors for each block. 83193323Sed for (unsigned i = 0, e = Intervals.size(); i != e; ++i) 84193323Sed updatePredecessors(Intervals[i]); 85193323Sed return false; 86193323Sed} 87193323Sed 88193323Sed 89193323Sed// IntervalPartition ctor - Build a reduced interval partition from an 90193323Sed// existing interval graph. This takes an additional boolean parameter to 91193323Sed// distinguish it from a copy constructor. Always pass in false for now. 92193323Sed// 93193323SedIntervalPartition::IntervalPartition(IntervalPartition &IP, bool) 94212904Sdim : FunctionPass(ID) { 95193323Sed assert(IP.getRootInterval() && "Cannot operate on empty IntervalPartitions!"); 96193323Sed 97193323Sed // Pass false to intervals_begin because we take ownership of it's memory 98193323Sed interval_part_interval_iterator I = intervals_begin(IP, false); 99193323Sed assert(I != intervals_end(IP) && "No intervals in interval partition!?!?!"); 100193323Sed 101193323Sed addIntervalToPartition(RootInterval = *I); 102193323Sed 103193323Sed ++I; // After the first one... 104193323Sed 105193323Sed // Add the rest of the intervals to the partition. 106193323Sed for (interval_part_interval_iterator E = intervals_end(IP); I != E; ++I) 107193323Sed addIntervalToPartition(*I); 108193323Sed 109193323Sed // Now that we know all of the successor information, propagate this to the 110193323Sed // predecessors for each block. 111193323Sed for (unsigned i = 0, e = Intervals.size(); i != e; ++i) 112193323Sed updatePredecessors(Intervals[i]); 113193323Sed} 114193323Sed 115