1//===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
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// This file implements the LivePhysRegs utility for tracking liveness of
10// physical registers across machine instructions in forward or backward order.
11// A more detailed description can be found in the corresponding header file.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/CodeGen/LivePhysRegs.h"
16#include "llvm/CodeGen/LiveRegUnits.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"
24using 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.
31void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
32 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers) {
33 RegisterSet::iterator LRI = LiveRegs.begin();
34 while (LRI != LiveRegs.end()) {
35 if (MO.clobbersPhysReg(PhysReg: *LRI)) {
36 if (Clobbers)
37 Clobbers->push_back(Elt: std::make_pair(x&: *LRI, y: &MO));
38 LRI = LiveRegs.erase(I: LRI);
39 } else
40 ++LRI;
41 }
42}
43
44/// Remove defined registers and regmask kills from the set.
45void LivePhysRegs::removeDefs(const MachineInstr &MI) {
46 for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
47 if (MOP.isRegMask()) {
48 removeRegsInMask(MO: MOP);
49 continue;
50 }
51
52 if (MOP.isDef())
53 removeReg(Reg: MOP.getReg());
54 }
55}
56
57/// Add uses to the set.
58void LivePhysRegs::addUses(const MachineInstr &MI) {
59 for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
60 if (!MOP.isReg() || !MOP.readsReg())
61 continue;
62 addReg(Reg: MOP.getReg());
63 }
64}
65
66/// Simulates liveness when stepping backwards over an instruction(bundle):
67/// Remove Defs, add uses. This is the recommended way of calculating liveness.
68void LivePhysRegs::stepBackward(const MachineInstr &MI) {
69 // Remove defined registers and regmask kills from the set.
70 removeDefs(MI);
71
72 // Add uses to the set.
73 addUses(MI);
74}
75
76/// Simulates liveness when stepping forward over an instruction(bundle): Remove
77/// killed-uses, add defs. This is the not recommended way, because it depends
78/// on accurate kill flags. If possible use stepBackward() instead of this
79/// function.
80void LivePhysRegs::stepForward(const MachineInstr &MI,
81 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers) {
82 // Remove killed registers from the set.
83 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
84 if (O->isReg()) {
85 if (O->isDebug())
86 continue;
87 Register Reg = O->getReg();
88 if (!Reg.isPhysical())
89 continue;
90 if (O->isDef()) {
91 // Note, dead defs are still recorded. The caller should decide how to
92 // handle them.
93 Clobbers.push_back(Elt: std::make_pair(x: Reg.id(), y: &*O));
94 } else {
95 assert(O->isUse());
96 if (O->isKill())
97 removeReg(Reg);
98 }
99 } else if (O->isRegMask()) {
100 removeRegsInMask(MO: *O, Clobbers: &Clobbers);
101 }
102 }
103
104 // Add defs to the set.
105 for (auto Reg : Clobbers) {
106 // Skip dead defs and registers clobbered by regmasks. They shouldn't
107 // be added to the set.
108 if (Reg.second->isReg() && Reg.second->isDead())
109 continue;
110 if (Reg.second->isRegMask() &&
111 MachineOperand::clobbersPhysReg(RegMask: Reg.second->getRegMask(), PhysReg: Reg.first))
112 continue;
113 addReg(Reg: Reg.first);
114 }
115}
116
117/// Print the currently live registers to OS.
118void LivePhysRegs::print(raw_ostream &OS) const {
119 OS << "Live Registers:";
120 if (!TRI) {
121 OS << " (uninitialized)\n";
122 return;
123 }
124
125 if (empty()) {
126 OS << " (empty)\n";
127 return;
128 }
129
130 for (MCPhysReg R : *this)
131 OS << " " << printReg(Reg: R, TRI);
132 OS << "\n";
133}
134
135#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
136LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
137 dbgs() << " " << *this;
138}
139#endif
140
141bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
142 MCRegister Reg) const {
143 if (LiveRegs.count(Key: Reg.id()))
144 return false;
145 if (MRI.isReserved(PhysReg: Reg))
146 return false;
147 for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
148 if (LiveRegs.count(Key: *R))
149 return false;
150 }
151 return true;
152}
153
154/// Add live-in registers of basic block \p MBB to \p LiveRegs.
155void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
156 for (const auto &LI : MBB.liveins()) {
157 MCRegister Reg = LI.PhysReg;
158 LaneBitmask Mask = LI.LaneMask;
159 MCSubRegIndexIterator S(Reg, TRI);
160 assert(Mask.any() && "Invalid livein mask");
161 if (Mask.all() || !S.isValid()) {
162 addReg(Reg);
163 continue;
164 }
165 for (; S.isValid(); ++S) {
166 unsigned SI = S.getSubRegIndex();
167 if ((Mask & TRI->getSubRegIndexLaneMask(SubIdx: SI)).any())
168 addReg(Reg: S.getSubReg());
169 }
170 }
171}
172
173/// Adds all callee saved registers to \p LiveRegs.
174static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
175 const MachineFunction &MF) {
176 const MachineRegisterInfo &MRI = MF.getRegInfo();
177 for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
178 LiveRegs.addReg(Reg: *CSR);
179}
180
181void LivePhysRegs::addPristines(const MachineFunction &MF) {
182 const MachineFrameInfo &MFI = MF.getFrameInfo();
183 if (!MFI.isCalleeSavedInfoValid())
184 return;
185 /// This function will usually be called on an empty object, handle this
186 /// as a special case.
187 if (empty()) {
188 /// Add all callee saved regs, then remove the ones that are saved and
189 /// restored.
190 addCalleeSavedRegs(LiveRegs&: *this, MF);
191 /// Remove the ones that are not saved/restored; they are pristine.
192 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
193 removeReg(Reg: Info.getReg());
194 return;
195 }
196 /// If a callee-saved register that is not pristine is already present
197 /// in the set, we should make sure that it stays in it. Precompute the
198 /// set of pristine registers in a separate object.
199 /// Add all callee saved regs, then remove the ones that are saved+restored.
200 LivePhysRegs Pristine(*TRI);
201 addCalleeSavedRegs(LiveRegs&: Pristine, MF);
202 /// Remove the ones that are not saved/restored; they are pristine.
203 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
204 Pristine.removeReg(Reg: Info.getReg());
205 for (MCPhysReg R : Pristine)
206 addReg(Reg: R);
207}
208
209void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
210 // To get the live-outs we simply merge the live-ins of all successors.
211 for (const MachineBasicBlock *Succ : MBB.successors())
212 addBlockLiveIns(MBB: *Succ);
213 if (MBB.isReturnBlock()) {
214 // Return blocks are a special case because we currently don't mark up
215 // return instructions completely: specifically, there is no explicit
216 // use for callee-saved registers. So we add all callee saved registers
217 // that are saved and restored (somewhere). This does not include
218 // callee saved registers that are unused and hence not saved and
219 // restored; they are called pristine.
220 // FIXME: PEI should add explicit markings to return instructions
221 // instead of implicitly handling them here.
222 const MachineFunction &MF = *MBB.getParent();
223 const MachineFrameInfo &MFI = MF.getFrameInfo();
224 if (MFI.isCalleeSavedInfoValid()) {
225 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
226 if (Info.isRestored())
227 addReg(Reg: Info.getReg());
228 }
229 }
230}
231
232void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
233 const MachineFunction &MF = *MBB.getParent();
234 addPristines(MF);
235 addLiveOutsNoPristines(MBB);
236}
237
238void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
239 const MachineFunction &MF = *MBB.getParent();
240 addPristines(MF);
241 addBlockLiveIns(MBB);
242}
243
244void LivePhysRegs::addLiveInsNoPristines(const MachineBasicBlock &MBB) {
245 addBlockLiveIns(MBB);
246}
247
248void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
249 const MachineBasicBlock &MBB) {
250 const MachineFunction &MF = *MBB.getParent();
251 const MachineRegisterInfo &MRI = MF.getRegInfo();
252 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
253 LiveRegs.init(TRI);
254 LiveRegs.addLiveOutsNoPristines(MBB);
255 for (const MachineInstr &MI : llvm::reverse(C: MBB))
256 LiveRegs.stepBackward(MI);
257}
258
259void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
260 assert(MBB.livein_empty() && "Expected empty live-in list");
261 const MachineFunction &MF = *MBB.getParent();
262 const MachineRegisterInfo &MRI = MF.getRegInfo();
263 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
264 for (MCPhysReg Reg : LiveRegs) {
265 if (MRI.isReserved(PhysReg: Reg))
266 continue;
267 // Skip the register if we are about to add one of its super registers.
268 if (any_of(Range: TRI.superregs(Reg), P: [&](MCPhysReg SReg) {
269 return LiveRegs.contains(Reg: SReg) && !MRI.isReserved(PhysReg: SReg);
270 }))
271 continue;
272 MBB.addLiveIn(PhysReg: Reg);
273 }
274}
275
276void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
277 const MachineFunction &MF = *MBB.getParent();
278 const MachineRegisterInfo &MRI = MF.getRegInfo();
279 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
280 const MachineFrameInfo &MFI = MF.getFrameInfo();
281
282 // We walk through the block backwards and start with the live outs.
283 LivePhysRegs LiveRegs;
284 LiveRegs.init(TRI);
285 LiveRegs.addLiveOutsNoPristines(MBB);
286
287 for (MachineInstr &MI : llvm::reverse(C&: MBB)) {
288 // Recompute dead flags.
289 for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
290 if (!MO->isReg() || !MO->isDef() || MO->isDebug())
291 continue;
292
293 Register Reg = MO->getReg();
294 if (Reg == 0)
295 continue;
296 assert(Reg.isPhysical());
297
298 bool IsNotLive = LiveRegs.available(MRI, Reg);
299
300 // Special-case return instructions for cases when a return is not
301 // the last instruction in the block.
302 if (MI.isReturn() && MFI.isCalleeSavedInfoValid()) {
303 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
304 if (Info.getReg() == Reg.asMCReg()) {
305 IsNotLive = !Info.isRestored();
306 break;
307 }
308 }
309 }
310
311 MO->setIsDead(IsNotLive);
312 }
313
314 // Step backward over defs.
315 LiveRegs.removeDefs(MI);
316
317 // Recompute kill flags.
318 for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
319 if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
320 continue;
321
322 Register Reg = MO->getReg();
323 if (Reg == 0)
324 continue;
325 assert(Reg.isPhysical());
326
327 bool IsNotLive = LiveRegs.available(MRI, Reg);
328 MO->setIsKill(IsNotLive);
329 }
330
331 // Complete the stepbackward.
332 LiveRegs.addUses(MI);
333 }
334}
335
336void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
337 MachineBasicBlock &MBB) {
338 computeLiveIns(LiveRegs, MBB);
339 addLiveIns(MBB, LiveRegs);
340}
341
342// Returns true if `Reg` is used after this iterator in the rest of the
343// basic block or any successors of the basic block.
344bool llvm::isPhysRegUsedAfter(Register Reg, MachineBasicBlock::iterator MBI) {
345 assert(Reg.isPhysical() && "Apply to physical register only");
346
347 MachineBasicBlock *MBB = MBI->getParent();
348 // Scan forward through BB for a use/def of Reg
349 for (const MachineInstr &MI : llvm::make_range(x: std::next(x: MBI), y: MBB->end())) {
350 if (MI.readsRegister(Reg, /*TRI=*/nullptr))
351 return true;
352 // If we found a def, we can stop searching.
353 if (MI.definesRegister(Reg, /*TRI=*/nullptr))
354 return false;
355 }
356
357 // If we hit the end of the block, check whether Reg is live into a
358 // successor.
359 for (MachineBasicBlock *Succ : MBB->successors())
360 if (Succ->isLiveIn(Reg))
361 return true;
362
363 return false;
364}
365