LLVM  14.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 
41 namespace llvm {
42 
43 class MachineBasicBlock;
44 class MachineRegisterInfo;
45 
47 public:
48  static char ID; // Pass identification, replacement for typeid
51  }
52 
53  /// VarInfo - This represents the regions where a virtual register is live in
54  /// the program. We represent this with three different pieces of
55  /// information: the set of blocks in which the instruction is live
56  /// throughout, the set of blocks in which the instruction is actually used,
57  /// and the set of non-phi instructions that are the last users of the value.
58  ///
59  /// In the common case where a value is defined and killed in the same block,
60  /// There is one killing instruction, and AliveBlocks is empty.
61  ///
62  /// Otherwise, the value is live out of the block. If the value is live
63  /// throughout any blocks, these blocks are listed in AliveBlocks. Blocks
64  /// where the liveness range ends are not included in AliveBlocks, instead
65  /// being captured by the Kills set. In these blocks, the value is live into
66  /// the block (unless the value is defined and killed in the same block) and
67  /// lives until the specified instruction. Note that there cannot ever be a
68  /// value whose Kills set contains two instructions from the same basic block.
69  ///
70  /// PHI nodes complicate things a bit. If a PHI node is the last user of a
71  /// value in one of its predecessor blocks, it is not listed in the kills set,
72  /// but does include the predecessor block in the AliveBlocks set (unless that
73  /// block also defines the value). This leads to the (perfectly sensical)
74  /// situation where a value is defined in a block, and the last use is a phi
75  /// node in the successor. In this case, AliveBlocks is empty (the value is
76  /// not live across any blocks) and Kills is empty (phi nodes are not
77  /// included). This is sensical because the value must be live to the end of
78  /// the block, but is not live in any successor blocks.
79  struct VarInfo {
80  /// AliveBlocks - Set of blocks in which this value is alive completely
81  /// through. This is a bit set which uses the basic block number as an
82  /// index.
83  ///
85 
86  /// Kills - List of MachineInstruction's which are the last use of this
87  /// virtual register (kill it) in their basic block.
88  ///
89  std::vector<MachineInstr*> Kills;
90 
91  /// removeKill - Delete a kill corresponding to the specified
92  /// machine instruction. Returns true if there was a kill
93  /// corresponding to this instruction, false otherwise.
95  std::vector<MachineInstr *>::iterator I = find(Kills, &MI);
96  if (I == Kills.end())
97  return false;
98  Kills.erase(I);
99  return true;
100  }
101 
102  /// findKill - Find a kill instruction in MBB. Return NULL if none is found.
104 
105  /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through
106  /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in
107  /// MBB, it is not considered live in.
109  MachineRegisterInfo &MRI);
110 
111  void dump() const;
112  };
113 
114 private:
115  /// VirtRegInfo - This list is a mapping from virtual register number to
116  /// variable information.
117  ///
119 
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;
124 
125 private: // Intermediate data structures
126  MachineFunction *MF;
127 
128  MachineRegisterInfo* MRI;
129 
130  const TargetRegisterInfo *TRI;
131 
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;
136 
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;
141 
142  std::vector<SmallVector<unsigned, 4>> PHIVarInfo;
143 
144  // DistanceMap - Keep track the distance of a MI from the start of the
145  // current basic block.
147 
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(Register Reg, MachineInstr *MI);
152 
153  /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask.
154  void HandleRegMask(const MachineOperand&);
155 
156  void HandlePhysRegUse(Register Reg, MachineInstr &MI);
157  void HandlePhysRegDef(Register Reg, MachineInstr *MI,
159  void UpdatePhysRegDefs(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs);
160 
161  /// FindLastRefOrPartRef - Return the last reference or partial reference of
162  /// the specified register.
163  MachineInstr *FindLastRefOrPartRef(Register Reg);
164 
165  /// FindLastPartialDef - Return the last partial def of the specified
166  /// register. Also returns the sub-registers that're defined by the
167  /// instruction.
168  MachineInstr *FindLastPartialDef(Register Reg,
169  SmallSet<unsigned, 4> &PartDefRegs);
170 
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
174  /// is coming from.
175  void analyzePHINodes(const MachineFunction& Fn);
176 
177  void runOnInstr(MachineInstr &MI, SmallVectorImpl<unsigned> &Defs);
178 
179  void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs);
180 public:
181 
182  bool runOnMachineFunction(MachineFunction &MF) override;
183 
184  /// RegisterDefIsDead - Return true if the specified instruction defines the
185  /// specified register, but that definition is dead.
187 
188  //===--------------------------------------------------------------------===//
189  // API to update live variable information
190 
191  /// replaceKillInstruction - Update register kill info by replacing a kill
192  /// instruction with a new one.
194  MachineInstr &NewMI);
195 
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
199  /// not found.
201  bool AddIfNotFound = false) {
202  if (MI.addRegisterKilled(IncomingReg, TRI, AddIfNotFound))
203  getVarInfo(IncomingReg).Kills.push_back(&MI);
204  }
205 
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,
209  /// false otherwise.
211  if (!getVarInfo(Reg).removeKill(MI))
212  return false;
213 
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) {
218  MO.setIsKill(false);
219  Removed = true;
220  break;
221  }
222  }
223 
224  assert(Removed && "Register is not used by this instruction!");
225  (void)Removed;
226  return true;
227  }
228 
229  /// removeVirtualRegistersKilled - Remove all killed info for the specified
230  /// instruction.
232 
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.
237  bool AddIfNotFound = false) {
238  if (MI.addRegisterDead(IncomingReg, TRI, AddIfNotFound))
239  getVarInfo(IncomingReg).Kills.push_back(&MI);
240  }
241 
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
245  /// otherwise.
247  if (!getVarInfo(Reg).removeKill(MI))
248  return false;
249 
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) {
254  MO.setIsDead(false);
255  Removed = true;
256  break;
257  }
258  }
259  assert(Removed && "Register is not defined by this instruction!");
260  (void)Removed;
261  return true;
262  }
263 
264  void getAnalysisUsage(AnalysisUsage &AU) const override;
265 
266  void releaseMemory() override {
267  VirtRegInfo.clear();
268  }
269 
270  /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
271  /// register.
272  VarInfo &getVarInfo(Register Reg);
273 
274  void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock,
276  void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock,
279 
282 
284  return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI);
285  }
286 
287  /// isLiveOut - Determine if Reg is live out from MBB, when not considering
288  /// PHI nodes. This means that Reg is either killed by a successor block or
289  /// passed through one.
291 
292  /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
293  /// variables that are live out of DomBB and live into SuccBB will be marked
294  /// as passing live through BB. This method assumes that the machine code is
295  /// still in SSA form.
297  MachineBasicBlock *DomBB,
298  MachineBasicBlock *SuccBB);
299 
301  MachineBasicBlock *DomBB,
302  MachineBasicBlock *SuccBB,
303  std::vector<SparseBitVector<>> &LiveInSets);
304 
305  /// isPHIJoin - Return true if Reg is a phi join register.
306  bool isPHIJoin(Register Reg) { return PHIJoins.test(Reg.id()); }
307 
308  /// setPHIJoin - Mark Reg as a phi join register.
309  void setPHIJoin(Register Reg) { PHIJoins.set(Reg.id()); }
310 };
311 
312 } // End llvm namespace
313 
314 #endif
i
i
Definition: README.txt:29
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:713
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:200
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:236
IndexedMap.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
MachineInstr.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::LiveVariables::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: LiveVariables.cpp:613
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LiveVariables::ID
static char ID
Definition: LiveVariables.h:48
llvm::LiveVariables::isLiveIn
bool isLiveIn(Register Reg, const MachineBasicBlock &MBB)
Definition: LiveVariables.h:283
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:52
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:500
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:89
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:233
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:134
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
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::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:390
llvm::SparseBitVector
Definition: SparseBitVector.h:255
llvm::LiveVariables::VarInfo::removeKill
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:94
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LiveVariables::VarInfo
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:79
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:210
llvm::IndexedMap
Definition: IndexedMap.h:29
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:674
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
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::MachineBasicBlock
Definition: MachineBasicBlock.h:95
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:266
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:755
llvm::MachineOperand::setIsDead
void setIsDead(bool Val=true)
Definition: MachineOperand.h:506
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:507
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
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:1571
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SparseBitVector::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:471
I
#define I(x, y, z)
Definition: MD5.cpp:59
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::MachineFunction
Definition: MachineFunction.h:230
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:730
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
llvm::LiveVariables::LiveVariables
LiveVariables()
Definition: LiveVariables.h:49
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:309
llvm::LiveVariables::isPHIJoin
bool isPHIJoin(Register Reg)
isPHIJoin - Return true if Reg is a phi join register.
Definition: LiveVariables.h:306
llvm::LiveVariables::removeVirtualRegistersKilled
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
Definition: LiveVariables.cpp:682
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:46
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:246
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:84