LLVM 17.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
121 /// PHIJoins - list of virtual registers that are PHI joins. These registers
122 /// may have multiple definitions, and they require special handling when
123 /// building live intervals.
124 SparseBitVector<> PHIJoins;
125
126private: // Intermediate data structures
127 MachineFunction *MF;
128
130
131 const TargetRegisterInfo *TRI;
132
133 // PhysRegInfo - Keep track of which instruction was the last def 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 *> PhysRegDef;
137
138 // PhysRegInfo - Keep track of which instruction was the last use of a
139 // physical register. This is a purely local property, because all physical
140 // register references are presumed dead across basic blocks.
141 std::vector<MachineInstr *> PhysRegUse;
142
143 std::vector<SmallVector<unsigned, 4>> PHIVarInfo;
144
145 // DistanceMap - Keep track the distance of a MI from the start of the
146 // current basic block.
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&);
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
180 void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs);
181public:
182
183 bool runOnMachineFunction(MachineFunction &MF) override;
184
185 /// RegisterDefIsDead - Return true if the specified instruction defines the
186 /// specified register, but that definition is dead.
188
189 //===--------------------------------------------------------------------===//
190 // API to update live variable information
191
192 /// Recompute liveness from scratch for a virtual register \p Reg that is
193 /// known to have a single def that dominates all uses. This can be useful
194 /// after removing some uses of \p Reg. It is not necessary for the whole
195 /// machine function to be in SSA form.
197
198 /// replaceKillInstruction - Update register kill info by replacing a kill
199 /// instruction with a new one.
201 MachineInstr &NewMI);
202
203 /// addVirtualRegisterKilled - Add information about the fact that the
204 /// specified register is killed after being used by the specified
205 /// instruction. If AddIfNotFound is true, add a implicit operand if it's
206 /// not found.
208 bool AddIfNotFound = false) {
209 if (MI.addRegisterKilled(IncomingReg, TRI, AddIfNotFound))
210 getVarInfo(IncomingReg).Kills.push_back(&MI);
211 }
212
213 /// removeVirtualRegisterKilled - Remove the specified kill of the virtual
214 /// register from the live variable information. Returns true if the
215 /// variable was marked as killed by the specified instruction,
216 /// false otherwise.
218 if (!getVarInfo(Reg).removeKill(MI))
219 return false;
220
221 bool Removed = false;
222 for (MachineOperand &MO : MI.operands()) {
223 if (MO.isReg() && MO.isKill() && MO.getReg() == Reg) {
224 MO.setIsKill(false);
225 Removed = true;
226 break;
227 }
228 }
229
230 assert(Removed && "Register is not used by this instruction!");
231 (void)Removed;
232 return true;
233 }
234
235 /// removeVirtualRegistersKilled - Remove all killed info for the specified
236 /// instruction.
238
239 /// addVirtualRegisterDead - Add information about the fact that the specified
240 /// register is dead after being used by the specified instruction. If
241 /// AddIfNotFound is true, add a implicit operand if it's not found.
243 bool AddIfNotFound = false) {
244 if (MI.addRegisterDead(IncomingReg, TRI, AddIfNotFound))
245 getVarInfo(IncomingReg).Kills.push_back(&MI);
246 }
247
248 /// removeVirtualRegisterDead - Remove the specified kill of the virtual
249 /// register from the live variable information. Returns true if the
250 /// variable was marked dead at the specified instruction, false
251 /// otherwise.
253 if (!getVarInfo(Reg).removeKill(MI))
254 return false;
255
256 bool Removed = false;
257 for (MachineOperand &MO : MI.operands()) {
258 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
259 MO.setIsDead(false);
260 Removed = true;
261 break;
262 }
263 }
264 assert(Removed && "Register is not defined by this instruction!");
265 (void)Removed;
266 return true;
267 }
268
269 void getAnalysisUsage(AnalysisUsage &AU) const override;
270
271 void releaseMemory() override {
272 VirtRegInfo.clear();
273 }
274
275 /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
276 /// register.
277 VarInfo &getVarInfo(Register Reg);
278
279 void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
281 void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock,
284
287
289 return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI);
290 }
291
292 /// isLiveOut - Determine if Reg is live out from MBB, when not considering
293 /// PHI nodes. This means that Reg is either killed by a successor block or
294 /// passed through one.
296
297 /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
298 /// variables that are live out of DomBB and live into SuccBB will be marked
299 /// as passing live through BB. This method assumes that the machine code is
300 /// still in SSA form.
302 MachineBasicBlock *DomBB,
303 MachineBasicBlock *SuccBB);
304
306 MachineBasicBlock *DomBB,
307 MachineBasicBlock *SuccBB,
308 std::vector<SparseBitVector<>> &LiveInSets);
309
310 /// isPHIJoin - Return true if Reg is a phi join register.
311 bool isPHIJoin(Register Reg) { return PHIJoins.test(Reg.id()); }
312
313 /// setPHIJoin - Mark Reg as a phi join register.
314 void setPHIJoin(Register Reg) { PHIJoins.set(Reg.id()); }
315};
316
317} // End llvm namespace
318
319#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)
bool isPHIJoin(Register Reg)
isPHIJoin - Return true if Reg is a phi join register.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool RegisterDefIsDead(MachineInstr &MI, Register Reg) const
RegisterDefIsDead - Return true if the specified instruction defines the specified register,...
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 setPHIJoin(Register Reg)
setPHIJoin - Mark Reg as a phi join register.
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:68
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:577
void set(unsigned Idx)
bool test(unsigned Idx) const
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:1755
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.