136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- llvm/CodeGen/LivePhysRegs.h - Live Physical Register Set -*- C++ -*-===// 236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The LLVM Compiler Infrastructure 436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file is distributed under the University of Illinois Open Source 636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// License. See LICENSE.TXT for details. 736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file implements the LivePhysRegs utility for tracking liveness of 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// physical registers. This can be used for ad-hoc liveness tracking after 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// register allocation. You can start with the live-ins/live-outs at the 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// beginning/end of a block and update the information while walking the 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// instructions inside the block. This implementation tracks the liveness on a 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// sub-register granularity. 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// We assume that the high bits of a physical super-register are not preserved 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// unless the instruction has an implicit-use operand reading the super- 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// register. 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// X86 Example: 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// %YMM0<def> = ... 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// %XMM0<def> = ... (Kills %XMM0, all %XMM0s sub-registers, and %YMM0) 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// %YMM0<def> = ... 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// %XMM0<def> = ..., %YMM0<imp-use> (%YMM0 and all its sub-registers are alive) 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef LLVM_CODEGEN_LIVE_PHYS_REGS_H 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_CODEGEN_LIVE_PHYS_REGS_H 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SparseSet.h" 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/CodeGen/MachineBasicBlock.h" 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Target/TargetRegisterInfo.h" 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include <cassert> 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace llvm { 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass MachineInstr; 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief A set of live physical registers with functions to track liveness 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// when walking backward/forward through a basic block. 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass LivePhysRegs { 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const TargetRegisterInfo *TRI; 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SparseSet<unsigned> LiveRegs; 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LivePhysRegs(const LivePhysRegs&) LLVM_DELETED_FUNCTION; 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LivePhysRegs &operator=(const LivePhysRegs&) LLVM_DELETED_FUNCTION; 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Constructs a new empty LivePhysRegs set. 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LivePhysRegs() : TRI(nullptr), LiveRegs() {} 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Constructs and initialize an empty LivePhysRegs set. 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LivePhysRegs(const TargetRegisterInfo *TRI) : TRI(TRI) { 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(TRI && "Invalid TargetRegisterInfo pointer."); 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveRegs.setUniverse(TRI->getNumRegs()); 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Clear and initialize the LivePhysRegs set. 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void init(const TargetRegisterInfo *_TRI) { 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(_TRI && "Invalid TargetRegisterInfo pointer."); 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TRI = _TRI; 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveRegs.clear(); 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveRegs.setUniverse(TRI->getNumRegs()); 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Clears the LivePhysRegs set. 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void clear() { LiveRegs.clear(); } 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Returns true if the set is empty. 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool empty() const { return LiveRegs.empty(); } 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Adds a physical register and all its sub-registers to the set. 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void addReg(unsigned Reg) { 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(TRI && "LivePhysRegs is not initialized."); 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Reg <= TRI->getNumRegs() && "Expected a physical register."); 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SubRegs.isValid(); ++SubRegs) 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveRegs.insert(*SubRegs); 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Removes a physical register, all its sub-registers, and all its 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// super-registers from the set. 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void removeReg(unsigned Reg) { 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(TRI && "LivePhysRegs is not initialized."); 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(Reg <= TRI->getNumRegs() && "Expected a physical register."); 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SubRegs.isValid(); ++SubRegs) 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveRegs.erase(*SubRegs); 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MCSuperRegIterator SuperRegs(Reg, TRI, /*IncludeSelf=*/false); 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SuperRegs.isValid(); ++SuperRegs) 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LiveRegs.erase(*SuperRegs); 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Removes physical registers clobbered by the regmask operand @p MO. 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void removeRegsInMask(const MachineOperand &MO); 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Returns true if register @p Reg is contained in the set. This also 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// works if only the super register of @p Reg has been defined, because we 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// always add also all sub-registers to the set. 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool contains(unsigned Reg) const { return LiveRegs.count(Reg); } 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Simulates liveness when stepping backwards over an 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// instruction(bundle): Remove Defs, add uses. This is the recommended way of 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// calculating liveness. 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void stepBackward(const MachineInstr &MI); 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Simulates liveness when stepping forward over an 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// instruction(bundle): Remove killed-uses, add defs. This is the not 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// recommended way, because it depends on accurate kill flags. If possible 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// use stepBackwards() instead of this function. 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void stepForward(const MachineInstr &MI); 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Adds all live-in registers of basic block @p MBB. 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void addLiveIns(const MachineBasicBlock *MBB) { 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LE = MBB->livein_end(); LI != LE; ++LI) 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addReg(*LI); 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Adds all live-out registers of basic block @p MBB. 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void addLiveOuts(const MachineBasicBlock *MBB) { 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SE = MBB->succ_end(); SI != SE; ++SI) 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addLiveIns(*SI); 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef SparseSet<unsigned>::const_iterator const_iterator; 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const_iterator begin() const { return LiveRegs.begin(); } 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const_iterator end() const { return LiveRegs.end(); } 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Prints the currently live registers to @p OS. 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void print(raw_ostream &OS) const; 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Dumps the currently live registers to the debug output. 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void dump() const; 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 13836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesinline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) { 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LR.print(OS); 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return OS; 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} // namespace llvm 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif // LLVM_CODEGEN_LIVE_PHYS_REGS_H 147