lib/CodeGen/LivePhysRegs.cpp

   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/Config/llvm-config.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 using namespace llvm;
  25
  26
  27 /// Remove all registers from the set that get clobbered by the register
  28 /// mask.
  29 /// The clobbers set will be the list of live registers clobbered
  30 /// by the regmask.
  31 void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
  32         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers) {
  33   SparseSet<unsigned>::iterator LRI = LiveRegs.begin();
  34   while (LRI != LiveRegs.end()) {
  35     if (MO.clobbersPhysReg(*LRI)) {
  36       if (Clobbers)
  37         Clobbers->push_back(std::make_pair(*LRI, &MO));
  38       LRI = LiveRegs.erase(LRI);
  39     } else
  40       ++LRI;
  41   }
  42 }
  43
  44 /// Remove defined registers and regmask kills from the set.
  45 void LivePhysRegs::removeDefs(const MachineInstr &MI) {
  46   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
  47     if (O->isReg()) {
  48       if (!O->isDef() || O->isDebug())
  49         continue;
  50       unsigned Reg = O->getReg();
  51       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
  52         continue;
  53       removeReg(Reg);
  54     } else if (O->isRegMask())
  55       removeRegsInMask(*O);
  56   }
  57 }
  58
  59 /// Add uses to the set.
  60 void LivePhysRegs::addUses(const MachineInstr &MI) {
  61   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
  62     if (!O->isReg() || !O->readsReg() || O->isDebug())
  63       continue;
  64     unsigned Reg = O->getReg();
  65     if (!TargetRegisterInfo::isPhysicalRegister(Reg))
  66       continue;
  67     addReg(Reg);
  68   }
  69 }
  70
  71 /// Simulates liveness when stepping backwards over an instruction(bundle):
  72 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
  73 void LivePhysRegs::stepBackward(const MachineInstr &MI) {
  74   // Remove defined registers and regmask kills from the set.
  75   removeDefs(MI);
  76
  77   // Add uses to the set.
  78   addUses(MI);
  79 }
  80
  81 /// Simulates liveness when stepping forward over an instruction(bundle): Remove
  82 /// killed-uses, add defs. This is the not recommended way, because it depends
  83 /// on accurate kill flags. If possible use stepBackward() instead of this
  84 /// function.
  85 void LivePhysRegs::stepForward(const MachineInstr &MI,
  86         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
  87   // Remove killed registers from the set.
  88   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
  89     if (O->isReg() && !O->isDebug()) {
  90       unsigned Reg = O->getReg();
  91       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
  92         continue;
  93       if (O->isDef()) {
  94         // Note, dead defs are still recorded.  The caller should decide how to
  95         // handle them.
  96         Clobbers.push_back(std::make_pair(Reg, &*O));
  97       } else {
  98         if (!O->isKill())
  99           continue;
 100         assert(O->isUse());
 101         removeReg(Reg);
 102       }
 103     } else if (O->isRegMask())
 104       removeRegsInMask(*O, &Clobbers);
 105   }
 106
 107   // Add defs to the set.
 108   for (auto Reg : Clobbers) {
 109     // Skip dead defs and registers clobbered by regmasks. They shouldn't
 110     // be added to the set.
 111     if (Reg.second->isReg() && Reg.second->isDead())
 112       continue;
 113     if (Reg.second->isRegMask() &&
 114         MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
 115       continue;
 116     addReg(Reg.first);
 117   }
 118 }
 119
 120 /// Prin the currently live registers to OS.
 121 void LivePhysRegs::print(raw_ostream &OS) const {
 122   OS << "Live Registers:";
 123   if (!TRI) {
 124     OS << " (uninitialized)\n";
 125     return;
 126   }
 127
 128   if (empty()) {
 129     OS << " (empty)\n";
 130     return;
 131   }
 132
 133   for (const_iterator I = begin(), E = end(); I != E; ++I)
 134     OS << " " << printReg(*I, TRI);
 135   OS << "\n";
 136 }
 137
 138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 139 LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
 140   dbgs() << "  " << *this;
 141 }
 142 #endif
 143
 144 bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
 145                              unsigned Reg) const {
 146   if (LiveRegs.count(Reg))
 147     return false;
 148   if (MRI.isReserved(Reg))
 149     return false;
 150   for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
 151     if (LiveRegs.count(*R))
 152       return false;
 153   }
 154   return true;
 155 }
 156
 157 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
 158 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
 159   for (const auto &LI : MBB.liveins()) {
 160     unsigned Reg = LI.PhysReg;
 161     LaneBitmask Mask = LI.LaneMask;
 162     MCSubRegIndexIterator S(Reg, TRI);
 163     assert(Mask.any() && "Invalid livein mask");
 164     if (Mask.all() || !S.isValid()) {
 165       addReg(Reg);
 166       continue;
 167     }
 168     for (; S.isValid(); ++S) {
 169       unsigned SI = S.getSubRegIndex();
 170       if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
 171         addReg(S.getSubReg());
 172     }
 173   }
 174 }
 175
 176 /// Adds all callee saved registers to \p LiveRegs.
 177 static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
 178                                const MachineFunction &MF) {
 179   const MachineRegisterInfo &MRI = MF.getRegInfo();
 180   for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
 181     LiveRegs.addReg(*CSR);
 182 }
 183
 184 void LivePhysRegs::addPristines(const MachineFunction &MF) {
 185   const MachineFrameInfo &MFI = MF.getFrameInfo();
 186   if (!MFI.isCalleeSavedInfoValid())
 187     return;
 188   /// This function will usually be called on an empty object, handle this
 189   /// as a special case.
 190   if (empty()) {
 191     /// Add all callee saved regs, then remove the ones that are saved and
 192     /// restored.
 193     addCalleeSavedRegs(*this, MF);
 194     /// Remove the ones that are not saved/restored; they are pristine.
 195     for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
 196       removeReg(Info.getReg());
 197     return;
 198   }
 199   /// If a callee-saved register that is not pristine is already present
 200   /// in the set, we should make sure that it stays in it. Precompute the
 201   /// set of pristine registers in a separate object.
 202   /// Add all callee saved regs, then remove the ones that are saved+restored.
 203   LivePhysRegs Pristine(*TRI);
 204   addCalleeSavedRegs(Pristine, MF);
 205   /// Remove the ones that are not saved/restored; they are pristine.
 206   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
 207     Pristine.removeReg(Info.getReg());
 208   for (MCPhysReg R : Pristine)
 209     addReg(R);
 210 }
 211
 212 void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
 213   // To get the live-outs we simply merge the live-ins of all successors.
 214   for (const MachineBasicBlock *Succ : MBB.successors())
 215     addBlockLiveIns(*Succ);
 216   if (MBB.isReturnBlock()) {
 217     // Return blocks are a special case because we currently don't mark up
 218     // return instructions completely: specifically, there is no explicit
 219     // use for callee-saved registers. So we add all callee saved registers
 220     // that are saved and restored (somewhere). This does not include
 221     // callee saved registers that are unused and hence not saved and
 222     // restored; they are called pristine.
 223     // FIXME: PEI should add explicit markings to return instructions
 224     // instead of implicitly handling them here.
 225     const MachineFunction &MF = *MBB.getParent();
 226     const MachineFrameInfo &MFI = MF.getFrameInfo();
 227     if (MFI.isCalleeSavedInfoValid()) {
 228       for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
 229         if (Info.isRestored())
 230           addReg(Info.getReg());
 231     }
 232   }
 233 }
 234
 235 void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
 236   const MachineFunction &MF = *MBB.getParent();
 237   addPristines(MF);
 238   addLiveOutsNoPristines(MBB);
 239 }
 240
 241 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
 242   const MachineFunction &MF = *MBB.getParent();
 243   addPristines(MF);
 244   addBlockLiveIns(MBB);
 245 }
 246
 247 void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
 248                           const MachineBasicBlock &MBB) {
 249   const MachineFunction &MF = *MBB.getParent();
 250   const MachineRegisterInfo &MRI = MF.getRegInfo();
 251   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 252   LiveRegs.init(TRI);
 253   LiveRegs.addLiveOutsNoPristines(MBB);
 254   for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
 255     LiveRegs.stepBackward(MI);
 256 }
 257
 258 void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
 259   assert(MBB.livein_empty() && "Expected empty live-in list");
 260   const MachineFunction &MF = *MBB.getParent();
 261   const MachineRegisterInfo &MRI = MF.getRegInfo();
 262   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 263   for (MCPhysReg Reg : LiveRegs) {
 264     if (MRI.isReserved(Reg))
 265       continue;
 266     // Skip the register if we are about to add one of its super registers.
 267     bool ContainsSuperReg = false;
 268     for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
 269       if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
 270         ContainsSuperReg = true;
 271         break;
 272       }
 273     }
 274     if (ContainsSuperReg)
 275       continue;
 276     MBB.addLiveIn(Reg);
 277   }
 278 }
 279
 280 void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
 281   const MachineFunction &MF = *MBB.getParent();
 282   const MachineRegisterInfo &MRI = MF.getRegInfo();
 283   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 284
 285   // We walk through the block backwards and start with the live outs.
 286   LivePhysRegs LiveRegs;
 287   LiveRegs.init(TRI);
 288   LiveRegs.addLiveOutsNoPristines(MBB);
 289
 290   for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
 291     // Recompute dead flags.
 292     for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
 293       if (!MO->isReg() || !MO->isDef() || MO->isDebug())
 294         continue;
 295
 296       unsigned Reg = MO->getReg();
 297       if (Reg == 0)
 298         continue;
 299       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
 300
 301       bool IsNotLive = LiveRegs.available(MRI, Reg);
 302       MO->setIsDead(IsNotLive);
 303     }
 304
 305     // Step backward over defs.
 306     LiveRegs.removeDefs(MI);
 307
 308     // Recompute kill flags.
 309     for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
 310       if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
 311         continue;
 312
 313       unsigned Reg = MO->getReg();
 314       if (Reg == 0)
 315         continue;
 316       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
 317
 318       bool IsNotLive = LiveRegs.available(MRI, Reg);
 319       MO->setIsKill(IsNotLive);
 320     }
 321
 322     // Complete the stepbackward.
 323     LiveRegs.addUses(MI);
 324   }
 325 }
 326
 327 void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
 328                                 MachineBasicBlock &MBB) {
 329   computeLiveIns(LiveRegs, MBB);
 330   addLiveIns(MBB, LiveRegs);
 331 }