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" |
34 | #include "llvm/ADT/SmallVector.h" |
35 | #include "llvm/ADT/SparseBitVector.h" |
36 | #include "llvm/CodeGen/MachineFunctionPass.h" |
37 | #include "llvm/CodeGen/MachineInstr.h" |
38 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
39 | #include "llvm/InitializePasses.h" |
40 | #include "llvm/PassRegistry.h" |
41 | |
42 | namespace llvm { |
43 | |
44 | class MachineBasicBlock; |
45 | class MachineRegisterInfo; |
46 | |
47 | class LiveVariables : public MachineFunctionPass { |
48 | public: |
49 | static char ID; // Pass identification, replacement for typeid |
50 | LiveVariables() : MachineFunctionPass(ID) { |
51 | initializeLiveVariablesPass(*PassRegistry::getPassRegistry()); |
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 | /// |
85 | SparseBitVector<> AliveBlocks; |
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. |
95 | bool removeKill(MachineInstr &MI) { |
96 | std::vector<MachineInstr *>::iterator I = find(Range&: Kills, Val: &MI); |
97 | if (I == Kills.end()) |
98 | return false; |
99 | Kills.erase(position: I); |
100 | return true; |
101 | } |
102 | |
103 | /// findKill - Find a kill instruction in MBB. Return NULL if none is found. |
104 | MachineInstr *findKill(const MachineBasicBlock *MBB) const; |
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. |
109 | bool isLiveIn(const MachineBasicBlock &MBB, Register Reg, |
110 | MachineRegisterInfo &MRI); |
111 | |
112 | void dump() const; |
113 | }; |
114 | |
115 | private: |
116 | /// VirtRegInfo - This list is a mapping from virtual register number to |
117 | /// variable information. |
118 | /// |
119 | IndexedMap<VarInfo, VirtReg2IndexFunctor> VirtRegInfo; |
120 | |
121 | private: // 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. |
142 | DenseMap<MachineInstr*, unsigned> DistanceMap; |
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, |
154 | SmallVectorImpl<unsigned> &Defs); |
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); |
177 | public: |
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. |
188 | void recomputeForSingleDefVirtReg(Register Reg); |
189 | |
190 | /// replaceKillInstruction - Update register kill info by replacing a kill |
191 | /// instruction with a new one. |
192 | void replaceKillInstruction(Register Reg, MachineInstr &OldMI, |
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. |
199 | void addVirtualRegisterKilled(Register IncomingReg, MachineInstr &MI, |
200 | bool AddIfNotFound = false) { |
201 | if (MI.addRegisterKilled(IncomingReg, RegInfo: TRI, AddIfNotFound)) |
202 | getVarInfo(Reg: IncomingReg).Kills.push_back(x: &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. |
209 | bool removeVirtualRegisterKilled(Register Reg, MachineInstr &MI) { |
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. |
229 | void removeVirtualRegistersKilled(MachineInstr &MI); |
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. |
234 | void addVirtualRegisterDead(Register IncomingReg, MachineInstr &MI, |
235 | bool AddIfNotFound = false) { |
236 | if (MI.addRegisterDead(Reg: IncomingReg, RegInfo: TRI, AddIfNotFound)) |
237 | getVarInfo(Reg: IncomingReg).Kills.push_back(x: &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. |
244 | bool removeVirtualRegisterDead(Register Reg, MachineInstr &MI) { |
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, |
272 | MachineBasicBlock *BB); |
273 | void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, |
274 | MachineBasicBlock *BB, |
275 | SmallVectorImpl<MachineBasicBlock *> &WorkList); |
276 | |
277 | void HandleVirtRegDef(Register reg, MachineInstr &MI); |
278 | void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI); |
279 | |
280 | bool isLiveIn(Register Reg, const MachineBasicBlock &MBB) { |
281 | return getVarInfo(Reg).isLiveIn(MBB, Reg, MRI&: *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. |
287 | bool isLiveOut(Register Reg, const MachineBasicBlock &MBB); |
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. |
293 | void addNewBlock(MachineBasicBlock *BB, |
294 | MachineBasicBlock *DomBB, |
295 | MachineBasicBlock *SuccBB); |
296 | |
297 | void addNewBlock(MachineBasicBlock *BB, |
298 | MachineBasicBlock *DomBB, |
299 | MachineBasicBlock *SuccBB, |
300 | std::vector<SparseBitVector<>> &LiveInSets); |
301 | }; |
302 | |
303 | } // End llvm namespace |
304 | |
305 | #endif |
306 | |