MachineInstr.cpp revision 705e07f578e2b3af47ddab610feb4e7f2d3063a5 
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/InlineAsm.h"
17#include "llvm/Value.h"
18#include "llvm/CodeGen/MachineFunction.h"
19#include "llvm/CodeGen/MachineRegisterInfo.h"
20#include "llvm/CodeGen/PseudoSourceValue.h"
21#include "llvm/Target/TargetMachine.h"
22#include "llvm/Target/TargetInstrInfo.h"
23#include "llvm/Target/TargetInstrDesc.h"
24#include "llvm/Target/TargetRegisterInfo.h"
25#include "llvm/Analysis/DebugInfo.h"
26#include "llvm/Support/ErrorHandling.h"
27#include "llvm/Support/LeakDetector.h"
28#include "llvm/Support/MathExtras.h"
29#include "llvm/Support/Streams.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/ADT/FoldingSet.h"
32using namespace llvm;
33
34//===----------------------------------------------------------------------===//
35// MachineOperand Implementation
36//===----------------------------------------------------------------------===//
37
38/// AddRegOperandToRegInfo - Add this register operand to the specified
39/// MachineRegisterInfo.  If it is null, then the next/prev fields should be
40/// explicitly nulled out.
41void MachineOperand::AddRegOperandToRegInfo(MachineRegisterInfo *RegInfo) {
42  assert(isReg() && "Can only add reg operand to use lists");
43
44  // If the reginfo pointer is null, just explicitly null out or next/prev
45  // pointers, to ensure they are not garbage.
46  if (RegInfo == 0) {
47    Contents.Reg.Prev = 0;
48    Contents.Reg.Next = 0;
49    return;
50  }
51
52  // Otherwise, add this operand to the head of the registers use/def list.
53  MachineOperand **Head = &RegInfo->getRegUseDefListHead(getReg());
54
55  // For SSA values, we prefer to keep the definition at the start of the list.
56  // we do this by skipping over the definition if it is at the head of the
57  // list.
58  if (*Head && (*Head)->isDef())
59    Head = &(*Head)->Contents.Reg.Next;
60
61  Contents.Reg.Next = *Head;
62  if (Contents.Reg.Next) {
63    assert(getReg() == Contents.Reg.Next->getReg() &&
64           "Different regs on the same list!");
65    Contents.Reg.Next->Contents.Reg.Prev = &Contents.Reg.Next;
66  }
67
68  Contents.Reg.Prev = Head;
69  *Head = this;
70}
71
72/// RemoveRegOperandFromRegInfo - Remove this register operand from the
73/// MachineRegisterInfo it is linked with.
74void MachineOperand::RemoveRegOperandFromRegInfo() {
75  assert(isOnRegUseList() && "Reg operand is not on a use list");
76  // Unlink this from the doubly linked list of operands.
77  MachineOperand *NextOp = Contents.Reg.Next;
78  *Contents.Reg.Prev = NextOp;
79  if (NextOp) {
80    assert(NextOp->getReg() == getReg() && "Corrupt reg use/def chain!");
81    NextOp->Contents.Reg.Prev = Contents.Reg.Prev;
82  }
83  Contents.Reg.Prev = 0;
84  Contents.Reg.Next = 0;
85}
86
87void MachineOperand::setReg(unsigned Reg) {
88  if (getReg() == Reg) return; // No change.
89
90  // Otherwise, we have to change the register.  If this operand is embedded
91  // into a machine function, we need to update the old and new register's
92  // use/def lists.
93  if (MachineInstr *MI = getParent())
94    if (MachineBasicBlock *MBB = MI->getParent())
95      if (MachineFunction *MF = MBB->getParent()) {
96        RemoveRegOperandFromRegInfo();
97        Contents.Reg.RegNo = Reg;
98        AddRegOperandToRegInfo(&MF->getRegInfo());
99        return;
100      }
101
102  // Otherwise, just change the register, no problem.  :)
103  Contents.Reg.RegNo = Reg;
104}
105
106/// ChangeToImmediate - Replace this operand with a new immediate operand of
107/// the specified value.  If an operand is known to be an immediate already,
108/// the setImm method should be used.
109void MachineOperand::ChangeToImmediate(int64_t ImmVal) {
110  // If this operand is currently a register operand, and if this is in a
111  // function, deregister the operand from the register's use/def list.
112  if (isReg() && getParent() && getParent()->getParent() &&
113      getParent()->getParent()->getParent())
114    RemoveRegOperandFromRegInfo();
115
116  OpKind = MO_Immediate;
117  Contents.ImmVal = ImmVal;
118}
119
120/// ChangeToRegister - Replace this operand with a new register operand of
121/// the specified value.  If an operand is known to be an register already,
122/// the setReg method should be used.
123void MachineOperand::ChangeToRegister(unsigned Reg, bool isDef, bool isImp,
124                                      bool isKill, bool isDead, bool isUndef) {
125  // If this operand is already a register operand, use setReg to update the
126  // register's use/def lists.
127  if (isReg()) {
128    assert(!isEarlyClobber());
129    setReg(Reg);
130  } else {
131    // Otherwise, change this to a register and set the reg#.
132    OpKind = MO_Register;
133    Contents.Reg.RegNo = Reg;
134
135    // If this operand is embedded in a function, add the operand to the
136    // register's use/def list.
137    if (MachineInstr *MI = getParent())
138      if (MachineBasicBlock *MBB = MI->getParent())
139        if (MachineFunction *MF = MBB->getParent())
140          AddRegOperandToRegInfo(&MF->getRegInfo());
141  }
142
143  IsDef = isDef;
144  IsImp = isImp;
145  IsKill = isKill;
146  IsDead = isDead;
147  IsUndef = isUndef;
148  IsEarlyClobber = false;
149  SubReg = 0;
150}
151
152/// isIdenticalTo - Return true if this operand is identical to the specified
153/// operand.
154bool MachineOperand::isIdenticalTo(const MachineOperand &Other) const {
155  if (getType() != Other.getType() ||
156      getTargetFlags() != Other.getTargetFlags())
157    return false;
158
159  switch (getType()) {
160  default: llvm_unreachable("Unrecognized operand type");
161  case MachineOperand::MO_Register:
162    return getReg() == Other.getReg() && isDef() == Other.isDef() &&
163           getSubReg() == Other.getSubReg();
164  case MachineOperand::MO_Immediate:
165    return getImm() == Other.getImm();
166  case MachineOperand::MO_FPImmediate:
167    return getFPImm() == Other.getFPImm();
168  case MachineOperand::MO_MachineBasicBlock:
169    return getMBB() == Other.getMBB();
170  case MachineOperand::MO_FrameIndex:
171    return getIndex() == Other.getIndex();
172  case MachineOperand::MO_ConstantPoolIndex:
173    return getIndex() == Other.getIndex() && getOffset() == Other.getOffset();
174  case MachineOperand::MO_JumpTableIndex:
175    return getIndex() == Other.getIndex();
176  case MachineOperand::MO_GlobalAddress:
177    return getGlobal() == Other.getGlobal() && getOffset() == Other.getOffset();
178  case MachineOperand::MO_ExternalSymbol:
179    return !strcmp(getSymbolName(), Other.getSymbolName()) &&
180           getOffset() == Other.getOffset();
181  }
182}
183
184/// print - Print the specified machine operand.
185///
186void MachineOperand::print(raw_ostream &OS, const TargetMachine *TM) const {
187  switch (getType()) {
188  case MachineOperand::MO_Register:
189    if (getReg() == 0 || TargetRegisterInfo::isVirtualRegister(getReg())) {
190      OS << "%reg" << getReg();
191    } else {
192      // If the instruction is embedded into a basic block, we can find the
193      // target info for the instruction.
194      if (TM == 0)
195        if (const MachineInstr *MI = getParent())
196          if (const MachineBasicBlock *MBB = MI->getParent())
197            if (const MachineFunction *MF = MBB->getParent())
198              TM = &MF->getTarget();
199
200      if (TM)
201        OS << "%" << TM->getRegisterInfo()->get(getReg()).Name;
202      else
203        OS << "%mreg" << getReg();
204    }
205
206    if (getSubReg() != 0)
207      OS << ':' << getSubReg();
208
209    if (isDef() || isKill() || isDead() || isImplicit() || isUndef() ||
210        isEarlyClobber()) {
211      OS << '<';
212      bool NeedComma = false;
213      if (isImplicit()) {
214        if (NeedComma) OS << ',';
215        OS << (isDef() ? "imp-def" : "imp-use");
216        NeedComma = true;
217      } else if (isDef()) {
218        if (NeedComma) OS << ',';
219        if (isEarlyClobber())
220          OS << "earlyclobber,";
221        OS << "def";
222        NeedComma = true;
223      }
224      if (isKill() || isDead() || isUndef()) {
225        if (NeedComma) OS << ',';
226        if (isKill())  OS << "kill";
227        if (isDead())  OS << "dead";
228        if (isUndef()) {
229          if (isKill() || isDead())
230            OS << ',';
231          OS << "undef";
232        }
233      }
234      OS << '>';
235    }
236    break;
237  case MachineOperand::MO_Immediate:
238    OS << getImm();
239    break;
240  case MachineOperand::MO_FPImmediate:
241    if (getFPImm()->getType() == Type::getFloatTy(getFPImm()->getContext()))
242      OS << getFPImm()->getValueAPF().convertToFloat();
243    else
244      OS << getFPImm()->getValueAPF().convertToDouble();
245    break;
246  case MachineOperand::MO_MachineBasicBlock:
247    OS << "mbb<"
248       << ((Value*)getMBB()->getBasicBlock())->getName()
249       << "," << (void*)getMBB() << '>';
250    break;
251  case MachineOperand::MO_FrameIndex:
252    OS << "<fi#" << getIndex() << '>';
253    break;
254  case MachineOperand::MO_ConstantPoolIndex:
255    OS << "<cp#" << getIndex();
256    if (getOffset()) OS << "+" << getOffset();
257    OS << '>';
258    break;
259  case MachineOperand::MO_JumpTableIndex:
260    OS << "<jt#" << getIndex() << '>';
261    break;
262  case MachineOperand::MO_GlobalAddress:
263    OS << "<ga:" << ((Value*)getGlobal())->getName();
264    if (getOffset()) OS << "+" << getOffset();
265    OS << '>';
266    break;
267  case MachineOperand::MO_ExternalSymbol:
268    OS << "<es:" << getSymbolName();
269    if (getOffset()) OS << "+" << getOffset();
270    OS << '>';
271    break;
272  default:
273    llvm_unreachable("Unrecognized operand type");
274  }
275
276  if (unsigned TF = getTargetFlags())
277    OS << "[TF=" << TF << ']';
278}
279
280//===----------------------------------------------------------------------===//
281// MachineMemOperand Implementation
282//===----------------------------------------------------------------------===//
283
284MachineMemOperand::MachineMemOperand(const Value *v, unsigned int f,
285                                     int64_t o, uint64_t s, unsigned int a)
286  : Offset(o), Size(s), V(v),
287    Flags((f & 7) | ((Log2_32(a) + 1) << 3)) {
288  assert(isPowerOf2_32(a) && "Alignment is not a power of 2!");
289  assert((isLoad() || isStore()) && "Not a load/store!");
290}
291
292/// Profile - Gather unique data for the object.
293///
294void MachineMemOperand::Profile(FoldingSetNodeID &ID) const {
295  ID.AddInteger(Offset);
296  ID.AddInteger(Size);
297  ID.AddPointer(V);
298  ID.AddInteger(Flags);
299}
300
301//===----------------------------------------------------------------------===//
302// MachineInstr Implementation
303//===----------------------------------------------------------------------===//
304
305/// MachineInstr ctor - This constructor creates a dummy MachineInstr with
306/// TID NULL and no operands.
307MachineInstr::MachineInstr()
308  : TID(0), NumImplicitOps(0), Parent(0), debugLoc(DebugLoc::getUnknownLoc()) {
309  // Make sure that we get added to a machine basicblock
310  LeakDetector::addGarbageObject(this);
311}
312
313void MachineInstr::addImplicitDefUseOperands() {
314  if (TID->ImplicitDefs)
315    for (const unsigned *ImpDefs = TID->ImplicitDefs; *ImpDefs; ++ImpDefs)
316      addOperand(MachineOperand::CreateReg(*ImpDefs, true, true));
317  if (TID->ImplicitUses)
318    for (const unsigned *ImpUses = TID->ImplicitUses; *ImpUses; ++ImpUses)
319      addOperand(MachineOperand::CreateReg(*ImpUses, false, true));
320}
321
322/// MachineInstr ctor - This constructor create a MachineInstr and add the
323/// implicit operands. It reserves space for number of operands specified by
324/// TargetInstrDesc or the numOperands if it is not zero. (for
325/// instructions with variable number of operands).
326MachineInstr::MachineInstr(const TargetInstrDesc &tid, bool NoImp)
327  : TID(&tid), NumImplicitOps(0), Parent(0),
328    debugLoc(DebugLoc::getUnknownLoc()) {
329  if (!NoImp && TID->getImplicitDefs())
330    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
331      NumImplicitOps++;
332  if (!NoImp && TID->getImplicitUses())
333    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
334      NumImplicitOps++;
335  Operands.reserve(NumImplicitOps + TID->getNumOperands());
336  if (!NoImp)
337    addImplicitDefUseOperands();
338  // Make sure that we get added to a machine basicblock
339  LeakDetector::addGarbageObject(this);
340}
341
342/// MachineInstr ctor - As above, but with a DebugLoc.
343MachineInstr::MachineInstr(const TargetInstrDesc &tid, const DebugLoc dl,
344                           bool NoImp)
345  : TID(&tid), NumImplicitOps(0), Parent(0), debugLoc(dl) {
346  if (!NoImp && TID->getImplicitDefs())
347    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
348      NumImplicitOps++;
349  if (!NoImp && TID->getImplicitUses())
350    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
351      NumImplicitOps++;
352  Operands.reserve(NumImplicitOps + TID->getNumOperands());
353  if (!NoImp)
354    addImplicitDefUseOperands();
355  // Make sure that we get added to a machine basicblock
356  LeakDetector::addGarbageObject(this);
357}
358
359/// MachineInstr ctor - Work exactly the same as the ctor two above, except
360/// that the MachineInstr is created and added to the end of the specified
361/// basic block.
362///
363MachineInstr::MachineInstr(MachineBasicBlock *MBB, const TargetInstrDesc &tid)
364  : TID(&tid), NumImplicitOps(0), Parent(0),
365    debugLoc(DebugLoc::getUnknownLoc()) {
366  assert(MBB && "Cannot use inserting ctor with null basic block!");
367  if (TID->ImplicitDefs)
368    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
369      NumImplicitOps++;
370  if (TID->ImplicitUses)
371    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
372      NumImplicitOps++;
373  Operands.reserve(NumImplicitOps + TID->getNumOperands());
374  addImplicitDefUseOperands();
375  // Make sure that we get added to a machine basicblock
376  LeakDetector::addGarbageObject(this);
377  MBB->push_back(this);  // Add instruction to end of basic block!
378}
379
380/// MachineInstr ctor - As above, but with a DebugLoc.
381///
382MachineInstr::MachineInstr(MachineBasicBlock *MBB, const DebugLoc dl,
383                           const TargetInstrDesc &tid)
384  : TID(&tid), NumImplicitOps(0), Parent(0), debugLoc(dl) {
385  assert(MBB && "Cannot use inserting ctor with null basic block!");
386  if (TID->ImplicitDefs)
387    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
388      NumImplicitOps++;
389  if (TID->ImplicitUses)
390    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
391      NumImplicitOps++;
392  Operands.reserve(NumImplicitOps + TID->getNumOperands());
393  addImplicitDefUseOperands();
394  // Make sure that we get added to a machine basicblock
395  LeakDetector::addGarbageObject(this);
396  MBB->push_back(this);  // Add instruction to end of basic block!
397}
398
399/// MachineInstr ctor - Copies MachineInstr arg exactly
400///
401MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI)
402  : TID(&MI.getDesc()), NumImplicitOps(0), Parent(0),
403        debugLoc(MI.getDebugLoc()) {
404  Operands.reserve(MI.getNumOperands());
405
406  // Add operands
407  for (unsigned i = 0; i != MI.getNumOperands(); ++i)
408    addOperand(MI.getOperand(i));
409  NumImplicitOps = MI.NumImplicitOps;
410
411  // Add memory operands.
412  for (std::list<MachineMemOperand>::const_iterator i = MI.memoperands_begin(),
413       j = MI.memoperands_end(); i != j; ++i)
414    addMemOperand(MF, *i);
415
416  // Set parent to null.
417  Parent = 0;
418
419  LeakDetector::addGarbageObject(this);
420}
421
422MachineInstr::~MachineInstr() {
423  LeakDetector::removeGarbageObject(this);
424  assert(MemOperands.empty() &&
425         "MachineInstr being deleted with live memoperands!");
426#ifndef NDEBUG
427  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
428    assert(Operands[i].ParentMI == this && "ParentMI mismatch!");
429    assert((!Operands[i].isReg() || !Operands[i].isOnRegUseList()) &&
430           "Reg operand def/use list corrupted");
431  }
432#endif
433}
434
435/// getRegInfo - If this instruction is embedded into a MachineFunction,
436/// return the MachineRegisterInfo object for the current function, otherwise
437/// return null.
438MachineRegisterInfo *MachineInstr::getRegInfo() {
439  if (MachineBasicBlock *MBB = getParent())
440    return &MBB->getParent()->getRegInfo();
441  return 0;
442}
443
444/// RemoveRegOperandsFromUseLists - Unlink all of the register operands in
445/// this instruction from their respective use lists.  This requires that the
446/// operands already be on their use lists.
447void MachineInstr::RemoveRegOperandsFromUseLists() {
448  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
449    if (Operands[i].isReg())
450      Operands[i].RemoveRegOperandFromRegInfo();
451  }
452}
453
454/// AddRegOperandsToUseLists - Add all of the register operands in
455/// this instruction from their respective use lists.  This requires that the
456/// operands not be on their use lists yet.
457void MachineInstr::AddRegOperandsToUseLists(MachineRegisterInfo &RegInfo) {
458  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
459    if (Operands[i].isReg())
460      Operands[i].AddRegOperandToRegInfo(&RegInfo);
461  }
462}
463
464
465/// addOperand - Add the specified operand to the instruction.  If it is an
466/// implicit operand, it is added to the end of the operand list.  If it is
467/// an explicit operand it is added at the end of the explicit operand list
468/// (before the first implicit operand).
469void MachineInstr::addOperand(const MachineOperand &Op) {
470  bool isImpReg = Op.isReg() && Op.isImplicit();
471  assert((isImpReg || !OperandsComplete()) &&
472         "Trying to add an operand to a machine instr that is already done!");
473
474  MachineRegisterInfo *RegInfo = getRegInfo();
475
476  // If we are adding the operand to the end of the list, our job is simpler.
477  // This is true most of the time, so this is a reasonable optimization.
478  if (isImpReg || NumImplicitOps == 0) {
479    // We can only do this optimization if we know that the operand list won't
480    // reallocate.
481    if (Operands.empty() || Operands.size()+1 <= Operands.capacity()) {
482      Operands.push_back(Op);
483
484      // Set the parent of the operand.
485      Operands.back().ParentMI = this;
486
487      // If the operand is a register, update the operand's use list.
488      if (Op.isReg())
489        Operands.back().AddRegOperandToRegInfo(RegInfo);
490      return;
491    }
492  }
493
494  // Otherwise, we have to insert a real operand before any implicit ones.
495  unsigned OpNo = Operands.size()-NumImplicitOps;
496
497  // If this instruction isn't embedded into a function, then we don't need to
498  // update any operand lists.
499  if (RegInfo == 0) {
500    // Simple insertion, no reginfo update needed for other register operands.
501    Operands.insert(Operands.begin()+OpNo, Op);
502    Operands[OpNo].ParentMI = this;
503
504    // Do explicitly set the reginfo for this operand though, to ensure the
505    // next/prev fields are properly nulled out.
506    if (Operands[OpNo].isReg())
507      Operands[OpNo].AddRegOperandToRegInfo(0);
508
509  } else if (Operands.size()+1 <= Operands.capacity()) {
510    // Otherwise, we have to remove register operands from their register use
511    // list, add the operand, then add the register operands back to their use
512    // list.  This also must handle the case when the operand list reallocates
513    // to somewhere else.
514
515    // If insertion of this operand won't cause reallocation of the operand
516    // list, just remove the implicit operands, add the operand, then re-add all
517    // the rest of the operands.
518    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
519      assert(Operands[i].isReg() && "Should only be an implicit reg!");
520      Operands[i].RemoveRegOperandFromRegInfo();
521    }
522
523    // Add the operand.  If it is a register, add it to the reg list.
524    Operands.insert(Operands.begin()+OpNo, Op);
525    Operands[OpNo].ParentMI = this;
526
527    if (Operands[OpNo].isReg())
528      Operands[OpNo].AddRegOperandToRegInfo(RegInfo);
529
530    // Re-add all the implicit ops.
531    for (unsigned i = OpNo+1, e = Operands.size(); i != e; ++i) {
532      assert(Operands[i].isReg() && "Should only be an implicit reg!");
533      Operands[i].AddRegOperandToRegInfo(RegInfo);
534    }
535  } else {
536    // Otherwise, we will be reallocating the operand list.  Remove all reg
537    // operands from their list, then readd them after the operand list is
538    // reallocated.
539    RemoveRegOperandsFromUseLists();
540
541    Operands.insert(Operands.begin()+OpNo, Op);
542    Operands[OpNo].ParentMI = this;
543
544    // Re-add all the operands.
545    AddRegOperandsToUseLists(*RegInfo);
546  }
547}
548
549/// RemoveOperand - Erase an operand  from an instruction, leaving it with one
550/// fewer operand than it started with.
551///
552void MachineInstr::RemoveOperand(unsigned OpNo) {
553  assert(OpNo < Operands.size() && "Invalid operand number");
554
555  // Special case removing the last one.
556  if (OpNo == Operands.size()-1) {
557    // If needed, remove from the reg def/use list.
558    if (Operands.back().isReg() && Operands.back().isOnRegUseList())
559      Operands.back().RemoveRegOperandFromRegInfo();
560
561    Operands.pop_back();
562    return;
563  }
564
565  // Otherwise, we are removing an interior operand.  If we have reginfo to
566  // update, remove all operands that will be shifted down from their reg lists,
567  // move everything down, then re-add them.
568  MachineRegisterInfo *RegInfo = getRegInfo();
569  if (RegInfo) {
570    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
571      if (Operands[i].isReg())
572        Operands[i].RemoveRegOperandFromRegInfo();
573    }
574  }
575
576  Operands.erase(Operands.begin()+OpNo);
577
578  if (RegInfo) {
579    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
580      if (Operands[i].isReg())
581        Operands[i].AddRegOperandToRegInfo(RegInfo);
582    }
583  }
584}
585
586/// addMemOperand - Add a MachineMemOperand to the machine instruction,
587/// referencing arbitrary storage.
588void MachineInstr::addMemOperand(MachineFunction &MF,
589                                 const MachineMemOperand &MO) {
590  MemOperands.push_back(MO);
591}
592
593/// clearMemOperands - Erase all of this MachineInstr's MachineMemOperands.
594void MachineInstr::clearMemOperands(MachineFunction &MF) {
595  MemOperands.clear();
596}
597
598
599/// removeFromParent - This method unlinks 'this' from the containing basic
600/// block, and returns it, but does not delete it.
601MachineInstr *MachineInstr::removeFromParent() {
602  assert(getParent() && "Not embedded in a basic block!");
603  getParent()->remove(this);
604  return this;
605}
606
607
608/// eraseFromParent - This method unlinks 'this' from the containing basic
609/// block, and deletes it.
610void MachineInstr::eraseFromParent() {
611  assert(getParent() && "Not embedded in a basic block!");
612  getParent()->erase(this);
613}
614
615
616/// OperandComplete - Return true if it's illegal to add a new operand
617///
618bool MachineInstr::OperandsComplete() const {
619  unsigned short NumOperands = TID->getNumOperands();
620  if (!TID->isVariadic() && getNumOperands()-NumImplicitOps >= NumOperands)
621    return true;  // Broken: we have all the operands of this instruction!
622  return false;
623}
624
625/// getNumExplicitOperands - Returns the number of non-implicit operands.
626///
627unsigned MachineInstr::getNumExplicitOperands() const {
628  unsigned NumOperands = TID->getNumOperands();
629  if (!TID->isVariadic())
630    return NumOperands;
631
632  for (unsigned i = NumOperands, e = getNumOperands(); i != e; ++i) {
633    const MachineOperand &MO = getOperand(i);
634    if (!MO.isReg() || !MO.isImplicit())
635      NumOperands++;
636  }
637  return NumOperands;
638}
639
640
641/// isLabel - Returns true if the MachineInstr represents a label.
642///
643bool MachineInstr::isLabel() const {
644  return getOpcode() == TargetInstrInfo::DBG_LABEL ||
645         getOpcode() == TargetInstrInfo::EH_LABEL ||
646         getOpcode() == TargetInstrInfo::GC_LABEL;
647}
648
649/// isDebugLabel - Returns true if the MachineInstr represents a debug label.
650///
651bool MachineInstr::isDebugLabel() const {
652  return getOpcode() == TargetInstrInfo::DBG_LABEL;
653}
654
655/// findRegisterUseOperandIdx() - Returns the MachineOperand that is a use of
656/// the specific register or -1 if it is not found. It further tightening
657/// the search criteria to a use that kills the register if isKill is true.
658int MachineInstr::findRegisterUseOperandIdx(unsigned Reg, bool isKill,
659                                          const TargetRegisterInfo *TRI) const {
660  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
661    const MachineOperand &MO = getOperand(i);
662    if (!MO.isReg() || !MO.isUse())
663      continue;
664    unsigned MOReg = MO.getReg();
665    if (!MOReg)
666      continue;
667    if (MOReg == Reg ||
668        (TRI &&
669         TargetRegisterInfo::isPhysicalRegister(MOReg) &&
670         TargetRegisterInfo::isPhysicalRegister(Reg) &&
671         TRI->isSubRegister(MOReg, Reg)))
672      if (!isKill || MO.isKill())
673        return i;
674  }
675  return -1;
676}
677
678/// findRegisterDefOperandIdx() - Returns the operand index that is a def of
679/// the specified register or -1 if it is not found. If isDead is true, defs
680/// that are not dead are skipped. If TargetRegisterInfo is non-null, then it
681/// also checks if there is a def of a super-register.
682int MachineInstr::findRegisterDefOperandIdx(unsigned Reg, bool isDead,
683                                          const TargetRegisterInfo *TRI) const {
684  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
685    const MachineOperand &MO = getOperand(i);
686    if (!MO.isReg() || !MO.isDef())
687      continue;
688    unsigned MOReg = MO.getReg();
689    if (MOReg == Reg ||
690        (TRI &&
691         TargetRegisterInfo::isPhysicalRegister(MOReg) &&
692         TargetRegisterInfo::isPhysicalRegister(Reg) &&
693         TRI->isSubRegister(MOReg, Reg)))
694      if (!isDead || MO.isDead())
695        return i;
696  }
697  return -1;
698}
699
700/// findFirstPredOperandIdx() - Find the index of the first operand in the
701/// operand list that is used to represent the predicate. It returns -1 if
702/// none is found.
703int MachineInstr::findFirstPredOperandIdx() const {
704  const TargetInstrDesc &TID = getDesc();
705  if (TID.isPredicable()) {
706    for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
707      if (TID.OpInfo[i].isPredicate())
708        return i;
709  }
710
711  return -1;
712}
713
714/// isRegTiedToUseOperand - Given the index of a register def operand,
715/// check if the register def is tied to a source operand, due to either
716/// two-address elimination or inline assembly constraints. Returns the
717/// first tied use operand index by reference is UseOpIdx is not null.
718bool MachineInstr::
719isRegTiedToUseOperand(unsigned DefOpIdx, unsigned *UseOpIdx) const {
720  if (getOpcode() == TargetInstrInfo::INLINEASM) {
721    assert(DefOpIdx >= 2);
722    const MachineOperand &MO = getOperand(DefOpIdx);
723    if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0)
724      return false;
725    // Determine the actual operand index that corresponds to this index.
726    unsigned DefNo = 0;
727    unsigned DefPart = 0;
728    for (unsigned i = 1, e = getNumOperands(); i < e; ) {
729      const MachineOperand &FMO = getOperand(i);
730      // After the normal asm operands there may be additional imp-def regs.
731      if (!FMO.isImm())
732        return false;
733      // Skip over this def.
734      unsigned NumOps = InlineAsm::getNumOperandRegisters(FMO.getImm());
735      unsigned PrevDef = i + 1;
736      i = PrevDef + NumOps;
737      if (i > DefOpIdx) {
738        DefPart = DefOpIdx - PrevDef;
739        break;
740      }
741      ++DefNo;
742    }
743    for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
744      const MachineOperand &FMO = getOperand(i);
745      if (!FMO.isImm())
746        continue;
747      if (i+1 >= e || !getOperand(i+1).isReg() || !getOperand(i+1).isUse())
748        continue;
749      unsigned Idx;
750      if (InlineAsm::isUseOperandTiedToDef(FMO.getImm(), Idx) &&
751          Idx == DefNo) {
752        if (UseOpIdx)
753          *UseOpIdx = (unsigned)i + 1 + DefPart;
754        return true;
755      }
756    }
757    return false;
758  }
759
760  assert(getOperand(DefOpIdx).isDef() && "DefOpIdx is not a def!");
761  const TargetInstrDesc &TID = getDesc();
762  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
763    const MachineOperand &MO = getOperand(i);
764    if (MO.isReg() && MO.isUse() &&
765        TID.getOperandConstraint(i, TOI::TIED_TO) == (int)DefOpIdx) {
766      if (UseOpIdx)
767        *UseOpIdx = (unsigned)i;
768      return true;
769    }
770  }
771  return false;
772}
773
774/// isRegTiedToDefOperand - Return true if the operand of the specified index
775/// is a register use and it is tied to an def operand. It also returns the def
776/// operand index by reference.
777bool MachineInstr::
778isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx) const {
779  if (getOpcode() == TargetInstrInfo::INLINEASM) {
780    const MachineOperand &MO = getOperand(UseOpIdx);
781    if (!MO.isReg() || !MO.isUse() || MO.getReg() == 0)
782      return false;
783
784    // Find the flag operand corresponding to UseOpIdx
785    unsigned FlagIdx, NumOps=0;
786    for (FlagIdx = 1; FlagIdx < UseOpIdx; FlagIdx += NumOps+1) {
787      const MachineOperand &UFMO = getOperand(FlagIdx);
788      // After the normal asm operands there may be additional imp-def regs.
789      if (!UFMO.isImm())
790        return false;
791      NumOps = InlineAsm::getNumOperandRegisters(UFMO.getImm());
792      assert(NumOps < getNumOperands() && "Invalid inline asm flag");
793      if (UseOpIdx < FlagIdx+NumOps+1)
794        break;
795    }
796    if (FlagIdx >= UseOpIdx)
797      return false;
798    const MachineOperand &UFMO = getOperand(FlagIdx);
799    unsigned DefNo;
800    if (InlineAsm::isUseOperandTiedToDef(UFMO.getImm(), DefNo)) {
801      if (!DefOpIdx)
802        return true;
803
804      unsigned DefIdx = 1;
805      // Remember to adjust the index. First operand is asm string, then there
806      // is a flag for each.
807      while (DefNo) {
808        const MachineOperand &FMO = getOperand(DefIdx);
809        assert(FMO.isImm());
810        // Skip over this def.
811        DefIdx += InlineAsm::getNumOperandRegisters(FMO.getImm()) + 1;
812        --DefNo;
813      }
814      *DefOpIdx = DefIdx + UseOpIdx - FlagIdx;
815      return true;
816    }
817    return false;
818  }
819
820  const TargetInstrDesc &TID = getDesc();
821  if (UseOpIdx >= TID.getNumOperands())
822    return false;
823  const MachineOperand &MO = getOperand(UseOpIdx);
824  if (!MO.isReg() || !MO.isUse())
825    return false;
826  int DefIdx = TID.getOperandConstraint(UseOpIdx, TOI::TIED_TO);
827  if (DefIdx == -1)
828    return false;
829  if (DefOpIdx)
830    *DefOpIdx = (unsigned)DefIdx;
831  return true;
832}
833
834/// copyKillDeadInfo - Copies kill / dead operand properties from MI.
835///
836void MachineInstr::copyKillDeadInfo(const MachineInstr *MI) {
837  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
838    const MachineOperand &MO = MI->getOperand(i);
839    if (!MO.isReg() || (!MO.isKill() && !MO.isDead()))
840      continue;
841    for (unsigned j = 0, ee = getNumOperands(); j != ee; ++j) {
842      MachineOperand &MOp = getOperand(j);
843      if (!MOp.isIdenticalTo(MO))
844        continue;
845      if (MO.isKill())
846        MOp.setIsKill();
847      else
848        MOp.setIsDead();
849      break;
850    }
851  }
852}
853
854/// copyPredicates - Copies predicate operand(s) from MI.
855void MachineInstr::copyPredicates(const MachineInstr *MI) {
856  const TargetInstrDesc &TID = MI->getDesc();
857  if (!TID.isPredicable())
858    return;
859  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
860    if (TID.OpInfo[i].isPredicate()) {
861      // Predicated operands must be last operands.
862      addOperand(MI->getOperand(i));
863    }
864  }
865}
866
867/// isSafeToMove - Return true if it is safe to move this instruction. If
868/// SawStore is set to true, it means that there is a store (or call) between
869/// the instruction's location and its intended destination.
870bool MachineInstr::isSafeToMove(const TargetInstrInfo *TII,
871                                bool &SawStore) const {
872  // Ignore stuff that we obviously can't move.
873  if (TID->mayStore() || TID->isCall()) {
874    SawStore = true;
875    return false;
876  }
877  if (TID->isTerminator() || TID->hasUnmodeledSideEffects())
878    return false;
879
880  // See if this instruction does a load.  If so, we have to guarantee that the
881  // loaded value doesn't change between the load and the its intended
882  // destination. The check for isInvariantLoad gives the targe the chance to
883  // classify the load as always returning a constant, e.g. a constant pool
884  // load.
885  if (TID->mayLoad() && !TII->isInvariantLoad(this))
886    // Otherwise, this is a real load.  If there is a store between the load and
887    // end of block, or if the load is volatile, we can't move it.
888    return !SawStore && !hasVolatileMemoryRef();
889
890  return true;
891}
892
893/// isSafeToReMat - Return true if it's safe to rematerialize the specified
894/// instruction which defined the specified register instead of copying it.
895bool MachineInstr::isSafeToReMat(const TargetInstrInfo *TII,
896                                 unsigned DstReg) const {
897  bool SawStore = false;
898  if (!getDesc().isRematerializable() ||
899      !TII->isTriviallyReMaterializable(this) ||
900      !isSafeToMove(TII, SawStore))
901    return false;
902  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
903    const MachineOperand &MO = getOperand(i);
904    if (!MO.isReg())
905      continue;
906    // FIXME: For now, do not remat any instruction with register operands.
907    // Later on, we can loosen the restriction is the register operands have
908    // not been modified between the def and use. Note, this is different from
909    // MachineSink because the code is no longer in two-address form (at least
910    // partially).
911    if (MO.isUse())
912      return false;
913    else if (!MO.isDead() && MO.getReg() != DstReg)
914      return false;
915  }
916  return true;
917}
918
919/// hasVolatileMemoryRef - Return true if this instruction may have a
920/// volatile memory reference, or if the information describing the
921/// memory reference is not available. Return false if it is known to
922/// have no volatile memory references.
923bool MachineInstr::hasVolatileMemoryRef() const {
924  // An instruction known never to access memory won't have a volatile access.
925  if (!TID->mayStore() &&
926      !TID->mayLoad() &&
927      !TID->isCall() &&
928      !TID->hasUnmodeledSideEffects())
929    return false;
930
931  // Otherwise, if the instruction has no memory reference information,
932  // conservatively assume it wasn't preserved.
933  if (memoperands_empty())
934    return true;
935
936  // Check the memory reference information for volatile references.
937  for (std::list<MachineMemOperand>::const_iterator I = memoperands_begin(),
938       E = memoperands_end(); I != E; ++I)
939    if (I->isVolatile())
940      return true;
941
942  return false;
943}
944
945void MachineInstr::dump() const {
946  errs() << "  " << *this;
947}
948
949void MachineInstr::print(raw_ostream &OS, const TargetMachine *TM) const {
950  // Specialize printing if op#0 is definition
951  unsigned StartOp = 0;
952  if (getNumOperands() && getOperand(0).isReg() && getOperand(0).isDef()) {
953    getOperand(0).print(OS, TM);
954    OS << " = ";
955    ++StartOp;   // Don't print this operand again!
956  }
957
958  OS << getDesc().getName();
959
960  for (unsigned i = StartOp, e = getNumOperands(); i != e; ++i) {
961    if (i != StartOp)
962      OS << ",";
963    OS << " ";
964    getOperand(i).print(OS, TM);
965  }
966
967  if (!memoperands_empty()) {
968    OS << ", Mem:";
969    for (std::list<MachineMemOperand>::const_iterator i = memoperands_begin(),
970         e = memoperands_end(); i != e; ++i) {
971      const MachineMemOperand &MRO = *i;
972      const Value *V = MRO.getValue();
973
974      assert((MRO.isLoad() || MRO.isStore()) &&
975             "SV has to be a load, store or both.");
976
977      if (MRO.isVolatile())
978        OS << "Volatile ";
979
980      if (MRO.isLoad())
981        OS << "LD";
982      if (MRO.isStore())
983        OS << "ST";
984
985      OS << "(" << MRO.getSize() << "," << MRO.getAlignment() << ") [";
986
987      if (!V)
988        OS << "<unknown>";
989      else if (!V->getName().empty())
990        OS << V->getName();
991      else if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
992        PSV->print(OS);
993      } else
994        OS << V;
995
996      OS << " + " << MRO.getOffset() << "]";
997    }
998  }
999
1000  if (!debugLoc.isUnknown()) {
1001    const MachineFunction *MF = getParent()->getParent();
1002    DebugLocTuple DLT = MF->getDebugLocTuple(debugLoc);
1003    DICompileUnit CU(DLT.CompileUnit);
1004    std::string Dir, Fn;
1005    OS << " [dbg: "
1006       << CU.getDirectory(Dir) << '/' << CU.getFilename(Fn) << ","
1007       << DLT.Line << ","
1008       << DLT.Col  << "]";
1009  }
1010
1011  OS << "\n";
1012}
1013
1014bool MachineInstr::addRegisterKilled(unsigned IncomingReg,
1015                                     const TargetRegisterInfo *RegInfo,
1016                                     bool AddIfNotFound) {
1017  bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(IncomingReg);
1018  bool hasAliases = isPhysReg && RegInfo->getAliasSet(IncomingReg);
1019  bool Found = false;
1020  SmallVector<unsigned,4> DeadOps;
1021  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1022    MachineOperand &MO = getOperand(i);
1023    if (!MO.isReg() || !MO.isUse() || MO.isUndef())
1024      continue;
1025    unsigned Reg = MO.getReg();
1026    if (!Reg)
1027      continue;
1028
1029    if (Reg == IncomingReg) {
1030      if (!Found) {
1031        if (MO.isKill())
1032          // The register is already marked kill.
1033          return true;
1034        if (isPhysReg && isRegTiedToDefOperand(i))
1035          // Two-address uses of physregs must not be marked kill.
1036          return true;
1037        MO.setIsKill();
1038        Found = true;
1039      }
1040    } else if (hasAliases && MO.isKill() &&
1041               TargetRegisterInfo::isPhysicalRegister(Reg)) {
1042      // A super-register kill already exists.
1043      if (RegInfo->isSuperRegister(IncomingReg, Reg))
1044        return true;
1045      if (RegInfo->isSubRegister(IncomingReg, Reg))
1046        DeadOps.push_back(i);
1047    }
1048  }
1049
1050  // Trim unneeded kill operands.
1051  while (!DeadOps.empty()) {
1052    unsigned OpIdx = DeadOps.back();
1053    if (getOperand(OpIdx).isImplicit())
1054      RemoveOperand(OpIdx);
1055    else
1056      getOperand(OpIdx).setIsKill(false);
1057    DeadOps.pop_back();
1058  }
1059
1060  // If not found, this means an alias of one of the operands is killed. Add a
1061  // new implicit operand if required.
1062  if (!Found && AddIfNotFound) {
1063    addOperand(MachineOperand::CreateReg(IncomingReg,
1064                                         false /*IsDef*/,
1065                                         true  /*IsImp*/,
1066                                         true  /*IsKill*/));
1067    return true;
1068  }
1069  return Found;
1070}
1071
1072bool MachineInstr::addRegisterDead(unsigned IncomingReg,
1073                                   const TargetRegisterInfo *RegInfo,
1074                                   bool AddIfNotFound) {
1075  bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(IncomingReg);
1076  bool hasAliases = isPhysReg && RegInfo->getAliasSet(IncomingReg);
1077  bool Found = false;
1078  SmallVector<unsigned,4> DeadOps;
1079  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1080    MachineOperand &MO = getOperand(i);
1081    if (!MO.isReg() || !MO.isDef())
1082      continue;
1083    unsigned Reg = MO.getReg();
1084    if (!Reg)
1085      continue;
1086
1087    if (Reg == IncomingReg) {
1088      if (!Found) {
1089        if (MO.isDead())
1090          // The register is already marked dead.
1091          return true;
1092        MO.setIsDead();
1093        Found = true;
1094      }
1095    } else if (hasAliases && MO.isDead() &&
1096               TargetRegisterInfo::isPhysicalRegister(Reg)) {
1097      // There exists a super-register that's marked dead.
1098      if (RegInfo->isSuperRegister(IncomingReg, Reg))
1099        return true;
1100      if (RegInfo->getSubRegisters(IncomingReg) &&
1101          RegInfo->getSuperRegisters(Reg) &&
1102          RegInfo->isSubRegister(IncomingReg, Reg))
1103        DeadOps.push_back(i);
1104    }
1105  }
1106
1107  // Trim unneeded dead operands.
1108  while (!DeadOps.empty()) {
1109    unsigned OpIdx = DeadOps.back();
1110    if (getOperand(OpIdx).isImplicit())
1111      RemoveOperand(OpIdx);
1112    else
1113      getOperand(OpIdx).setIsDead(false);
1114    DeadOps.pop_back();
1115  }
1116
1117  // If not found, this means an alias of one of the operands is dead. Add a
1118  // new implicit operand if required.
1119  if (Found || !AddIfNotFound)
1120    return Found;
1121
1122  addOperand(MachineOperand::CreateReg(IncomingReg,
1123                                       true  /*IsDef*/,
1124                                       true  /*IsImp*/,
1125                                       false /*IsKill*/,
1126                                       true  /*IsDead*/));
1127  return true;
1128}
1129