LLVM 19.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"
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 += LiveIntervals::getSpillWeight(true, false, &MBFI, LocalMBB);
202 TotalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, LocalMBB);
203
204 NumInstr += 2;
205 }
206
207 // CopyHint is a sortable hint derived from a COPY instruction.
208 struct CopyHint {
209 const Register Reg;
210 const float Weight;
211 CopyHint(Register R, float W) : Reg(R), Weight(W) {}
212 bool operator<(const CopyHint &Rhs) const {
213 // Always prefer any physreg hint.
214 if (Reg.isPhysical() != Rhs.Reg.isPhysical())
215 return Reg.isPhysical();
216 if (Weight != Rhs.Weight)
217 return (Weight > Rhs.Weight);
218 return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
219 }
220 };
221
222 bool IsExiting = false;
223 std::set<CopyHint> CopyHints;
226 I = MRI.reg_instr_nodbg_begin(LI.reg()),
227 E = MRI.reg_instr_nodbg_end();
228 I != E;) {
229 MachineInstr *MI = &*(I++);
230
231 // For local split artifacts, we are interested only in instructions between
232 // the expected start and end of the range.
234 if (IsLocalSplitArtifact && ((SI < *Start) || (SI > *End)))
235 continue;
236
237 NumInstr++;
238 bool identityCopy = false;
239 auto DestSrc = TII.isCopyInstr(*MI);
240 if (DestSrc) {
241 const MachineOperand *DestRegOp = DestSrc->Destination;
242 const MachineOperand *SrcRegOp = DestSrc->Source;
243 identityCopy = DestRegOp->getReg() == SrcRegOp->getReg() &&
244 DestRegOp->getSubReg() == SrcRegOp->getSubReg();
245 }
246
247 if (identityCopy || MI->isImplicitDef())
248 continue;
249 if (!Visited.insert(MI).second)
250 continue;
251
252 // For terminators that produce values, ask the backend if the register is
253 // not spillable.
254 if (TII.isUnspillableTerminator(MI) && MI->definesRegister(LI.reg())) {
255 LI.markNotSpillable();
256 return -1.0f;
257 }
258
259 float Weight = 1.0f;
260 if (IsSpillable) {
261 // Get loop info for mi.
262 if (MI->getParent() != MBB) {
263 MBB = MI->getParent();
264 const MachineLoop *Loop = Loops.getLoopFor(MBB);
265 IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
266 }
267
268 // Calculate instr weight.
269 bool Reads, Writes;
270 std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
271 Weight = LiveIntervals::getSpillWeight(Writes, Reads, &MBFI, *MI);
272
273 // Give extra weight to what looks like a loop induction variable update.
274 if (Writes && IsExiting && LIS.isLiveOutOfMBB(LI, MBB))
275 Weight *= 3;
276
277 TotalWeight += Weight;
278 }
279
280 // Get allocation hints from copies.
281 if (!TII.isCopyInstr(*MI))
282 continue;
283 Register HintReg = copyHint(MI, LI.reg(), TRI, MRI);
284 if (!HintReg)
285 continue;
286 // Force hweight onto the stack so that x86 doesn't add hidden precision,
287 // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
288 //
289 // FIXME: we probably shouldn't use floats at all.
290 volatile float HWeight = Hint[HintReg] += Weight;
291 if (HintReg.isVirtual() || MRI.isAllocatable(HintReg))
292 CopyHints.insert(CopyHint(HintReg, HWeight));
293 }
294
295 // Pass all the sorted copy hints to mri.
296 if (ShouldUpdateLI && CopyHints.size()) {
297 // Remove a generic hint if previously added by target.
298 if (TargetHint.first == 0 && TargetHint.second)
299 MRI.clearSimpleHint(LI.reg());
300
301 SmallSet<Register, 4> HintedRegs;
302 for (const auto &Hint : CopyHints) {
303 if (!HintedRegs.insert(Hint.Reg).second ||
304 (TargetHint.first != 0 && Hint.Reg == TargetHint.second))
305 // Don't add the same reg twice or the target-type hint again.
306 continue;
307 MRI.addRegAllocationHint(LI.reg(), Hint.Reg);
308 }
309
310 // Weakly boost the spill weight of hinted registers.
311 TotalWeight *= 1.01F;
312 }
313
314 // If the live interval was already unspillable, leave it that way.
315 if (!IsSpillable)
316 return -1.0;
317
318 // Mark li as unspillable if all live ranges are tiny and the interval
319 // is not live at any reg mask. If the interval is live at a reg mask
320 // spilling may be required. If li is live as use in statepoint instruction
321 // spilling may be required due to if we mark interval with use in statepoint
322 // as not spillable we are risky to end up with no register to allocate.
323 // At the same time STATEPOINT instruction is perfectly fine to have this
324 // operand on stack, so spilling such interval and folding its load from stack
325 // into instruction itself makes perfect sense.
326 if (ShouldUpdateLI && LI.isZeroLength(LIS.getSlotIndexes()) &&
327 !LI.isLiveAtIndexes(LIS.getRegMaskSlots()) &&
328 !isLiveAtStatepointVarArg(LI) && !canMemFoldInlineAsm(LI, MRI)) {
329 LI.markNotSpillable();
330 return -1.0;
331 }
332
333 // If all of the definitions of the interval are re-materializable,
334 // it is a preferred candidate for spilling.
335 // FIXME: this gets much more complicated once we support non-trivial
336 // re-materialization.
337 if (isRematerializable(LI, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
338 TotalWeight *= 0.5F;
339
340 if (IsLocalSplitArtifact)
341 return normalize(TotalWeight, Start->distance(*End), NumInstr);
342 return normalize(TotalWeight, LI.getSize(), NumInstr);
343}
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:220
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.
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
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
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:68
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
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
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:1738
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163