#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
-#include "LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "PhysRegTracker.h"
#include "VirtRegMap.h"
#include <algorithm>
const TargetMachine* tm_;
const MRegisterInfo* mri_;
LiveIntervals* li_;
+ bool *PhysRegsUsed;
typedef std::vector<LiveInterval*> IntervalPtrs;
IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_, spilled_;
tm_ = &fn.getTarget();
mri_ = tm_->getRegisterInfo();
li_ = &getAnalysis<LiveIntervals>();
+
+ PhysRegsUsed = new bool[mri_->getNumRegs()];
+ std::fill(PhysRegsUsed, PhysRegsUsed+mri_->getNumRegs(), false);
+ fn.setUsedPhysRegs(PhysRegsUsed);
+
if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
vrm_.reset(new VirtRegMap(*mf_));
if (!spiller_.get()) spiller_.reset(createSpiller());
for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
unhandled_.push_back(&i->second);
- if (MRegisterInfo::isPhysicalRegister(i->second.reg))
+ if (MRegisterInfo::isPhysicalRegister(i->second.reg)) {
+ PhysRegsUsed[i->second.reg] = true;
fixed_.push_back(&i->second);
+ }
}
}
unsigned reg = i->reg;
// remove expired intervals
- if (i->expiredAt(cur->start())) {
+ if (i->expiredAt(cur->beginNumber())) {
DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
if (MRegisterInfo::isVirtualRegister(reg))
reg = vrm_->getPhys(reg);
std::iter_swap(ii, --ie);
}
// move inactive intervals to inactive list
- else if (!i->liveAt(cur->start())) {
+ else if (!i->liveAt(cur->beginNumber())) {
DEBUG(std::cerr << "\t\tinterval " << *i << " inactive\n");
if (MRegisterInfo::isVirtualRegister(reg))
reg = vrm_->getPhys(reg);
unsigned reg = i->reg;
// remove expired intervals
- if (i->expiredAt(cur->start())) {
+ if (i->expiredAt(cur->beginNumber())) {
DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
// swap with last element and move end iterator back one position
std::iter_swap(ii, --ie);
}
// move re-activated intervals in active list
- else if (i->liveAt(cur->start())) {
+ else if (i->liveAt(cur->beginNumber())) {
DEBUG(std::cerr << "\t\tinterval " << *i << " active\n");
if (MRegisterInfo::isVirtualRegister(reg))
reg = vrm_->getPhys(reg);
DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
- float minWeight = HUGE_VAL;
+ float minWeight = (float)HUGE_VAL;
unsigned minReg = 0;
const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
- for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
- i != rc->allocation_order_end(*mf_); ++i) {
+ for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
+ e = rc->allocation_order_end(*mf_); i != e; ++i) {
unsigned reg = *i;
if (minWeight > spillWeights_[reg]) {
minWeight = spillWeights_[reg];
toSpill[minReg] = true;
for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
toSpill[*as] = true;
- unsigned earliestStart = cur->start();
+ unsigned earliestStart = cur->beginNumber();
std::set<unsigned> spilled;
}
-unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
+unsigned RA::getFreePhysReg(LiveInterval* cur)
{
+ std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
+ for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
+ i != e; ++i) {
+ unsigned reg = (*i)->reg;
+ if (MRegisterInfo::isVirtualRegister(reg))
+ reg = vrm_->getPhys(reg);
+ ++inactiveCounts[reg];
+ }
+
const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
- for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
- i != rc->allocation_order_end(*mf_); ++i) {
+ unsigned freeReg = 0;
+ for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
+ e = rc->allocation_order_end(*mf_); i != e; ++i) {
unsigned reg = *i;
- if (prt_->isRegAvail(reg))
- return reg;
+ if (prt_->isRegAvail(reg) &&
+ (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
+ freeReg = reg;
}
- return 0;
+ return freeReg;
}
FunctionPass* llvm::createIterativeScanRegisterAllocator() {