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 template <typename T> class ArrayRef; 43 44 class MachineInstr; 45 class MachineFunction; 46 class MachineOperand; 47 class MachineRegisterInfo; 48 class raw_ostream; 49 50 /// A set of physical registers with utility functions to track liveness 51 /// when walking backward/forward through a basic block. 52 class LivePhysRegs { 53 const TargetRegisterInfo *TRI = nullptr; 54 using RegisterSet = SparseSet<MCPhysReg, identity<MCPhysReg>>; 55 RegisterSet LiveRegs; 56 57 public: 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(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(*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(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 167 private: 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 177 inline 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. 185 void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB); 186 187 /// Recomputes dead and kill flags in \p MBB. 188 void 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. 192 void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs); 193 194 /// Convenience function combining computeLiveIns() and addLiveIns(). 195 void 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. 200 static inline bool recomputeLiveIns(MachineBasicBlock &MBB) { 201 LivePhysRegs LPR; 202 std::vector<MachineBasicBlock::RegisterMaskPair> OldLiveIns; 203 204 MBB.clearLiveIns(OldLiveIns); 205 computeAndAddLiveIns(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. 215 inline 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(*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