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