contrib/llvm/include/llvm/CodeGen/LivePhysRegs.h

   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