LLVM 20.0.0git
CalcSpillWeights.cpp
Go to the documentation of this file.
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
23#include "llvm/Support/Debug.h"
26#include <cassert>
27#include <tuple>
28
29using namespace llvm;
30
31#define DEBUG_TYPE "calcspillweights"
32
34 LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
35 << "********** Function: " << MF.getName() << '\n');
36
38 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
40 if (MRI.reg_nodbg_empty(Reg))
41 continue;
43 }
44}
45
46// Return the preferred allocation register for reg, given a COPY instruction.
49 const MachineRegisterInfo &MRI) {
50 unsigned Sub, HSub;
51 Register HReg;
52 if (MI->getOperand(0).getReg() == Reg) {
53 Sub = MI->getOperand(0).getSubReg();
54 HReg = MI->getOperand(1).getReg();
55 HSub = MI->getOperand(1).getSubReg();
56 } else {
57 Sub = MI->getOperand(1).getSubReg();
58 HReg = MI->getOperand(0).getReg();
59 HSub = MI->getOperand(0).getSubReg();
60 }
61
62 if (!HReg)
63 return 0;
64
65 if (HReg.isVirtual())
66 return Sub == HSub ? HReg : Register();
67
68 const TargetRegisterClass *RC = MRI.getRegClass(Reg);
69 MCRegister CopiedPReg = HSub ? TRI.getSubReg(HReg, HSub) : HReg.asMCReg();
70 if (RC->contains(CopiedPReg))
71 return CopiedPReg;
72
73 // Check if reg:sub matches so that a super register could be hinted.
74 if (Sub)
75 return TRI.getMatchingSuperReg(CopiedPReg, Sub, RC);
76
77 return 0;
78}
79
80// Check if all values in LI are rematerializable
82 const LiveIntervals &LIS,
83 const VirtRegMap &VRM,
84 const TargetInstrInfo &TII) {
85 Register Reg = LI.reg();
86 Register Original = VRM.getOriginal(Reg);
88 I != E; ++I) {
89 const VNInfo *VNI = *I;
90 if (VNI->isUnused())
91 continue;
92 if (VNI->isPHIDef())
93 return false;
94
96 assert(MI && "Dead valno in interval");
97
98 // Trace copies introduced by live range splitting. The inline
99 // spiller can rematerialize through these copies, so the spill
100 // weight must reflect this.
101 while (TII.isFullCopyInstr(*MI)) {
102 // The copy destination must match the interval register.
103 if (MI->getOperand(0).getReg() != Reg)
104 return false;
105
106 // Get the source register.
107 Reg = MI->getOperand(1).getReg();
108
109 // If the original (pre-splitting) registers match this
110 // copy came from a split.
111 if (!Reg.isVirtual() || VRM.getOriginal(Reg) != Original)
112 return false;
113
114 // Follow the copy live-in value.
115 const LiveInterval &SrcLI = LIS.getInterval(Reg);
116 LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
117 VNI = SrcQ.valueIn();
118 assert(VNI && "Copy from non-existing value");
119 if (VNI->isPHIDef())
120 return false;
121 MI = LIS.getInstructionFromIndex(VNI->def);
122 assert(MI && "Dead valno in interval");
123 }
124
125 if (!TII.isTriviallyReMaterializable(*MI))
126 return false;
127 }
128 return true;
129}
130
131bool VirtRegAuxInfo::isLiveAtStatepointVarArg(LiveInterval &LI) {
132 return any_of(VRM.getRegInfo().reg_operands(LI.reg()),
133 [](MachineOperand &MO) {
134 MachineInstr *MI = MO.getParent();
135 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
136 return false;
137 return StatepointOpers(MI).getVarIdx() <= MO.getOperandNo();
138 });
139}
140
142 float Weight = weightCalcHelper(LI);
143 // Check if unspillable.
144 if (Weight < 0)
145 return;
146 LI.setWeight(Weight);
147}
148
150 const MachineRegisterInfo &MRI) {
151 for (const MachineOperand &MO : MRI.reg_operands(LI.reg())) {
152 const MachineInstr *MI = MO.getParent();
153 if (MI->isInlineAsm() && MI->mayFoldInlineAsmRegOp(MI->getOperandNo(&MO)))
154 return true;
155 }
156
157 return false;
158}
159
161 SlotIndex *End) {
165 MachineBasicBlock *MBB = nullptr;
166 float TotalWeight = 0;
167 unsigned NumInstr = 0; // Number of instructions using LI
169
170 std::pair<unsigned, Register> TargetHint = MRI.getRegAllocationHint(LI.reg());
171
172 if (LI.isSpillable()) {
173 Register Reg = LI.reg();
174 Register Original = VRM.getOriginal(Reg);
175 const LiveInterval &OrigInt = LIS.getInterval(Original);
176 // li comes from a split of OrigInt. If OrigInt was marked
177 // as not spillable, make sure the new interval is marked
178 // as not spillable as well.
179 if (!OrigInt.isSpillable())
180 LI.markNotSpillable();
181 }
182
183 // Don't recompute spill weight for an unspillable register.
184 bool IsSpillable = LI.isSpillable();
185
186 bool IsLocalSplitArtifact = Start && End;
187
188 // Do not update future local split artifacts.
189 bool ShouldUpdateLI = !IsLocalSplitArtifact;
190
191 if (IsLocalSplitArtifact) {
192 MachineBasicBlock *LocalMBB = LIS.getMBBFromIndex(*End);
193 assert(LocalMBB == LIS.getMBBFromIndex(*Start) &&
194 "start and end are expected to be in the same basic block");
195
196 // Local split artifact will have 2 additional copy instructions and they
197 // will be in the same BB.
198 // localLI = COPY other
199 // ...
200 // other = COPY localLI
201 TotalWeight +=
202 LiveIntervals::getSpillWeight(true, false, &MBFI, LocalMBB, PSI);
203 TotalWeight +=
204 LiveIntervals::getSpillWeight(false, true, &MBFI, LocalMBB, PSI);
205
206 NumInstr += 2;
207 }
208
209 // CopyHint is a sortable hint derived from a COPY instruction.
210 struct CopyHint {
212 float Weight;
213 CopyHint(Register R, float W) : Reg(R), Weight(W) {}
214 bool operator<(const CopyHint &Rhs) const {
215 // Always prefer any physreg hint.
216 if (Reg.isPhysical() != Rhs.Reg.isPhysical())
217 return Reg.isPhysical();
218 if (Weight != Rhs.Weight)
219 return (Weight > Rhs.Weight);
220 return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
221 }
222 };
223
224 bool IsExiting = false;
227 I = MRI.reg_instr_nodbg_begin(LI.reg()),
228 E = MRI.reg_instr_nodbg_end();
229 I != E;) {
230 MachineInstr *MI = &*(I++);
231
232 // For local split artifacts, we are interested only in instructions between
233 // the expected start and end of the range.
235 if (IsLocalSplitArtifact && ((SI < *Start) || (SI > *End)))
236 continue;
237
238 NumInstr++;
239 bool identityCopy = false;
240 auto DestSrc = TII.isCopyInstr(*MI);
241 if (DestSrc) {
242 const MachineOperand *DestRegOp = DestSrc->Destination;
243 const MachineOperand *SrcRegOp = DestSrc->Source;
244 identityCopy = DestRegOp->getReg() == SrcRegOp->getReg() &&
245 DestRegOp->getSubReg() == SrcRegOp->getSubReg();
246 }
247
248 if (identityCopy || MI->isImplicitDef())
249 continue;
250 if (!Visited.insert(MI).second)
251 continue;
252
253 // For terminators that produce values, ask the backend if the register is
254 // not spillable.
255 if (TII.isUnspillableTerminator(MI) &&
256 MI->definesRegister(LI.reg(), /*TRI=*/nullptr)) {
257 LI.markNotSpillable();
258 return -1.0f;
259 }
260
261 // Force Weight onto the stack so that x86 doesn't add hidden precision.
262 stack_float_t Weight = 1.0f;
263 if (IsSpillable) {
264 // Get loop info for mi.
265 if (MI->getParent() != MBB) {
266 MBB = MI->getParent();
267 const MachineLoop *Loop = Loops.getLoopFor(MBB);
268 IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
269 }
270
271 // Calculate instr weight.
272 bool Reads, Writes;
273 std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
274 Weight = LiveIntervals::getSpillWeight(Writes, Reads, &MBFI, *MI, PSI);
275
276 // Give extra weight to what looks like a loop induction variable update.
277 if (Writes && IsExiting && LIS.isLiveOutOfMBB(LI, MBB))
278 Weight *= 3;
279
280 TotalWeight += Weight;
281 }
282
283 // Get allocation hints from copies.
284 if (!TII.isCopyInstr(*MI))
285 continue;
286 Register HintReg = copyHint(MI, LI.reg(), TRI, MRI);
287 if (HintReg && (HintReg.isVirtual() || MRI.isAllocatable(HintReg)))
288 Hint[HintReg] += Weight;
289 }
290
291 // Pass all the sorted copy hints to mri.
292 if (ShouldUpdateLI && Hint.size()) {
293 // Remove a generic hint if previously added by target.
294 if (TargetHint.first == 0 && TargetHint.second)
295 MRI.clearSimpleHint(LI.reg());
296
297 // Don't add the target-type hint again.
298 Register SkipReg = TargetHint.first != 0 ? TargetHint.second : Register();
300 for (const auto &[Reg, Weight] : Hint) {
301 if (Reg != SkipReg)
302 RegHints.emplace_back(Reg, Weight);
303 }
304 sort(RegHints);
305 for (const auto &[Reg, Weight] : RegHints)
306 MRI.addRegAllocationHint(LI.reg(), Reg);
307
308 // Weakly boost the spill weight of hinted registers.
309 TotalWeight *= 1.01F;
310 }
311
312 // If the live interval was already unspillable, leave it that way.
313 if (!IsSpillable)
314 return -1.0;
315
316 // Mark li as unspillable if all live ranges are tiny and the interval
317 // is not live at any reg mask. If the interval is live at a reg mask
318 // spilling may be required. If li is live as use in statepoint instruction
319 // spilling may be required due to if we mark interval with use in statepoint
320 // as not spillable we are risky to end up with no register to allocate.
321 // At the same time STATEPOINT instruction is perfectly fine to have this
322 // operand on stack, so spilling such interval and folding its load from stack
323 // into instruction itself makes perfect sense.
324 if (ShouldUpdateLI && LI.isZeroLength(LIS.getSlotIndexes()) &&
325 !LI.isLiveAtIndexes(LIS.getRegMaskSlots()) &&
326 !isLiveAtStatepointVarArg(LI) && !canMemFoldInlineAsm(LI, MRI)) {
327 LI.markNotSpillable();
328 return -1.0;
329 }
330
331 // If all of the definitions of the interval are re-materializable,
332 // it is a preferred candidate for spilling.
333 // FIXME: this gets much more complicated once we support non-trivial
334 // re-materialization.
335 if (isRematerializable(LI, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
336 TotalWeight *= 0.5F;
337
338 if (IsLocalSplitArtifact)
339 return normalize(TotalWeight, Start->distance(*End), NumInstr);
340 return normalize(TotalWeight, LI.getSize(), NumInstr);
341}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static bool canMemFoldInlineAsm(LiveInterval &LI, const MachineRegisterInfo &MRI)
#define LLVM_DEBUG(...)
Definition: Debug.h:106
bool End
Definition: ELF_riscv.cpp:480
SmallVector< uint32_t, 0 > Writes
Definition: ELF_riscv.cpp:497
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
unsigned Reg
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
unsigned size() const
Definition: DenseMap.h:99
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Definition: LiveInterval.h:829
Register reg() const
Definition: LiveInterval.h:718
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:826
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
void setWeight(float Value)
Definition: LiveInterval.h:721
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
SlotIndexes * getSlotIndexes() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI, ProfileSummaryInfo *PSI=nullptr)
Calculate the spill weight to assign to a single instruction.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
LiveInterval & getInterval(Register Reg)
bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Result of a LiveRange query.
Definition: LiveInterval.h:90
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
Definition: LiveInterval.h:105
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
vni_iterator vni_begin()
Definition: LiveInterval.h:224
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
Definition: LiveInterval.h:587
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:542
vni_iterator vni_end()
Definition: LiveInterval.h:225
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:39
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
Register getReg() const
getReg - Returns the register number.
defusechain_iterator - This class provides iterator support for machine operands in the function that...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
iterator_range< reg_iterator > reg_operands(Register Reg) const
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:110
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:65
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:384
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:519
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
TargetInstrInfo - Interface to description of machine instruction set.
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Definition: LiveInterval.h:78
static Register copyHint(const MachineInstr *MI, unsigned Reg, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI)
Return the preferred allocation register for reg, given a COPY instruction.
float weightCalcHelper(LiveInterval &LI, SlotIndex *Start=nullptr, SlotIndex *End=nullptr)
Helper function for weight calculations.
void calculateSpillWeightsAndHints()
Compute spill weights and allocation hints for all virtual register live intervals.
virtual float normalize(float UseDefFreq, unsigned Size, unsigned NumInstr)
Weight normalization function.
static bool isRematerializable(const LiveInterval &LI, const LiveIntervals &LIS, const VirtRegMap &VRM, const TargetInstrInfo &TII)
Determine if all values in LI are rematerializable.
void calculateSpillWeightAndHint(LiveInterval &LI)
(re)compute li's spill weight and allocation hint.
Register getOriginal(Register VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting.
Definition: VirtRegMap.h:154
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:79
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
float stack_float_t
Type to force float point values onto the stack, so that x86 doesn't add hidden precision,...
Definition: MathExtras.h:786
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:361
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1746
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1664
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163