lib/CodeGen/MachineInstr.cpp

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