1 //===- CalcSpillWeights.cpp -----------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
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"
29 #define DEBUG_TYPE "calcspillweights"
31 void llvm::calculateSpillWeightsAndHints(LiveIntervals
&LIS
,
34 const MachineLoopInfo
&MLI
,
35 const MachineBlockFrequencyInfo
&MBFI
,
36 VirtRegAuxInfo::NormalizingFn norm
) {
37 LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
38 << "********** Function: " << MF
.getName() << '\n');
40 MachineRegisterInfo
&MRI
= MF
.getRegInfo();
41 VirtRegAuxInfo
VRAI(MF
, LIS
, VRM
, MLI
, MBFI
, norm
);
42 for (unsigned i
= 0, e
= MRI
.getNumVirtRegs(); i
!= e
; ++i
) {
43 unsigned Reg
= TargetRegisterInfo::index2VirtReg(i
);
44 if (MRI
.reg_nodbg_empty(Reg
))
46 VRAI
.calculateSpillWeightAndHint(LIS
.getInterval(Reg
));
50 // Return the preferred allocation register for reg, given a COPY instruction.
51 static unsigned copyHint(const MachineInstr
*mi
, unsigned reg
,
52 const TargetRegisterInfo
&tri
,
53 const MachineRegisterInfo
&mri
) {
54 unsigned sub
, hreg
, hsub
;
55 if (mi
->getOperand(0).getReg() == reg
) {
56 sub
= mi
->getOperand(0).getSubReg();
57 hreg
= mi
->getOperand(1).getReg();
58 hsub
= mi
->getOperand(1).getSubReg();
60 sub
= mi
->getOperand(1).getSubReg();
61 hreg
= mi
->getOperand(0).getReg();
62 hsub
= mi
->getOperand(0).getSubReg();
68 if (TargetRegisterInfo::isVirtualRegister(hreg
))
69 return sub
== hsub
? hreg
: 0;
71 const TargetRegisterClass
*rc
= mri
.getRegClass(reg
);
72 unsigned CopiedPReg
= (hsub
? tri
.getSubReg(hreg
, hsub
) : hreg
);
73 if (rc
->contains(CopiedPReg
))
76 // Check if reg:sub matches so that a super register could be hinted.
78 return tri
.getMatchingSuperReg(CopiedPReg
, sub
, rc
);
83 // Check if all values in LI are rematerializable
84 static bool isRematerializable(const LiveInterval
&LI
,
85 const LiveIntervals
&LIS
,
87 const TargetInstrInfo
&TII
) {
88 unsigned Reg
= LI
.reg
;
89 unsigned Original
= VRM
? VRM
->getOriginal(Reg
) : 0;
90 for (LiveInterval::const_vni_iterator I
= LI
.vni_begin(), E
= LI
.vni_end();
92 const VNInfo
*VNI
= *I
;
98 MachineInstr
*MI
= LIS
.getInstructionFromIndex(VNI
->def
);
99 assert(MI
&& "Dead valno in interval");
101 // Trace copies introduced by live range splitting. The inline
102 // spiller can rematerialize through these copies, so the spill
103 // weight must reflect this.
105 while (MI
->isFullCopy()) {
106 // The copy destination must match the interval register.
107 if (MI
->getOperand(0).getReg() != Reg
)
110 // Get the source register.
111 Reg
= MI
->getOperand(1).getReg();
113 // If the original (pre-splitting) registers match this
114 // copy came from a split.
115 if (!TargetRegisterInfo::isVirtualRegister(Reg
) ||
116 VRM
->getOriginal(Reg
) != Original
)
119 // Follow the copy live-in value.
120 const LiveInterval
&SrcLI
= LIS
.getInterval(Reg
);
121 LiveQueryResult SrcQ
= SrcLI
.Query(VNI
->def
);
122 VNI
= SrcQ
.valueIn();
123 assert(VNI
&& "Copy from non-existing value");
126 MI
= LIS
.getInstructionFromIndex(VNI
->def
);
127 assert(MI
&& "Dead valno in interval");
131 if (!TII
.isTriviallyReMaterializable(*MI
, LIS
.getAliasAnalysis()))
137 void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval
&li
) {
138 float weight
= weightCalcHelper(li
);
139 // Check if unspillable.
145 float VirtRegAuxInfo::futureWeight(LiveInterval
&li
, SlotIndex start
,
147 return weightCalcHelper(li
, &start
, &end
);
150 float VirtRegAuxInfo::weightCalcHelper(LiveInterval
&li
, SlotIndex
*start
,
152 MachineRegisterInfo
&mri
= MF
.getRegInfo();
153 const TargetRegisterInfo
&tri
= *MF
.getSubtarget().getRegisterInfo();
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
159 SmallPtrSet
<MachineInstr
*, 8> visited
;
161 std::pair
<unsigned, unsigned> TargetHint
= mri
.getRegAllocationHint(li
.reg
);
163 // Don't recompute spill weight for an unspillable register.
164 bool Spillable
= li
.isSpillable();
166 bool localSplitArtifact
= start
&& end
;
168 // Do not update future local split artifacts.
169 bool updateLI
= !localSplitArtifact
;
171 if (localSplitArtifact
) {
172 MachineBasicBlock
*localMBB
= LIS
.getMBBFromIndex(*end
);
173 assert(localMBB
== LIS
.getMBBFromIndex(*start
) &&
174 "start and end are expected to be in the same basic block");
176 // Local split artifact will have 2 additional copy instructions and they
177 // will be in the same BB.
178 // localLI = COPY other
180 // other = COPY localLI
181 totalWeight
+= LiveIntervals::getSpillWeight(true, false, &MBFI
, localMBB
);
182 totalWeight
+= LiveIntervals::getSpillWeight(false, true, &MBFI
, localMBB
);
187 // CopyHint is a sortable hint derived from a COPY instruction.
192 CopyHint(unsigned R
, float W
, bool P
) :
193 Reg(R
), Weight(W
), IsPhys(P
) {}
194 bool operator<(const CopyHint
&rhs
) const {
195 // Always prefer any physreg hint.
196 if (IsPhys
!= rhs
.IsPhys
)
197 return (IsPhys
&& !rhs
.IsPhys
);
198 if (Weight
!= rhs
.Weight
)
199 return (Weight
> rhs
.Weight
);
200 return Reg
< rhs
.Reg
; // Tie-breaker.
203 std::set
<CopyHint
> CopyHints
;
205 for (MachineRegisterInfo::reg_instr_iterator
206 I
= mri
.reg_instr_begin(li
.reg
), E
= mri
.reg_instr_end();
208 MachineInstr
*mi
= &*(I
++);
210 // For local split artifacts, we are interested only in instructions between
211 // the expected start and end of the range.
212 SlotIndex si
= LIS
.getInstructionIndex(*mi
);
213 if (localSplitArtifact
&& ((si
< *start
) || (si
> *end
)))
217 if (mi
->isIdentityCopy() || mi
->isImplicitDef() || mi
->isDebugInstr())
219 if (!visited
.insert(mi
).second
)
224 // Get loop info for mi.
225 if (mi
->getParent() != mbb
) {
226 mbb
= mi
->getParent();
227 loop
= Loops
.getLoopFor(mbb
);
228 isExiting
= loop
? loop
->isLoopExiting(mbb
) : false;
231 // Calculate instr weight.
233 std::tie(reads
, writes
) = mi
->readsWritesVirtualRegister(li
.reg
);
234 weight
= LiveIntervals::getSpillWeight(writes
, reads
, &MBFI
, *mi
);
236 // Give extra weight to what looks like a loop induction variable update.
237 if (writes
&& isExiting
&& LIS
.isLiveOutOfMBB(li
, mbb
))
240 totalWeight
+= weight
;
243 // Get allocation hints from copies.
246 unsigned hint
= copyHint(mi
, li
.reg
, tri
, mri
);
249 // Force hweight onto the stack so that x86 doesn't add hidden precision,
250 // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
252 // FIXME: we probably shouldn't use floats at all.
253 volatile float hweight
= Hint
[hint
] += weight
;
254 if (TargetRegisterInfo::isVirtualRegister(hint
) || mri
.isAllocatable(hint
))
255 CopyHints
.insert(CopyHint(hint
, hweight
, tri
.isPhysicalRegister(hint
)));
260 // Pass all the sorted copy hints to mri.
261 if (updateLI
&& CopyHints
.size()) {
262 // Remove a generic hint if previously added by target.
263 if (TargetHint
.first
== 0 && TargetHint
.second
)
264 mri
.clearSimpleHint(li
.reg
);
266 std::set
<unsigned> HintedRegs
;
267 for (auto &Hint
: CopyHints
) {
268 if (!HintedRegs
.insert(Hint
.Reg
).second
||
269 (TargetHint
.first
!= 0 && Hint
.Reg
== TargetHint
.second
))
270 // Don't add the same reg twice or the target-type hint again.
272 mri
.addRegAllocationHint(li
.reg
, Hint
.Reg
);
275 // Weakly boost the spill weight of hinted registers.
276 totalWeight
*= 1.01F
;
279 // If the live interval was already unspillable, leave it that way.
283 // Mark li as unspillable if all live ranges are tiny and the interval
284 // is not live at any reg mask. If the interval is live at a reg mask
285 // spilling may be required.
286 if (updateLI
&& li
.isZeroLength(LIS
.getSlotIndexes()) &&
287 !li
.isLiveAtIndexes(LIS
.getRegMaskSlots())) {
288 li
.markNotSpillable();
292 // If all of the definitions of the interval are re-materializable,
293 // it is a preferred candidate for spilling.
294 // FIXME: this gets much more complicated once we support non-trivial
295 // re-materialization.
296 if (isRematerializable(li
, LIS
, VRM
, *MF
.getSubtarget().getInstrInfo()))
299 if (localSplitArtifact
)
300 return normalize(totalWeight
, start
->distance(*end
), numInstr
);
301 return normalize(totalWeight
, li
.getSize(), numInstr
);