X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=4c44d9201cb67841b4d21f76cc0334206f656e35;hb=c998981505023a79ea96fe871b68512d08704e65;hp=9e8089a35e5225422a8a9fddb252c6c961c3c429;hpb=4d7af65903cbc858464362e70a6adf499982ec8a;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 9e8089a35e5..4c44d9201cb 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -10,64 +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/Target/TargetRegInfo.h" -#include "llvm/Support/CFG.h" #include "Support/Debug.h" -#include "Support/DepthFirstIterator.h" #include "Support/Statistic.h" #include "Support/STLExtras.h" -#include +#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"); - 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_; - - Regs reserved_; - - typedef LiveIntervals::MachineBasicBlockPtrs MachineBasicBlockPtrs; - MachineBasicBlockPtrs mbbs_; - - typedef std::vector Phys2VirtMap; - Phys2VirtMap p2vMap_; - - 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 { @@ -80,730 +71,464 @@ 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); + + /// updateSpillWeights - updates the spill weights of the + /// specifed physical register and its weight + void updateSpillWeights(unsigned reg, SpillWeights::value_type weight); - /// 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); + /// assignRegOrStackSlotAtInterval - assign a register if one + /// is available, or spill. + void assignRegOrStackSlotAtInterval(LiveInterval* cur); /// /// register handling helpers /// - /// reservePhysReg - reserves a physical register and spills - /// any value assigned to it if any - void reservePhysReg(unsigned reg); - - /// clearReservedPhysReg - marks pysical register as free for - /// use - void clearReservedPhysReg(unsigned reg); - - /// physRegAvailable - returns true if the specifed physical - /// register is available - bool physRegAvailable(unsigned physReg); - /// getFreePhysReg - return a free physical register for this - /// virtual register if we have one, otherwise return 0 - unsigned getFreePhysReg(unsigned virtReg); - - - /// tempPhysRegAvailable - returns true if the specifed - /// temporary physical register is available - bool tempPhysRegAvailable(unsigned physReg); - - /// getFreeTempPhysReg - return a free temprorary physical - /// register for this register class if we have one (should - /// never return 0) - unsigned getFreeTempPhysReg(const TargetRegisterClass* rc); - - /// getFreeTempPhysReg - return a free temprorary physical - /// register for this virtual register if we have one (should - /// never return 0) - unsigned getFreeTempPhysReg(unsigned virtReg) { - const TargetRegisterClass* rc = - mf_->getSSARegMap()->getRegClass(virtReg); - return getFreeTempPhysReg(rc); - } - - /// 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); + /// virtual register interval if we have one, otherwise return + /// 0 + 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 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 { + /// stack slot. returns the stack slot + int assignVirt2StackSlot(unsigned virtReg); + + 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 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(); - mbbs_ = getAnalysis().getOrderedMachineBasicBlockPtrs(); - p2vMap_.resize(MRegisterInfo::FirstVirtualRegister-1); - p2vMap_.clear(); - v2pMap_.clear(); - v2ssMap_.clear(); - - 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 R32: EDI, EBX, - // R16: DI, BX, - // R8: DH, BH, - // RFP: FP5, FP6 - reserved_.push_back(19); /* EDI */ - reserved_.push_back(17); /* EBX */ - reserved_.push_back(12); /* DI */ - reserved_.push_back( 7); /* BX */ - reserved_.push_back(11); /* DH */ - reserved_.push_back( 4); /* BH */ - reserved_.push_back(28); /* FP5 */ - reserved_.push_back(29); /* 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); - - // if this register is preallocated, look for an interval that - // overlaps with it and assign it to a memory location - if (i->reg < MRegisterInfo::FirstVirtualRegister) { - reservePhysReg(i->reg); - active_.push_back(&*i); + li_ = &getAnalysis(); + if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_)); + vrm_.reset(new VirtRegMap(*mf_)); + if (!spiller_.get()) spiller_.reset(createSpiller()); + + initIntervalSets(); + + linearScan(); + + spiller_->runOnMachineFunction(*mf_, *vrm_); + + return true; +} + +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->reg); - if (!physReg) { - assignStackSlotAtInterval(i); - } - else { - 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) { - clearReservedPhysReg(reg); - } - else { - p2vMap_[v2pMap_[reg]] = 0; - } - // remove interval from active + 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 this virtual registers lives on the stack, - // load it to a temporary physical register - 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()) { - unsigned virtReg = op.getAllocatedRegNum(); - unsigned physReg = v2pMap_[virtReg]; - if (!physReg) { - physReg = getFreeTempPhysReg(virtReg); - } - loadVirt2PhysReg(virtReg, physReg); - tempUseOperands_.push_back(virtReg); - (*currentInstr_)->SetMachineOperandReg(i, physReg); - } - } - - 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); - } - } - - - // if the instruction is a two address instruction and the - // source operands are not identical we need to insert - // extra instructions. - - unsigned opcode = (*currentInstr_)->getOpcode(); - if (tm_->getInstrInfo().isTwoAddrInstr(opcode) && - (*currentInstr_)->getOperand(0).getAllocatedRegNum() != - (*currentInstr_)->getOperand(1).getAllocatedRegNum()) { - assert((*currentInstr_)->getOperand(1).isRegister() && - (*currentInstr_)->getOperand(1).getAllocatedRegNum() && - (*currentInstr_)->getOperand(1).isUse() && - "Two address instruction invalid"); - - unsigned regA = - (*currentInstr_)->getOperand(0).getAllocatedRegNum(); - unsigned regB = - (*currentInstr_)->getOperand(1).getAllocatedRegNum(); - unsigned regC = - ((*currentInstr_)->getNumOperands() > 2 && - (*currentInstr_)->getOperand(2).isRegister()) ? - (*currentInstr_)->getOperand(2).getAllocatedRegNum() : - 0; - - const TargetRegisterClass* rc = mri_->getRegClass(regA); - - // special case: "a = b op a". If b is a temporary - // reserved register rewrite as: "b = b op a; a = b" - // otherwise use a temporary reserved register t and - // rewrite as: "t = b; t = t op a; a = t" - if (regC && regA == regC) { - // b is a temp reserved register - if (find(reserved_.begin(), reserved_.end(), - regB) != reserved_.end()) { - (*currentInstr_)->SetMachineOperandReg(0, regB); - ++currentInstr_; - instrAdded_ += mri_->copyRegToReg(*currentMbb_, - currentInstr_, - regA, - regB, - rc); - --currentInstr_; - } - // b is just a normal register - else { - unsigned tempReg = getFreeTempPhysReg(rc); - assert (tempReg && - "no free temp reserved physical register?"); - instrAdded_ += mri_->copyRegToReg(*currentMbb_, - currentInstr_, - tempReg, - regB, - rc); - (*currentInstr_)->SetMachineOperandReg(0, tempReg); - (*currentInstr_)->SetMachineOperandReg(1, tempReg); - ++currentInstr_; - instrAdded_ += mri_->copyRegToReg(*currentMbb_, - currentInstr_, - regA, - tempReg, - rc); - --currentInstr_; - } - } - // "a = b op c" gets rewritten to "a = b; a = a op c" - else { - instrAdded_ += mri_->copyRegToReg(*currentMbb_, - currentInstr_, - regA, - regB, - rc); - (*currentInstr_)->SetMachineOperandReg(1, regA); - } - } + // 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\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(); - } + DEBUG(std::cerr << *vrm_); +} - for (unsigned i = 0, e = p2vMap_.size(); i != e; ++i) { - assert(p2vMap_[i] != i && - "reserved physical registers at end of basic block?"); - } +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)->expired(cur->start() + 1)) { + // remove expired intervals + if ((*i)->expiredAt(cur->start())) { DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); - if (reg < MRegisterInfo::FirstVirtualRegister) { - clearReservedPhysReg(reg); - } - else { - p2vMap_[v2pMap_[reg]] = 0; - } - // remove interval from active - i = active_.erase(i); + if (MRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + prt_->delRegUse(reg); + // remove from active + 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\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)); } - // move not active intervals to inactive list -// else if (!(*i)->overlaps(curIndex)) { -// DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n"); -// unmarkReg(virtReg); -// // add interval to inactive -// inactive_.push_back(*i); -// // remove interval from active -// i = active_.erase(i); -// } else { ++i; } } } -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();) { -// unsigned virtReg = (*i)->reg; -// // remove expired intervals -// if ((*i)->expired(curIndex)) { -// DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n"); -// freePhysReg(virtReg); -// // remove from inactive -// i = inactive_.erase(i); -// } -// // move re-activated intervals in active list -// else if ((*i)->overlaps(curIndex)) { -// DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n"); -// markReg(virtReg); -// // add to active -// active_.push_back(*i); -// // remove from inactive -// i = inactive_.erase(i); -// } -// else { -// ++i; -// } -// } -} - -void RA::assignStackSlotAtInterval(Intervals::const_iterator cur) -{ - DEBUG(std::cerr << "\t\tassigning stack slot at interval " - << *cur << ":\n"); - assert(!active_.empty() && - "active set cannot be empty when choosing a register to spill"); - const TargetRegisterClass* rcCur = - mf_->getSSARegMap()->getRegClass(cur->reg); - - // find the interval for a virtual register that ends last in - // active and belongs to the same register class as the current - // interval - IntervalPtrs::iterator lastEndActive = active_.begin(); - for (IntervalPtrs::iterator e = active_.end(); - lastEndActive != e; ++lastEndActive) { - if ((*lastEndActive)->reg >= MRegisterInfo::FirstVirtualRegister) { - const TargetRegisterClass* rc = - mri_->getRegClass(v2pMap_[(*lastEndActive)->reg]); - if (rcCur == rc) { - break; - } - } - } - for (IntervalPtrs::iterator i = lastEndActive, e = active_.end(); - i != e; ++i) { - if ((*i)->reg >= MRegisterInfo::FirstVirtualRegister) { - const TargetRegisterClass* rc = - mri_->getRegClass(v2pMap_[(*i)->reg]); - if (rcCur == rc && - (*lastEndActive)->end() < (*i)->end()) { - lastEndActive = i; - } - } - } + DEBUG(std::cerr << "\tprocessing inactive intervals:\n"); + for (IntervalPtrs::reverse_iterator + i = inactive_.rbegin(); i != inactive_.rend();) { + unsigned reg = (*i)->reg; - // find the interval for a virtual register that ends last in - // inactive and belongs to the same register class as the current - // interval - IntervalPtrs::iterator lastEndInactive = inactive_.begin(); - for (IntervalPtrs::iterator e = inactive_.end(); - lastEndInactive != e; ++lastEndInactive) { - if ((*lastEndInactive)->reg >= MRegisterInfo::FirstVirtualRegister) { - const TargetRegisterClass* rc = - mri_->getRegClass(v2pMap_[(*lastEndInactive)->reg]); - if (rcCur == rc) { - break; - } - } - } - for (IntervalPtrs::iterator i = lastEndInactive, e = inactive_.end(); - i != e; ++i) { - if ((*i)->reg >= MRegisterInfo::FirstVirtualRegister) { - const TargetRegisterClass* rc = - mri_->getRegClass(v2pMap_[(*i)->reg]); - if (rcCur == rc && - (*lastEndInactive)->end() < (*i)->end()) { - lastEndInactive = i; - } + // 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)); } - } - - unsigned lastEndActiveInactive = 0; - if (lastEndActive != active_.end() && - lastEndActiveInactive < (*lastEndActive)->end()) { - lastEndActiveInactive = (*lastEndActive)->end(); - } - if (lastEndInactive != inactive_.end() && - lastEndActiveInactive < (*lastEndInactive)->end()) { - lastEndActiveInactive = (*lastEndInactive)->end(); - } - - if (lastEndActiveInactive > cur->end()) { - if (lastEndInactive == inactive_.end() || - (*lastEndActive)->end() > (*lastEndInactive)->end()) { - assignVirt2StackSlot((*lastEndActive)->reg); - active_.erase(lastEndActive); + // move re-activated intervals in active list + else if ((*i)->liveAt(cur->start())) { + 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)); } else { - assignVirt2StackSlot((*lastEndInactive)->reg); - inactive_.erase(lastEndInactive); + ++i; } - unsigned physReg = getFreePhysReg(cur->reg); - assert(physReg && "no free physical register after spill?"); - assignVirt2PhysReg(cur->reg, physReg); - active_.push_back(&*cur); - } - else { - assignVirt2StackSlot(cur->reg); } } -void RA::reservePhysReg(unsigned physReg) +void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight) { - DEBUG(std::cerr << "\t\t\treserving physical register: " - << mri_->getName(physReg) << '\n'); - // if this register holds a value spill it - unsigned virtReg = p2vMap_[physReg]; - if (virtReg != 0) { - assert(virtReg != physReg && "reserving an already reserved phus reg?"); - // remove interval from active - for (IntervalPtrs::iterator i = active_.begin(), e = active_.end(); - i != e; ++i) { - if ((*i)->reg == virtReg) { - active_.erase(i); - break; - } - } - assignVirt2StackSlot(virtReg); - } - p2vMap_[physReg] = physReg; // this denotes a reserved physical register - - // if it also aliases any other registers with values spill them too - for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) { - unsigned virtReg = p2vMap_[*as]; - if (virtReg != 0 && virtReg != *as) { - // remove interval from active - for (IntervalPtrs::iterator i = active_.begin(), e = active_.end(); - i != e; ++i) { - if ((*i)->reg == virtReg) { - active_.erase(i); - break; - } - } - assignVirt2StackSlot(virtReg); - } - } + spillWeights_[reg] += weight; + for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) + spillWeights_[*as] += weight; } -void RA::clearReservedPhysReg(unsigned physReg) +void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur) { - DEBUG(std::cerr << "\t\t\tclearing reserved physical register: " - << mri_->getName(physReg) << '\n'); - assert(p2vMap_[physReg] == physReg && - "attempt to clear a non reserved physical register"); - p2vMap_[physReg] = 0; -} + DEBUG(std::cerr << "\tallocating current interval: "); -bool RA::physRegAvailable(unsigned physReg) -{ - if (p2vMap_[physReg]) { - return false; + PhysRegTracker backupPrt = *prt_; + + 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 = vrm_->getPhys(reg); + updateSpillWeights(reg, (*i)->weight); } - // if it aliases other registers it is still not free - for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) { - if (p2vMap_[*as]) { - return false; + // 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); } } - // if it is one of the reserved registers it is still not free - if (find(reserved_.begin(), reserved_.end(), physReg) != reserved_.end()) { - return false; + // 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); + } } - return true; -} - -unsigned RA::getFreePhysReg(unsigned virtReg) -{ - DEBUG(std::cerr << "\t\tgetting free physical register: "); - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg); - TargetRegisterClass::iterator reg = rc->allocation_order_begin(*mf_); - TargetRegisterClass::iterator regEnd = rc->allocation_order_end(*mf_); - - for (; reg != regEnd; ++reg) { - if (physRegAvailable(*reg)) { - assert(*reg != 0 && "Cannot use register!"); - DEBUG(std::cerr << mri_->getName(*reg) << '\n'); - return *reg; // Found an unused register! + 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 = 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 (minWeight > spillWeights_[reg]) { + minWeight = spillWeights_[reg]; + minReg = reg; } } - - DEBUG(std::cerr << "no free register\n"); - return 0; -} - -bool RA::tempPhysRegAvailable(unsigned physReg) -{ - assert(find(reserved_.begin(), reserved_.end(), physReg) != reserved_.end() - && "cannot call this method with a non reserved temp register"); - - if (p2vMap_[physReg]) { - return false; + 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 it aliases other registers it is still not free - for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) { - if (p2vMap_[*as]) { - return false; + // 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); } } - - return true; -} - -unsigned RA::getFreeTempPhysReg(const TargetRegisterClass* rc) -{ - DEBUG(std::cerr << "\t\tgetting free temporary physical register: "); - - for (Regs::const_iterator - reg = reserved_.begin(), regEnd = reserved_.end(); - reg != regEnd; ++reg) { - if (rc == mri_->getRegClass(*reg) && tempPhysRegAvailable(*reg)) { - assert(*reg != 0 && "Cannot use register!"); - DEBUG(std::cerr << mri_->getName(*reg) << '\n'); - return *reg; // Found an unused register! + 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); } } - assert(0 && "no free temporary physical register?"); - return 0; -} - -void RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg) -{ - assert((physRegAvailable(physReg) || - find(reserved_.begin(), - reserved_.end(), - physReg) != reserved_.end()) && - "attempt to allocate to a not available physical register"); - v2pMap_[virtReg] = physReg; - p2vMap_[physReg] = virtReg; -} - -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; - p2vMap_[physReg] = 0; - 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); + 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 { + if (!spilled.count(i->reg)) + unhandled_.push(i); + prt_->delRegUse(vrm_->getPhys(i->reg)); + vrm_->clearVirt(i->reg); + } + } + else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) { + inactive_.erase(it); + if (MRegisterInfo::isPhysicalRegister(i->reg)) + unhandled_.push(i); + else { + if (!spilled.count(i->reg)) + unhandled_.push(i); + vrm_->clearVirt(i->reg); + } + } + else { + if (MRegisterInfo::isVirtualRegister(i->reg)) + vrm_->clearVirt(i->reg); + unhandled_.push(i); + } } - else { - v2pMap_[virtReg] = 0; // this marks that this virtual register - // lives on the stack + + // 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)); + } } -} -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; + 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]); } -void RA::spillVirtReg(unsigned virtReg) +unsigned RA::getFreePhysReg(LiveInterval* cur) { - 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); -} + const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg); -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'); - instrAdded_ += mri_->loadRegFromStackSlot(*currentMbb_, currentInstr_, - physReg, frameIndex, rc); - assignVirt2PhysReg(virtReg, physReg); + for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_); + i != rc->allocation_order_end(*mf_); ++i) { + unsigned reg = *i; + if (prt_->isRegAvail(reg)) + return reg; + } + return 0; } FunctionPass* llvm::createLinearScanRegisterAllocator() {