MachineInstr.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
1//===-- lib/CodeGen/MachineInstr.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// Methods common to all machine instructions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/MachineInstr.h"
15#include "llvm/ADT/FoldingSet.h"
16#include "llvm/ADT/Hashing.h"
17#include "llvm/Analysis/AliasAnalysis.h"
18#include "llvm/CodeGen/MachineConstantPool.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/MachineMemOperand.h"
21#include "llvm/CodeGen/MachineModuleInfo.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/CodeGen/PseudoSourceValue.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/DebugInfo.h"
26#include "llvm/IR/Function.h"
27#include "llvm/IR/InlineAsm.h"
28#include "llvm/IR/LLVMContext.h"
29#include "llvm/IR/Metadata.h"
30#include "llvm/IR/Module.h"
31#include "llvm/IR/Type.h"
32#include "llvm/IR/Value.h"
33#include "llvm/MC/MCInstrDesc.h"
34#include "llvm/MC/MCSymbol.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/ErrorHandling.h"
37#include "llvm/Support/MathExtras.h"
38#include "llvm/Support/raw_ostream.h"
39#include "llvm/Target/TargetInstrInfo.h"
40#include "llvm/Target/TargetMachine.h"
41#include "llvm/Target/TargetRegisterInfo.h"
42using namespace llvm;
43
44//===----------------------------------------------------------------------===//
45// MachineOperand Implementation
46//===----------------------------------------------------------------------===//
47
48void MachineOperand::setReg(unsigned Reg) {
49  if (getReg() == Reg) return; // No change.
50
51  // Otherwise, we have to change the register.  If this operand is embedded
52  // into a machine function, we need to update the old and new register's
53  // use/def lists.
54  if (MachineInstr *MI = getParent())
55    if (MachineBasicBlock *MBB = MI->getParent())
56      if (MachineFunction *MF = MBB->getParent()) {
57        MachineRegisterInfo &MRI = MF->getRegInfo();
58        MRI.removeRegOperandFromUseList(this);
59        SmallContents.RegNo = Reg;
60        MRI.addRegOperandToUseList(this);
61        return;
62      }
63
64  // Otherwise, just change the register, no problem.  :)
65  SmallContents.RegNo = Reg;
66}
67
68void MachineOperand::substVirtReg(unsigned Reg, unsigned SubIdx,
69                                  const TargetRegisterInfo &TRI) {
70  assert(TargetRegisterInfo::isVirtualRegister(Reg));
71  if (SubIdx && getSubReg())
72    SubIdx = TRI.composeSubRegIndices(SubIdx, getSubReg());
73  setReg(Reg);
74  if (SubIdx)
75    setSubReg(SubIdx);
76}
77
78void MachineOperand::substPhysReg(unsigned Reg, const TargetRegisterInfo &TRI) {
79  assert(TargetRegisterInfo::isPhysicalRegister(Reg));
80  if (getSubReg()) {
81    Reg = TRI.getSubReg(Reg, getSubReg());
82    // Note that getSubReg() may return 0 if the sub-register doesn't exist.
83    // That won't happen in legal code.
84    setSubReg(0);
85  }
86  setReg(Reg);
87}
88
89/// Change a def to a use, or a use to a def.
90void MachineOperand::setIsDef(bool Val) {
91  assert(isReg() && "Wrong MachineOperand accessor");
92  assert((!Val || !isDebug()) && "Marking a debug operation as def");
93  if (IsDef == Val)
94    return;
95  // MRI may keep uses and defs in different list positions.
96  if (MachineInstr *MI = getParent())
97    if (MachineBasicBlock *MBB = MI->getParent())
98      if (MachineFunction *MF = MBB->getParent()) {
99        MachineRegisterInfo &MRI = MF->getRegInfo();
100        MRI.removeRegOperandFromUseList(this);
101        IsDef = Val;
102        MRI.addRegOperandToUseList(this);
103        return;
104      }
105  IsDef = Val;
106}
107
108/// ChangeToImmediate - Replace this operand with a new immediate operand of
109/// the specified value.  If an operand is known to be an immediate already,
110/// the setImm method should be used.
111void MachineOperand::ChangeToImmediate(int64_t ImmVal) {
112  assert((!isReg() || !isTied()) && "Cannot change a tied operand into an imm");
113  // If this operand is currently a register operand, and if this is in a
114  // function, deregister the operand from the register's use/def list.
115  if (isReg() && isOnRegUseList())
116    if (MachineInstr *MI = getParent())
117      if (MachineBasicBlock *MBB = MI->getParent())
118        if (MachineFunction *MF = MBB->getParent())
119          MF->getRegInfo().removeRegOperandFromUseList(this);
120
121  OpKind = MO_Immediate;
122  Contents.ImmVal = ImmVal;
123}
124
125/// ChangeToRegister - Replace this operand with a new register operand of
126/// the specified value.  If an operand is known to be an register already,
127/// the setReg method should be used.
128void MachineOperand::ChangeToRegister(unsigned Reg, bool isDef, bool isImp,
129                                      bool isKill, bool isDead, bool isUndef,
130                                      bool isDebug) {
131  MachineRegisterInfo *RegInfo = 0;
132  if (MachineInstr *MI = getParent())
133    if (MachineBasicBlock *MBB = MI->getParent())
134      if (MachineFunction *MF = MBB->getParent())
135        RegInfo = &MF->getRegInfo();
136  // If this operand is already a register operand, remove it from the
137  // register's use/def lists.
138  bool WasReg = isReg();
139  if (RegInfo && WasReg)
140    RegInfo->removeRegOperandFromUseList(this);
141
142  // Change this to a register and set the reg#.
143  OpKind = MO_Register;
144  SmallContents.RegNo = Reg;
145  SubReg_TargetFlags = 0;
146  IsDef = isDef;
147  IsImp = isImp;
148  IsKill = isKill;
149  IsDead = isDead;
150  IsUndef = isUndef;
151  IsInternalRead = false;
152  IsEarlyClobber = false;
153  IsDebug = isDebug;
154  // Ensure isOnRegUseList() returns false.
155  Contents.Reg.Prev = 0;
156  // Preserve the tie when the operand was already a register.
157  if (!WasReg)
158    TiedTo = 0;
159
160  // If this operand is embedded in a function, add the operand to the
161  // register's use/def list.
162  if (RegInfo)
163    RegInfo->addRegOperandToUseList(this);
164}
165
166/// isIdenticalTo - Return true if this operand is identical to the specified
167/// operand. Note that this should stay in sync with the hash_value overload
168/// below.
169bool MachineOperand::isIdenticalTo(const MachineOperand &Other) const {
170  if (getType() != Other.getType() ||
171      getTargetFlags() != Other.getTargetFlags())
172    return false;
173
174  switch (getType()) {
175  case MachineOperand::MO_Register:
176    return getReg() == Other.getReg() && isDef() == Other.isDef() &&
177           getSubReg() == Other.getSubReg();
178  case MachineOperand::MO_Immediate:
179    return getImm() == Other.getImm();
180  case MachineOperand::MO_CImmediate:
181    return getCImm() == Other.getCImm();
182  case MachineOperand::MO_FPImmediate:
183    return getFPImm() == Other.getFPImm();
184  case MachineOperand::MO_MachineBasicBlock:
185    return getMBB() == Other.getMBB();
186  case MachineOperand::MO_FrameIndex:
187    return getIndex() == Other.getIndex();
188  case MachineOperand::MO_ConstantPoolIndex:
189  case MachineOperand::MO_TargetIndex:
190    return getIndex() == Other.getIndex() && getOffset() == Other.getOffset();
191  case MachineOperand::MO_JumpTableIndex:
192    return getIndex() == Other.getIndex();
193  case MachineOperand::MO_GlobalAddress:
194    return getGlobal() == Other.getGlobal() && getOffset() == Other.getOffset();
195  case MachineOperand::MO_ExternalSymbol:
196    return !strcmp(getSymbolName(), Other.getSymbolName()) &&
197           getOffset() == Other.getOffset();
198  case MachineOperand::MO_BlockAddress:
199    return getBlockAddress() == Other.getBlockAddress() &&
200           getOffset() == Other.getOffset();
201  case MachineOperand::MO_RegisterMask:
202  case MachineOperand::MO_RegisterLiveOut:
203    return getRegMask() == Other.getRegMask();
204  case MachineOperand::MO_MCSymbol:
205    return getMCSymbol() == Other.getMCSymbol();
206  case MachineOperand::MO_CFIIndex:
207    return getCFIIndex() == Other.getCFIIndex();
208  case MachineOperand::MO_Metadata:
209    return getMetadata() == Other.getMetadata();
210  }
211  llvm_unreachable("Invalid machine operand type");
212}
213
214// Note: this must stay exactly in sync with isIdenticalTo above.
215hash_code llvm::hash_value(const MachineOperand &MO) {
216  switch (MO.getType()) {
217  case MachineOperand::MO_Register:
218    // Register operands don't have target flags.
219    return hash_combine(MO.getType(), MO.getReg(), MO.getSubReg(), MO.isDef());
220  case MachineOperand::MO_Immediate:
221    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getImm());
222  case MachineOperand::MO_CImmediate:
223    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getCImm());
224  case MachineOperand::MO_FPImmediate:
225    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getFPImm());
226  case MachineOperand::MO_MachineBasicBlock:
227    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getMBB());
228  case MachineOperand::MO_FrameIndex:
229    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIndex());
230  case MachineOperand::MO_ConstantPoolIndex:
231  case MachineOperand::MO_TargetIndex:
232    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIndex(),
233                        MO.getOffset());
234  case MachineOperand::MO_JumpTableIndex:
235    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIndex());
236  case MachineOperand::MO_ExternalSymbol:
237    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
238                        MO.getSymbolName());
239  case MachineOperand::MO_GlobalAddress:
240    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getGlobal(),
241                        MO.getOffset());
242  case MachineOperand::MO_BlockAddress:
243    return hash_combine(MO.getType(), MO.getTargetFlags(),
244                        MO.getBlockAddress(), MO.getOffset());
245  case MachineOperand::MO_RegisterMask:
246  case MachineOperand::MO_RegisterLiveOut:
247    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getRegMask());
248  case MachineOperand::MO_Metadata:
249    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getMetadata());
250  case MachineOperand::MO_MCSymbol:
251    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getMCSymbol());
252  case MachineOperand::MO_CFIIndex:
253    return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getCFIIndex());
254  }
255  llvm_unreachable("Invalid machine operand type");
256}
257
258/// print - Print the specified machine operand.
259///
260void MachineOperand::print(raw_ostream &OS, const TargetMachine *TM) const {
261  // If the instruction is embedded into a basic block, we can find the
262  // target info for the instruction.
263  if (!TM)
264    if (const MachineInstr *MI = getParent())
265      if (const MachineBasicBlock *MBB = MI->getParent())
266        if (const MachineFunction *MF = MBB->getParent())
267          TM = &MF->getTarget();
268  const TargetRegisterInfo *TRI = TM ? TM->getRegisterInfo() : 0;
269
270  switch (getType()) {
271  case MachineOperand::MO_Register:
272    OS << PrintReg(getReg(), TRI, getSubReg());
273
274    if (isDef() || isKill() || isDead() || isImplicit() || isUndef() ||
275        isInternalRead() || isEarlyClobber() || isTied()) {
276      OS << '<';
277      bool NeedComma = false;
278      if (isDef()) {
279        if (NeedComma) OS << ',';
280        if (isEarlyClobber())
281          OS << "earlyclobber,";
282        if (isImplicit())
283          OS << "imp-";
284        OS << "def";
285        NeedComma = true;
286        // <def,read-undef> only makes sense when getSubReg() is set.
287        // Don't clutter the output otherwise.
288        if (isUndef() && getSubReg())
289          OS << ",read-undef";
290      } else if (isImplicit()) {
291          OS << "imp-use";
292          NeedComma = true;
293      }
294
295      if (isKill()) {
296        if (NeedComma) OS << ',';
297        OS << "kill";
298        NeedComma = true;
299      }
300      if (isDead()) {
301        if (NeedComma) OS << ',';
302        OS << "dead";
303        NeedComma = true;
304      }
305      if (isUndef() && isUse()) {
306        if (NeedComma) OS << ',';
307        OS << "undef";
308        NeedComma = true;
309      }
310      if (isInternalRead()) {
311        if (NeedComma) OS << ',';
312        OS << "internal";
313        NeedComma = true;
314      }
315      if (isTied()) {
316        if (NeedComma) OS << ',';
317        OS << "tied";
318        if (TiedTo != 15)
319          OS << unsigned(TiedTo - 1);
320      }
321      OS << '>';
322    }
323    break;
324  case MachineOperand::MO_Immediate:
325    OS << getImm();
326    break;
327  case MachineOperand::MO_CImmediate:
328    getCImm()->getValue().print(OS, false);
329    break;
330  case MachineOperand::MO_FPImmediate:
331    if (getFPImm()->getType()->isFloatTy())
332      OS << getFPImm()->getValueAPF().convertToFloat();
333    else
334      OS << getFPImm()->getValueAPF().convertToDouble();
335    break;
336  case MachineOperand::MO_MachineBasicBlock:
337    OS << "<BB#" << getMBB()->getNumber() << ">";
338    break;
339  case MachineOperand::MO_FrameIndex:
340    OS << "<fi#" << getIndex() << '>';
341    break;
342  case MachineOperand::MO_ConstantPoolIndex:
343    OS << "<cp#" << getIndex();
344    if (getOffset()) OS << "+" << getOffset();
345    OS << '>';
346    break;
347  case MachineOperand::MO_TargetIndex:
348    OS << "<ti#" << getIndex();
349    if (getOffset()) OS << "+" << getOffset();
350    OS << '>';
351    break;
352  case MachineOperand::MO_JumpTableIndex:
353    OS << "<jt#" << getIndex() << '>';
354    break;
355  case MachineOperand::MO_GlobalAddress:
356    OS << "<ga:";
357    getGlobal()->printAsOperand(OS, /*PrintType=*/false);
358    if (getOffset()) OS << "+" << getOffset();
359    OS << '>';
360    break;
361  case MachineOperand::MO_ExternalSymbol:
362    OS << "<es:" << getSymbolName();
363    if (getOffset()) OS << "+" << getOffset();
364    OS << '>';
365    break;
366  case MachineOperand::MO_BlockAddress:
367    OS << '<';
368    getBlockAddress()->printAsOperand(OS, /*PrintType=*/false);
369    if (getOffset()) OS << "+" << getOffset();
370    OS << '>';
371    break;
372  case MachineOperand::MO_RegisterMask:
373    OS << "<regmask>";
374    break;
375  case MachineOperand::MO_RegisterLiveOut:
376    OS << "<regliveout>";
377    break;
378  case MachineOperand::MO_Metadata:
379    OS << '<';
380    getMetadata()->printAsOperand(OS, /*PrintType=*/false);
381    OS << '>';
382    break;
383  case MachineOperand::MO_MCSymbol:
384    OS << "<MCSym=" << *getMCSymbol() << '>';
385    break;
386  case MachineOperand::MO_CFIIndex:
387    OS << "<call frame instruction>";
388    break;
389  }
390
391  if (unsigned TF = getTargetFlags())
392    OS << "[TF=" << TF << ']';
393}
394
395//===----------------------------------------------------------------------===//
396// MachineMemOperand Implementation
397//===----------------------------------------------------------------------===//
398
399/// getAddrSpace - Return the LLVM IR address space number that this pointer
400/// points into.
401unsigned MachinePointerInfo::getAddrSpace() const {
402  if (V == 0) return 0;
403  return cast<PointerType>(V->getType())->getAddressSpace();
404}
405
406/// getConstantPool - Return a MachinePointerInfo record that refers to the
407/// constant pool.
408MachinePointerInfo MachinePointerInfo::getConstantPool() {
409  return MachinePointerInfo(PseudoSourceValue::getConstantPool());
410}
411
412/// getFixedStack - Return a MachinePointerInfo record that refers to the
413/// the specified FrameIndex.
414MachinePointerInfo MachinePointerInfo::getFixedStack(int FI, int64_t offset) {
415  return MachinePointerInfo(PseudoSourceValue::getFixedStack(FI), offset);
416}
417
418MachinePointerInfo MachinePointerInfo::getJumpTable() {
419  return MachinePointerInfo(PseudoSourceValue::getJumpTable());
420}
421
422MachinePointerInfo MachinePointerInfo::getGOT() {
423  return MachinePointerInfo(PseudoSourceValue::getGOT());
424}
425
426MachinePointerInfo MachinePointerInfo::getStack(int64_t Offset) {
427  return MachinePointerInfo(PseudoSourceValue::getStack(), Offset);
428}
429
430MachineMemOperand::MachineMemOperand(MachinePointerInfo ptrinfo, unsigned f,
431                                     uint64_t s, unsigned int a,
432                                     const MDNode *TBAAInfo,
433                                     const MDNode *Ranges)
434  : PtrInfo(ptrinfo), Size(s),
435    Flags((f & ((1 << MOMaxBits) - 1)) | ((Log2_32(a) + 1) << MOMaxBits)),
436    TBAAInfo(TBAAInfo), Ranges(Ranges) {
437  assert((PtrInfo.V == 0 || isa<PointerType>(PtrInfo.V->getType())) &&
438         "invalid pointer value");
439  assert(getBaseAlignment() == a && "Alignment is not a power of 2!");
440  assert((isLoad() || isStore()) && "Not a load/store!");
441}
442
443/// Profile - Gather unique data for the object.
444///
445void MachineMemOperand::Profile(FoldingSetNodeID &ID) const {
446  ID.AddInteger(getOffset());
447  ID.AddInteger(Size);
448  ID.AddPointer(getValue());
449  ID.AddInteger(Flags);
450}
451
452void MachineMemOperand::refineAlignment(const MachineMemOperand *MMO) {
453  // The Value and Offset may differ due to CSE. But the flags and size
454  // should be the same.
455  assert(MMO->getFlags() == getFlags() && "Flags mismatch!");
456  assert(MMO->getSize() == getSize() && "Size mismatch!");
457
458  if (MMO->getBaseAlignment() >= getBaseAlignment()) {
459    // Update the alignment value.
460    Flags = (Flags & ((1 << MOMaxBits) - 1)) |
461      ((Log2_32(MMO->getBaseAlignment()) + 1) << MOMaxBits);
462    // Also update the base and offset, because the new alignment may
463    // not be applicable with the old ones.
464    PtrInfo = MMO->PtrInfo;
465  }
466}
467
468/// getAlignment - Return the minimum known alignment in bytes of the
469/// actual memory reference.
470uint64_t MachineMemOperand::getAlignment() const {
471  return MinAlign(getBaseAlignment(), getOffset());
472}
473
474raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineMemOperand &MMO) {
475  assert((MMO.isLoad() || MMO.isStore()) &&
476         "SV has to be a load, store or both.");
477
478  if (MMO.isVolatile())
479    OS << "Volatile ";
480
481  if (MMO.isLoad())
482    OS << "LD";
483  if (MMO.isStore())
484    OS << "ST";
485  OS << MMO.getSize();
486
487  // Print the address information.
488  OS << "[";
489  if (!MMO.getValue())
490    OS << "<unknown>";
491  else
492    MMO.getValue()->printAsOperand(OS, /*PrintType=*/false);
493
494  unsigned AS = MMO.getAddrSpace();
495  if (AS != 0)
496    OS << "(addrspace=" << AS << ')';
497
498  // If the alignment of the memory reference itself differs from the alignment
499  // of the base pointer, print the base alignment explicitly, next to the base
500  // pointer.
501  if (MMO.getBaseAlignment() != MMO.getAlignment())
502    OS << "(align=" << MMO.getBaseAlignment() << ")";
503
504  if (MMO.getOffset() != 0)
505    OS << "+" << MMO.getOffset();
506  OS << "]";
507
508  // Print the alignment of the reference.
509  if (MMO.getBaseAlignment() != MMO.getAlignment() ||
510      MMO.getBaseAlignment() != MMO.getSize())
511    OS << "(align=" << MMO.getAlignment() << ")";
512
513  // Print TBAA info.
514  if (const MDNode *TBAAInfo = MMO.getTBAAInfo()) {
515    OS << "(tbaa=";
516    if (TBAAInfo->getNumOperands() > 0)
517      TBAAInfo->getOperand(0)->printAsOperand(OS, /*PrintType=*/false);
518    else
519      OS << "<unknown>";
520    OS << ")";
521  }
522
523  // Print nontemporal info.
524  if (MMO.isNonTemporal())
525    OS << "(nontemporal)";
526
527  return OS;
528}
529
530//===----------------------------------------------------------------------===//
531// MachineInstr Implementation
532//===----------------------------------------------------------------------===//
533
534void MachineInstr::addImplicitDefUseOperands(MachineFunction &MF) {
535  if (MCID->ImplicitDefs)
536    for (const uint16_t *ImpDefs = MCID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
537      addOperand(MF, MachineOperand::CreateReg(*ImpDefs, true, true));
538  if (MCID->ImplicitUses)
539    for (const uint16_t *ImpUses = MCID->getImplicitUses(); *ImpUses; ++ImpUses)
540      addOperand(MF, MachineOperand::CreateReg(*ImpUses, false, true));
541}
542
543/// MachineInstr ctor - This constructor creates a MachineInstr and adds the
544/// implicit operands. It reserves space for the number of operands specified by
545/// the MCInstrDesc.
546MachineInstr::MachineInstr(MachineFunction &MF, const MCInstrDesc &tid,
547                           const DebugLoc dl, bool NoImp)
548  : MCID(&tid), Parent(0), Operands(0), NumOperands(0),
549    Flags(0), AsmPrinterFlags(0),
550    NumMemRefs(0), MemRefs(0), debugLoc(dl) {
551  // Reserve space for the expected number of operands.
552  if (unsigned NumOps = MCID->getNumOperands() +
553    MCID->getNumImplicitDefs() + MCID->getNumImplicitUses()) {
554    CapOperands = OperandCapacity::get(NumOps);
555    Operands = MF.allocateOperandArray(CapOperands);
556  }
557
558  if (!NoImp)
559    addImplicitDefUseOperands(MF);
560}
561
562/// MachineInstr ctor - Copies MachineInstr arg exactly
563///
564MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI)
565  : MCID(&MI.getDesc()), Parent(0), Operands(0), NumOperands(0),
566    Flags(0), AsmPrinterFlags(0),
567    NumMemRefs(MI.NumMemRefs), MemRefs(MI.MemRefs),
568    debugLoc(MI.getDebugLoc()) {
569  CapOperands = OperandCapacity::get(MI.getNumOperands());
570  Operands = MF.allocateOperandArray(CapOperands);
571
572  // Copy operands.
573  for (unsigned i = 0; i != MI.getNumOperands(); ++i)
574    addOperand(MF, MI.getOperand(i));
575
576  // Copy all the sensible flags.
577  setFlags(MI.Flags);
578}
579
580/// getRegInfo - If this instruction is embedded into a MachineFunction,
581/// return the MachineRegisterInfo object for the current function, otherwise
582/// return null.
583MachineRegisterInfo *MachineInstr::getRegInfo() {
584  if (MachineBasicBlock *MBB = getParent())
585    return &MBB->getParent()->getRegInfo();
586  return 0;
587}
588
589/// RemoveRegOperandsFromUseLists - Unlink all of the register operands in
590/// this instruction from their respective use lists.  This requires that the
591/// operands already be on their use lists.
592void MachineInstr::RemoveRegOperandsFromUseLists(MachineRegisterInfo &MRI) {
593  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
594    if (Operands[i].isReg())
595      MRI.removeRegOperandFromUseList(&Operands[i]);
596}
597
598/// AddRegOperandsToUseLists - Add all of the register operands in
599/// this instruction from their respective use lists.  This requires that the
600/// operands not be on their use lists yet.
601void MachineInstr::AddRegOperandsToUseLists(MachineRegisterInfo &MRI) {
602  for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
603    if (Operands[i].isReg())
604      MRI.addRegOperandToUseList(&Operands[i]);
605}
606
607void MachineInstr::addOperand(const MachineOperand &Op) {
608  MachineBasicBlock *MBB = getParent();
609  assert(MBB && "Use MachineInstrBuilder to add operands to dangling instrs");
610  MachineFunction *MF = MBB->getParent();
611  assert(MF && "Use MachineInstrBuilder to add operands to dangling instrs");
612  addOperand(*MF, Op);
613}
614
615/// Move NumOps MachineOperands from Src to Dst, with support for overlapping
616/// ranges. If MRI is non-null also update use-def chains.
617static void moveOperands(MachineOperand *Dst, MachineOperand *Src,
618                         unsigned NumOps, MachineRegisterInfo *MRI) {
619  if (MRI)
620    return MRI->moveOperands(Dst, Src, NumOps);
621
622  // Here it would be convenient to call memmove, so that isn't allowed because
623  // MachineOperand has a constructor and so isn't a POD type.
624  if (Dst < Src)
625    for (unsigned i = 0; i != NumOps; ++i)
626      new (Dst + i) MachineOperand(Src[i]);
627  else
628    for (unsigned i = NumOps; i ; --i)
629      new (Dst + i - 1) MachineOperand(Src[i - 1]);
630}
631
632/// addOperand - Add the specified operand to the instruction.  If it is an
633/// implicit operand, it is added to the end of the operand list.  If it is
634/// an explicit operand it is added at the end of the explicit operand list
635/// (before the first implicit operand).
636void MachineInstr::addOperand(MachineFunction &MF, const MachineOperand &Op) {
637  assert(MCID && "Cannot add operands before providing an instr descriptor");
638
639  // Check if we're adding one of our existing operands.
640  if (&Op >= Operands && &Op < Operands + NumOperands) {
641    // This is unusual: MI->addOperand(MI->getOperand(i)).
642    // If adding Op requires reallocating or moving existing operands around,
643    // the Op reference could go stale. Support it by copying Op.
644    MachineOperand CopyOp(Op);
645    return addOperand(MF, CopyOp);
646  }
647
648  // Find the insert location for the new operand.  Implicit registers go at
649  // the end, everything else goes before the implicit regs.
650  //
651  // FIXME: Allow mixed explicit and implicit operands on inline asm.
652  // InstrEmitter::EmitSpecialNode() is marking inline asm clobbers as
653  // implicit-defs, but they must not be moved around.  See the FIXME in
654  // InstrEmitter.cpp.
655  unsigned OpNo = getNumOperands();
656  bool isImpReg = Op.isReg() && Op.isImplicit();
657  if (!isImpReg && !isInlineAsm()) {
658    while (OpNo && Operands[OpNo-1].isReg() && Operands[OpNo-1].isImplicit()) {
659      --OpNo;
660      assert(!Operands[OpNo].isTied() && "Cannot move tied operands");
661    }
662  }
663
664#ifndef NDEBUG
665  bool isMetaDataOp = Op.getType() == MachineOperand::MO_Metadata;
666  // OpNo now points as the desired insertion point.  Unless this is a variadic
667  // instruction, only implicit regs are allowed beyond MCID->getNumOperands().
668  // RegMask operands go between the explicit and implicit operands.
669  assert((isImpReg || Op.isRegMask() || MCID->isVariadic() ||
670          OpNo < MCID->getNumOperands() || isMetaDataOp) &&
671         "Trying to add an operand to a machine instr that is already done!");
672#endif
673
674  MachineRegisterInfo *MRI = getRegInfo();
675
676  // Determine if the Operands array needs to be reallocated.
677  // Save the old capacity and operand array.
678  OperandCapacity OldCap = CapOperands;
679  MachineOperand *OldOperands = Operands;
680  if (!OldOperands || OldCap.getSize() == getNumOperands()) {
681    CapOperands = OldOperands ? OldCap.getNext() : OldCap.get(1);
682    Operands = MF.allocateOperandArray(CapOperands);
683    // Move the operands before the insertion point.
684    if (OpNo)
685      moveOperands(Operands, OldOperands, OpNo, MRI);
686  }
687
688  // Move the operands following the insertion point.
689  if (OpNo != NumOperands)
690    moveOperands(Operands + OpNo + 1, OldOperands + OpNo, NumOperands - OpNo,
691                 MRI);
692  ++NumOperands;
693
694  // Deallocate the old operand array.
695  if (OldOperands != Operands && OldOperands)
696    MF.deallocateOperandArray(OldCap, OldOperands);
697
698  // Copy Op into place. It still needs to be inserted into the MRI use lists.
699  MachineOperand *NewMO = new (Operands + OpNo) MachineOperand(Op);
700  NewMO->ParentMI = this;
701
702  // When adding a register operand, tell MRI about it.
703  if (NewMO->isReg()) {
704    // Ensure isOnRegUseList() returns false, regardless of Op's status.
705    NewMO->Contents.Reg.Prev = 0;
706    // Ignore existing ties. This is not a property that can be copied.
707    NewMO->TiedTo = 0;
708    // Add the new operand to MRI, but only for instructions in an MBB.
709    if (MRI)
710      MRI->addRegOperandToUseList(NewMO);
711    // The MCID operand information isn't accurate until we start adding
712    // explicit operands. The implicit operands are added first, then the
713    // explicits are inserted before them.
714    if (!isImpReg) {
715      // Tie uses to defs as indicated in MCInstrDesc.
716      if (NewMO->isUse()) {
717        int DefIdx = MCID->getOperandConstraint(OpNo, MCOI::TIED_TO);
718        if (DefIdx != -1)
719          tieOperands(DefIdx, OpNo);
720      }
721      // If the register operand is flagged as early, mark the operand as such.
722      if (MCID->getOperandConstraint(OpNo, MCOI::EARLY_CLOBBER) != -1)
723        NewMO->setIsEarlyClobber(true);
724    }
725  }
726}
727
728/// RemoveOperand - Erase an operand  from an instruction, leaving it with one
729/// fewer operand than it started with.
730///
731void MachineInstr::RemoveOperand(unsigned OpNo) {
732  assert(OpNo < getNumOperands() && "Invalid operand number");
733  untieRegOperand(OpNo);
734
735#ifndef NDEBUG
736  // Moving tied operands would break the ties.
737  for (unsigned i = OpNo + 1, e = getNumOperands(); i != e; ++i)
738    if (Operands[i].isReg())
739      assert(!Operands[i].isTied() && "Cannot move tied operands");
740#endif
741
742  MachineRegisterInfo *MRI = getRegInfo();
743  if (MRI && Operands[OpNo].isReg())
744    MRI->removeRegOperandFromUseList(Operands + OpNo);
745
746  // Don't call the MachineOperand destructor. A lot of this code depends on
747  // MachineOperand having a trivial destructor anyway, and adding a call here
748  // wouldn't make it 'destructor-correct'.
749
750  if (unsigned N = NumOperands - 1 - OpNo)
751    moveOperands(Operands + OpNo, Operands + OpNo + 1, N, MRI);
752  --NumOperands;
753}
754
755/// addMemOperand - Add a MachineMemOperand to the machine instruction.
756/// This function should be used only occasionally. The setMemRefs function
757/// is the primary method for setting up a MachineInstr's MemRefs list.
758void MachineInstr::addMemOperand(MachineFunction &MF,
759                                 MachineMemOperand *MO) {
760  mmo_iterator OldMemRefs = MemRefs;
761  unsigned OldNumMemRefs = NumMemRefs;
762
763  unsigned NewNum = NumMemRefs + 1;
764  mmo_iterator NewMemRefs = MF.allocateMemRefsArray(NewNum);
765
766  std::copy(OldMemRefs, OldMemRefs + OldNumMemRefs, NewMemRefs);
767  NewMemRefs[NewNum - 1] = MO;
768  setMemRefs(NewMemRefs, NewMemRefs + NewNum);
769}
770
771bool MachineInstr::hasPropertyInBundle(unsigned Mask, QueryType Type) const {
772  assert(!isBundledWithPred() && "Must be called on bundle header");
773  for (MachineBasicBlock::const_instr_iterator MII = this;; ++MII) {
774    if (MII->getDesc().getFlags() & Mask) {
775      if (Type == AnyInBundle)
776        return true;
777    } else {
778      if (Type == AllInBundle && !MII->isBundle())
779        return false;
780    }
781    // This was the last instruction in the bundle.
782    if (!MII->isBundledWithSucc())
783      return Type == AllInBundle;
784  }
785}
786
787bool MachineInstr::isIdenticalTo(const MachineInstr *Other,
788                                 MICheckType Check) const {
789  // If opcodes or number of operands are not the same then the two
790  // instructions are obviously not identical.
791  if (Other->getOpcode() != getOpcode() ||
792      Other->getNumOperands() != getNumOperands())
793    return false;
794
795  if (isBundle()) {
796    // Both instructions are bundles, compare MIs inside the bundle.
797    MachineBasicBlock::const_instr_iterator I1 = *this;
798    MachineBasicBlock::const_instr_iterator E1 = getParent()->instr_end();
799    MachineBasicBlock::const_instr_iterator I2 = *Other;
800    MachineBasicBlock::const_instr_iterator E2= Other->getParent()->instr_end();
801    while (++I1 != E1 && I1->isInsideBundle()) {
802      ++I2;
803      if (I2 == E2 || !I2->isInsideBundle() || !I1->isIdenticalTo(I2, Check))
804        return false;
805    }
806  }
807
808  // Check operands to make sure they match.
809  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
810    const MachineOperand &MO = getOperand(i);
811    const MachineOperand &OMO = Other->getOperand(i);
812    if (!MO.isReg()) {
813      if (!MO.isIdenticalTo(OMO))
814        return false;
815      continue;
816    }
817
818    // Clients may or may not want to ignore defs when testing for equality.
819    // For example, machine CSE pass only cares about finding common
820    // subexpressions, so it's safe to ignore virtual register defs.
821    if (MO.isDef()) {
822      if (Check == IgnoreDefs)
823        continue;
824      else if (Check == IgnoreVRegDefs) {
825        if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()) ||
826            TargetRegisterInfo::isPhysicalRegister(OMO.getReg()))
827          if (MO.getReg() != OMO.getReg())
828            return false;
829      } else {
830        if (!MO.isIdenticalTo(OMO))
831          return false;
832        if (Check == CheckKillDead && MO.isDead() != OMO.isDead())
833          return false;
834      }
835    } else {
836      if (!MO.isIdenticalTo(OMO))
837        return false;
838      if (Check == CheckKillDead && MO.isKill() != OMO.isKill())
839        return false;
840    }
841  }
842  // If DebugLoc does not match then two dbg.values are not identical.
843  if (isDebugValue())
844    if (!getDebugLoc().isUnknown() && !Other->getDebugLoc().isUnknown()
845        && getDebugLoc() != Other->getDebugLoc())
846      return false;
847  return true;
848}
849
850MachineInstr *MachineInstr::removeFromParent() {
851  assert(getParent() && "Not embedded in a basic block!");
852  return getParent()->remove(this);
853}
854
855MachineInstr *MachineInstr::removeFromBundle() {
856  assert(getParent() && "Not embedded in a basic block!");
857  return getParent()->remove_instr(this);
858}
859
860void MachineInstr::eraseFromParent() {
861  assert(getParent() && "Not embedded in a basic block!");
862  getParent()->erase(this);
863}
864
865void MachineInstr::eraseFromBundle() {
866  assert(getParent() && "Not embedded in a basic block!");
867  getParent()->erase_instr(this);
868}
869
870/// getNumExplicitOperands - Returns the number of non-implicit operands.
871///
872unsigned MachineInstr::getNumExplicitOperands() const {
873  unsigned NumOperands = MCID->getNumOperands();
874  if (!MCID->isVariadic())
875    return NumOperands;
876
877  for (unsigned i = NumOperands, e = getNumOperands(); i != e; ++i) {
878    const MachineOperand &MO = getOperand(i);
879    if (!MO.isReg() || !MO.isImplicit())
880      NumOperands++;
881  }
882  return NumOperands;
883}
884
885void MachineInstr::bundleWithPred() {
886  assert(!isBundledWithPred() && "MI is already bundled with its predecessor");
887  setFlag(BundledPred);
888  MachineBasicBlock::instr_iterator Pred = this;
889  --Pred;
890  assert(!Pred->isBundledWithSucc() && "Inconsistent bundle flags");
891  Pred->setFlag(BundledSucc);
892}
893
894void MachineInstr::bundleWithSucc() {
895  assert(!isBundledWithSucc() && "MI is already bundled with its successor");
896  setFlag(BundledSucc);
897  MachineBasicBlock::instr_iterator Succ = this;
898  ++Succ;
899  assert(!Succ->isBundledWithPred() && "Inconsistent bundle flags");
900  Succ->setFlag(BundledPred);
901}
902
903void MachineInstr::unbundleFromPred() {
904  assert(isBundledWithPred() && "MI isn't bundled with its predecessor");
905  clearFlag(BundledPred);
906  MachineBasicBlock::instr_iterator Pred = this;
907  --Pred;
908  assert(Pred->isBundledWithSucc() && "Inconsistent bundle flags");
909  Pred->clearFlag(BundledSucc);
910}
911
912void MachineInstr::unbundleFromSucc() {
913  assert(isBundledWithSucc() && "MI isn't bundled with its successor");
914  clearFlag(BundledSucc);
915  MachineBasicBlock::instr_iterator Succ = this;
916  ++Succ;
917  assert(Succ->isBundledWithPred() && "Inconsistent bundle flags");
918  Succ->clearFlag(BundledPred);
919}
920
921bool MachineInstr::isStackAligningInlineAsm() const {
922  if (isInlineAsm()) {
923    unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
924    if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
925      return true;
926  }
927  return false;
928}
929
930InlineAsm::AsmDialect MachineInstr::getInlineAsmDialect() const {
931  assert(isInlineAsm() && "getInlineAsmDialect() only works for inline asms!");
932  unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
933  return InlineAsm::AsmDialect((ExtraInfo & InlineAsm::Extra_AsmDialect) != 0);
934}
935
936int MachineInstr::findInlineAsmFlagIdx(unsigned OpIdx,
937                                       unsigned *GroupNo) const {
938  assert(isInlineAsm() && "Expected an inline asm instruction");
939  assert(OpIdx < getNumOperands() && "OpIdx out of range");
940
941  // Ignore queries about the initial operands.
942  if (OpIdx < InlineAsm::MIOp_FirstOperand)
943    return -1;
944
945  unsigned Group = 0;
946  unsigned NumOps;
947  for (unsigned i = InlineAsm::MIOp_FirstOperand, e = getNumOperands(); i < e;
948       i += NumOps) {
949    const MachineOperand &FlagMO = getOperand(i);
950    // If we reach the implicit register operands, stop looking.
951    if (!FlagMO.isImm())
952      return -1;
953    NumOps = 1 + InlineAsm::getNumOperandRegisters(FlagMO.getImm());
954    if (i + NumOps > OpIdx) {
955      if (GroupNo)
956        *GroupNo = Group;
957      return i;
958    }
959    ++Group;
960  }
961  return -1;
962}
963
964const TargetRegisterClass*
965MachineInstr::getRegClassConstraint(unsigned OpIdx,
966                                    const TargetInstrInfo *TII,
967                                    const TargetRegisterInfo *TRI) const {
968  assert(getParent() && "Can't have an MBB reference here!");
969  assert(getParent()->getParent() && "Can't have an MF reference here!");
970  const MachineFunction &MF = *getParent()->getParent();
971
972  // Most opcodes have fixed constraints in their MCInstrDesc.
973  if (!isInlineAsm())
974    return TII->getRegClass(getDesc(), OpIdx, TRI, MF);
975
976  if (!getOperand(OpIdx).isReg())
977    return NULL;
978
979  // For tied uses on inline asm, get the constraint from the def.
980  unsigned DefIdx;
981  if (getOperand(OpIdx).isUse() && isRegTiedToDefOperand(OpIdx, &DefIdx))
982    OpIdx = DefIdx;
983
984  // Inline asm stores register class constraints in the flag word.
985  int FlagIdx = findInlineAsmFlagIdx(OpIdx);
986  if (FlagIdx < 0)
987    return NULL;
988
989  unsigned Flag = getOperand(FlagIdx).getImm();
990  unsigned RCID;
991  if (InlineAsm::hasRegClassConstraint(Flag, RCID))
992    return TRI->getRegClass(RCID);
993
994  // Assume that all registers in a memory operand are pointers.
995  if (InlineAsm::getKind(Flag) == InlineAsm::Kind_Mem)
996    return TRI->getPointerRegClass(MF);
997
998  return NULL;
999}
1000
1001const TargetRegisterClass *MachineInstr::getRegClassConstraintEffectForVReg(
1002    unsigned Reg, const TargetRegisterClass *CurRC, const TargetInstrInfo *TII,
1003    const TargetRegisterInfo *TRI, bool ExploreBundle) const {
1004  // Check every operands inside the bundle if we have
1005  // been asked to.
1006  if (ExploreBundle)
1007    for (ConstMIBundleOperands OpndIt(this); OpndIt.isValid() && CurRC;
1008         ++OpndIt)
1009      CurRC = OpndIt->getParent()->getRegClassConstraintEffectForVRegImpl(
1010          OpndIt.getOperandNo(), Reg, CurRC, TII, TRI);
1011  else
1012    // Otherwise, just check the current operands.
1013    for (ConstMIOperands OpndIt(this); OpndIt.isValid() && CurRC; ++OpndIt)
1014      CurRC = getRegClassConstraintEffectForVRegImpl(OpndIt.getOperandNo(), Reg,
1015                                                     CurRC, TII, TRI);
1016  return CurRC;
1017}
1018
1019const TargetRegisterClass *MachineInstr::getRegClassConstraintEffectForVRegImpl(
1020    unsigned OpIdx, unsigned Reg, const TargetRegisterClass *CurRC,
1021    const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const {
1022  assert(CurRC && "Invalid initial register class");
1023  // Check if Reg is constrained by some of its use/def from MI.
1024  const MachineOperand &MO = getOperand(OpIdx);
1025  if (!MO.isReg() || MO.getReg() != Reg)
1026    return CurRC;
1027  // If yes, accumulate the constraints through the operand.
1028  return getRegClassConstraintEffect(OpIdx, CurRC, TII, TRI);
1029}
1030
1031const TargetRegisterClass *MachineInstr::getRegClassConstraintEffect(
1032    unsigned OpIdx, const TargetRegisterClass *CurRC,
1033    const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const {
1034  const TargetRegisterClass *OpRC = getRegClassConstraint(OpIdx, TII, TRI);
1035  const MachineOperand &MO = getOperand(OpIdx);
1036  assert(MO.isReg() &&
1037         "Cannot get register constraints for non-register operand");
1038  assert(CurRC && "Invalid initial register class");
1039  if (unsigned SubIdx = MO.getSubReg()) {
1040    if (OpRC)
1041      CurRC = TRI->getMatchingSuperRegClass(CurRC, OpRC, SubIdx);
1042    else
1043      CurRC = TRI->getSubClassWithSubReg(CurRC, SubIdx);
1044  } else if (OpRC)
1045    CurRC = TRI->getCommonSubClass(CurRC, OpRC);
1046  return CurRC;
1047}
1048
1049/// Return the number of instructions inside the MI bundle, not counting the
1050/// header instruction.
1051unsigned MachineInstr::getBundleSize() const {
1052  MachineBasicBlock::const_instr_iterator I = this;
1053  unsigned Size = 0;
1054  while (I->isBundledWithSucc())
1055    ++Size, ++I;
1056  return Size;
1057}
1058
1059/// findRegisterUseOperandIdx() - Returns the MachineOperand that is a use of
1060/// the specific register or -1 if it is not found. It further tightens
1061/// the search criteria to a use that kills the register if isKill is true.
1062int MachineInstr::findRegisterUseOperandIdx(unsigned Reg, bool isKill,
1063                                          const TargetRegisterInfo *TRI) const {
1064  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1065    const MachineOperand &MO = getOperand(i);
1066    if (!MO.isReg() || !MO.isUse())
1067      continue;
1068    unsigned MOReg = MO.getReg();
1069    if (!MOReg)
1070      continue;
1071    if (MOReg == Reg ||
1072        (TRI &&
1073         TargetRegisterInfo::isPhysicalRegister(MOReg) &&
1074         TargetRegisterInfo::isPhysicalRegister(Reg) &&
1075         TRI->isSubRegister(MOReg, Reg)))
1076      if (!isKill || MO.isKill())
1077        return i;
1078  }
1079  return -1;
1080}
1081
1082/// readsWritesVirtualRegister - Return a pair of bools (reads, writes)
1083/// indicating if this instruction reads or writes Reg. This also considers
1084/// partial defines.
1085std::pair<bool,bool>
1086MachineInstr::readsWritesVirtualRegister(unsigned Reg,
1087                                         SmallVectorImpl<unsigned> *Ops) const {
1088  bool PartDef = false; // Partial redefine.
1089  bool FullDef = false; // Full define.
1090  bool Use = false;
1091
1092  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1093    const MachineOperand &MO = getOperand(i);
1094    if (!MO.isReg() || MO.getReg() != Reg)
1095      continue;
1096    if (Ops)
1097      Ops->push_back(i);
1098    if (MO.isUse())
1099      Use |= !MO.isUndef();
1100    else if (MO.getSubReg() && !MO.isUndef())
1101      // A partial <def,undef> doesn't count as reading the register.
1102      PartDef = true;
1103    else
1104      FullDef = true;
1105  }
1106  // A partial redefine uses Reg unless there is also a full define.
1107  return std::make_pair(Use || (PartDef && !FullDef), PartDef || FullDef);
1108}
1109
1110/// findRegisterDefOperandIdx() - Returns the operand index that is a def of
1111/// the specified register or -1 if it is not found. If isDead is true, defs
1112/// that are not dead are skipped. If TargetRegisterInfo is non-null, then it
1113/// also checks if there is a def of a super-register.
1114int
1115MachineInstr::findRegisterDefOperandIdx(unsigned Reg, bool isDead, bool Overlap,
1116                                        const TargetRegisterInfo *TRI) const {
1117  bool isPhys = TargetRegisterInfo::isPhysicalRegister(Reg);
1118  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1119    const MachineOperand &MO = getOperand(i);
1120    // Accept regmask operands when Overlap is set.
1121    // Ignore them when looking for a specific def operand (Overlap == false).
1122    if (isPhys && Overlap && MO.isRegMask() && MO.clobbersPhysReg(Reg))
1123      return i;
1124    if (!MO.isReg() || !MO.isDef())
1125      continue;
1126    unsigned MOReg = MO.getReg();
1127    bool Found = (MOReg == Reg);
1128    if (!Found && TRI && isPhys &&
1129        TargetRegisterInfo::isPhysicalRegister(MOReg)) {
1130      if (Overlap)
1131        Found = TRI->regsOverlap(MOReg, Reg);
1132      else
1133        Found = TRI->isSubRegister(MOReg, Reg);
1134    }
1135    if (Found && (!isDead || MO.isDead()))
1136      return i;
1137  }
1138  return -1;
1139}
1140
1141/// findFirstPredOperandIdx() - Find the index of the first operand in the
1142/// operand list that is used to represent the predicate. It returns -1 if
1143/// none is found.
1144int MachineInstr::findFirstPredOperandIdx() const {
1145  // Don't call MCID.findFirstPredOperandIdx() because this variant
1146  // is sometimes called on an instruction that's not yet complete, and
1147  // so the number of operands is less than the MCID indicates. In
1148  // particular, the PTX target does this.
1149  const MCInstrDesc &MCID = getDesc();
1150  if (MCID.isPredicable()) {
1151    for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
1152      if (MCID.OpInfo[i].isPredicate())
1153        return i;
1154  }
1155
1156  return -1;
1157}
1158
1159// MachineOperand::TiedTo is 4 bits wide.
1160const unsigned TiedMax = 15;
1161
1162/// tieOperands - Mark operands at DefIdx and UseIdx as tied to each other.
1163///
1164/// Use and def operands can be tied together, indicated by a non-zero TiedTo
1165/// field. TiedTo can have these values:
1166///
1167/// 0:              Operand is not tied to anything.
1168/// 1 to TiedMax-1: Tied to getOperand(TiedTo-1).
1169/// TiedMax:        Tied to an operand >= TiedMax-1.
1170///
1171/// The tied def must be one of the first TiedMax operands on a normal
1172/// instruction. INLINEASM instructions allow more tied defs.
1173///
1174void MachineInstr::tieOperands(unsigned DefIdx, unsigned UseIdx) {
1175  MachineOperand &DefMO = getOperand(DefIdx);
1176  MachineOperand &UseMO = getOperand(UseIdx);
1177  assert(DefMO.isDef() && "DefIdx must be a def operand");
1178  assert(UseMO.isUse() && "UseIdx must be a use operand");
1179  assert(!DefMO.isTied() && "Def is already tied to another use");
1180  assert(!UseMO.isTied() && "Use is already tied to another def");
1181
1182  if (DefIdx < TiedMax)
1183    UseMO.TiedTo = DefIdx + 1;
1184  else {
1185    // Inline asm can use the group descriptors to find tied operands, but on
1186    // normal instruction, the tied def must be within the first TiedMax
1187    // operands.
1188    assert(isInlineAsm() && "DefIdx out of range");
1189    UseMO.TiedTo = TiedMax;
1190  }
1191
1192  // UseIdx can be out of range, we'll search for it in findTiedOperandIdx().
1193  DefMO.TiedTo = std::min(UseIdx + 1, TiedMax);
1194}
1195
1196/// Given the index of a tied register operand, find the operand it is tied to.
1197/// Defs are tied to uses and vice versa. Returns the index of the tied operand
1198/// which must exist.
1199unsigned MachineInstr::findTiedOperandIdx(unsigned OpIdx) const {
1200  const MachineOperand &MO = getOperand(OpIdx);
1201  assert(MO.isTied() && "Operand isn't tied");
1202
1203  // Normally TiedTo is in range.
1204  if (MO.TiedTo < TiedMax)
1205    return MO.TiedTo - 1;
1206
1207  // Uses on normal instructions can be out of range.
1208  if (!isInlineAsm()) {
1209    // Normal tied defs must be in the 0..TiedMax-1 range.
1210    if (MO.isUse())
1211      return TiedMax - 1;
1212    // MO is a def. Search for the tied use.
1213    for (unsigned i = TiedMax - 1, e = getNumOperands(); i != e; ++i) {
1214      const MachineOperand &UseMO = getOperand(i);
1215      if (UseMO.isReg() && UseMO.isUse() && UseMO.TiedTo == OpIdx + 1)
1216        return i;
1217    }
1218    llvm_unreachable("Can't find tied use");
1219  }
1220
1221  // Now deal with inline asm by parsing the operand group descriptor flags.
1222  // Find the beginning of each operand group.
1223  SmallVector<unsigned, 8> GroupIdx;
1224  unsigned OpIdxGroup = ~0u;
1225  unsigned NumOps;
1226  for (unsigned i = InlineAsm::MIOp_FirstOperand, e = getNumOperands(); i < e;
1227       i += NumOps) {
1228    const MachineOperand &FlagMO = getOperand(i);
1229    assert(FlagMO.isImm() && "Invalid tied operand on inline asm");
1230    unsigned CurGroup = GroupIdx.size();
1231    GroupIdx.push_back(i);
1232    NumOps = 1 + InlineAsm::getNumOperandRegisters(FlagMO.getImm());
1233    // OpIdx belongs to this operand group.
1234    if (OpIdx > i && OpIdx < i + NumOps)
1235      OpIdxGroup = CurGroup;
1236    unsigned TiedGroup;
1237    if (!InlineAsm::isUseOperandTiedToDef(FlagMO.getImm(), TiedGroup))
1238      continue;
1239    // Operands in this group are tied to operands in TiedGroup which must be
1240    // earlier. Find the number of operands between the two groups.
1241    unsigned Delta = i - GroupIdx[TiedGroup];
1242
1243    // OpIdx is a use tied to TiedGroup.
1244    if (OpIdxGroup == CurGroup)
1245      return OpIdx - Delta;
1246
1247    // OpIdx is a def tied to this use group.
1248    if (OpIdxGroup == TiedGroup)
1249      return OpIdx + Delta;
1250  }
1251  llvm_unreachable("Invalid tied operand on inline asm");
1252}
1253
1254/// clearKillInfo - Clears kill flags on all operands.
1255///
1256void MachineInstr::clearKillInfo() {
1257  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1258    MachineOperand &MO = getOperand(i);
1259    if (MO.isReg() && MO.isUse())
1260      MO.setIsKill(false);
1261  }
1262}
1263
1264void MachineInstr::substituteRegister(unsigned FromReg,
1265                                      unsigned ToReg,
1266                                      unsigned SubIdx,
1267                                      const TargetRegisterInfo &RegInfo) {
1268  if (TargetRegisterInfo::isPhysicalRegister(ToReg)) {
1269    if (SubIdx)
1270      ToReg = RegInfo.getSubReg(ToReg, SubIdx);
1271    for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1272      MachineOperand &MO = getOperand(i);
1273      if (!MO.isReg() || MO.getReg() != FromReg)
1274        continue;
1275      MO.substPhysReg(ToReg, RegInfo);
1276    }
1277  } else {
1278    for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1279      MachineOperand &MO = getOperand(i);
1280      if (!MO.isReg() || MO.getReg() != FromReg)
1281        continue;
1282      MO.substVirtReg(ToReg, SubIdx, RegInfo);
1283    }
1284  }
1285}
1286
1287/// isSafeToMove - Return true if it is safe to move this instruction. If
1288/// SawStore is set to true, it means that there is a store (or call) between
1289/// the instruction's location and its intended destination.
1290bool MachineInstr::isSafeToMove(const TargetInstrInfo *TII,
1291                                AliasAnalysis *AA,
1292                                bool &SawStore) const {
1293  // Ignore stuff that we obviously can't move.
1294  //
1295  // Treat volatile loads as stores. This is not strictly necessary for
1296  // volatiles, but it is required for atomic loads. It is not allowed to move
1297  // a load across an atomic load with Ordering > Monotonic.
1298  if (mayStore() || isCall() ||
1299      (mayLoad() && hasOrderedMemoryRef())) {
1300    SawStore = true;
1301    return false;
1302  }
1303
1304  if (isPosition() || isDebugValue() || isTerminator() ||
1305      hasUnmodeledSideEffects())
1306    return false;
1307
1308  // See if this instruction does a load.  If so, we have to guarantee that the
1309  // loaded value doesn't change between the load and the its intended
1310  // destination. The check for isInvariantLoad gives the targe the chance to
1311  // classify the load as always returning a constant, e.g. a constant pool
1312  // load.
1313  if (mayLoad() && !isInvariantLoad(AA))
1314    // Otherwise, this is a real load.  If there is a store between the load and
1315    // end of block, we can't move it.
1316    return !SawStore;
1317
1318  return true;
1319}
1320
1321/// hasOrderedMemoryRef - Return true if this instruction may have an ordered
1322/// or volatile memory reference, or if the information describing the memory
1323/// reference is not available. Return false if it is known to have no ordered
1324/// memory references.
1325bool MachineInstr::hasOrderedMemoryRef() const {
1326  // An instruction known never to access memory won't have a volatile access.
1327  if (!mayStore() &&
1328      !mayLoad() &&
1329      !isCall() &&
1330      !hasUnmodeledSideEffects())
1331    return false;
1332
1333  // Otherwise, if the instruction has no memory reference information,
1334  // conservatively assume it wasn't preserved.
1335  if (memoperands_empty())
1336    return true;
1337
1338  // Check the memory reference information for ordered references.
1339  for (mmo_iterator I = memoperands_begin(), E = memoperands_end(); I != E; ++I)
1340    if (!(*I)->isUnordered())
1341      return true;
1342
1343  return false;
1344}
1345
1346/// isInvariantLoad - Return true if this instruction is loading from a
1347/// location whose value is invariant across the function.  For example,
1348/// loading a value from the constant pool or from the argument area
1349/// of a function if it does not change.  This should only return true of
1350/// *all* loads the instruction does are invariant (if it does multiple loads).
1351bool MachineInstr::isInvariantLoad(AliasAnalysis *AA) const {
1352  // If the instruction doesn't load at all, it isn't an invariant load.
1353  if (!mayLoad())
1354    return false;
1355
1356  // If the instruction has lost its memoperands, conservatively assume that
1357  // it may not be an invariant load.
1358  if (memoperands_empty())
1359    return false;
1360
1361  const MachineFrameInfo *MFI = getParent()->getParent()->getFrameInfo();
1362
1363  for (mmo_iterator I = memoperands_begin(),
1364       E = memoperands_end(); I != E; ++I) {
1365    if ((*I)->isVolatile()) return false;
1366    if ((*I)->isStore()) return false;
1367    if ((*I)->isInvariant()) return true;
1368
1369    if (const Value *V = (*I)->getValue()) {
1370      // A load from a constant PseudoSourceValue is invariant.
1371      if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V))
1372        if (PSV->isConstant(MFI))
1373          continue;
1374      // If we have an AliasAnalysis, ask it whether the memory is constant.
1375      if (AA && AA->pointsToConstantMemory(
1376                      AliasAnalysis::Location(V, (*I)->getSize(),
1377                                              (*I)->getTBAAInfo())))
1378        continue;
1379    }
1380
1381    // Otherwise assume conservatively.
1382    return false;
1383  }
1384
1385  // Everything checks out.
1386  return true;
1387}
1388
1389/// isConstantValuePHI - If the specified instruction is a PHI that always
1390/// merges together the same virtual register, return the register, otherwise
1391/// return 0.
1392unsigned MachineInstr::isConstantValuePHI() const {
1393  if (!isPHI())
1394    return 0;
1395  assert(getNumOperands() >= 3 &&
1396         "It's illegal to have a PHI without source operands");
1397
1398  unsigned Reg = getOperand(1).getReg();
1399  for (unsigned i = 3, e = getNumOperands(); i < e; i += 2)
1400    if (getOperand(i).getReg() != Reg)
1401      return 0;
1402  return Reg;
1403}
1404
1405bool MachineInstr::hasUnmodeledSideEffects() const {
1406  if (hasProperty(MCID::UnmodeledSideEffects))
1407    return true;
1408  if (isInlineAsm()) {
1409    unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
1410    if (ExtraInfo & InlineAsm::Extra_HasSideEffects)
1411      return true;
1412  }
1413
1414  return false;
1415}
1416
1417/// allDefsAreDead - Return true if all the defs of this instruction are dead.
1418///
1419bool MachineInstr::allDefsAreDead() const {
1420  for (unsigned i = 0, e = getNumOperands(); i < e; ++i) {
1421    const MachineOperand &MO = getOperand(i);
1422    if (!MO.isReg() || MO.isUse())
1423      continue;
1424    if (!MO.isDead())
1425      return false;
1426  }
1427  return true;
1428}
1429
1430/// copyImplicitOps - Copy implicit register operands from specified
1431/// instruction to this instruction.
1432void MachineInstr::copyImplicitOps(MachineFunction &MF,
1433                                   const MachineInstr *MI) {
1434  for (unsigned i = MI->getDesc().getNumOperands(), e = MI->getNumOperands();
1435       i != e; ++i) {
1436    const MachineOperand &MO = MI->getOperand(i);
1437    if ((MO.isReg() && MO.isImplicit()) || MO.isRegMask())
1438      addOperand(MF, MO);
1439  }
1440}
1441
1442void MachineInstr::dump() const {
1443#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1444  dbgs() << "  " << *this;
1445#endif
1446}
1447
1448static void printDebugLoc(DebugLoc DL, const MachineFunction *MF,
1449                         raw_ostream &CommentOS) {
1450  const LLVMContext &Ctx = MF->getFunction()->getContext();
1451  if (!DL.isUnknown()) {          // Print source line info.
1452    DIScope Scope(DL.getScope(Ctx));
1453    assert((!Scope || Scope.isScope()) &&
1454      "Scope of a DebugLoc should be null or a DIScope.");
1455    // Omit the directory, because it's likely to be long and uninteresting.
1456    if (Scope)
1457      CommentOS << Scope.getFilename();
1458    else
1459      CommentOS << "<unknown>";
1460    CommentOS << ':' << DL.getLine();
1461    if (DL.getCol() != 0)
1462      CommentOS << ':' << DL.getCol();
1463    DebugLoc InlinedAtDL = DebugLoc::getFromDILocation(DL.getInlinedAt(Ctx));
1464    if (!InlinedAtDL.isUnknown()) {
1465      CommentOS << " @[ ";
1466      printDebugLoc(InlinedAtDL, MF, CommentOS);
1467      CommentOS << " ]";
1468    }
1469  }
1470}
1471
1472void MachineInstr::print(raw_ostream &OS, const TargetMachine *TM,
1473                         bool SkipOpers) const {
1474  // We can be a bit tidier if we know the TargetMachine and/or MachineFunction.
1475  const MachineFunction *MF = 0;
1476  const MachineRegisterInfo *MRI = 0;
1477  if (const MachineBasicBlock *MBB = getParent()) {
1478    MF = MBB->getParent();
1479    if (!TM && MF)
1480      TM = &MF->getTarget();
1481    if (MF)
1482      MRI = &MF->getRegInfo();
1483  }
1484
1485  // Save a list of virtual registers.
1486  SmallVector<unsigned, 8> VirtRegs;
1487
1488  // Print explicitly defined operands on the left of an assignment syntax.
1489  unsigned StartOp = 0, e = getNumOperands();
1490  for (; StartOp < e && getOperand(StartOp).isReg() &&
1491         getOperand(StartOp).isDef() &&
1492         !getOperand(StartOp).isImplicit();
1493       ++StartOp) {
1494    if (StartOp != 0) OS << ", ";
1495    getOperand(StartOp).print(OS, TM);
1496    unsigned Reg = getOperand(StartOp).getReg();
1497    if (TargetRegisterInfo::isVirtualRegister(Reg))
1498      VirtRegs.push_back(Reg);
1499  }
1500
1501  if (StartOp != 0)
1502    OS << " = ";
1503
1504  // Print the opcode name.
1505  if (TM && TM->getInstrInfo())
1506    OS << TM->getInstrInfo()->getName(getOpcode());
1507  else
1508    OS << "UNKNOWN";
1509
1510  if (SkipOpers)
1511    return;
1512
1513  // Print the rest of the operands.
1514  bool OmittedAnyCallClobbers = false;
1515  bool FirstOp = true;
1516  unsigned AsmDescOp = ~0u;
1517  unsigned AsmOpCount = 0;
1518
1519  if (isInlineAsm() && e >= InlineAsm::MIOp_FirstOperand) {
1520    // Print asm string.
1521    OS << " ";
1522    getOperand(InlineAsm::MIOp_AsmString).print(OS, TM);
1523
1524    // Print HasSideEffects, MayLoad, MayStore, IsAlignStack
1525    unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
1526    if (ExtraInfo & InlineAsm::Extra_HasSideEffects)
1527      OS << " [sideeffect]";
1528    if (ExtraInfo & InlineAsm::Extra_MayLoad)
1529      OS << " [mayload]";
1530    if (ExtraInfo & InlineAsm::Extra_MayStore)
1531      OS << " [maystore]";
1532    if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
1533      OS << " [alignstack]";
1534    if (getInlineAsmDialect() == InlineAsm::AD_ATT)
1535      OS << " [attdialect]";
1536    if (getInlineAsmDialect() == InlineAsm::AD_Intel)
1537      OS << " [inteldialect]";
1538
1539    StartOp = AsmDescOp = InlineAsm::MIOp_FirstOperand;
1540    FirstOp = false;
1541  }
1542
1543
1544  for (unsigned i = StartOp, e = getNumOperands(); i != e; ++i) {
1545    const MachineOperand &MO = getOperand(i);
1546
1547    if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
1548      VirtRegs.push_back(MO.getReg());
1549
1550    // Omit call-clobbered registers which aren't used anywhere. This makes
1551    // call instructions much less noisy on targets where calls clobber lots
1552    // of registers. Don't rely on MO.isDead() because we may be called before
1553    // LiveVariables is run, or we may be looking at a non-allocatable reg.
1554    if (MF && isCall() &&
1555        MO.isReg() && MO.isImplicit() && MO.isDef()) {
1556      unsigned Reg = MO.getReg();
1557      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1558        const MachineRegisterInfo &MRI = MF->getRegInfo();
1559        if (MRI.use_empty(Reg)) {
1560          bool HasAliasLive = false;
1561          for (MCRegAliasIterator AI(Reg, TM->getRegisterInfo(), true);
1562               AI.isValid(); ++AI) {
1563            unsigned AliasReg = *AI;
1564            if (!MRI.use_empty(AliasReg)) {
1565              HasAliasLive = true;
1566              break;
1567            }
1568          }
1569          if (!HasAliasLive) {
1570            OmittedAnyCallClobbers = true;
1571            continue;
1572          }
1573        }
1574      }
1575    }
1576
1577    if (FirstOp) FirstOp = false; else OS << ",";
1578    OS << " ";
1579    if (i < getDesc().NumOperands) {
1580      const MCOperandInfo &MCOI = getDesc().OpInfo[i];
1581      if (MCOI.isPredicate())
1582        OS << "pred:";
1583      if (MCOI.isOptionalDef())
1584        OS << "opt:";
1585    }
1586    if (isDebugValue() && MO.isMetadata()) {
1587      // Pretty print DBG_VALUE instructions.
1588      const MDNode *MD = MO.getMetadata();
1589      if (const MDString *MDS = dyn_cast<MDString>(MD->getOperand(2)))
1590        OS << "!\"" << MDS->getString() << '\"';
1591      else
1592        MO.print(OS, TM);
1593    } else if (TM && (isInsertSubreg() || isRegSequence()) && MO.isImm()) {
1594      OS << TM->getRegisterInfo()->getSubRegIndexName(MO.getImm());
1595    } else if (i == AsmDescOp && MO.isImm()) {
1596      // Pretty print the inline asm operand descriptor.
1597      OS << '$' << AsmOpCount++;
1598      unsigned Flag = MO.getImm();
1599      switch (InlineAsm::getKind(Flag)) {
1600      case InlineAsm::Kind_RegUse:             OS << ":[reguse"; break;
1601      case InlineAsm::Kind_RegDef:             OS << ":[regdef"; break;
1602      case InlineAsm::Kind_RegDefEarlyClobber: OS << ":[regdef-ec"; break;
1603      case InlineAsm::Kind_Clobber:            OS << ":[clobber"; break;
1604      case InlineAsm::Kind_Imm:                OS << ":[imm"; break;
1605      case InlineAsm::Kind_Mem:                OS << ":[mem"; break;
1606      default: OS << ":[??" << InlineAsm::getKind(Flag); break;
1607      }
1608
1609      unsigned RCID = 0;
1610      if (InlineAsm::hasRegClassConstraint(Flag, RCID)) {
1611        if (TM)
1612          OS << ':' << TM->getRegisterInfo()->getRegClass(RCID)->getName();
1613        else
1614          OS << ":RC" << RCID;
1615      }
1616
1617      unsigned TiedTo = 0;
1618      if (InlineAsm::isUseOperandTiedToDef(Flag, TiedTo))
1619        OS << " tiedto:$" << TiedTo;
1620
1621      OS << ']';
1622
1623      // Compute the index of the next operand descriptor.
1624      AsmDescOp += 1 + InlineAsm::getNumOperandRegisters(Flag);
1625    } else
1626      MO.print(OS, TM);
1627  }
1628
1629  // Briefly indicate whether any call clobbers were omitted.
1630  if (OmittedAnyCallClobbers) {
1631    if (!FirstOp) OS << ",";
1632    OS << " ...";
1633  }
1634
1635  bool HaveSemi = false;
1636  const unsigned PrintableFlags = FrameSetup;
1637  if (Flags & PrintableFlags) {
1638    if (!HaveSemi) OS << ";"; HaveSemi = true;
1639    OS << " flags: ";
1640
1641    if (Flags & FrameSetup)
1642      OS << "FrameSetup";
1643  }
1644
1645  if (!memoperands_empty()) {
1646    if (!HaveSemi) OS << ";"; HaveSemi = true;
1647
1648    OS << " mem:";
1649    for (mmo_iterator i = memoperands_begin(), e = memoperands_end();
1650         i != e; ++i) {
1651      OS << **i;
1652      if (std::next(i) != e)
1653        OS << " ";
1654    }
1655  }
1656
1657  // Print the regclass of any virtual registers encountered.
1658  if (MRI && !VirtRegs.empty()) {
1659    if (!HaveSemi) OS << ";"; HaveSemi = true;
1660    for (unsigned i = 0; i != VirtRegs.size(); ++i) {
1661      const TargetRegisterClass *RC = MRI->getRegClass(VirtRegs[i]);
1662      OS << " " << RC->getName() << ':' << PrintReg(VirtRegs[i]);
1663      for (unsigned j = i+1; j != VirtRegs.size();) {
1664        if (MRI->getRegClass(VirtRegs[j]) != RC) {
1665          ++j;
1666          continue;
1667        }
1668        if (VirtRegs[i] != VirtRegs[j])
1669          OS << "," << PrintReg(VirtRegs[j]);
1670        VirtRegs.erase(VirtRegs.begin()+j);
1671      }
1672    }
1673  }
1674
1675  // Print debug location information.
1676  if (isDebugValue() && getOperand(e - 1).isMetadata()) {
1677    if (!HaveSemi) OS << ";";
1678    DIVariable DV(getOperand(e - 1).getMetadata());
1679    OS << " line no:" <<  DV.getLineNumber();
1680    if (MDNode *InlinedAt = DV.getInlinedAt()) {
1681      DebugLoc InlinedAtDL = DebugLoc::getFromDILocation(InlinedAt);
1682      if (!InlinedAtDL.isUnknown()) {
1683        OS << " inlined @[ ";
1684        printDebugLoc(InlinedAtDL, MF, OS);
1685        OS << " ]";
1686      }
1687    }
1688  } else if (!debugLoc.isUnknown() && MF) {
1689    if (!HaveSemi) OS << ";";
1690    OS << " dbg:";
1691    printDebugLoc(debugLoc, MF, OS);
1692  }
1693
1694  OS << '\n';
1695}
1696
1697bool MachineInstr::addRegisterKilled(unsigned IncomingReg,
1698                                     const TargetRegisterInfo *RegInfo,
1699                                     bool AddIfNotFound) {
1700  bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(IncomingReg);
1701  bool hasAliases = isPhysReg &&
1702    MCRegAliasIterator(IncomingReg, RegInfo, false).isValid();
1703  bool Found = false;
1704  SmallVector<unsigned,4> DeadOps;
1705  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1706    MachineOperand &MO = getOperand(i);
1707    if (!MO.isReg() || !MO.isUse() || MO.isUndef())
1708      continue;
1709    unsigned Reg = MO.getReg();
1710    if (!Reg)
1711      continue;
1712
1713    if (Reg == IncomingReg) {
1714      if (!Found) {
1715        if (MO.isKill())
1716          // The register is already marked kill.
1717          return true;
1718        if (isPhysReg && isRegTiedToDefOperand(i))
1719          // Two-address uses of physregs must not be marked kill.
1720          return true;
1721        MO.setIsKill();
1722        Found = true;
1723      }
1724    } else if (hasAliases && MO.isKill() &&
1725               TargetRegisterInfo::isPhysicalRegister(Reg)) {
1726      // A super-register kill already exists.
1727      if (RegInfo->isSuperRegister(IncomingReg, Reg))
1728        return true;
1729      if (RegInfo->isSubRegister(IncomingReg, Reg))
1730        DeadOps.push_back(i);
1731    }
1732  }
1733
1734  // Trim unneeded kill operands.
1735  while (!DeadOps.empty()) {
1736    unsigned OpIdx = DeadOps.back();
1737    if (getOperand(OpIdx).isImplicit())
1738      RemoveOperand(OpIdx);
1739    else
1740      getOperand(OpIdx).setIsKill(false);
1741    DeadOps.pop_back();
1742  }
1743
1744  // If not found, this means an alias of one of the operands is killed. Add a
1745  // new implicit operand if required.
1746  if (!Found && AddIfNotFound) {
1747    addOperand(MachineOperand::CreateReg(IncomingReg,
1748                                         false /*IsDef*/,
1749                                         true  /*IsImp*/,
1750                                         true  /*IsKill*/));
1751    return true;
1752  }
1753  return Found;
1754}
1755
1756void MachineInstr::clearRegisterKills(unsigned Reg,
1757                                      const TargetRegisterInfo *RegInfo) {
1758  if (!TargetRegisterInfo::isPhysicalRegister(Reg))
1759    RegInfo = 0;
1760  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1761    MachineOperand &MO = getOperand(i);
1762    if (!MO.isReg() || !MO.isUse() || !MO.isKill())
1763      continue;
1764    unsigned OpReg = MO.getReg();
1765    if (OpReg == Reg || (RegInfo && RegInfo->isSuperRegister(Reg, OpReg)))
1766      MO.setIsKill(false);
1767  }
1768}
1769
1770bool MachineInstr::addRegisterDead(unsigned Reg,
1771                                   const TargetRegisterInfo *RegInfo,
1772                                   bool AddIfNotFound) {
1773  bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(Reg);
1774  bool hasAliases = isPhysReg &&
1775    MCRegAliasIterator(Reg, RegInfo, false).isValid();
1776  bool Found = false;
1777  SmallVector<unsigned,4> DeadOps;
1778  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1779    MachineOperand &MO = getOperand(i);
1780    if (!MO.isReg() || !MO.isDef())
1781      continue;
1782    unsigned MOReg = MO.getReg();
1783    if (!MOReg)
1784      continue;
1785
1786    if (MOReg == Reg) {
1787      MO.setIsDead();
1788      Found = true;
1789    } else if (hasAliases && MO.isDead() &&
1790               TargetRegisterInfo::isPhysicalRegister(MOReg)) {
1791      // There exists a super-register that's marked dead.
1792      if (RegInfo->isSuperRegister(Reg, MOReg))
1793        return true;
1794      if (RegInfo->isSubRegister(Reg, MOReg))
1795        DeadOps.push_back(i);
1796    }
1797  }
1798
1799  // Trim unneeded dead operands.
1800  while (!DeadOps.empty()) {
1801    unsigned OpIdx = DeadOps.back();
1802    if (getOperand(OpIdx).isImplicit())
1803      RemoveOperand(OpIdx);
1804    else
1805      getOperand(OpIdx).setIsDead(false);
1806    DeadOps.pop_back();
1807  }
1808
1809  // If not found, this means an alias of one of the operands is dead. Add a
1810  // new implicit operand if required.
1811  if (Found || !AddIfNotFound)
1812    return Found;
1813
1814  addOperand(MachineOperand::CreateReg(Reg,
1815                                       true  /*IsDef*/,
1816                                       true  /*IsImp*/,
1817                                       false /*IsKill*/,
1818                                       true  /*IsDead*/));
1819  return true;
1820}
1821
1822void MachineInstr::addRegisterDefined(unsigned Reg,
1823                                      const TargetRegisterInfo *RegInfo) {
1824  if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1825    MachineOperand *MO = findRegisterDefOperand(Reg, false, RegInfo);
1826    if (MO)
1827      return;
1828  } else {
1829    for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1830      const MachineOperand &MO = getOperand(i);
1831      if (MO.isReg() && MO.getReg() == Reg && MO.isDef() &&
1832          MO.getSubReg() == 0)
1833        return;
1834    }
1835  }
1836  addOperand(MachineOperand::CreateReg(Reg,
1837                                       true  /*IsDef*/,
1838                                       true  /*IsImp*/));
1839}
1840
1841void MachineInstr::setPhysRegsDeadExcept(ArrayRef<unsigned> UsedRegs,
1842                                         const TargetRegisterInfo &TRI) {
1843  bool HasRegMask = false;
1844  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1845    MachineOperand &MO = getOperand(i);
1846    if (MO.isRegMask()) {
1847      HasRegMask = true;
1848      continue;
1849    }
1850    if (!MO.isReg() || !MO.isDef()) continue;
1851    unsigned Reg = MO.getReg();
1852    if (!TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
1853    bool Dead = true;
1854    for (ArrayRef<unsigned>::iterator I = UsedRegs.begin(), E = UsedRegs.end();
1855         I != E; ++I)
1856      if (TRI.regsOverlap(*I, Reg)) {
1857        Dead = false;
1858        break;
1859      }
1860    // If there are no uses, including partial uses, the def is dead.
1861    if (Dead) MO.setIsDead();
1862  }
1863
1864  // This is a call with a register mask operand.
1865  // Mask clobbers are always dead, so add defs for the non-dead defines.
1866  if (HasRegMask)
1867    for (ArrayRef<unsigned>::iterator I = UsedRegs.begin(), E = UsedRegs.end();
1868         I != E; ++I)
1869      addRegisterDefined(*I, &TRI);
1870}
1871
1872unsigned
1873MachineInstrExpressionTrait::getHashValue(const MachineInstr* const &MI) {
1874  // Build up a buffer of hash code components.
1875  SmallVector<size_t, 8> HashComponents;
1876  HashComponents.reserve(MI->getNumOperands() + 1);
1877  HashComponents.push_back(MI->getOpcode());
1878  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1879    const MachineOperand &MO = MI->getOperand(i);
1880    if (MO.isReg() && MO.isDef() &&
1881        TargetRegisterInfo::isVirtualRegister(MO.getReg()))
1882      continue;  // Skip virtual register defs.
1883
1884    HashComponents.push_back(hash_value(MO));
1885  }
1886  return hash_combine_range(HashComponents.begin(), HashComponents.end());
1887}
1888
1889void MachineInstr::emitError(StringRef Msg) const {
1890  // Find the source location cookie.
1891  unsigned LocCookie = 0;
1892  const MDNode *LocMD = 0;
1893  for (unsigned i = getNumOperands(); i != 0; --i) {
1894    if (getOperand(i-1).isMetadata() &&
1895        (LocMD = getOperand(i-1).getMetadata()) &&
1896        LocMD->getNumOperands() != 0) {
1897      if (const ConstantInt *CI = dyn_cast<ConstantInt>(LocMD->getOperand(0))) {
1898        LocCookie = CI->getZExtValue();
1899        break;
1900      }
1901    }
1902  }
1903
1904  if (const MachineBasicBlock *MBB = getParent())
1905    if (const MachineFunction *MF = MBB->getParent())
1906      return MF->getMMI().getModule()->getContext().emitError(LocCookie, Msg);
1907  report_fatal_error(Msg);
1908}
1909