#include "Support/Debug.h"
#include "Support/Statistic.h"
#include "Support/STLExtras.h"
-#include "LiveIntervals.h"
+#include "LiveIntervalAnalysis.h"
#include "PhysRegTracker.h"
#include "VirtRegMap.h"
#include <algorithm>
#include <cmath>
-#include <iostream>
#include <set>
using namespace llvm;
const TargetMachine* tm_;
const MRegisterInfo* mri_;
LiveIntervals* li_;
- typedef std::list<LiveInterval*> IntervalPtrs;
+ typedef std::vector<LiveInterval*> IntervalPtrs;
IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_, spilled_;
std::auto_ptr<PhysRegTracker> prt_;
public:
virtual const char* getPassName() const {
- return "Linear Scan Register Allocator";
+ return "Iterative Scan Register Allocator";
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
/// initIntervalSets - initializes the four interval sets:
/// unhandled, fixed, active and inactive
- void initIntervalSets(LiveIntervals::Intervals& li);
+ void initIntervalSets();
/// processActiveIntervals - expire old intervals and move
/// non-overlapping ones to the incative list
vrm_.reset(new VirtRegMap(*mf_));
if (!spiller_.get()) spiller_.reset(createSpiller());
- initIntervalSets(li_->getIntervals());
+ initIntervalSets();
- numIntervals += li_->getIntervals().size();
+ numIntervals += li_->getNumIntervals();
while (linearScan()) {
// we spilled some registers, so we need to add intervals for
// the spill code and restart the algorithm
std::set<unsigned> spilledRegs;
for (IntervalPtrs::iterator
- i = spilled_.begin(); i != spilled_.end(); ) {
+ i = spilled_.begin(); i != spilled_.end(); ++i) {
int slot = vrm_->assignVirt2StackSlot((*i)->reg);
std::vector<LiveInterval*> added =
li_->addIntervalsForSpills(**i, *vrm_, slot);
std::copy(added.begin(), added.end(), std::back_inserter(handled_));
spilledRegs.insert((*i)->reg);
- i = spilled_.erase(i);
}
+ spilled_.clear();
for (IntervalPtrs::iterator
i = handled_.begin(); i != handled_.end(); )
if (spilledRegs.count((*i)->reg))
<< mf_->getFunction()->getName() << '\n');
- unhandled_.sort(less_ptr<LiveInterval>());
+ std::sort(unhandled_.begin(), unhandled_.end(),
+ greater_ptr<LiveInterval>());
DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
DEBUG(printIntervals("active", active_.begin(), active_.end()));
while (!unhandled_.empty()) {
// pick the interval with the earliest start point
- IntervalPtrs::value_type cur = unhandled_.front();
- unhandled_.pop_front();
+ IntervalPtrs::value_type cur = unhandled_.back();
+ unhandled_.pop_back();
++numIterations;
DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
}
// expire any remaining active intervals
- for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
+ for (IntervalPtrs::reverse_iterator
+ i = active_.rbegin(); i != active_.rend(); ) {
unsigned reg = (*i)->reg;
DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
if (MRegisterInfo::isVirtualRegister(reg))
reg = vrm_->getPhys(reg);
prt_->delRegUse(reg);
- i = active_.erase(i);
+ i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
}
// expire any remaining inactive intervals
- for (IntervalPtrs::iterator
- i = inactive_.begin(); i != inactive_.end(); ) {
+ for (IntervalPtrs::reverse_iterator
+ i = inactive_.rbegin(); i != inactive_.rend(); ) {
DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
- i = inactive_.erase(i);
+ i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
}
// return true if we spilled anything
return !spilled_.empty();
}
-void RA::initIntervalSets(LiveIntervals::Intervals& li)
-{
+void RA::initIntervalSets() {
assert(unhandled_.empty() && fixed_.empty() &&
active_.empty() && inactive_.empty() &&
"interval sets should be empty on initialization");
- for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
- i != e; ++i) {
- unhandled_.push_back(&*i);
- if (MRegisterInfo::isPhysicalRegister(i->reg))
- fixed_.push_back(&*i);
+ for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
+ unhandled_.push_back(&i->second);
+ if (MRegisterInfo::isPhysicalRegister(i->second.reg))
+ fixed_.push_back(&i->second);
}
}
void RA::processActiveIntervals(IntervalPtrs::value_type cur)
{
DEBUG(std::cerr << "\tprocessing active intervals:\n");
- for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
+ for (IntervalPtrs::reverse_iterator
+ i = active_.rbegin(); i != active_.rend();) {
unsigned reg = (*i)->reg;
// remove expired intervals
if ((*i)->expiredAt(cur->start())) {
reg = vrm_->getPhys(reg);
prt_->delRegUse(reg);
// remove from active
- i = active_.erase(i);
+ i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
}
// move inactive intervals to inactive list
else if (!(*i)->liveAt(cur->start())) {
// add to inactive
inactive_.push_back(*i);
// remove from active
- i = active_.erase(i);
+ i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
}
else {
++i;
void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
{
DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
- for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
+ for (IntervalPtrs::reverse_iterator
+ i = inactive_.rbegin(); i != inactive_.rend();) {
unsigned reg = (*i)->reg;
// remove expired intervals
if ((*i)->expiredAt(cur->start())) {
DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
// remove from inactive
- i = inactive_.erase(i);
+ i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
}
// move re-activated intervals in active list
else if ((*i)->liveAt(cur->start())) {
// add to active
active_.push_back(*i);
// remove from inactive
- i = inactive_.erase(i);
+ i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
}
else {
++i;
// otherwise we spill all intervals aliasing the register with
// minimum weight, assigned the newly cleared register to the
// current interval and continue
- std::vector<LiveInterval*> added;
assert(MRegisterInfo::isPhysicalRegister(minReg) &&
"did not choose a register to spill?");
std::vector<bool> toSpill(mri_->getNumRegs(), false);