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