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"
33#include "llvm/CodeGen/MachineBasicBlock.h"
34#include "llvm/CodeGen/TargetRegisterInfo.h"
35#include "llvm/MC/MCRegister.h"
36#include "llvm/MC/MCRegisterInfo.h"
37#include <cassert>
38#include <utility>
39
40namespace llvm {
41
42template <typename T> class ArrayRef;
43
44class MachineInstr;
45class MachineFunction;
46class MachineOperand;
47class MachineRegisterInfo;
48class raw_ostream;
49
50/// A set of physical registers with utility functions to track liveness
51/// when walking backward/forward through a basic block.
52class LivePhysRegs {
53 const TargetRegisterInfo *TRI = nullptr;
54 using RegisterSet = SparseSet<MCPhysReg, identity<MCPhysReg>>;
55 RegisterSet LiveRegs;
56
57public:
58 /// Constructs an unitialized set. init() needs to be called to initialize it.
59 LivePhysRegs() = default;
60
61 /// Constructs and initializes an empty set.
62 LivePhysRegs(const TargetRegisterInfo &TRI) : TRI(&TRI) {
63 LiveRegs.setUniverse(TRI.getNumRegs());
64 }
65
66 LivePhysRegs(const LivePhysRegs&) = delete;
67 LivePhysRegs &operator=(const LivePhysRegs&) = delete;
68
69 /// (re-)initializes and clears the set.
70 void init(const TargetRegisterInfo &TRI) {
71 this->TRI = &TRI;
72 LiveRegs.clear();
73 LiveRegs.setUniverse(TRI.getNumRegs());
74 }
75
76 /// Clears the set.
77 void clear() { LiveRegs.clear(); }
78
79 /// Returns true if the set is empty.
80 bool empty() const { return LiveRegs.empty(); }
81
82 /// Adds a physical register and all its sub-registers to the set.
83 void addReg(MCPhysReg Reg) {
84 assert(TRI && "LivePhysRegs is not initialized.");
85 assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
86 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
87 LiveRegs.insert(Val: SubReg);
88 }
89
90 /// Removes a physical register, all its sub-registers, and all its
91 /// super-registers from the set.
92 void removeReg(MCPhysReg Reg) {
93 assert(TRI && "LivePhysRegs is not initialized.");
94 assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
95 for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R)
96 LiveRegs.erase(Key: *R);
97 }
98
99 /// Removes physical registers clobbered by the regmask operand \p MO.
100 void removeRegsInMask(const MachineOperand &MO,
101 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers =
102 nullptr);
103
104 /// Returns true if register \p Reg is contained in the set. This also
105 /// works if only the super register of \p Reg has been defined, because
106 /// addReg() always adds all sub-registers to the set as well.
107 /// Note: Returns false if just some sub registers are live, use available()
108 /// when searching a free register.
109 bool contains(MCPhysReg Reg) const { return LiveRegs.count(Key: Reg); }
110
111 /// Returns true if register \p Reg and no aliasing register is in the set.
112 bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const;
113
114 /// Remove defined registers and regmask kills from the set.
115 void removeDefs(const MachineInstr &MI);
116
117 /// Add uses to the set.
118 void addUses(const MachineInstr &MI);
119
120 /// Simulates liveness when stepping backwards over an instruction(bundle).
121 /// Remove Defs, add uses. This is the recommended way of calculating
122 /// liveness.
123 void stepBackward(const MachineInstr &MI);
124
125 /// Simulates liveness when stepping forward over an instruction(bundle).
126 /// Remove killed-uses, add defs. This is the not recommended way, because it
127 /// depends on accurate kill flags. If possible use stepBackward() instead of
128 /// this function. The clobbers set will be the list of registers either
129 /// defined or clobbered by a regmask. The operand will identify whether this
130 /// is a regmask or register operand.
131 void stepForward(const MachineInstr &MI,
132 SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers);
133
134 /// Adds all live-in registers of basic block \p MBB.
135 /// Live in registers are the registers in the blocks live-in list and the
136 /// pristine registers.
137 void addLiveIns(const MachineBasicBlock &MBB);
138
139 /// Adds all live-in registers of basic block \p MBB but skips pristine
140 /// registers.
141 void addLiveInsNoPristines(const MachineBasicBlock &MBB);
142
143 /// Adds all live-out registers of basic block \p MBB.
144 /// Live out registers are the union of the live-in registers of the successor
145 /// blocks and pristine registers. Live out registers of the end block are the
146 /// callee saved registers.
147 /// If a register is not added by this method, it is guaranteed to not be
148 /// live out from MBB, although a sub-register may be. This is true
149 /// both before and after regalloc.
150 void addLiveOuts(const MachineBasicBlock &MBB);
151
152 /// Adds all live-out registers of basic block \p MBB but skips pristine
153 /// registers.
154 void addLiveOutsNoPristines(const MachineBasicBlock &MBB);
155
156 using const_iterator = RegisterSet::const_iterator;
157
158 const_iterator begin() const { return LiveRegs.begin(); }
159 const_iterator end() const { return LiveRegs.end(); }
160
161 /// Prints the currently live registers to \p OS.
162 void print(raw_ostream &OS) const;
163
164 /// Dumps the currently live registers to the debug output.
165 void dump() const;
166
167private:
168 /// Adds live-in registers from basic block \p MBB, taking associated
169 /// lane masks into consideration.
170 void addBlockLiveIns(const MachineBasicBlock &MBB);
171
172 /// Adds pristine registers. Pristine registers are callee saved registers
173 /// that are unused in the function.
174 void addPristines(const MachineFunction &MF);
175};
176
177inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
178 LR.print(OS);
179 return OS;
180}
181
182/// Computes registers live-in to \p MBB assuming all of its successors
183/// live-in lists are up-to-date. Puts the result into the given LivePhysReg
184/// instance \p LiveRegs.
185void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB);
186
187/// Recomputes dead and kill flags in \p MBB.
188void recomputeLivenessFlags(MachineBasicBlock &MBB);
189
190/// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB.
191/// Does not add reserved registers.
192void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
193
194/// Convenience function combining computeLiveIns() and addLiveIns().
195void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
196 MachineBasicBlock &MBB);
197
198/// Convenience function for recomputing live-in's for a MBB. Returns true if
199/// any changes were made.
200static inline bool recomputeLiveIns(MachineBasicBlock &MBB) {
201 LivePhysRegs LPR;
202 std::vector<MachineBasicBlock::RegisterMaskPair> OldLiveIns;
203
204 MBB.clearLiveIns(OldLiveIns);
205 computeAndAddLiveIns(LiveRegs&: LPR, MBB);
206 MBB.sortUniqueLiveIns();
207
208 const std::vector<MachineBasicBlock::RegisterMaskPair> &NewLiveIns =
209 MBB.getLiveIns();
210 return OldLiveIns != NewLiveIns;
211}
212
213/// Convenience function for recomputing live-in's for a set of MBBs until the
214/// computation converges.
215inline void fullyRecomputeLiveIns(ArrayRef<MachineBasicBlock *> MBBs) {
216 MachineBasicBlock *const *Data = MBBs.data();
217 const size_t Len = MBBs.size();
218 while (true) {
219 bool AnyChange = false;
220 for (size_t I = 0; I < Len; ++I)
221 if (recomputeLiveIns(MBB&: *Data[I]))
222 AnyChange = true;
223 if (!AnyChange)
224 return;
225 }
226}
227
228
229} // end namespace llvm
230
231#endif // LLVM_CODEGEN_LIVEPHYSREGS_H
232