lib/CodeGen/MachineInstr.cpp

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