X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=4c44d9201cb67841b4d21f76cc0334206f656e35;hb=c998981505023a79ea96fe871b68512d08704e65;hp=d5d3459906ffbf89fd92b9723b9a7c273ddb814e;hpb=c156095b174987226a94583cb7e10c426dddaea6;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index d5d3459906f..4c44d9201cb 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -23,13 +23,13 @@ #include "Support/Debug.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 +#include using namespace llvm; @@ -47,9 +47,12 @@ namespace { const TargetMachine* tm_; 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_; std::auto_ptr vrm_; std::auto_ptr spiller_; @@ -79,15 +82,15 @@ namespace { /// 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 @@ -95,7 +98,7 @@ namespace { /// assignRegOrStackSlotAtInterval - assign a register if one /// is available, or spill. - void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur); + void assignRegOrStackSlotAtInterval(LiveInterval* cur); /// /// register handling helpers @@ -104,15 +107,14 @@ 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); + unsigned getFreePhysReg(LiveInterval* cur); /// assignVirt2StackSlot - assigns this virtual register to a /// stack slot. returns the stack slot int assignVirt2StackSlot(unsigned virtReg); - void printIntervals(const char* const str, - RA::IntervalPtrs::const_iterator i, - RA::IntervalPtrs::const_iterator e) const { + 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 << " -> "; @@ -123,29 +125,12 @@ namespace { 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 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() { - unhandled_.clear(); + while (!unhandled_.empty()) unhandled_.pop(); fixed_.clear(); active_.clear(); inactive_.clear(); @@ -161,7 +146,7 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { vrm_.reset(new VirtRegMap(*mf_)); if (!spiller_.get()) spiller_.reset(createSpiller()); - initIntervalSets(li_->getIntervals()); + initIntervalSets(); linearScan(); @@ -177,15 +162,15 @@ void RA::linearScan() 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()) { // pick the interval with the earliest start point - IntervalPtrs::value_type cur = unhandled_.front(); - unhandled_.pop_front(); + LiveInterval* cur = unhandled_.top(); + unhandled_.pop(); ++numIterations; DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n'); @@ -207,41 +192,49 @@ void RA::linearScan() DEBUG(printIntervals("active", active_.begin(), active_.end())); DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); - // DEBUG(verifyAssignment()); } - numIntervals += li_->getIntervals().size(); + 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 = vrm_->getPhys(reg); prt_->delRegUse(reg); + i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); + } + + // 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 << *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) { - unhandled_.push_back(&*i); - if (MRegisterInfo::isPhysicalRegister(i->reg)) - fixed_.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())) { @@ -250,7 +243,7 @@ void RA::processActiveIntervals(IntervalPtrs::value_type cur) 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())) { @@ -261,7 +254,7 @@ void RA::processActiveIntervals(IntervalPtrs::value_type cur) // 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; @@ -272,14 +265,15 @@ 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())) { @@ -290,7 +284,7 @@ void RA::processInactiveIntervals(IntervalPtrs::value_type cur) // 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; @@ -305,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: "); @@ -386,25 +380,21 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) int slot = vrm_->assignVirt2StackSlot(cur->reg); std::vector added = li_->addIntervalsForSpills(*cur, *vrm_, slot); - - // merge added with unhandled - std::vector::iterator addedIt = added.begin(); - std::vector::iterator addedItEnd = added.end(); - for (IntervalPtrs::iterator i = unhandled_.begin(), e = unhandled_.end(); - i != e && addedIt != addedItEnd; ++i) { - if ((*i)->start() > (*addedIt)->start()) - i = unhandled_.insert(i, *(addedIt++)); - } - while (addedIt != addedItEnd) - unhandled_.push_back(*(addedIt++)); - + 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 @@ -413,14 +403,26 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) 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; - for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { + // 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)] && @@ -434,8 +436,8 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) 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[vrm_->getPhys(reg)] && @@ -451,25 +453,29 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) } DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n'); - // scan handled in reverse order and undo each one, restoring the - // state of unhandled + // 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\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_front(i); + unhandled_.push(i); } else { if (!spilled.count(i->reg)) - unhandled_.push_front(i); + unhandled_.push(i); prt_->delRegUse(vrm_->getPhys(i->reg)); vrm_->clearVirt(i->reg); } @@ -477,17 +483,17 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) { inactive_.erase(it); if (MRegisterInfo::isPhysicalRegister(i->reg)) - unhandled_.push_front(i); + unhandled_.push(i); else { if (!spilled.count(i->reg)) - unhandled_.push_front(i); + unhandled_.push(i); vrm_->clearVirt(i->reg); } } else { if (MRegisterInfo::isVirtualRegister(i->reg)) vrm_->clearVirt(i->reg); - unhandled_.push_front(i); + unhandled_.push(i); } } @@ -508,19 +514,11 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) std::sort(added.begin(), added.end(), less_ptr()); // merge added with unhandled - std::vector::iterator addedIt = added.begin(); - std::vector::iterator addedItEnd = added.end(); - for (IntervalPtrs::iterator i = unhandled_.begin(), e = unhandled_.end(); - i != e && addedIt != addedItEnd; ++i) { - if ((*i)->start() > (*addedIt)->start()) - i = unhandled_.insert(i, *(addedIt++)); - } - while (addedIt != addedItEnd) - unhandled_.push_back(*(addedIt++)); - + 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);