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
42namespace llvm {
43
44class MachineBasicBlock;
45class MachineRegisterInfo;
46
47class LiveVariables : public MachineFunctionPass {
48public:
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
115private:
116 /// VirtRegInfo - This list is a mapping from virtual register number to
117 /// variable information.
118 ///
119 IndexedMap<VarInfo, VirtReg2IndexFunctor> VirtRegInfo;
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.
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);
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.
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

source code of llvm/include/llvm/CodeGen/LiveVariables.h