llvm/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/LiveRegUnits.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<MCPhysReg, const MachineOperand*>> *Clobbers) {
  33   RegisterSet::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 (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
  47     if (MOP.isRegMask()) {
  48       removeRegsInMask(MOP);
  49       continue;
  50     }
  51
  52     if (MOP.isDef())
  53       removeReg(MOP.getReg());
  54   }
  55 }
  56
  57 /// Add uses to the set.
  58 void LivePhysRegs::addUses(const MachineInstr &MI) {
  59   for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
  60     if (!MOP.isReg() || !MOP.readsReg())
  61       continue;
  62     addReg(MOP.getReg());
  63   }
  64 }
  65
  66 /// Simulates liveness when stepping backwards over an instruction(bundle):
  67 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
  68 void LivePhysRegs::stepBackward(const MachineInstr &MI) {
  69   // Remove defined registers and regmask kills from the set.
  70   removeDefs(MI);
  71
  72   // Add uses to the set.
  73   addUses(MI);
  74 }
  75
  76 /// Simulates liveness when stepping forward over an instruction(bundle): Remove
  77 /// killed-uses, add defs. This is the not recommended way, because it depends
  78 /// on accurate kill flags. If possible use stepBackward() instead of this
  79 /// function.
  80 void LivePhysRegs::stepForward(const MachineInstr &MI,
  81     SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers) {
  82   // Remove killed registers from the set.
  83   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
  84     if (O->isReg() && !O->isDebug()) {
  85       Register Reg = O->getReg();
  86       if (!Register::isPhysicalRegister(Reg))
  87         continue;
  88       if (O->isDef()) {
  89         // Note, dead defs are still recorded.  The caller should decide how to
  90         // handle them.
  91         Clobbers.push_back(std::make_pair(Reg, &*O));
  92       } else {
  93         if (!O->isKill())
  94           continue;
  95         assert(O->isUse());
  96         removeReg(Reg);
  97       }
  98     } else if (O->isRegMask())
  99       removeRegsInMask(*O, &Clobbers);
 100   }
 101
 102   // Add defs to the set.
 103   for (auto Reg : Clobbers) {
 104     // Skip dead defs and registers clobbered by regmasks. They shouldn't
 105     // be added to the set.
 106     if (Reg.second->isReg() && Reg.second->isDead())
 107       continue;
 108     if (Reg.second->isRegMask() &&
 109         MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
 110       continue;
 111     addReg(Reg.first);
 112   }
 113 }
 114
 115 /// Print the currently live registers to OS.
 116 void LivePhysRegs::print(raw_ostream &OS) const {
 117   OS << "Live Registers:";
 118   if (!TRI) {
 119     OS << " (uninitialized)\n";
 120     return;
 121   }
 122
 123   if (empty()) {
 124     OS << " (empty)\n";
 125     return;
 126   }
 127
 128   for (MCPhysReg R : *this)
 129     OS << " " << printReg(R, TRI);
 130   OS << "\n";
 131 }
 132
 133 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 134 LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
 135   dbgs() << "  " << *this;
 136 }
 137 #endif
 138
 139 bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
 140                              MCPhysReg Reg) const {
 141   if (LiveRegs.count(Reg))
 142     return false;
 143   if (MRI.isReserved(Reg))
 144     return false;
 145   for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
 146     if (LiveRegs.count(*R))
 147       return false;
 148   }
 149   return true;
 150 }
 151
 152 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
 153 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
 154   for (const auto &LI : MBB.liveins()) {
 155     MCPhysReg Reg = LI.PhysReg;
 156     LaneBitmask Mask = LI.LaneMask;
 157     MCSubRegIndexIterator S(Reg, TRI);
 158     assert(Mask.any() && "Invalid livein mask");
 159     if (Mask.all() || !S.isValid()) {
 160       addReg(Reg);
 161       continue;
 162     }
 163     for (; S.isValid(); ++S) {
 164       unsigned SI = S.getSubRegIndex();
 165       if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
 166         addReg(S.getSubReg());
 167     }
 168   }
 169 }
 170
 171 /// Adds all callee saved registers to \p LiveRegs.
 172 static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
 173                                const MachineFunction &MF) {
 174   const MachineRegisterInfo &MRI = MF.getRegInfo();
 175   for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
 176     LiveRegs.addReg(*CSR);
 177 }
 178
 179 void LivePhysRegs::addPristines(const MachineFunction &MF) {
 180   const MachineFrameInfo &MFI = MF.getFrameInfo();
 181   if (!MFI.isCalleeSavedInfoValid())
 182     return;
 183   /// This function will usually be called on an empty object, handle this
 184   /// as a special case.
 185   if (empty()) {
 186     /// Add all callee saved regs, then remove the ones that are saved and
 187     /// restored.
 188     addCalleeSavedRegs(*this, MF);
 189     /// Remove the ones that are not saved/restored; they are pristine.
 190     for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
 191       removeReg(Info.getReg());
 192     return;
 193   }
 194   /// If a callee-saved register that is not pristine is already present
 195   /// in the set, we should make sure that it stays in it. Precompute the
 196   /// set of pristine registers in a separate object.
 197   /// Add all callee saved regs, then remove the ones that are saved+restored.
 198   LivePhysRegs Pristine(*TRI);
 199   addCalleeSavedRegs(Pristine, MF);
 200   /// Remove the ones that are not saved/restored; they are pristine.
 201   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
 202     Pristine.removeReg(Info.getReg());
 203   for (MCPhysReg R : Pristine)
 204     addReg(R);
 205 }
 206
 207 void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
 208   // To get the live-outs we simply merge the live-ins of all successors.
 209   for (const MachineBasicBlock *Succ : MBB.successors())
 210     addBlockLiveIns(*Succ);
 211   if (MBB.isReturnBlock()) {
 212     // Return blocks are a special case because we currently don't mark up
 213     // return instructions completely: specifically, there is no explicit
 214     // use for callee-saved registers. So we add all callee saved registers
 215     // that are saved and restored (somewhere). This does not include
 216     // callee saved registers that are unused and hence not saved and
 217     // restored; they are called pristine.
 218     // FIXME: PEI should add explicit markings to return instructions
 219     // instead of implicitly handling them here.
 220     const MachineFunction &MF = *MBB.getParent();
 221     const MachineFrameInfo &MFI = MF.getFrameInfo();
 222     if (MFI.isCalleeSavedInfoValid()) {
 223       for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
 224         if (Info.isRestored())
 225           addReg(Info.getReg());
 226     }
 227   }
 228 }
 229
 230 void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
 231   const MachineFunction &MF = *MBB.getParent();
 232   addPristines(MF);
 233   addLiveOutsNoPristines(MBB);
 234 }
 235
 236 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
 237   const MachineFunction &MF = *MBB.getParent();
 238   addPristines(MF);
 239   addBlockLiveIns(MBB);
 240 }
 241
 242 void LivePhysRegs::addLiveInsNoPristines(const MachineBasicBlock &MBB) {
 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   const MachineFrameInfo &MFI = MF.getFrameInfo();
 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       Register Reg = MO->getReg();
 297       if (Reg == 0)
 298         continue;
 299       assert(Register::isPhysicalRegister(Reg));
 300
 301       bool IsNotLive = LiveRegs.available(MRI, Reg);
 302
 303       // Special-case return instructions for cases when a return is not
 304       // the last instruction in the block.
 305       if (MI.isReturn() && MFI.isCalleeSavedInfoValid()) {
 306         for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
 307           if (Info.getReg() == Reg) {
 308             IsNotLive = !Info.isRestored();
 309             break;
 310           }
 311         }
 312       }
 313
 314       MO->setIsDead(IsNotLive);
 315     }
 316
 317     // Step backward over defs.
 318     LiveRegs.removeDefs(MI);
 319
 320     // Recompute kill flags.
 321     for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
 322       if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
 323         continue;
 324
 325       Register Reg = MO->getReg();
 326       if (Reg == 0)
 327         continue;
 328       assert(Register::isPhysicalRegister(Reg));
 329
 330       bool IsNotLive = LiveRegs.available(MRI, Reg);
 331       MO->setIsKill(IsNotLive);
 332     }
 333
 334     // Complete the stepbackward.
 335     LiveRegs.addUses(MI);
 336   }
 337 }
 338
 339 void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
 340                                 MachineBasicBlock &MBB) {
 341   computeLiveIns(LiveRegs, MBB);
 342   addLiveIns(MBB, LiveRegs);
 343 }