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 /// \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   /// Simulates liveness when stepping backwards over an instruction(bundle).
 112   /// Remove Defs, add uses. This is the recommended way of calculating
 113   /// liveness.
 114   void stepBackward(const MachineInstr &MI);
 115
 116   /// Simulates liveness when stepping forward over an instruction(bundle).
 117   /// Remove killed-uses, add defs. This is the not recommended way, because it
 118   /// depends on accurate kill flags. If possible use stepBackward() instead of
 119   /// this function. The clobbers set will be the list of registers either
 120   /// defined or clobbered by a regmask.  The operand will identify whether this
 121   /// is a regmask or register operand.
 122   void stepForward(const MachineInstr &MI,
 123         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers);
 124
 125   /// Adds all live-in registers of basic block \p MBB.
 126   /// Live in registers are the registers in the blocks live-in list and the
 127   /// pristine registers.
 128   void addLiveIns(const MachineBasicBlock &MBB);
 129
 130   /// Adds all live-out registers of basic block \p MBB.
 131   /// Live out registers are the union of the live-in registers of the successor
 132   /// blocks and pristine registers. Live out registers of the end block are the
 133   /// callee saved registers.
 134   void addLiveOuts(const MachineBasicBlock &MBB);
 135
 136   /// Adds all live-out registers of basic block \p MBB but skips pristine
 137   /// registers.
 138   void addLiveOutsNoPristines(const MachineBasicBlock &MBB);
 139
 140   using const_iterator = SparseSet<unsigned>::const_iterator;
 141
 142   const_iterator begin() const { return LiveRegs.begin(); }
 143   const_iterator end() const { return LiveRegs.end(); }
 144
 145   /// Prints the currently live registers to \p OS.
 146   void print(raw_ostream &OS) const;
 147
 148   /// Dumps the currently live registers to the debug output.
 149   void dump() const;
 150
 151 private:
 152   /// \brief Adds live-in registers from basic block \p MBB, taking associated
 153   /// lane masks into consideration.
 154   void addBlockLiveIns(const MachineBasicBlock &MBB);
 155 };
 156
 157 inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
 158   LR.print(OS);
 159   return OS;
 160 }
 161
 162 /// \brief Computes the live-in list for \p MBB assuming all of its successors
 163 /// live-in lists are up-to-date. Uses the given LivePhysReg instance \p
 164 /// LiveRegs; This is just here to avoid repeated heap allocations when calling
 165 /// this multiple times in a pass.
 166 void computeLiveIns(LivePhysRegs &LiveRegs, const MachineRegisterInfo &MRI,
 167                     MachineBasicBlock &MBB);
 168
 169 } // end namespace llvm
 170
 171 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H