aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm14/lib/CodeGen/LivePhysRegs.cpp
blob: d4848f16dcf2dfb88687e94441aeb8d23fabc8a7 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
//===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the LivePhysRegs utility for tracking liveness of
// physical registers across machine instructions in forward or backward order.
// A more detailed description can be found in the corresponding header file.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/LiveRegUnits.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBundle.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;


/// Remove all registers from the set that get clobbered by the register
/// mask.
/// The clobbers set will be the list of live registers clobbered
/// by the regmask.
void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
    SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers) {
  RegisterSet::iterator LRI = LiveRegs.begin();
  while (LRI != LiveRegs.end()) {
    if (MO.clobbersPhysReg(*LRI)) {
      if (Clobbers)
        Clobbers->push_back(std::make_pair(*LRI, &MO));
      LRI = LiveRegs.erase(LRI);
    } else
      ++LRI;
  }
}

/// Remove defined registers and regmask kills from the set.
void LivePhysRegs::removeDefs(const MachineInstr &MI) {
  for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
    if (MOP.isRegMask()) {
      removeRegsInMask(MOP);
      continue;
    }

    if (MOP.isDef())
      removeReg(MOP.getReg());
  }
}

/// Add uses to the set.
void LivePhysRegs::addUses(const MachineInstr &MI) {
  for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
    if (!MOP.isReg() || !MOP.readsReg())
      continue;
    addReg(MOP.getReg());
  }
}

/// Simulates liveness when stepping backwards over an instruction(bundle):
/// Remove Defs, add uses. This is the recommended way of calculating liveness.
void LivePhysRegs::stepBackward(const MachineInstr &MI) {
  // Remove defined registers and regmask kills from the set.
  removeDefs(MI);

  // Add uses to the set.
  addUses(MI);
}

/// Simulates liveness when stepping forward over an instruction(bundle): Remove
/// killed-uses, add defs. This is the not recommended way, because it depends
/// on accurate kill flags. If possible use stepBackward() instead of this
/// function.
void LivePhysRegs::stepForward(const MachineInstr &MI,
    SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers) {
  // Remove killed registers from the set.
  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
    if (O->isReg()) {
      if (O->isDebug())
        continue;
      Register Reg = O->getReg();
      if (!Reg.isPhysical())
        continue;
      if (O->isDef()) {
        // Note, dead defs are still recorded.  The caller should decide how to
        // handle them.
        Clobbers.push_back(std::make_pair(Reg, &*O));
      } else {
        assert(O->isUse());
        if (O->isKill())
          removeReg(Reg);
      }
    } else if (O->isRegMask()) {
      removeRegsInMask(*O, &Clobbers);
    }
  }

  // Add defs to the set.
  for (auto Reg : Clobbers) {
    // Skip dead defs and registers clobbered by regmasks. They shouldn't
    // be added to the set.
    if (Reg.second->isReg() && Reg.second->isDead())
      continue;
    if (Reg.second->isRegMask() &&
        MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
      continue;
    addReg(Reg.first);
  }
}

/// Print the currently live registers to OS.
void LivePhysRegs::print(raw_ostream &OS) const {
  OS << "Live Registers:";
  if (!TRI) {
    OS << " (uninitialized)\n";
    return;
  }

  if (empty()) {
    OS << " (empty)\n";
    return;
  }

  for (MCPhysReg R : *this)
    OS << " " << printReg(R, TRI);
  OS << "\n";
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
  dbgs() << "  " << *this;
}
#endif

bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
                             MCPhysReg Reg) const {
  if (LiveRegs.count(Reg))
    return false;
  if (MRI.isReserved(Reg))
    return false;
  for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
    if (LiveRegs.count(*R))
      return false;
  }
  return true;
}

/// Add live-in registers of basic block \p MBB to \p LiveRegs.
void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
  for (const auto &LI : MBB.liveins()) {
    MCPhysReg Reg = LI.PhysReg;
    LaneBitmask Mask = LI.LaneMask;
    MCSubRegIndexIterator S(Reg, TRI);
    assert(Mask.any() && "Invalid livein mask");
    if (Mask.all() || !S.isValid()) {
      addReg(Reg);
      continue;
    }
    for (; S.isValid(); ++S) {
      unsigned SI = S.getSubRegIndex();
      if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
        addReg(S.getSubReg());
    }
  }
}

/// Adds all callee saved registers to \p LiveRegs.
static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
                               const MachineFunction &MF) {
  const MachineRegisterInfo &MRI = MF.getRegInfo();
  for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
    LiveRegs.addReg(*CSR);
}

