Line data Source code
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/Config/llvm-config.h"
22 : #include "llvm/Support/Debug.h"
23 : #include "llvm/Support/raw_ostream.h"
24 : using namespace llvm;
25 :
26 :
27 : /// Remove all registers from the set that get clobbered by the register
28 : /// mask.
29 : /// The clobbers set will be the list of live registers clobbered
30 : /// by the regmask.
31 219333 : void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
32 : SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers) {
33 : SparseSet<unsigned>::iterator LRI = LiveRegs.begin();
34 4873329 : while (LRI != LiveRegs.end()) {
35 9307992 : if (MO.clobbersPhysReg(*LRI)) {
36 1664588 : if (Clobbers)
37 254 : Clobbers->push_back(std::make_pair(*LRI, &MO));
38 1664588 : LRI = LiveRegs.erase(LRI);
39 : } else
40 2989408 : ++LRI;
41 : }
42 219333 : }
43 :
44 : /// Remove defined registers and regmask kills from the set.
45 3574634 : void LivePhysRegs::removeDefs(const MachineInstr &MI) {
46 20127149 : for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
47 16552515 : if (O->isReg()) {
48 10780034 : if (!O->isDef() || O->isDebug())
49 : continue;
50 3099776 : unsigned Reg = O->getReg();
51 3099776 : if (!TargetRegisterInfo::isPhysicalRegister(Reg))
52 : continue;
53 3099769 : removeReg(Reg);
54 5772481 : } else if (O->isRegMask())
55 175285 : removeRegsInMask(*O);
56 : }
57 3574634 : }
58 :
59 : /// Add uses to the set.
60 3574634 : void LivePhysRegs::addUses(const MachineInstr &MI) {
61 20127149 : for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
62 24083424 : if (!O->isReg() || !O->readsReg() || O->isDebug())
63 : continue;
64 7294452 : unsigned Reg = O->getReg();
65 7294452 : if (!TargetRegisterInfo::isPhysicalRegister(Reg))
66 : continue;
67 4050703 : addReg(Reg);
68 : }
69 3574634 : }
70 :
71 : /// Simulates liveness when stepping backwards over an instruction(bundle):
72 : /// Remove Defs, add uses. This is the recommended way of calculating liveness.
73 3567463 : void LivePhysRegs::stepBackward(const MachineInstr &MI) {
74 : // Remove defined registers and regmask kills from the set.
75 3567463 : removeDefs(MI);
76 :
77 : // Add uses to the set.
78 3567463 : addUses(MI);
79 3567463 : }
80 :
81 : /// Simulates liveness when stepping forward over an instruction(bundle): Remove
82 : /// killed-uses, add defs. This is the not recommended way, because it depends
83 : /// on accurate kill flags. If possible use stepBackward() instead of this
84 : /// function.
85 4119 : void LivePhysRegs::stepForward(const MachineInstr &MI,
86 : SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
87 : // Remove killed registers from the set.
88 24835 : for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
89 20716 : if (O->isReg() && !O->isDebug()) {
90 11955 : unsigned Reg = O->getReg();
91 11955 : if (!TargetRegisterInfo::isPhysicalRegister(Reg))
92 : continue;
93 11644 : if (O->isDef()) {
94 : // Note, dead defs are still recorded. The caller should decide how to
95 : // handle them.
96 3206 : Clobbers.push_back(std::make_pair(Reg, &*O));
97 : } else {
98 8438 : if (!O->isKill())
99 : continue;
100 : assert(O->isUse());
101 2294 : removeReg(Reg);
102 : }
103 8761 : } else if (O->isRegMask())
104 170 : removeRegsInMask(*O, &Clobbers);
105 : }
106 :
107 : // Add defs to the set.
108 23817 : for (auto Reg : Clobbers) {
109 : // Skip dead defs and registers clobbered by regmasks. They shouldn't
110 : // be added to the set.
111 19698 : if (Reg.second->isReg() && Reg.second->isDead())
112 : continue;
113 18181 : if (Reg.second->isRegMask() &&
114 1711 : MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
115 : continue;
116 16470 : addReg(Reg.first);
117 : }
118 4119 : }
119 :
120 : /// Prin the currently live registers to OS.
121 0 : void LivePhysRegs::print(raw_ostream &OS) const {
122 0 : OS << "Live Registers:";
123 0 : if (!TRI) {
124 0 : OS << " (uninitialized)\n";
125 0 : return;
126 : }
127 :
128 0 : if (empty()) {
129 0 : OS << " (empty)\n";
130 0 : return;
131 : }
132 :
133 0 : for (const_iterator I = begin(), E = end(); I != E; ++I)
134 0 : OS << " " << printReg(*I, TRI);
135 0 : OS << "\n";
136 : }
137 :
138 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
139 : LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
140 : dbgs() << " " << *this;
141 : }
142 : #endif
143 :
144 2196732 : bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
145 : unsigned Reg) const {
146 2196732 : if (LiveRegs.count(Reg))
147 : return false;
148 1085972 : if (MRI.isReserved(Reg))
149 : return false;
150 6854319 : for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
151 6052110 : if (LiveRegs.count(*R))
152 15229 : return false;
153 : }
154 802209 : return true;
155 : }
156 :
157 : /// Add live-in registers of basic block \p MBB to \p LiveRegs.
158 626307 : void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
159 2168800 : for (const auto &LI : MBB.liveins()) {
160 1542493 : unsigned Reg = LI.PhysReg;
161 1542493 : LaneBitmask Mask = LI.LaneMask;
162 1542493 : MCSubRegIndexIterator S(Reg, TRI);
163 : assert(Mask.any() && "Invalid livein mask");
164 1542493 : if (Mask.all() || !S.isValid()) {
165 1539997 : addReg(Reg);
166 : continue;
167 : }
168 16512 : for (; S.isValid(); ++S) {
169 : unsigned SI = S.getSubRegIndex();
170 28032 : if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
171 9747 : addReg(S.getSubReg());
172 : }
173 : }
174 626307 : }
175 :
176 : /// Adds all callee saved registers to \p LiveRegs.
177 562580 : static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
178 : const MachineFunction &MF) {
179 562580 : const MachineRegisterInfo &MRI = MF.getRegInfo();
180 5111412 : for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
181 4548832 : LiveRegs.addReg(*CSR);
182 562580 : }
183 :
184 642642 : void LivePhysRegs::addPristines(const MachineFunction &MF) {
185 642642 : const MachineFrameInfo &MFI = MF.getFrameInfo();
186 642642 : if (!MFI.isCalleeSavedInfoValid())
187 640924 : return;
188 : /// This function will usually be called on an empty object, handle this
189 : /// as a special case.
190 562580 : if (empty()) {
191 : /// Add all callee saved regs, then remove the ones that are saved and
192 : /// restored.
193 560862 : addCalleeSavedRegs(*this, MF);
194 : /// Remove the ones that are not saved/restored; they are pristine.
195 2076192 : for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
196 1515330 : removeReg(Info.getReg());
197 : return;
198 : }
199 : /// If a callee-saved register that is not pristine is already present
200 : /// in the set, we should make sure that it stays in it. Precompute the
201 : /// set of pristine registers in a separate object.
202 : /// Add all callee saved regs, then remove the ones that are saved+restored.
203 1718 : LivePhysRegs Pristine(*TRI);
204 1718 : addCalleeSavedRegs(Pristine, MF);
205 : /// Remove the ones that are not saved/restored; they are pristine.
206 2544 : for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
207 826 : Pristine.removeReg(Info.getReg());
208 76717 : for (MCPhysReg R : Pristine)
209 74999 : addReg(R);
210 : }
211 :
212 660583 : void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
213 : // To get the live-outs we simply merge the live-ins of all successors.
214 1283414 : for (const MachineBasicBlock *Succ : MBB.successors())
215 622831 : addBlockLiveIns(*Succ);
216 660583 : if (MBB.isReturnBlock()) {
217 : // Return blocks are a special case because we currently don't mark up
218 : // return instructions completely: specifically, there is no explicit
219 : // use for callee-saved registers. So we add all callee saved registers
220 : // that are saved and restored (somewhere). This does not include
221 : // callee saved registers that are unused and hence not saved and
222 : // restored; they are called pristine.
223 : // FIXME: PEI should add explicit markings to return instructions
224 : // instead of implicitly handling them here.
225 190523 : const MachineFunction &MF = *MBB.getParent();
226 190523 : const MachineFrameInfo &MFI = MF.getFrameInfo();
227 190523 : if (MFI.isCalleeSavedInfoValid()) {
228 246443 : for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
229 57775 : if (Info.isRestored())
230 55366 : addReg(Info.getReg());
231 : }
232 : }
233 660583 : }
234 :
235 639166 : void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
236 639166 : const MachineFunction &MF = *MBB.getParent();
237 639166 : addPristines(MF);
238 639166 : addLiveOutsNoPristines(MBB);
239 639166 : }
240 :
241 3476 : void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
242 3476 : const MachineFunction &MF = *MBB.getParent();
243 3476 : addPristines(MF);
244 3476 : addBlockLiveIns(MBB);
245 3476 : }
246 :
247 19517 : void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
248 : const MachineBasicBlock &MBB) {
249 19517 : const MachineFunction &MF = *MBB.getParent();
250 19517 : const MachineRegisterInfo &MRI = MF.getRegInfo();
251 19517 : const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
252 : LiveRegs.init(TRI);
253 19517 : LiveRegs.addLiveOutsNoPristines(MBB);
254 82986 : for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
255 63469 : LiveRegs.stepBackward(MI);
256 19517 : }
257 :
258 19517 : void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
259 : assert(MBB.livein_empty() && "Expected empty live-in list");
260 19517 : const MachineFunction &MF = *MBB.getParent();
261 19517 : const MachineRegisterInfo &MRI = MF.getRegInfo();
262 19517 : const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
263 323234 : for (MCPhysReg Reg : LiveRegs) {
264 303717 : if (MRI.isReserved(Reg))
265 : continue;
266 : // Skip the register if we are about to add one of its super registers.
267 : bool ContainsSuperReg = false;
268 246944 : for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
269 199714 : if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
270 : ContainsSuperReg = true;
271 : break;
272 : }
273 : }
274 216192 : if (ContainsSuperReg)
275 : continue;
276 : MBB.addLiveIn(Reg);
277 : }
278 19517 : }
279 :
280 1726 : void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
281 1726 : const MachineFunction &MF = *MBB.getParent();
282 1726 : const MachineRegisterInfo &MRI = MF.getRegInfo();
283 1726 : const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
284 :
285 : // We walk through the block backwards and start with the live outs.
286 : LivePhysRegs LiveRegs;
287 : LiveRegs.init(TRI);
288 1726 : LiveRegs.addLiveOutsNoPristines(MBB);
289 :
290 8897 : for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
291 : // Recompute dead flags.
292 37821 : for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
293 30650 : if (!MO->isReg() || !MO->isDef() || MO->isDebug())
294 : continue;
295 :
296 6473 : unsigned Reg = MO->getReg();
297 6473 : if (Reg == 0)
298 : continue;
299 : assert(TargetRegisterInfo::isPhysicalRegister(Reg));
300 :
301 6473 : bool IsNotLive = LiveRegs.available(MRI, Reg);
302 : MO->setIsDead(IsNotLive);
303 : }
304 :
305 : // Step backward over defs.
306 7171 : LiveRegs.removeDefs(MI);
307 :
308 : // Recompute kill flags.
309 37821 : for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
310 44597 : if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
311 : continue;
312 :
313 13938 : unsigned Reg = MO->getReg();
314 13938 : if (Reg == 0)
315 : continue;
316 : assert(TargetRegisterInfo::isPhysicalRegister(Reg));
317 :
318 10782 : bool IsNotLive = LiveRegs.available(MRI, Reg);
319 : MO->setIsKill(IsNotLive);
320 : }
321 :
322 : // Complete the stepbackward.
323 7171 : LiveRegs.addUses(MI);
324 : }
325 1726 : }
326 :
327 9195 : void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
328 : MachineBasicBlock &MBB) {
329 9195 : computeLiveIns(LiveRegs, MBB);
330 9195 : addLiveIns(MBB, LiveRegs);
331 9195 : }
|
