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