void LivePhysRegs::addPristines(const MachineFunction &MF) {
  const MachineFrameInfo &MFI = MF.getFrameInfo();
  if (!MFI.isCalleeSavedInfoValid())
    return;
  /// This function will usually be called on an empty object, handle this
  /// as a special case.
  if (empty()) {
    /// Add all callee saved regs, then remove the ones that are saved and
    /// restored.
    addCalleeSavedRegs(*this, MF);
    /// Remove the ones that are not saved/restored; they are pristine.
    for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
      removeReg(Info.getReg());
    return;
  }
  /// If a callee-saved register that is not pristine is already present
  /// in the set, we should make sure that it stays in it. Precompute the
  /// set of pristine registers in a separate object.
  /// Add all callee saved regs, then remove the ones that are saved+restored.
  LivePhysRegs Pristine(*TRI);
  addCalleeSavedRegs(Pristine, MF);
  /// Remove the ones that are not saved/restored; they are pristine.
  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
    Pristine.removeReg(Info.getReg());
  for (MCPhysReg R : Pristine)
    addReg(R);
}

void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
  // To get the live-outs we simply merge the live-ins of all successors.
  for (const MachineBasicBlock *Succ : MBB.successors())
    addBlockLiveIns(*Succ);
  if (MBB.isReturnBlock()) {
    // Return blocks are a special case because we currently don't mark up
    // return instructions completely: specifically, there is no explicit
    // use for callee-saved registers. So we add all callee saved registers
    // that are saved and restored (somewhere). This does not include
    // callee saved registers that are unused and hence not saved and
    // restored; they are called pristine.
    // FIXME: PEI should add explicit markings to return instructions
    // instead of implicitly handling them here.
    const MachineFunction &MF = *MBB.getParent();
    const MachineFrameInfo &MFI = MF.getFrameInfo();
    if (MFI.isCalleeSavedInfoValid()) {
      for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
        if (Info.isRestored())
          addReg(Info.getReg());
    }
  }
}

void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
  const MachineFunction &MF = *MBB.getParent();
  addPristines(MF);
  addLiveOutsNoPristines(MBB);
}

void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
  const MachineFunction &MF = *MBB.getParent();
  addPristines(MF);
  addBlockLiveIns(MBB);
}

void LivePhysRegs::addLiveInsNoPristines(const MachineBasicBlock &MBB) {
  addBlockLiveIns(MBB);
}

void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
                          const MachineBasicBlock &MBB) {
  const MachineFunction &MF = *MBB.getParent();
  const MachineRegisterInfo &MRI = MF.getRegInfo();
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
  LiveRegs.init(TRI);
  LiveRegs.addLiveOutsNoPristines(MBB);
  for (const MachineInstr &MI : llvm::reverse(MBB))
    LiveRegs.stepBackward(MI);
}

void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
  assert(MBB.livein_empty() && "Expected empty live-in list");
  const MachineFunction &MF = *MBB.getParent();
  const MachineRegisterInfo &MRI = MF.getRegInfo();
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
  for (MCPhysReg Reg : LiveRegs) {
    if (MRI.isReserved(Reg))
      continue;
    // Skip the register if we are about to add one of its super registers.
    bool ContainsSuperReg = false;
    for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
      if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
        ContainsSuperReg = true;
        break;
      }
    }
    if (ContainsSuperReg)
      continue;
    MBB.addLiveIn(Reg);
  }
}

void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
  const MachineFunction &MF = *MBB.getParent();
  const MachineRegisterInfo &MRI = MF.getRegInfo();
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
  const MachineFrameInfo &MFI = MF.getFrameInfo();

  // We walk through the block backwards and start with the live outs.
  LivePhysRegs LiveRegs;
  LiveRegs.init(TRI);
  LiveRegs.addLiveOutsNoPristines(MBB);

  for (MachineInstr &MI : llvm::reverse(MBB)) {
    // Recompute dead flags.
    for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
      if (!MO->isReg() || !MO->isDef() || MO->isDebug())
        continue;

      Register Reg = MO->getReg();
      if (Reg == 0)
        continue;
      assert(Reg.isPhysical());

      bool IsNotLive = LiveRegs.available(MRI, Reg);

      // Special-case return instructions for cases when a return is not
      // the last instruction in the block.
      if (MI.isReturn() && MFI.isCalleeSavedInfoValid()) {
        for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
          if (Info.getReg() == Reg) {
            IsNotLive = !Info.isRestored();
            break;
          }
        }
      }

      MO->setIsDead(IsNotLive);
    }

    // Step backward over defs.
    LiveRegs.removeDefs(MI);

    // Recompute kill flags.
    for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
      if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
        continue;

      Register Reg = MO->getReg();
      if (Reg == 0)
        continue;
      assert(Reg.isPhysical());

      bool IsNotLive = LiveRegs.available(MRI, Reg);
      MO->setIsKill(IsNotLive);
    }

    // Complete the stepbackward.
    LiveRegs.addUses(MI);
  }
}

void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
                                MachineBasicBlock &MBB) {
  computeLiveIns(LiveRegs, MBB);
  addLiveIns(MBB, LiveRegs);
}