include/llvm/CodeGen/LiveRegUnits.h

   1 //===-- llvm/CodeGen/LiveRegUnits.h - Live register unit 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 a Set of live register units. This can be used for ad
  11 // hoc liveness tracking after register allocation. You can start with the
  12 // live-ins/live-outs at the beginning/end of a block and update the information
  13 // while walking the instructions inside the block.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_CODEGEN_LIVEREGUNITS_H
  18 #define LLVM_CODEGEN_LIVEREGUNITS_H
  19
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/MC/MCRegisterInfo.h"
  23 #include <cassert>
  24
  25 namespace llvm {
  26
  27 class MachineInstr;
  28
  29 /// A set of live register units with functions to track liveness when walking
  30 /// backward/forward through a basic block.
  31 class LiveRegUnits {
  32   SmallSet<unsigned, 32> LiveUnits;
  33
  34 public:
  35   /// Constructs a new empty LiveRegUnits set.
  36   LiveRegUnits() {
  37   }
  38
  39   /// Constructs a new LiveRegUnits set by copying @p Other.
  40   LiveRegUnits(const LiveRegUnits &Other)
  41     : LiveUnits(Other.LiveUnits) {
  42   }
  43
  44   /// Adds a register to the set.
  45   void addReg(unsigned Reg, const MCRegisterInfo &MCRI) {
  46     for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits)
  47       LiveUnits.insert(*RUnits);
  48   }
  49
  50   /// Removes a register from the set.
  51   void removeReg(unsigned Reg, const MCRegisterInfo &MCRI) {
  52     for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits)
  53       LiveUnits.erase(*RUnits);
  54   }
  55
  56   /// \brief Removes registers clobbered by the regmask operand @p Op.
  57   /// Note that we assume the high bits of a physical super register are not
  58   /// preserved unless the instruction has an implicit-use operand reading
  59   /// the super-register or a register unit for the upper bits is available.
  60   void removeRegsInMask(const MachineOperand &Op,
  61                         const MCRegisterInfo &MCRI) {
  62     const uint32_t *Mask = Op.getRegMask();
  63     unsigned Bit = 0;
  64     for (unsigned R = 0; R < MCRI.getNumRegs(); ++R) {
  65       if ((*Mask & (1u << Bit)) == 0)
  66         removeReg(R, MCRI);
  67       ++Bit;
  68       if (Bit >= 32) {
  69         Bit = 0;
  70         ++Mask;
  71       }
  72     }
  73   }
  74
  75   /// Returns true if register @p Reg (or one of its super register) is
  76   /// contained in the set.
  77   bool contains(unsigned Reg, const MCRegisterInfo &MCRI) const {
  78     for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits) {
  79       if (LiveUnits.count(*RUnits))
  80         return true;
  81     }
  82     return false;
  83   }
  84
  85   /// Simulates liveness when stepping backwards over an instruction(bundle):
  86   /// Defs are removed from the set, uses added.
  87   void stepBackward(const MachineInstr &MI, const MCRegisterInfo &MCRI) {
  88     // Remove defined registers and regmask kills from the set.
  89     for (ConstMIBundleOperands O(&MI); O.isValid(); ++O) {
  90       if (O->isReg()) {
  91         if (!O->isDef())
  92           continue;
  93         unsigned Reg = O->getReg();
  94         if (Reg == 0)
  95           continue;
  96         removeReg(Reg, MCRI);
  97       } else if (O->isRegMask()) {
  98         removeRegsInMask(*O, MCRI);
  99       }
 100     }
 101     // Add uses to the set.
 102     for (ConstMIBundleOperands O(&MI); O.isValid(); ++O) {
 103       if (!O->isReg() || !O->readsReg() || O->isUndef())
 104         continue;
 105       unsigned Reg = O->getReg();
 106       if (Reg == 0)
 107         continue;
 108       addReg(Reg, MCRI);
 109     }
 110   }
 111
 112   /// \brief Simulates liveness when stepping forward over an
 113   /// instruction(bundle).
 114   ///
 115   /// Uses with kill flag get removed from the set, defs added. If possible
 116   /// use StepBackward() instead of this function because some kill flags may
 117   /// be missing.
 118   void stepForward(const MachineInstr &MI, const MCRegisterInfo &MCRI) {
 119     SmallVector<unsigned, 4> Defs;
 120     // Remove killed registers from the set.
 121     for (ConstMIBundleOperands O(&MI); O.isValid(); ++O) {
 122       if (O->isReg()) {
 123         unsigned Reg = O->getReg();
 124         if (Reg == 0)
 125           continue;
 126         if (O->isDef()) {
 127           if (!O->isDead())
 128             Defs.push_back(Reg);
 129         } else {
 130           if (!O->isKill())
 131             continue;
 132           assert(O->isUse());
 133           removeReg(Reg, MCRI);
 134         }
 135       } else if (O->isRegMask()) {
 136         removeRegsInMask(*O, MCRI);
 137       }
 138     }
 139     // Add defs to the set.
 140     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
 141       addReg(Defs[i], MCRI);
 142     }
 143   }
 144
 145   /// Adds all registers in the live-in list of block @p BB.
 146   void addLiveIns(const MachineBasicBlock &BB, const MCRegisterInfo &MCRI) {
 147     for (MachineBasicBlock::livein_iterator L = BB.livein_begin(),
 148          LE = BB.livein_end(); L != LE; ++L) {
 149       addReg(*L, MCRI);
 150     }
 151   }
 152 };
 153
 154 } // namespace llvm
 155
 156 #endif