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 | |
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; |
52 | using RegisterSet = SparseSet<MCPhysReg, identity<MCPhysReg>>; |
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. |
60 | LivePhysRegs(const TargetRegisterInfo &TRI) : TRI(&TRI) { |
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. |
81 | void addReg(MCPhysReg Reg) { |
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(Val: SubReg); |
86 | } |
87 | |
88 | /// Removes a physical register, all its sub-registers, and all its |
89 | /// super-registers from the set. |
90 | void removeReg(MCPhysReg Reg) { |
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(Key: *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(Key: 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. |
139 | void addLiveInsNoPristines(const MachineBasicBlock &MBB); |
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. |
152 | void addLiveOutsNoPristines(const MachineBasicBlock &MBB); |
153 | |
154 | using const_iterator = RegisterSet::const_iterator; |
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 | |
165 | private: |
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 | |
175 | inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) { |
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. |
183 | void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB); |
184 | |
185 | /// Recomputes dead and kill flags in \p MBB. |
186 | void 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. |
190 | void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs); |
191 | |
192 | /// Convenience function combining computeLiveIns() and addLiveIns(). |
193 | void 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. |
198 | static inline bool recomputeLiveIns(MachineBasicBlock &MBB) { |
199 | LivePhysRegs LPR; |
200 | auto oldLiveIns = MBB.getLiveIns(); |
201 | |
202 | MBB.clearLiveIns(); |
203 | computeAndAddLiveIns(LiveRegs&: LPR, MBB); |
204 | MBB.sortUniqueLiveIns(); |
205 | |
206 | auto newLiveIns = MBB.getLiveIns(); |
207 | return oldLiveIns != newLiveIns; |
208 | } |
209 | |
210 | } // end namespace llvm |
211 | |
212 | #endif // LLVM_CODEGEN_LIVEPHYSREGS_H |
213 | |