1 //===- CalcSpillWeights.cpp -----------------------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 #include "llvm/CodeGen/CalcSpillWeights.h"
10 #include "llvm/ADT/SmallPtrSet.h"
11 #include "llvm/CodeGen/LiveInterval.h"
12 #include "llvm/CodeGen/LiveIntervals.h"
13 #include "llvm/CodeGen/MachineFunction.h"
14 #include "llvm/CodeGen/MachineInstr.h"
15 #include "llvm/CodeGen/MachineLoopInfo.h"
16 #include "llvm/CodeGen/MachineOperand.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/TargetInstrInfo.h"
19 #include "llvm/CodeGen/TargetRegisterInfo.h"
20 #include "llvm/CodeGen/TargetSubtargetInfo.h"
21 #include "llvm/CodeGen/VirtRegMap.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
29 #define DEBUG_TYPE "calcspillweights"
31 void llvm::calculateSpillWeightsAndHints(LiveIntervals
&LIS
,
34 const MachineLoopInfo
&MLI
,
35 const MachineBlockFrequencyInfo
&MBFI
,
36 VirtRegAuxInfo::NormalizingFn norm
) {
37 LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
38 << "********** Function: " << MF
.getName() << '\n');
40 MachineRegisterInfo
&MRI
= MF
.getRegInfo();
41 VirtRegAuxInfo
VRAI(MF
, LIS
, VRM
, MLI
, MBFI
, norm
);
42 for (unsigned i
= 0, e
= MRI
.getNumVirtRegs(); i
!= e
; ++i
) {
43 unsigned Reg
= Register::index2VirtReg(i
);
44 if (MRI
.reg_nodbg_empty(Reg
))
46 VRAI
.calculateSpillWeightAndHint(LIS
.getInterval(Reg
));
50 // Return the preferred allocation register for reg, given a COPY instruction.
51 static Register
copyHint(const MachineInstr
*mi
, unsigned reg
,
52 const TargetRegisterInfo
&tri
,
53 const MachineRegisterInfo
&mri
) {
56 if (mi
->getOperand(0).getReg() == reg
) {
57 sub
= mi
->getOperand(0).getSubReg();
58 hreg
= mi
->getOperand(1).getReg();
59 hsub
= mi
->getOperand(1).getSubReg();
61 sub
= mi
->getOperand(1).getSubReg();
62 hreg
= mi
->getOperand(0).getReg();
63 hsub
= mi
->getOperand(0).getSubReg();
69 if (Register::isVirtualRegister(hreg
))
70 return sub
== hsub
? hreg
: Register();
72 const TargetRegisterClass
*rc
= mri
.getRegClass(reg
);
73 Register CopiedPReg
= (hsub
? tri
.getSubReg(hreg
, hsub
) : hreg
);
74 if (rc
->contains(CopiedPReg
))
77 // Check if reg:sub matches so that a super register could be hinted.
79 return tri
.getMatchingSuperReg(CopiedPReg
, sub
, rc
);
84 // Check if all values in LI are rematerializable
85 static bool isRematerializable(const LiveInterval
&LI
,
86 const LiveIntervals
&LIS
,
88 const TargetInstrInfo
&TII
) {
89 unsigned Reg
= LI
.reg
;
90 unsigned Original
= VRM
? VRM
->getOriginal(Reg
) : 0;
91 for (LiveInterval::const_vni_iterator I
= LI
.vni_begin(), E
= LI
.vni_end();
93 const VNInfo
*VNI
= *I
;
99 MachineInstr
*MI
= LIS
.getInstructionFromIndex(VNI
->def
);
100 assert(MI
&& "Dead valno in interval");
102 // Trace copies introduced by live range splitting. The inline
103 // spiller can rematerialize through these copies, so the spill
104 // weight must reflect this.
106 while (MI
->isFullCopy()) {
107 // The copy destination must match the interval register.
108 if (MI
->getOperand(0).getReg() != Reg
)
111 // Get the source register.
112 Reg
= MI
->getOperand(1).getReg();
114 // If the original (pre-splitting) registers match this
115 // copy came from a split.
116 if (!Register::isVirtualRegister(Reg
) ||
117 VRM
->getOriginal(Reg
) != Original
)
120 // Follow the copy live-in value.
121 const LiveInterval
&SrcLI
= LIS
.getInterval(Reg
);
122 LiveQueryResult SrcQ
= SrcLI
.Query(VNI
->def
);
123 VNI
= SrcQ
.valueIn();
124 assert(VNI
&& "Copy from non-existing value");
127 MI
= LIS
.getInstructionFromIndex(VNI
->def
);
128 assert(MI
&& "Dead valno in interval");
132 if (!TII
.isTriviallyReMaterializable(*MI
, LIS
.getAliasAnalysis()))
138 void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval
&li
) {
139 float weight
= weightCalcHelper(li
);
140 // Check if unspillable.
146 float VirtRegAuxInfo::futureWeight(LiveInterval
&li
, SlotIndex start
,
148 return weightCalcHelper(li
, &start
, &end
);
151 float VirtRegAuxInfo::weightCalcHelper(LiveInterval
&li
, SlotIndex
*start
,
153 MachineRegisterInfo
&mri
= MF
.getRegInfo();
154 const TargetRegisterInfo
&tri
= *MF
.getSubtarget().getRegisterInfo();
155 MachineBasicBlock
*mbb
= nullptr;
156 MachineLoop
*loop
= nullptr;
157 bool isExiting
= false;
158 float totalWeight
= 0;
159 unsigned numInstr
= 0; // Number of instructions using li
160 SmallPtrSet
<MachineInstr
*, 8> visited
;
162 std::pair
<unsigned, unsigned> TargetHint
= mri
.getRegAllocationHint(li
.reg
);
164 // Don't recompute spill weight for an unspillable register.
165 bool Spillable
= li
.isSpillable();
167 bool localSplitArtifact
= start
&& end
;
169 // Do not update future local split artifacts.
170 bool updateLI
= !localSplitArtifact
;
172 if (localSplitArtifact
) {
173 MachineBasicBlock
*localMBB
= LIS
.getMBBFromIndex(*end
);
174 assert(localMBB
== LIS
.getMBBFromIndex(*start
) &&
175 "start and end are expected to be in the same basic block");
177 // Local split artifact will have 2 additional copy instructions and they
178 // will be in the same BB.
179 // localLI = COPY other
181 // other = COPY localLI
182 totalWeight
+= LiveIntervals::getSpillWeight(true, false, &MBFI
, localMBB
);
183 totalWeight
+= LiveIntervals::getSpillWeight(false, true, &MBFI
, localMBB
);
188 // CopyHint is a sortable hint derived from a COPY instruction.
193 CopyHint(unsigned R
, float W
, bool P
) :
194 Reg(R
), Weight(W
), IsPhys(P
) {}
195 bool operator<(const CopyHint
&rhs
) const {
196 // Always prefer any physreg hint.
197 if (IsPhys
!= rhs
.IsPhys
)
198 return (IsPhys
&& !rhs
.IsPhys
);
199 if (Weight
!= rhs
.Weight
)
200 return (Weight
> rhs
.Weight
);
201 return Reg
< rhs
.Reg
; // Tie-breaker.
204 std::set
<CopyHint
> CopyHints
;
206 for (MachineRegisterInfo::reg_instr_iterator
207 I
= mri
.reg_instr_begin(li
.reg
), E
= mri
.reg_instr_end();
209 MachineInstr
*mi
= &*(I
++);
211 // For local split artifacts, we are interested only in instructions between
212 // the expected start and end of the range.
213 SlotIndex si
= LIS
.getInstructionIndex(*mi
);
214 if (localSplitArtifact
&& ((si
< *start
) || (si
> *end
)))
218 if (mi
->isIdentityCopy() || mi
->isImplicitDef() || mi
->isDebugInstr())
220 if (!visited
.insert(mi
).second
)
225 // Get loop info for mi.
226 if (mi
->getParent() != mbb
) {
227 mbb
= mi
->getParent();
228 loop
= Loops
.getLoopFor(mbb
);
229 isExiting
= loop
? loop
->isLoopExiting(mbb
) : false;
232 // Calculate instr weight.
234 std::tie(reads
, writes
) = mi
->readsWritesVirtualRegister(li
.reg
);
235 weight
= LiveIntervals::getSpillWeight(writes
, reads
, &MBFI
, *mi
);
237 // Give extra weight to what looks like a loop induction variable update.
238 if (writes
&& isExiting
&& LIS
.isLiveOutOfMBB(li
, mbb
))
241 totalWeight
+= weight
;
244 // Get allocation hints from copies.
247 Register hint
= copyHint(mi
, li
.reg
, tri
, mri
);
250 // Force hweight onto the stack so that x86 doesn't add hidden precision,
251 // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
253 // FIXME: we probably shouldn't use floats at all.
254 volatile float hweight
= Hint
[hint
] += weight
;
255 if (Register::isVirtualRegister(hint
) || mri
.isAllocatable(hint
))
257 CopyHint(hint
, hweight
, Register::isPhysicalRegister(hint
)));
262 // Pass all the sorted copy hints to mri.
263 if (updateLI
&& CopyHints
.size()) {
264 // Remove a generic hint if previously added by target.
265 if (TargetHint
.first
== 0 && TargetHint
.second
)
266 mri
.clearSimpleHint(li
.reg
);
268 std::set
<unsigned> HintedRegs
;
269 for (auto &Hint
: CopyHints
) {
270 if (!HintedRegs
.insert(Hint
.Reg
).second
||
271 (TargetHint
.first
!= 0 && Hint
.Reg
== TargetHint
.second
))
272 // Don't add the same reg twice or the target-type hint again.
274 mri
.addRegAllocationHint(li
.reg
, Hint
.Reg
);
277 // Weakly boost the spill weight of hinted registers.
278 totalWeight
*= 1.01F
;
281 // If the live interval was already unspillable, leave it that way.
285 // Mark li as unspillable if all live ranges are tiny and the interval
286 // is not live at any reg mask. If the interval is live at a reg mask
287 // spilling may be required.
288 if (updateLI
&& li
.isZeroLength(LIS
.getSlotIndexes()) &&
289 !li
.isLiveAtIndexes(LIS
.getRegMaskSlots())) {
290 li
.markNotSpillable();
294 // If all of the definitions of the interval are re-materializable,
295 // it is a preferred candidate for spilling.
296 // FIXME: this gets much more complicated once we support non-trivial
297 // re-materialization.
298 if (isRematerializable(li
, LIS
, VRM
, *MF
.getSubtarget().getInstrInfo()))
301 if (localSplitArtifact
)
302 return normalize(totalWeight
, start
->distance(*end
), numInstr
);
303 return normalize(totalWeight
, li
.getSize(), numInstr
);