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