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/MachinePassManager.h"
39#include "llvm/CodeGen/TargetRegisterInfo.h"
40#include "llvm/InitializePasses.h"
41#include "llvm/PassRegistry.h"
42
43namespace llvm {
44
45class MachineBasicBlock;
46class MachineRegisterInfo;
47
48class LiveVariables {
49 friend class LiveVariablesWrapperPass;
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 ///
83 SparseBitVector<> AliveBlocks;
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.
93 bool removeKill(MachineInstr &MI) {
94 std::vector<MachineInstr *>::iterator I = find(Range&: Kills, Val: &MI);
95 if (I == Kills.end())
96 return false;
97 Kills.erase(position: I);
98 return true;
99 }
100
101 /// findKill - Find a kill instruction in MBB. Return NULL if none is found.
102 MachineInstr *findKill(const MachineBasicBlock *MBB) const;
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.
107 bool isLiveIn(const MachineBasicBlock &MBB, Register Reg,
108 MachineRegisterInfo &MRI);
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 ///
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 // 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,
159 SmallVectorImpl<unsigned> &Defs);
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:
184 LiveVariables(MachineFunction &MF);
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.
195 void recomputeForSingleDefVirtReg(Register Reg);
196
197 /// replaceKillInstruction - Update register kill info by replacing a kill
198 /// instruction with a new one.
199 void replaceKillInstruction(Register Reg, MachineInstr &OldMI,
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.
206 void addVirtualRegisterKilled(Register IncomingReg, MachineInstr &MI,
207 bool AddIfNotFound = false) {
208 if (MI.addRegisterKilled(IncomingReg, RegInfo: TRI, AddIfNotFound))
209 getVarInfo(Reg: IncomingReg).Kills.push_back(x: &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.
216 bool removeVirtualRegisterKilled(Register Reg, MachineInstr &MI) {
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.
236 void removeVirtualRegistersKilled(MachineInstr &MI);
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.
241 void addVirtualRegisterDead(Register IncomingReg, MachineInstr &MI,
242 bool AddIfNotFound = false) {
243 if (MI.addRegisterDead(Reg: IncomingReg, RegInfo: TRI, AddIfNotFound))
244 getVarInfo(Reg: IncomingReg).Kills.push_back(x: &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.
251 bool removeVirtualRegisterDead(Register Reg, MachineInstr &MI) {
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,
273 MachineBasicBlock *BB);
274 void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock,
275 MachineBasicBlock *BB,
276 SmallVectorImpl<MachineBasicBlock *> &WorkList);
277
278 void HandleVirtRegDef(Register reg, MachineInstr &MI);
279 void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI);
280
281 bool isLiveIn(Register Reg, const MachineBasicBlock &MBB) {
282 return getVarInfo(Reg).isLiveIn(MBB, Reg, MRI&: *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.
288 bool isLiveOut(Register Reg, const MachineBasicBlock &MBB);
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.
294 void addNewBlock(MachineBasicBlock *BB,
295 MachineBasicBlock *DomBB,
296 MachineBasicBlock *SuccBB);
297
298 void addNewBlock(MachineBasicBlock *BB,
299 MachineBasicBlock *DomBB,
300 MachineBasicBlock *SuccBB,
301 std::vector<SparseBitVector<>> &LiveInSets);
302};
303
304class LiveVariablesAnalysis : public AnalysisInfoMixin<LiveVariablesAnalysis> {
305 friend AnalysisInfoMixin<LiveVariablesAnalysis>;
306 static AnalysisKey Key;
307
308public:
309 using Result = LiveVariables;
310 Result run(MachineFunction &MF, MachineFunctionAnalysisManager &);
311};
312
313class LiveVariablesPrinterPass
314 : public PassInfoMixin<LiveVariablesPrinterPass> {
315 raw_ostream &OS;
316
317public:
318 explicit LiveVariablesPrinterPass(raw_ostream &OS) : OS(OS) {}
319 PreservedAnalyses run(MachineFunction &MF,
320 MachineFunctionAnalysisManager &MFAM);
321 static bool isRequired() { return true; }
322};
323
324class LiveVariablesWrapperPass : public MachineFunctionPass {
325 LiveVariables LV;
326
327public:
328 static char ID; // Pass identification, replacement for typeid
329
330 LiveVariablesWrapperPass() : MachineFunctionPass(ID) {
331 initializeLiveVariablesWrapperPassPass(*PassRegistry::getPassRegistry());
332 }
333
334 bool runOnMachineFunction(MachineFunction &MF) override {
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
349