LLVM 17.0.0git
LivePhysRegs.h
Go to the documentation of this file.
1//===- llvm/CodeGen/LivePhysRegs.h - Live Physical Register Set -*- 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/// \file
10/// This file implements the LivePhysRegs utility for tracking liveness of
11/// physical registers. This can be used for ad-hoc liveness tracking after
12/// register allocation. You can start with the live-ins/live-outs at the
13/// beginning/end of a block and update the information while walking the
14/// instructions inside the block. This implementation tracks the liveness on a
15/// sub-register granularity.
16///
17/// We assume that the high bits of a physical super-register are not preserved
18/// unless the instruction has an implicit-use operand reading the super-
19/// register.
20///
21/// X86 Example:
22/// %ymm0 = ...
23/// %xmm0 = ... (Kills %xmm0, all %xmm0s sub-registers, and %ymm0)
24///
25/// %ymm0 = ...
26/// %xmm0 = ..., implicit %ymm0 (%ymm0 and all its sub-registers are alive)
27//===----------------------------------------------------------------------===//
28
29#ifndef LLVM_CODEGEN_LIVEPHYSREGS_H
30#define LLVM_CODEGEN_LIVEPHYSREGS_H
31
32#include "llvm/ADT/SparseSet.h"
35#include "llvm/MC/MCRegister.h"
37#include <cassert>
38#include <utility>
39
40namespace llvm {
41
42class MachineInstr;
43class MachineFunction;
44class MachineOperand;
45class MachineRegisterInfo;
46class raw_ostream;
47
48/// A set of physical registers with utility functions to track liveness
49/// when walking backward/forward through a basic block.
51 const TargetRegisterInfo *TRI = nullptr;
53 RegisterSet LiveRegs;
54
55public:
56 /// Constructs an unitialized set. init() needs to be called to initialize it.
57 LivePhysRegs() = default;
58
59 /// Constructs and initializes an empty set.
61 LiveRegs.setUniverse(TRI.getNumRegs());
62 }
63
64 LivePhysRegs(const LivePhysRegs&) = delete;
66
67 /// (re-)initializes and clears the set.
68 void init(const TargetRegisterInfo &TRI) {
69 this->TRI = &TRI;
70 LiveRegs.clear();
71 LiveRegs.setUniverse(TRI.getNumRegs());
72 }
73
74 /// Clears the set.
75 void clear() { LiveRegs.clear(); }
76
77 /// Returns true if the set is empty.
78 bool empty() const { return LiveRegs.empty(); }
79
80 /// Adds a physical register and all its sub-registers to the set.
82 assert(TRI && "LivePhysRegs is not initialized.");
83 assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
84 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
85 SubRegs.isValid(); ++SubRegs)
86 LiveRegs.insert(*SubRegs);
87 }
88
89 /// Removes a physical register, all its sub-registers, and all its
90 /// super-registers from the set.
92 assert(TRI && "LivePhysRegs is not initialized.");
93 assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
94 for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R)
95 LiveRegs.erase(*R);
96 }
97
98 /// Removes physical registers clobbered by the regmask operand \p MO.
99 void removeRegsInMask(const MachineOperand &MO,
100 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers =
101 nullptr);
102
103 /// Returns true if register \p Reg is contained in the set. This also
104 /// works if only the super register of \p Reg has been defined, because
105 /// addReg() always adds all sub-registers to the set as well.
106 /// Note: Returns false if just some sub registers are live, use available()
107 /// when searching a free register.
108 bool contains(MCPhysReg Reg) const { return LiveRegs.count(Reg); }
109
110 /// Returns true if register \p Reg and no aliasing register is in the set.
111 bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const;
112
113 /// Remove defined registers and regmask kills from the set.
114 void removeDefs(const MachineInstr &MI);
115
116 /// Add uses to the set.
117 void addUses(const MachineInstr &MI);
118
119 /// Simulates liveness when stepping backwards over an instruction(bundle).
120 /// Remove Defs, add uses. This is the recommended way of calculating
121 /// liveness.
122 void stepBackward(const MachineInstr &MI);
123
124 /// Simulates liveness when stepping forward over an instruction(bundle).
125 /// Remove killed-uses, add defs. This is the not recommended way, because it
126 /// depends on accurate kill flags. If possible use stepBackward() instead of
127 /// this function. The clobbers set will be the list of registers either
128 /// defined or clobbered by a regmask. The operand will identify whether this
129 /// is a regmask or register operand.
130 void stepForward(const MachineInstr &MI,
131 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers);
132
133 /// Adds all live-in registers of basic block \p MBB.
134 /// Live in registers are the registers in the blocks live-in list and the
135 /// pristine registers.
136 void addLiveIns(const MachineBasicBlock &MBB);
137
138 /// Adds all live-in registers of basic block \p MBB but skips pristine
139 /// registers.
141
142 /// Adds all live-out registers of basic block \p MBB.
143 /// Live out registers are the union of the live-in registers of the successor
144 /// blocks and pristine registers. Live out registers of the end block are the
145 /// callee saved registers.
146 /// If a register is not added by this method, it is guaranteed to not be
147 /// live out from MBB, although a sub-register may be. This is true
148 /// both before and after regalloc.
149 void addLiveOuts(const MachineBasicBlock &MBB);
150
151 /// Adds all live-out registers of basic block \p MBB but skips pristine
152 /// registers.
154
156
157 const_iterator begin() const { return LiveRegs.begin(); }
158 const_iterator end() const { return LiveRegs.end(); }
159
160 /// Prints the currently live registers to \p OS.
161 void print(raw_ostream &OS) const;
162
163 /// Dumps the currently live registers to the debug output.
164 void dump() const;
165
166private:
167 /// Adds live-in registers from basic block \p MBB, taking associated
168 /// lane masks into consideration.
169 void addBlockLiveIns(const MachineBasicBlock &MBB);
170
171 /// Adds pristine registers. Pristine registers are callee saved registers
172 /// that are unused in the function.
173 void addPristines(const MachineFunction &MF);
174};
175
177 LR.print(OS);
178 return OS;
179}
180
181/// Computes registers live-in to \p MBB assuming all of its successors
182/// live-in lists are up-to-date. Puts the result into the given LivePhysReg
183/// instance \p LiveRegs.
184void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB);
185
186/// Recomputes dead and kill flags in \p MBB.
187void recomputeLivenessFlags(MachineBasicBlock &MBB);
188
189/// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB.
190/// Does not add reserved registers.
191void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
192
193/// Convenience function combining computeLiveIns() and addLiveIns().
194void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
195 MachineBasicBlock &MBB);
196
197/// Convenience function for recomputing live-in's for \p MBB.
199 LivePhysRegs LPR;
202}
203
204} // end namespace llvm
205
206#endif // LLVM_CODEGEN_LIVEPHYSREGS_H
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
IRTranslator LLVM IR MI
unsigned const TargetRegisterInfo * TRI
unsigned Reg
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SparseSet class derived from the version described in Briggs,...
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
bool contains(MCPhysReg Reg) const
Returns true if register Reg is contained in the set.
Definition: LivePhysRegs.h:108
RegisterSet::const_iterator const_iterator
Definition: LivePhysRegs.h:155
const_iterator end() const
Definition: LivePhysRegs.h:158
void clear()
Clears the set.
Definition: LivePhysRegs.h:75
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * > > &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
LivePhysRegs(const LivePhysRegs &)=delete
void print(raw_ostream &OS) const
Prints the currently live registers to OS.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void removeReg(MCPhysReg Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set.
Definition: LivePhysRegs.h:91
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:68
void addLiveIns(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB.
void addUses(const MachineInstr &MI)
Add uses to the set.
void removeDefs(const MachineInstr &MI)
Remove defined registers and regmask kills from the set.
void addLiveOutsNoPristines(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB but skips pristine registers.
LivePhysRegs(const TargetRegisterInfo &TRI)
Constructs and initializes an empty set.
Definition: LivePhysRegs.h:60
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
LivePhysRegs()=default
Constructs an unitialized set. init() needs to be called to initialize it.
const_iterator begin() const
Definition: LivePhysRegs.h:157
void addLiveInsNoPristines(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB but skips pristine registers.
LivePhysRegs & operator=(const LivePhysRegs &)=delete
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:81
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * > > *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
bool empty() const
Returns true if the set is empty.
Definition: LivePhysRegs.h:78
void dump() const
Dumps the currently live registers to the debug output.
MCRegAliasIterator enumerates all registers aliasing Reg.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MCSubRegIterator enumerates all sub-registers of Reg.
void clearLiveIns()
Clear live in list.
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:288
bool empty() const
empty - Returns true if the set is empty.
Definition: SparseSet.h:183
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
Definition: SparseSet.h:240
void clear()
clear - Clears the set.
Definition: SparseSet.h:194
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:252
const_iterator begin() const
Definition: SparseSet.h:174
const_iterator end() const
Definition: SparseSet.h:175
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
typename DenseT::const_iterator const_iterator
Definition: SparseSet.h:172
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for MBB.
Definition: LivePhysRegs.h:198
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)
Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date.
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.