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