Home | History | Annotate | Download | only in CodeGen 
      1 //===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
      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 across machine instructions in forward or backward order.
     12 // A more detailed description can be found in the corresponding header file.
     13 //
     14 //===----------------------------------------------------------------------===//
     15 
     16 #include "llvm/CodeGen/LivePhysRegs.h"
     17 #include "llvm/CodeGen/MachineFrameInfo.h"
     18 #include "llvm/CodeGen/MachineFunction.h"
     19 #include "llvm/CodeGen/MachineInstrBundle.h"
     20 #include "llvm/CodeGen/MachineRegisterInfo.h"
     21 #include "llvm/Support/Debug.h"
     22 #include "llvm/Support/raw_ostream.h"
     23 using namespace llvm;
     24 
     25 
     26 /// \brief Remove all registers from the set that get clobbered by the register
     27 /// mask.
     28 /// The clobbers set will be the list of live registers clobbered
     29 /// by the regmask.
     30 void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
     31         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers) {
     32   SparseSet<unsigned>::iterator LRI = LiveRegs.begin();
     33   while (LRI != LiveRegs.end()) {
     34     if (MO.clobbersPhysReg(*LRI)) {
     35       if (Clobbers)
     36         Clobbers->push_back(std::make_pair(*LRI, &MO));
     37       LRI = LiveRegs.erase(LRI);
     38     } else
     39       ++LRI;
     40   }
     41 }
     42 
     43 /// Simulates liveness when stepping backwards over an instruction(bundle):
     44 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
     45 void LivePhysRegs::stepBackward(const MachineInstr &MI) {
     46   // Remove defined registers and regmask kills from the set.
     47   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
     48     if (O->isReg()) {
     49       if (!O->isDef())
     50         continue;
     51       unsigned Reg = O->getReg();
     52       if (Reg == 0)
     53         continue;
     54       removeReg(Reg);
     55     } else if (O->isRegMask())
     56       removeRegsInMask(*O, nullptr);
     57   }
     58 
     59   // Add uses to the set.
     60   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
     61     if (!O->isReg() || !O->readsReg())
     62       continue;
     63     unsigned Reg = O->getReg();
     64     if (Reg == 0)
     65       continue;
     66     addReg(Reg);
     67   }
     68 }
     69 
     70 /// Simulates liveness when stepping forward over an instruction(bundle): Remove
     71 /// killed-uses, add defs. This is the not recommended way, because it depends
     72 /// on accurate kill flags. If possible use stepBackward() instead of this
     73 /// function.
     74 void LivePhysRegs::stepForward(const MachineInstr &MI,
     75         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
     76   // Remove killed registers from the set.
     77   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
     78     if (O->isReg()) {
     79       unsigned Reg = O->getReg();
     80       if (Reg == 0)
     81         continue;
     82       if (O->isDef()) {
     83         // Note, dead defs are still recorded.  The caller should decide how to
     84         // handle them.
     85         Clobbers.push_back(std::make_pair(Reg, &*O));
     86       } else {
     87         if (!O->isKill())
     88           continue;
     89         assert(O->isUse());
     90         removeReg(Reg);
     91       }
     92     } else if (O->isRegMask())
     93       removeRegsInMask(*O, &Clobbers);
     94   }
     95 
     96   // Add defs to the set.
     97   for (auto Reg : Clobbers) {
     98     // Skip dead defs.  They shouldn't be added to the set.
     99     if (Reg.second->isReg() && Reg.second->isDead())
    100       continue;
    101     addReg(Reg.first);
    102   }
    103 }
    104 
    105 /// Prin the currently live registers to OS.
    106 void LivePhysRegs::print(raw_ostream &OS) const {
    107   OS << "Live Registers:";
    108   if (!TRI) {
    109     OS << " (uninitialized)\n";
    110     return;
    111   }
    112 
    113   if (empty()) {
    114     OS << " (empty)\n";
    115     return;
    116   }
    117 
    118   for (const_iterator I = begin(), E = end(); I != E; ++I)
    119     OS << " " << PrintReg(*I, TRI);
    120   OS << "\n";
    121 }
    122 
    123 /// Dumps the currently live registers to the debug output.
    124 LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
    125 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    126   dbgs() << "  " << *this;
    127 #endif
    128 }
    129 
    130 bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
    131                              unsigned Reg) const {
    132   if (LiveRegs.count(Reg))
    133     return false;
    134   if (MRI.isReserved(Reg))
    135     return false;
    136   for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
    137     if (LiveRegs.count(*R))
    138       return false;
    139   }
    140   return true;
    141 }
    142 
    143 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
    144 static void addLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB) {
    145   for (const auto &LI : MBB.liveins())
    146     LiveRegs.addReg(LI.PhysReg);
    147 }
    148 
    149 /// Add pristine registers to the given \p LiveRegs. This function removes
    150 /// actually saved callee save registers when \p InPrologueEpilogue is false.
    151 static void addPristines(LivePhysRegs &LiveRegs, const MachineFunction &MF,
    152                          const MachineFrameInfo &MFI,
    153                          const TargetRegisterInfo &TRI) {
    154   for (const MCPhysReg *CSR = TRI.getCalleeSavedRegs(&MF); CSR && *CSR; ++CSR)
    155     LiveRegs.addReg(*CSR);
    156   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
    157     LiveRegs.removeReg(Info.getReg());
    158 }
    159 
    160 void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
    161   // To get the live-outs we simply merge the live-ins of all successors.
    162   for (const MachineBasicBlock *Succ : MBB.successors())
    163     ::addLiveIns(*this, *Succ);
    164 }
    165 
    166 void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
    167   const MachineFunction &MF = *MBB.getParent();
    168   const MachineFrameInfo &MFI = *MF.getFrameInfo();
    169   if (MFI.isCalleeSavedInfoValid()) {
    170     if (MBB.isReturnBlock()) {
    171       // The return block has no successors whose live-ins we could merge
    172       // below. So instead we add the callee saved registers manually.
    173       for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
    174         addReg(*I);
    175     } else {
    176       addPristines(*this, MF, MFI, *TRI);
    177     }
    178   }
    179 
    180   addLiveOutsNoPristines(MBB);
    181 }
    182 
    183 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
    184   const MachineFunction &MF = *MBB.getParent();
    185   const MachineFrameInfo &MFI = *MF.getFrameInfo();
    186   if (MFI.isCalleeSavedInfoValid())
    187     addPristines(*this, MF, MFI, *TRI);
    188   ::addLiveIns(*this, MBB);
    189 }
    190