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
11#include "llvm/ADT/SmallSet.h"
24#include "llvm/Support/Debug.h"
27#include <cassert>
28#include <tuple>
29
30using namespace llvm;
31
32#define DEBUG_TYPE "calcspillweights"
33
35 LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
36 << "********** Function: " << MF.getName() << '\n');
37
39 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
41 if (MRI.reg_nodbg_empty(Reg))
42 continue;
44 }
45}
46
47// Return the preferred allocation register for reg, given a COPY instruction.
50 const MachineRegisterInfo &MRI) {
51 unsigned Sub, HSub;
52 Register HReg;
53 if (MI->getOperand(0).getReg() == Reg) {
54 Sub = MI->getOperand(0).getSubReg();
55 HReg = MI->getOperand(1).getReg();
56 HSub = MI->getOperand(1).getSubReg();
57 } else {
58 Sub = MI->getOperand(1).getSubReg();
59 HReg = MI->getOperand(0).getReg();
60 HSub = MI->getOperand(0).getSubReg();
61 }
62
63 if (!HReg)
64 return 0;
65
66 if (HReg.isVirtual())
67 return Sub == HSub ? HReg : Register();
68
69 const TargetRegisterClass *RC = MRI.getRegClass(Reg);
70 MCRegister CopiedPReg = HSub ? TRI.getSubReg(HReg, HSub) : HReg.asMCReg();
71 if (RC->contains(CopiedPReg))
72 return CopiedPReg;
73
74 // Check if reg:sub matches so that a super register could be hinted.
75 if (Sub)
76 return TRI.getMatchingSuperReg(CopiedPReg, Sub, RC);
77
78 return 0;
79}
80
81// Check if all values in LI are rematerializable
83 const LiveIntervals &LIS,
84 const VirtRegMap &VRM,
85 const TargetInstrInfo &TII) {
86 Register Reg = LI.reg();
87 Register Original = VRM.getOriginal(Reg);
89 I != E; ++I) {
90 const VNInfo *VNI = *I;
91 if (VNI->isUnused())
92 continue;
93 if (VNI->isPHIDef())
94 return false;
95
97 assert(MI && "Dead valno in interval");
98
99 // Trace copies introduced by live range splitting. The inline
100 // spiller can rematerialize through these copies, so the spill
101 // weight must reflect this.
102 while (TII.isFullCopyInstr(*MI)) {
103 // The copy destination must match the interval register.
104 if (MI->getOperand(0).getReg() != Reg)
105 return false;
106
107 // Get the source register.
108 Reg = MI->getOperand(1).getReg();
109
110 // If the original (pre-splitting) registers match this
111 // copy came from a split.
112 if (!Reg.isVirtual() || VRM.getOriginal(Reg) != Original)
113 return false;
114
115 // Follow the copy live-in value.
116 const LiveInterval &SrcLI = LIS.getInterval(Reg);
117 LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
118 VNI = SrcQ.valueIn();
119 assert(VNI && "Copy from non-existing value");
120 if (VNI->isPHIDef())
121 return false;
122 MI = LIS.getInstructionFromIndex(VNI->def);
123 assert(MI && "Dead valno in interval");
124 }
125
126 if (!TII.isTriviallyReMaterializable(*MI))
127 return false;
128 }
129 return true;
130}
131
132bool VirtRegAuxInfo::isLiveAtStatepointVarArg(LiveInterval &LI) {
133 return any_of(VRM.getRegInfo().reg_operands(LI.reg()),
134 [](MachineOperand &MO) {
135 MachineInstr *MI = MO.getParent();
136 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
137 return false;
138 return StatepointOpers(MI).getVarIdx() <= MO.getOperandNo();
139 });
140}
141
143 float Weight = weightCalcHelper(LI);
144 // Check if unspillable.
145 if (Weight < 0)
146 return;
147 LI.setWeight(Weight);
148}
149
151 const MachineRegisterInfo &MRI) {
152 for (const MachineOperand &MO : MRI.reg_operands(LI.reg())) {
153 const MachineInstr *MI = MO.getParent();
154 if (MI->isInlineAsm() && MI->mayFoldInlineAsmRegOp(MI->getOperandNo(&MO)))
155 return true;
156 }
157
158 return false;
159}
160
162 SlotIndex *End) {
166 MachineBasicBlock *MBB = nullptr;
167 float TotalWeight = 0;
168 unsigned NumInstr = 0; // Number of instructions using LI
170
171 std::pair<unsigned, Register> TargetHint = MRI.getRegAllocationHint(LI.reg());
172
173 if (LI.isSpillable()) {
174 Register Reg = LI.reg();
175 Register Original = VRM.getOriginal(Reg);
176 const LiveInterval &OrigInt = LIS.getInterval(Original);
177 // li comes from a split of OrigInt. If OrigInt was marked
178 // as not spillable, make sure the new interval is marked
179 // as not spillable as well.
180 if (!OrigInt.isSpillable())
181 LI.markNotSpillable();
182 }
183
184 // Don't recompute spill weight for an unspillable register.
185 bool IsSpillable = LI.isSpillable();
186
187 bool IsLocalSplitArtifact = Start && End;
188
189 // Do not update future local split artifacts.
190 bool ShouldUpdateLI = !IsLocalSplitArtifact;
191
192 if (IsLocalSplitArtifact) {
193 MachineBasicBlock *LocalMBB = LIS.getMBBFromIndex(*End);
194 assert(LocalMBB == LIS.getMBBFromIndex(*Start) &&
195 "start and end are expected to be in the same basic block");
196
197 // Local split artifact will have 2 additional copy instructions and they
198 // will be in the same BB.
199 // localLI = COPY other
200 // ...
201 // other = COPY localLI
202 TotalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, LocalMBB);
203 TotalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, LocalMBB);
204
205 NumInstr += 2;
206 }
207
208 // CopyHint is a sortable hint derived from a COPY instruction.
209 struct CopyHint {
210 const Register Reg;
211 const float Weight;
212 CopyHint(Register R, float W) : Reg(R), Weight(W) {}
213 bool operator<(const CopyHint &Rhs) const {
214 // Always prefer any physreg hint.
215 if (Reg.isPhysical() != Rhs.Reg.isPhysical())
216 return Reg.isPhysical();
217 if (Weight != Rhs.Weight)
218 return (Weight > Rhs.Weight);
219 return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
220 }
221 };
222
223 bool IsExiting = false;
224 std::set<CopyHint> CopyHints;
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 // similar to HWeight below.
263 stack_float_t Weight = 1.0f;
264 if (IsSpillable) {
265 // Get loop info for mi.
266 if (MI->getParent() != MBB) {
267 MBB = MI->getParent();
268 const MachineLoop *Loop = Loops.getLoopFor(MBB);
269 IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
270 }
271
272 // Calculate instr weight.
273 bool Reads, Writes;
274 std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
275 Weight = LiveIntervals::getSpillWeight(Writes, Reads, &MBFI, *MI);
276
277 // Give extra weight to what looks like a loop induction variable update.
278 if (Writes && IsExiting && LIS.isLiveOutOfMBB(LI, MBB))
279 Weight *= 3;
280
281 TotalWeight += Weight;
282 }
283
284 // Get allocation hints from copies.
285 if (!TII.isCopyInstr(*MI))
286 continue;
287 Register HintReg = copyHint(MI, LI.reg(), TRI, MRI);
288 if (!HintReg)
289 continue;
290 // Force HWeight onto the stack so that x86 doesn't add hidden precision,
291 // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
292 stack_float_t HWeight = Hint[HintReg] += Weight;
293 if (HintReg.isVirtual() || MRI.isAllocatable(HintReg))
294 CopyHints.insert(CopyHint(HintReg, HWeight));
295 }
296
297 // Pass all the sorted copy hints to mri.
298 if (ShouldUpdateLI && CopyHints.size()) {
299 // Remove a generic hint if previously added by target.
300 if (TargetHint.first == 0 && TargetHint.second)
301 MRI.clearSimpleHint(LI.reg());
302
303 SmallSet<Register, 4> HintedRegs;
304 for (const auto &Hint : CopyHints) {
305 if (!HintedRegs.insert(Hint.Reg).second ||
306 (TargetHint.first != 0 && Hint.Reg == TargetHint.second))
307 // Don't add the same reg twice or the target-type hint again.
308 continue;
309 MRI.addRegAllocationHint(LI.reg(), Hint.Reg);
310 }
311
312 // Weakly boost the spill weight of hinted registers.
313 TotalWeight *= 1.01F;
314 }
315
316 // If the live interval was already unspillable, leave it that way.
317 if (!IsSpillable)
318 return -1.0;
319
320 // Mark li as unspillable if all live ranges are tiny and the interval
321 // is not live at any reg mask. If the interval is live at a reg mask
322 // spilling may be required. If li is live as use in statepoint instruction
323 // spilling may be required due to if we mark interval with use in statepoint
324 // as not spillable we are risky to end up with no register to allocate.
325 // At the same time STATEPOINT instruction is perfectly fine to have this
326 // operand on stack, so spilling such interval and folding its load from stack
327 // into instruction itself makes perfect sense.
328 if (ShouldUpdateLI && LI.isZeroLength(LIS.getSlotIndexes()) &&
329 !LI.isLiveAtIndexes(LIS.getRegMaskSlots()) &&
330 !isLiveAtStatepointVarArg(LI) && !canMemFoldInlineAsm(LI, MRI)) {
331 LI.markNotSpillable();
332 return -1.0;
333 }
334
335 // If all of the definitions of the interval are re-materializable,
336 // it is a preferred candidate for spilling.
337 // FIXME: this gets much more complicated once we support non-trivial
338 // re-materialization.
339 if (isRematerializable(LI, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
340 TotalWeight *= 0.5F;
341
342 if (IsLocalSplitArtifact)
343 return normalize(TotalWeight, Start->distance(*End), NumInstr);
344 return normalize(TotalWeight, LI.getSize(), NumInstr);
345}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static bool canMemFoldInlineAsm(LiveInterval &LI, const MachineRegisterInfo &MRI)
#define LLVM_DEBUG(X)
Definition: Debug.h:101
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.
This file defines the SmallSet class.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
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.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
LiveInterval & getInterval(Register Reg)
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
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:44
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:368
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
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:169
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:92
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:778
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:1729
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163