lib/CodeGen/LivePhysRegs.cpp

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