From a937f220e14826266a8f05b58a541aad669c8912 Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Mon, 14 Dec 2009 06:49:42 +0000 Subject: [PATCH] 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 --- include/llvm/CodeGen/CalcSpillWeights.h | 39 ++++++ lib/CodeGen/CalcSpillWeights.cpp | 154 +++++++++++++++++++++++ lib/CodeGen/PreAllocSplitting.cpp | 2 + lib/CodeGen/RegAllocLinearScan.cpp | 2 + lib/CodeGen/RegAllocPBQP.cpp | 2 + lib/CodeGen/SimpleRegisterCoalescing.cpp | 110 ---------------- lib/CodeGen/SimpleRegisterCoalescing.h | 4 - 7 files changed, 199 insertions(+), 114 deletions(-) create mode 100644 include/llvm/CodeGen/CalcSpillWeights.h create mode 100644 lib/CodeGen/CalcSpillWeights.cpp diff --git a/include/llvm/CodeGen/CalcSpillWeights.h b/include/llvm/CodeGen/CalcSpillWeights.h new file mode 100644 index 00000000000..2fc03bd41de --- /dev/null +++ b/include/llvm/CodeGen/CalcSpillWeights.h @@ -0,0 +1,39 @@ +//===---------------- lib/CodeGen/CalcSpillWeights.h ------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + + +#ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H +#define LLVM_CODEGEN_CALCSPILLWEIGHTS_H + +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + + class LiveInterval; + + /// CalculateSpillWeights - Compute spill weights for all virtual register + /// live intervals. + class CalculateSpillWeights : public MachineFunctionPass { + public: + static char ID; + + CalculateSpillWeights() : MachineFunctionPass(&ID) {} + + virtual void getAnalysisUsage(AnalysisUsage &au) const; + + virtual bool runOnMachineFunction(MachineFunction &fn); + + private: + /// Returns true if the given live interval is zero length. + bool isZeroLengthInterval(LiveInterval *li) const; + }; + +} + +#endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H diff --git a/lib/CodeGen/CalcSpillWeights.cpp b/lib/CodeGen/CalcSpillWeights.cpp new file mode 100644 index 00000000000..dcffb8a247a --- /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 X("calcspillweights", + "Calculate spill weights"); + +void CalculateSpillWeights::getAnalysisUsage(AnalysisUsage &au) const { + au.addRequired(); + au.addRequired(); + au.setPreservesAll(); + MachineFunctionPass::getAnalysisUsage(au); +} + +bool CalculateSpillWeights::runOnMachineFunction(MachineFunction &fn) { + + DEBUG(errs() << "********** Compute Spill Weights **********\n" + << "********** Function: " + << fn.getFunction()->getName() << '\n'); + + LiveIntervals *lis = &getAnalysis(); + MachineLoopInfo *loopInfo = &getAnalysis(); + const TargetInstrInfo *tii = fn.getTarget().getInstrInfo(); + MachineRegisterInfo *mri = &fn.getRegInfo(); + + SmallSet 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 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 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 afd7b882c70..b0d7a4757ef 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(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); if (StrongPHIElim) AU.addPreservedID(StrongPHIEliminationID); else diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 2a43811bf58..c02d47b9a38 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(); + AU.addRequired(); if (PreSplitIntervals) AU.addRequiredID(PreAllocSplittingID); AU.addRequired(); diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index c677d341bef..c2014a7649b 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(); //au.addRequiredID(SplitCriticalEdgesID); au.addRequired(); + au.addRequired(); au.addRequired(); au.addPreserved(); au.addRequired(); diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 810fabeef7b..ed407eb40cb 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 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 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 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 78f8a9a5638..605a7404c20 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; }; -- 2.34.1