LLVM  16.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"
36 #include "llvm/MC/MCRegisterInfo.h"
37 #include <cassert>
38 #include <utility>
39 
40 namespace llvm {
41 
42 class MachineInstr;
43 class MachineFunction;
44 class MachineOperand;
45 class MachineRegisterInfo;
46 class raw_ostream;
47 
48 /// A set of physical registers with utility functions to track liveness
49 /// when walking backward/forward through a basic block.
50 class LivePhysRegs {
51  const TargetRegisterInfo *TRI = nullptr;
53  RegisterSet LiveRegs;
54 
55 public:
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;
65  LivePhysRegs &operator=(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 
166 private:
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.
184 void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB);
185 
186 /// Recomputes dead and kill flags in \p MBB.
187 void 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.
191 void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
192 
193 /// Convenience function combining computeLiveIns() and addLiveIns().
194 void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
195  MachineBasicBlock &MBB);
196 
197 /// Convenience function for recomputing live-in's for \p MBB.
198 static inline void recomputeLiveIns(MachineBasicBlock &MBB) {
199  LivePhysRegs LPR;
200  MBB.clearLiveIns();
202 }
203 
204 } // end namespace llvm
205 
206 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm::LivePhysRegs::removeDefs
void removeDefs(const MachineInstr &MI)
Remove defined registers and regmask kills from the set.
Definition: LivePhysRegs.cpp:45
llvm::SparseSet< MCPhysReg, identity< MCPhysReg > >::const_iterator
typename DenseT::const_iterator const_iterator
Definition: SparseSet.h:172
llvm::LivePhysRegs::LivePhysRegs
LivePhysRegs()=default
Constructs an unitialized set. init() needs to be called to initialize it.
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LivePhysRegs::removeReg
void removeReg(MCPhysReg Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set.
Definition: LivePhysRegs.h:91
llvm::computeLiveIns
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.
Definition: LivePhysRegs.cpp:248
llvm::LivePhysRegs::addReg
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:81
llvm::LivePhysRegs::dump
void dump() const
Dumps the currently live registers to the debug output.
Definition: LivePhysRegs.cpp:136
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::recomputeLivenessFlags
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
Definition: LivePhysRegs.cpp:281
llvm::LivePhysRegs::addLiveInsNoPristines
void addLiveInsNoPristines(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB but skips pristine registers.
Definition: LivePhysRegs.cpp:244
llvm::recomputeLiveIns
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for MBB.
Definition: LivePhysRegs.h:198
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
MachineBasicBlock.h
llvm::SparseSet::begin
const_iterator begin() const
Definition: SparseSet.h:174
llvm::LivePhysRegs::removeRegsInMask
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * >> *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
Definition: LivePhysRegs.cpp:31
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::LivePhysRegs::contains
bool contains(MCPhysReg Reg) const
Returns true if register Reg is contained in the set.
Definition: LivePhysRegs.h:108
llvm::addLiveIns
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
Definition: LivePhysRegs.cpp:259
llvm::LivePhysRegs::empty
bool empty() const
Returns true if the set is empty.
Definition: LivePhysRegs.h:78
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::LivePhysRegs::begin
const_iterator begin() const
Definition: LivePhysRegs.h:157
llvm::SparseSet::end
const_iterator end() const
Definition: SparseSet.h:175
llvm::LivePhysRegs::addLiveIns
void addLiveIns(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB.
Definition: LivePhysRegs.cpp:238
llvm::LivePhysRegs::addLiveOuts
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
Definition: LivePhysRegs.cpp:232
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:291
llvm::computeAndAddLiveIns
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
Definition: LivePhysRegs.cpp:341
MCRegister.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::LivePhysRegs::stepBackward
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
Definition: LivePhysRegs.cpp:68
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::SparseSet::clear
void clear()
clear - Clears the set.
Definition: SparseSet.h:194
llvm::LivePhysRegs::addUses
void addUses(const MachineInstr &MI)
Add uses to the set.
Definition: LivePhysRegs.cpp:58
llvm::LivePhysRegs::available
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
Definition: LivePhysRegs.cpp:141
MCRegisterInfo.h
llvm::SparseSet::setUniverse
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LivePhysRegs::print
void print(raw_ostream &OS) const
Prints the currently live registers to OS.
Definition: LivePhysRegs.cpp:118
llvm::LivePhysRegs::operator=
LivePhysRegs & operator=(const LivePhysRegs &)=delete
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::LivePhysRegs::init
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:68
llvm::SparseSet::empty
bool empty() const
empty - Returns true if the set is empty.
Definition: SparseSet.h:183
llvm::LivePhysRegs::stepForward
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand * >> &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
Definition: LivePhysRegs.cpp:80
SparseSet.h
llvm::LivePhysRegs::const_iterator
RegisterSet::const_iterator const_iterator
Definition: LivePhysRegs.h:155
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::LivePhysRegs::LivePhysRegs
LivePhysRegs(const TargetRegisterInfo &TRI)
Constructs and initializes an empty set.
Definition: LivePhysRegs.h:60
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LivePhysRegs::addLiveOutsNoPristines
void addLiveOutsNoPristines(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB but skips pristine registers.
Definition: LivePhysRegs.cpp:209
llvm::SparseSet::insert
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:252
uint16_t
llvm::SparseSet::count
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
llvm::SparseSet::erase
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:288
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::LivePhysRegs::clear
void clear()
Clears the set.
Definition: LivePhysRegs.h:75
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::MachineBasicBlock::clearLiveIns
void clearLiveIns()
Clear live in list.
Definition: MachineBasicBlock.cpp:1611
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SparseSet< MCPhysReg, identity< MCPhysReg > >
TargetRegisterInfo.h
llvm::LivePhysRegs::end
const_iterator end() const
Definition: LivePhysRegs.h:158
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788