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/// Adds a register, taking associated lane masks into consideration.
155void LivePhysRegs::addRegMaskPair(
156 const MachineBasicBlock::RegisterMaskPair &Pair) {
157 MCRegister Reg = Pair.PhysReg;
158 LaneBitmask Mask = Pair.LaneMask;
159 MCSubRegIndexIterator S(Reg, TRI);
160 assert(Mask.any() && "Invalid livein mask");
161 if (Mask.all() || !S.isValid()) {
162 addReg(Reg);
163 return;
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/// Add live-in registers of basic block \p MBB to \p LiveRegs.
173void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
174 for (const auto &LI : MBB.liveins())
175 addRegMaskPair(Pair: LI);
176}
177
178/// Add live-out registers of basic block \p MBB to \p LiveRegs.
179void LivePhysRegs::addBlockLiveOuts(const MachineBasicBlock &MBB) {
180 for (const auto &LO : MBB.liveouts())
181 addRegMaskPair(Pair: LO);
182}
183
184/// Adds all callee saved registers to \p LiveRegs.
185static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
186 const MachineFunction &MF) {
187 const MachineRegisterInfo &MRI = MF.getRegInfo();
188 for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
189 LiveRegs.addReg(Reg: *CSR);
190}
191
192void LivePhysRegs::addPristines(const MachineFunction &MF) {
193 const MachineFrameInfo &MFI = MF.getFrameInfo();
194 if (!MFI.isCalleeSavedInfoValid())
195 return;
196 /// This function will usually be called on an empty object, handle this
197 /// as a special case.
198 if (empty()) {
199 /// Add all callee saved regs, then remove the ones that are saved and
200 /// restored.
201 addCalleeSavedRegs(LiveRegs&: *this, MF);
202 /// Remove the ones that are not saved/restored; they are pristine.
203 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
204 removeReg(Reg: Info.getReg());
205 return;
206 }
207 /// If a callee-saved register that is not pristine is already present
208 /// in the set, we should make sure that it stays in it. Precompute the
209 /// set of pristine registers in a separate object.
210 /// Add all callee saved regs, then remove the ones that are saved+restored.
211 LivePhysRegs Pristine(*TRI);
212 addCalleeSavedRegs(LiveRegs&: Pristine, MF);
213 /// Remove the ones that are not saved/restored; they are pristine.
214 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
215 Pristine.removeReg(Reg: Info.getReg());
216 for (MCPhysReg R : Pristine)
217 addReg(Reg: R);
218}
219
220void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
221 addBlockLiveOuts(MBB);
222 if (MBB.isReturnBlock()) {
223 // Return blocks are a special case because we currently don't mark up
224 // return instructions completely: specifically, there is no explicit
225 // use for callee-saved registers. So we add all callee saved registers
226 // that are saved and restored (somewhere). This does not include
227 // callee saved registers that are unused and hence not saved and
228 // restored; they are called pristine.
229 // FIXME: PEI should add explicit markings to return instructions
230 // instead of implicitly handling them here.
231 const MachineFunction &MF = *MBB.getParent();
232 const MachineFrameInfo &MFI = MF.getFrameInfo();
233 if (MFI.isCalleeSavedInfoValid()) {
234 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
235 if (Info.isRestored())
236 addReg(Reg: Info.getReg());
237 }
238 }
239}
240
241void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
242 const MachineFunction &MF = *MBB.getParent();
243 addPristines(MF);
244 addLiveOutsNoPristines(MBB);
245}
246
247void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
248 const MachineFunction &MF = *MBB.getParent();
249 addPristines(MF);
250 addBlockLiveIns(MBB);
251}
252
253void LivePhysRegs::addLiveInsNoPristines(const MachineBasicBlock &MBB) {
254 addBlockLiveIns(MBB);
255}
256
257void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
258 const MachineBasicBlock &MBB) {
259 const MachineFunction &MF = *MBB.getParent();
260 const MachineRegisterInfo &MRI = MF.getRegInfo();
261 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
262 LiveRegs.init(TRI);
263 LiveRegs.addLiveOutsNoPristines(MBB);
264 for (const MachineInstr &MI : llvm::reverse(C: MBB))
265 LiveRegs.stepBackward(MI);
266}
267
268void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
269 assert(MBB.livein_empty() && "Expected empty live-in list");
270 const MachineFunction &MF = *MBB.getParent();
271 const MachineRegisterInfo &MRI = MF.getRegInfo();
272 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
273 for (MCPhysReg Reg : LiveRegs) {
274 if (MRI.isReserved(PhysReg: Reg))
275 continue;
276 // Skip the register if we are about to add one of its super registers.
277 if (any_of(Range: TRI.superregs(Reg), P: [&](MCPhysReg SReg) {
278 return LiveRegs.contains(Reg: SReg) && !MRI.isReserved(PhysReg: SReg);
279 }))
280 continue;
281 MBB.addLiveIn(PhysReg: Reg);
282 }
283}
284
285void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
286 const MachineFunction &MF = *MBB.getParent();
287 const MachineRegisterInfo &MRI = MF.getRegInfo();
288 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
289 const MachineFrameInfo &MFI = MF.getFrameInfo();
290
291 // We walk through the block backwards and start with the live outs.
292 LivePhysRegs LiveRegs;
293 LiveRegs.init(TRI);
294 LiveRegs.addLiveOutsNoPristines(MBB);
295
296 for (MachineInstr &MI : llvm::reverse(C&: MBB)) {
297 // Recompute dead flags.
298 for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
299 if (!MO->isReg() || !MO->isDef() || MO->isDebug())
300 continue;
301
302 Register Reg = MO->getReg();
303 if (Reg == 0)
304 continue;
305 assert(Reg.isPhysical());
306
307 bool IsNotLive = LiveRegs.available(MRI, Reg);
308
309 // Special-case return instructions for cases when a return is not
310 // the last instruction in the block.
311 if (MI.isReturn() && MFI.isCalleeSavedInfoValid()) {
312 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
313 if (Info.getReg() == Reg.asMCReg()) {
314 IsNotLive = !Info.isRestored();
315 break;
316 }
317 }
318 }
319
320 MO->setIsDead(IsNotLive);
321 }
322
323 // Step backward over defs.
324 LiveRegs.removeDefs(MI);
325
326 // Recompute kill flags.
327 for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
328 if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
329 continue;
330
331 Register Reg = MO->getReg();
332 if (Reg == 0)
333 continue;
334 assert(Reg.isPhysical());
335
336 bool IsNotLive = LiveRegs.available(MRI, Reg);
337 MO->setIsKill(IsNotLive);
338 }
339
340 // Complete the stepbackward.
341 LiveRegs.addUses(MI);
342 }
343}
344
345void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
346 MachineBasicBlock &MBB) {
347 computeLiveIns(LiveRegs, MBB);
348 addLiveIns(MBB, LiveRegs);
349}
350
351// Returns true if `Reg` is used after this iterator in the rest of the
352// basic block or any successors of the basic block.
353bool llvm::isPhysRegUsedAfter(Register Reg, MachineBasicBlock::iterator MBI) {
354 assert(Reg.isPhysical() && "Apply to physical register only");
355
356 MachineBasicBlock *MBB = MBI->getParent();
357 // Scan forward through BB for a use/def of Reg
358 for (const MachineInstr &MI : llvm::make_range(x: std::next(x: MBI), y: MBB->end())) {
359 if (MI.readsRegister(Reg, /*TRI=*/nullptr))
360 return true;
361 // If we found a def, we can stop searching.
362 if (MI.definesRegister(Reg, /*TRI=*/nullptr))
363 return false;
364 }
365
366 // If we hit the end of the block, check whether Reg is live into a
367 // successor.
368 for (const auto &LO : MBB->liveouts())
369 if (LO.PhysReg == Reg.asMCReg() && LO.LaneMask.any())
370 return true;
371
372 return false;
373}
374