#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "Support/Debug.h"
-#include "Support/Statistic.h"
-#include "Support/STLExtras.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
#include "LiveIntervalAnalysis.h"
#include "PhysRegTracker.h"
#include "VirtRegMap.h"
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);
+ }
}
}
void RA::processActiveIntervals(IntervalPtrs::value_type cur)
{
DEBUG(std::cerr << "\tprocessing active intervals:\n");
- for (IntervalPtrs::reverse_iterator
- i = active_.rbegin(); i != active_.rend();) {
- unsigned reg = (*i)->reg;
+ IntervalPtrs::iterator ii = active_.begin(), ie = active_.end();
+ while (ii != ie) {
+ LiveInterval* i = *ii;
+ unsigned reg = i->reg;
+
// remove expired intervals
- if ((*i)->expiredAt(cur->start())) {
- DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
+ if (i->expiredAt(cur->beginNumber())) {
+ DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
if (MRegisterInfo::isVirtualRegister(reg))
reg = vrm_->getPhys(reg);
prt_->delRegUse(reg);
- // remove from active
- i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
+ // swap with last element and move end iterator back one position
+ std::iter_swap(ii, --ie);
}
// move inactive intervals to inactive list
- else if (!(*i)->liveAt(cur->start())) {
- DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
+ else if (!i->liveAt(cur->beginNumber())) {
+ DEBUG(std::cerr << "\t\tinterval " << *i << " inactive\n");
if (MRegisterInfo::isVirtualRegister(reg))
reg = vrm_->getPhys(reg);
prt_->delRegUse(reg);
// add to inactive
- inactive_.push_back(*i);
- // remove from active
- i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
+ inactive_.push_back(i);
+ // swap with last element and move end iterator back one postion
+ std::iter_swap(ii, --ie);
}
else {
- ++i;
+ ++ii;
}
}
+ active_.erase(ie, active_.end());
}
void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
{
DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
- for (IntervalPtrs::reverse_iterator
- i = inactive_.rbegin(); i != inactive_.rend();) {
- unsigned reg = (*i)->reg;
+ IntervalPtrs::iterator ii = inactive_.begin(), ie = inactive_.end();
+ while (ii != ie) {
+ LiveInterval* i = *ii;
+ unsigned reg = i->reg;
// remove expired intervals
- if ((*i)->expiredAt(cur->start())) {
- DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
- // remove from inactive
- i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
+ 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())) {
- DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
+ else if (i->liveAt(cur->beginNumber())) {
+ DEBUG(std::cerr << "\t\tinterval " << *i << " active\n");
if (MRegisterInfo::isVirtualRegister(reg))
reg = vrm_->getPhys(reg);
prt_->addRegUse(reg);
// add to active
- active_.push_back(*i);
- // remove from inactive
- i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
+ active_.push_back(i);
+ // swap with last element and move end iterator back one position
+ std::iter_swap(ii, --ie);
}
else {
- ++i;
+ ++ii;
}
}
+ inactive_.erase(ie, inactive_.end());
}
void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
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() {
projects / oota-llvm.git / blobdiff