LLVM  16.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"
34 #include "llvm/ADT/SmallVector.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/PassRegistry.h"
41 
42 namespace llvm {
43 
44 class MachineBasicBlock;
45 class MachineRegisterInfo;
46 
48 public:
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.
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  ///
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 
126 private: // Intermediate data structures
127  MachineFunction *MF;
128 
129  MachineRegisterInfo* MRI;
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);
181 public:
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
llvm::LiveVariables::VarInfo::isLiveIn
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.
Definition: LiveVariables.cpp:790
llvm::LiveVariables::addVirtualRegisterKilled
void addVirtualRegisterKilled(Register IncomingReg, MachineInstr &MI, bool AddIfNotFound=false)
addVirtualRegisterKilled - Add information about the fact that the specified register is killed after...
Definition: LiveVariables.h:207
llvm::LiveVariables::addVirtualRegisterDead
void addVirtualRegisterDead(Register IncomingReg, MachineInstr &MI, bool AddIfNotFound=false)
addVirtualRegisterDead - Add information about the fact that the specified register is dead after bei...
Definition: LiveVariables.h:242
IndexedMap.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LiveVariables::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: LiveVariables.cpp:611
llvm::LiveVariables::ID
static char ID
Definition: LiveVariables.h:49
llvm::LiveVariables::isLiveIn
bool isLiveIn(Register Reg, const MachineBasicBlock &MBB)
Definition: LiveVariables.h:288
llvm::LiveVariables::MarkVirtRegAliveInBlock
void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)
Definition: LiveVariables.cpp:115
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::LiveVariables::VarInfo::Kills
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
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
DenseMap.h
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
PassRegistry.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::LiveVariables::VarInfo::findKill
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
Definition: LiveVariables.cpp:60
SparseBitVector.h
llvm::SparseBitVector
Definition: SparseBitVector.h:256
llvm::LiveVariables::VarInfo::removeKill
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:95
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::LiveVariables::VarInfo
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:80
llvm::LiveVariables::removeVirtualRegisterKilled
bool removeVirtualRegisterKilled(Register Reg, MachineInstr &MI)
removeVirtualRegisterKilled - Remove the specified kill of the virtual register from the live variabl...
Definition: LiveVariables.h:217
llvm::LiveVariables::recomputeForSingleDefVirtReg
void recomputeForSingleDefVirtReg(Register Reg)
Recompute liveness from scratch for a virtual register Reg that is known to have a single def that do...
Definition: LiveVariables.cpp:670
llvm::IndexedMap
Definition: IndexedMap.h:30
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::initializeLiveVariablesPass
void initializeLiveVariablesPass(PassRegistry &)
llvm::LiveVariables::replaceKillInstruction
void replaceKillInstruction(Register Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one.
Definition: LiveVariables.cpp:752
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::LiveVariables::VarInfo::dump
void dump() const
Definition: LiveVariables.cpp:68
llvm::LiveVariables::HandleVirtRegDef
void HandleVirtRegDef(Register reg, MachineInstr &MI)
Definition: LiveVariables.cpp:178
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::LiveVariables::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: LiveVariables.h:271
llvm::LiveVariables::addNewBlock
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
Definition: LiveVariables.cpp:832
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:508
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::find
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:1610
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SparseBitVector::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:472
I
#define I(x, y, z)
Definition: MD5.cpp:58
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::LiveVariables::isLiveOut
bool isLiveOut(Register Reg, const MachineBasicBlock &MBB)
isLiveOut - Determine if Reg is live out from MBB, when not considering PHI nodes.
Definition: LiveVariables.cpp:807
llvm::LiveVariables::LiveVariables
LiveVariables()
Definition: LiveVariables.h:50
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LiveVariables::setPHIJoin
void setPHIJoin(Register Reg)
setPHIJoin - Mark Reg as a phi join register.
Definition: LiveVariables.h:314
llvm::LiveVariables::isPHIJoin
bool isPHIJoin(Register Reg)
isPHIJoin - Return true if Reg is a phi join register.
Definition: LiveVariables.h:311
llvm::LiveVariables::removeVirtualRegistersKilled
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
Definition: LiveVariables.cpp:760
llvm::LiveVariables::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LiveVariables.cpp:53
SmallVector.h
llvm::LiveVariables::HandleVirtRegUse
void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI)
Definition: LiveVariables.cpp:127
llvm::LiveVariables::getVarInfo
VarInfo & getVarInfo(Register Reg)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
Definition: LiveVariables.cpp:84
llvm::SmallVectorImpl< unsigned >
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::LiveVariables
Definition: LiveVariables.h:47
llvm::LiveVariables::removeVirtualRegisterDead
bool removeVirtualRegisterDead(Register Reg, MachineInstr &MI)
removeVirtualRegisterDead - Remove the specified kill of the virtual register from the live variable ...
Definition: LiveVariables.h:252
llvm::VirtRegInfo
VirtRegInfo - Information about a virtual register used by a set of operands.
Definition: MachineInstrBundle.h:218
InitializePasses.h
TargetRegisterInfo.h
llvm::LiveVariables::RegisterDefIsDead
bool RegisterDefIsDead(MachineInstr &MI, Register Reg) const
RegisterDefIsDead - Return true if the specified instruction defines the specified register,...
SmallSet.h
llvm::LiveVariables::VarInfo::AliveBlocks
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:85