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()) ||
171 TII.isIgnorableUse(MI: *MI, OpIdx: MI->getOperandNo(I: &MO)))
172 continue;
173 return false;
174 }
175
176 const LiveInterval &li = LIS.getInterval(Reg: MO.getReg());
177 const VNInfo *OVNI = li.getVNInfoAt(Idx: OrigIdx);
178 if (!OVNI)
179 continue;
180
181 // Don't allow rematerialization immediately after the original def.
182 // It would be incorrect if OrigMI redefines the register.
183 // See PR14098.
184 if (SlotIndex::isSameInstr(A: OrigIdx, B: UseIdx))
185 return false;
186
187 if (OVNI != li.getVNInfoAt(Idx: UseIdx))
188 return false;
189
190 // Check that subrange is live at UseIdx.
191 if (li.hasSubRanges()) {
192 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
193 unsigned SubReg = MO.getSubReg();
194 LaneBitmask LM = SubReg ? TRI->getSubRegIndexLaneMask(SubIdx: SubReg)
195 : MRI.getMaxLaneMaskForVReg(Reg: MO.getReg());
196 for (const LiveInterval::SubRange &SR : li.subranges()) {
197 if ((SR.LaneMask & LM).none())
198 continue;
199 if (!SR.liveAt(index: UseIdx))
200 return false;
201 // Early exit if all used lanes are checked. No need to continue.
202 LM &= ~SR.LaneMask;
203 if (LM.none())
204 break;
205 }
206 }
207 }
208 return true;
209}
210
211bool VirtRegAuxInfo::isLiveAtStatepointVarArg(LiveInterval &LI) {
212 return any_of(Range: VRM.getRegInfo().reg_operands(Reg: LI.reg()),
213 P: [](MachineOperand &MO) {
214 MachineInstr *MI = MO.getParent();
215 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
216 return false;
217 return StatepointOpers(MI).getVarIdx() <= MO.getOperandNo();
218 });
219}
220
221void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &LI) {
222 float Weight = weightCalcHelper(LI);
223 // Check if unspillable.
224 if (Weight < 0)
225 return;
226 LI.setWeight(Weight);
227}
228
229static bool canMemFoldInlineAsm(LiveInterval &LI,
230 const MachineRegisterInfo &MRI) {
231 for (const MachineOperand &MO : MRI.reg_operands(Reg: LI.reg())) {
232 const MachineInstr *MI = MO.getParent();
233 if (MI->isInlineAsm() && MI->mayFoldInlineAsmRegOp(OpId: MI->getOperandNo(I: &MO)))
234 return true;
235 }
236
237 return false;
238}
239
240float VirtRegAuxInfo::weightCalcHelper(LiveInterval &LI) {
241 MachineRegisterInfo &MRI = MF.getRegInfo();
242 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
243 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
244 MachineBasicBlock *MBB = nullptr;
245 float TotalWeight = 0;
246 unsigned NumInstr = 0; // Number of instructions using LI
247 SmallPtrSet<MachineInstr *, 8> Visited;
248
249 std::pair<unsigned, Register> TargetHint = MRI.getRegAllocationHint(VReg: LI.reg());
250
251 if (LI.isSpillable()) {
252 Register Reg = LI.reg();
253 Register Original = VRM.getOriginal(VirtReg: Reg);
254 const LiveInterval &OrigInt = LIS.getInterval(Reg: Original);
255 // li comes from a split of OrigInt. If OrigInt was marked
256 // as not spillable, make sure the new interval is marked
257 // as not spillable as well.
258 if (!OrigInt.isSpillable())
259 LI.markNotSpillable();
260 }
261
262 // Don't recompute spill weight for an unspillable register.
263 bool IsSpillable = LI.isSpillable();
264
265 // CopyHint is a sortable hint derived from a COPY instruction.
266 struct CopyHint {
267 Register Reg;
268 float Weight;
269 bool IsCSR;
270 CopyHint(Register R, float W, bool IsCSR)
271 : Reg(R), Weight(W), IsCSR(IsCSR) {}
272 bool operator<(const CopyHint &Rhs) const {
273 // Always prefer any physreg hint.
274 if (Reg.isPhysical() != Rhs.Reg.isPhysical())
275 return Reg.isPhysical();
276 if (Weight != Rhs.Weight)
277 return (Weight > Rhs.Weight);
278 // Prefer non-CSR to CSR.
279 if (Reg.isPhysical() && IsCSR != Rhs.IsCSR)
280 return !IsCSR;
281 return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
282 }
283 };
284
285 bool IsExiting = false;
286 SmallDenseMap<Register, float, 8> Hint;
287 for (MachineRegisterInfo::reg_instr_nodbg_iterator
288 I = MRI.reg_instr_nodbg_begin(RegNo: LI.reg()),
289 E = MRI.reg_instr_nodbg_end();
290 I != E;) {
291 MachineInstr *MI = &*(I++);
292
293 NumInstr++;
294 bool identityCopy = false;
295 auto DestSrc = TII.isCopyInstr(MI: *MI);
296 if (DestSrc) {
297 const MachineOperand *DestRegOp = DestSrc->Destination;
298 const MachineOperand *SrcRegOp = DestSrc->Source;
299 identityCopy = DestRegOp->getReg() == SrcRegOp->getReg() &&
300 DestRegOp->getSubReg() == SrcRegOp->getSubReg();
301 }
302
303 if (identityCopy || MI->isImplicitDef())
304 continue;
305 if (!Visited.insert(Ptr: MI).second)
306 continue;
307
308 // For terminators that produce values, ask the backend if the register is
309 // not spillable.
310 if (TII.isUnspillableTerminator(MI) &&
311 MI->definesRegister(Reg: LI.reg(), /*TRI=*/nullptr)) {
312 LI.markNotSpillable();
313 return -1.0f;
314 }
315
316 // Force Weight onto the stack so that x86 doesn't add hidden precision.
317 stack_float_t Weight = 1.0f;
318 if (IsSpillable) {
319 // Get loop info for mi.
320 if (MI->getParent() != MBB) {
321 MBB = MI->getParent();
322 const MachineLoop *Loop = Loops.getLoopFor(BB: MBB);
323 IsExiting = Loop ? Loop->isLoopExiting(BB: MBB) : false;
324 }
325
326 // Calculate instr weight.
327 bool Reads, Writes;
328 std::tie(args&: Reads, args&: Writes) = MI->readsWritesVirtualRegister(Reg: LI.reg());
329 Weight = LiveIntervals::getSpillWeight(isDef: Writes, isUse: Reads, MBFI: &MBFI, MI: *MI,
330 OptForSize: getCachedOptimizeForSize());
331
332 // Give extra weight to what looks like a loop induction variable update.
333 if (Writes && IsExiting && LIS.isLiveOutOfMBB(LR: LI, mbb: MBB))
334 Weight *= 3;
335
336 TotalWeight += Weight;
337 }
338
339 // Get allocation hints from copies.
340 if (!TII.isCopyInstr(MI: *MI))
341 continue;
342 Register HintReg = copyHint(MI, Reg: LI.reg(), TRI, MRI);
343 if (HintReg && (HintReg.isVirtual() || MRI.isAllocatable(PhysReg: HintReg)))
344 Hint[HintReg] += Weight;
345 }
346
347 // Pass all the sorted copy hints to mri.
348 if (Hint.size()) {
349 // Remove a generic hint if previously added by target.
350 if (TargetHint.first == 0 && TargetHint.second)
351 MRI.clearSimpleHint(VReg: LI.reg());
352
353 // Don't add the target-type hint again.
354 Register SkipReg = TargetHint.first != 0 ? TargetHint.second : Register();
355 SmallVector<CopyHint, 8> RegHints;
356 for (const auto &[Reg, Weight] : Hint) {
357 if (Reg != SkipReg)
358 RegHints.emplace_back(
359 Args: Reg, Args: Weight,
360 Args: Reg.isPhysical() ? TRI.isCalleeSavedPhysReg(PhysReg: Reg, MF) : false);
361 }
362 sort(C&: RegHints);
363 for (const auto &[Reg, _, __] : RegHints)
364 MRI.addRegAllocationHint(VReg: LI.reg(), PrefReg: Reg);
365
366 // Weakly boost the spill weight of hinted registers.
367 TotalWeight *= 1.01F;
368 }
369
370 // If the live interval was already unspillable, leave it that way.
371 if (!IsSpillable)
372 return -1.0;
373
374 // Mark li as unspillable if all live ranges are tiny and the interval
375 // is not live at any reg mask. If the interval is live at a reg mask
376 // spilling may be required. If li is live as use in statepoint instruction
377 // spilling may be required due to if we mark interval with use in statepoint
378 // as not spillable we are risky to end up with no register to allocate.
379 // At the same time STATEPOINT instruction is perfectly fine to have this
380 // operand on stack, so spilling such interval and folding its load from stack
381 // into instruction itself makes perfect sense.
382 if (LI.isZeroLength(Indexes: LIS.getSlotIndexes()) &&
383 !LI.isLiveAtIndexes(Slots: LIS.getRegMaskSlots()) &&
384 !isLiveAtStatepointVarArg(LI) && !canMemFoldInlineAsm(LI, MRI)) {
385 LI.markNotSpillable();
386 return -1.0;
387 }
388
389 // If all of the definitions of the interval are re-materializable,
390 // it is a preferred candidate for spilling.
391 // FIXME: this gets much more complicated once we support non-trivial
392 // re-materialization.
393 if (isRematerializable(LI, LIS, VRM, MRI, TII: *MF.getSubtarget().getInstrInfo()))
394 TotalWeight *= 0.5F;
395
396 // Finally, we scale the weight by the scale factor of register class.
397 const TargetRegisterClass *RC = MRI.getRegClass(Reg: LI.reg());
398 TotalWeight *= TRI.getSpillWeightScaleFactor(RC);
399
400 return normalize(UseDefFreq: TotalWeight, Size: LI.getSize(), NumInstr);
401}
402