X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=4c44d9201cb67841b4d21f76cc0334206f656e35;hb=c998981505023a79ea96fe871b68512d08704e65;hp=67adeb5e7eb59126faef176e1b4ed113385385e0;hpb=d195e99bc8c6ca5fed506239e298d023df20e942;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 67adeb5e7eb..4c44d9201cb 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -10,76 +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 "LiveIntervalAnalysis.h" +#include "PhysRegTracker.h" +#include "VirtRegMap.h" #include +#include +#include +#include + using namespace llvm; namespace { - Statistic<> numStores("ra-linearscan", "Number of stores added"); - Statistic<> numLoads ("ra-linearscan", "Number of loads added"); - - class PhysRegTracker { - private: - const MRegisterInfo* mri_; - std::vector regUse_; - - public: - PhysRegTracker(MachineFunction* mf) - : mri_(mf ? mf->getTarget().getRegisterInfo() : NULL) { - if (mri_) { - regUse_.assign(mri_->getNumRegs(), 0); - } - } - PhysRegTracker(const PhysRegTracker& rhs) - : mri_(rhs.mri_), - regUse_(rhs.regUse_) { - } + Statistic efficiency + ("regalloc", "Ratio of intervals processed over total intervals"); - const PhysRegTracker& operator=(const PhysRegTracker& rhs) { - mri_ = rhs.mri_; - regUse_ = rhs.regUse_; - return *this; - } - - 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 isPhysRegAvail(unsigned physReg) const { - return regUse_[physReg] == 0; - } - }; + static unsigned numIterations = 0; + static unsigned numIntervals = 0; class RA : public MachineFunctionPass { private: @@ -87,28 +47,20 @@ namespace { const TargetMachine* tm_; const MRegisterInfo* mri_; LiveIntervals* li_; - typedef std::list IntervalPtrs; - IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_; - - PhysRegTracker prt_; - - typedef std::map Virt2PhysMap; - Virt2PhysMap v2pMap_; - - typedef std::map Virt2StackSlotMap; - Virt2StackSlotMap v2ssMap_; - - int instrAdded_; + 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: - RA() - : prt_(NULL) { - - } - virtual const char* getPassName() const { return "Linear Scan Register Allocator"; } @@ -125,17 +77,20 @@ namespace { void releaseMemory(); private: + /// linearScan - the linear scan algorithm + void linearScan(); + /// initIntervalSets - initializa the four interval sets: /// unhandled, fixed, active and inactive - void initIntervalSets(LiveIntervals::Intervals& li); + void initIntervalSets(); /// processActiveIntervals - expire old intervals and move /// non-overlapping ones to the incative list - void processActiveIntervals(IntervalPtrs::value_type cur); + void processActiveIntervals(LiveInterval* cur); /// processInactiveIntervals - expire old intervals and move /// overlapping ones to the active list - void processInactiveIntervals(IntervalPtrs::value_type cur); + void processInactiveIntervals(LiveInterval* cur); /// updateSpillWeights - updates the spill weights of the /// specifed physical register and its weight @@ -143,11 +98,7 @@ namespace { /// assignRegOrStackSlotAtInterval - assign a register if one /// is available, or spill. - void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur); - - /// addSpillCode - adds spill code for interval. The interval - /// must be modified by LiveIntervals::updateIntervalForSpill. - void addSpillCode(IntervalPtrs::value_type li, int slot); + void assignRegOrStackSlotAtInterval(LiveInterval* cur); /// /// register handling helpers @@ -156,84 +107,33 @@ namespace { /// getFreePhysReg - return a free physical register for this /// virtual register interval if we have one, otherwise return /// 0 - unsigned getFreePhysReg(IntervalPtrs::value_type cur); - - /// assignVirt2PhysReg - assigns the free physical register to - /// the virtual register passed as arguments - Virt2PhysMap::iterator - 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(Virt2PhysMap::iterator it); + unsigned getFreePhysReg(LiveInterval* cur); /// assignVirt2StackSlot - assigns this virtual register to a /// stack slot. returns the stack slot int assignVirt2StackSlot(unsigned virtReg); - /// getStackSlot - returns the offset of the specified - /// register on the stack - int getStackSlot(unsigned virtReg); - - 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'; - } - - 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 << " -> "; + 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 verifyAssignment() const { - for (Virt2PhysMap::const_iterator i = v2pMap_.begin(), - e = v2pMap_.end(); i != e; ++i) - for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2) - if (MRegisterInfo::isVirtualRegister(i->second) && - (i->second == i2->second || - mri_->areAliases(i->second, i2->second))) { - const LiveIntervals::Interval - &in = li_->getInterval(i->second), - &in2 = li_->getInterval(i2->second); - if (in.overlaps(in2)) { - std::cerr << in << " overlaps " << in2 << '\n'; - assert(0); - } - } - } }; } void RA::releaseMemory() { - v2pMap_.clear(); - v2ssMap_.clear(); - unhandled_.clear(); + while (!unhandled_.empty()) unhandled_.pop(); + fixed_.clear(); active_.clear(); inactive_.clear(); - fixed_.clear(); handled_.clear(); } @@ -242,46 +142,44 @@ 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(); - initIntervalSets(li_->getIntervals()); + 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_.pop_front(); - } - else if (unhandled_.empty()) { - cur = fixed_.front(); - fixed_.pop_front(); - } - else if (unhandled_.front()->start() < fixed_.front()->start()) { - cur = unhandled_.front(); - unhandled_.pop_front(); - } - else { - cur = fixed_.front(); - fixed_.pop_front(); - } - - DEBUG(std::cerr << *cur << '\n'); + 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_.addPhysRegUse(cur->reg); + prt_->addRegUse(cur->reg); active_.push_back(cur); handled_.push_back(cur); } @@ -292,102 +190,71 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { 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())); + } + 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 (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); + i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); } - DEBUG(printVirtRegAssignment()); - DEBUG(std::cerr << "finished register allocation\n"); - // this is a slow operations do not uncomment - // DEBUG(verifyAssignment()); - - const TargetInstrInfo& tii = tm_->getInstrInfo(); - - DEBUG(std::cerr << "Rewrite machine code:\n"); - for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); - mbbi != mbbe; ++mbbi) { - instrAdded_ = 0; - - for (MachineBasicBlock::iterator mii = mbbi->begin(), mie = mbbi->end(); - mii != mie; ++mii) { - DEBUG(std::cerr << '\t'; mii->print(std::cerr, *tm_)); - - // use our current mapping and actually replace every - // virtual register with its allocated physical registers - DEBUG(std::cerr << "\t\treplacing virtual registers with mapped " - "physical registers:\n"); - for (unsigned i = 0, e = mii->getNumOperands(); - i != e; ++i) { - MachineOperand& op = mii->getOperand(i); - if (op.isRegister() && - MRegisterInfo::isVirtualRegister(op.getReg())) { - unsigned virtReg = op.getReg(); - Virt2PhysMap::iterator it = v2pMap_.find(virtReg); - assert(it != v2pMap_.end() && - "all virtual registers must be allocated"); - unsigned physReg = it->second; - assert(MRegisterInfo::isPhysicalRegister(physReg)); - DEBUG(std::cerr << "\t\t\t%reg" << virtReg - << " -> " << mri_->getName(physReg) << '\n'); - mii->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)); } - return true; + DEBUG(std::cerr << *vrm_); } -void RA::initIntervalSets(LiveIntervals::Intervals& li) +void RA::initIntervalSets() { assert(unhandled_.empty() && fixed_.empty() && active_.empty() && inactive_.empty() && "interval sets should be empty on initialization"); - for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end(); - i != e; ++i) { - if (MRegisterInfo::isPhysicalRegister(i->reg)) - fixed_.push_back(&*i); - else - unhandled_.push_back(&*i); + 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); } } 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 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); + 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 (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 - i = active_.erase(i); + i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); } else { ++i; @@ -398,26 +265,26 @@ void RA::processActiveIntervals(IntervalPtrs::value_type 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 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); + 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 (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 - i = inactive_.erase(i); + i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1)); } else { ++i; @@ -432,11 +299,11 @@ void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight) spillWeights_[*as] += weight; } -void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) +void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur) { - DEBUG(std::cerr << "\tallocating current interval:\n"); + DEBUG(std::cerr << "\tallocating current interval: "); - PhysRegTracker backupPrt = prt_; + PhysRegTracker backupPrt = *prt_; spillWeights_.assign(mri_->getNumRegs(), 0.0); @@ -445,7 +312,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) i != e; ++i) { unsigned reg = (*i)->reg; if (MRegisterInfo::isVirtualRegister(reg)) - reg = v2pMap_[reg]; + reg = vrm_->getPhys(reg); updateSpillWeights(reg, (*i)->weight); } @@ -456,8 +323,8 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) if (cur->overlaps(**i)) { unsigned reg = (*i)->reg; if (MRegisterInfo::isVirtualRegister(reg)) - reg = v2pMap_[reg]; - prt_.addPhysRegUse(reg); + reg = vrm_->getPhys(reg); + prt_->addRegUse(reg); updateSpillWeights(reg, (*i)->weight); } } @@ -468,30 +335,30 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) e = fixed_.end(); i != e; ++i) { if (cur->overlaps(**i)) { unsigned reg = (*i)->reg; - prt_.addPhysRegUse(reg); + prt_->addRegUse(reg); updateSpillWeights(reg, (*i)->weight); } } unsigned physReg = getFreePhysReg(cur); // restore the physical register tracker - prt_ = backupPrt; + *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) { - assignVirt2PhysReg(cur->reg, 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 << "\t\tassigning stack slot at interval "<< *cur << ":\n"); - // push the current interval back to unhandled since we are going - // to re-run at least this iteration - unhandled_.push_front(cur); + DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n"); - float minWeight = std::numeric_limits::infinity(); + float minWeight = HUGE_VAL; unsigned minReg = 0; const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg); for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_); @@ -502,101 +369,131 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) 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 the current has the minimum weight, we need to modify it, - // push it back in unhandled and let the linear scan algorithm run - // again - if (cur->weight < minWeight) { - DEBUG(std::cerr << "\t\t\t\tspilling(c): " << *cur;); - int slot = assignVirt2StackSlot(cur->reg); - li_->updateSpilledInterval(*cur); - addSpillCode(cur, slot); - DEBUG(std::cerr << "[ " << *cur << " ]\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; } + // 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(); - for (IntervalPtrs::iterator i = active_.begin(); - i != active_.end(); ++i) { + // 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[v2pMap_[reg]] && + toSpill[vrm_->getPhys(reg)] && cur->overlaps(**i)) { - DEBUG(std::cerr << "\t\t\t\tspilling(a): " << **i); - int slot = assignVirt2StackSlot((*i)->reg); - li_->updateSpilledInterval(**i); - addSpillCode(*i, slot); - DEBUG(std::cerr << "[ " << **i << " ]\n"); + 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) { + for (IntervalPtrs::iterator + i = inactive_.begin(); i != inactive_.end(); ++i) { unsigned reg = (*i)->reg; if (MRegisterInfo::isVirtualRegister(reg) && - toSpill[v2pMap_[reg]] && + toSpill[vrm_->getPhys(reg)] && cur->overlaps(**i)) { - DEBUG(std::cerr << "\t\t\t\tspilling(i): " << **i << '\n'); - int slot = assignVirt2StackSlot((*i)->reg); - li_->updateSpilledInterval(**i); - addSpillCode(*i, slot); - DEBUG(std::cerr << "[ " << **i << " ]\n"); + 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\t\t\trolling back to: " << earliestStart << '\n'); - // scan handled in reverse order and undo each one, restoring the - // state of unhandled and fixed + 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()) { - IntervalPtrs::value_type i = handled_.back(); + LiveInterval* i = handled_.back(); // if this interval starts before t we are done if (i->start() < earliestStart) break; - DEBUG(std::cerr << "\t\t\t\t\tundo changes for: " << *i << '\n'); + 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)) { - fixed_.push_front(i); - prt_.delPhysRegUse(i->reg); + prt_->delRegUse(i->reg); + unhandled_.push(i); } else { - Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg); - clearVirtReg(v2pIt); - unhandled_.push_front(i); - prt_.delPhysRegUse(v2pIt->second); + 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)) - fixed_.push_front(i); + unhandled_.push(i); else { - Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg); - clearVirtReg(v2pIt); - unhandled_.push_front(i); + if (!spilled.count(i->reg)) + unhandled_.push(i); + vrm_->clearVirt(i->reg); } } else { - if (MRegisterInfo::isPhysicalRegister(i->reg)) - fixed_.push_front(i); - else { - Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg); - clearVirtReg(v2pIt); - unhandled_.push_front(i); - } + if (MRegisterInfo::isVirtualRegister(i->reg)) + vrm_->clearVirt(i->reg); + unhandled_.push(i); } } @@ -606,156 +503,34 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) 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\t\t\tundo changes for: " << **i << '\n'); + DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n'); active_.push_back(*i); if (MRegisterInfo::isPhysicalRegister((*i)->reg)) - prt_.addPhysRegUse((*i)->reg); - else { - assert(v2pMap_.count((*i)->reg)); - prt_.addPhysRegUse(v2pMap_.find((*i)->reg)->second); - } + prt_->addRegUse((*i)->reg); + else + prt_->addRegUse(vrm_->getPhys((*i)->reg)); } } -} - -void RA::addSpillCode(IntervalPtrs::value_type li, int slot) -{ - // We scan the instructions corresponding to each range. We load - // when we have a use and spill at end of basic blocks or end of - // ranges only if the register was modified. - const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li->reg); - - for (LiveIntervals::Interval::Ranges::iterator i = li->ranges.begin(), - e = li->ranges.end(); i != e; ++i) { - unsigned index = i->first & ~1; - unsigned end = i->second; - - entry: - bool dirty = false, loaded = false; - - // skip deleted instructions. getInstructionFromIndex returns - // null if the instruction was deleted (because of coalescing - // for example) - while (!li_->getInstructionFromIndex(index)) index += 2; - MachineBasicBlock::iterator mi = li_->getInstructionFromIndex(index); - MachineBasicBlock* mbb = mi->getParent(); - - for (; index < end; index += 2) { - // ignore deleted instructions - while (!li_->getInstructionFromIndex(index)) index += 2; - - // if we changed basic block we need to start over - mi = li_->getInstructionFromIndex(index); - if (mbb != mi->getParent()) { - if (dirty) { - mi = li_->getInstructionFromIndex(index-2); - assert(mbb == mi->getParent() && - "rewound to wrong instruction?"); - DEBUG(std::cerr << "add store for reg" << li->reg << " to " - "stack slot " << slot << " after: "; - mi->print(std::cerr, *tm_)); - ++numStores; - mri_->storeRegToStackSlot(*mi->getParent(), - next(mi), li->reg, slot, rc); - } - goto entry; - } - // if it is used in this instruction load it - for (unsigned i = 0; i < mi->getNumOperands(); ++i) { - MachineOperand& mop = mi->getOperand(i); - if (mop.isRegister() && mop.getReg() == li->reg && - mop.isUse() && !loaded) { - loaded = true; - DEBUG(std::cerr << "add load for reg" << li->reg - << " from stack slot " << slot << " before: "; - mi->print(std::cerr, *tm_)); - ++numLoads; - mri_->loadRegFromStackSlot(*mi->getParent(), - mi, li->reg, slot, rc); - } - } - - // if it is defined in this instruction mark as dirty - for (unsigned i = 0; i < mi->getNumOperands(); ++i) { - MachineOperand& mop = mi->getOperand(i); - if (mop.isRegister() && mop.getReg() == li->reg && - mop.isDef()) - dirty = loaded = true; - } - } - if (dirty) { - mi = li_->getInstructionFromIndex(index-2); - assert(mbb == mi->getParent() && - "rewound to wrong instruction?"); - DEBUG(std::cerr << "add store for reg" << li->reg << " to " - "stack slot " << slot << " after: "; - mi->print(std::cerr, *tm_)); - ++numStores; - mri_->storeRegToStackSlot(*mi->getParent(), - next(mi), li->reg, slot, rc); - } - } + 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(IntervalPtrs::value_type 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 (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; } -RA::Virt2PhysMap::iterator -RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg) -{ - bool inserted; - Virt2PhysMap::iterator it; - tie(it, inserted) = v2pMap_.insert(std::make_pair(virtReg, physReg)); - assert(inserted && "attempting to assign a virt->phys mapping to an " - "already mapped register"); - prt_.addPhysRegUse(physReg); - return it; -} - -void RA::clearVirtReg(Virt2PhysMap::iterator it) -{ - assert(it != v2pMap_.end() && - "attempting to clear a not allocated virtual register"); - unsigned physReg = it->second; - v2pMap_.erase(it); - DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg) - << "\n"); -} - - -int 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 spilled register!"); - return frameIndex; -} - -int RA::getStackSlot(unsigned virtReg) -{ - assert(v2ssMap_.count(virtReg) && - "attempt to get stack slot for a non spilled register"); - return v2ssMap_.find(virtReg)->second; -} - FunctionPass* llvm::createLinearScanRegisterAllocator() { return new RA(); }