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