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