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 }
 155
 156 #endif