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