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<def> = ... 24 /// %XMM0<def> = ... (Kills %XMM0, all %XMM0s sub-registers, and %YMM0) 25 /// 26 /// %YMM0<def> = ... 27 /// %XMM0<def> = ..., %YMM0<imp-use> (%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/MC/MCRegisterInfo.h" 36 #include "llvm/Target/TargetRegisterInfo.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 /// \brief A set of physical registers with utility functions to track liveness 48 /// when walking backward/forward through a basic block. 49 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 LivePhysRegs() = default; 56 57 /// Constructs and initializes an empty set. 58 LivePhysRegs(const TargetRegisterInfo &TRI) : TRI(&TRI) { 59 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 this->TRI = &TRI; 68 LiveRegs.clear(); 69 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 void addReg(unsigned Reg) { 80 assert(TRI && "LivePhysRegs is not initialized."); 81 assert(Reg <= TRI->getNumRegs() && "Expected a physical register."); 82 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 83 SubRegs.isValid(); ++SubRegs) 84 LiveRegs.insert(*SubRegs); 85 } 86 87 /// \brief Removes a physical register, all its sub-registers, and all its 88 /// super-registers from the set. 89 void removeReg(unsigned Reg) { 90 assert(TRI && "LivePhysRegs is not initialized."); 91 assert(Reg <= TRI->getNumRegs() && "Expected a physical register."); 92 for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R) 93 LiveRegs.erase(*R); 94 } 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 /// \brief 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 /// \brief 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 /// \brief 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 } // end namespace llvm 189 190 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H 191
