1//===-- lib/CodeGen/MachineInstrBundle.cpp --------------------------------===//
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#include "llvm/CodeGen/MachineInstrBundle.h"
10#include "llvm/ADT/SmallSet.h"
11#include "llvm/ADT/SmallVector.h"
12#include "llvm/CodeGen/MachineFunctionPass.h"
13#include "llvm/CodeGen/MachineInstrBuilder.h"
14#include "llvm/CodeGen/Passes.h"
15#include "llvm/CodeGen/TargetInstrInfo.h"
16#include "llvm/CodeGen/TargetRegisterInfo.h"
17#include "llvm/CodeGen/TargetSubtargetInfo.h"
18#include "llvm/InitializePasses.h"
19#include "llvm/Target/TargetMachine.h"
20#include <utility>
21using namespace llvm;
22
23namespace {
24  class UnpackMachineBundles : public MachineFunctionPass {
25  public:
26    static char ID; // Pass identification
27    UnpackMachineBundles(
28        std::function<bool(const MachineFunction &)> Ftor = nullptr)
29        : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {
30      initializeUnpackMachineBundlesPass(*PassRegistry::getPassRegistry());
31    }
32
33    bool runOnMachineFunction(MachineFunction &MF) override;
34
35  private:
36    std::function<bool(const MachineFunction &)> PredicateFtor;
37  };
38} // end anonymous namespace
39
40char UnpackMachineBundles::ID = 0;
41char &llvm::UnpackMachineBundlesID = UnpackMachineBundles::ID;
42INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles",
43                "Unpack machine instruction bundles", false, false)
44
45bool UnpackMachineBundles::runOnMachineFunction(MachineFunction &MF) {
46  if (PredicateFtor && !PredicateFtor(MF))
47    return false;
48
49  bool Changed = false;
50  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
51    MachineBasicBlock *MBB = &*I;
52
53    for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
54           MIE = MBB->instr_end(); MII != MIE; ) {
55      MachineInstr *MI = &*MII;
56
57      // Remove BUNDLE instruction and the InsideBundle flags from bundled
58      // instructions.
59      if (MI->isBundle()) {
60        while (++MII != MIE && MII->isBundledWithPred()) {
61          MII->unbundleFromPred();
62          for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
63            MachineOperand &MO = MII->getOperand(i);
64            if (MO.isReg() && MO.isInternalRead())
65              MO.setIsInternalRead(false);
66          }
67        }
68        MI->eraseFromParent();
69
70        Changed = true;
71        continue;
72      }
73
74      ++MII;
75    }
76  }
77
78  return Changed;
79}
80
81FunctionPass *
82llvm::createUnpackMachineBundles(
83    std::function<bool(const MachineFunction &)> Ftor) {
84  return new UnpackMachineBundles(std::move(Ftor));
85}
86
87namespace {
88  class FinalizeMachineBundles : public MachineFunctionPass {
89  public:
90    static char ID; // Pass identification
91    FinalizeMachineBundles() : MachineFunctionPass(ID) {
92      initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry());
93    }
94
95    bool runOnMachineFunction(MachineFunction &MF) override;
96  };
97} // end anonymous namespace
98
99char FinalizeMachineBundles::ID = 0;
100char &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID;
101INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles",
102                "Finalize machine instruction bundles", false, false)
103
104bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) {
105  return llvm::finalizeBundles(MF);
106}
107
108/// Return the first found DebugLoc that has a DILocation, given a range of
109/// instructions. The search range is from FirstMI to LastMI (exclusive). If no
110/// DILocation is found, then an empty location is returned.
111static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI,
112                            MachineBasicBlock::instr_iterator LastMI) {
113  for (auto MII = FirstMI; MII != LastMI; ++MII)
114    if (MII->getDebugLoc().get())
115      return MII->getDebugLoc();
116  return DebugLoc();
117}
118
119/// finalizeBundle - Finalize a machine instruction bundle which includes
120/// a sequence of instructions starting from FirstMI to LastMI (exclusive).
121/// This routine adds a BUNDLE instruction to represent the bundle, it adds
122/// IsInternalRead markers to MachineOperands which are defined inside the
123/// bundle, and it copies externally visible defs and uses to the BUNDLE
124/// instruction.
125void llvm::finalizeBundle(MachineBasicBlock &MBB,
126                          MachineBasicBlock::instr_iterator FirstMI,
127                          MachineBasicBlock::instr_iterator LastMI) {
128  assert(FirstMI != LastMI && "Empty bundle?");
129  MIBundleBuilder Bundle(MBB, FirstMI, LastMI);
130
131  MachineFunction &MF = *MBB.getParent();
132  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
133  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
134
135  MachineInstrBuilder MIB =
136      BuildMI(MF, getDebugLoc(FirstMI, LastMI), TII->get(TargetOpcode::BUNDLE));
137  Bundle.prepend(MIB);
138
139  SmallVector<unsigned, 32> LocalDefs;
140  SmallSet<unsigned, 32> LocalDefSet;
141  SmallSet<unsigned, 8> DeadDefSet;
142  SmallSet<unsigned, 16> KilledDefSet;
143  SmallVector<unsigned, 8> ExternUses;
144  SmallSet<unsigned, 8> ExternUseSet;
145  SmallSet<unsigned, 8> KilledUseSet;
146  SmallSet<unsigned, 8> UndefUseSet;
147  SmallVector<MachineOperand*, 4> Defs;
148  for (auto MII = FirstMI; MII != LastMI; ++MII) {
149    for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
150      MachineOperand &MO = MII->getOperand(i);
151      if (!MO.isReg())
152        continue;
153      if (MO.isDef()) {
154        Defs.push_back(&MO);
155        continue;
156      }
157
158      Register Reg = MO.getReg();
159      if (!Reg)
160        continue;
161
162      if (LocalDefSet.count(Reg)) {
163        MO.setIsInternalRead();
164        if (MO.isKill())
165          // Internal def is now killed.
166          KilledDefSet.insert(Reg);
167      } else {
168        if (ExternUseSet.insert(Reg).second) {
169          ExternUses.push_back(Reg);
170          if (MO.isUndef())
171            UndefUseSet.insert(Reg);
172        }
173        if (MO.isKill())
174          // External def is now killed.
175          KilledUseSet.insert(Reg);
176      }
177    }
178
179    for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
180      MachineOperand &MO = *Defs[i];
181      Register Reg = MO.getReg();
182      if (!Reg)
183        continue;
184
185      if (LocalDefSet.insert(Reg).second) {
186        LocalDefs.push_back(Reg);
187        if (MO.isDead()) {
188          DeadDefSet.insert(Reg);
189        }
190      } else {
191        // Re-defined inside the bundle, it's no longer killed.
192        KilledDefSet.erase(Reg);
193        if (!MO.isDead())
194          // Previously defined but dead.
195          DeadDefSet.erase(Reg);
196      }
197
198      if (!MO.isDead() && Register::isPhysicalRegister(Reg)) {
199        for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
200          unsigned SubReg = *SubRegs;
201          if (LocalDefSet.insert(SubReg).second)
202            LocalDefs.push_back(SubReg);
203        }
204      }
205    }
206
207    Defs.clear();
208  }
209
210  SmallSet<unsigned, 32> Added;
211  for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
212    unsigned Reg = LocalDefs[i];
213    if (Added.insert(Reg).second) {
214      // If it's not live beyond end of the bundle, mark it dead.
215      bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg);
216      MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) |
217                 getImplRegState(true));
218    }
219  }
220
221  for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) {
222    unsigned Reg = ExternUses[i];
223    bool isKill = KilledUseSet.count(Reg);
224    bool isUndef = UndefUseSet.count(Reg);
225    MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) |
226               getImplRegState(true));
227  }
228
229  // Set FrameSetup/FrameDestroy for the bundle. If any of the instructions got
230  // the property, then also set it on the bundle.
231  for (auto MII = FirstMI; MII != LastMI; ++MII) {
232    if (MII->getFlag(MachineInstr::FrameSetup))
233      MIB.setMIFlag(MachineInstr::FrameSetup);
234    if (MII->getFlag(MachineInstr::FrameDestroy))
235      MIB.setMIFlag(MachineInstr::FrameDestroy);
236  }
237}
238
239/// finalizeBundle - Same functionality as the previous finalizeBundle except
240/// the last instruction in the bundle is not provided as an input. This is
241/// used in cases where bundles are pre-determined by marking instructions
242/// with 'InsideBundle' marker. It returns the MBB instruction iterator that
243/// points to the end of the bundle.
244MachineBasicBlock::instr_iterator
245llvm::finalizeBundle(MachineBasicBlock &MBB,
246                     MachineBasicBlock::instr_iterator FirstMI) {
247  MachineBasicBlock::instr_iterator E = MBB.instr_end();
248  MachineBasicBlock::instr_iterator LastMI = std::next(FirstMI);
249  while (LastMI != E && LastMI->isInsideBundle())
250    ++LastMI;
251  finalizeBundle(MBB, FirstMI, LastMI);
252  return LastMI;
253}
254
255/// finalizeBundles - Finalize instruction bundles in the specified
256/// MachineFunction. Return true if any bundles are finalized.
257bool llvm::finalizeBundles(MachineFunction &MF) {
258  bool Changed = false;
259  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
260    MachineBasicBlock &MBB = *I;
261    MachineBasicBlock::instr_iterator MII = MBB.instr_begin();
262    MachineBasicBlock::instr_iterator MIE = MBB.instr_end();
263    if (MII == MIE)
264      continue;
265    assert(!MII->isInsideBundle() &&
266           "First instr cannot be inside bundle before finalization!");
267
268    for (++MII; MII != MIE; ) {
269      if (!MII->isInsideBundle())
270        ++MII;
271      else {
272        MII = finalizeBundle(MBB, std::prev(MII));
273        Changed = true;
274      }
275    }
276  }
277
278  return Changed;
279}
280
281VirtRegInfo llvm::AnalyzeVirtRegInBundle(
282    MachineInstr &MI, unsigned Reg,
283    SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) {
284  VirtRegInfo RI = {false, false, false};
285  for (MIBundleOperands O(MI); O.isValid(); ++O) {
286    MachineOperand &MO = *O;
287    if (!MO.isReg() || MO.getReg() != Reg)
288      continue;
289
290    // Remember each (MI, OpNo) that refers to Reg.
291    if (Ops)
292      Ops->push_back(std::make_pair(MO.getParent(), O.getOperandNo()));
293
294    // Both defs and uses can read virtual registers.
295    if (MO.readsReg()) {
296      RI.Reads = true;
297      if (MO.isDef())
298        RI.Tied = true;
299    }
300
301    // Only defs can write.
302    if (MO.isDef())
303      RI.Writes = true;
304    else if (!RI.Tied &&
305             MO.getParent()->isRegTiedToDefOperand(O.getOperandNo()))
306      RI.Tied = true;
307  }
308  return RI;
309}
310
311PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, unsigned Reg,
312                                         const TargetRegisterInfo *TRI) {
313  bool AllDefsDead = true;
314  PhysRegInfo PRI = {false, false, false, false, false, false, false, false};
315
316  assert(Register::isPhysicalRegister(Reg) &&
317         "analyzePhysReg not given a physical register!");
318  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
319    const MachineOperand &MO = *O;
320
321    if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) {
322      PRI.Clobbered = true;
323      continue;
324    }
325
326    if (!MO.isReg())
327      continue;
328
329    Register MOReg = MO.getReg();
330    if (!MOReg || !Register::isPhysicalRegister(MOReg))
331      continue;
332
333    if (!TRI->regsOverlap(MOReg, Reg))
334      continue;
335
336    bool Covered = TRI->isSuperRegisterEq(Reg, MOReg);
337    if (MO.readsReg()) {
338      PRI.Read = true;
339      if (Covered) {
340        PRI.FullyRead = true;
341        if (MO.isKill())
342          PRI.Killed = true;
343      }
344    } else if (MO.isDef()) {
345      PRI.Defined = true;
346      if (Covered)
347        PRI.FullyDefined = true;
348      if (!MO.isDead())
349        AllDefsDead = false;
350    }
351  }
352
353  if (AllDefsDead) {
354    if (PRI.FullyDefined || PRI.Clobbered)
355      PRI.DeadDef = true;
356    else if (PRI.Defined)
357      PRI.PartialDeadDef = true;
358  }
359
360  return PRI;
361}
362