1 //===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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
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.
26 //===----------------------------------------------------------------------===//
28 #ifndef LLVM_CODEGEN_LIVEVARIABLES_H
29 #define LLVM_CODEGEN_LIVEVARIABLES_H
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"
42 class MachineBasicBlock
;
43 class MachineRegisterInfo
;
45 class LiveVariables
: public MachineFunctionPass
{
47 static char ID
; // Pass identification, replacement for typeid
48 LiveVariables() : MachineFunctionPass(ID
) {
49 initializeLiveVariablesPass(*PassRegistry::getPassRegistry());
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.
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.
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.
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.
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
83 SparseBitVector
<> AliveBlocks
;
85 /// Kills - List of MachineInstruction's which are the last use of this
86 /// virtual register (kill it) in their basic block.
88 std::vector
<MachineInstr
*> Kills
;
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(Kills
, &MI
);
101 /// findKill - Find a kill instruction in MBB. Return NULL if none is found.
102 MachineInstr
*findKill(const MachineBasicBlock
*MBB
) const;
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
,
109 MachineRegisterInfo
&MRI
);
115 /// VirtRegInfo - This list is a mapping from virtual register number to
116 /// variable information.
118 IndexedMap
<VarInfo
, VirtReg2IndexFunctor
> VirtRegInfo
;
120 /// PHIJoins - list of virtual registers that are PHI joins. These registers
121 /// may have multiple definitions, and they require special handling when
122 /// building live intervals.
123 SparseBitVector
<> PHIJoins
;
125 private: // Intermediate data structures
128 MachineRegisterInfo
* MRI
;
130 const TargetRegisterInfo
*TRI
;
132 // PhysRegInfo - Keep track of which instruction was the last def of a
133 // physical register. This is a purely local property, because all physical
134 // register references are presumed dead across basic blocks.
135 std::vector
<MachineInstr
*> PhysRegDef
;
137 // PhysRegInfo - Keep track of which instruction was the last use of a
138 // physical register. This is a purely local property, because all physical
139 // register references are presumed dead across basic blocks.
140 std::vector
<MachineInstr
*> PhysRegUse
;
142 std::vector
<SmallVector
<unsigned, 4>> PHIVarInfo
;
144 // DistanceMap - Keep track the distance of a MI from the start of the
145 // current basic block.
146 DenseMap
<MachineInstr
*, unsigned> DistanceMap
;
148 /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the
149 /// uses. Pay special attention to the sub-register uses which may come below
150 /// the last use of the whole register.
151 bool HandlePhysRegKill(unsigned Reg
, MachineInstr
*MI
);
153 /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask.
154 void HandleRegMask(const MachineOperand
&);
156 void HandlePhysRegUse(unsigned Reg
, MachineInstr
&MI
);
157 void HandlePhysRegDef(unsigned Reg
, MachineInstr
*MI
,
158 SmallVectorImpl
<unsigned> &Defs
);
159 void UpdatePhysRegDefs(MachineInstr
&MI
, SmallVectorImpl
<unsigned> &Defs
);
161 /// FindLastRefOrPartRef - Return the last reference or partial reference of
162 /// the specified register.
163 MachineInstr
*FindLastRefOrPartRef(unsigned Reg
);
165 /// FindLastPartialDef - Return the last partial def of the specified
166 /// register. Also returns the sub-registers that're defined by the
168 MachineInstr
*FindLastPartialDef(unsigned Reg
,
169 SmallSet
<unsigned,4> &PartDefRegs
);
171 /// analyzePHINodes - Gather information about the PHI nodes in here. In
172 /// particular, we want to map the variable information of a virtual
173 /// register which is used in a PHI node. We map that to the BB the vreg
175 void analyzePHINodes(const MachineFunction
& Fn
);
177 void runOnInstr(MachineInstr
&MI
, SmallVectorImpl
<unsigned> &Defs
);
179 void runOnBlock(MachineBasicBlock
*MBB
, unsigned NumRegs
);
182 bool runOnMachineFunction(MachineFunction
&MF
) override
;
184 /// RegisterDefIsDead - Return true if the specified instruction defines the
185 /// specified register, but that definition is dead.
186 bool RegisterDefIsDead(MachineInstr
&MI
, unsigned Reg
) const;
188 //===--------------------------------------------------------------------===//
189 // API to update live variable information
191 /// replaceKillInstruction - Update register kill info by replacing a kill
192 /// instruction with a new one.
193 void replaceKillInstruction(unsigned Reg
, MachineInstr
&OldMI
,
194 MachineInstr
&NewMI
);
196 /// addVirtualRegisterKilled - Add information about the fact that the
197 /// specified register is killed after being used by the specified
198 /// instruction. If AddIfNotFound is true, add a implicit operand if it's
200 void addVirtualRegisterKilled(unsigned IncomingReg
, MachineInstr
&MI
,
201 bool AddIfNotFound
= false) {
202 if (MI
.addRegisterKilled(IncomingReg
, TRI
, AddIfNotFound
))
203 getVarInfo(IncomingReg
).Kills
.push_back(&MI
);
206 /// removeVirtualRegisterKilled - Remove the specified kill of the virtual
207 /// register from the live variable information. Returns true if the
208 /// variable was marked as killed by the specified instruction,
210 bool removeVirtualRegisterKilled(unsigned reg
, MachineInstr
&MI
) {
211 if (!getVarInfo(reg
).removeKill(MI
))
214 bool Removed
= false;
215 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
216 MachineOperand
&MO
= MI
.getOperand(i
);
217 if (MO
.isReg() && MO
.isKill() && MO
.getReg() == reg
) {
224 assert(Removed
&& "Register is not used by this instruction!");
229 /// removeVirtualRegistersKilled - Remove all killed info for the specified
231 void removeVirtualRegistersKilled(MachineInstr
&MI
);
233 /// addVirtualRegisterDead - Add information about the fact that the specified
234 /// register is dead after being used by the specified instruction. If
235 /// AddIfNotFound is true, add a implicit operand if it's not found.
236 void addVirtualRegisterDead(unsigned IncomingReg
, MachineInstr
&MI
,
237 bool AddIfNotFound
= false) {
238 if (MI
.addRegisterDead(IncomingReg
, TRI
, AddIfNotFound
))
239 getVarInfo(IncomingReg
).Kills
.push_back(&MI
);
242 /// removeVirtualRegisterDead - Remove the specified kill of the virtual
243 /// register from the live variable information. Returns true if the
244 /// variable was marked dead at the specified instruction, false
246 bool removeVirtualRegisterDead(unsigned reg
, MachineInstr
&MI
) {
247 if (!getVarInfo(reg
).removeKill(MI
))
250 bool Removed
= false;
251 for (unsigned i
= 0, e
= MI
.getNumOperands(); i
!= e
; ++i
) {
252 MachineOperand
&MO
= MI
.getOperand(i
);
253 if (MO
.isReg() && MO
.isDef() && MO
.getReg() == reg
) {
259 assert(Removed
&& "Register is not defined by this instruction!");
264 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
266 void releaseMemory() override
{
270 /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
272 VarInfo
&getVarInfo(unsigned RegIdx
);
274 void MarkVirtRegAliveInBlock(VarInfo
& VRInfo
, MachineBasicBlock
* DefBlock
,
275 MachineBasicBlock
*BB
);
276 void MarkVirtRegAliveInBlock(VarInfo
& VRInfo
, MachineBasicBlock
* DefBlock
,
277 MachineBasicBlock
*BB
,
278 std::vector
<MachineBasicBlock
*> &WorkList
);
279 void HandleVirtRegDef(unsigned reg
, MachineInstr
&MI
);
280 void HandleVirtRegUse(unsigned reg
, MachineBasicBlock
*MBB
, MachineInstr
&MI
);
282 bool isLiveIn(unsigned Reg
, const MachineBasicBlock
&MBB
) {
283 return getVarInfo(Reg
).isLiveIn(MBB
, Reg
, *MRI
);
286 /// isLiveOut - Determine if Reg is live out from MBB, when not considering
287 /// PHI nodes. This means that Reg is either killed by a successor block or
288 /// passed through one.
289 bool isLiveOut(unsigned Reg
, const MachineBasicBlock
&MBB
);
291 /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
292 /// variables that are live out of DomBB and live into SuccBB will be marked
293 /// as passing live through BB. This method assumes that the machine code is
294 /// still in SSA form.
295 void addNewBlock(MachineBasicBlock
*BB
,
296 MachineBasicBlock
*DomBB
,
297 MachineBasicBlock
*SuccBB
);
299 /// isPHIJoin - Return true if Reg is a phi join register.
300 bool isPHIJoin(unsigned Reg
) { return PHIJoins
.test(Reg
); }
302 /// setPHIJoin - Mark Reg as a phi join register.
303 void setPHIJoin(unsigned Reg
) { PHIJoins
.set(Reg
); }
306 } // End llvm namespace