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 // 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<def> = ... 23 // %XMM0<def> = ... (Kills %XMM0, all %XMM0s sub-registers, and %YMM0) 24 // 25 // %YMM0<def> = ... 26 // %XMM0<def> = ..., %YMM0<imp-use> (%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/MC/MCRegisterInfo.h" 35 #include "llvm/Target/TargetRegisterInfo.h" 36 #include <cassert> 37 #include <utility> 38 39 namespace llvm { 40 41 class MachineInstr; 42 43 /// \brief A set of live physical registers with functions to track liveness 44 /// when walking backward/forward through a basic block. 45 class LivePhysRegs { 46 const TargetRegisterInfo *TRI = nullptr; 47 SparseSet<unsigned> LiveRegs; 48 49 LivePhysRegs(const LivePhysRegs&) = delete; 50 LivePhysRegs &operator=(const LivePhysRegs&) = delete; 51 52 public: 53 /// \brief Constructs a new empty LivePhysRegs set. 54 LivePhysRegs() = default; 55 56 /// \brief Constructs and initialize an empty LivePhysRegs set. 57 LivePhysRegs(const TargetRegisterInfo *TRI) : TRI(TRI) { 58 assert(TRI && "Invalid TargetRegisterInfo pointer."); 59 LiveRegs.setUniverse(TRI->getNumRegs()); 60 } 61 62 /// \brief Clear and initialize the LivePhysRegs set. 63 void init(const TargetRegisterInfo &TRI) { 64 this->TRI = &TRI; 65 LiveRegs.clear(); 66 LiveRegs.setUniverse(TRI.getNumRegs()); 67 } 68 69 /// \brief Clears the LivePhysRegs set. 70 void clear() { LiveRegs.clear(); } 71 72 /// \brief Returns true if the set is empty. 73 bool empty() const { return LiveRegs.empty(); } 74 75 /// \brief Adds a physical register and all its sub-registers to the set. 76 void addReg(unsigned Reg) { 77 assert(TRI && "LivePhysRegs is not initialized."); 78 assert(Reg <= TRI->getNumRegs() && "Expected a physical register."); 79 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 80 SubRegs.isValid(); ++SubRegs) 81 LiveRegs.insert(*SubRegs); 82 } 83 84 /// \brief Removes a physical register, all its sub-registers, and all its 85 /// super-registers from the set. 86 void removeReg(unsigned Reg) { 87 assert(TRI && "LivePhysRegs is not initialized."); 88 assert(Reg <= TRI->getNumRegs() && "Expected a physical register."); 89 for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R) 90 LiveRegs.erase(*R); 91 } 92 93 /// \brief Removes physical registers clobbered by the regmask operand @p MO. 94 void removeRegsInMask(const MachineOperand &MO, 95 SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers); 96 97 /// \brief Returns true if register @p Reg is contained in the set. This also 98 /// works if only the super register of @p Reg has been defined, because 99 /// addReg() always adds all sub-registers to the set as well. 100 /// Note: Returns false if just some sub registers are live, use available() 101 /// when searching a free register. 102 bool contains(unsigned Reg) const { return LiveRegs.count(Reg); } 103 104 /// Returns true if register \p Reg and no aliasing register is in the set. 105 bool available(const MachineRegisterInfo &MRI, unsigned Reg) const; 106 107 /// \brief Simulates liveness when stepping backwards over an 108 /// instruction(bundle): Remove Defs, add uses. This is the recommended way of 109 /// calculating liveness. 110 void stepBackward(const MachineInstr &MI); 111 112 /// \brief Simulates liveness when stepping forward over an 113 /// instruction(bundle): Remove killed-uses, add defs. This is the not 114 /// recommended way, because it depends on accurate kill flags. If possible 115 /// use stepBackward() instead of this function. 116 /// The clobbers set will be the list of registers either defined or clobbered 117 /// by a regmask. The operand will identify whether this is a regmask or 118 /// register operand. 119 void stepForward(const MachineInstr &MI, 120 SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers); 121 122 /// Adds all live-in registers of basic block @p MBB. 123 /// Live in registers are the registers in the blocks live-in list and the 124 /// pristine registers. 125 void addLiveIns(const MachineBasicBlock &MBB); 126 127 /// Adds all live-out registers of basic block @p MBB. 128 /// Live out registers are the union of the live-in registers of the successor 129 /// blocks and pristine registers. Live out registers of the end block are the 130 /// callee saved registers. 131 void addLiveOuts(const MachineBasicBlock &MBB); 132 133 /// Like addLiveOuts() but does not add pristine registers/callee saved 134 /// registers. 135 void addLiveOutsNoPristines(const MachineBasicBlock &MBB); 136 137 typedef SparseSet<unsigned>::const_iterator const_iterator; 138 const_iterator begin() const { return LiveRegs.begin(); } 139 const_iterator end() const { return LiveRegs.end(); } 140 141 /// \brief Prints the currently live registers to @p OS. 142 void print(raw_ostream &OS) const; 143 144 /// \brief Dumps the currently live registers to the debug output. 145 void dump() const; 146 147 private: 148 /// Adds live-in registers from basic block @p MBB, taking associated 149 /// lane masks into consideration. 150 void addBlockLiveIns(const MachineBasicBlock &MBB); 151 }; 152 153 inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) { 154 LR.print(OS); 155 return OS; 156 } 157 158 /// Compute the live-in list for \p MBB assuming all of its successors live-in 159 /// lists are up-to-date. Uses the given LivePhysReg instance \p LiveRegs; This 160 /// is just here to avoid repeated heap allocations when calling this multiple 161 /// times in a pass. 162 void computeLiveIns(LivePhysRegs &LiveRegs, const TargetRegisterInfo &TRI, 163 MachineBasicBlock &MBB); 164 165 } // end namespace llvm 166 167 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H 168