LLVM  6.0.0svn
MachineInstrBundle.cpp
Go to the documentation of this file.
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 
11 #include "llvm/ADT/SmallSet.h"
12 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/CodeGen/Passes.h"
20 #include <utility>
21 using namespace llvm;
22 
23 namespace {
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)) {
31  }
32 
33  bool runOnMachineFunction(MachineFunction &MF) override;
34 
35  private:
36  std::function<bool(const MachineFunction &)> PredicateFtor;
37  };
38 } // end anonymous namespace
39 
42 INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles",
43  "Unpack machine instruction bundles", false, false)
44 
45 bool 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 
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 
83  std::function<bool(const MachineFunction &)> Ftor) {
84  return new UnpackMachineBundles(std::move(Ftor));
85 }
86 
87 namespace {
88  class FinalizeMachineBundles : public MachineFunctionPass {
89  public:
90  static char ID; // Pass identification
91  FinalizeMachineBundles() : MachineFunctionPass(ID) {
93  }
94 
95  bool runOnMachineFunction(MachineFunction &MF) override;
96  };
97 } // end anonymous namespace
98 
101 INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles",
102  "Finalize machine instruction bundles", false, false)
103 
104 bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) {
105  return llvm::finalizeBundles(MF);
106 }
107 
108 
109 /// finalizeBundle - Finalize a machine instruction bundle which includes
110 /// a sequence of instructions starting from FirstMI to LastMI (exclusive).
111 /// This routine adds a BUNDLE instruction to represent the bundle, it adds
112 /// IsInternalRead markers to MachineOperands which are defined inside the
113 /// bundle, and it copies externally visible defs and uses to the BUNDLE
114 /// instruction.
118  assert(FirstMI != LastMI && "Empty bundle?");
119  MIBundleBuilder Bundle(MBB, FirstMI, LastMI);
120 
121  MachineFunction &MF = *MBB.getParent();
123  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
124 
125  MachineInstrBuilder MIB =
126  BuildMI(MF, FirstMI->getDebugLoc(), TII->get(TargetOpcode::BUNDLE));
127  Bundle.prepend(MIB);
128 
129  SmallVector<unsigned, 32> LocalDefs;
130  SmallSet<unsigned, 32> LocalDefSet;
131  SmallSet<unsigned, 8> DeadDefSet;
132  SmallSet<unsigned, 16> KilledDefSet;
133  SmallVector<unsigned, 8> ExternUses;
134  SmallSet<unsigned, 8> ExternUseSet;
135  SmallSet<unsigned, 8> KilledUseSet;
136  SmallSet<unsigned, 8> UndefUseSet;
138  for (; FirstMI != LastMI; ++FirstMI) {
139  for (unsigned i = 0, e = FirstMI->getNumOperands(); i != e; ++i) {
140  MachineOperand &MO = FirstMI->getOperand(i);
141  if (!MO.isReg())
142  continue;
143  if (MO.isDef()) {
144  Defs.push_back(&MO);
145  continue;
146  }
147 
148  unsigned Reg = MO.getReg();
149  if (!Reg)
150  continue;
152  if (LocalDefSet.count(Reg)) {
153  MO.setIsInternalRead();
154  if (MO.isKill())
155  // Internal def is now killed.
156  KilledDefSet.insert(Reg);
157  } else {
158  if (ExternUseSet.insert(Reg).second) {
159  ExternUses.push_back(Reg);
160  if (MO.isUndef())
161  UndefUseSet.insert(Reg);
162  }
163  if (MO.isKill())
164  // External def is now killed.
165  KilledUseSet.insert(Reg);
166  }
167  }
168 
169  for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
170  MachineOperand &MO = *Defs[i];
171  unsigned Reg = MO.getReg();
172  if (!Reg)
173  continue;
174 
175  if (LocalDefSet.insert(Reg).second) {
176  LocalDefs.push_back(Reg);
177  if (MO.isDead()) {
178  DeadDefSet.insert(Reg);
179  }
180  } else {
181  // Re-defined inside the bundle, it's no longer killed.
182  KilledDefSet.erase(Reg);
183  if (!MO.isDead())
184  // Previously defined but dead.
185  DeadDefSet.erase(Reg);
186  }
187 
188  if (!MO.isDead()) {
189  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
190  unsigned SubReg = *SubRegs;
191  if (LocalDefSet.insert(SubReg).second)
192  LocalDefs.push_back(SubReg);
193  }
194  }
195  }
196 
197  Defs.clear();
198  }
199 
201  for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
202  unsigned Reg = LocalDefs[i];
203  if (Added.insert(Reg).second) {
204  // If it's not live beyond end of the bundle, mark it dead.
205  bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg);
206  MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) |
207  getImplRegState(true));
208  }
209  }
210 
211  for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) {
212  unsigned Reg = ExternUses[i];
213  bool isKill = KilledUseSet.count(Reg);
214  bool isUndef = UndefUseSet.count(Reg);
215  MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) |
216  getImplRegState(true));
217  }
218 }
219 
220 /// finalizeBundle - Same functionality as the previous finalizeBundle except
221 /// the last instruction in the bundle is not provided as an input. This is
222 /// used in cases where bundles are pre-determined by marking instructions
223 /// with 'InsideBundle' marker. It returns the MBB instruction iterator that
224 /// points to the end of the bundle.
229  MachineBasicBlock::instr_iterator LastMI = std::next(FirstMI);
230  while (LastMI != E && LastMI->isInsideBundle())
231  ++LastMI;
232  finalizeBundle(MBB, FirstMI, LastMI);
233  return LastMI;
234 }
235 
236 /// finalizeBundles - Finalize instruction bundles in the specified
237 /// MachineFunction. Return true if any bundles are finalized.
239  bool Changed = false;
240  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
241  MachineBasicBlock &MBB = *I;
244  if (MII == MIE)
245  continue;
246  assert(!MII->isInsideBundle() &&
247  "First instr cannot be inside bundle before finalization!");
248 
249  for (++MII; MII != MIE; ) {
250  if (!MII->isInsideBundle())
251  ++MII;
252  else {
253  MII = finalizeBundle(MBB, std::prev(MII));
254  Changed = true;
255  }
256  }
257  }
258 
259  return Changed;
260 }
261 
262 //===----------------------------------------------------------------------===//
263 // MachineOperand iterator
264 //===----------------------------------------------------------------------===//
265 
268  SmallVectorImpl<std::pair<MachineInstr*, unsigned> > *Ops) {
269  VirtRegInfo RI = { false, false, false };
270  for(; isValid(); ++*this) {
271  MachineOperand &MO = deref();
272  if (!MO.isReg() || MO.getReg() != Reg)
273  continue;
274 
275  // Remember each (MI, OpNo) that refers to Reg.
276  if (Ops)
277  Ops->push_back(std::make_pair(MO.getParent(), getOperandNo()));
278 
279  // Both defs and uses can read virtual registers.
280  if (MO.readsReg()) {
281  RI.Reads = true;
282  if (MO.isDef())
283  RI.Tied = true;
284  }
285 
286  // Only defs can write.
287  if (MO.isDef())
288  RI.Writes = true;
289  else if (!RI.Tied && MO.getParent()->isRegTiedToDefOperand(getOperandNo()))
290  RI.Tied = true;
291  }
292  return RI;
293 }
294 
297  const TargetRegisterInfo *TRI) {
298  bool AllDefsDead = true;
299  PhysRegInfo PRI = {false, false, false, false, false, false, false, false};
300 
302  "analyzePhysReg not given a physical register!");
303  for (; isValid(); ++*this) {
304  MachineOperand &MO = deref();
305 
306  if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) {
307  PRI.Clobbered = true;
308  continue;
309  }
310 
311  if (!MO.isReg())
312  continue;
313 
314  unsigned MOReg = MO.getReg();
315  if (!MOReg || !TargetRegisterInfo::isPhysicalRegister(MOReg))
316  continue;
317 
318  if (!TRI->regsOverlap(MOReg, Reg))
319  continue;
320 
321  bool Covered = TRI->isSuperRegisterEq(Reg, MOReg);
322  if (MO.readsReg()) {
323  PRI.Read = true;
324  if (Covered) {
325  PRI.FullyRead = true;
326  if (MO.isKill())
327  PRI.Killed = true;
328  }
329  } else if (MO.isDef()) {
330  PRI.Defined = true;
331  if (Covered)
332  PRI.FullyDefined = true;
333  if (!MO.isDead())
334  AllDefsDead = false;
335  }
336  }
337 
338  if (AllDefsDead) {
339  if (PRI.FullyDefined || PRI.Clobbered)
340  PRI.DeadDef = true;
341  else if (PRI.Defined)
342  PRI.PartialDeadDef = true;
343  }
344 
345  return PRI;
346 }
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
bool isSuperRegisterEq(unsigned RegA, unsigned RegB) const
Returns true if RegB is a super-register of RegA or if RegB == RegA.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_begin()
instr_iterator instr_end()
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool Tied
Tied - Uses and defs must use the same register.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned getReg() const
getReg - Returns the register number.
void initializeFinalizeMachineBundlesPass(PassRegistry &)
void initializeUnpackMachineBundlesPass(PassRegistry &)
bool erase(const T &V)
Definition: SmallSet.h:108
bool isInternalRead() const
VirtRegInfo analyzeVirtReg(unsigned Reg, SmallVectorImpl< std::pair< MachineInstr *, unsigned > > *Ops=nullptr)
analyzeVirtReg - Analyze how the current instruction or bundle uses a virtual register.
Definition: BitVector.h:920
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned SubReg
Reg
All possible values of the reg field in the ModR/M byte.
char & FinalizeMachineBundlesID
FinalizeMachineBundles - This pass finalize machine instruction bundles (created earlier, e.g.
PhysRegInfo analyzePhysReg(unsigned Reg, const TargetRegisterInfo *TRI)
analyzePhysReg - Analyze how the current instruction or bundle uses a physical register.
INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles", "Unpack machine instruction bundles", false, false) bool UnpackMachineBundles
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register. ...
MIBundleBuilder & prepend(MachineInstr *MI)
Insert MI into MBB by prepending it to the instructions in the bundle.
bool isBundle() const
Definition: MachineInstr.h:853
virtual const TargetInstrInfo * getInstrInfo() const
unsigned getUndefRegState(bool B)
bool PartialDeadDef
Reg is Defined and all defs of reg or an overlapping register are dead.
VirtRegInfo - Information about a virtual register used by a set of operands.
unsigned getKillRegState(bool B)
TargetInstrInfo - Interface to description of machine instruction set.
unsigned getDeadRegState(bool B)
unsigned getDefRegState(bool B)
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool Writes
Writes - One of the operands writes the virtual register.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool Read
Reg or one of its aliases is read.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
bool Clobbered
There is a regmask operand indicating Reg is clobbered.
bool Killed
There is a use operand of reg or a super-register with kill flag set.
void setIsInternalRead(bool Val=true)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
bool isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx=nullptr) const
Return true if the use operand of the specified index is tied to a def operand.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
bool Reads
Reads - One of the operands read the virtual register.
char & UnpackMachineBundlesID
UnpackMachineBundles - This pass unpack machine instruction bundles.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCSubRegIterator enumerates all sub-registers of Reg.
Iterator for intrusive lists based on ilist_node.
bool regsOverlap(unsigned regA, unsigned regB) const
Returns true if the two registers are equal or alias each other.
MachineOperand class - Representation of each machine instruction operand.
bool finalizeBundles(MachineFunction &MF)
finalizeBundles - Finalize instruction bundles in the specified MachineFunction.
bool FullyDefined
Reg or a super-register is defined.
FunctionPass * createUnpackMachineBundles(std::function< bool(const MachineFunction &)> Ftor)
bool FullyRead
Reg or a super-register is read. The full register is read.
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Representation of each machine instruction.
Definition: MachineInstr.h:59
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned getImplRegState(bool B)
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Information about how a physical register Reg is used by a set of operands.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Instructions::iterator instr_iterator
bool Defined
Reg or one of its aliases is defined.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
print Print MemDeps of function
IRTranslator LLVM IR MI
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:952
void finalizeBundle(MachineBasicBlock &MBB, MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
finalizeBundle - Finalize a machine instruction bundle which includes a sequence of instructions star...
Helper class for constructing bundles of MachineInstrs.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:65