LLVM 17.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"
25#include <cassert>
26#include <tuple>
27
28using namespace llvm;
29
30#define DEBUG_TYPE "calcspillweights"
31
33 LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
34 << "********** Function: " << MF.getName() << '\n');
35
37 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
39 if (MRI.reg_nodbg_empty(Reg))
40 continue;
42 }
43}
44
45// Return the preferred allocation register for reg, given a COPY instruction.
48 const MachineRegisterInfo &MRI) {
49 unsigned Sub, HSub;
50 Register HReg;
51 if (MI->getOperand(0).getReg() == Reg) {
52 Sub = MI->getOperand(0).getSubReg();
53 HReg = MI->getOperand(1).getReg();
54 HSub = MI->getOperand(1).getSubReg();
55 } else {
56 Sub = MI->getOperand(1).getSubReg();
57 HReg = MI->getOperand(0).getReg();
58 HSub = MI->getOperand(0).getSubReg();
59 }
60
61 if (!HReg)
62 return 0;
63
64 if (HReg.isVirtual())
65 return Sub == HSub ? HReg : Register();
66
67 const TargetRegisterClass *RC = MRI.getRegClass(Reg);
68 MCRegister CopiedPReg = HSub ? TRI.getSubReg(HReg, HSub) : HReg.asMCReg();
69 if (RC->contains(CopiedPReg))
70 return CopiedPReg;
71
72 // Check if reg:sub matches so that a super register could be hinted.
73 if (Sub)
74 return TRI.getMatchingSuperReg(CopiedPReg, Sub, RC);
75
76 return 0;
77}
78
79// Check if all values in LI are rematerializable
81 const LiveIntervals &LIS,
82 const VirtRegMap &VRM,
83 const TargetInstrInfo &TII) {
84 Register Reg = LI.reg();
85 Register Original = VRM.getOriginal(Reg);
87 I != E; ++I) {
88 const VNInfo *VNI = *I;
89 if (VNI->isUnused())
90 continue;
91 if (VNI->isPHIDef())
92 return false;
93
95 assert(MI && "Dead valno in interval");
96
97 // Trace copies introduced by live range splitting. The inline
98 // spiller can rematerialize through these copies, so the spill
99 // weight must reflect this.
100 while (MI->isFullCopy()) {
101 // The copy destination must match the interval register.
102 if (MI->getOperand(0).getReg() != Reg)
103 return false;
104
105 // Get the source register.
106 Reg = MI->getOperand(1).getReg();
107
108 // If the original (pre-splitting) registers match this
109 // copy came from a split.
110 if (!Reg.isVirtual() || VRM.getOriginal(Reg) != Original)
111 return false;
112
113 // Follow the copy live-in value.
114 const LiveInterval &SrcLI = LIS.getInterval(Reg);
115 LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
116 VNI = SrcQ.valueIn();
117 assert(VNI && "Copy from non-existing value");
118 if (VNI->isPHIDef())
119 return false;
120 MI = LIS.getInstructionFromIndex(VNI->def);
121 assert(MI && "Dead valno in interval");
122 }
123
124 if (!TII.isTriviallyReMaterializable(*MI))
125 return false;
126 }
127 return true;
128}
129
130bool VirtRegAuxInfo::isLiveAtStatepointVarArg(LiveInterval &LI) {
131 return any_of(VRM.getRegInfo().reg_operands(LI.reg()),
132 [](MachineOperand &MO) {
133 MachineInstr *MI = MO.getParent();
134 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
135 return false;
136 return StatepointOpers(MI).getVarIdx() <= MI->getOperandNo(&MO);
137 });
138}
139
141 float Weight = weightCalcHelper(LI);
142 // Check if unspillable.
143 if (Weight < 0)
144 return;
145 LI.setWeight(Weight);
146}
147
149 SlotIndex *End) {
153 MachineBasicBlock *MBB = nullptr;
154 MachineLoop *Loop = nullptr;
155 bool IsExiting = false;
156 float TotalWeight = 0;
157 unsigned NumInstr = 0; // Number of instructions using LI
159
160 std::pair<Register, Register> TargetHint = MRI.getRegAllocationHint(LI.reg());
161
162 if (LI.isSpillable()) {
163 Register Reg = LI.reg();
164 Register Original = VRM.getOriginal(Reg);
165 const LiveInterval &OrigInt = LIS.getInterval(Original);
166 // li comes from a split of OrigInt. If OrigInt was marked
167 // as not spillable, make sure the new interval is marked
168 // as not spillable as well.
169 if (!OrigInt.isSpillable())
170 LI.markNotSpillable();
171 }
172
173 // Don't recompute spill weight for an unspillable register.
174 bool IsSpillable = LI.isSpillable();
175
176 bool IsLocalSplitArtifact = Start && End;
177
178 // Do not update future local split artifacts.
179 bool ShouldUpdateLI = !IsLocalSplitArtifact;
180
181 if (IsLocalSplitArtifact) {
182 MachineBasicBlock *LocalMBB = LIS.getMBBFromIndex(*End);
183 assert(LocalMBB == LIS.getMBBFromIndex(*Start) &&
184 "start and end are expected to be in the same basic block");
185
186 // Local split artifact will have 2 additional copy instructions and they
187 // will be in the same BB.
188 // localLI = COPY other
189 // ...
190 // other = COPY localLI
191 TotalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, LocalMBB);
192 TotalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, LocalMBB);
193
194 NumInstr += 2;
195 }
196
197 // CopyHint is a sortable hint derived from a COPY instruction.
198 struct CopyHint {
199 const Register Reg;
200 const float Weight;
201 CopyHint(Register R, float W) : Reg(R), Weight(W) {}
202 bool operator<(const CopyHint &Rhs) const {
203 // Always prefer any physreg hint.
204 if (Reg.isPhysical() != Rhs.Reg.isPhysical())
205 return Reg.isPhysical();
206 if (Weight != Rhs.Weight)
207 return (Weight > Rhs.Weight);
208 return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
209 }
210 };
211
212 std::set<CopyHint> CopyHints;
215 I = MRI.reg_instr_nodbg_begin(LI.reg()),
216 E = MRI.reg_instr_nodbg_end();
217 I != E;) {
218 MachineInstr *MI = &*(I++);
219
220 // For local split artifacts, we are interested only in instructions between
221 // the expected start and end of the range.
223 if (IsLocalSplitArtifact && ((SI < *Start) || (SI > *End)))
224 continue;
225
226 NumInstr++;
227 if (MI->isIdentityCopy() || MI->isImplicitDef())
228 continue;
229 if (!Visited.insert(MI).second)
230 continue;
231
232 // For terminators that produce values, ask the backend if the register is
233 // not spillable.
234 if (TII.isUnspillableTerminator(MI) && MI->definesRegister(LI.reg())) {
235 LI.markNotSpillable();
236 return -1.0f;
237 }
238
239 float Weight = 1.0f;
240 if (IsSpillable) {
241 // Get loop info for mi.
242 if (MI->getParent() != MBB) {
243 MBB = MI->getParent();
244 Loop = Loops.getLoopFor(MBB);
245 IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
246 }
247
248 // Calculate instr weight.
249 bool Reads, Writes;
250 std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
251 Weight = LiveIntervals::getSpillWeight(Writes, Reads, &MBFI, *MI);
252
253 // Give extra weight to what looks like a loop induction variable update.
254 if (Writes && IsExiting && LIS.isLiveOutOfMBB(LI, MBB))
255 Weight *= 3;
256
257 TotalWeight += Weight;
258 }
259
260 // Get allocation hints from copies.
261 if (!MI->isCopy())
262 continue;
263 Register HintReg = copyHint(MI, LI.reg(), TRI, MRI);
264 if (!HintReg)
265 continue;
266 // Force hweight onto the stack so that x86 doesn't add hidden precision,
267 // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
268 //
269 // FIXME: we probably shouldn't use floats at all.
270 volatile float HWeight = Hint[HintReg] += Weight;
271 if (HintReg.isVirtual() || MRI.isAllocatable(HintReg))
272 CopyHints.insert(CopyHint(HintReg, HWeight));
273 }
274
275 // Pass all the sorted copy hints to mri.
276 if (ShouldUpdateLI && CopyHints.size()) {
277 // Remove a generic hint if previously added by target.
278 if (TargetHint.first == 0 && TargetHint.second)
279 MRI.clearSimpleHint(LI.reg());
280
281 SmallSet<Register, 4> HintedRegs;
282 for (const auto &Hint : CopyHints) {
283 if (!HintedRegs.insert(Hint.Reg).second ||
284 (TargetHint.first != 0 && Hint.Reg == TargetHint.second))
285 // Don't add the same reg twice or the target-type hint again.
286 continue;
287 MRI.addRegAllocationHint(LI.reg(), Hint.Reg);
288 }
289
290 // Weakly boost the spill weight of hinted registers.
291 TotalWeight *= 1.01F;
292 }
293
294 // If the live interval was already unspillable, leave it that way.
295 if (!IsSpillable)
296 return -1.0;
297
298 // Mark li as unspillable if all live ranges are tiny and the interval
299 // is not live at any reg mask. If the interval is live at a reg mask
300 // spilling may be required. If li is live as use in statepoint instruction
301 // spilling may be required due to if we mark interval with use in statepoint
302 // as not spillable we are risky to end up with no register to allocate.
303 // At the same time STATEPOINT instruction is perfectly fine to have this
304 // operand on stack, so spilling such interval and folding its load from stack
305 // into instruction itself makes perfect sense.
306 if (ShouldUpdateLI && LI.isZeroLength(LIS.getSlotIndexes()) &&
307 !LI.isLiveAtIndexes(LIS.getRegMaskSlots()) &&
308 !isLiveAtStatepointVarArg(LI)) {
309 LI.markNotSpillable();
310 return -1.0;
311 }
312
313 // If all of the definitions of the interval are re-materializable,
314 // it is a preferred candidate for spilling.
315 // FIXME: this gets much more complicated once we support non-trivial
316 // re-materialization.
317 if (isRematerializable(LI, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
318 TotalWeight *= 0.5F;
319
320 if (IsLocalSplitArtifact)
321 return normalize(TotalWeight, Start->distance(*End), NumInstr);
322 return normalize(TotalWeight, LI.getSize(), NumInstr);
323}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
unsigned Reg
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
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.
Definition: LoopInfo.h:242
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
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.
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:120
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:82
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:177
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:1742
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163