1//===- CalcSpillWeights.cpp -----------------------------------------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8
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/MachineSizeOpts.h"
19#include "llvm/CodeGen/StackMaps.h"
20#include "llvm/CodeGen/TargetInstrInfo.h"
21#include "llvm/CodeGen/TargetRegisterInfo.h"
22#include "llvm/CodeGen/TargetSubtargetInfo.h"
23#include "llvm/CodeGen/VirtRegMap.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/MathExtras.h"
26#include "llvm/Support/raw_ostream.h"
27#include <cassert>
28#include <tuple>
29
30using namespace llvm;
31
32#define DEBUG_TYPE "calcspillweights"
33
34bool VirtRegAuxInfo::getCachedOptimizeForSize() {
35 if (!CachedOptForSize.has_value())
36 CachedOptForSize = PSI && llvm::shouldOptimizeForSize(MF: &MF, PSI, BFI: &MBFI);
37 return *CachedOptForSize;
38}
39
40void VirtRegAuxInfo::calculateSpillWeightsAndHints() {
41 LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
42 << "********** Function: " << MF.getName() << '\n');
43
44 MachineRegisterInfo &MRI = MF.getRegInfo();
45 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
46 Register Reg = Register::index2VirtReg(Index: I);
47 if (MRI.reg_nodbg_empty(RegNo: Reg))
48 continue;
49 calculateSpillWeightAndHint(LI&: LIS.getInterval(Reg));
50 }
51}
52
53// Return the preferred allocation register for reg, given a COPY instruction.
54Register VirtRegAuxInfo::copyHint(const MachineInstr *MI, Register Reg,
55 const TargetRegisterInfo &TRI,
56 const MachineRegisterInfo &MRI) {
57 unsigned Sub, HSub;
58 Register HReg;
59 if (MI->getOperand(i: 0).getReg() == Reg) {
60 Sub = MI->getOperand(i: 0).getSubReg();
61 HReg = MI->getOperand(i: 1).getReg();
62 HSub = MI->getOperand(i: 1).getSubReg();
63 } else {
64 Sub = MI->getOperand(i: 1).getSubReg();
65 HReg = MI->getOperand(i: 0).getReg();
66 HSub = MI->getOperand(i: 0).getSubReg();
67 }
68
69 if (!HReg)
70 return 0;
71
72 if (HReg.isVirtual())
73 return Sub == HSub ? HReg : Register();
74
75 const TargetRegisterClass *RC = MRI.getRegClass(Reg);
76 MCRegister CopiedPReg = HSub ? TRI.getSubReg(Reg: HReg, Idx: HSub) : HReg.asMCReg();
77 if (RC->contains(Reg: CopiedPReg))
78 return CopiedPReg;
79
80 // Check if reg:sub matches so that a super register could be hinted.
81 if (Sub)
82 return TRI.getMatchingSuperReg(Reg: CopiedPReg, SubIdx: Sub, RC);
83
84 return Register();
85}
86
87// Check if all values in LI are rematerializable
88bool VirtRegAuxInfo::isRematerializable(const LiveInterval &LI,
89 const LiveIntervals &LIS,
90 const VirtRegMap &VRM,
91 const MachineRegisterInfo &MRI,
92 const TargetInstrInfo &TII) {
93 Register Reg = LI.reg();
94 Register Original = VRM.getOriginal(VirtReg: Reg);
95 SmallDenseMap<unsigned, MachineInstr *> VNIDefs;
96 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
97 I != E; ++I) {
98 const VNInfo *VNI = *I;
99 const VNInfo *OrigVNI = VNI;
100 if (VNI->isUnused())
101 continue;
102 if (VNI->isPHIDef())
103 return false;
104
105 MachineInstr *MI = LIS.getInstructionFromIndex(index: VNI->def);
106 assert(MI && "Dead valno in interval");
107
108 // Trace copies introduced by live range splitting. The inline
109 // spiller can rematerialize through these copies, so the spill
110 // weight must reflect this.
111 while (TII.isFullCopyInstr(MI: *MI)) {
112 // The copy destination must match the interval register.
113 if (MI->getOperand(i: 0).getReg() != Reg)
114 return false;
115
116 // Get the source register.
117 Reg = MI->getOperand(i: 1).getReg();
118
119 // If the original (pre-splitting) registers match this
120 // copy came from a split.
121 if (!Reg.isVirtual() || VRM.getOriginal(VirtReg: Reg) != Original)
122 return false;
123
124 // Follow the copy live-in value.
125 const LiveInterval &SrcLI = LIS.getInterval(Reg);
126 LiveQueryResult SrcQ = SrcLI.Query(Idx: VNI->def);
127 VNI = SrcQ.valueIn();
128 assert(VNI && "Copy from non-existing value");
129 if (VNI->isPHIDef())
130 return false;
131 MI = LIS.getInstructionFromIndex(index: VNI->def);
132 assert(MI && "Dead valno in interval");
133 }
134
135 if (!TII.isReMaterializable(MI: *MI))
136 return false;
137
138 VNIDefs[OrigVNI->id] = MI;
139 }
140
141 // If MI has register uses, it will only be rematerializable if its uses are
142 // also live at the indices it will be rematerialized at.
143 for (MachineOperand &MO : MRI.reg_nodbg_operands(Reg: LI.reg())) {
144 if (!MO.readsReg())
145 continue;
146 SlotIndex UseIdx = LIS.getInstructionIndex(Instr: *MO.getParent());
147 MachineInstr *Def = VNIDefs[LI.getVNInfoAt(Idx: UseIdx)->id];
148 assert(Def && "Use with no def");
149 if (!allUsesAvailableAt(MI: Def, UseIdx, LIS, MRI, TII))
150 return false;
151 }
152
153 return true;
154}
155
156bool VirtRegAuxInfo::allUsesAvailableAt(const MachineInstr *MI,
157 SlotIndex UseIdx,
158 const LiveIntervals &LIS,
159 const MachineRegisterInfo &MRI,
160 const TargetInstrInfo &TII) {
161 SlotIndex OrigIdx = LIS.getInstructionIndex(Instr: *MI).getRegSlot(EC: true);
162 UseIdx = std::max(a: UseIdx, b: UseIdx.getRegSlot(EC: true));
163 for (const MachineOperand &MO : MI->operands()) {
164 if (!MO.isReg() || !MO.getReg() || !MO.readsReg())
165 continue;
166
167 // We can't remat physreg uses, unless it is a constant or target wants
168 // to ignore this use.
169 if (MO.getReg().isPhysical()) {
170 if (MRI.isConstantPhysReg(PhysReg: MO.getReg()) || TII.isIgnorableUse(MO))
171 continue;
172 return false;
173 }
174
175 const LiveInterval &li = LIS.getInterval(Reg: MO.getReg());
176 const VNInfo *OVNI = li.getVNInfoAt(Idx: OrigIdx);
177 if (!OVNI)
178 continue;
179
180 // Don't allow rematerialization immediately after the original def.
181 // It would be incorrect if OrigMI redefines the register.
182 // See PR14098.
183 if (SlotIndex::isSameInstr(A: OrigIdx, B: UseIdx))
184 return false;
185
186 if (OVNI != li.getVNInfoAt(Idx: UseIdx))
187 return false;
188
189 // Check that subrange is live at UseIdx.
190 if (li.hasSubRanges()) {
191 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
192 unsigned SubReg = MO.getSubReg();
193 LaneBitmask LM = SubReg ? TRI->getSubRegIndexLaneMask(SubIdx: SubReg)
194 : MRI.getMaxLaneMaskForVReg(Reg: MO.getReg());
195 for (const LiveInterval::SubRange &SR : li.subranges()) {
196 if ((SR.LaneMask & LM).none())
197 continue;
198 if (!SR.liveAt(index: UseIdx))
199 return false;
200 // Early exit if all used lanes are checked. No need to continue.
201 LM &= ~SR.LaneMask;
202 if (LM.none())
203 break;
204 }
205 }
206 }
207 return true;
208}
209
210bool VirtRegAuxInfo::isLiveAtStatepointVarArg(LiveInterval &LI) {
211 return any_of(Range: VRM.getRegInfo().reg_operands(Reg: LI.reg()),
212 P: [](MachineOperand &MO) {
213 MachineInstr *MI = MO.getParent();
214 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
215 return false;
216 return StatepointOpers(MI).getVarIdx() <= MO.getOperandNo();
217 });
218}
219
220void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &LI) {
221 float Weight = weightCalcHelper(LI);
222 // Check if unspillable.
223 if (Weight < 0)
224 return;
225 LI.setWeight(Weight);
226}
227
228static bool canMemFoldInlineAsm(LiveInterval &LI,
229 const MachineRegisterInfo &MRI) {
230 for (const MachineOperand &MO : MRI.reg_operands(Reg: LI.reg())) {
231 const MachineInstr *MI = MO.getParent();
232 if (MI->isInlineAsm() && MI->mayFoldInlineAsmRegOp(OpId: MI->getOperandNo(I: &MO)))
233 return true;
234 }
235
236 return false;
237}
238
239float VirtRegAuxInfo::weightCalcHelper(LiveInterval &LI) {
240 MachineRegisterInfo &MRI = MF.getRegInfo();
241 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
242 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
243 MachineBasicBlock *MBB = nullptr;
244 float TotalWeight = 0;
245 unsigned NumInstr = 0; // Number of instructions using LI
246 SmallPtrSet<MachineInstr *, 8> Visited;
247
248 std::pair<unsigned, Register> TargetHint = MRI.getRegAllocationHint(VReg: LI.reg());
249
250 if (LI.isSpillable()) {
251 Register Reg = LI.reg();
252 Register Original = VRM.getOriginal(VirtReg: Reg);
253 const LiveInterval &OrigInt = LIS.getInterval(Reg: Original);
254 // li comes from a split of OrigInt. If OrigInt was marked
255 // as not spillable, make sure the new interval is marked
256 // as not spillable as well.
257 if (!OrigInt.isSpillable())
258 LI.markNotSpillable();
259 }
260
261 // Don't recompute spill weight for an unspillable register.
262 bool IsSpillable = LI.isSpillable();
263
264 // CopyHint is a sortable hint derived from a COPY instruction.
265 struct CopyHint {
266 Register Reg;
267 float Weight;
268 bool IsCSR;
269 CopyHint(Register R, float W, bool IsCSR)
270 : Reg(R), Weight(W), IsCSR(IsCSR) {}
271 bool operator<(const CopyHint &Rhs) const {
272 // Always prefer any physreg hint.
273 if (Reg.isPhysical() != Rhs.Reg.isPhysical())
274 return Reg.isPhysical();
275 if (Weight != Rhs.Weight)
276 return (Weight > Rhs.Weight);
277 // Prefer non-CSR to CSR.
278 if (Reg.isPhysical() && IsCSR != Rhs.IsCSR)
279 return !IsCSR;
280 return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
281 }
282 };
283
284 bool IsExiting = false;
285 SmallDenseMap<Register, float, 8> Hint;
286 for (MachineRegisterInfo::reg_instr_nodbg_iterator
287 I = MRI.reg_instr_nodbg_begin(RegNo: LI.reg()),
288 E = MRI.reg_instr_nodbg_end();
289 I != E;) {
290 MachineInstr *MI = &*(I++);
291
292 NumInstr++;
293 bool identityCopy = false;
294 auto DestSrc = TII.isCopyInstr(MI: *MI);
295 if (DestSrc) {
296 const MachineOperand *DestRegOp = DestSrc->Destination;
297 const MachineOperand *SrcRegOp = DestSrc->Source;
298 identityCopy = DestRegOp->getReg() == SrcRegOp->getReg() &&
299 DestRegOp->getSubReg() == SrcRegOp->getSubReg();
300 }
301
302 if (identityCopy || MI->isImplicitDef())
303 continue;
304 if (!Visited.insert(Ptr: MI).second)
305 continue;
306
307 // For terminators that produce values, ask the backend if the register is
308 // not spillable.
309 if (TII.isUnspillableTerminator(MI) &&
310 MI->definesRegister(Reg: LI.reg(), /*TRI=*/nullptr)) {
311 LI.markNotSpillable();
312 return -1.0f;
313 }
314
315 // Force Weight onto the stack so that x86 doesn't add hidden precision.
316 stack_float_t Weight = 1.0f;
317 if (IsSpillable) {
318 // Get loop info for mi.
319 if (MI->getParent() != MBB) {
320 MBB = MI->getParent();
321 const MachineLoop *Loop = Loops.getLoopFor(BB: MBB);
322 IsExiting = Loop ? Loop->isLoopExiting(BB: MBB) : false;
323 }
324
325 // Calculate instr weight.
326 bool Reads, Writes;
327 std::tie(args&: Reads, args&: Writes) = MI->readsWritesVirtualRegister(Reg: LI.reg());
328 Weight = LiveIntervals::getSpillWeight(isDef: Writes, isUse: Reads, MBFI: &MBFI, MI: *MI,
329 OptForSize: getCachedOptimizeForSize());
330
331 // Give extra weight to what looks like a loop induction variable update.
332 if (Writes && IsExiting && LIS.isLiveOutOfMBB(LR: LI, mbb: MBB))
333 Weight *= 3;
334
335 TotalWeight += Weight;
336 }
337
338 // Get allocation hints from copies.
339 if (!TII.isCopyInstr(MI: *MI))
340 continue;
341 Register HintReg = copyHint(MI, Reg: LI.reg(), TRI, MRI);
342 if (HintReg && (HintReg.isVirtual() || MRI.isAllocatable(PhysReg: HintReg)))
343 Hint[HintReg] += Weight;
344 }
345
346 // Pass all the sorted copy hints to mri.
347 if (Hint.size()) {
348 // Remove a generic hint if previously added by target.
349 if (TargetHint.first == 0 && TargetHint.second)
350 MRI.clearSimpleHint(VReg: LI.reg());
351
352 // Don't add the target-type hint again.
353 Register SkipReg = TargetHint.first != 0 ? TargetHint.second : Register();
354 SmallVector<CopyHint, 8> RegHints;
355 for (const auto &[Reg, Weight] : Hint) {
356 if (Reg != SkipReg)
357 RegHints.emplace_back(
358 Args: Reg, Args: Weight,
359 Args: Reg.isPhysical() ? TRI.isCalleeSavedPhysReg(PhysReg: Reg, MF) : false);
360 }
361 sort(C&: RegHints);
362 for (const auto &[Reg, _, __] : RegHints)
363 MRI.addRegAllocationHint(VReg: LI.reg(), PrefReg: Reg);
364
365 // Weakly boost the spill weight of hinted registers.
366 TotalWeight *= 1.01F;
367 }
368
369 // If the live interval was already unspillable, leave it that way.
370 if (!IsSpillable)
371 return -1.0;
372
373 // Mark li as unspillable if all live ranges are tiny and the interval
374 // is not live at any reg mask. If the interval is live at a reg mask
375 // spilling may be required. If li is live as use in statepoint instruction
376 // spilling may be required due to if we mark interval with use in statepoint
377 // as not spillable we are risky to end up with no register to allocate.
378 // At the same time STATEPOINT instruction is perfectly fine to have this
379 // operand on stack, so spilling such interval and folding its load from stack
380 // into instruction itself makes perfect sense.
381 if (LI.isZeroLength(Indexes: LIS.getSlotIndexes()) &&
382 !LI.isLiveAtIndexes(Slots: LIS.getRegMaskSlots()) &&
383 !isLiveAtStatepointVarArg(LI) && !canMemFoldInlineAsm(LI, MRI)) {
384 LI.markNotSpillable();
385 return -1.0;
386 }
387
388 // If all of the definitions of the interval are re-materializable,
389 // it is a preferred candidate for spilling.
390 // FIXME: this gets much more complicated once we support non-trivial
391 // re-materialization.
392 if (isRematerializable(LI, LIS, VRM, MRI, TII: *MF.getSubtarget().getInstrInfo()))
393 TotalWeight *= 0.5F;
394
395 // Finally, we scale the weight by the scale factor of register class.
396 const TargetRegisterClass *RC = MRI.getRegClass(Reg: LI.reg());
397 TotalWeight *= TRI.getSpillWeightScaleFactor(RC);
398
399 return normalize(UseDefFreq: TotalWeight, Size: LI.getSize(), NumInstr);
400}
401