LLVM API Documentation

MachineInstr.cpp

Go to the documentation of this file.
00001 //===-- lib/CodeGen/MachineInstr.cpp --------------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Methods common to all machine instructions.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/CodeGen/MachineInstr.h"
00015 #include "llvm/Constants.h"
00016 #include "llvm/InlineAsm.h"
00017 #include "llvm/Value.h"
00018 #include "llvm/CodeGen/MachineFunction.h"
00019 #include "llvm/CodeGen/MachineRegisterInfo.h"
00020 #include "llvm/CodeGen/PseudoSourceValue.h"
00021 #include "llvm/Target/TargetMachine.h"
00022 #include "llvm/Target/TargetInstrInfo.h"
00023 #include "llvm/Target/TargetInstrDesc.h"
00024 #include "llvm/Target/TargetRegisterInfo.h"
00025 #include "llvm/Analysis/DebugInfo.h"
00026 #include "llvm/Support/ErrorHandling.h"
00027 #include "llvm/Support/LeakDetector.h"
00028 #include "llvm/Support/MathExtras.h"
00029 #include "llvm/Support/Streams.h"
00030 #include "llvm/Support/raw_ostream.h"
00031 #include "llvm/ADT/FoldingSet.h"
00032 using namespace llvm;
00033 
00034 //===----------------------------------------------------------------------===//
00035 // MachineOperand Implementation
00036 //===----------------------------------------------------------------------===//
00037 
00038 /// AddRegOperandToRegInfo - Add this register operand to the specified
00039 /// MachineRegisterInfo.  If it is null, then the next/prev fields should be
00040 /// explicitly nulled out.
00041 void MachineOperand::AddRegOperandToRegInfo(MachineRegisterInfo *RegInfo) {
00042   assert(isReg() && "Can only add reg operand to use lists");
00043   
00044   // If the reginfo pointer is null, just explicitly null out or next/prev
00045   // pointers, to ensure they are not garbage.
00046   if (RegInfo == 0) {
00047     Contents.Reg.Prev = 0;
00048     Contents.Reg.Next = 0;
00049     return;
00050   }
00051   
00052   // Otherwise, add this operand to the head of the registers use/def list.
00053   MachineOperand **Head = &RegInfo->getRegUseDefListHead(getReg());
00054   
00055   // For SSA values, we prefer to keep the definition at the start of the list.
00056   // we do this by skipping over the definition if it is at the head of the
00057   // list.
00058   if (*Head && (*Head)->isDef())
00059     Head = &(*Head)->Contents.Reg.Next;
00060   
00061   Contents.Reg.Next = *Head;
00062   if (Contents.Reg.Next) {
00063     assert(getReg() == Contents.Reg.Next->getReg() &&
00064            "Different regs on the same list!");
00065     Contents.Reg.Next->Contents.Reg.Prev = &Contents.Reg.Next;
00066   }
00067   
00068   Contents.Reg.Prev = Head;
00069   *Head = this;
00070 }
00071 
00072 /// RemoveRegOperandFromRegInfo - Remove this register operand from the
00073 /// MachineRegisterInfo it is linked with.
00074 void MachineOperand::RemoveRegOperandFromRegInfo() {
00075   assert(isOnRegUseList() && "Reg operand is not on a use list");
00076   // Unlink this from the doubly linked list of operands.
00077   MachineOperand *NextOp = Contents.Reg.Next;
00078   *Contents.Reg.Prev = NextOp; 
00079   if (NextOp) {
00080     assert(NextOp->getReg() == getReg() && "Corrupt reg use/def chain!");
00081     NextOp->Contents.Reg.Prev = Contents.Reg.Prev;
00082   }
00083   Contents.Reg.Prev = 0;
00084   Contents.Reg.Next = 0;
00085 }
00086 
00087 void MachineOperand::setReg(unsigned Reg) {
00088   if (getReg() == Reg) return; // No change.
00089   
00090   // Otherwise, we have to change the register.  If this operand is embedded
00091   // into a machine function, we need to update the old and new register's
00092   // use/def lists.
00093   if (MachineInstr *MI = getParent())
00094     if (MachineBasicBlock *MBB = MI->getParent())
00095       if (MachineFunction *MF = MBB->getParent()) {
00096         RemoveRegOperandFromRegInfo();
00097         Contents.Reg.RegNo = Reg;
00098         AddRegOperandToRegInfo(&MF->getRegInfo());
00099         return;
00100       }
00101         
00102   // Otherwise, just change the register, no problem.  :)
00103   Contents.Reg.RegNo = Reg;
00104 }
00105 
00106 /// ChangeToImmediate - Replace this operand with a new immediate operand of
00107 /// the specified value.  If an operand is known to be an immediate already,
00108 /// the setImm method should be used.
00109 void MachineOperand::ChangeToImmediate(int64_t ImmVal) {
00110   // If this operand is currently a register operand, and if this is in a
00111   // function, deregister the operand from the register's use/def list.
00112   if (isReg() && getParent() && getParent()->getParent() &&
00113       getParent()->getParent()->getParent())
00114     RemoveRegOperandFromRegInfo();
00115   
00116   OpKind = MO_Immediate;
00117   Contents.ImmVal = ImmVal;
00118 }
00119 
00120 /// ChangeToRegister - Replace this operand with a new register operand of
00121 /// the specified value.  If an operand is known to be an register already,
00122 /// the setReg method should be used.
00123 void MachineOperand::ChangeToRegister(unsigned Reg, bool isDef, bool isImp,
00124                                       bool isKill, bool isDead, bool isUndef) {
00125   // If this operand is already a register operand, use setReg to update the 
00126   // register's use/def lists.
00127   if (isReg()) {
00128     assert(!isEarlyClobber());
00129     setReg(Reg);
00130   } else {
00131     // Otherwise, change this to a register and set the reg#.
00132     OpKind = MO_Register;
00133     Contents.Reg.RegNo = Reg;
00134 
00135     // If this operand is embedded in a function, add the operand to the
00136     // register's use/def list.
00137     if (MachineInstr *MI = getParent())
00138       if (MachineBasicBlock *MBB = MI->getParent())
00139         if (MachineFunction *MF = MBB->getParent())
00140           AddRegOperandToRegInfo(&MF->getRegInfo());
00141   }
00142 
00143   IsDef = isDef;
00144   IsImp = isImp;
00145   IsKill = isKill;
00146   IsDead = isDead;
00147   IsUndef = isUndef;
00148   IsEarlyClobber = false;
00149   SubReg = 0;
00150 }
00151 
00152 /// isIdenticalTo - Return true if this operand is identical to the specified
00153 /// operand.
00154 bool MachineOperand::isIdenticalTo(const MachineOperand &Other) const {
00155   if (getType() != Other.getType() ||
00156       getTargetFlags() != Other.getTargetFlags())
00157     return false;
00158   
00159   switch (getType()) {
00160   default: llvm_unreachable("Unrecognized operand type");
00161   case MachineOperand::MO_Register:
00162     return getReg() == Other.getReg() && isDef() == Other.isDef() &&
00163            getSubReg() == Other.getSubReg();
00164   case MachineOperand::MO_Immediate:
00165     return getImm() == Other.getImm();
00166   case MachineOperand::MO_FPImmediate:
00167     return getFPImm() == Other.getFPImm();
00168   case MachineOperand::MO_MachineBasicBlock:
00169     return getMBB() == Other.getMBB();
00170   case MachineOperand::MO_FrameIndex:
00171     return getIndex() == Other.getIndex();
00172   case MachineOperand::MO_ConstantPoolIndex:
00173     return getIndex() == Other.getIndex() && getOffset() == Other.getOffset();
00174   case MachineOperand::MO_JumpTableIndex:
00175     return getIndex() == Other.getIndex();
00176   case MachineOperand::MO_GlobalAddress:
00177     return getGlobal() == Other.getGlobal() && getOffset() == Other.getOffset();
00178   case MachineOperand::MO_ExternalSymbol:
00179     return !strcmp(getSymbolName(), Other.getSymbolName()) &&
00180            getOffset() == Other.getOffset();
00181   }
00182 }
00183 
00184 /// print - Print the specified machine operand.
00185 ///
00186 void MachineOperand::print(std::ostream &OS, const TargetMachine *TM) const {
00187   raw_os_ostream RawOS(OS);
00188   print(RawOS, TM);
00189 }
00190 
00191 void MachineOperand::print(raw_ostream &OS, const TargetMachine *TM) const {
00192   switch (getType()) {
00193   case MachineOperand::MO_Register:
00194     if (getReg() == 0 || TargetRegisterInfo::isVirtualRegister(getReg())) {
00195       OS << "%reg" << getReg();
00196     } else {
00197       // If the instruction is embedded into a basic block, we can find the
00198       // target info for the instruction.
00199       if (TM == 0)
00200         if (const MachineInstr *MI = getParent())
00201           if (const MachineBasicBlock *MBB = MI->getParent())
00202             if (const MachineFunction *MF = MBB->getParent())
00203               TM = &MF->getTarget();
00204       
00205       if (TM)
00206         OS << "%" << TM->getRegisterInfo()->get(getReg()).Name;
00207       else
00208         OS << "%mreg" << getReg();
00209     }
00210 
00211     if (getSubReg() != 0)
00212       OS << ':' << getSubReg();
00213 
00214     if (isDef() || isKill() || isDead() || isImplicit() || isUndef() ||
00215         isEarlyClobber()) {
00216       OS << '<';
00217       bool NeedComma = false;
00218       if (isImplicit()) {
00219         if (NeedComma) OS << ',';
00220         OS << (isDef() ? "imp-def" : "imp-use");
00221         NeedComma = true;
00222       } else if (isDef()) {
00223         if (NeedComma) OS << ',';
00224         if (isEarlyClobber())
00225           OS << "earlyclobber,";
00226         OS << "def";
00227         NeedComma = true;
00228       }
00229       if (isKill() || isDead() || isUndef()) {
00230         if (NeedComma) OS << ',';
00231         if (isKill())  OS << "kill";
00232         if (isDead())  OS << "dead";
00233         if (isUndef()) {
00234           if (isKill() || isDead())
00235             OS << ',';
00236           OS << "undef";
00237         }
00238       }
00239       OS << '>';
00240     }
00241     break;
00242   case MachineOperand::MO_Immediate:
00243     OS << getImm();
00244     break;
00245   case MachineOperand::MO_FPImmediate:
00246     if (getFPImm()->getType() == Type::getFloatTy(getFPImm()->getContext()))
00247       OS << getFPImm()->getValueAPF().convertToFloat();
00248     else
00249       OS << getFPImm()->getValueAPF().convertToDouble();
00250     break;
00251   case MachineOperand::MO_MachineBasicBlock:
00252     OS << "mbb<"
00253        << ((Value*)getMBB()->getBasicBlock())->getName()
00254        << "," << (void*)getMBB() << '>';
00255     break;
00256   case MachineOperand::MO_FrameIndex:
00257     OS << "<fi#" << getIndex() << '>';
00258     break;
00259   case MachineOperand::MO_ConstantPoolIndex:
00260     OS << "<cp#" << getIndex();
00261     if (getOffset()) OS << "+" << getOffset();
00262     OS << '>';
00263     break;
00264   case MachineOperand::MO_JumpTableIndex:
00265     OS << "<jt#" << getIndex() << '>';
00266     break;
00267   case MachineOperand::MO_GlobalAddress:
00268     OS << "<ga:" << ((Value*)getGlobal())->getName();
00269     if (getOffset()) OS << "+" << getOffset();
00270     OS << '>';
00271     break;
00272   case MachineOperand::MO_ExternalSymbol:
00273     OS << "<es:" << getSymbolName();
00274     if (getOffset()) OS << "+" << getOffset();
00275     OS << '>';
00276     break;
00277   default:
00278     llvm_unreachable("Unrecognized operand type");
00279   }
00280   
00281   if (unsigned TF = getTargetFlags())
00282     OS << "[TF=" << TF << ']';
00283 }
00284 
00285 //===----------------------------------------------------------------------===//
00286 // MachineMemOperand Implementation
00287 //===----------------------------------------------------------------------===//
00288 
00289 MachineMemOperand::MachineMemOperand(const Value *v, unsigned int f,
00290                                      int64_t o, uint64_t s, unsigned int a)
00291   : Offset(o), Size(s), V(v),
00292     Flags((f & 7) | ((Log2_32(a) + 1) << 3)) {
00293   assert(isPowerOf2_32(a) && "Alignment is not a power of 2!");
00294   assert((isLoad() || isStore()) && "Not a load/store!");
00295 }
00296 
00297 /// Profile - Gather unique data for the object.
00298 ///
00299 void MachineMemOperand::Profile(FoldingSetNodeID &ID) const {
00300   ID.AddInteger(Offset);
00301   ID.AddInteger(Size);
00302   ID.AddPointer(V);
00303   ID.AddInteger(Flags);
00304 }
00305 
00306 //===----------------------------------------------------------------------===//
00307 // MachineInstr Implementation
00308 //===----------------------------------------------------------------------===//
00309 
00310 /// MachineInstr ctor - This constructor creates a dummy MachineInstr with
00311 /// TID NULL and no operands.
00312 MachineInstr::MachineInstr()
00313   : TID(0), NumImplicitOps(0), Parent(0), debugLoc(DebugLoc::getUnknownLoc()) {
00314   // Make sure that we get added to a machine basicblock
00315   LeakDetector::addGarbageObject(this);
00316 }
00317 
00318 void MachineInstr::addImplicitDefUseOperands() {
00319   if (TID->ImplicitDefs)
00320     for (const unsigned *ImpDefs = TID->ImplicitDefs; *ImpDefs; ++ImpDefs)
00321       addOperand(MachineOperand::CreateReg(*ImpDefs, true, true));
00322   if (TID->ImplicitUses)
00323     for (const unsigned *ImpUses = TID->ImplicitUses; *ImpUses; ++ImpUses)
00324       addOperand(MachineOperand::CreateReg(*ImpUses, false, true));
00325 }
00326 
00327 /// MachineInstr ctor - This constructor create a MachineInstr and add the
00328 /// implicit operands. It reserves space for number of operands specified by
00329 /// TargetInstrDesc or the numOperands if it is not zero. (for
00330 /// instructions with variable number of operands).
00331 MachineInstr::MachineInstr(const TargetInstrDesc &tid, bool NoImp)
00332   : TID(&tid), NumImplicitOps(0), Parent(0), 
00333     debugLoc(DebugLoc::getUnknownLoc()) {
00334   if (!NoImp && TID->getImplicitDefs())
00335     for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
00336       NumImplicitOps++;
00337   if (!NoImp && TID->getImplicitUses())
00338     for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
00339       NumImplicitOps++;
00340   Operands.reserve(NumImplicitOps + TID->getNumOperands());
00341   if (!NoImp)
00342     addImplicitDefUseOperands();
00343   // Make sure that we get added to a machine basicblock
00344   LeakDetector::addGarbageObject(this);
00345 }
00346 
00347 /// MachineInstr ctor - As above, but with a DebugLoc.
00348 MachineInstr::MachineInstr(const TargetInstrDesc &tid, const DebugLoc dl,
00349                            bool NoImp)
00350   : TID(&tid), NumImplicitOps(0), Parent(0), debugLoc(dl) {
00351   if (!NoImp && TID->getImplicitDefs())
00352     for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
00353       NumImplicitOps++;
00354   if (!NoImp && TID->getImplicitUses())
00355     for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
00356       NumImplicitOps++;
00357   Operands.reserve(NumImplicitOps + TID->getNumOperands());
00358   if (!NoImp)
00359     addImplicitDefUseOperands();
00360   // Make sure that we get added to a machine basicblock
00361   LeakDetector::addGarbageObject(this);
00362 }
00363 
00364 /// MachineInstr ctor - Work exactly the same as the ctor two above, except
00365 /// that the MachineInstr is created and added to the end of the specified 
00366 /// basic block.
00367 ///
00368 MachineInstr::MachineInstr(MachineBasicBlock *MBB, const TargetInstrDesc &tid)
00369   : TID(&tid), NumImplicitOps(0), Parent(0), 
00370     debugLoc(DebugLoc::getUnknownLoc()) {
00371   assert(MBB && "Cannot use inserting ctor with null basic block!");
00372   if (TID->ImplicitDefs)
00373     for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
00374       NumImplicitOps++;
00375   if (TID->ImplicitUses)
00376     for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
00377       NumImplicitOps++;
00378   Operands.reserve(NumImplicitOps + TID->getNumOperands());
00379   addImplicitDefUseOperands();
00380   // Make sure that we get added to a machine basicblock
00381   LeakDetector::addGarbageObject(this);
00382   MBB->push_back(this);  // Add instruction to end of basic block!
00383 }
00384 
00385 /// MachineInstr ctor - As above, but with a DebugLoc.
00386 ///
00387 MachineInstr::MachineInstr(MachineBasicBlock *MBB, const DebugLoc dl,
00388                            const TargetInstrDesc &tid)
00389   : TID(&tid), NumImplicitOps(0), Parent(0), debugLoc(dl) {
00390   assert(MBB && "Cannot use inserting ctor with null basic block!");
00391   if (TID->ImplicitDefs)
00392     for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
00393       NumImplicitOps++;
00394   if (TID->ImplicitUses)
00395     for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
00396       NumImplicitOps++;
00397   Operands.reserve(NumImplicitOps + TID->getNumOperands());
00398   addImplicitDefUseOperands();
00399   // Make sure that we get added to a machine basicblock
00400   LeakDetector::addGarbageObject(this);
00401   MBB->push_back(this);  // Add instruction to end of basic block!
00402 }
00403 
00404 /// MachineInstr ctor - Copies MachineInstr arg exactly
00405 ///
00406 MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI)
00407   : TID(&MI.getDesc()), NumImplicitOps(0), Parent(0), 
00408         debugLoc(MI.getDebugLoc()) {
00409   Operands.reserve(MI.getNumOperands());
00410 
00411   // Add operands
00412   for (unsigned i = 0; i != MI.getNumOperands(); ++i)
00413     addOperand(MI.getOperand(i));
00414   NumImplicitOps = MI.NumImplicitOps;
00415 
00416   // Add memory operands.
00417   for (std::list<MachineMemOperand>::const_iterator i = MI.memoperands_begin(),
00418        j = MI.memoperands_end(); i != j; ++i)
00419     addMemOperand(MF, *i);
00420 
00421   // Set parent to null.
00422   Parent = 0;
00423 
00424   LeakDetector::addGarbageObject(this);
00425 }
00426 
00427 MachineInstr::~MachineInstr() {
00428   LeakDetector::removeGarbageObject(this);
00429   assert(MemOperands.empty() &&
00430          "MachineInstr being deleted with live memoperands!");
00431 #ifndef NDEBUG
00432   for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
00433     assert(Operands[i].ParentMI == this && "ParentMI mismatch!");
00434     assert((!Operands[i].isReg() || !Operands[i].isOnRegUseList()) &&
00435            "Reg operand def/use list corrupted");
00436   }
00437 #endif
00438 }
00439 
00440 /// getRegInfo - If this instruction is embedded into a MachineFunction,
00441 /// return the MachineRegisterInfo object for the current function, otherwise
00442 /// return null.
00443 MachineRegisterInfo *MachineInstr::getRegInfo() {
00444   if (MachineBasicBlock *MBB = getParent())
00445     return &MBB->getParent()->getRegInfo();
00446   return 0;
00447 }
00448 
00449 /// RemoveRegOperandsFromUseLists - Unlink all of the register operands in
00450 /// this instruction from their respective use lists.  This requires that the
00451 /// operands already be on their use lists.
00452 void MachineInstr::RemoveRegOperandsFromUseLists() {
00453   for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
00454     if (Operands[i].isReg())
00455       Operands[i].RemoveRegOperandFromRegInfo();
00456   }
00457 }
00458 
00459 /// AddRegOperandsToUseLists - Add all of the register operands in
00460 /// this instruction from their respective use lists.  This requires that the
00461 /// operands not be on their use lists yet.
00462 void MachineInstr::AddRegOperandsToUseLists(MachineRegisterInfo &RegInfo) {
00463   for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
00464     if (Operands[i].isReg())
00465       Operands[i].AddRegOperandToRegInfo(&RegInfo);
00466   }
00467 }
00468 
00469 
00470 /// addOperand - Add the specified operand to the instruction.  If it is an
00471 /// implicit operand, it is added to the end of the operand list.  If it is
00472 /// an explicit operand it is added at the end of the explicit operand list
00473 /// (before the first implicit operand). 
00474 void MachineInstr::addOperand(const MachineOperand &Op) {
00475   bool isImpReg = Op.isReg() && Op.isImplicit();
00476   assert((isImpReg || !OperandsComplete()) &&
00477          "Trying to add an operand to a machine instr that is already done!");
00478 
00479   MachineRegisterInfo *RegInfo = getRegInfo();
00480 
00481   // If we are adding the operand to the end of the list, our job is simpler.
00482   // This is true most of the time, so this is a reasonable optimization.
00483   if (isImpReg || NumImplicitOps == 0) {
00484     // We can only do this optimization if we know that the operand list won't
00485     // reallocate.
00486     if (Operands.empty() || Operands.size()+1 <= Operands.capacity()) {
00487       Operands.push_back(Op);
00488     
00489       // Set the parent of the operand.
00490       Operands.back().ParentMI = this;
00491   
00492       // If the operand is a register, update the operand's use list.
00493       if (Op.isReg())
00494         Operands.back().AddRegOperandToRegInfo(RegInfo);
00495       return;
00496     }
00497   }
00498   
00499   // Otherwise, we have to insert a real operand before any implicit ones.
00500   unsigned OpNo = Operands.size()-NumImplicitOps;
00501 
00502   // If this instruction isn't embedded into a function, then we don't need to
00503   // update any operand lists.
00504   if (RegInfo == 0) {
00505     // Simple insertion, no reginfo update needed for other register operands.
00506     Operands.insert(Operands.begin()+OpNo, Op);
00507     Operands[OpNo].ParentMI = this;
00508 
00509     // Do explicitly set the reginfo for this operand though, to ensure the
00510     // next/prev fields are properly nulled out.
00511     if (Operands[OpNo].isReg())
00512       Operands[OpNo].AddRegOperandToRegInfo(0);
00513 
00514   } else if (Operands.size()+1 <= Operands.capacity()) {
00515     // Otherwise, we have to remove register operands from their register use
00516     // list, add the operand, then add the register operands back to their use
00517     // list.  This also must handle the case when the operand list reallocates
00518     // to somewhere else.
00519   
00520     // If insertion of this operand won't cause reallocation of the operand
00521     // list, just remove the implicit operands, add the operand, then re-add all
00522     // the rest of the operands.
00523     for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
00524       assert(Operands[i].isReg() && "Should only be an implicit reg!");
00525       Operands[i].RemoveRegOperandFromRegInfo();
00526     }
00527     
00528     // Add the operand.  If it is a register, add it to the reg list.
00529     Operands.insert(Operands.begin()+OpNo, Op);
00530     Operands[OpNo].ParentMI = this;
00531 
00532     if (Operands[OpNo].isReg())
00533       Operands[OpNo].AddRegOperandToRegInfo(RegInfo);
00534     
00535     // Re-add all the implicit ops.
00536     for (unsigned i = OpNo+1, e = Operands.size(); i != e; ++i) {
00537       assert(Operands[i].isReg() && "Should only be an implicit reg!");
00538       Operands[i].AddRegOperandToRegInfo(RegInfo);
00539     }
00540   } else {
00541     // Otherwise, we will be reallocating the operand list.  Remove all reg
00542     // operands from their list, then readd them after the operand list is
00543     // reallocated.
00544     RemoveRegOperandsFromUseLists();
00545     
00546     Operands.insert(Operands.begin()+OpNo, Op);
00547     Operands[OpNo].ParentMI = this;
00548   
00549     // Re-add all the operands.
00550     AddRegOperandsToUseLists(*RegInfo);
00551   }
00552 }
00553 
00554 /// RemoveOperand - Erase an operand  from an instruction, leaving it with one
00555 /// fewer operand than it started with.
00556 ///
00557 void MachineInstr::RemoveOperand(unsigned OpNo) {
00558   assert(OpNo < Operands.size() && "Invalid operand number");
00559   
00560   // Special case removing the last one.
00561   if (OpNo == Operands.size()-1) {
00562     // If needed, remove from the reg def/use list.
00563     if (Operands.back().isReg() && Operands.back().isOnRegUseList())
00564       Operands.back().RemoveRegOperandFromRegInfo();
00565     
00566     Operands.pop_back();
00567     return;
00568   }
00569 
00570   // Otherwise, we are removing an interior operand.  If we have reginfo to
00571   // update, remove all operands that will be shifted down from their reg lists,
00572   // move everything down, then re-add them.
00573   MachineRegisterInfo *RegInfo = getRegInfo();
00574   if (RegInfo) {
00575     for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
00576       if (Operands[i].isReg())
00577         Operands[i].RemoveRegOperandFromRegInfo();
00578     }
00579   }
00580   
00581   Operands.erase(Operands.begin()+OpNo);
00582 
00583   if (RegInfo) {
00584     for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
00585       if (Operands[i].isReg())
00586         Operands[i].AddRegOperandToRegInfo(RegInfo);
00587     }
00588   }
00589 }
00590 
00591 /// addMemOperand - Add a MachineMemOperand to the machine instruction,
00592 /// referencing arbitrary storage.
00593 void MachineInstr::addMemOperand(MachineFunction &MF,
00594                                  const MachineMemOperand &MO) {
00595   MemOperands.push_back(MO);
00596 }
00597 
00598 /// clearMemOperands - Erase all of this MachineInstr's MachineMemOperands.
00599 void MachineInstr::clearMemOperands(MachineFunction &MF) {
00600   MemOperands.clear();
00601 }
00602 
00603 
00604 /// removeFromParent - This method unlinks 'this' from the containing basic
00605 /// block, and returns it, but does not delete it.
00606 MachineInstr *MachineInstr::removeFromParent() {
00607   assert(getParent() && "Not embedded in a basic block!");
00608   getParent()->remove(this);
00609   return this;
00610 }
00611 
00612 
00613 /// eraseFromParent - This method unlinks 'this' from the containing basic
00614 /// block, and deletes it.
00615 void MachineInstr::eraseFromParent() {
00616   assert(getParent() && "Not embedded in a basic block!");
00617   getParent()->erase(this);
00618 }
00619 
00620 
00621 /// OperandComplete - Return true if it's illegal to add a new operand
00622 ///
00623 bool MachineInstr::OperandsComplete() const {
00624   unsigned short NumOperands = TID->getNumOperands();
00625   if (!TID->isVariadic() && getNumOperands()-NumImplicitOps >= NumOperands)
00626     return true;  // Broken: we have all the operands of this instruction!
00627   return false;
00628 }
00629 
00630 /// getNumExplicitOperands - Returns the number of non-implicit operands.
00631 ///
00632 unsigned MachineInstr::getNumExplicitOperands() const {
00633   unsigned NumOperands = TID->getNumOperands();
00634   if (!TID->isVariadic())
00635     return NumOperands;
00636 
00637   for (unsigned i = NumOperands, e = getNumOperands(); i != e; ++i) {
00638     const MachineOperand &MO = getOperand(i);
00639     if (!MO.isReg() || !MO.isImplicit())
00640       NumOperands++;
00641   }
00642   return NumOperands;
00643 }
00644 
00645 
00646 /// isLabel - Returns true if the MachineInstr represents a label.
00647 ///
00648 bool MachineInstr::isLabel() const {
00649   return getOpcode() == TargetInstrInfo::DBG_LABEL ||
00650          getOpcode() == TargetInstrInfo::EH_LABEL ||
00651          getOpcode() == TargetInstrInfo::GC_LABEL;
00652 }
00653 
00654 /// isDebugLabel - Returns true if the MachineInstr represents a debug label.
00655 ///
00656 bool MachineInstr::isDebugLabel() const {
00657   return getOpcode() == TargetInstrInfo::DBG_LABEL;
00658 }
00659 
00660 /// findRegisterUseOperandIdx() - Returns the MachineOperand that is a use of
00661 /// the specific register or -1 if it is not found. It further tightening
00662 /// the search criteria to a use that kills the register if isKill is true.
00663 int MachineInstr::findRegisterUseOperandIdx(unsigned Reg, bool isKill,
00664                                           const TargetRegisterInfo *TRI) const {
00665   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
00666     const MachineOperand &MO = getOperand(i);
00667     if (!MO.isReg() || !MO.isUse())
00668       continue;
00669     unsigned MOReg = MO.getReg();
00670     if (!MOReg)
00671       continue;
00672     if (MOReg == Reg ||
00673         (TRI &&
00674          TargetRegisterInfo::isPhysicalRegister(MOReg) &&
00675          TargetRegisterInfo::isPhysicalRegister(Reg) &&
00676          TRI->isSubRegister(MOReg, Reg)))
00677       if (!isKill || MO.isKill())
00678         return i;
00679   }
00680   return -1;
00681 }
00682   
00683 /// findRegisterDefOperandIdx() - Returns the operand index that is a def of
00684 /// the specified register or -1 if it is not found. If isDead is true, defs
00685 /// that are not dead are skipped. If TargetRegisterInfo is non-null, then it
00686 /// also checks if there is a def of a super-register.
00687 int MachineInstr::findRegisterDefOperandIdx(unsigned Reg, bool isDead,
00688                                           const TargetRegisterInfo *TRI) const {
00689   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
00690     const MachineOperand &MO = getOperand(i);
00691     if (!MO.isReg() || !MO.isDef())
00692       continue;
00693     unsigned MOReg = MO.getReg();
00694     if (MOReg == Reg ||
00695         (TRI &&
00696          TargetRegisterInfo::isPhysicalRegister(MOReg) &&
00697          TargetRegisterInfo::isPhysicalRegister(Reg) &&
00698          TRI->isSubRegister(MOReg, Reg)))
00699       if (!isDead || MO.isDead())
00700         return i;
00701   }
00702   return -1;
00703 }
00704 
00705 /// findFirstPredOperandIdx() - Find the index of the first operand in the
00706 /// operand list that is used to represent the predicate. It returns -1 if
00707 /// none is found.
00708 int MachineInstr::findFirstPredOperandIdx() const {
00709   const TargetInstrDesc &TID = getDesc();
00710   if (TID.isPredicable()) {
00711     for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00712       if (TID.OpInfo[i].isPredicate())
00713         return i;
00714   }
00715 
00716   return -1;
00717 }
00718   
00719 /// isRegTiedToUseOperand - Given the index of a register def operand,
00720 /// check if the register def is tied to a source operand, due to either
00721 /// two-address elimination or inline assembly constraints. Returns the
00722 /// first tied use operand index by reference is UseOpIdx is not null.
00723 bool MachineInstr::
00724 isRegTiedToUseOperand(unsigned DefOpIdx, unsigned *UseOpIdx) const {
00725   if (getOpcode() == TargetInstrInfo::INLINEASM) {
00726     assert(DefOpIdx >= 2);
00727     const MachineOperand &MO = getOperand(DefOpIdx);
00728     if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0)
00729       return false;
00730     // Determine the actual operand index that corresponds to this index.
00731     unsigned DefNo = 0;
00732     unsigned DefPart = 0;
00733     for (unsigned i = 1, e = getNumOperands(); i < e; ) {
00734       const MachineOperand &FMO = getOperand(i);
00735       // After the normal asm operands there may be additional imp-def regs.
00736       if (!FMO.isImm())
00737         return false;
00738       // Skip over this def.
00739       unsigned NumOps = InlineAsm::getNumOperandRegisters(FMO.getImm());
00740       unsigned PrevDef = i + 1;
00741       i = PrevDef + NumOps;
00742       if (i > DefOpIdx) {
00743         DefPart = DefOpIdx - PrevDef;
00744         break;
00745       }
00746       ++DefNo;
00747     }
00748     for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
00749       const MachineOperand &FMO = getOperand(i);
00750       if (!FMO.isImm())
00751         continue;
00752       if (i+1 >= e || !getOperand(i+1).isReg() || !getOperand(i+1).isUse())
00753         continue;
00754       unsigned Idx;
00755       if (InlineAsm::isUseOperandTiedToDef(FMO.getImm(), Idx) &&
00756           Idx == DefNo) {
00757         if (UseOpIdx)
00758           *UseOpIdx = (unsigned)i + 1 + DefPart;
00759         return true;
00760       }
00761     }
00762     return false;
00763   }
00764 
00765   assert(getOperand(DefOpIdx).isDef() && "DefOpIdx is not a def!");
00766   const TargetInstrDesc &TID = getDesc();
00767   for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
00768     const MachineOperand &MO = getOperand(i);
00769     if (MO.isReg() && MO.isUse() &&
00770         TID.getOperandConstraint(i, TOI::TIED_TO) == (int)DefOpIdx) {
00771       if (UseOpIdx)
00772         *UseOpIdx = (unsigned)i;
00773       return true;
00774     }
00775   }
00776   return false;
00777 }
00778 
00779 /// isRegTiedToDefOperand - Return true if the operand of the specified index
00780 /// is a register use and it is tied to an def operand. It also returns the def
00781 /// operand index by reference.
00782 bool MachineInstr::
00783 isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx) const {
00784   if (getOpcode() == TargetInstrInfo::INLINEASM) {
00785     const MachineOperand &MO = getOperand(UseOpIdx);
00786     if (!MO.isReg() || !MO.isUse() || MO.getReg() == 0)
00787       return false;
00788 
00789     // Find the flag operand corresponding to UseOpIdx
00790     unsigned FlagIdx, NumOps=0;
00791     for (FlagIdx = 1; FlagIdx < UseOpIdx; FlagIdx += NumOps+1) {
00792       const MachineOperand &UFMO = getOperand(FlagIdx);
00793       // After the normal asm operands there may be additional imp-def regs.
00794       if (!UFMO.isImm())
00795         return false;
00796       NumOps = InlineAsm::getNumOperandRegisters(UFMO.getImm());
00797       assert(NumOps < getNumOperands() && "Invalid inline asm flag");
00798       if (UseOpIdx < FlagIdx+NumOps+1)
00799         break;
00800     }
00801     if (FlagIdx >= UseOpIdx)
00802       return false;
00803     const MachineOperand &UFMO = getOperand(FlagIdx);
00804     unsigned DefNo;
00805     if (InlineAsm::isUseOperandTiedToDef(UFMO.getImm(), DefNo)) {
00806       if (!DefOpIdx)
00807         return true;
00808 
00809       unsigned DefIdx = 1;
00810       // Remember to adjust the index. First operand is asm string, then there
00811       // is a flag for each.
00812       while (DefNo) {
00813         const MachineOperand &FMO = getOperand(DefIdx);
00814         assert(FMO.isImm());
00815         // Skip over this def.
00816         DefIdx += InlineAsm::getNumOperandRegisters(FMO.getImm()) + 1;
00817         --DefNo;
00818       }
00819       *DefOpIdx = DefIdx + UseOpIdx - FlagIdx;
00820       return true;
00821     }
00822     return false;
00823   }
00824 
00825   const TargetInstrDesc &TID = getDesc();
00826   if (UseOpIdx >= TID.getNumOperands())
00827     return false;
00828   const MachineOperand &MO = getOperand(UseOpIdx);
00829   if (!MO.isReg() || !MO.isUse())
00830     return false;
00831   int DefIdx = TID.getOperandConstraint(UseOpIdx, TOI::TIED_TO);
00832   if (DefIdx == -1)
00833     return false;
00834   if (DefOpIdx)
00835     *DefOpIdx = (unsigned)DefIdx;
00836   return true;
00837 }
00838 
00839 /// copyKillDeadInfo - Copies kill / dead operand properties from MI.
00840 ///
00841 void MachineInstr::copyKillDeadInfo(const MachineInstr *MI) {
00842   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00843     const MachineOperand &MO = MI->getOperand(i);
00844     if (!MO.isReg() || (!MO.isKill() && !MO.isDead()))
00845       continue;
00846     for (unsigned j = 0, ee = getNumOperands(); j != ee; ++j) {
00847       MachineOperand &MOp = getOperand(j);
00848       if (!MOp.isIdenticalTo(MO))
00849         continue;
00850       if (MO.isKill())
00851         MOp.setIsKill();
00852       else
00853         MOp.setIsDead();
00854       break;
00855     }
00856   }
00857 }
00858 
00859 /// copyPredicates - Copies predicate operand(s) from MI.
00860 void MachineInstr::copyPredicates(const MachineInstr *MI) {
00861   const TargetInstrDesc &TID = MI->getDesc();
00862   if (!TID.isPredicable())
00863     return;
00864   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00865     if (TID.OpInfo[i].isPredicate()) {
00866       // Predicated operands must be last operands.
00867       addOperand(MI->getOperand(i));
00868     }
00869   }
00870 }
00871 
00872 /// isSafeToMove - Return true if it is safe to move this instruction. If
00873 /// SawStore is set to true, it means that there is a store (or call) between
00874 /// the instruction's location and its intended destination.
00875 bool MachineInstr::isSafeToMove(const TargetInstrInfo *TII,
00876                                 bool &SawStore) const {
00877   // Ignore stuff that we obviously can't move.
00878   if (TID->mayStore() || TID->isCall()) {
00879     SawStore = true;
00880     return false;
00881   }
00882   if (TID->isTerminator() || TID->hasUnmodeledSideEffects())
00883     return false;
00884 
00885   // See if this instruction does a load.  If so, we have to guarantee that the
00886   // loaded value doesn't change between the load and the its intended
00887   // destination. The check for isInvariantLoad gives the targe the chance to
00888   // classify the load as always returning a constant, e.g. a constant pool
00889   // load.
00890   if (TID->mayLoad() && !TII->isInvariantLoad(this))
00891     // Otherwise, this is a real load.  If there is a store between the load and
00892     // end of block, or if the load is volatile, we can't move it.
00893     return !SawStore && !hasVolatileMemoryRef();
00894 
00895   return true;
00896 }
00897 
00898 /// isSafeToReMat - Return true if it's safe to rematerialize the specified
00899 /// instruction which defined the specified register instead of copying it.
00900 bool MachineInstr::isSafeToReMat(const TargetInstrInfo *TII,
00901                                  unsigned DstReg) const {
00902   bool SawStore = false;
00903   if (!getDesc().isRematerializable() ||
00904       !TII->isTriviallyReMaterializable(this) ||
00905       !isSafeToMove(TII, SawStore))
00906     return false;
00907   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
00908     const MachineOperand &MO = getOperand(i);
00909     if (!MO.isReg())
00910       continue;
00911     // FIXME: For now, do not remat any instruction with register operands.
00912     // Later on, we can loosen the restriction is the register operands have
00913     // not been modified between the def and use. Note, this is different from
00914     // MachineSink because the code is no longer in two-address form (at least
00915     // partially).
00916     if (MO.isUse())
00917       return false;
00918     else if (!MO.isDead() && MO.getReg() != DstReg)
00919       return false;
00920   }
00921   return true;
00922 }
00923 
00924 /// hasVolatileMemoryRef - Return true if this instruction may have a
00925 /// volatile memory reference, or if the information describing the
00926 /// memory reference is not available. Return false if it is known to
00927 /// have no volatile memory references.
00928 bool MachineInstr::hasVolatileMemoryRef() const {
00929   // An instruction known never to access memory won't have a volatile access.
00930   if (!TID->mayStore() &&
00931       !TID->mayLoad() &&
00932       !TID->isCall() &&
00933       !TID->hasUnmodeledSideEffects())
00934     return false;
00935 
00936   // Otherwise, if the instruction has no memory reference information,
00937   // conservatively assume it wasn't preserved.
00938   if (memoperands_empty())
00939     return true;
00940   
00941   // Check the memory reference information for volatile references.
00942   for (std::list<MachineMemOperand>::const_iterator I = memoperands_begin(),
00943        E = memoperands_end(); I != E; ++I)
00944     if (I->isVolatile())
00945       return true;
00946 
00947   return false;
00948 }
00949 
00950 void MachineInstr::dump() const {
00951   cerr << "  " << *this;
00952 }
00953 
00954 void MachineInstr::print(std::ostream &OS, const TargetMachine *TM) const {
00955   raw_os_ostream RawOS(OS);
00956   print(RawOS, TM);
00957 }
00958 
00959 void MachineInstr::print(raw_ostream &OS, const TargetMachine *TM) const {
00960   // Specialize printing if op#0 is definition
00961   unsigned StartOp = 0;
00962   if (getNumOperands() && getOperand(0).isReg() && getOperand(0).isDef()) {
00963     getOperand(0).print(OS, TM);
00964     OS << " = ";
00965     ++StartOp;   // Don't print this operand again!
00966   }
00967 
00968   OS << getDesc().getName();
00969 
00970   for (unsigned i = StartOp, e = getNumOperands(); i != e; ++i) {
00971     if (i != StartOp)
00972       OS << ",";
00973     OS << " ";
00974     getOperand(i).print(OS, TM);
00975   }
00976 
00977   if (!memoperands_empty()) {
00978     OS << ", Mem:";
00979     for (std::list<MachineMemOperand>::const_iterator i = memoperands_begin(),
00980          e = memoperands_end(); i != e; ++i) {
00981       const MachineMemOperand &MRO = *i;
00982       const Value *V = MRO.getValue();
00983 
00984       assert((MRO.isLoad() || MRO.isStore()) &&
00985              "SV has to be a load, store or both.");
00986       
00987       if (MRO.isVolatile())
00988         OS << "Volatile ";
00989 
00990       if (MRO.isLoad())
00991         OS << "LD";
00992       if (MRO.isStore())
00993         OS << "ST";
00994         
00995       OS << "(" << MRO.getSize() << "," << MRO.getAlignment() << ") [";
00996       
00997       if (!V)
00998         OS << "<unknown>";
00999       else if (!V->getName().empty())
01000         OS << V->getName();
01001       else if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
01002         PSV->print(OS);
01003       } else
01004         OS << V;
01005 
01006       OS << " + " << MRO.getOffset() << "]";
01007     }
01008   }
01009 
01010   if (!debugLoc.isUnknown()) {
01011     const MachineFunction *MF = getParent()->getParent();
01012     DebugLocTuple DLT = MF->getDebugLocTuple(debugLoc);
01013     DICompileUnit CU(DLT.CompileUnit);
01014     std::string Dir, Fn;
01015     OS << " [dbg: "
01016        << CU.getDirectory(Dir) << '/' << CU.getFilename(Fn) << ","
01017        << DLT.Line << ","
01018        << DLT.Col  << "]";
01019   }
01020 
01021   OS << "\n";
01022 }
01023 
01024 bool MachineInstr::addRegisterKilled(unsigned IncomingReg,
01025                                      const TargetRegisterInfo *RegInfo,
01026                                      bool AddIfNotFound) {
01027   bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(IncomingReg);
01028   bool hasAliases = isPhysReg && RegInfo->getAliasSet(IncomingReg);
01029   bool Found = false;
01030   SmallVector<unsigned,4> DeadOps;
01031   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
01032     MachineOperand &MO = getOperand(i);
01033     if (!MO.isReg() || !MO.isUse() || MO.isUndef())
01034       continue;
01035     unsigned Reg = MO.getReg();
01036     if (!Reg)
01037       continue;
01038 
01039     if (Reg == IncomingReg) {
01040       if (!Found) {
01041         if (MO.isKill())
01042           // The register is already marked kill.
01043           return true;
01044         if (isPhysReg && isRegTiedToDefOperand(i))
01045           // Two-address uses of physregs must not be marked kill.
01046           return true;
01047         MO.setIsKill();
01048         Found = true;
01049       }
01050     } else if (hasAliases && MO.isKill() &&
01051                TargetRegisterInfo::isPhysicalRegister(Reg)) {
01052       // A super-register kill already exists.
01053       if (RegInfo->isSuperRegister(IncomingReg, Reg))
01054         return true;
01055       if (RegInfo->isSubRegister(IncomingReg, Reg))
01056         DeadOps.push_back(i);
01057     }
01058   }
01059 
01060   // Trim unneeded kill operands.
01061   while (!DeadOps.empty()) {
01062     unsigned OpIdx = DeadOps.back();
01063     if (getOperand(OpIdx).isImplicit())
01064       RemoveOperand(OpIdx);
01065     else
01066       getOperand(OpIdx).setIsKill(false);
01067     DeadOps.pop_back();
01068   }
01069 
01070   // If not found, this means an alias of one of the operands is killed. Add a
01071   // new implicit operand if required.
01072   if (!Found && AddIfNotFound) {
01073     addOperand(MachineOperand::CreateReg(IncomingReg,
01074                                          false /*IsDef*/,
01075                                          true  /*IsImp*/,
01076                                          true  /*IsKill*/));
01077     return true;
01078   }
01079   return Found;
01080 }
01081 
01082 bool MachineInstr::addRegisterDead(unsigned IncomingReg,
01083                                    const TargetRegisterInfo *RegInfo,
01084                                    bool AddIfNotFound) {
01085   bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(IncomingReg);
01086   bool hasAliases = isPhysReg && RegInfo->getAliasSet(IncomingReg);
01087   bool Found = false;
01088   SmallVector<unsigned,4> DeadOps;
01089   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
01090     MachineOperand &MO = getOperand(i);
01091     if (!MO.isReg() || !MO.isDef())
01092       continue;
01093     unsigned Reg = MO.getReg();
01094     if (!Reg)
01095       continue;
01096 
01097     if (Reg == IncomingReg) {
01098       if (!Found) {
01099         if (MO.isDead())
01100           // The register is already marked dead.
01101           return true;
01102         MO.setIsDead();
01103         Found = true;
01104       }
01105     } else if (hasAliases && MO.isDead() &&
01106                TargetRegisterInfo::isPhysicalRegister(Reg)) {
01107       // There exists a super-register that's marked dead.
01108       if (RegInfo->isSuperRegister(IncomingReg, Reg))
01109         return true;
01110       if (RegInfo->getSubRegisters(IncomingReg) &&
01111           RegInfo->getSuperRegisters(Reg) &&
01112           RegInfo->isSubRegister(IncomingReg, Reg))
01113         DeadOps.push_back(i);
01114     }
01115   }
01116 
01117   // Trim unneeded dead operands.
01118   while (!DeadOps.empty()) {
01119     unsigned OpIdx = DeadOps.back();
01120     if (getOperand(OpIdx).isImplicit())
01121       RemoveOperand(OpIdx);
01122     else
01123       getOperand(OpIdx).setIsDead(false);
01124     DeadOps.pop_back();
01125   }
01126 
01127   // If not found, this means an alias of one of the operands is dead. Add a
01128   // new implicit operand if required.
01129   if (Found || !AddIfNotFound)
01130     return Found;
01131     
01132   addOperand(MachineOperand::CreateReg(IncomingReg,
01133                                        true  /*IsDef*/,
01134                                        true  /*IsImp*/,
01135                                        false /*IsKill*/,
01136                                        true  /*IsDead*/));
01137   return true;
01138 }