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