Line data Source code
1 : //===- llvm/CodeGen/LivePhysRegs.h - Live Physical Register Set -*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : /// \file
11 : /// This file implements the LivePhysRegs utility for tracking liveness of
12 : /// physical registers. This can be used for ad-hoc liveness tracking after
13 : /// register allocation. You can start with the live-ins/live-outs at the
14 : /// beginning/end of a block and update the information while walking the
15 : /// instructions inside the block. This implementation tracks the liveness on a
16 : /// sub-register granularity.
17 : ///
18 : /// We assume that the high bits of a physical super-register are not preserved
19 : /// unless the instruction has an implicit-use operand reading the super-
20 : /// register.
21 : ///
22 : /// X86 Example:
23 : /// %ymm0 = ...
24 : /// %xmm0 = ... (Kills %xmm0, all %xmm0s sub-registers, and %ymm0)
25 : ///
26 : /// %ymm0 = ...
27 : /// %xmm0 = ..., implicit %ymm0 (%ymm0 and all its sub-registers are alive)
28 : //===----------------------------------------------------------------------===//
29 :
30 : #ifndef LLVM_CODEGEN_LIVEPHYSREGS_H
31 : #define LLVM_CODEGEN_LIVEPHYSREGS_H
32 :
33 : #include "llvm/ADT/SparseSet.h"
34 : #include "llvm/CodeGen/MachineBasicBlock.h"
35 : #include "llvm/CodeGen/TargetRegisterInfo.h"
36 : #include "llvm/MC/MCRegisterInfo.h"
37 : #include <cassert>
38 : #include <utility>
39 :
40 : namespace llvm {
41 :
42 : class MachineInstr;
43 : class MachineOperand;
44 : class MachineRegisterInfo;
45 : class raw_ostream;
46 :
47 : /// A set of physical registers with utility functions to track liveness
48 : /// when walking backward/forward through a basic block.
49 253872 : class LivePhysRegs {
50 : const TargetRegisterInfo *TRI = nullptr;
51 : SparseSet<unsigned> LiveRegs;
52 :
53 : public:
54 : /// Constructs an unitialized set. init() needs to be called to initialize it.
55 532587 : LivePhysRegs() = default;
56 :
57 : /// Constructs and initializes an empty set.
58 17461 : LivePhysRegs(const TargetRegisterInfo &TRI) : TRI(&TRI) {
59 17461 : LiveRegs.setUniverse(TRI.getNumRegs());
60 : }
61 :
62 : LivePhysRegs(const LivePhysRegs&) = delete;
63 : LivePhysRegs &operator=(const LivePhysRegs&) = delete;
64 :
65 : /// (re-)initializes and clears the set.
66 : void init(const TargetRegisterInfo &TRI) {
67 307987 : this->TRI = &TRI;
68 : LiveRegs.clear();
69 309713 : LiveRegs.setUniverse(TRI.getNumRegs());
70 : }
71 :
72 : /// Clears the set.
73 : void clear() { LiveRegs.clear(); }
74 :
75 : /// Returns true if the set is empty.
76 : bool empty() const { return LiveRegs.empty(); }
77 :
78 : /// Adds a physical register and all its sub-registers to the set.
79 12224737 : void addReg(unsigned Reg) {
80 : assert(TRI && "LivePhysRegs is not initialized.");
81 : assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
82 12224737 : for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
83 59037995 : SubRegs.isValid(); ++SubRegs)
84 93626516 : LiveRegs.insert(*SubRegs);
85 12224737 : }
86 :
87 : /// Removes a physical register, all its sub-registers, and all its
88 : /// super-registers from the set.
89 5712656 : void removeReg(unsigned Reg) {
90 : assert(TRI && "LivePhysRegs is not initialized.");
91 : assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
92 48468373 : for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R)
93 85511434 : LiveRegs.erase(*R);
94 5712656 : }
95 :
96 : /// Removes physical registers clobbered by the regmask operand \p MO.
97 : void removeRegsInMask(const MachineOperand &MO,
98 : SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers =
99 : nullptr);
100 :
101 : /// Returns true if register \p Reg is contained in the set. This also
102 : /// works if only the super register of \p Reg has been defined, because
103 : /// addReg() always adds all sub-registers to the set as well.
104 : /// Note: Returns false if just some sub registers are live, use available()
105 : /// when searching a free register.
106 : bool contains(unsigned Reg) const { return LiveRegs.count(Reg); }
107 :
108 : /// Returns true if register \p Reg and no aliasing register is in the set.
109 : bool available(const MachineRegisterInfo &MRI, unsigned Reg) const;
110 :
111 : /// Remove defined registers and regmask kills from the set.
112 : void removeDefs(const MachineInstr &MI);
113 :
114 : /// Add uses to the set.
115 : void addUses(const MachineInstr &MI);
116 :
117 : /// Simulates liveness when stepping backwards over an instruction(bundle).
118 : /// Remove Defs, add uses. This is the recommended way of calculating
119 : /// liveness.
120 : void stepBackward(const MachineInstr &MI);
121 :
122 : /// Simulates liveness when stepping forward over an instruction(bundle).
123 : /// Remove killed-uses, add defs. This is the not recommended way, because it
124 : /// depends on accurate kill flags. If possible use stepBackward() instead of
125 : /// this function. The clobbers set will be the list of registers either
126 : /// defined or clobbered by a regmask. The operand will identify whether this
127 : /// is a regmask or register operand.
128 : void stepForward(const MachineInstr &MI,
129 : SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers);
130 :
131 : /// Adds all live-in registers of basic block \p MBB.
132 : /// Live in registers are the registers in the blocks live-in list and the
133 : /// pristine registers.
134 : void addLiveIns(const MachineBasicBlock &MBB);
135 :
136 : /// Adds all live-out registers of basic block \p MBB.
137 : /// Live out registers are the union of the live-in registers of the successor
138 : /// blocks and pristine registers. Live out registers of the end block are the
139 : /// callee saved registers.
140 : void addLiveOuts(const MachineBasicBlock &MBB);
141 :
142 : /// Adds all live-out registers of basic block \p MBB but skips pristine
143 : /// registers.
144 : void addLiveOutsNoPristines(const MachineBasicBlock &MBB);
145 :
146 : using const_iterator = SparseSet<unsigned>::const_iterator;
147 :
148 : const_iterator begin() const { return LiveRegs.begin(); }
149 : const_iterator end() const { return LiveRegs.end(); }
150 :
151 : /// Prints the currently live registers to \p OS.
152 : void print(raw_ostream &OS) const;
153 :
154 : /// Dumps the currently live registers to the debug output.
155 : void dump() const;
156 :
157 : private:
158 : /// Adds live-in registers from basic block \p MBB, taking associated
159 : /// lane masks into consideration.
160 : void addBlockLiveIns(const MachineBasicBlock &MBB);
161 :
162 : /// Adds pristine registers. Pristine registers are callee saved registers
163 : /// that are unused in the function.
164 : void addPristines(const MachineFunction &MF);
165 : };
166 :
167 : inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
168 : LR.print(OS);
169 : return OS;
170 : }
171 :
172 : /// Computes registers live-in to \p MBB assuming all of its successors
173 : /// live-in lists are up-to-date. Puts the result into the given LivePhysReg
174 : /// instance \p LiveRegs.
175 : void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB);
176 :
177 : /// Recomputes dead and kill flags in \p MBB.
178 : void recomputeLivenessFlags(MachineBasicBlock &MBB);
179 :
180 : /// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB.
181 : /// Does not add reserved registers.
182 : void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
183 :
184 : /// Convenience function combining computeLiveIns() and addLiveIns().
185 : void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
186 : MachineBasicBlock &MBB);
187 :
188 : /// Convenience function for recomputing live-in's for \p MBB.
189 344 : static inline void recomputeLiveIns(MachineBasicBlock &MBB) {
190 : LivePhysRegs LPR;
191 344 : MBB.clearLiveIns();
192 344 : computeAndAddLiveIns(LPR, MBB);
193 344 : }
194 :
195 : } // end namespace llvm
196 :
197 : #endif // LLVM_CODEGEN_LIVEPHYSREGS_H
|
