/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LivePhysRegs.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===// |
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 | | // This file implements the LivePhysRegs utility for tracking liveness of |
11 | | // physical registers across machine instructions in forward or backward order. |
12 | | // A more detailed description can be found in the corresponding header file. |
13 | | // |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #include "llvm/CodeGen/LivePhysRegs.h" |
17 | | #include "llvm/CodeGen/MachineFrameInfo.h" |
18 | | #include "llvm/CodeGen/MachineFunction.h" |
19 | | #include "llvm/CodeGen/MachineInstrBundle.h" |
20 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
21 | | #include "llvm/Support/Debug.h" |
22 | | #include "llvm/Support/raw_ostream.h" |
23 | | using namespace llvm; |
24 | | |
25 | | |
26 | | /// \brief Remove all registers from the set that get clobbered by the register |
27 | | /// mask. |
28 | | /// The clobbers set will be the list of live registers clobbered |
29 | | /// by the regmask. |
30 | | void LivePhysRegs::removeRegsInMask(const MachineOperand &MO, |
31 | 282k | SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers) { |
32 | 282k | SparseSet<unsigned>::iterator LRI = LiveRegs.begin(); |
33 | 7.85M | while (LRI != LiveRegs.end()7.85M ) { |
34 | 7.56M | if (MO.clobbersPhysReg(*LRI)7.56M ) { |
35 | 488k | if (Clobbers) |
36 | 467 | Clobbers->push_back(std::make_pair(*LRI, &MO)); |
37 | 488k | LRI = LiveRegs.erase(LRI); |
38 | 488k | } else |
39 | 7.08M | ++LRI; |
40 | 7.56M | } |
41 | 282k | } |
42 | | |
43 | | /// Remove defined registers and regmask kills from the set. |
44 | 2.30M | void LivePhysRegs::removeDefs(const MachineInstr &MI) { |
45 | 11.0M | for (ConstMIBundleOperands O(MI); O.isValid()11.0M ; ++O8.70M ) { |
46 | 8.70M | if (O->isReg()8.70M ) { |
47 | 6.45M | if (!O->isDef()) |
48 | 3.64M | continue; |
49 | 2.80M | unsigned Reg = O->getReg(); |
50 | 2.80M | if (!TargetRegisterInfo::isPhysicalRegister(Reg)) |
51 | 7 | continue; |
52 | 2.80M | removeReg(Reg); |
53 | 8.70M | } else if (2.24M O->isRegMask()2.24M ) |
54 | 265k | removeRegsInMask(*O); |
55 | 8.70M | } |
56 | 2.30M | } |
57 | | |
58 | | /// Add uses to the set. |
59 | 2.30M | void LivePhysRegs::addUses(const MachineInstr &MI) { |
60 | 11.0M | for (ConstMIBundleOperands O(MI); O.isValid()11.0M ; ++O8.70M ) { |
61 | 8.70M | if (!O->isReg() || 8.70M !O->readsReg()6.45M ) |
62 | 5.11M | continue; |
63 | 3.59M | unsigned Reg = O->getReg(); |
64 | 3.59M | if (!TargetRegisterInfo::isPhysicalRegister(Reg)) |
65 | 507k | continue; |
66 | 3.08M | addReg(Reg); |
67 | 3.08M | } |
68 | 2.30M | } |
69 | | |
70 | | /// Simulates liveness when stepping backwards over an instruction(bundle): |
71 | | /// Remove Defs, add uses. This is the recommended way of calculating liveness. |
72 | 2.28M | void LivePhysRegs::stepBackward(const MachineInstr &MI) { |
73 | 2.28M | // Remove defined registers and regmask kills from the set. |
74 | 2.28M | removeDefs(MI); |
75 | 2.28M | |
76 | 2.28M | // Add uses to the set. |
77 | 2.28M | addUses(MI); |
78 | 2.28M | } |
79 | | |
80 | | /// Simulates liveness when stepping forward over an instruction(bundle): Remove |
81 | | /// killed-uses, add defs. This is the not recommended way, because it depends |
82 | | /// on accurate kill flags. If possible use stepBackward() instead of this |
83 | | /// function. |
84 | | void LivePhysRegs::stepForward(const MachineInstr &MI, |
85 | 8.05k | SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) { |
86 | 8.05k | // Remove killed registers from the set. |
87 | 50.5k | for (ConstMIBundleOperands O(MI); O.isValid()50.5k ; ++O42.5k ) { |
88 | 42.5k | if (O->isReg()42.5k ) { |
89 | 27.0k | unsigned Reg = O->getReg(); |
90 | 27.0k | if (!TargetRegisterInfo::isPhysicalRegister(Reg)) |
91 | 1.58k | continue; |
92 | 25.4k | if (25.4k O->isDef()25.4k ) { |
93 | 8.05k | // Note, dead defs are still recorded. The caller should decide how to |
94 | 8.05k | // handle them. |
95 | 8.05k | Clobbers.push_back(std::make_pair(Reg, &*O)); |
96 | 25.4k | } else { |
97 | 17.4k | if (!O->isKill()) |
98 | 13.2k | continue; |
99 | 17.4k | assert(O->isUse()); |
100 | 4.21k | removeReg(Reg); |
101 | 4.21k | } |
102 | 42.5k | } else if (15.4k O->isRegMask()15.4k ) |
103 | 308 | removeRegsInMask(*O, &Clobbers); |
104 | 42.5k | } |
105 | 8.05k | |
106 | 8.05k | // Add defs to the set. |
107 | 24.9k | for (auto Reg : Clobbers) { |
108 | 24.9k | // Skip dead defs. They shouldn't be added to the set. |
109 | 24.9k | if (Reg.second->isReg() && 24.9k Reg.second->isDead()22.6k ) |
110 | 1.38k | continue; |
111 | 23.5k | addReg(Reg.first); |
112 | 23.5k | } |
113 | 8.05k | } |
114 | | |
115 | | /// Prin the currently live registers to OS. |
116 | 0 | void LivePhysRegs::print(raw_ostream &OS) const { |
117 | 0 | OS << "Live Registers:"; |
118 | 0 | if (!TRI0 ) { |
119 | 0 | OS << " (uninitialized)\n"; |
120 | 0 | return; |
121 | 0 | } |
122 | 0 |
|
123 | 0 | if (0 empty()0 ) { |
124 | 0 | OS << " (empty)\n"; |
125 | 0 | return; |
126 | 0 | } |
127 | 0 |
|
128 | 0 | for (const_iterator I = begin(), E = end(); 0 I != E0 ; ++I0 ) |
129 | 0 | OS << " " << PrintReg(*I, TRI); |
130 | 0 | OS << "\n"; |
131 | 0 | } |
132 | | |
133 | | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
134 | | LLVM_DUMP_METHOD void LivePhysRegs::dump() const { |
135 | | dbgs() << " " << *this; |
136 | | } |
137 | | #endif |
138 | | |
139 | | bool LivePhysRegs::available(const MachineRegisterInfo &MRI, |
140 | 3.44M | unsigned Reg) const { |
141 | 3.44M | if (LiveRegs.count(Reg)) |
142 | 2.64M | return false; |
143 | 807k | if (807k MRI.isReserved(Reg)807k ) |
144 | 280k | return false; |
145 | 4.34M | for (MCRegAliasIterator R(Reg, TRI, false); 526k R.isValid()4.34M ; ++R3.82M ) { |
146 | 3.83M | if (LiveRegs.count(*R)) |
147 | 13.4k | return false; |
148 | 3.83M | } |
149 | 512k | return true; |
150 | 3.44M | } |
151 | | |
152 | | /// Add live-in registers of basic block \p MBB to \p LiveRegs. |
153 | 787k | void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) { |
154 | 3.61M | for (const auto &LI : MBB.liveins()) { |
155 | 3.61M | unsigned Reg = LI.PhysReg; |
156 | 3.61M | LaneBitmask Mask = LI.LaneMask; |
157 | 3.61M | MCSubRegIndexIterator S(Reg, TRI); |
158 | 3.61M | assert(Mask.any() && "Invalid livein mask"); |
159 | 3.61M | if (Mask.all() || 3.61M !S.isValid()11.5k ) { |
160 | 3.61M | addReg(Reg); |
161 | 3.61M | continue; |
162 | 3.61M | } |
163 | 10.4k | for (; 1.44k S.isValid()10.4k ; ++S8.98k ) { |
164 | 8.98k | unsigned SI = S.getSubRegIndex(); |
165 | 8.98k | if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any()) |
166 | 6.02k | addReg(S.getSubReg()); |
167 | 8.98k | } |
168 | 3.61M | } |
169 | 787k | } |
170 | | |
171 | | /// Adds all callee saved registers to \p LiveRegs. |
172 | | static void addCalleeSavedRegs(LivePhysRegs &LiveRegs, |
173 | 603k | const MachineFunction &MF) { |
174 | 603k | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
175 | 10.6M | for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && 10.6M *CSR10.6M ; ++CSR10.0M ) |
176 | 10.0M | LiveRegs.addReg(*CSR); |
177 | 603k | } |
178 | | |
179 | 422k | void LivePhysRegs::addPristines(const MachineFunction &MF) { |
180 | 422k | const MachineFrameInfo &MFI = MF.getFrameInfo(); |
181 | 422k | if (!MFI.isCalleeSavedInfoValid()) |
182 | 3.94k | return; |
183 | 418k | /// This function will usually be called on an empty object, handle this |
184 | 418k | /// as a special case. |
185 | 418k | if (418k empty()418k ) { |
186 | 415k | /// Add all callee saved regs, then remove the ones that are saved and |
187 | 415k | /// restored. |
188 | 415k | addCalleeSavedRegs(*this, MF); |
189 | 415k | /// Remove the ones that are not saved/restored; they are pristine. |
190 | 415k | for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) |
191 | 3.55M | removeReg(Info.getReg()); |
192 | 415k | return; |
193 | 415k | } |
194 | 3.67k | /// If a callee-saved register that is not pristine is already present |
195 | 3.67k | /// in the set, we should make sure that it stays in it. Precompute the |
196 | 3.67k | /// set of pristine registers in a separate object. |
197 | 3.67k | /// Add all callee saved regs, then remove the ones that are saved+restored. |
198 | 3.67k | LivePhysRegs Pristine(*TRI); |
199 | 3.67k | addCalleeSavedRegs(Pristine, MF); |
200 | 3.67k | /// Remove the ones that are not saved/restored; they are pristine. |
201 | 3.67k | for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) |
202 | 9.65k | Pristine.removeReg(Info.getReg()); |
203 | 3.67k | for (MCPhysReg R : Pristine) |
204 | 125k | addReg(R); |
205 | 422k | } |
206 | | |
207 | 632k | void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) { |
208 | 632k | if (!MBB.succ_empty()632k ) { |
209 | 587k | // To get the live-outs we simply merge the live-ins of all successors. |
210 | 587k | for (const MachineBasicBlock *Succ : MBB.successors()) |
211 | 780k | addBlockLiveIns(*Succ); |
212 | 632k | } else if (44.5k MBB.isReturnBlock()44.5k ) { |
213 | 42.0k | // For the return block: Add all callee saved registers that are saved and |
214 | 42.0k | // restored (somewhere); This does not include callee saved registers that |
215 | 42.0k | // are unused and hence not saved and restored; they are called pristine. |
216 | 42.0k | const MachineFunction &MF = *MBB.getParent(); |
217 | 42.0k | const MachineFrameInfo &MFI = MF.getFrameInfo(); |
218 | 42.0k | if (MFI.isCalleeSavedInfoValid()42.0k ) { |
219 | 42.0k | for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) |
220 | 177k | if (177k Info.isRestored()177k ) |
221 | 177k | addReg(Info.getReg()); |
222 | 42.0k | } |
223 | 44.5k | } |
224 | 632k | } |
225 | | |
226 | 611k | void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) { |
227 | 611k | const MachineFunction &MF = *MBB.getParent(); |
228 | 611k | if (!MBB.succ_empty()611k ) { |
229 | 415k | addPristines(MF); |
230 | 415k | addLiveOutsNoPristines(MBB); |
231 | 611k | } else if (195k MBB.isReturnBlock()195k ) { |
232 | 185k | // For the return block: Add all callee saved registers. |
233 | 185k | const MachineFrameInfo &MFI = MF.getFrameInfo(); |
234 | 185k | if (MFI.isCalleeSavedInfoValid()) |
235 | 184k | addCalleeSavedRegs(*this, MF); |
236 | 195k | } |
237 | 611k | } |
238 | | |
239 | 7.36k | void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) { |
240 | 7.36k | const MachineFunction &MF = *MBB.getParent(); |
241 | 7.36k | addPristines(MF); |
242 | 7.36k | addBlockLiveIns(MBB); |
243 | 7.36k | } |
244 | | |
245 | | void llvm::computeLiveIns(LivePhysRegs &LiveRegs, |
246 | 213k | const MachineBasicBlock &MBB) { |
247 | 213k | const MachineFunction &MF = *MBB.getParent(); |
248 | 213k | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
249 | 213k | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); |
250 | 213k | LiveRegs.init(TRI); |
251 | 213k | LiveRegs.addLiveOutsNoPristines(MBB); |
252 | 213k | for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) |
253 | 602k | LiveRegs.stepBackward(MI); |
254 | 213k | } |
255 | | |
256 | 213k | void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) { |
257 | 213k | assert(MBB.livein_empty() && "Expected empty live-in list"); |
258 | 213k | const MachineFunction &MF = *MBB.getParent(); |
259 | 213k | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
260 | 213k | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); |
261 | 2.38M | for (MCPhysReg Reg : LiveRegs) { |
262 | 2.38M | if (MRI.isReserved(Reg)) |
263 | 279k | continue; |
264 | 2.10M | // Skip the register if we are about to add one of its super registers. |
265 | 2.10M | bool ContainsSuperReg = false; |
266 | 5.69M | for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid()5.69M ; ++SReg3.58M ) { |
267 | 4.62M | if (LiveRegs.contains(*SReg) && 4.62M !MRI.isReserved(*SReg)1.04M ) { |
268 | 1.04M | ContainsSuperReg = true; |
269 | 1.04M | break; |
270 | 1.04M | } |
271 | 4.62M | } |
272 | 2.10M | if (ContainsSuperReg) |
273 | 1.04M | continue; |
274 | 1.06M | MBB.addLiveIn(Reg); |
275 | 1.06M | } |
276 | 213k | } |
277 | | |
278 | 3.67k | void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) { |
279 | 3.67k | const MachineFunction &MF = *MBB.getParent(); |
280 | 3.67k | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
281 | 3.67k | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); |
282 | 3.67k | |
283 | 3.67k | // We walk through the block backwards and start with the live outs. |
284 | 3.67k | LivePhysRegs LiveRegs; |
285 | 3.67k | LiveRegs.init(TRI); |
286 | 3.67k | LiveRegs.addLiveOutsNoPristines(MBB); |
287 | 3.67k | |
288 | 22.4k | for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) { |
289 | 22.4k | // Recompute dead flags. |
290 | 126k | for (MIBundleOperands MO(MI); MO.isValid()126k ; ++MO104k ) { |
291 | 104k | if (!MO->isReg() || 104k !MO->isDef()69.1k || MO->isDebug()20.8k ) |
292 | 83.5k | continue; |
293 | 20.8k | |
294 | 20.8k | unsigned Reg = MO->getReg(); |
295 | 20.8k | if (Reg == 0) |
296 | 0 | continue; |
297 | 20.8k | assert(TargetRegisterInfo::isPhysicalRegister(Reg)); |
298 | 20.8k | |
299 | 20.8k | bool IsNotLive = LiveRegs.available(MRI, Reg); |
300 | 20.8k | MO->setIsDead(IsNotLive); |
301 | 20.8k | } |
302 | 22.4k | |
303 | 22.4k | // Step backward over defs. |
304 | 22.4k | LiveRegs.removeDefs(MI); |
305 | 22.4k | |
306 | 22.4k | // Recompute kill flags. |
307 | 126k | for (MIBundleOperands MO(MI); MO.isValid()126k ; ++MO104k ) { |
308 | 104k | if (!MO->isReg() || 104k !MO->readsReg()69.1k || MO->isDebug()48.1k ) |
309 | 56.2k | continue; |
310 | 48.1k | |
311 | 48.1k | unsigned Reg = MO->getReg(); |
312 | 48.1k | if (Reg == 0) |
313 | 14.4k | continue; |
314 | 48.1k | assert(TargetRegisterInfo::isPhysicalRegister(Reg)); |
315 | 33.7k | |
316 | 33.7k | bool IsNotLive = LiveRegs.available(MRI, Reg); |
317 | 33.7k | MO->setIsKill(IsNotLive); |
318 | 33.7k | } |
319 | 22.4k | |
320 | 22.4k | // Complete the stepbackward. |
321 | 22.4k | LiveRegs.addUses(MI); |
322 | 22.4k | } |
323 | 3.67k | } |
324 | | |
325 | | void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs, |
326 | 82.0k | MachineBasicBlock &MBB) { |
327 | 82.0k | computeLiveIns(LiveRegs, MBB); |
328 | 82.0k | addLiveIns(MBB, LiveRegs); |
329 | 82.0k | } |