LLVM 20.0.0git
LiveVariables.h
Go to the documentation of this file.
1//===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===//
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 LiveVariables analysis pass. For each machine
10// instruction in the function, this pass calculates the set of registers that
11// are immediately dead after the instruction (i.e., the instruction calculates
12// the value, but it is never used) and the set of registers that are used by
13// the instruction, but are never used after the instruction (i.e., they are
14// killed).
15//
16// This class computes live variables using a sparse implementation based on
17// the machine code SSA form. This class computes live variable information for
18// each virtual and _register allocatable_ physical register in a function. It
19// uses the dominance properties of SSA form to efficiently compute live
20// variables for virtual registers, and assumes that physical registers are only
21// live within a single basic block (allowing it to do a single local analysis
22// to resolve physical register lifetimes in each basic block). If a physical
23// register is not register allocatable, it is not tracked. This is useful for
24// things like the stack pointer and condition codes.
25//
26//===----------------------------------------------------------------------===//
27
28#ifndef LLVM_CODEGEN_LIVEVARIABLES_H
29#define LLVM_CODEGEN_LIVEVARIABLES_H
30
31#include "llvm/ADT/DenseMap.h"
32#include "llvm/ADT/IndexedMap.h"
33#include "llvm/ADT/SmallSet.h"
41#include "llvm/PassRegistry.h"
42
43namespace llvm {
44
45class MachineBasicBlock;
46class MachineRegisterInfo;
47
50
51public:
52 /// VarInfo - This represents the regions where a virtual register is live in
53 /// the program. We represent this with three different pieces of
54 /// information: the set of blocks in which the instruction is live
55 /// throughout, the set of blocks in which the instruction is actually used,
56 /// and the set of non-phi instructions that are the last users of the value.
57 ///
58 /// In the common case where a value is defined and killed in the same block,
59 /// There is one killing instruction, and AliveBlocks is empty.
60 ///
61 /// Otherwise, the value is live out of the block. If the value is live
62 /// throughout any blocks, these blocks are listed in AliveBlocks. Blocks
63 /// where the liveness range ends are not included in AliveBlocks, instead
64 /// being captured by the Kills set. In these blocks, the value is live into
65 /// the block (unless the value is defined and killed in the same block) and
66 /// lives until the specified instruction. Note that there cannot ever be a
67 /// value whose Kills set contains two instructions from the same basic block.
68 ///
69 /// PHI nodes complicate things a bit. If a PHI node is the last user of a
70 /// value in one of its predecessor blocks, it is not listed in the kills set,
71 /// but does include the predecessor block in the AliveBlocks set (unless that
72 /// block also defines the value). This leads to the (perfectly sensical)
73 /// situation where a value is defined in a block, and the last use is a phi
74 /// node in the successor. In this case, AliveBlocks is empty (the value is
75 /// not live across any blocks) and Kills is empty (phi nodes are not
76 /// included). This is sensical because the value must be live to the end of
77 /// the block, but is not live in any successor blocks.
78 struct VarInfo {
79 /// AliveBlocks - Set of blocks in which this value is alive completely
80 /// through. This is a bit set which uses the basic block number as an
81 /// index.
82 ///
84
85 /// Kills - List of MachineInstruction's which are the last use of this
86 /// virtual register (kill it) in their basic block.
87 ///
88 std::vector<MachineInstr*> Kills;
89
90 /// removeKill - Delete a kill corresponding to the specified
91 /// machine instruction. Returns true if there was a kill
92 /// corresponding to this instruction, false otherwise.
94 std::vector<MachineInstr *>::iterator I = find(Kills, &MI);
95 if (I == Kills.end())
96 return false;
97 Kills.erase(I);
98 return true;
99 }
100
101 /// findKill - Find a kill instruction in MBB. Return NULL if none is found.
103
104 /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through
105 /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in
106 /// MBB, it is not considered live in.
109
110 void print(raw_ostream &OS) const;
111
112 void dump() const;
113 };
114
115private:
116 /// VirtRegInfo - This list is a mapping from virtual register number to
117 /// variable information.
118 ///
120
121private: // Intermediate data structures
122 MachineFunction *MF = nullptr;
123
124 MachineRegisterInfo *MRI = nullptr;
125
126 const TargetRegisterInfo *TRI = nullptr;
127
128 // PhysRegInfo - Keep track of which instruction was the last def of a
129 // physical register. This is a purely local property, because all physical
130 // register references are presumed dead across basic blocks.
131 std::vector<MachineInstr *> PhysRegDef;
132
133 // PhysRegInfo - Keep track of which instruction was the last use of a
134 // physical register. This is a purely local property, because all physical
135 // register references are presumed dead across basic blocks.
136 std::vector<MachineInstr *> PhysRegUse;
137
138 std::vector<SmallVector<unsigned, 4>> PHIVarInfo;
139
140 // DistanceMap - Keep track the distance of a MI from the start of the
141 // current basic block.
143
144 // For legacy pass.
145 LiveVariables() = default;
146
147 void analyze(MachineFunction &MF);
148
149 /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the
150 /// uses. Pay special attention to the sub-register uses which may come below
151 /// the last use of the whole register.
152 bool HandlePhysRegKill(Register Reg, MachineInstr *MI);
153
154 /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask.
155 void HandleRegMask(const MachineOperand &, unsigned);
156
157 void HandlePhysRegUse(Register Reg, MachineInstr &MI);
158 void HandlePhysRegDef(Register Reg, MachineInstr *MI,
160 void UpdatePhysRegDefs(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs);
161
162 /// FindLastRefOrPartRef - Return the last reference or partial reference of
163 /// the specified register.
164 MachineInstr *FindLastRefOrPartRef(Register Reg);
165
166 /// FindLastPartialDef - Return the last partial def of the specified
167 /// register. Also returns the sub-registers that're defined by the
168 /// instruction.
169 MachineInstr *FindLastPartialDef(Register Reg,
170 SmallSet<unsigned, 4> &PartDefRegs);
171
172 /// analyzePHINodes - Gather information about the PHI nodes in here. In
173 /// particular, we want to map the variable information of a virtual
174 /// register which is used in a PHI node. We map that to the BB the vreg
175 /// is coming from.
176 void analyzePHINodes(const MachineFunction& Fn);
177
178 void runOnInstr(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs,
179 unsigned NumRegs);
180
181 void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs);
182
183public:
185
186 void print(raw_ostream &OS) const;
187
188 //===--------------------------------------------------------------------===//
189 // API to update live variable information
190
191 /// Recompute liveness from scratch for a virtual register \p Reg that is
192 /// known to have a single def that dominates all uses. This can be useful
193 /// after removing some uses of \p Reg. It is not necessary for the whole
194 /// machine function to be in SSA form.
196
197 /// replaceKillInstruction - Update register kill info by replacing a kill
198 /// instruction with a new one.
200 MachineInstr &NewMI);
201
202 /// addVirtualRegisterKilled - Add information about the fact that the
203 /// specified register is killed after being used by the specified
204 /// instruction. If AddIfNotFound is true, add a implicit operand if it's
205 /// not found.
207 bool AddIfNotFound = false) {
208 if (MI.addRegisterKilled(IncomingReg, TRI, AddIfNotFound))
209 getVarInfo(IncomingReg).Kills.push_back(&MI);
210 }
211
212 /// removeVirtualRegisterKilled - Remove the specified kill of the virtual
213 /// register from the live variable information. Returns true if the
214 /// variable was marked as killed by the specified instruction,
215 /// false otherwise.
217 if (!getVarInfo(Reg).removeKill(MI))
218 return false;
219
220 bool Removed = false;
221 for (MachineOperand &MO : MI.operands()) {
222 if (MO.isReg() && MO.isKill() && MO.getReg() == Reg) {
223 MO.setIsKill(false);
224 Removed = true;
225 break;
226 }
227 }
228
229 assert(Removed && "Register is not used by this instruction!");
230 (void)Removed;
231 return true;
232 }
233
234 /// removeVirtualRegistersKilled - Remove all killed info for the specified
235 /// instruction.
237
238 /// addVirtualRegisterDead - Add information about the fact that the specified
239 /// register is dead after being used by the specified instruction. If
240 /// AddIfNotFound is true, add a implicit operand if it's not found.
242 bool AddIfNotFound = false) {
243 if (MI.addRegisterDead(IncomingReg, TRI, AddIfNotFound))
244 getVarInfo(IncomingReg).Kills.push_back(&MI);
245 }
246
247 /// removeVirtualRegisterDead - Remove the specified kill of the virtual
248 /// register from the live variable information. Returns true if the
249 /// variable was marked dead at the specified instruction, false
250 /// otherwise.
252 if (!getVarInfo(Reg).removeKill(MI))
253 return false;
254
255 bool Removed = false;
256 for (MachineOperand &MO : MI.operands()) {
257 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
258 MO.setIsDead(false);
259 Removed = true;
260 break;
261 }
262 }
263 assert(Removed && "Register is not defined by this instruction!");
264 (void)Removed;
265 return true;
266 }
267
268 /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
269 /// register.
270 VarInfo &getVarInfo(Register Reg);
271
272 void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
274 void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock,
277
280
282 return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI);
283 }
284
285 /// isLiveOut - Determine if Reg is live out from MBB, when not considering
286 /// PHI nodes. This means that Reg is either killed by a successor block or
287 /// passed through one.
289
290 /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
291 /// variables that are live out of DomBB and live into SuccBB will be marked
292 /// as passing live through BB. This method assumes that the machine code is
293 /// still in SSA form.
295 MachineBasicBlock *DomBB,
296 MachineBasicBlock *SuccBB);
297
299 MachineBasicBlock *DomBB,
300 MachineBasicBlock *SuccBB,
301 std::vector<SparseBitVector<>> &LiveInSets);
302};
303
304class LiveVariablesAnalysis : public AnalysisInfoMixin<LiveVariablesAnalysis> {
306 static AnalysisKey Key;
307
308public:
311};
312
314 : public PassInfoMixin<LiveVariablesPrinterPass> {
315 raw_ostream &OS;
316
317public:
321 static bool isRequired() { return true; }
322};
323
325 LiveVariables LV;
326
327public:
328 static char ID; // Pass identification, replacement for typeid
329
332 }
333
335 LV.analyze(MF);
336 return false;
337 }
338
339 void getAnalysisUsage(AnalysisUsage &AU) const override;
340
341 void releaseMemory() override { LV.VirtRegInfo.clear(); }
342
343 LiveVariables &getLV() { return LV; }
344};
345
346} // End llvm namespace
347
348#endif
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
This file defines the DenseMap class.
IRTranslator LLVM IR MI
This file implements an indexed map.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
unsigned Reg
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the SparseBitVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
Represent the analysis usage information of a pass.
Result run(MachineFunction &MF, MachineFunctionAnalysisManager &)
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LiveVariablesPrinterPass(raw_ostream &OS)
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void replaceKillInstruction(Register Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one.
void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)
bool removeVirtualRegisterDead(Register Reg, MachineInstr &MI)
removeVirtualRegisterDead - Remove the specified kill of the virtual register from the live variable ...
bool removeVirtualRegisterKilled(Register Reg, MachineInstr &MI)
removeVirtualRegisterKilled - Remove the specified kill of the virtual register from the live variabl...
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
void addVirtualRegisterDead(Register IncomingReg, MachineInstr &MI, bool AddIfNotFound=false)
addVirtualRegisterDead - Add information about the fact that the specified register is dead after bei...
bool isLiveOut(Register Reg, const MachineBasicBlock &MBB)
isLiveOut - Determine if Reg is live out from MBB, when not considering PHI nodes.
void HandleVirtRegDef(Register reg, MachineInstr &MI)
void print(raw_ostream &OS) const
bool isLiveIn(Register Reg, const MachineBasicBlock &MBB)
void recomputeForSingleDefVirtReg(Register Reg)
Recompute liveness from scratch for a virtual register Reg that is known to have a single def that do...
void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI)
void addVirtualRegisterKilled(Register IncomingReg, MachineInstr &MI, bool AddIfNotFound=false)
addVirtualRegisterKilled - Add information about the fact that the specified register is killed after...
VarInfo & getVarInfo(Register Reg)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
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
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
void initializeLiveVariablesWrapperPassPass(PassRegistry &)
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:92
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:78
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:93
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:88
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:83
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
void print(raw_ostream &OS) const
bool isLiveIn(const MachineBasicBlock &MBB, Register Reg, MachineRegisterInfo &MRI)
isLiveIn - Is Reg live in to MBB? This means that Reg is live through MBB, or it is killed in MBB.
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
VirtRegInfo - Information about a virtual register used by a set of operands.