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