LLVM 19.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 (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
85 LiveRegs.insert(SubReg);
86 }
87
88 /// Removes a physical register, all its sub-registers, and all its
89 /// super-registers from the set.
91 assert(TRI && "LivePhysRegs is not initialized.");
92 assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
93 for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R)
94 LiveRegs.erase(*R);
95 }
96
97 /// Removes physical registers clobbered by the regmask operand \p MO.
98 void removeRegsInMask(const MachineOperand &MO,
99 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers =
100 nullptr);
101
102 /// Returns true if register \p Reg is contained in the set. This also
103 /// works if only the super register of \p Reg has been defined, because
104 /// addReg() always adds all sub-registers to the set as well.
105 /// Note: Returns false if just some sub registers are live, use available()
106 /// when searching a free register.
107 bool contains(MCPhysReg Reg) const { return LiveRegs.count(Reg); }
108
109 /// Returns true if register \p Reg and no aliasing register is in the set.
110 bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const;
111
112 /// Remove defined registers and regmask kills from the set.
113 void removeDefs(const MachineInstr &MI);
114
115 /// Add uses to the set.
116 void addUses(const MachineInstr &MI);
117
118 /// Simulates liveness when stepping backwards over an instruction(bundle).
119 /// Remove Defs, add uses. This is the recommended way of calculating
120 /// liveness.
121 void stepBackward(const MachineInstr &MI);
122
123 /// Simulates liveness when stepping forward over an instruction(bundle).
124 /// Remove killed-uses, add defs. This is the not recommended way, because it
125 /// depends on accurate kill flags. If possible use stepBackward() instead of
126 /// this function. The clobbers set will be the list of registers either
127 /// defined or clobbered by a regmask. The operand will identify whether this
128 /// is a regmask or register operand.
129 void stepForward(const MachineInstr &MI,
130 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers);
131
132 /// Adds all live-in registers of basic block \p MBB.
133 /// Live in registers are the registers in the blocks live-in list and the
134 /// pristine registers.
135 void addLiveIns(const MachineBasicBlock &MBB);
136
137 /// Adds all live-in registers of basic block \p MBB but skips pristine
138 /// registers.
140
141 /// Adds all live-out registers of basic block \p MBB.
142 /// Live out registers are the union of the live-in registers of the successor
143 /// blocks and pristine registers. Live out registers of the end block are the
144 /// callee saved registers.
145 /// If a register is not added by this method, it is guaranteed to not be
146 /// live out from MBB, although a sub-register may be. This is true
147 /// both before and after regalloc.
148 void addLiveOuts(const MachineBasicBlock &MBB);
149
150 /// Adds all live-out registers of basic block \p MBB but skips pristine
151 /// registers.
153
155
156 const_iterator begin() const { return LiveRegs.begin(); }
157 const_iterator end() const { return LiveRegs.end(); }
158
159 /// Prints the currently live registers to \p OS.
160 void print(raw_ostream &OS) const;
161
162 /// Dumps the currently live registers to the debug output.
163 void dump() const;
164
165private:
166 /// Adds live-in registers from basic block \p MBB, taking associated
167 /// lane masks into consideration.
168 void addBlockLiveIns(const MachineBasicBlock &MBB);
169
170 /// Adds pristine registers. Pristine registers are callee saved registers
171 /// that are unused in the function.
172 void addPristines(const MachineFunction &MF);
173};
174
176 LR.print(OS);
177 return OS;
178}
179
180/// Computes registers live-in to \p MBB assuming all of its successors
181/// live-in lists are up-to-date. Puts the result into the given LivePhysReg
182/// instance \p LiveRegs.
183void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB);
184
185/// Recomputes dead and kill flags in \p MBB.
186void recomputeLivenessFlags(MachineBasicBlock &MBB);
187
188/// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB.
189/// Does not add reserved registers.
190void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
191
192/// Convenience function combining computeLiveIns() and addLiveIns().
193void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
194 MachineBasicBlock &MBB);
195
196/// Convenience function for recomputing live-in's for a MBB. Returns true if
197/// any changes were made.
199 LivePhysRegs LPR;
200 auto oldLiveIns = MBB.getLiveIns();
201
205
206 auto newLiveIns = MBB.getLiveIns();
207 return oldLiveIns != newLiveIns;
208}
209
210} // end namespace llvm
211
212#endif // LLVM_CODEGEN_LIVEPHYSREGS_H
unsigned SubReg
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:107
RegisterSet::const_iterator const_iterator
Definition: LivePhysRegs.h:154
const_iterator end() const
Definition: LivePhysRegs.h:157
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:90
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:156
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.
void clearLiveIns()
Clear live in list.
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
std::vector< RegisterMaskPair > getLiveIns() const
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:586
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:289
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:241
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:253
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
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
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.
static bool recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for a MBB.
Definition: LivePhysRegs.h:198