/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/CalcSpillWeights.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===------------------------ CalcSpillWeights.cpp ------------------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | |
10 | | #include "llvm/CodeGen/CalcSpillWeights.h" |
11 | | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
12 | | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
13 | | #include "llvm/CodeGen/MachineFunction.h" |
14 | | #include "llvm/CodeGen/MachineLoopInfo.h" |
15 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
16 | | #include "llvm/CodeGen/VirtRegMap.h" |
17 | | #include "llvm/Support/Debug.h" |
18 | | #include "llvm/Support/raw_ostream.h" |
19 | | #include "llvm/Target/TargetInstrInfo.h" |
20 | | #include "llvm/Target/TargetRegisterInfo.h" |
21 | | #include "llvm/Target/TargetSubtargetInfo.h" |
22 | | using namespace llvm; |
23 | | |
24 | | #define DEBUG_TYPE "calcspillweights" |
25 | | |
26 | | void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS, |
27 | | MachineFunction &MF, |
28 | | VirtRegMap *VRM, |
29 | | const MachineLoopInfo &MLI, |
30 | | const MachineBlockFrequencyInfo &MBFI, |
31 | 587k | VirtRegAuxInfo::NormalizingFn norm) { |
32 | 587k | DEBUG(dbgs() << "********** Compute Spill Weights **********\n" |
33 | 587k | << "********** Function: " << MF.getName() << '\n'); |
34 | 587k | |
35 | 587k | MachineRegisterInfo &MRI = MF.getRegInfo(); |
36 | 587k | VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm); |
37 | 21.2M | for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e21.2M ; ++i20.6M ) { |
38 | 20.6M | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
39 | 20.6M | if (MRI.reg_nodbg_empty(Reg)) |
40 | 10.9M | continue; |
41 | 9.66M | VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg)); |
42 | 9.66M | } |
43 | 587k | } |
44 | | |
45 | | // Return the preferred allocation register for reg, given a COPY instruction. |
46 | | static unsigned copyHint(const MachineInstr *mi, unsigned reg, |
47 | | const TargetRegisterInfo &tri, |
48 | 8.81M | const MachineRegisterInfo &mri) { |
49 | 8.81M | unsigned sub, hreg, hsub; |
50 | 8.81M | if (mi->getOperand(0).getReg() == reg8.81M ) { |
51 | 3.25M | sub = mi->getOperand(0).getSubReg(); |
52 | 3.25M | hreg = mi->getOperand(1).getReg(); |
53 | 3.25M | hsub = mi->getOperand(1).getSubReg(); |
54 | 8.81M | } else { |
55 | 5.56M | sub = mi->getOperand(1).getSubReg(); |
56 | 5.56M | hreg = mi->getOperand(0).getReg(); |
57 | 5.56M | hsub = mi->getOperand(0).getSubReg(); |
58 | 5.56M | } |
59 | 8.81M | |
60 | 8.81M | if (!hreg) |
61 | 0 | return 0; |
62 | 8.81M | |
63 | 8.81M | if (8.81M TargetRegisterInfo::isVirtualRegister(hreg)8.81M ) |
64 | 1.17M | return sub == hsub ? 1.17M hreg1.06M : 0114k ; |
65 | 7.63M | |
66 | 7.63M | const TargetRegisterClass *rc = mri.getRegClass(reg); |
67 | 7.63M | |
68 | 7.63M | // Only allow physreg hints in rc. |
69 | 7.63M | if (sub == 0) |
70 | 7.45M | return rc->contains(hreg) ? 7.45M hreg7.30M : 0145k ; |
71 | 185k | |
72 | 185k | // reg:sub should match the physreg hreg. |
73 | 185k | return tri.getMatchingSuperReg(hreg, sub, rc); |
74 | 185k | } |
75 | | |
76 | | // Check if all values in LI are rematerializable |
77 | | static bool isRematerializable(const LiveInterval &LI, |
78 | | const LiveIntervals &LIS, |
79 | | VirtRegMap *VRM, |
80 | 7.02M | const TargetInstrInfo &TII) { |
81 | 7.02M | unsigned Reg = LI.reg; |
82 | 7.02M | unsigned Original = VRM ? VRM->getOriginal(Reg)7.02M : 00 ; |
83 | 7.02M | for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); |
84 | 8.61M | I != E8.61M ; ++I1.58M ) { |
85 | 7.28M | const VNInfo *VNI = *I; |
86 | 7.28M | if (VNI->isUnused()) |
87 | 263 | continue; |
88 | 7.28M | if (7.28M VNI->isPHIDef()7.28M ) |
89 | 148k | return false; |
90 | 7.13M | |
91 | 7.13M | MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); |
92 | 7.13M | assert(MI && "Dead valno in interval"); |
93 | 7.13M | |
94 | 7.13M | // Trace copies introduced by live range splitting. The inline |
95 | 7.13M | // spiller can rematerialize through these copies, so the spill |
96 | 7.13M | // weight must reflect this. |
97 | 7.13M | if (VRM7.13M ) { |
98 | 7.39M | while (MI->isFullCopy()7.39M ) { |
99 | 2.48M | // The copy destination must match the interval register. |
100 | 2.48M | if (MI->getOperand(0).getReg() != Reg) |
101 | 1.17k | return false; |
102 | 2.48M | |
103 | 2.48M | // Get the source register. |
104 | 2.48M | Reg = MI->getOperand(1).getReg(); |
105 | 2.48M | |
106 | 2.48M | // If the original (pre-splitting) registers match this |
107 | 2.48M | // copy came from a split. |
108 | 2.48M | if (!TargetRegisterInfo::isVirtualRegister(Reg) || |
109 | 402k | VRM->getOriginal(Reg) != Original) |
110 | 2.18M | return false; |
111 | 300k | |
112 | 300k | // Follow the copy live-in value. |
113 | 300k | const LiveInterval &SrcLI = LIS.getInterval(Reg); |
114 | 300k | LiveQueryResult SrcQ = SrcLI.Query(VNI->def); |
115 | 300k | VNI = SrcQ.valueIn(); |
116 | 300k | assert(VNI && "Copy from non-existing value"); |
117 | 300k | if (VNI->isPHIDef()) |
118 | 42.5k | return false; |
119 | 258k | MI = LIS.getInstructionFromIndex(VNI->def); |
120 | 258k | assert(MI && "Dead valno in interval"); |
121 | 258k | } |
122 | 7.13M | } |
123 | 7.13M | |
124 | 4.90M | if (4.90M !TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis())4.90M ) |
125 | 3.32M | return false; |
126 | 7.28M | } |
127 | 1.33M | return true; |
128 | 7.02M | } |
129 | | |
130 | | void |
131 | 10.3M | VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) { |
132 | 10.3M | MachineRegisterInfo &mri = MF.getRegInfo(); |
133 | 10.3M | const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo(); |
134 | 10.3M | MachineBasicBlock *mbb = nullptr; |
135 | 10.3M | MachineLoop *loop = nullptr; |
136 | 10.3M | bool isExiting = false; |
137 | 10.3M | float totalWeight = 0; |
138 | 10.3M | unsigned numInstr = 0; // Number of instructions using li |
139 | 10.3M | SmallPtrSet<MachineInstr*, 8> visited; |
140 | 10.3M | |
141 | 10.3M | // Find the best physreg hint and the best virtreg hint. |
142 | 10.3M | float bestPhys = 0, bestVirt = 0; |
143 | 10.3M | unsigned hintPhys = 0, hintVirt = 0; |
144 | 10.3M | |
145 | 10.3M | // Don't recompute a target specific hint. |
146 | 10.3M | bool noHint = mri.getRegAllocationHint(li.reg).first != 0; |
147 | 10.3M | |
148 | 10.3M | // Don't recompute spill weight for an unspillable register. |
149 | 10.3M | bool Spillable = li.isSpillable(); |
150 | 10.3M | |
151 | 10.3M | for (MachineRegisterInfo::reg_instr_iterator |
152 | 10.3M | I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end(); |
153 | 41.4M | I != E41.4M ; ) { |
154 | 31.0M | MachineInstr *mi = &*(I++); |
155 | 31.0M | numInstr++; |
156 | 31.0M | if (mi->isIdentityCopy() || 31.0M mi->isImplicitDef()31.0M || mi->isDebugValue()31.0M ) |
157 | 3.77k | continue; |
158 | 31.0M | if (31.0M !visited.insert(mi).second31.0M ) |
159 | 499k | continue; |
160 | 30.5M | |
161 | 30.5M | float weight = 1.0f; |
162 | 30.5M | if (Spillable30.5M ) { |
163 | 30.5M | // Get loop info for mi. |
164 | 30.5M | if (mi->getParent() != mbb30.5M ) { |
165 | 17.8M | mbb = mi->getParent(); |
166 | 17.8M | loop = Loops.getLoopFor(mbb); |
167 | 17.8M | isExiting = loop ? loop->isLoopExiting(mbb)6.06M : false11.7M ; |
168 | 17.8M | } |
169 | 30.5M | |
170 | 30.5M | // Calculate instr weight. |
171 | 30.5M | bool reads, writes; |
172 | 30.5M | std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg); |
173 | 30.5M | weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi); |
174 | 30.5M | |
175 | 30.5M | // Give extra weight to what looks like a loop induction variable update. |
176 | 30.5M | if (writes && 30.5M isExiting11.8M && LIS.isLiveOutOfMBB(li, mbb)1.57M ) |
177 | 572k | weight *= 3; |
178 | 30.5M | |
179 | 30.5M | totalWeight += weight; |
180 | 30.5M | } |
181 | 30.5M | |
182 | 30.5M | // Get allocation hints from copies. |
183 | 30.5M | if (noHint || 30.5M !mi->isCopy()30.5M ) |
184 | 21.7M | continue; |
185 | 8.81M | unsigned hint = copyHint(mi, li.reg, tri, mri); |
186 | 8.81M | if (!hint) |
187 | 273k | continue; |
188 | 8.54M | // Force hweight onto the stack so that x86 doesn't add hidden precision, |
189 | 8.54M | // making the comparison incorrectly pass (i.e., 1 > 1 == true??). |
190 | 8.54M | // |
191 | 8.54M | // FIXME: we probably shouldn't use floats at all. |
192 | 8.54M | volatile float hweight = Hint[hint] += weight; |
193 | 8.54M | if (TargetRegisterInfo::isPhysicalRegister(hint)8.54M ) { |
194 | 7.47M | if (hweight > bestPhys && 7.47M mri.isAllocatable(hint)6.98M ) { |
195 | 6.89M | bestPhys = hweight; |
196 | 6.89M | hintPhys = hint; |
197 | 6.89M | } |
198 | 8.54M | } else { |
199 | 1.06M | if (hweight > bestVirt1.06M ) { |
200 | 916k | bestVirt = hweight; |
201 | 916k | hintVirt = hint; |
202 | 916k | } |
203 | 1.06M | } |
204 | 31.0M | } |
205 | 10.3M | |
206 | 10.3M | Hint.clear(); |
207 | 10.3M | |
208 | 10.3M | // Always prefer the physreg hint. |
209 | 10.3M | if (unsigned hint10.3M = hintPhys ? hintPhys : hintVirt) { |
210 | 4.83M | mri.setRegAllocationHint(li.reg, 0, hint); |
211 | 4.83M | // Weakly boost the spill weight of hinted registers. |
212 | 4.83M | totalWeight *= 1.01F; |
213 | 4.83M | } |
214 | 10.3M | |
215 | 10.3M | // If the live interval was already unspillable, leave it that way. |
216 | 10.3M | if (!Spillable) |
217 | 0 | return; |
218 | 10.3M | |
219 | 10.3M | // Mark li as unspillable if all live ranges are tiny and the interval |
220 | 10.3M | // is not live at any reg mask. If the interval is live at a reg mask |
221 | 10.3M | // spilling may be required. |
222 | 10.3M | if (10.3M li.isZeroLength(LIS.getSlotIndexes()) && |
223 | 10.3M | !li.isLiveAtIndexes(LIS.getRegMaskSlots())3.27M ) { |
224 | 3.27M | li.markNotSpillable(); |
225 | 3.27M | return; |
226 | 3.27M | } |
227 | 7.02M | |
228 | 7.02M | // If all of the definitions of the interval are re-materializable, |
229 | 7.02M | // it is a preferred candidate for spilling. |
230 | 7.02M | // FIXME: this gets much more complicated once we support non-trivial |
231 | 7.02M | // re-materialization. |
232 | 7.02M | if (7.02M isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo())7.02M ) |
233 | 1.33M | totalWeight *= 0.5F; |
234 | 10.3M | |
235 | 10.3M | li.weight = normalize(totalWeight, li.getSize(), numInstr); |
236 | 10.3M | } |