include/llvm/CodeGen/LivePhysRegs.h

   1 //===- llvm/CodeGen/LivePhysRegs.h - Live Physical Register Set -*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  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 = ...
  23 /// %xmm0 = ... (Kills %xmm0, all %xmm0s sub-registers, and %ymm0)
  24 ///
  25 /// %ymm0 = ...
  26 /// %xmm0 = ..., implicit %ymm0 (%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/CodeGen/TargetRegisterInfo.h"
  35 #include "llvm/MC/MCRegisterInfo.h"
  36 #include <cassert>
  37 #include <utility>
  38
  39 namespace llvm {
  40
  41 class MachineInstr;
  42 class MachineOperand;
  43 class MachineRegisterInfo;
  44 class raw_ostream;
  45
  46 /// A set of physical registers with utility functions to track liveness
  47 /// when walking backward/forward through a basic block.
  48 class LivePhysRegs {
  49   const TargetRegisterInfo *TRI = nullptr;
  50   using RegisterSet = SparseSet<MCPhysReg, identity<MCPhysReg>>;
  51   RegisterSet 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(MCPhysReg 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   /// Removes a physical register, all its sub-registers, and all its
  88   /// super-registers from the set.
  89   void removeReg(MCPhysReg 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<MCPhysReg, const MachineOperand*>> *Clobbers =
  99         nullptr);
 100
 101   /// 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(MCPhysReg 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, MCPhysReg 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<MCPhysReg, 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 = RegisterSet::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   /// 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 /// 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 /// Convenience function for recomputing live-in's for \p MBB.
 189 static inline void recomputeLiveIns(MachineBasicBlock &MBB) {
 190   LivePhysRegs LPR;
 191   MBB.clearLiveIns();
 192   computeAndAddLiveIns(LPR, MBB);
 193 }
 194
 195 } // end namespace llvm
 196
 197 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H