From ed543731fb385b55750d0c514d130a810339d739 Mon Sep 17 00:00:00 2001 From: Alkis Evlogimenos Date: Wed, 1 Sep 2004 22:52:29 +0000 Subject: [PATCH] Be a bit more efficient when processing the active and inactive lists. Instead of scanning the vector backwards, scan it forward and swap each element we want to erase. Then at the end erase all removed intervals at once. This doesn't save much: 0.08s out of 4s when compiling 176.gcc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16136 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegAllocIterativeScan.cpp | 57 +++++++++++++++------------ lib/CodeGen/RegAllocLinearScan.cpp | 57 +++++++++++++++------------ 2 files changed, 62 insertions(+), 52 deletions(-) diff --git a/lib/CodeGen/RegAllocIterativeScan.cpp b/lib/CodeGen/RegAllocIterativeScan.cpp index 764c884fafe..ffeb68d9dda 100644 --- a/lib/CodeGen/RegAllocIterativeScan.cpp +++ b/lib/CodeGen/RegAllocIterativeScan.cpp @@ -264,63 +264,68 @@ void RA::initIntervalSets() { void RA::processActiveIntervals(IntervalPtrs::value_type cur) { DEBUG(std::cerr << "\tprocessing active intervals:\n"); - for (IntervalPtrs::reverse_iterator - i = active_.rbegin(); i != active_.rend();) { - unsigned reg = (*i)->reg; + IntervalPtrs::iterator ii = active_.begin(), ie = active_.end(); + while (ii != ie) { + LiveInterval* i = *ii; + unsigned reg = i->reg; + // remove expired intervals - if ((*i)->expiredAt(cur->start())) { - DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); + if (i->expiredAt(cur->start())) { + DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n"); if (MRegisterInfo::isVirtualRegister(reg)) reg = vrm_->getPhys(reg); prt_->delRegUse(reg); - // remove from active - i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); + // swap with last element and move end iterator back one position + std::iter_swap(ii, --ie); } // move inactive intervals to inactive list - else if (!(*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n"); + 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)); + inactive_.push_back(i); + // swap with last element and move end iterator back one postion + std::iter_swap(ii, --ie); } else { - ++i; + ++ii; } } + active_.erase(ie, active_.end()); } void RA::processInactiveIntervals(IntervalPtrs::value_type cur) { DEBUG(std::cerr << "\tprocessing inactive intervals:\n"); - for (IntervalPtrs::reverse_iterator - i = inactive_.rbegin(); i != inactive_.rend();) { - unsigned reg = (*i)->reg; + IntervalPtrs::iterator ii = inactive_.begin(), ie = inactive_.end(); + while (ii != ie) { + LiveInterval* i = *ii; + unsigned reg = i->reg; // 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)); + if (i->expiredAt(cur->start())) { + DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n"); + // swap with last element and move end iterator back one position + std::iter_swap(ii, --ie); } // move re-activated intervals in active list - else if ((*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\tinterval " << **i << " active\n"); + 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)); + active_.push_back(i); + // swap with last element and move end iterator back one position + std::iter_swap(ii, --ie); } else { - ++i; + ++ii; } } + inactive_.erase(ie, inactive_.end()); } void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight) diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index b9af3970e0e..181f061986a 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -231,63 +231,68 @@ void RA::initIntervalSets() void RA::processActiveIntervals(IntervalPtrs::value_type cur) { DEBUG(std::cerr << "\tprocessing active intervals:\n"); - for (IntervalPtrs::reverse_iterator - i = active_.rbegin(); i != active_.rend();) { - unsigned reg = (*i)->reg; + IntervalPtrs::iterator ii = active_.begin(), ie = active_.end(); + while (ii != ie) { + LiveInterval* i = *ii; + unsigned reg = i->reg; + // remove expired intervals - if ((*i)->expiredAt(cur->start())) { - DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); + if (i->expiredAt(cur->start())) { + DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n"); if (MRegisterInfo::isVirtualRegister(reg)) reg = vrm_->getPhys(reg); prt_->delRegUse(reg); - // remove from active - i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); + // swap with last element and move end iterator back one position + std::iter_swap(ii, --ie); } // move inactive intervals to inactive list - else if (!(*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n"); + 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)); + inactive_.push_back(i); + // swap with last element and move end iterator back one postion + std::iter_swap(ii, --ie); } else { - ++i; + ++ii; } } + active_.erase(ie, active_.end()); } void RA::processInactiveIntervals(IntervalPtrs::value_type cur) { DEBUG(std::cerr << "\tprocessing inactive intervals:\n"); - for (IntervalPtrs::reverse_iterator - i = inactive_.rbegin(); i != inactive_.rend();) { - unsigned reg = (*i)->reg; + IntervalPtrs::iterator ii = inactive_.begin(), ie = inactive_.end(); + while (ii != ie) { + LiveInterval* i = *ii; + unsigned reg = i->reg; // 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)); + if (i->expiredAt(cur->start())) { + DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n"); + // swap with last element and move end iterator back one position + std::iter_swap(ii, --ie); } // move re-activated intervals in active list - else if ((*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\tinterval " << **i << " active\n"); + 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)); + active_.push_back(i); + // swap with last element and move end iterator back one position + std::iter_swap(ii, --ie); } else { - ++i; + ++ii; } } + inactive_.erase(ie, inactive_.end()); } void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight) -- 2.34.1