LLVM 19.0.0git
LivePhysRegs.cpp
Go to the documentation of this file.
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
21#include "llvm/Config/llvm-config.h"
22#include "llvm/Support/Debug.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.
32 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers) {
33 RegisterSet::iterator LRI = LiveRegs.begin();
34 while (LRI != LiveRegs.end()) {
35 if (MO.clobbersPhysReg(*LRI)) {
36 if (Clobbers)
37 Clobbers->push_back(std::make_pair(*LRI, &MO));
38 LRI = LiveRegs.erase(LRI);
39 } else
40 ++LRI;
41 }
42}
43
44/// Remove defined registers and regmask kills from the set.
46 for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
47 if (MOP.isRegMask()) {
49 continue;
50 }
51
52 if (MOP.isDef())
53 removeReg(MOP.getReg());
54 }
55}
56
57/// Add uses to the set.
59 for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
60 if (!MOP.isReg() || !MOP.readsReg())
61 continue;
62 addReg(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.
69 // Remove defined registers and regmask kills from the set.
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.
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(std::make_pair(Reg, &*O));
94 } else {
95 assert(O->isUse());
96 if (O->isKill())
97 removeReg(Reg);
98 }
99 } else if (O->isRegMask()) {
100 removeRegsInMask(*O, &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(Reg.second->getRegMask(), Reg.first))
112 continue;
113 addReg(Reg.first);
114 }
115}
116
117/// Print the currently live registers to OS.
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(R, TRI);
132 OS << "\n";
133}
134
135#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
137 dbgs() << " " << *this;
138}
139#endif
140
142 MCPhysReg Reg) const {
143 if (LiveRegs.count(Reg))
144 return false;
145 if (MRI.isReserved(Reg))
146 return false;
147 for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
148 if (LiveRegs.count(*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 MCPhysReg 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(SI)).any())
168 addReg(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(*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(*this, MF);
191 /// Remove the ones that are not saved/restored; they are pristine.
192 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
193 removeReg(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(Pristine, MF);
202 /// Remove the ones that are not saved/restored; they are pristine.
203 for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
204 Pristine.removeReg(Info.getReg());
205 for (MCPhysReg R : Pristine)
206 addReg(R);
207}
208
210 // To get the live-outs we simply merge the live-ins of all successors.
211 for (const MachineBasicBlock *Succ : MBB.successors())
212 addBlockLiveIns(*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(Info.getReg());
228 }
229 }
230}
231
233 const MachineFunction &MF = *MBB.getParent();
234 addPristines(MF);
236}
237
239 const MachineFunction &MF = *MBB.getParent();
240 addPristines(MF);
241 addBlockLiveIns(MBB);
242}
243
245 addBlockLiveIns(MBB);
246}
247
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(MBB))
256 LiveRegs.stepBackward(MI);
257}
258
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(Reg))
266 continue;
267 // Skip the register if we are about to add one of its super registers.
268 if (any_of(TRI.superregs(Reg), [&](MCPhysReg SReg) {
269 return LiveRegs.contains(SReg) && !MRI.isReserved(SReg);
270 }))
271 continue;
272 MBB.addLiveIn(Reg);
273 }
274}
275
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(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) {
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
338 computeLiveIns(LiveRegs, MBB);
339 addLiveIns(MBB, LiveRegs);
340}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
IRTranslator LLVM IR MI
static void addCalleeSavedRegs(LivePhysRegs &LiveRegs, const MachineFunction &MF)
Adds all callee saved registers to LiveRegs.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
A set of register units.
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
The CalleeSavedInfo class tracks the information need to locate where a callee saved register is in t...
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * > > &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
void print(raw_ostream &OS) const
Prints the currently live registers to OS.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void removeReg(MCPhysReg Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set.
Definition: LivePhysRegs.h:90
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:68
void addLiveIns(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB.
void addUses(const MachineInstr &MI)
Add uses to the set.
void removeDefs(const MachineInstr &MI)
Remove defined registers and regmask kills from the set.
void addLiveOutsNoPristines(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB but skips pristine registers.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
void addLiveInsNoPristines(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB but skips pristine registers.
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:81
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * > > *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
bool empty() const
Returns true if the set is empty.
Definition: LivePhysRegs.h:78
void dump() const
Dumps the currently live registers to the debug output.
MCRegAliasIterator enumerates all registers aliasing Reg.
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
bool isValid() const
isValid - Returns true until all the operands have been visited.
MIBundleOperands - Iterate over all operands in a bundle of machine instructions.
iterator_range< livein_iterator > liveins() const
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool isCalleeSavedInfoValid() const
Has the callee saved info been calculated yet?
const std::vector< CalleeSavedInfo > & getCalleeSavedInfo() const
Returns a reference to call saved info vector for the current function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:289
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
Definition: SparseSet.h:241
const_iterator begin() const
Definition: SparseSet.h:174
const_iterator end() const
Definition: SparseSet.h:175
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< filter_iterator< ConstMIBundleOperands, bool(*)(const MachineOperand &)> > phys_regs_and_masks(const MachineInstr &MI)
Returns an iterator range over all physical register and mask operands for MI and bundled instruction...
Definition: LiveRegUnits.h:166
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1738
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)
Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.