X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=4c44d9201cb67841b4d21f76cc0334206f656e35;hb=c998981505023a79ea96fe871b68512d08704e65;hp=49e33d86f5dacc1e21a179c4c2aef9438349a1c5;hpb=75ca6a3e828332de32caac572275e889a2848bf0;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 49e33d86f5d..4c44d9201cb 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -10,63 +10,55 @@ // This file implements a linear scan register allocator. // //===----------------------------------------------------------------------===// + #define DEBUG_TYPE "regalloc" #include "llvm/Function.h" -#include "llvm/CodeGen/LiveIntervals.h" #include "llvm/CodeGen/LiveVariables.h" -#include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/SSARegMap.h" #include "llvm/Target/MRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" -#include "llvm/Support/CFG.h" #include "Support/Debug.h" -#include "Support/DepthFirstIterator.h" #include "Support/Statistic.h" #include "Support/STLExtras.h" +#include "LiveIntervalAnalysis.h" +#include "PhysRegTracker.h" +#include "VirtRegMap.h" +#include +#include +#include +#include + using namespace llvm; namespace { - Statistic<> numSpilled ("ra-linearscan", "Number of registers spilled"); - Statistic<> numReloaded("ra-linearscan", "Number of registers reloaded"); - class RA : public MachineFunctionPass { - public: - typedef std::vector IntervalPtrs; + Statistic efficiency + ("regalloc", "Ratio of intervals processed over total intervals"); + + static unsigned numIterations = 0; + static unsigned numIntervals = 0; + class RA : public MachineFunctionPass { private: MachineFunction* mf_; const TargetMachine* tm_; const MRegisterInfo* mri_; - MachineBasicBlock* currentMbb_; - MachineBasicBlock::iterator currentInstr_; - typedef LiveIntervals::Intervals Intervals; - const Intervals* li_; - IntervalPtrs active_, inactive_; - - typedef std::vector Regs; - Regs tempUseOperands_; - Regs tempDefOperands_; - - typedef std::vector RegMask; - RegMask reserved_; - - unsigned regUse_[MRegisterInfo::FirstVirtualRegister]; - unsigned regUseBackup_[MRegisterInfo::FirstVirtualRegister]; - - typedef LiveIntervals::MachineBasicBlockPtrs MachineBasicBlockPtrs; - MachineBasicBlockPtrs mbbs_; - - typedef std::map Virt2PhysMap; - Virt2PhysMap v2pMap_; - - typedef std::map Virt2StackSlotMap; - Virt2StackSlotMap v2ssMap_; - - int instrAdded_; + LiveIntervals* li_; + typedef std::vector IntervalPtrs; + IntervalPtrs handled_, fixed_, active_, inactive_; + typedef std::priority_queue > IntervalHeap; + IntervalHeap unhandled_; + std::auto_ptr prt_; + std::auto_ptr vrm_; + std::auto_ptr spiller_; + + typedef std::vector SpillWeights; + SpillWeights spillWeights_; public: virtual const char* getPassName() const { @@ -79,23 +71,34 @@ namespace { MachineFunctionPass::getAnalysisUsage(AU); } - private: /// runOnMachineFunction - register allocate the whole function bool runOnMachineFunction(MachineFunction&); + void releaseMemory(); + + private: + /// linearScan - the linear scan algorithm + void linearScan(); + + /// initIntervalSets - initializa the four interval sets: + /// unhandled, fixed, active and inactive + void initIntervalSets(); + /// processActiveIntervals - expire old intervals and move /// non-overlapping ones to the incative list - void processActiveIntervals(Intervals::const_iterator cur); + void processActiveIntervals(LiveInterval* cur); /// processInactiveIntervals - expire old intervals and move /// overlapping ones to the active list - void processInactiveIntervals(Intervals::const_iterator cur); + void processInactiveIntervals(LiveInterval* cur); - /// assignStackSlotAtInterval - choose and spill - /// interval. Currently we spill the interval with the last - /// end point in the active and inactive lists and the current - /// interval - void assignStackSlotAtInterval(Intervals::const_iterator cur); + /// updateSpillWeights - updates the spill weights of the + /// specifed physical register and its weight + void updateSpillWeights(unsigned reg, SpillWeights::value_type weight); + + /// assignRegOrStackSlotAtInterval - assign a register if one + /// is available, or spill. + void assignRegOrStackSlotAtInterval(LiveInterval* cur); /// /// register handling helpers @@ -104,335 +107,154 @@ namespace { /// getFreePhysReg - return a free physical register for this /// virtual register interval if we have one, otherwise return /// 0 - unsigned getFreePhysReg(Intervals::const_iterator cur); - - /// physRegAvailable - returns true if the specifed physical - /// register is available - bool physRegAvailable(unsigned physReg); - - /// tempPhysRegAvailable - returns true if the specifed - /// temporary physical register is available - bool tempPhysRegAvailable(unsigned physReg); - - /// getFreeTempPhysReg - return a free temprorary physical - /// register for this virtual register if we have one (should - /// never return 0) - unsigned getFreeTempPhysReg(unsigned virtReg); - - /// assignVirt2PhysReg - assigns the free physical register to - /// the virtual register passed as arguments - void assignVirt2PhysReg(unsigned virtReg, unsigned physReg); - - /// clearVirtReg - free the physical register associated with this - /// virtual register and disassociate virtual->physical and - /// physical->virtual mappings - void clearVirtReg(unsigned virtReg); + unsigned getFreePhysReg(LiveInterval* cur); /// assignVirt2StackSlot - assigns this virtual register to a - /// stack slot - void assignVirt2StackSlot(unsigned virtReg); - - /// getStackSlot - returns the offset of the specified - /// register on the stack - int getStackSlot(unsigned virtReg); - - /// spillVirtReg - spills the virtual register - void spillVirtReg(unsigned virtReg); - - /// loadPhysReg - loads to the physical register the value of - /// the virtual register specifed. Virtual register must have - /// an assigned stack slot - void loadVirt2PhysReg(unsigned virtReg, unsigned physReg); - - void markPhysRegFree(unsigned physReg); - void markPhysRegNotFree(unsigned physReg); - - void backupRegUse() { - memcpy(regUseBackup_, regUse_, sizeof(regUseBackup_)); - } + /// stack slot. returns the stack slot + int assignVirt2StackSlot(unsigned virtReg); - void restoreRegUse() { - memcpy(regUse_, regUseBackup_, sizeof(regUseBackup_)); - } - - void printVirt2PhysMap() const { - std::cerr << "allocated registers:\n"; - for (Virt2PhysMap::const_iterator - i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) { - std::cerr << '[' << i->first << ',' - << mri_->getName(i->second) << "]\n"; - } - std::cerr << '\n'; - } - void printIntervals(const char* const str, - RA::IntervalPtrs::const_iterator i, - RA::IntervalPtrs::const_iterator e) const { + template + void printIntervals(const char* const str, ItTy i, ItTy e) const { if (str) std::cerr << str << " intervals:\n"; for (; i != e; ++i) { - std::cerr << "\t\t" << **i << " -> "; - if ((*i)->reg < MRegisterInfo::FirstVirtualRegister) { - std::cerr << mri_->getName((*i)->reg); - } - else { - std::cerr << mri_->getName(v2pMap_.find((*i)->reg)->second); + std::cerr << "\t" << **i << " -> "; + unsigned reg = (*i)->reg; + if (MRegisterInfo::isVirtualRegister(reg)) { + reg = vrm_->getPhys(reg); } - std::cerr << '\n'; + std::cerr << mri_->getName(reg) << '\n'; } } - void printFreeRegs(const char* const str, - const TargetRegisterClass* rc) const { - if (str) std::cerr << str << ':'; - for (TargetRegisterClass::iterator i = - rc->allocation_order_begin(*mf_); - i != rc->allocation_order_end(*mf_); ++i) { - unsigned reg = *i; - if (!regUse_[reg]) { - std::cerr << ' ' << mri_->getName(reg); - if (reserved_[reg]) std::cerr << "*"; - } - } - std::cerr << '\n'; - } }; } +void RA::releaseMemory() +{ + while (!unhandled_.empty()) unhandled_.pop(); + fixed_.clear(); + active_.clear(); + inactive_.clear(); + handled_.clear(); +} + bool RA::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; tm_ = &fn.getTarget(); mri_ = tm_->getRegisterInfo(); - li_ = &getAnalysis().getIntervals(); - active_.clear(); - inactive_.clear(); + li_ = &getAnalysis(); + if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_)); + vrm_.reset(new VirtRegMap(*mf_)); + if (!spiller_.get()) spiller_.reset(createSpiller()); - mbbs_ = getAnalysis().getOrderedMachineBasicBlockPtrs(); - v2pMap_.clear(); - v2ssMap_.clear(); - memset(regUse_, 0, sizeof(regUse_)); - memset(regUseBackup_, 0, sizeof(regUseBackup_)); - - DEBUG( - unsigned i = 0; - for (MachineBasicBlockPtrs::iterator - mbbi = mbbs_.begin(), mbbe = mbbs_.end(); - mbbi != mbbe; ++mbbi) { - MachineBasicBlock* mbb = *mbbi; - std::cerr << mbb->getBasicBlock()->getName() << '\n'; - for (MachineBasicBlock::iterator - ii = mbb->begin(), ie = mbb->end(); - ii != ie; ++ii) { - MachineInstr* instr = *ii; - - std::cerr << i++ << "\t"; - instr->print(std::cerr, *tm_); - } - } - ); - - // FIXME: this will work only for the X86 backend. I need to - // device an algorthm to select the minimal (considering register - // aliasing) number of temp registers to reserve so that we have 2 - // registers for each register class available. - - // reserve R8: CH, CL - // R16: CX, DI, - // R32: ECX, EDI, - // RFP: FP5, FP6 - reserved_.assign(MRegisterInfo::FirstVirtualRegister, false); - reserved_[ 8] = true; /* CH */ - reserved_[ 9] = true; /* CL */ - reserved_[10] = true; /* CX */ - reserved_[12] = true; /* DI */ - reserved_[18] = true; /* ECX */ - reserved_[19] = true; /* EDI */ - reserved_[28] = true; /* FP5 */ - reserved_[29] = true; /* FP6 */ - - // liner scan algorithm - for (Intervals::const_iterator - i = li_->begin(), e = li_->end(); i != e; ++i) { - DEBUG(std::cerr << "processing current interval: " << *i << '\n'); - - DEBUG(printIntervals("\tactive", active_.begin(), active_.end())); - DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end())); - processActiveIntervals(i); - processInactiveIntervals(i); - - backupRegUse(); - - // for every interval in inactive we overlap mark the register - // as not free - for (IntervalPtrs::iterator j = inactive_.begin(); - j != inactive_.end(); ++j) { - unsigned reg = (*j)->reg; - if (reg >= MRegisterInfo::FirstVirtualRegister) - reg = v2pMap_[reg]; - - if (i->overlaps(**j)) { - markPhysRegNotFree(reg); - } - } + initIntervalSets(); - // for every pre-allocated interval in unhandled we overlap - // mark the register as not free - for (Intervals::const_iterator j = i + 1; j != e; ++j) { - if (j->reg < MRegisterInfo::FirstVirtualRegister && - i->overlaps(*j)) - markPhysRegNotFree(j->reg); - } + linearScan(); + + spiller_->runOnMachineFunction(*mf_, *vrm_); + + return true; +} - DEBUG(std::cerr << "\tallocating current interval:\n"); - // if this register is preallocated reserve it - if (i->reg < MRegisterInfo::FirstVirtualRegister) { - restoreRegUse(); - markPhysRegNotFree(i->reg); - active_.push_back(&*i); +void RA::linearScan() +{ + // linear scan algorithm + DEBUG(std::cerr << "********** LINEAR SCAN **********\n"); + DEBUG(std::cerr << "********** Function: " + << mf_->getFunction()->getName() << '\n'); + + // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end())); + DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end())); + DEBUG(printIntervals("active", active_.begin(), active_.end())); + DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); + + while (!unhandled_.empty()) { + // pick the interval with the earliest start point + LiveInterval* cur = unhandled_.top(); + unhandled_.pop(); + ++numIterations; + DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n'); + + processActiveIntervals(cur); + processInactiveIntervals(cur); + + // if this register is fixed we are done + if (MRegisterInfo::isPhysicalRegister(cur->reg)) { + prt_->addRegUse(cur->reg); + active_.push_back(cur); + handled_.push_back(cur); } // otherwise we are allocating a virtual register. try to find // a free physical register or spill an interval in order to // assign it one (we could spill the current though). else { - unsigned physReg = getFreePhysReg(i); - if (!physReg) { - assignStackSlotAtInterval(i); - } - else { - restoreRegUse(); - assignVirt2PhysReg(i->reg, physReg); - active_.push_back(&*i); - } + assignRegOrStackSlotAtInterval(cur); } + + DEBUG(printIntervals("active", active_.begin(), active_.end())); + DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); } + numIntervals += li_->getNumIntervals(); + efficiency = double(numIterations) / double(numIntervals); + // expire any remaining active intervals - for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { + for (IntervalPtrs::reverse_iterator + i = active_.rbegin(); i != active_.rend(); ) { unsigned reg = (*i)->reg; - DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); - if (reg >= MRegisterInfo::FirstVirtualRegister) { - reg = v2pMap_[reg]; - } - markPhysRegFree(reg); + DEBUG(std::cerr << "\tinterval " << **i << " expired\n"); + if (MRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + prt_->delRegUse(reg); + i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); } - DEBUG(std::cerr << "finished register allocation\n"); - DEBUG(printVirt2PhysMap()); - - DEBUG(std::cerr << "Rewrite machine code:\n"); - for (MachineBasicBlockPtrs::iterator - mbbi = mbbs_.begin(), mbbe = mbbs_.end(); mbbi != mbbe; ++mbbi) { - instrAdded_ = 0; - currentMbb_ = *mbbi; - - for (currentInstr_ = currentMbb_->begin(); - currentInstr_ != currentMbb_->end(); ++currentInstr_) { - - DEBUG(std::cerr << "\tinstruction: "; - (*currentInstr_)->print(std::cerr, *tm_);); - - // use our current mapping and actually replace and - // virtual register with its allocated physical registers - DEBUG(std::cerr << "\t\treplacing virtual registers with mapped " - "physical registers:\n"); - for (unsigned i = 0, e = (*currentInstr_)->getNumOperands(); - i != e; ++i) { - MachineOperand& op = (*currentInstr_)->getOperand(i); - if (op.isVirtualRegister()) { - unsigned virtReg = op.getAllocatedRegNum(); - unsigned physReg = v2pMap_[virtReg]; - if (physReg) { - DEBUG(std::cerr << "\t\t\t%reg" << virtReg - << " -> " << mri_->getName(physReg) << '\n'); - (*currentInstr_)->SetMachineOperandReg(i, physReg); - } - } - } - - DEBUG(std::cerr << "\t\tloading temporarily used operands to " - "registers:\n"); - for (unsigned i = 0, e = (*currentInstr_)->getNumOperands(); - i != e; ++i) { - MachineOperand& op = (*currentInstr_)->getOperand(i); - if (op.isVirtualRegister() && op.isUse() && !op.isDef()) { - unsigned virtReg = op.getAllocatedRegNum(); - unsigned physReg = v2pMap_[virtReg]; - if (!physReg) { - physReg = getFreeTempPhysReg(virtReg); - loadVirt2PhysReg(virtReg, physReg); - tempUseOperands_.push_back(virtReg); - } - (*currentInstr_)->SetMachineOperandReg(i, physReg); - } - } + // expire any remaining inactive intervals + for (IntervalPtrs::reverse_iterator + i = inactive_.rbegin(); i != inactive_.rend(); ) { + DEBUG(std::cerr << "\tinterval " << **i << " expired\n"); + i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1)); + } - DEBUG(std::cerr << "\t\tclearing temporarily used operands:\n"); - for (unsigned i = 0, e = tempUseOperands_.size(); i != e; ++i) { - clearVirtReg(tempUseOperands_[i]); - } - tempUseOperands_.clear(); - - DEBUG(std::cerr << "\t\tassigning temporarily defined operands to " - "registers:\n"); - for (unsigned i = 0, e = (*currentInstr_)->getNumOperands(); - i != e; ++i) { - MachineOperand& op = (*currentInstr_)->getOperand(i); - if (op.isVirtualRegister() && op.isDef()) { - unsigned virtReg = op.getAllocatedRegNum(); - unsigned physReg = v2pMap_[virtReg]; - if (!physReg) { - physReg = getFreeTempPhysReg(virtReg); - } - if (op.isUse()) { // def and use - loadVirt2PhysReg(virtReg, physReg); - } - else { - assignVirt2PhysReg(virtReg, physReg); - } - tempDefOperands_.push_back(virtReg); - (*currentInstr_)->SetMachineOperandReg(i, physReg); - } - } + DEBUG(std::cerr << *vrm_); +} - DEBUG(std::cerr << "\t\tspilling temporarily defined operands " - "of this instruction:\n"); - ++currentInstr_; // we want to insert after this instruction - for (unsigned i = 0, e = tempDefOperands_.size(); i != e; ++i) { - spillVirtReg(tempDefOperands_[i]); - } - --currentInstr_; // restore currentInstr_ iterator - tempDefOperands_.clear(); - } +void RA::initIntervalSets() +{ + assert(unhandled_.empty() && fixed_.empty() && + active_.empty() && inactive_.empty() && + "interval sets should be empty on initialization"); + + for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){ + unhandled_.push(&i->second); + if (MRegisterInfo::isPhysicalRegister(i->second.reg)) + fixed_.push_back(&i->second); } - - return true; } -void RA::processActiveIntervals(Intervals::const_iterator cur) +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. we expire earlier because this if - // an interval expires this is going to be the last use. in - // this case we can reuse the register for a def in the same - // instruction - if ((*i)->expiredAt(cur->start() + 1)) { + // remove expired intervals + if ((*i)->expiredAt(cur->start())) { DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); - if (reg >= MRegisterInfo::FirstVirtualRegister) { - reg = v2pMap_[reg]; - } - markPhysRegFree(reg); + if (MRegisterInfo::isVirtualRegister(reg)) + 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())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n"); - if (reg >= MRegisterInfo::FirstVirtualRegister) { - reg = v2pMap_[reg]; - } - markPhysRegFree(reg); + 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 = active_.erase(i); + i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); } else { ++i; @@ -440,32 +262,29 @@ void RA::processActiveIntervals(Intervals::const_iterator cur) } } -void RA::processInactiveIntervals(Intervals::const_iterator cur) +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. we expire earlier because this if - // an interval expires this is going to be the last use. in - // this case we can reuse the register for a def in the same - // instruction - if ((*i)->expiredAt(cur->start() + 1)) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n"); + // 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())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n"); - if (reg >= MRegisterInfo::FirstVirtualRegister) { - reg = v2pMap_[reg]; - } - markPhysRegNotFree(reg); + 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 = inactive_.erase(i); + i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1)); } else { ++i; @@ -473,277 +292,245 @@ void RA::processInactiveIntervals(Intervals::const_iterator cur) } } -namespace { - template - void updateWeight(T rw[], int reg, T w) - { - if (rw[reg] == std::numeric_limits::max() || - w == std::numeric_limits::max()) - rw[reg] = std::numeric_limits::max(); - else - rw[reg] += w; - } +void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight) +{ + spillWeights_[reg] += weight; + for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) + spillWeights_[*as] += weight; } -void RA::assignStackSlotAtInterval(Intervals::const_iterator cur) +void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur) { - DEBUG(std::cerr << "\t\tassigning stack slot at interval " - << *cur << ":\n"); + DEBUG(std::cerr << "\tallocating current interval: "); - // set all weights to zero - float regWeight[MRegisterInfo::FirstVirtualRegister]; - for (unsigned i = 0; i < MRegisterInfo::FirstVirtualRegister; ++i) - regWeight[i] = 0.0F; + PhysRegTracker backupPrt = *prt_; - // for each interval in active that overlaps - for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { - if (!cur->overlaps(**i)) - continue; + spillWeights_.assign(mri_->getNumRegs(), 0.0); + // for each interval in active update spill weights + for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end(); + i != e; ++i) { unsigned reg = (*i)->reg; - if (reg >= MRegisterInfo::FirstVirtualRegister) { - reg = v2pMap_[reg]; - } - updateWeight(regWeight, reg, (*i)->weight); - for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) - updateWeight(regWeight, *as, (*i)->weight); + if (MRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + updateSpillWeights(reg, (*i)->weight); } - // for each interval in inactive that overlaps - for (IntervalPtrs::iterator i = inactive_.begin(); - i != inactive_.end(); ++i) { - if (!cur->overlaps(**i)) - continue; + // for every interval in inactive we overlap with, mark the + // register as not free and update spill weights + for (IntervalPtrs::const_iterator i = inactive_.begin(), + e = inactive_.end(); i != e; ++i) { + if (cur->overlaps(**i)) { + unsigned reg = (*i)->reg; + if (MRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + prt_->addRegUse(reg); + updateSpillWeights(reg, (*i)->weight); + } + } - unsigned reg = (*i)->reg; - if (reg >= MRegisterInfo::FirstVirtualRegister) { - reg = v2pMap_[reg]; + // for every interval in fixed we overlap with, + // mark the register as not free and update spill weights + for (IntervalPtrs::const_iterator i = fixed_.begin(), + e = fixed_.end(); i != e; ++i) { + if (cur->overlaps(**i)) { + unsigned reg = (*i)->reg; + prt_->addRegUse(reg); + updateSpillWeights(reg, (*i)->weight); } - updateWeight(regWeight, reg, (*i)->weight); - for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) - updateWeight(regWeight, *as, (*i)->weight); } - // for each fixed interval in unhandled that overlaps - for (Intervals::const_iterator j = cur + 1; j != li_->end(); ++j) { - if (j->reg >= MRegisterInfo::FirstVirtualRegister) - continue; - updateWeight(regWeight, j->reg, j->weight); - for (const unsigned* as = mri_->getAliasSet(j->reg); *as; ++as) - updateWeight(regWeight, *as, j->weight); + unsigned physReg = getFreePhysReg(cur); + // restore the physical register tracker + *prt_ = backupPrt; + // if we find a free register, we are done: assign this virtual to + // the free physical register and add this interval to the active + // list. + if (physReg) { + DEBUG(std::cerr << mri_->getName(physReg) << '\n'); + vrm_->assignVirt2Phys(cur->reg, physReg); + prt_->addRegUse(physReg); + active_.push_back(cur); + handled_.push_back(cur); + return; } + DEBUG(std::cerr << "no free registers\n"); + + DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n"); - float minWeight = std::numeric_limits::max(); + float minWeight = 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) { unsigned reg = *i; - if (!reserved_[reg] && minWeight > regWeight[reg]) { - minWeight = regWeight[reg]; + if (minWeight > spillWeights_[reg]) { + minWeight = spillWeights_[reg]; minReg = reg; } } + DEBUG(std::cerr << "\t\tregister with min weight: " + << mri_->getName(minReg) << " (" << minWeight << ")\n"); + + // if the current has the minimum weight, we need to spill it and + // add any added intervals back to unhandled, and restart + // linearscan. + if (cur->weight <= minWeight) { + DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';); + int slot = vrm_->assignVirt2StackSlot(cur->reg); + std::vector added = + li_->addIntervalsForSpills(*cur, *vrm_, slot); + if (added.empty()) + return; // Early exit if all spills were folded. + + // Merge added with unhandled. Note that we know that + // addIntervalsForSpills returns intervals sorted by their starting + // point. + for (unsigned i = 0, e = added.size(); i != e; ++i) + unhandled_.push(added[i]); + return; + } - if (cur->weight < minWeight) { - restoreRegUse(); - DEBUG(std::cerr << "\t\t\t\tspilling : " << *cur << '\n'); - assignVirt2StackSlot(cur->reg); + // push the current interval back to unhandled since we are going + // to re-run at least this iteration. Since we didn't modify it it + // should go back right in the front of the list + unhandled_.push(cur); + + // otherwise we spill all intervals aliasing the register with + // minimum weight, rollback to the interval with the earliest + // start point and let the linear scan algorithm run again + std::vector added; + assert(MRegisterInfo::isPhysicalRegister(minReg) && + "did not choose a register to spill?"); + std::vector toSpill(mri_->getNumRegs(), false); + // we are going to spill minReg and all its aliases + toSpill[minReg] = true; + for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as) + toSpill[*as] = true; + + // the earliest start of a spilled interval indicates up to where + // in handled we need to roll back + unsigned earliestStart = cur->start(); + + // set of spilled vregs (used later to rollback properly) + std::set spilled; + + // spill live intervals of virtual regs mapped to the physical + // register we want to clear (and its aliases). we only spill + // those that overlap with the current interval as the rest do not + // affect its allocation. we also keep track of the earliest start + // of all spilled live intervals since this will mark our rollback + // point + for (IntervalPtrs::iterator + i = active_.begin(); i != active_.end(); ++i) { + unsigned reg = (*i)->reg; + if (MRegisterInfo::isVirtualRegister(reg) && + toSpill[vrm_->getPhys(reg)] && + cur->overlaps(**i)) { + DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n'); + earliestStart = std::min(earliestStart, (*i)->start()); + int slot = vrm_->assignVirt2StackSlot((*i)->reg); + std::vector newIs = + li_->addIntervalsForSpills(**i, *vrm_, slot); + std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); + spilled.insert(reg); + } } - else { - std::set toSpill; - toSpill.insert(minReg); - for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as) - toSpill.insert(*as); - - std::vector spilled; - for (IntervalPtrs::iterator i = active_.begin(); - i != active_.end(); ) { - unsigned reg = (*i)->reg; - if (reg >= MRegisterInfo::FirstVirtualRegister && - toSpill.find(v2pMap_[reg]) != toSpill.end() && - cur->overlaps(**i)) { - spilled.push_back(v2pMap_[reg]); - DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n'); - assignVirt2StackSlot(reg); - i = active_.erase(i); + for (IntervalPtrs::iterator + i = inactive_.begin(); i != inactive_.end(); ++i) { + unsigned reg = (*i)->reg; + if (MRegisterInfo::isVirtualRegister(reg) && + toSpill[vrm_->getPhys(reg)] && + cur->overlaps(**i)) { + DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n'); + earliestStart = std::min(earliestStart, (*i)->start()); + int slot = vrm_->assignVirt2StackSlot((*i)->reg); + std::vector newIs = + li_->addIntervalsForSpills(**i, *vrm_, slot); + std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); + spilled.insert(reg); + } + } + + DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n'); + // scan handled in reverse order up to the earliaset start of a + // spilled live interval and undo each one, restoring the state of + // unhandled + while (!handled_.empty()) { + LiveInterval* i = handled_.back(); + // if this interval starts before t we are done + if (i->start() < earliestStart) + break; + DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n'); + handled_.pop_back(); + // when undoing a live interval allocation we must know if it + // is active or inactive to properly update the PhysRegTracker + // and the VirtRegMap + IntervalPtrs::iterator it; + if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) { + active_.erase(it); + if (MRegisterInfo::isPhysicalRegister(i->reg)) { + prt_->delRegUse(i->reg); + unhandled_.push(i); } else { - ++i; + if (!spilled.count(i->reg)) + unhandled_.push(i); + prt_->delRegUse(vrm_->getPhys(i->reg)); + vrm_->clearVirt(i->reg); } } - for (IntervalPtrs::iterator i = inactive_.begin(); - i != inactive_.end(); ) { - unsigned reg = (*i)->reg; - if (reg >= MRegisterInfo::FirstVirtualRegister && - toSpill.find(v2pMap_[reg]) != toSpill.end() && - cur->overlaps(**i)) { - DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n'); - assignVirt2StackSlot(reg); - i = inactive_.erase(i); - } + else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) { + inactive_.erase(it); + if (MRegisterInfo::isPhysicalRegister(i->reg)) + unhandled_.push(i); else { - ++i; + if (!spilled.count(i->reg)) + unhandled_.push(i); + vrm_->clearVirt(i->reg); } } - - unsigned physReg = getFreePhysReg(cur); - assert(physReg && "no free physical register after spill?"); - - restoreRegUse(); - for (unsigned i = 0; i < spilled.size(); ++i) - markPhysRegFree(spilled[i]); - - assignVirt2PhysReg(cur->reg, physReg); - active_.push_back(&*cur); + else { + if (MRegisterInfo::isVirtualRegister(i->reg)) + vrm_->clearVirt(i->reg); + unhandled_.push(i); + } } -} -bool RA::physRegAvailable(unsigned physReg) -{ - assert(!reserved_[physReg] && - "cannot call this method with a reserved register"); + // scan the rest and undo each interval that expired after t and + // insert it in active (the next iteration of the algorithm will + // put it in inactive if required) + IntervalPtrs::iterator i = handled_.begin(), e = handled_.end(); + for (; i != e; ++i) { + if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) { + DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n'); + active_.push_back(*i); + if (MRegisterInfo::isPhysicalRegister((*i)->reg)) + prt_->addRegUse((*i)->reg); + else + prt_->addRegUse(vrm_->getPhys((*i)->reg)); + } + } - return !regUse_[physReg]; + std::sort(added.begin(), added.end(), less_ptr()); + // merge added with unhandled + for (unsigned i = 0, e = added.size(); i != e; ++i) + unhandled_.push(added[i]); } -unsigned RA::getFreePhysReg(Intervals::const_iterator cur) +unsigned RA::getFreePhysReg(LiveInterval* cur) { - DEBUG(std::cerr << "\t\tgetting free physical register: "); 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 reg = *i; - if (!reserved_[reg] && !regUse_[reg]) { - DEBUG(std::cerr << mri_->getName(reg) << '\n'); + if (prt_->isRegAvail(reg)) return reg; - } } - - DEBUG(std::cerr << "no free register\n"); return 0; } -bool RA::tempPhysRegAvailable(unsigned physReg) -{ - assert(reserved_[physReg] && - "cannot call this method with a not reserved temp register"); - - return !regUse_[physReg]; -} - -unsigned RA::getFreeTempPhysReg(unsigned virtReg) -{ - DEBUG(std::cerr << "\t\tgetting free temporary physical register: "); - - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg); - // go in reverse allocation order for the temp registers - for (TargetRegisterClass::iterator i = rc->allocation_order_end(*mf_) - 1; - i != rc->allocation_order_begin(*mf_) - 1; --i) { - unsigned reg = *i; - if (reserved_[reg] && !regUse_[reg]) { - DEBUG(std::cerr << mri_->getName(reg) << '\n'); - return reg; - } - } - - assert(0 && "no free temporary physical register?"); - return 0; -} - -void RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg) -{ - v2pMap_[virtReg] = physReg; - markPhysRegNotFree(physReg); -} - -void RA::clearVirtReg(unsigned virtReg) -{ - Virt2PhysMap::iterator it = v2pMap_.find(virtReg); - assert(it != v2pMap_.end() && - "attempting to clear a not allocated virtual register"); - unsigned physReg = it->second; - markPhysRegFree(physReg); - v2pMap_[virtReg] = 0; // this marks that this virtual register - // lives on the stack - DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg) - << "\n"); -} - -void RA::assignVirt2StackSlot(unsigned virtReg) -{ - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg); - int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc); - - bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second; - assert(inserted && - "attempt to assign stack slot to already assigned register?"); - // if the virtual register was previously assigned clear the mapping - // and free the virtual register - if (v2pMap_.find(virtReg) != v2pMap_.end()) { - clearVirtReg(virtReg); - } - else { - v2pMap_[virtReg] = 0; // this marks that this virtual register - // lives on the stack - } -} - -int RA::getStackSlot(unsigned virtReg) -{ - // use lower_bound so that we can do a possibly O(1) insert later - // if necessary - Virt2StackSlotMap::iterator it = v2ssMap_.find(virtReg); - assert(it != v2ssMap_.end() && - "attempt to get stack slot on register that does not live on the stack"); - return it->second; -} - -void RA::spillVirtReg(unsigned virtReg) -{ - DEBUG(std::cerr << "\t\t\tspilling register: " << virtReg); - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg); - int frameIndex = getStackSlot(virtReg); - DEBUG(std::cerr << " to stack slot #" << frameIndex << '\n'); - ++numSpilled; - instrAdded_ += mri_->storeRegToStackSlot(*currentMbb_, currentInstr_, - v2pMap_[virtReg], frameIndex, rc); - clearVirtReg(virtReg); -} - -void RA::loadVirt2PhysReg(unsigned virtReg, unsigned physReg) -{ - DEBUG(std::cerr << "\t\t\tloading register: " << virtReg); - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg); - int frameIndex = getStackSlot(virtReg); - DEBUG(std::cerr << " from stack slot #" << frameIndex << '\n'); - ++numReloaded; - instrAdded_ += mri_->loadRegFromStackSlot(*currentMbb_, currentInstr_, - physReg, frameIndex, rc); - assignVirt2PhysReg(virtReg, physReg); -} - -void RA::markPhysRegFree(unsigned physReg) -{ - assert(regUse_[physReg] != 0); - --regUse_[physReg]; - for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) { - physReg = *as; - assert(regUse_[physReg] != 0); - --regUse_[physReg]; - } -} - -void RA::markPhysRegNotFree(unsigned physReg) -{ - ++regUse_[physReg]; - for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) { - physReg = *as; - ++regUse_[physReg]; - } -} - FunctionPass* llvm::createLinearScanRegisterAllocator() { return new RA(); }