LLVM 18.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 SlotIndex *End) {
154 MachineBasicBlock *MBB = nullptr;
155 MachineLoop *Loop = nullptr;
156 bool IsExiting = false;
157 float TotalWeight = 0;
158 unsigned NumInstr = 0; // Number of instructions using LI
160
161 std::pair<unsigned, Register> TargetHint = MRI.getRegAllocationHint(LI.reg());
162
163 if (LI.isSpillable()) {
164 Register Reg = LI.reg();
165 Register Original = VRM.getOriginal(Reg);
166 const LiveInterval &OrigInt = LIS.getInterval(Original);
167 // li comes from a split of OrigInt. If OrigInt was marked
168 // as not spillable, make sure the new interval is marked
169 // as not spillable as well.
170 if (!OrigInt.isSpillable())
171 LI.markNotSpillable();
172 }
173
174 // Don't recompute spill weight for an unspillable register.
175 bool IsSpillable = LI.isSpillable();
176
177 bool IsLocalSplitArtifact = Start && End;
178
179 // Do not update future local split artifacts.
180 bool ShouldUpdateLI = !IsLocalSplitArtifact;
181
182 if (IsLocalSplitArtifact) {
183 MachineBasicBlock *LocalMBB = LIS.getMBBFromIndex(*End);
184 assert(LocalMBB == LIS.getMBBFromIndex(*Start) &&
185 "start and end are expected to be in the same basic block");
186
187 // Local split artifact will have 2 additional copy instructions and they
188 // will be in the same BB.
189 // localLI = COPY other
190 // ...
191 // other = COPY localLI
192 TotalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, LocalMBB);
193 TotalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, LocalMBB);
194
195 NumInstr += 2;
196 }
197
198 // CopyHint is a sortable hint derived from a COPY instruction.
199 struct CopyHint {
200 const Register Reg;
201 const float Weight;
202 CopyHint(Register R, float W) : Reg(R), Weight(W) {}
203 bool operator<(const CopyHint &Rhs) const {
204 // Always prefer any physreg hint.
205 if (Reg.isPhysical() != Rhs.Reg.isPhysical())
206 return Reg.isPhysical();
207 if (Weight != Rhs.Weight)
208 return (Weight > Rhs.Weight);
209 return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
210 }
211 };
212
213 std::set<CopyHint> CopyHints;
216 I = MRI.reg_instr_nodbg_begin(LI.reg()),
217 E = MRI.reg_instr_nodbg_end();
218 I != E;) {
219 MachineInstr *MI = &*(I++);
220
221 // For local split artifacts, we are interested only in instructions between
222 // the expected start and end of the range.
224 if (IsLocalSplitArtifact && ((SI < *Start) || (SI > *End)))
225 continue;
226
227 NumInstr++;
228 bool identityCopy = false;
229 auto DestSrc = TII.isCopyInstr(*MI);
230 if (DestSrc) {
231 const MachineOperand *DestRegOp = DestSrc->Destination;
232 const MachineOperand *SrcRegOp = DestSrc->Source;
233 identityCopy = DestRegOp->getReg() == SrcRegOp->getReg() &&
234 DestRegOp->getSubReg() == SrcRegOp->getSubReg();
235 }
236
237 if (identityCopy || MI->isImplicitDef())
238 continue;
239 if (!Visited.insert(MI).second)
240 continue;
241
242 // For terminators that produce values, ask the backend if the register is
243 // not spillable.
244 if (TII.isUnspillableTerminator(MI) && MI->definesRegister(LI.reg())) {
245 LI.markNotSpillable();
246 return -1.0f;
247 }
248
249 float Weight = 1.0f;
250 if (IsSpillable) {
251 // Get loop info for mi.
252 if (MI->getParent() != MBB) {
253 MBB = MI->getParent();
254 Loop = Loops.getLoopFor(MBB);
255 IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
256 }
257
258 // Calculate instr weight.
259 bool Reads, Writes;
260 std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
261 Weight = LiveIntervals::getSpillWeight(Writes, Reads, &MBFI, *MI);
262
263 // Give extra weight to what looks like a loop induction variable update.
264 if (Writes && IsExiting && LIS.isLiveOutOfMBB(LI, MBB))
265 Weight *= 3;
266
267 TotalWeight += Weight;
268 }
269
270 // Get allocation hints from copies.
271 if (!TII.isCopyInstr(*MI))
272 continue;
273 Register HintReg = copyHint(MI, LI.reg(), TRI, MRI);
274 if (!HintReg)
275 continue;
276 // Force hweight onto the stack so that x86 doesn't add hidden precision,
277 // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
278 //
279 // FIXME: we probably shouldn't use floats at all.
280 volatile float HWeight = Hint[HintReg] += Weight;
281 if (HintReg.isVirtual() || MRI.isAllocatable(HintReg))
282 CopyHints.insert(CopyHint(HintReg, HWeight));
283 }
284
285 // Pass all the sorted copy hints to mri.
286 if (ShouldUpdateLI && CopyHints.size()) {
287 // Remove a generic hint if previously added by target.
288 if (TargetHint.first == 0 && TargetHint.second)
289 MRI.clearSimpleHint(LI.reg());
290
291 SmallSet<Register, 4> HintedRegs;
292 for (const auto &Hint : CopyHints) {
293 if (!HintedRegs.insert(Hint.Reg).second ||
294 (TargetHint.first != 0 && Hint.Reg == TargetHint.second))
295 // Don't add the same reg twice or the target-type hint again.
296 continue;
297 MRI.addRegAllocationHint(LI.reg(), Hint.Reg);
298 }
299
300 // Weakly boost the spill weight of hinted registers.
301 TotalWeight *= 1.01F;
302 }
303
304 // If the live interval was already unspillable, leave it that way.
305 if (!IsSpillable)
306 return -1.0;
307
308 // Mark li as unspillable if all live ranges are tiny and the interval
309 // is not live at any reg mask. If the interval is live at a reg mask
310 // spilling may be required. If li is live as use in statepoint instruction
311 // spilling may be required due to if we mark interval with use in statepoint
312 // as not spillable we are risky to end up with no register to allocate.
313 // At the same time STATEPOINT instruction is perfectly fine to have this
314 // operand on stack, so spilling such interval and folding its load from stack
315 // into instruction itself makes perfect sense.
316 if (ShouldUpdateLI && LI.isZeroLength(LIS.getSlotIndexes()) &&
317 !LI.isLiveAtIndexes(LIS.getRegMaskSlots()) &&
318 !isLiveAtStatepointVarArg(LI)) {
319 LI.markNotSpillable();
320 return -1.0;
321 }
322
323 // If all of the definitions of the interval are re-materializable,
324 // it is a preferred candidate for spilling.
325 // FIXME: this gets much more complicated once we support non-trivial
326 // re-materialization.
327 if (isRematerializable(LI, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
328 TotalWeight *= 0.5F;
329
330 if (IsLocalSplitArtifact)
331 return normalize(TotalWeight, Start->distance(*End), NumInstr);
332 return normalize(TotalWeight, LI.getSize(), NumInstr);
333}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:469
SmallVector< uint32_t, 0 > Writes
Definition: ELF_riscv.cpp:486
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:686
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Definition: LiveInterval.h:822
Register reg() const
Definition: LiveInterval.h:717
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:819
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange's.
void setWeight(float Value)
Definition: LiveInterval.h:720
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:586
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:541
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:47
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:68
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
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:1734
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163