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"
24using 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.
31void 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.
45void 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.
58void 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.
68void 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.
80void 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.
118void 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)
136LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
137  dbgs() << "  " << *this;
138}
139#endif
140
141bool 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.
155void 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.
174static 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
181void 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
209void 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
232void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
233  const MachineFunction &MF = *MBB.getParent();
234  addPristines(MF);
235  addLiveOutsNoPristines(MBB);
236}
237
238void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
239  const MachineFunction &MF = *MBB.getParent();
240  addPristines(MF);
241  addBlockLiveIns(MBB);
242}
243
244void LivePhysRegs::addLiveInsNoPristines(const MachineBasicBlock &MBB) {
245  addBlockLiveIns(MBB);
246}
247
248void 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
259void 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
276void 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
336void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
337                                MachineBasicBlock &MBB) {
338  computeLiveIns(LiveRegs, MBB);
339  addLiveIns(MBB, LiveRegs);
340}
341