diff options
author | Lang Hames <lhames@gmail.com> | 2009-12-14 06:49:42 +0000 |
---|---|---|
committer | Lang Hames <lhames@gmail.com> | 2009-12-14 06:49:42 +0000 |
commit | a937f220e14826266a8f05b58a541aad669c8912 (patch) | |
tree | 1cd989b52ede088f5b2366dccb88e82923041bcd /lib | |
parent | a59adc40153f3e0f9843952c127d179b5ebe6c4c (diff) | |
download | external_llvm-a937f220e14826266a8f05b58a541aad669c8912.zip external_llvm-a937f220e14826266a8f05b58a541aad669c8912.tar.gz external_llvm-a937f220e14826266a8f05b58a541aad669c8912.tar.bz2 |
Moved spill weight calculation out of SimpleRegisterCoalescing and into its own pass: CalculateSpillWeights.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91273 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/CodeGen/CalcSpillWeights.cpp | 154 | ||||
-rw-r--r-- | lib/CodeGen/PreAllocSplitting.cpp | 2 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 2 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocPBQP.cpp | 2 | ||||
-rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.cpp | 110 | ||||
-rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.h | 4 |
6 files changed, 160 insertions, 114 deletions
diff --git a/lib/CodeGen/CalcSpillWeights.cpp b/lib/CodeGen/CalcSpillWeights.cpp new file mode 100644 index 0000000..dcffb8a --- /dev/null +++ b/lib/CodeGen/CalcSpillWeights.cpp @@ -0,0 +1,154 @@ +//===------------------------ CalcSpillWeights.cpp ------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "calcspillweights" + +#include "llvm/Function.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/CodeGen/CalcSpillWeights.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" + +using namespace llvm; + +char CalculateSpillWeights::ID = 0; +static RegisterPass<CalculateSpillWeights> X("calcspillweights", + "Calculate spill weights"); + +void CalculateSpillWeights::getAnalysisUsage(AnalysisUsage &au) const { + au.addRequired<LiveIntervals>(); + au.addRequired<MachineLoopInfo>(); + au.setPreservesAll(); + MachineFunctionPass::getAnalysisUsage(au); +} + +bool CalculateSpillWeights::runOnMachineFunction(MachineFunction &fn) { + + DEBUG(errs() << "********** Compute Spill Weights **********\n" + << "********** Function: " + << fn.getFunction()->getName() << '\n'); + + LiveIntervals *lis = &getAnalysis<LiveIntervals>(); + MachineLoopInfo *loopInfo = &getAnalysis<MachineLoopInfo>(); + const TargetInstrInfo *tii = fn.getTarget().getInstrInfo(); + MachineRegisterInfo *mri = &fn.getRegInfo(); + + SmallSet<unsigned, 4> processed; + for (MachineFunction::iterator mbbi = fn.begin(), mbbe = fn.end(); + mbbi != mbbe; ++mbbi) { + MachineBasicBlock* mbb = mbbi; + SlotIndex mbbEnd = lis->getMBBEndIdx(mbb); + MachineLoop* loop = loopInfo->getLoopFor(mbb); + unsigned loopDepth = loop ? loop->getLoopDepth() : 0; + bool isExiting = loop ? loop->isLoopExiting(mbb) : false; + + for (MachineBasicBlock::const_iterator mii = mbb->begin(), mie = mbb->end(); + mii != mie; ++mii) { + const MachineInstr *mi = mii; + if (tii->isIdentityCopy(*mi)) + continue; + + if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) + continue; + + for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { + const MachineOperand &mopi = mi->getOperand(i); + if (!mopi.isReg() || mopi.getReg() == 0) + continue; + unsigned reg = mopi.getReg(); + if (!TargetRegisterInfo::isVirtualRegister(mopi.getReg())) + continue; + // Multiple uses of reg by the same instruction. It should not + // contribute to spill weight again. + if (!processed.insert(reg)) + continue; + + bool hasDef = mopi.isDef(); + bool hasUse = !hasDef; + for (unsigned j = i+1; j != e; ++j) { + const MachineOperand &mopj = mi->getOperand(j); + if (!mopj.isReg() || mopj.getReg() != reg) + continue; + hasDef |= mopj.isDef(); + hasUse |= mopj.isUse(); + if (hasDef && hasUse) + break; + } + + LiveInterval ®Int = lis->getInterval(reg); + float weight = lis->getSpillWeight(hasDef, hasUse, loopDepth); + if (hasDef && isExiting) { + // Looks like this is a loop count variable update. + SlotIndex defIdx = lis->getInstructionIndex(mi).getDefIndex(); + const LiveRange *dlr = + lis->getInterval(reg).getLiveRangeContaining(defIdx); + if (dlr->end > mbbEnd) + weight *= 3.0F; + } + regInt.weight += weight; + } + processed.clear(); + } + } + + for (LiveIntervals::iterator I = lis->begin(), E = lis->end(); I != E; ++I) { + LiveInterval &li = *I->second; + if (TargetRegisterInfo::isVirtualRegister(li.reg)) { + // If the live interval length is essentially zero, i.e. in every live + // range the use follows def immediately, it doesn't make sense to spill + // it and hope it will be easier to allocate for this li. + if (isZeroLengthInterval(&li)) { + li.weight = HUGE_VALF; + continue; + } + + bool isLoad = false; + SmallVector<LiveInterval*, 4> spillIs; + if (lis->isReMaterializable(li, spillIs, isLoad)) { + // If all of the definitions of the interval are re-materializable, + // it is a preferred candidate for spilling. If non of the defs are + // loads, then it's potentially very cheap to re-materialize. + // FIXME: this gets much more complicated once we support non-trivial + // re-materialization. + if (isLoad) + li.weight *= 0.9F; + else + li.weight *= 0.5F; + } + + // Slightly prefer live interval that has been assigned a preferred reg. + std::pair<unsigned, unsigned> Hint = mri->getRegAllocationHint(li.reg); + if (Hint.first || Hint.second) + li.weight *= 1.01F; + + // Divide the weight of the interval by its size. This encourages + // spilling of intervals that are large and have few uses, and + // discourages spilling of small intervals with many uses. + li.weight /= lis->getApproximateInstructionCount(li) * SlotIndex::NUM; + } + } + + return false; +} + +/// Returns true if the given live interval is zero length. +bool CalculateSpillWeights::isZeroLengthInterval(LiveInterval *li) const { + for (LiveInterval::Ranges::const_iterator + i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) + if (i->end.getPrevIndex() > i->start) + return false; + return true; +} diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp index afd7b88..b0d7a47 100644 --- a/lib/CodeGen/PreAllocSplitting.cpp +++ b/lib/CodeGen/PreAllocSplitting.cpp @@ -16,6 +16,7 @@ #define DEBUG_TYPE "pre-alloc-split" #include "VirtRegMap.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineDominators.h" @@ -104,6 +105,7 @@ namespace { AU.addRequired<LiveStacks>(); AU.addPreserved<LiveStacks>(); AU.addPreserved<RegisterCoalescer>(); + AU.addPreserved<CalculateSpillWeights>(); if (StrongPHIElim) AU.addPreservedID(StrongPHIEliminationID); else diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 2a43811..c02d47b 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -16,6 +16,7 @@ #include "VirtRegRewriter.h" #include "Spiller.h" #include "llvm/Function.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -187,6 +188,7 @@ namespace { // Make sure PassManager knows which analyses to make available // to coalescing and which analyses coalescing invalidates. AU.addRequiredTransitive<RegisterCoalescer>(); + AU.addRequired<CalculateSpillWeights>(); if (PreSplitIntervals) AU.addRequiredID(PreAllocSplittingID); AU.addRequired<LiveStacks>(); diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index c677d34..c2014a7 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -36,6 +36,7 @@ #include "PBQP/Heuristics/Briggs.h" #include "VirtRegMap.h" #include "VirtRegRewriter.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -90,6 +91,7 @@ namespace { au.addRequired<LiveIntervals>(); //au.addRequiredID(SplitCriticalEdgesID); au.addRequired<RegisterCoalescer>(); + au.addRequired<CalculateSpillWeights>(); au.addRequired<LiveStacks>(); au.addPreserved<LiveStacks>(); au.addRequired<MachineLoopInfo>(); diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 810fabe..ed407eb 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -2622,114 +2622,6 @@ void SimpleRegisterCoalescing::releaseMemory() { ReMatDefs.clear(); } -/// Returns true if the given live interval is zero length. -static bool isZeroLengthInterval(LiveInterval *li, LiveIntervals *li_) { - for (LiveInterval::Ranges::const_iterator - i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) - if (i->end.getPrevIndex() > i->start) - return false; - return true; -} - - -void SimpleRegisterCoalescing::CalculateSpillWeights() { - SmallSet<unsigned, 4> Processed; - for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); - mbbi != mbbe; ++mbbi) { - MachineBasicBlock* MBB = mbbi; - SlotIndex MBBEnd = li_->getMBBEndIdx(MBB); - MachineLoop* loop = loopInfo->getLoopFor(MBB); - unsigned loopDepth = loop ? loop->getLoopDepth() : 0; - bool isExiting = loop ? loop->isLoopExiting(MBB) : false; - - for (MachineBasicBlock::const_iterator mii = MBB->begin(), mie = MBB->end(); - mii != mie; ++mii) { - const MachineInstr *MI = mii; - if (tii_->isIdentityCopy(*MI)) - continue; - - if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) - continue; - - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &mopi = MI->getOperand(i); - if (!mopi.isReg() || mopi.getReg() == 0) - continue; - unsigned Reg = mopi.getReg(); - if (!TargetRegisterInfo::isVirtualRegister(mopi.getReg())) - continue; - // Multiple uses of reg by the same instruction. It should not - // contribute to spill weight again. - if (!Processed.insert(Reg)) - continue; - - bool HasDef = mopi.isDef(); - bool HasUse = !HasDef; - for (unsigned j = i+1; j != e; ++j) { - const MachineOperand &mopj = MI->getOperand(j); - if (!mopj.isReg() || mopj.getReg() != Reg) - continue; - HasDef |= mopj.isDef(); - HasUse |= mopj.isUse(); - if (HasDef && HasUse) - break; - } - - LiveInterval &RegInt = li_->getInterval(Reg); - float Weight = li_->getSpillWeight(HasDef, HasUse, loopDepth); - if (HasDef && isExiting) { - // Looks like this is a loop count variable update. - SlotIndex DefIdx = li_->getInstructionIndex(MI).getDefIndex(); - const LiveRange *DLR = - li_->getInterval(Reg).getLiveRangeContaining(DefIdx); - if (DLR->end > MBBEnd) - Weight *= 3.0F; - } - RegInt.weight += Weight; - } - Processed.clear(); - } - } - - for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) { - LiveInterval &LI = *I->second; - if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { - // If the live interval length is essentially zero, i.e. in every live - // range the use follows def immediately, it doesn't make sense to spill - // it and hope it will be easier to allocate for this li. - if (isZeroLengthInterval(&LI, li_)) { - LI.weight = HUGE_VALF; - continue; - } - - bool isLoad = false; - SmallVector<LiveInterval*, 4> SpillIs; - if (li_->isReMaterializable(LI, SpillIs, isLoad)) { - // If all of the definitions of the interval are re-materializable, - // it is a preferred candidate for spilling. If non of the defs are - // loads, then it's potentially very cheap to re-materialize. - // FIXME: this gets much more complicated once we support non-trivial - // re-materialization. - if (isLoad) - LI.weight *= 0.9F; - else - LI.weight *= 0.5F; - } - - // Slightly prefer live interval that has been assigned a preferred reg. - std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(LI.reg); - if (Hint.first || Hint.second) - LI.weight *= 1.01F; - - // Divide the weight of the interval by its size. This encourages - // spilling of intervals that are large and have few uses, and - // discourages spilling of small intervals with many uses. - LI.weight /= li_->getApproximateInstructionCount(LI) * InstrSlots::NUM; - } - } -} - - bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; mri_ = &fn.getRegInfo(); @@ -2860,8 +2752,6 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { } } - CalculateSpillWeights(); - DEBUG(dump()); return true; } diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h index 78f8a9a..605a740 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.h +++ b/lib/CodeGen/SimpleRegisterCoalescing.h @@ -244,10 +244,6 @@ namespace llvm { MachineOperand *lastRegisterUse(SlotIndex Start, SlotIndex End, unsigned Reg, SlotIndex &LastUseIdx) const; - /// CalculateSpillWeights - Compute spill weights for all virtual register - /// live intervals. - void CalculateSpillWeights(); - void printRegName(unsigned reg) const; }; |