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 (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.
91   void removeReg(MCPhysReg Reg) {
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.
140   void addLiveInsNoPristines(const MachineBasicBlock &MBB);
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.
153   void addLiveOutsNoPristines(const MachineBasicBlock &MBB);
154 
155   using const_iterator = RegisterSet::const_iterator;
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 
176 inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
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();
201   computeAndAddLiveIns(LPR, MBB);
202 }
203 
204 } // end namespace llvm
205 
206 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H
207