LLVM 19.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"
40#include "llvm/PassRegistry.h"
41
42namespace llvm {
43
44class MachineBasicBlock;
45class MachineRegisterInfo;
46
48public:
49 static char ID; // Pass identification, replacement for typeid
52 }
53
54 /// VarInfo - This represents the regions where a virtual register is live in
55 /// the program. We represent this with three different pieces of
56 /// information: the set of blocks in which the instruction is live
57 /// throughout, the set of blocks in which the instruction is actually used,
58 /// and the set of non-phi instructions that are the last users of the value.
59 ///
60 /// In the common case where a value is defined and killed in the same block,
61 /// There is one killing instruction, and AliveBlocks is empty.
62 ///
63 /// Otherwise, the value is live out of the block. If the value is live
64 /// throughout any blocks, these blocks are listed in AliveBlocks. Blocks
65 /// where the liveness range ends are not included in AliveBlocks, instead
66 /// being captured by the Kills set. In these blocks, the value is live into
67 /// the block (unless the value is defined and killed in the same block) and
68 /// lives until the specified instruction. Note that there cannot ever be a
69 /// value whose Kills set contains two instructions from the same basic block.
70 ///
71 /// PHI nodes complicate things a bit. If a PHI node is the last user of a
72 /// value in one of its predecessor blocks, it is not listed in the kills set,
73 /// but does include the predecessor block in the AliveBlocks set (unless that
74 /// block also defines the value). This leads to the (perfectly sensical)
75 /// situation where a value is defined in a block, and the last use is a phi
76 /// node in the successor. In this case, AliveBlocks is empty (the value is
77 /// not live across any blocks) and Kills is empty (phi nodes are not
78 /// included). This is sensical because the value must be live to the end of
79 /// the block, but is not live in any successor blocks.
80 struct VarInfo {
81 /// AliveBlocks - Set of blocks in which this value is alive completely
82 /// through. This is a bit set which uses the basic block number as an
83 /// index.
84 ///
86
87 /// Kills - List of MachineInstruction's which are the last use of this
88 /// virtual register (kill it) in their basic block.
89 ///
90 std::vector<MachineInstr*> Kills;
91
92 /// removeKill - Delete a kill corresponding to the specified
93 /// machine instruction. Returns true if there was a kill
94 /// corresponding to this instruction, false otherwise.
96 std::vector<MachineInstr *>::iterator I = find(Kills, &MI);
97 if (I == Kills.end())
98 return false;
99 Kills.erase(I);
100 return true;
101 }
102
103 /// findKill - Find a kill instruction in MBB. Return NULL if none is found.
105
106 /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through
107 /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in
108 /// MBB, it is not considered live in.
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 /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the
145 /// uses. Pay special attention to the sub-register uses which may come below
146 /// the last use of the whole register.
147 bool HandlePhysRegKill(Register Reg, MachineInstr *MI);
148
149 /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask.
150 void HandleRegMask(const MachineOperand &, unsigned);
151
152 void HandlePhysRegUse(Register Reg, MachineInstr &MI);
153 void HandlePhysRegDef(Register Reg, MachineInstr *MI,
155 void UpdatePhysRegDefs(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs);
156
157 /// FindLastRefOrPartRef - Return the last reference or partial reference of
158 /// the specified register.
159 MachineInstr *FindLastRefOrPartRef(Register Reg);
160
161 /// FindLastPartialDef - Return the last partial def of the specified
162 /// register. Also returns the sub-registers that're defined by the
163 /// instruction.
164 MachineInstr *FindLastPartialDef(Register Reg,
165 SmallSet<unsigned, 4> &PartDefRegs);
166
167 /// analyzePHINodes - Gather information about the PHI nodes in here. In
168 /// particular, we want to map the variable information of a virtual
169 /// register which is used in a PHI node. We map that to the BB the vreg
170 /// is coming from.
171 void analyzePHINodes(const MachineFunction& Fn);
172
173 void runOnInstr(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs,
174 unsigned NumRegs);
175
176 void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs);
177public:
178
179 bool runOnMachineFunction(MachineFunction &MF) override;
180
181 //===--------------------------------------------------------------------===//
182 // API to update live variable information
183
184 /// Recompute liveness from scratch for a virtual register \p Reg that is
185 /// known to have a single def that dominates all uses. This can be useful
186 /// after removing some uses of \p Reg. It is not necessary for the whole
187 /// machine function to be in SSA form.
189
190 /// replaceKillInstruction - Update register kill info by replacing a kill
191 /// instruction with a new one.
193 MachineInstr &NewMI);
194
195 /// addVirtualRegisterKilled - Add information about the fact that the
196 /// specified register is killed after being used by the specified
197 /// instruction. If AddIfNotFound is true, add a implicit operand if it's
198 /// not found.
200 bool AddIfNotFound = false) {
201 if (MI.addRegisterKilled(IncomingReg, TRI, AddIfNotFound))
202 getVarInfo(IncomingReg).Kills.push_back(&MI);
203 }
204
205 /// removeVirtualRegisterKilled - Remove the specified kill of the virtual
206 /// register from the live variable information. Returns true if the
207 /// variable was marked as killed by the specified instruction,
208 /// false otherwise.
210 if (!getVarInfo(Reg).removeKill(MI))
211 return false;
212
213 bool Removed = false;
214 for (MachineOperand &MO : MI.operands()) {
215 if (MO.isReg() && MO.isKill() && MO.getReg() == Reg) {
216 MO.setIsKill(false);
217 Removed = true;
218 break;
219 }
220 }
221
222 assert(Removed && "Register is not used by this instruction!");
223 (void)Removed;
224 return true;
225 }
226
227 /// removeVirtualRegistersKilled - Remove all killed info for the specified
228 /// instruction.
230
231 /// addVirtualRegisterDead - Add information about the fact that the specified
232 /// register is dead after being used by the specified instruction. If
233 /// AddIfNotFound is true, add a implicit operand if it's not found.
235 bool AddIfNotFound = false) {
236 if (MI.addRegisterDead(IncomingReg, TRI, AddIfNotFound))
237 getVarInfo(IncomingReg).Kills.push_back(&MI);
238 }
239
240 /// removeVirtualRegisterDead - Remove the specified kill of the virtual
241 /// register from the live variable information. Returns true if the
242 /// variable was marked dead at the specified instruction, false
243 /// otherwise.
245 if (!getVarInfo(Reg).removeKill(MI))
246 return false;
247
248 bool Removed = false;
249 for (MachineOperand &MO : MI.operands()) {
250 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
251 MO.setIsDead(false);
252 Removed = true;
253 break;
254 }
255 }
256 assert(Removed && "Register is not defined by this instruction!");
257 (void)Removed;
258 return true;
259 }
260
261 void getAnalysisUsage(AnalysisUsage &AU) const override;
262
263 void releaseMemory() override {
264 VirtRegInfo.clear();
265 }
266
267 /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
268 /// register.
269 VarInfo &getVarInfo(Register Reg);
270
271 void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
273 void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock,
276
279
281 return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI);
282 }
283
284 /// isLiveOut - Determine if Reg is live out from MBB, when not considering
285 /// PHI nodes. This means that Reg is either killed by a successor block or
286 /// passed through one.
288
289 /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
290 /// variables that are live out of DomBB and live into SuccBB will be marked
291 /// as passing live through BB. This method assumes that the machine code is
292 /// still in SSA form.
294 MachineBasicBlock *DomBB,
295 MachineBasicBlock *SuccBB);
296
298 MachineBasicBlock *DomBB,
299 MachineBasicBlock *SuccBB,
300 std::vector<SparseBitVector<>> &LiveInSets);
301};
302
303} // End llvm namespace
304
305#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())
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the SparseBitVector class.
Represent the analysis usage information of a pass.
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)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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)
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...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
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...
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 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:1751
void initializeLiveVariablesPass(PassRegistry &)
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:80
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:95
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:90
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:85
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
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.
VirtRegInfo - Information about a virtual register used by a set of operands.