diff options
author | Alkis Evlogimenos <alkis@evlogimenos.com> | 2003-12-21 20:19:10 +0000 |
---|---|---|
committer | Alkis Evlogimenos <alkis@evlogimenos.com> | 2003-12-21 20:19:10 +0000 |
commit | 6b4edbaaf9021e0434f0ce0c3724eb43ed41b770 (patch) | |
tree | a37baf95e09c52fae7e10e2f034303b4d0d1b4f9 /lib | |
parent | 595bb97fc745172204980f0addcabc76f5f9f843 (diff) | |
download | external_llvm-6b4edbaaf9021e0434f0ce0c3724eb43ed41b770.zip external_llvm-6b4edbaaf9021e0434f0ce0c3724eb43ed41b770.tar.gz external_llvm-6b4edbaaf9021e0434f0ce0c3724eb43ed41b770.tar.bz2 |
Change weight into a float so that we can take into account the
nesting level when computing it. Right now the allocator uses:
w = sum_over_defs_uses( 10 ^ nesting level );
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10569 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 14 | ||||
-rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.h | 5 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 27 |
3 files changed, 31 insertions, 15 deletions
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 2a0ab9e..05b4f5a 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -18,6 +18,7 @@ #define DEBUG_TYPE "liveintervals" #include "llvm/CodeGen/LiveIntervals.h" #include "llvm/Function.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -32,8 +33,9 @@ #include "Support/Debug.h" #include "Support/DepthFirstIterator.h" #include "Support/Statistic.h" -#include <limits> +#include <cmath> #include <iostream> +#include <limits> using namespace llvm; @@ -51,6 +53,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const AU.addPreservedID(PHIEliminationID); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); + AU.addRequired<LoopInfo>(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -251,12 +254,17 @@ void LiveIntervals::computeIntervals() { DEBUG(std::cerr << "computing live intervals:\n"); + const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); + for (MbbIndex2MbbMap::iterator it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); it != itEnd; ++it) { MachineBasicBlock* mbb = it->second; DEBUG(std::cerr << "machine basic block: " << mbb->getBasicBlock()->getName() << "\n"); + + unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); + for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); mi != miEnd; ++mi) { MachineInstr* instr = *mi; @@ -292,7 +300,7 @@ void LiveIntervals::computeIntervals() Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); if (r2iit != r2iMap_.end() && reg >= MRegisterInfo::FirstVirtualRegister) - ++intervals_[r2iit->second].weight; + intervals_[r2iit->second].weight += pow(10.0F, loopDepth); } } } @@ -305,7 +313,7 @@ void LiveIntervals::computeIntervals() LiveIntervals::Interval::Interval(unsigned r) : reg(r), weight((r < MRegisterInfo::FirstVirtualRegister ? - std::numeric_limits<unsigned>::max() : 0)) + std::numeric_limits<float>::max() : 0.0F)) { } diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index 7ef2e78..cecfbba 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -38,8 +38,9 @@ namespace llvm { typedef std::pair<unsigned, unsigned> Range; typedef std::vector<Range> Ranges; unsigned reg; // the register of this interval - unsigned weight; // weight of this interval (number of uses) - Ranges ranges; // the ranges this register is valid + float weight; // weight of this interval (number of uses + // * 10^loopDepth) + Ranges ranges; // the ranges this register is valid Interval(unsigned r); diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 561448b..9538e04 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -524,11 +524,12 @@ void RA::processInactiveIntervals(Intervals::const_iterator cur) } namespace { - void updateWeight(unsigned rw[], unsigned reg, unsigned w) + template <typename T> + void updateWeight(T rw[], int reg, T w) { - if (rw[reg] == std::numeric_limits<unsigned>::max() || - w == std::numeric_limits<unsigned>::max()) - rw[reg] = std::numeric_limits<unsigned>::max(); + if (rw[reg] == std::numeric_limits<T>::max() || + w == std::numeric_limits<T>::max()) + rw[reg] = std::numeric_limits<T>::max(); else rw[reg] += w; } @@ -543,8 +544,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur) "a register to spill"); // set all weights to zero - unsigned regWeight[MRegisterInfo::FirstVirtualRegister]; - memset(regWeight, 0, sizeof(regWeight)); + float regWeight[MRegisterInfo::FirstVirtualRegister]; + for (unsigned i = 0; i < MRegisterInfo::FirstVirtualRegister; ++i) + regWeight[i] = 0.0F; for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { // if (!cur->overlaps(**i)) @@ -573,7 +575,7 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur) updateWeight(regWeight, *as, (*i)->weight); } - unsigned minWeight = std::numeric_limits<unsigned>::max(); + float minWeight = std::numeric_limits<float>::max(); unsigned minReg = 0; const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg); for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_); @@ -585,10 +587,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur) } } - DEBUG(std::cerr << "\t\t\t\tspill candidate: " - << mri_->getName(minReg) << '\n'); - if (cur->weight < minWeight) { + DEBUG(std::cerr << "\t\t\t\tspilling : " << mri_->getName(minReg) + << ", weight: " << cur->weight << '\n'); assignVirt2StackSlot(cur->reg); } else { @@ -602,6 +603,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur) unsigned reg = (*i)->reg; if (reg >= MRegisterInfo::FirstVirtualRegister && toSpill.find(v2pMap_[reg]) != toSpill.end()) { + DEBUG(std::cerr << "\t\t\t\tspilling : " + << mri_->getName(minReg) << ", weight: " + << (*i)->weight << '\n'); assignVirt2StackSlot(reg); i = active_.erase(i); } @@ -614,6 +618,9 @@ void RA::assignStackSlotAtInterval(Intervals::const_iterator cur) unsigned reg = (*i)->reg; if (reg >= MRegisterInfo::FirstVirtualRegister && toSpill.find(v2pMap_[reg]) != toSpill.end()) { + DEBUG(std::cerr << "\t\t\t\tspilling : " + << mri_->getName(minReg) << ", weight: " + << (*i)->weight << '\n'); assignVirt2StackSlot(reg); i = inactive_.erase(i); } |