]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/CodeGen/CalcSpillWeights.cpp
1 //===------------------------ CalcSpillWeights.cpp ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define DEBUG_TYPE "calcspillweights"
12 #include "llvm/ADT/SmallSet.h"
13 #include "llvm/CodeGen/CalcSpillWeights.h"
14 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
15 #include "llvm/CodeGen/MachineFunction.h"
16 #include "llvm/CodeGen/MachineLoopInfo.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/SlotIndexes.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include "llvm/Target/TargetInstrInfo.h"
22 #include "llvm/Target/TargetMachine.h"
23 #include "llvm/Target/TargetRegisterInfo.h"
26 char CalculateSpillWeights::ID
= 0;
27 INITIALIZE_PASS_BEGIN(CalculateSpillWeights
, "calcspillweights",
28 "Calculate spill weights", false, false)
29 INITIALIZE_PASS_DEPENDENCY(LiveIntervals
)
30 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo
)
31 INITIALIZE_PASS_END(CalculateSpillWeights
, "calcspillweights",
32 "Calculate spill weights", false, false)
34 void CalculateSpillWeights::getAnalysisUsage(AnalysisUsage
&au
) const {
35 au
.addRequired
<LiveIntervals
>();
36 au
.addRequired
<MachineLoopInfo
>();
38 MachineFunctionPass::getAnalysisUsage(au
);
41 bool CalculateSpillWeights::runOnMachineFunction(MachineFunction
&MF
) {
43 DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
44 << "********** Function: " << MF
.getName() << '\n');
46 LiveIntervals
&LIS
= getAnalysis
<LiveIntervals
>();
47 MachineRegisterInfo
&MRI
= MF
.getRegInfo();
48 VirtRegAuxInfo
VRAI(MF
, LIS
, getAnalysis
<MachineLoopInfo
>());
49 for (unsigned i
= 0, e
= MRI
.getNumVirtRegs(); i
!= e
; ++i
) {
50 unsigned Reg
= TargetRegisterInfo::index2VirtReg(i
);
51 if (MRI
.reg_nodbg_empty(Reg
))
53 VRAI
.CalculateWeightAndHint(LIS
.getInterval(Reg
));
58 // Return the preferred allocation register for reg, given a COPY instruction.
59 static unsigned copyHint(const MachineInstr
*mi
, unsigned reg
,
60 const TargetRegisterInfo
&tri
,
61 const MachineRegisterInfo
&mri
) {
62 unsigned sub
, hreg
, hsub
;
63 if (mi
->getOperand(0).getReg() == reg
) {
64 sub
= mi
->getOperand(0).getSubReg();
65 hreg
= mi
->getOperand(1).getReg();
66 hsub
= mi
->getOperand(1).getSubReg();
68 sub
= mi
->getOperand(1).getSubReg();
69 hreg
= mi
->getOperand(0).getReg();
70 hsub
= mi
->getOperand(0).getSubReg();
76 if (TargetRegisterInfo::isVirtualRegister(hreg
))
77 return sub
== hsub
? hreg
: 0;
79 const TargetRegisterClass
*rc
= mri
.getRegClass(reg
);
81 // Only allow physreg hints in rc.
83 return rc
->contains(hreg
) ? hreg
: 0;
85 // reg:sub should match the physreg hreg.
86 return tri
.getMatchingSuperReg(hreg
, sub
, rc
);
89 // Check if all values in LI are rematerializable
90 static bool isRematerializable(const LiveInterval
&LI
,
91 const LiveIntervals
&LIS
,
92 const TargetInstrInfo
&TII
) {
93 for (LiveInterval::const_vni_iterator I
= LI
.vni_begin(), E
= LI
.vni_end();
95 const VNInfo
*VNI
= *I
;
101 MachineInstr
*MI
= LIS
.getInstructionFromIndex(VNI
->def
);
102 assert(MI
&& "Dead valno in interval");
104 if (!TII
.isTriviallyReMaterializable(MI
, LIS
.getAliasAnalysis()))
110 void VirtRegAuxInfo::CalculateWeightAndHint(LiveInterval
&li
) {
111 MachineRegisterInfo
&mri
= MF
.getRegInfo();
112 const TargetRegisterInfo
&tri
= *MF
.getTarget().getRegisterInfo();
113 MachineBasicBlock
*mbb
= 0;
114 MachineLoop
*loop
= 0;
115 unsigned loopDepth
= 0;
116 bool isExiting
= false;
117 float totalWeight
= 0;
118 SmallPtrSet
<MachineInstr
*, 8> visited
;
120 // Find the best physreg hist and the best virtreg hint.
121 float bestPhys
= 0, bestVirt
= 0;
122 unsigned hintPhys
= 0, hintVirt
= 0;
124 // Don't recompute a target specific hint.
125 bool noHint
= mri
.getRegAllocationHint(li
.reg
).first
!= 0;
127 // Don't recompute spill weight for an unspillable register.
128 bool Spillable
= li
.isSpillable();
130 for (MachineRegisterInfo::reg_iterator I
= mri
.reg_begin(li
.reg
);
131 MachineInstr
*mi
= I
.skipInstruction();) {
132 if (mi
->isIdentityCopy() || mi
->isImplicitDef() || mi
->isDebugValue())
134 if (!visited
.insert(mi
))
139 // Get loop info for mi.
140 if (mi
->getParent() != mbb
) {
141 mbb
= mi
->getParent();
142 loop
= Loops
.getLoopFor(mbb
);
143 loopDepth
= loop
? loop
->getLoopDepth() : 0;
144 isExiting
= loop
? loop
->isLoopExiting(mbb
) : false;
147 // Calculate instr weight.
149 tie(reads
, writes
) = mi
->readsWritesVirtualRegister(li
.reg
);
150 weight
= LiveIntervals::getSpillWeight(writes
, reads
, loopDepth
);
152 // Give extra weight to what looks like a loop induction variable update.
153 if (writes
&& isExiting
&& LIS
.isLiveOutOfMBB(li
, mbb
))
156 totalWeight
+= weight
;
159 // Get allocation hints from copies.
160 if (noHint
|| !mi
->isCopy())
162 unsigned hint
= copyHint(mi
, li
.reg
, tri
, mri
);
165 float hweight
= Hint
[hint
] += weight
;
166 if (TargetRegisterInfo::isPhysicalRegister(hint
)) {
167 if (hweight
> bestPhys
&& mri
.isAllocatable(hint
))
168 bestPhys
= hweight
, hintPhys
= hint
;
170 if (hweight
> bestVirt
)
171 bestVirt
= hweight
, hintVirt
= hint
;
177 // Always prefer the physreg hint.
178 if (unsigned hint
= hintPhys
? hintPhys
: hintVirt
) {
179 mri
.setRegAllocationHint(li
.reg
, 0, hint
);
180 // Weakly boost the spill weight of hinted registers.
181 totalWeight
*= 1.01F
;
184 // If the live interval was already unspillable, leave it that way.
188 // Mark li as unspillable if all live ranges are tiny.
189 if (li
.isZeroLength(LIS
.getSlotIndexes())) {
190 li
.markNotSpillable();
194 // If all of the definitions of the interval are re-materializable,
195 // it is a preferred candidate for spilling.
196 // FIXME: this gets much more complicated once we support non-trivial
197 // re-materialization.
198 if (isRematerializable(li
, LIS
, *MF
.getTarget().getInstrInfo()))
201 li
.weight
= normalizeSpillWeight(totalWeight
, li
.getSize());