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