From e5d90416ee1a4f45eba80789a7a3cbc3d497a4cd Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 1 Mar 2010 20:59:38 +0000 Subject: [PATCH] Use methods to determine if a LiveInterval is spillable. Don't accidentally produce unspillable intervals for deeply nested loops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97496 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveInterval.h | 10 +++++ include/llvm/CodeGen/LiveIntervalAnalysis.h | 5 +-- lib/CodeGen/LiveIntervalAnalysis.cpp | 44 ++++++++++++--------- 3 files changed, 38 insertions(+), 21 deletions(-) diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 512c94d87cc..eb5901cf2f1 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -569,6 +569,16 @@ namespace llvm { /// unsigned getSize() const; + /// isSpillable - Can this interval be spilled? + bool isSpillable() const { + return weight != HUGE_VALF; + } + + /// markNotSpillable - Mark interval as not spillable + void markNotSpillable() { + weight = HUGE_VALF; + } + /// ComputeJoinedWeight - Set the weight of a live interval after /// Other has been merged into it. void ComputeJoinedWeight(const LiveInterval &Other); diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 294eb25fb23..e8856ac1037 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -70,9 +70,8 @@ namespace llvm { static char ID; // Pass identification, replacement for typeid LiveIntervals() : MachineFunctionPass(&ID) {} - static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { - return (isDef + isUse) * powf(10.0F, (float)loopDepth); - } + // Calculate the spill weight to assign to a single instruction. + static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth); // After summing the spill weights of all defs and uses, the final weight // should be normalized, dividing the weight of the interval by its size. diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index ebcfd60a711..ccda66f0054 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1340,11 +1340,9 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, MachineBasicBlock *MBB = MI->getParent(); if (ImpUse && MI != ReMatDefMI) { - // Re-matting an instruction with virtual register use. Update the - // register interval's spill weight to HUGE_VALF to prevent it from - // being spilled. - LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight = HUGE_VALF; + // Re-matting an instruction with virtual register use. Prevent interval + // from being spilled. + getInterval(ImpUse).markNotSpillable(); } unsigned MBBId = MBB->getNumber(); @@ -1396,7 +1394,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval &nI = getOrCreateInterval(NewVReg); if (!TrySplit) { // The spill weight is now infinity as it cannot be spilled again. - nI.weight = HUGE_VALF; + nI.markNotSpillable(); continue; } @@ -1544,6 +1542,22 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, } } +float +LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { + // Limit the loop depth ridiculousness. + if (loopDepth > 200) + loopDepth = 200; + + // The loop depth is used to roughly estimate the number of times the + // instruction is executed. Something like 10^d is simple, but will quickly + // overflow a float. This expression behaves like 10^d for small d, but is + // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of + // headroom before overflow. + float lc = powf(1 + (100.0f / (loopDepth+10)), (float)loopDepth); + + return (isDef + isUse) * lc; +} + void LiveIntervals::normalizeSpillWeights(std::vector &NewLIs) { for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) @@ -1558,8 +1572,7 @@ addIntervalsForSpillsFast(const LiveInterval &li, std::vector added; - assert(li.weight != HUGE_VALF && - "attempt to spill already spilled interval!"); + assert(li.isSpillable() && "attempt to spill already spilled interval!"); DEBUG({ dbgs() << "\t\t\t\tadding intervals for spills for interval: "; @@ -1595,10 +1608,7 @@ addIntervalsForSpillsFast(const LiveInterval &li, // create a new register for this spill LiveInterval &nI = getOrCreateInterval(NewVReg); - - // the spill weight is now infinity as it - // cannot be spilled again - nI.weight = HUGE_VALF; + nI.markNotSpillable(); // Rewrite register operands to use the new vreg. for (SmallVectorImpl::iterator I = Indices.begin(), @@ -1652,8 +1662,7 @@ addIntervalsForSpills(const LiveInterval &li, if (EnableFastSpilling) return addIntervalsForSpillsFast(li, loopInfo, vrm); - assert(li.weight != HUGE_VALF && - "attempt to spill already spilled interval!"); + assert(li.isSpillable() && "attempt to spill already spilled interval!"); DEBUG({ dbgs() << "\t\t\t\tadding intervals for spills for interval: "; @@ -1920,11 +1929,10 @@ addIntervalsForSpills(const LiveInterval &li, unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); if (ImpUse) { // Re-matting an instruction with virtual register use. Add the - // register as an implicit use on the use MI and update the register - // interval's spill weight to HUGE_VALF to prevent it from being - // spilled. + // register as an implicit use on the use MI and mark the register + // interval as unspillable. LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight = HUGE_VALF; + ImpLi.markNotSpillable(); MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); } } -- 2.34.1