X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=4a55df189369f51c65db08e06cb0d575f28ea7b2;hb=fc29e63afec1e8f4636c13bd9723b27efc2d4c73;hp=7a7c1c0bb9a8985c8b8e72662a231088d4c4d099;hpb=14be64018fb38d1fa535b9cd12d11371f4eba3b5;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 7a7c1c0bb9a..4a55df18936 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -10,93 +10,36 @@ // 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 "LiveIntervals.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"); - Statistic<> numPeep ("ra-linearscan", - "Number of identity moves eliminated"); - - class PhysRegTracker { - private: - const MRegisterInfo* mri_; - std::vector reserved_; - std::vector regUse_; - - public: - PhysRegTracker(MachineFunction* mf) - : mri_(mf ? mf->getTarget().getRegisterInfo() : NULL) { - if (mri_) { - reserved_.assign(mri_->getNumRegs(), false); - regUse_.assign(mri_->getNumRegs(), 0); - } - } - - PhysRegTracker(const PhysRegTracker& rhs) - : mri_(rhs.mri_), - reserved_(rhs.reserved_), - regUse_(rhs.regUse_) { - } - - const PhysRegTracker& operator=(const PhysRegTracker& rhs) { - mri_ = rhs.mri_; - reserved_ = rhs.reserved_; - regUse_ = rhs.regUse_; - return *this; - } - - void reservePhysReg(unsigned physReg) { - reserved_[physReg] = true; - } - - void addPhysRegUse(unsigned physReg) { - ++regUse_[physReg]; - for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) { - physReg = *as; - ++regUse_[physReg]; - } - } - - void delPhysRegUse(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]; - } - } - - bool isPhysRegReserved(unsigned physReg) const { - return reserved_[physReg]; - } - bool isPhysRegAvail(unsigned physReg) const { - return regUse_[physReg] == 0 && !isPhysRegReserved(physReg); - } + Statistic efficiency + ("regalloc", "Ratio of intervals processed over total intervals"); - bool isReservedPhysRegAvail(unsigned physReg) const { - return regUse_[physReg] == 0 && isPhysRegReserved(physReg); - } - }; + static unsigned numIterations = 0; + static unsigned numIntervals = 0; class RA : public MachineFunctionPass { private: @@ -104,27 +47,17 @@ namespace { const TargetMachine* tm_; const MRegisterInfo* mri_; LiveIntervals* li_; - MachineFunction::iterator currentMbb_; - MachineBasicBlock::iterator currentInstr_; - typedef std::vector IntervalPtrs; - IntervalPtrs unhandled_, fixed_, active_, inactive_; - - PhysRegTracker prt_; - - typedef std::map Virt2PhysMap; - Virt2PhysMap v2pMap_; + typedef std::list IntervalPtrs; + IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_; - typedef std::map Virt2StackSlotMap; - Virt2StackSlotMap v2ssMap_; + std::auto_ptr prt_; + std::auto_ptr vrm_; + std::auto_ptr spiller_; - int instrAdded_; + typedef std::vector SpillWeights; + SpillWeights spillWeights_; public: - RA() - : prt_(NULL) { - - } - virtual const char* getPassName() const { return "Linear Scan Register Allocator"; } @@ -141,9 +74,12 @@ namespace { void releaseMemory(); private: + /// linearScan - the linear scan algorithm + void linearScan(); + /// initIntervalSets - initializa the four interval sets: /// unhandled, fixed, active and inactive - void initIntervalSets(const LiveIntervals::Intervals& li); + void initIntervalSets(LiveIntervals::Intervals& li); /// processActiveIntervals - expire old intervals and move /// non-overlapping ones to the incative list @@ -153,12 +89,13 @@ namespace { /// overlapping ones to the active list void processInactiveIntervals(IntervalPtrs::value_type 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(IntervalPtrs::value_type cur, - const PhysRegTracker& backupPtr); + /// 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(IntervalPtrs::value_type cur); /// /// register handling helpers @@ -169,93 +106,33 @@ namespace { /// 0 unsigned getFreePhysReg(IntervalPtrs::value_type cur); - /// 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); - /// 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 printVirtRegAssignment() const { - std::cerr << "register assignment:\n"; - - for (Virt2PhysMap::const_iterator - i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) { - assert(i->second != 0); - std::cerr << '[' << i->first << ',' - << mri_->getName(i->second) << "]\n"; - } - for (Virt2StackSlotMap::const_iterator - i = v2ssMap_.begin(), e = v2ssMap_.end(); i != e; ++i) { - std::cerr << '[' << i->first << ",ss#" << i->second << "]\n"; - } - std::cerr << '\n'; - } + /// stack slot. returns the stack slot + int assignVirt2StackSlot(unsigned virtReg); void printIntervals(const char* const str, RA::IntervalPtrs::const_iterator i, RA::IntervalPtrs::const_iterator e) const { if (str) std::cerr << str << " intervals:\n"; for (; i != e; ++i) { - std::cerr << "\t\t" << **i << " -> "; + std::cerr << "\t" << **i << " -> "; unsigned reg = (*i)->reg; if (MRegisterInfo::isVirtualRegister(reg)) { - Virt2PhysMap::const_iterator it = v2pMap_.find(reg); - reg = (it == v2pMap_.end() ? 0 : it->second); + reg = vrm_->getPhys(reg); } 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() { - v2pMap_.clear(); - v2ssMap_.clear(); unhandled_.clear(); + fixed_.clear(); active_.clear(); inactive_.clear(); - fixed_.clear(); - + handled_.clear(); } bool RA::runOnMachineFunction(MachineFunction &fn) { @@ -263,284 +140,84 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { tm_ = &fn.getTarget(); mri_ = tm_->getRegisterInfo(); li_ = &getAnalysis(); - prt_ = PhysRegTracker(mf_); + if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_)); + vrm_.reset(new VirtRegMap(*mf_)); + if (!spiller_.get()) spiller_.reset(createSpiller()); initIntervalSets(li_->getIntervals()); - // 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 - prt_.reservePhysReg( 8); /* CH */ - prt_.reservePhysReg( 9); /* CL */ - prt_.reservePhysReg(10); /* CX */ - prt_.reservePhysReg(12); /* DI */ - prt_.reservePhysReg(18); /* ECX */ - prt_.reservePhysReg(19); /* EDI */ - prt_.reservePhysReg(28); /* FP5 */ - prt_.reservePhysReg(29); /* FP6 */ + linearScan(); + + spiller_->runOnMachineFunction(*mf_, *vrm_); + return true; +} + +void RA::linearScan() +{ // linear scan algorithm - DEBUG(std::cerr << "Machine Function\n"); + DEBUG(std::cerr << "********** LINEAR SCAN **********\n"); + DEBUG(std::cerr << "********** Function: " + << mf_->getFunction()->getName() << '\n'); - DEBUG(printIntervals("\tunhandled", unhandled_.begin(), unhandled_.end())); - DEBUG(printIntervals("\tfixed", fixed_.begin(), fixed_.end())); - DEBUG(printIntervals("\tactive", active_.begin(), active_.end())); - DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end())); + 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() || !fixed_.empty()) { + while (!unhandled_.empty()) { // pick the interval with the earliest start point - IntervalPtrs::value_type cur; - if (fixed_.empty()) { - cur = unhandled_.front(); - unhandled_.erase(unhandled_.begin()); - } - else if (unhandled_.empty()) { - cur = fixed_.front(); - fixed_.erase(fixed_.begin()); - } - else if (unhandled_.front()->start() < fixed_.front()->start()) { - cur = unhandled_.front(); - unhandled_.erase(unhandled_.begin()); - } - else { - cur = fixed_.front(); - fixed_.erase(fixed_.begin()); - } - - DEBUG(std::cerr << *cur << '\n'); + IntervalPtrs::value_type cur = unhandled_.front(); + unhandled_.pop_front(); + ++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_.addPhysRegUse(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 { - PhysRegTracker backupPrt = prt_; - - // for every interval in inactive we overlap with, mark the - // register as not free - for (IntervalPtrs::const_iterator i = inactive_.begin(), - e = inactive_.end(); i != e; ++i) { - unsigned reg = (*i)->reg; - if (MRegisterInfo::isVirtualRegister(reg)) - reg = v2pMap_[reg]; - - if (cur->overlaps(**i)) { - prt_.addPhysRegUse(reg); - } - } - - // for every interval in fixed we overlap with, - // mark the register as not free - for (IntervalPtrs::const_iterator i = fixed_.begin(), - e = fixed_.end(); i != e; ++i) { - assert(MRegisterInfo::isPhysicalRegister((*i)->reg) && - "virtual register interval in fixed set?"); - if (cur->overlaps(**i)) - prt_.addPhysRegUse((*i)->reg); - } - - DEBUG(std::cerr << "\tallocating current interval:\n"); - - unsigned physReg = getFreePhysReg(cur); - if (!physReg) { - assignStackSlotAtInterval(cur, backupPrt); - } - else { - prt_ = backupPrt; - assignVirt2PhysReg(cur->reg, physReg); - active_.push_back(cur); - } + assignRegOrStackSlotAtInterval(cur); } - DEBUG(printIntervals("\tactive", active_.begin(), active_.end())); - DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end())); } + DEBUG(printIntervals("active", active_.begin(), active_.end())); + DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); + // DEBUG(verifyAssignment()); + } + numIntervals += li_->getIntervals().size(); + efficiency = double(numIterations) / double(numIntervals); // expire any remaining active intervals for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { unsigned reg = (*i)->reg; - DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); - if (MRegisterInfo::isVirtualRegister(reg)) { - reg = v2pMap_[reg]; - } - prt_.delPhysRegUse(reg); + DEBUG(std::cerr << "\tinterval " << **i << " expired\n"); + if (MRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + prt_->delRegUse(reg); } - typedef LiveIntervals::Reg2RegMap Reg2RegMap; - const Reg2RegMap& r2rMap = li_->getJoinedRegMap(); - - DEBUG(printVirtRegAssignment()); - DEBUG(std::cerr << "Performing coalescing on joined intervals\n"); - // perform coalescing if we were passed joined intervals - for(Reg2RegMap::const_iterator i = r2rMap.begin(), e = r2rMap.end(); - i != e; ++i) { - unsigned reg = i->first; - unsigned rep = li_->rep(reg); - - assert((MRegisterInfo::isPhysicalRegister(rep) || - v2pMap_.count(rep) || v2ssMap_.count(rep)) && - "representative register is not allocated!"); - - assert(MRegisterInfo::isVirtualRegister(reg) && - !v2pMap_.count(reg) && !v2ssMap_.count(reg) && - "coalesced register is already allocated!"); - - if (MRegisterInfo::isPhysicalRegister(rep)) { - v2pMap_.insert(std::make_pair(reg, rep)); - } - else { - Virt2PhysMap::const_iterator pr = v2pMap_.find(rep); - if (pr != v2pMap_.end()) { - v2pMap_.insert(std::make_pair(reg, pr->second)); - } - else { - Virt2StackSlotMap::const_iterator ss = v2ssMap_.find(rep); - assert(ss != v2ssMap_.end()); - v2ssMap_.insert(std::make_pair(reg, ss->second)); - } - } - } - - DEBUG(printVirtRegAssignment()); - DEBUG(std::cerr << "finished register allocation\n"); - - const TargetInstrInfo& tii = tm_->getInstrInfo(); - - DEBUG(std::cerr << "Rewrite machine code:\n"); - for (currentMbb_ = mf_->begin(); currentMbb_ != mf_->end(); ++currentMbb_) { - instrAdded_ = 0; - - for (currentInstr_ = currentMbb_->begin(); - currentInstr_ != currentMbb_->end(); ) { - 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(); - Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg); - if (it != v2pMap_.end()) { - DEBUG(std::cerr << "\t\t\t%reg" << it->first - << " -> " << mri_->getName(it->second) << '\n'); - (*currentInstr_)->SetMachineOperandReg(i, it->second); - } - } - } - - unsigned srcReg, dstReg; - if (tii.isMoveInstr(**currentInstr_, srcReg, dstReg) && - ((MRegisterInfo::isPhysicalRegister(srcReg) && - MRegisterInfo::isPhysicalRegister(dstReg) && - srcReg == dstReg) || - (MRegisterInfo::isVirtualRegister(srcReg) && - MRegisterInfo::isVirtualRegister(dstReg) && - v2ssMap_[srcReg] == v2ssMap_[dstReg]))) { - delete *currentInstr_; - currentInstr_ = currentMbb_->erase(currentInstr_); - ++numPeep; - DEBUG(std::cerr << "\t\tdeleting instruction\n"); - continue; - } - - typedef std::vector Regs; - Regs toClear; - Regs toSpill; - - const unsigned numOperands = (*currentInstr_)->getNumOperands(); - - DEBUG(std::cerr << "\t\tloading temporarily used operands to " - "registers:\n"); - for (unsigned i = 0; i != numOperands; ++i) { - MachineOperand& op = (*currentInstr_)->getOperand(i); - if (op.isVirtualRegister() && op.isUse()) { - unsigned virtReg = op.getAllocatedRegNum(); - unsigned physReg = 0; - Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg); - if (it != v2pMap_.end()) { - physReg = it->second; - } - else { - physReg = getFreeTempPhysReg(virtReg); - loadVirt2PhysReg(virtReg, physReg); - // we will clear uses that are not also defs - // before we allocate registers the defs - if (op.isDef()) - toSpill.push_back(virtReg); - else - toClear.push_back(virtReg); - } - (*currentInstr_)->SetMachineOperandReg(i, physReg); - } - } - - DEBUG(std::cerr << "\t\tclearing temporarily used but not defined " - "operands:\n"); - std::for_each(toClear.begin(), toClear.end(), - std::bind1st(std::mem_fun(&RA::clearVirtReg), this)); - - DEBUG(std::cerr << "\t\tassigning temporarily defined operands to " - "registers:\n"); - for (unsigned i = 0; i != numOperands; ++i) { - MachineOperand& op = (*currentInstr_)->getOperand(i); - if (op.isVirtualRegister()) { - assert(!op.isUse() && "we should not have uses here!"); - unsigned virtReg = op.getAllocatedRegNum(); - unsigned physReg = 0; - Virt2PhysMap::const_iterator it = v2pMap_.find(virtReg); - if (it != v2pMap_.end()) { - physReg = it->second; - } - else { - physReg = getFreeTempPhysReg(virtReg); - assignVirt2PhysReg(virtReg, physReg); - // need to spill this after we are done with - // this instruction - toSpill.push_back(virtReg); - } - (*currentInstr_)->SetMachineOperandReg(i, physReg); - } - } - ++currentInstr_; // spills will go after this instruction - - DEBUG(std::cerr << "\t\tspilling temporarily defined operands:\n"); - std::for_each(toSpill.begin(), toSpill.end(), - std::bind1st(std::mem_fun(&RA::spillVirtReg), this)); - } - } - - return true; + DEBUG(std::cerr << *vrm_); } -void RA::initIntervalSets(const LiveIntervals::Intervals& li) +void RA::initIntervalSets(LiveIntervals::Intervals& li) { assert(unhandled_.empty() && fixed_.empty() && active_.empty() && inactive_.empty() && "interval sets should be empty on initialization"); - for (LiveIntervals::Intervals::const_iterator i = li.begin(), e = li.end(); + 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); - else - unhandled_.push_back(&*i); } } @@ -552,20 +229,18 @@ void RA::processActiveIntervals(IntervalPtrs::value_type cur) // remove expired intervals if ((*i)->expiredAt(cur->start())) { DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); - if (MRegisterInfo::isVirtualRegister(reg)) { - reg = v2pMap_[reg]; - } - prt_.delPhysRegUse(reg); + if (MRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + prt_->delRegUse(reg); // remove from active i = active_.erase(i); } // move inactive intervals to inactive list else if (!(*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n"); - if (MRegisterInfo::isVirtualRegister(reg)) { - reg = v2pMap_[reg]; - } - prt_.delPhysRegUse(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 @@ -585,17 +260,16 @@ void RA::processInactiveIntervals(IntervalPtrs::value_type cur) // remove expired intervals if ((*i)->expiredAt(cur->start())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n"); + DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); // remove from inactive i = inactive_.erase(i); } // move re-activated intervals in active list else if ((*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n"); - if (MRegisterInfo::isVirtualRegister(reg)) { - reg = v2pMap_[reg]; - } - prt_.addPhysRegUse(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 @@ -607,240 +281,265 @@ void RA::processInactiveIntervals(IntervalPtrs::value_type cur) } } -namespace { - template - void updateWeight(std::vector& 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(IntervalPtrs::value_type cur, - const PhysRegTracker& backupPrt) +void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) { - DEBUG(std::cerr << "\t\tassigning stack slot at interval " - << *cur << ":\n"); + DEBUG(std::cerr << "\tallocating current interval: "); - std::vector regWeight(mri_->getNumRegs(), 0.0); + PhysRegTracker backupPrt = *prt_; - // for each interval in active + 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 (MRegisterInfo::isVirtualRegister(reg)) { - 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 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)) - continue; + 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 (MRegisterInfo::isVirtualRegister(reg)) { - 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 that overlaps - for (IntervalPtrs::const_iterator i = fixed_.begin(), e = fixed_.end(); - i != e; ++i) { - if (!cur->overlaps(**i)) - continue; - - assert(MRegisterInfo::isPhysicalRegister((*i)->reg) && - "virtual register interval in fixed set?"); - updateWeight(regWeight, (*i)->reg, (*i)->weight); - for (const unsigned* as = mri_->getAliasSet((*i)->reg); *as; ++as) - updateWeight(regWeight, *as, (*i)->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 (!prt_.isPhysRegReserved(reg) && minWeight > regWeight[reg]) { - minWeight = regWeight[reg]; + if (minWeight > spillWeights_[reg]) { + minWeight = spillWeights_[reg]; minReg = reg; } } - DEBUG(std::cerr << "\t\t\tregister with min weight: " + DEBUG(std::cerr << "\t\tregister with min weight: " << mri_->getName(minReg) << " (" << minWeight << ")\n"); - if (cur->weight < minWeight) { - prt_ = backupPrt; - DEBUG(std::cerr << "\t\t\t\tspilling: " << *cur << '\n'); - assignVirt2StackSlot(cur->reg); + // 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. +#ifndef NDEBUG + int OldStart = -1; +#endif + + // Merge added with unhandled. Note that we know that + // addIntervalsForSpills returns intervals sorted by their starting + // point. + std::vector::iterator addedIt = added.begin(); + std::vector::iterator addedItEnd = added.end(); + for (IntervalPtrs::iterator i = unhandled_.begin(), e =unhandled_.end(); + i != e && addedIt != addedItEnd; ++i) { + while (addedIt != addedItEnd && + (*i)->start() > (*addedIt)->start()) { +#ifndef NDEBUG + // This code only works if addIntervalsForSpills retursn a + // sorted interval list. Assert this is the case now. + assert(OldStart <= (int)(*addedIt)->start() && + "addIntervalsForSpills didn't return sorted interval list!"); + OldStart = (*addedIt)->start(); +#endif + i = unhandled_.insert(i, *(addedIt++)); + } + } + + while (addedIt != addedItEnd) { +#ifndef NDEBUG + // This code only works if addIntervalsForSpills retursn a + // sorted interval list. Assert this is the case now. + assert(OldStart <= (int)(*addedIt)->start() && + "addIntervalsForSpills didn't return sorted interval list!"); + OldStart = (*addedIt)->start(); +#endif + unhandled_.push_back(*(addedIt++)); + } + return; } - else { - std::vector toSpill(mri_->getNumRegs(), false); - toSpill[minReg] = true; - for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as) - toSpill[*as] = true; - - std::vector spilled; - for (IntervalPtrs::iterator i = active_.begin(); - i != active_.end(); ) { - unsigned reg = (*i)->reg; - if (MRegisterInfo::isVirtualRegister(reg) && - toSpill[v2pMap_[reg]] && - cur->overlaps(**i)) { - spilled.push_back(v2pMap_[reg]); - DEBUG(std::cerr << "\t\t\t\tspilling : " << **i << '\n'); - assignVirt2StackSlot(reg); - i = active_.erase(i); + + // 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_front(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); + toSpill[minReg] = true; + for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as) + toSpill[*as] = true; + unsigned earliestStart = cur->start(); + + std::set spilled; + + 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); + } + } + 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 and undo each one, restoring the + // state of unhandled + while (!handled_.empty()) { + IntervalPtrs::value_type 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(); + 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_front(i); } else { - ++i; + if (!spilled.count(i->reg)) + unhandled_.push_front(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 (MRegisterInfo::isVirtualRegister(reg) && - toSpill[v2pMap_[reg]] && - 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_front(i); else { - ++i; + if (!spilled.count(i->reg)) + unhandled_.push_front(i); + vrm_->clearVirt(i->reg); } } + else { + if (MRegisterInfo::isVirtualRegister(i->reg)) + vrm_->clearVirt(i->reg); + unhandled_.push_front(i); + } + } - unsigned physReg = getFreePhysReg(cur); - assert(physReg && "no free physical register after spill?"); - - prt_ = backupPrt; - for (unsigned i = 0; i < spilled.size(); ++i) - prt_.delPhysRegUse(spilled[i]); + // 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)); + } + } - assignVirt2PhysReg(cur->reg, physReg); - active_.push_back(cur); + std::sort(added.begin(), added.end(), less_ptr()); + // merge added with unhandled + std::vector::iterator addedIt = added.begin(); + std::vector::iterator addedItEnd = added.end(); + for (IntervalPtrs::iterator i = unhandled_.begin(), e = unhandled_.end(); + i != e && addedIt != addedItEnd; ++i) { + if ((*i)->start() > (*addedIt)->start()) + i = unhandled_.insert(i, *(addedIt++)); } + while (addedIt != addedItEnd) + unhandled_.push_back(*(addedIt++)); + } unsigned RA::getFreePhysReg(IntervalPtrs::value_type 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 (prt_.isPhysRegAvail(reg)) { - DEBUG(std::cerr << mri_->getName(reg) << '\n'); + if (prt_->isRegAvail(reg)) return reg; - } } - - DEBUG(std::cerr << "no free register\n"); return 0; } -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 - typedef std::reverse_iterator TRCRevIter; - for (TRCRevIter - i(rc->allocation_order_end(*mf_)), - e(rc->allocation_order_begin(*mf_)); i != e; ++i) { - unsigned reg = *i; - if (prt_.isReservedPhysRegAvail(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) -{ - bool inserted = v2pMap_.insert(std::make_pair(virtReg, physReg)).second; - assert(inserted && "attempting to assign a virt->phys mapping to an " - "already mapped register"); - prt_.addPhysRegUse(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; - prt_.delPhysRegUse(physReg); - v2pMap_.erase(it); - 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_.count(virtReg)) { - clearVirtReg(virtReg); - } -} - -int RA::getStackSlot(unsigned virtReg) -{ - 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); -} - FunctionPass* llvm::createLinearScanRegisterAllocator() { return new RA(); }