X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=4c44d9201cb67841b4d21f76cc0334206f656e35;hb=c998981505023a79ea96fe871b68512d08704e65;hp=d4b258d1fc53bab3f86bc75e994d8c24fcecb226;hpb=e6394e2b625c369e9ac33c8113067d8626932fbe;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index d4b258d1fc5..4c44d9201cb 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -10,50 +10,52 @@ // This file implements a linear scan register allocator. // //===----------------------------------------------------------------------===// + #define DEBUG_TYPE "regalloc" #include "llvm/Function.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 "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"); + + 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 TargetInstrInfo* tii_; const MRegisterInfo* mri_; LiveIntervals* li_; - typedef std::list IntervalPtrs; - IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_; - + typedef std::vector IntervalPtrs; + IntervalPtrs handled_, fixed_, active_, inactive_; + typedef std::priority_queue > IntervalHeap; + IntervalHeap unhandled_; std::auto_ptr prt_; - - typedef std::map Virt2PhysMap; - Virt2PhysMap v2pMap_; - - typedef std::map Virt2StackSlotMap; - Virt2StackSlotMap v2ssMap_; - - int instrAdded_; + std::auto_ptr vrm_; + std::auto_ptr spiller_; typedef std::vector SpillWeights; SpillWeights spillWeights_; @@ -75,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 @@ -93,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 @@ -106,127 +107,71 @@ 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 << "[reg" << 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" << **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(); } bool RA::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; tm_ = &fn.getTarget(); - tii_ = &tm_->getInstrInfo(); mri_ = tm_->getRegisterInfo(); li_ = &getAnalysis(); if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_)); + vrm_.reset(new VirtRegMap(*mf_)); + if (!spiller_.get()) spiller_.reset(createSpiller()); - initIntervalSets(li_->getIntervals()); + 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("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(); - } - + LiveInterval* cur = unhandled_.top(); + unhandled_.pop(); + ++numIterations; DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n'); processActiveIntervals(cur); @@ -247,124 +192,69 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { DEBUG(printIntervals("active", active_.begin(), active_.end())); DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); - // DEBUG(verifyAssignment()); } + 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 << "\tinterval " << **i << " expired\n"); - if (MRegisterInfo::isVirtualRegister(reg)) { - reg = v2pMap_[reg]; - } + 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 << "********** REWRITE MACHINE CODE **********\n"); - DEBUG(std::cerr << "********** Function: " - << mf_->getFunction()->getName() << '\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 << '['; - unsigned index = li_->getInstructionIndex(mii); - if (index == std::numeric_limits::max()) - std::cerr << '*'; - else - std::cerr << index; - 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"); - 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[reg" << virtReg - << " -> " << mri_->getName(physReg) << ']'); - mii->SetMachineOperandReg(i, physReg); - } - } - DEBUG(std::cerr << '\n'); - } + // 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 << "********** MACHINEINSTRS **********\n"); - DEBUG( - for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); - mbbi != mbbe; ++mbbi) { - std::cerr << mbbi->getBasicBlock()->getName() << ":\n"; - for (MachineBasicBlock::iterator mii = mbbi->begin(), - mie = mbbi->end(); mii != mie; ++mii) { - unsigned index = li_->getInstructionIndex(mii); - if (index == std::numeric_limits::max()) - std::cerr << "*\t"; - else - std::cerr << index << '\t'; - mii->print(std::cerr, *tm_); - } - }); - - 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]; - } + 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\tinterval " << **i << " inactive\n"); - if (MRegisterInfo::isVirtualRegister(reg)) { - reg = v2pMap_[reg]; - } + 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; @@ -375,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\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\tinterval " << **i << " active\n"); - if (MRegisterInfo::isVirtualRegister(reg)) { - reg = v2pMap_[reg]; - } + 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; @@ -409,7 +299,7 @@ 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: "); @@ -422,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); } @@ -433,7 +323,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) if (cur->overlaps(**i)) { unsigned reg = (*i)->reg; if (MRegisterInfo::isVirtualRegister(reg)) - reg = v2pMap_[reg]; + reg = vrm_->getPhys(reg); prt_->addRegUse(reg); updateSpillWeights(reg, (*i)->weight); } @@ -458,7 +348,8 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) // list. if (physReg) { DEBUG(std::cerr << mri_->getName(physReg) << '\n'); - assignVirt2PhysReg(cur->reg, physReg); + vrm_->assignVirt2Phys(cur->reg, physReg); + prt_->addRegUse(physReg); active_.push_back(cur); handled_.push_back(cur); return; @@ -467,7 +358,7 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type 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_); @@ -481,133 +372,128 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) 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 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 = assignVirt2StackSlot(cur->reg); - li_->updateSpilledInterval(*cur, slot); - - // if we didn't eliminate the interval find where to add it - // back to unhandled. We need to scan since unhandled are - // sorted on earliest start point and we may have changed our - // start point. - if (!cur->empty()) { - addSpillCode(cur, slot); - IntervalPtrs::iterator it = unhandled_.begin(); - while (it != unhandled_.end() && (*it)->start() < cur->start()) - ++it; - unhandled_.insert(it, cur); - } + 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_front(cur); + 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\tspilling(a): " << **i << '\n'); earliestStart = std::min(earliestStart, (*i)->start()); - int slot = assignVirt2StackSlot((*i)->reg); - li_->updateSpilledInterval(**i, slot); - addSpillCode(*i, slot); + 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\tspilling(i): " << **i << '\n'); earliestStart = std::min(earliestStart, (*i)->start()); - int slot = assignVirt2StackSlot((*i)->reg); - li_->updateSpilledInterval(**i, slot); - addSpillCode(*i, slot); + 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 and fixed + // 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->empty() && i->start() < earliestStart) + 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)) { - fixed_.push_front(i); prt_->delRegUse(i->reg); + unhandled_.push(i); } else { - Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg); - clearVirtReg(v2pIt); - prt_->delRegUse(v2pIt->second); - if (i->spilled()) { - if (!i->empty()) { - IntervalPtrs::iterator it = unhandled_.begin(); - while (it != unhandled_.end() && - (*it)->start() < i->start()) - ++it; - unhandled_.insert(it, i); - } - } - else - unhandled_.push_front(i); - + 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); - if (i->spilled()) { - if (!i->empty()) { - IntervalPtrs::iterator it = unhandled_.begin(); - while (it != unhandled_.end() && - (*it)->start() < i->start()) - ++it; - unhandled_.insert(it, i); - } - } - else - 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); } } @@ -621,80 +507,18 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) active_.push_back(*i); if (MRegisterInfo::isPhysicalRegister((*i)->reg)) prt_->addRegUse((*i)->reg); - else { - assert(v2pMap_.count((*i)->reg)); - prt_->addRegUse(v2pMap_.find((*i)->reg)->second); - } + 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; - unsigned end = i->second; - - bool loaded = false; - - // skip deleted instructions. getInstructionFromIndex returns - // null if the instruction was deleted (because of coalescing - // for example) - while (!li_->getInstructionFromIndex(index)) - index += LiveIntervals::InstrSlots::NUM; - MachineBasicBlock::iterator mi = li_->getInstructionFromIndex(index); - MachineBasicBlock* mbb = mi->getParent(); - assert(mbb && "machine instruction not bound to basic block"); - - for (; index < end; index += LiveIntervals::InstrSlots::NUM) { - // ignore deleted instructions - while (!li_->getInstructionFromIndex(index)) index += 2; - mi = li_->getInstructionFromIndex(index); - DEBUG(std::cerr << "\t\t\t\texamining: \t\t\t\t\t" - << LiveIntervals::getBaseIndex(index) << '\t'; - mi->print(std::cerr, *tm_)); - - // 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; - mri_->loadRegFromStackSlot(*mbb, mi, li->reg, slot, rc); - ++numLoads; - DEBUG(std::cerr << "\t\t\t\tadded load for reg" << li->reg - << " from ss#" << slot << " before: \t" - << LiveIntervals::getBaseIndex(index) << '\t'; - mi->print(std::cerr, *tm_)); - } - } - - // 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()) { - loaded = true; - - mri_->storeRegToStackSlot(*mbb, next(mi), li->reg, slot,rc); - ++numStores; - DEBUG(std::cerr << "\t\t\t\tadded store for reg" << li->reg - << " to ss#" << slot << " after: \t\t" - << LiveIntervals::getBaseIndex(index) << " \t"; - mi->print(std::cerr, *tm_)); - } - } - } - } + 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) { const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg); @@ -707,46 +531,6 @@ unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur) 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_->addRegUse(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(); }