lib/CodeGen/TwoAddressInstructionPass.cpp

   1 //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===//
   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 // This file implements the TwoAddress instruction pass which is used
  11 // by most register allocators. Two-Address instructions are rewritten
  12 // from:
  13 //
  14 //     A = B op C
  15 //
  16 // to:
  17 //
  18 //     A = B
  19 //     A op= C
  20 //
  21 // Note that if a register allocator chooses to use this pass, that it
  22 // has to be capable of handling the non-SSA nature of these rewritten
  23 // virtual registers.
  24 //
  25 // It is also worth noting that the duplicate operand of the two
  26 // address instruction is removed.
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #define DEBUG_TYPE "twoaddrinstr"
  31 #include "llvm/CodeGen/Passes.h"
  32 #include "llvm/ADT/BitVector.h"
  33 #include "llvm/ADT/DenseMap.h"
  34 #include "llvm/ADT/STLExtras.h"
  35 #include "llvm/ADT/SmallSet.h"
  36 #include "llvm/ADT/Statistic.h"
  37 #include "llvm/Analysis/AliasAnalysis.h"
  38 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  39 #include "llvm/CodeGen/LiveVariables.h"
  40 #include "llvm/CodeGen/MachineFunctionPass.h"
  41 #include "llvm/CodeGen/MachineInstr.h"
  42 #include "llvm/CodeGen/MachineInstrBuilder.h"
  43 #include "llvm/CodeGen/MachineRegisterInfo.h"
  44 #include "llvm/IR/Function.h"
  45 #include "llvm/MC/MCInstrItineraries.h"
  46 #include "llvm/Support/Debug.h"
  47 #include "llvm/Support/ErrorHandling.h"
  48 #include "llvm/Target/TargetInstrInfo.h"
  49 #include "llvm/Target/TargetMachine.h"
  50 #include "llvm/Target/TargetOptions.h"
  51 #include "llvm/Target/TargetRegisterInfo.h"
  52 using namespace llvm;
  53
  54 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
  55 STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
  56 STATISTIC(NumAggrCommuted    , "Number of instructions aggressively commuted");
  57 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
  58 STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
  59 STATISTIC(NumReSchedUps,       "Number of instructions re-scheduled up");
  60 STATISTIC(NumReSchedDowns,     "Number of instructions re-scheduled down");
  61
  62 namespace {
  63 class TwoAddressInstructionPass : public MachineFunctionPass {
  64   MachineFunction *MF;
  65   const TargetInstrInfo *TII;
  66   const TargetRegisterInfo *TRI;
  67   const InstrItineraryData *InstrItins;
  68   MachineRegisterInfo *MRI;
  69   LiveVariables *LV;
  70   LiveIntervals *LIS;
  71   AliasAnalysis *AA;
  72   CodeGenOpt::Level OptLevel;
  73
  74   // The current basic block being processed.
  75   MachineBasicBlock *MBB;
  76
  77   // DistanceMap - Keep track the distance of a MI from the start of the
  78   // current basic block.
  79   DenseMap<MachineInstr*, unsigned> DistanceMap;
  80
  81   // Set of already processed instructions in the current block.
  82   SmallPtrSet<MachineInstr*, 8> Processed;
  83
  84   // SrcRegMap - A map from virtual registers to physical registers which are
  85   // likely targets to be coalesced to due to copies from physical registers to
  86   // virtual registers. e.g. v1024 = move r0.
  87   DenseMap<unsigned, unsigned> SrcRegMap;
  88
  89   // DstRegMap - A map from virtual registers to physical registers which are
  90   // likely targets to be coalesced to due to copies to physical registers from
  91   // virtual registers. e.g. r1 = move v1024.
  92   DenseMap<unsigned, unsigned> DstRegMap;
  93
  94   bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg,
  95                             MachineBasicBlock::iterator OldPos);
  96
  97   bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef);
  98
  99   bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
 100                              MachineInstr *MI, unsigned Dist);
 101
 102   bool commuteInstruction(MachineBasicBlock::iterator &mi,
 103                           unsigned RegB, unsigned RegC, unsigned Dist);
 104
 105   bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB);
 106
 107   bool convertInstTo3Addr(MachineBasicBlock::iterator &mi,
 108                           MachineBasicBlock::iterator &nmi,
 109                           unsigned RegA, unsigned RegB, unsigned Dist);
 110
 111   bool isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI);
 112
 113   bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
 114                              MachineBasicBlock::iterator &nmi,
 115                              unsigned Reg);
 116   bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
 117                              MachineBasicBlock::iterator &nmi,
 118                              unsigned Reg);
 119
 120   bool tryInstructionTransform(MachineBasicBlock::iterator &mi,
 121                                MachineBasicBlock::iterator &nmi,
 122                                unsigned SrcIdx, unsigned DstIdx,
 123                                unsigned Dist);
 124
 125   void scanUses(unsigned DstReg);
 126
 127   void processCopy(MachineInstr *MI);
 128
 129   typedef SmallVector<std::pair<unsigned, unsigned>, 4> TiedPairList;
 130   typedef SmallDenseMap<unsigned, TiedPairList> TiedOperandMap;
 131   bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&);
 132   void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist);
 133   void eliminateRegSequence(MachineBasicBlock::iterator&);
 134
 135 public:
 136   static char ID; // Pass identification, replacement for typeid
 137   TwoAddressInstructionPass() : MachineFunctionPass(ID) {
 138     initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry());
 139   }
 140
 141   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 142     AU.setPreservesCFG();
 143     AU.addRequired<AliasAnalysis>();
 144     AU.addPreserved<LiveVariables>();
 145     AU.addPreserved<SlotIndexes>();
 146     AU.addPreserved<LiveIntervals>();
 147     AU.addPreservedID(MachineLoopInfoID);
 148     AU.addPreservedID(MachineDominatorsID);
 149     MachineFunctionPass::getAnalysisUsage(AU);
 150   }
 151
 152   /// runOnMachineFunction - Pass entry point.
 153   bool runOnMachineFunction(MachineFunction&);
 154 };
 155 } // end anonymous namespace
 156
 157 char TwoAddressInstructionPass::ID = 0;
 158 INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction",
 159                 "Two-Address instruction pass", false, false)
 160 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 161 INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction",
 162                 "Two-Address instruction pass", false, false)
 163
 164 char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID;
 165
 166 /// sink3AddrInstruction - A two-address instruction has been converted to a
 167 /// three-address instruction to avoid clobbering a register. Try to sink it
 168 /// past the instruction that would kill the above mentioned register to reduce
 169 /// register pressure.
 170 bool TwoAddressInstructionPass::
 171 sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg,
 172                      MachineBasicBlock::iterator OldPos) {
 173   // FIXME: Shouldn't we be trying to do this before we three-addressify the
 174   // instruction?  After this transformation is done, we no longer need
 175   // the instruction to be in three-address form.
 176
 177   // Check if it's safe to move this instruction.
 178   bool SeenStore = true; // Be conservative.
 179   if (!MI->isSafeToMove(TII, AA, SeenStore))
 180     return false;
 181
 182   unsigned DefReg = 0;
 183   SmallSet<unsigned, 4> UseRegs;
 184
 185   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 186     const MachineOperand &MO = MI->getOperand(i);
 187     if (!MO.isReg())
 188       continue;
 189     unsigned MOReg = MO.getReg();
 190     if (!MOReg)
 191       continue;
 192     if (MO.isUse() && MOReg != SavedReg)
 193       UseRegs.insert(MO.getReg());
 194     if (!MO.isDef())
 195       continue;
 196     if (MO.isImplicit())
 197       // Don't try to move it if it implicitly defines a register.
 198       return false;
 199     if (DefReg)
 200       // For now, don't move any instructions that define multiple registers.
 201       return false;
 202     DefReg = MO.getReg();
 203   }
 204
 205   // Find the instruction that kills SavedReg.
 206   MachineInstr *KillMI = NULL;
 207   for (MachineRegisterInfo::use_nodbg_iterator
 208          UI = MRI->use_nodbg_begin(SavedReg),
 209          UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
 210     MachineOperand &UseMO = UI.getOperand();
 211     if (!UseMO.isKill())
 212       continue;
 213     KillMI = UseMO.getParent();
 214     break;
 215   }
 216
 217   // If we find the instruction that kills SavedReg, and it is in an
 218   // appropriate location, we can try to sink the current instruction
 219   // past it.
 220   if (!KillMI || KillMI->getParent() != MBB || KillMI == MI ||
 221       KillMI == OldPos || KillMI->isTerminator())
 222     return false;
 223
 224   // If any of the definitions are used by another instruction between the
 225   // position and the kill use, then it's not safe to sink it.
 226   //
 227   // FIXME: This can be sped up if there is an easy way to query whether an
 228   // instruction is before or after another instruction. Then we can use
 229   // MachineRegisterInfo def / use instead.
 230   MachineOperand *KillMO = NULL;
 231   MachineBasicBlock::iterator KillPos = KillMI;
 232   ++KillPos;
 233
 234   unsigned NumVisited = 0;
 235   for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) {
 236     MachineInstr *OtherMI = I;
 237     // DBG_VALUE cannot be counted against the limit.
 238     if (OtherMI->isDebugValue())
 239       continue;
 240     if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
 241       return false;
 242     ++NumVisited;
 243     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 244       MachineOperand &MO = OtherMI->getOperand(i);
 245       if (!MO.isReg())
 246         continue;
 247       unsigned MOReg = MO.getReg();
 248       if (!MOReg)
 249         continue;
 250       if (DefReg == MOReg)
 251         return false;
 252
 253       if (MO.isKill()) {
 254         if (OtherMI == KillMI && MOReg == SavedReg)
 255           // Save the operand that kills the register. We want to unset the kill
 256           // marker if we can sink MI past it.
 257           KillMO = &MO;
 258         else if (UseRegs.count(MOReg))
 259           // One of the uses is killed before the destination.
 260           return false;
 261       }
 262     }
 263   }
 264   assert(KillMO && "Didn't find kill");
 265
 266   // Update kill and LV information.
 267   KillMO->setIsKill(false);
 268   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 269   KillMO->setIsKill(true);
 270
 271   if (LV)
 272     LV->replaceKillInstruction(SavedReg, KillMI, MI);
 273
 274   // Move instruction to its destination.
 275   MBB->remove(MI);
 276   MBB->insert(KillPos, MI);
 277
 278   if (LIS)
 279     LIS->handleMove(MI);
 280
 281   ++Num3AddrSunk;
 282   return true;
 283 }
 284
 285 /// noUseAfterLastDef - Return true if there are no intervening uses between the
 286 /// last instruction in the MBB that defines the specified register and the
 287 /// two-address instruction which is being processed. It also returns the last
 288 /// def location by reference
 289 bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist,
 290                                                   unsigned &LastDef) {
 291   LastDef = 0;
 292   unsigned LastUse = Dist;
 293   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
 294          E = MRI->reg_end(); I != E; ++I) {
 295     MachineOperand &MO = I.getOperand();
 296     MachineInstr *MI = MO.getParent();
 297     if (MI->getParent() != MBB || MI->isDebugValue())
 298       continue;
 299     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
 300     if (DI == DistanceMap.end())
 301       continue;
 302     if (MO.isUse() && DI->second < LastUse)
 303       LastUse = DI->second;
 304     if (MO.isDef() && DI->second > LastDef)
 305       LastDef = DI->second;
 306   }
 307
 308   return !(LastUse > LastDef && LastUse < Dist);
 309 }
 310
 311 /// isCopyToReg - Return true if the specified MI is a copy instruction or
 312 /// a extract_subreg instruction. It also returns the source and destination
 313 /// registers and whether they are physical registers by reference.
 314 static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
 315                         unsigned &SrcReg, unsigned &DstReg,
 316                         bool &IsSrcPhys, bool &IsDstPhys) {
 317   SrcReg = 0;
 318   DstReg = 0;
 319   if (MI.isCopy()) {
 320     DstReg = MI.getOperand(0).getReg();
 321     SrcReg = MI.getOperand(1).getReg();
 322   } else if (MI.isInsertSubreg() || MI.isSubregToReg()) {
 323     DstReg = MI.getOperand(0).getReg();
 324     SrcReg = MI.getOperand(2).getReg();
 325   } else
 326     return false;
 327
 328   IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
 329   IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 330   return true;
 331 }
 332
 333 /// isPLainlyKilled - Test if the given register value, which is used by the
 334 // given instruction, is killed by the given instruction.
 335 static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg,
 336                             LiveIntervals *LIS) {
 337   if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) &&
 338       !LIS->isNotInMIMap(MI)) {
 339     // FIXME: Sometimes tryInstructionTransform() will add instructions and
 340     // test whether they can be folded before keeping them. In this case it
 341     // sets a kill before recursively calling tryInstructionTransform() again.
 342     // If there is no interval available, we assume that this instruction is
 343     // one of those. A kill flag is manually inserted on the operand so the
 344     // check below will handle it.
 345     LiveInterval &LI = LIS->getInterval(Reg);
 346     // This is to match the kill flag version where undefs don't have kill
 347     // flags.
 348     if (!LI.hasAtLeastOneValue())
 349       return false;
 350
 351     SlotIndex useIdx = LIS->getInstructionIndex(MI);
 352     LiveInterval::const_iterator I = LI.find(useIdx);
 353     assert(I != LI.end() && "Reg must be live-in to use.");
 354     return SlotIndex::isSameInstr(I->end, useIdx);
 355   }
 356
 357   return MI->killsRegister(Reg);
 358 }
 359
 360 /// isKilled - Test if the given register value, which is used by the given
 361 /// instruction, is killed by the given instruction. This looks through
 362 /// coalescable copies to see if the original value is potentially not killed.
 363 ///
 364 /// For example, in this code:
 365 ///
 366 ///   %reg1034 = copy %reg1024
 367 ///   %reg1035 = copy %reg1025<kill>
 368 ///   %reg1036 = add %reg1034<kill>, %reg1035<kill>
 369 ///
 370 /// %reg1034 is not considered to be killed, since it is copied from a
 371 /// register which is not killed. Treating it as not killed lets the
 372 /// normal heuristics commute the (two-address) add, which lets
 373 /// coalescing eliminate the extra copy.
 374 ///
 375 /// If allowFalsePositives is true then likely kills are treated as kills even
 376 /// if it can't be proven that they are kills.
 377 static bool isKilled(MachineInstr &MI, unsigned Reg,
 378                      const MachineRegisterInfo *MRI,
 379                      const TargetInstrInfo *TII,
 380                      LiveIntervals *LIS,
 381                      bool allowFalsePositives) {
 382   MachineInstr *DefMI = &MI;
 383   for (;;) {
 384     // All uses of physical registers are likely to be kills.
 385     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
 386         (allowFalsePositives || MRI->hasOneUse(Reg)))
 387       return true;
 388     if (!isPlainlyKilled(DefMI, Reg, LIS))
 389       return false;
 390     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 391       return true;
 392     MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
 393     // If there are multiple defs, we can't do a simple analysis, so just
 394     // go with what the kill flag says.
 395     if (llvm::next(Begin) != MRI->def_end())
 396       return true;
 397     DefMI = &*Begin;
 398     bool IsSrcPhys, IsDstPhys;
 399     unsigned SrcReg,  DstReg;
 400     // If the def is something other than a copy, then it isn't going to
 401     // be coalesced, so follow the kill flag.
 402     if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
 403       return true;
 404     Reg = SrcReg;
 405   }
 406 }
 407
 408 /// isTwoAddrUse - Return true if the specified MI uses the specified register
 409 /// as a two-address use. If so, return the destination register by reference.
 410 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
 411   const MCInstrDesc &MCID = MI.getDesc();
 412   unsigned NumOps = MI.isInlineAsm()
 413     ? MI.getNumOperands() : MCID.getNumOperands();
 414   for (unsigned i = 0; i != NumOps; ++i) {
 415     const MachineOperand &MO = MI.getOperand(i);
 416     if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
 417       continue;
 418     unsigned ti;
 419     if (MI.isRegTiedToDefOperand(i, &ti)) {
 420       DstReg = MI.getOperand(ti).getReg();
 421       return true;
 422     }
 423   }
 424   return false;
 425 }
 426
 427 /// findOnlyInterestingUse - Given a register, if has a single in-basic block
 428 /// use, return the use instruction if it's a copy or a two-address use.
 429 static
 430 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
 431                                      MachineRegisterInfo *MRI,
 432                                      const TargetInstrInfo *TII,
 433                                      bool &IsCopy,
 434                                      unsigned &DstReg, bool &IsDstPhys) {
 435   if (!MRI->hasOneNonDBGUse(Reg))
 436     // None or more than one use.
 437     return 0;
 438   MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg);
 439   if (UseMI.getParent() != MBB)
 440     return 0;
 441   unsigned SrcReg;
 442   bool IsSrcPhys;
 443   if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
 444     IsCopy = true;
 445     return &UseMI;
 446   }
 447   IsDstPhys = false;
 448   if (isTwoAddrUse(UseMI, Reg, DstReg)) {
 449     IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 450     return &UseMI;
 451   }
 452   return 0;
 453 }
 454
 455 /// getMappedReg - Return the physical register the specified virtual register
 456 /// might be mapped to.
 457 static unsigned
 458 getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) {
 459   while (TargetRegisterInfo::isVirtualRegister(Reg))  {
 460     DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg);
 461     if (SI == RegMap.end())
 462       return 0;
 463     Reg = SI->second;
 464   }
 465   if (TargetRegisterInfo::isPhysicalRegister(Reg))
 466     return Reg;
 467   return 0;
 468 }
 469
 470 /// regsAreCompatible - Return true if the two registers are equal or aliased.
 471 ///
 472 static bool
 473 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
 474   if (RegA == RegB)
 475     return true;
 476   if (!RegA || !RegB)
 477     return false;
 478   return TRI->regsOverlap(RegA, RegB);
 479 }
 480
 481
 482 /// isProfitableToCommute - Return true if it's potentially profitable to commute
 483 /// the two-address instruction that's being processed.
 484 bool
 485 TwoAddressInstructionPass::
 486 isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
 487                       MachineInstr *MI, unsigned Dist) {
 488   if (OptLevel == CodeGenOpt::None)
 489     return false;
 490
 491   // Determine if it's profitable to commute this two address instruction. In
 492   // general, we want no uses between this instruction and the definition of
 493   // the two-address register.
 494   // e.g.
 495   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 496   // %reg1029<def> = MOV8rr %reg1028
 497   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 498   // insert => %reg1030<def> = MOV8rr %reg1028
 499   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 500   // In this case, it might not be possible to coalesce the second MOV8rr
 501   // instruction if the first one is coalesced. So it would be profitable to
 502   // commute it:
 503   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 504   // %reg1029<def> = MOV8rr %reg1028
 505   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 506   // insert => %reg1030<def> = MOV8rr %reg1029
 507   // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
 508
 509   if (!isPlainlyKilled(MI, regC, LIS))
 510     return false;
 511
 512   // Ok, we have something like:
 513   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 514   // let's see if it's worth commuting it.
 515
 516   // Look for situations like this:
 517   // %reg1024<def> = MOV r1
 518   // %reg1025<def> = MOV r0
 519   // %reg1026<def> = ADD %reg1024, %reg1025
 520   // r0            = MOV %reg1026
 521   // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
 522   unsigned ToRegA = getMappedReg(regA, DstRegMap);
 523   if (ToRegA) {
 524     unsigned FromRegB = getMappedReg(regB, SrcRegMap);
 525     unsigned FromRegC = getMappedReg(regC, SrcRegMap);
 526     bool BComp = !FromRegB || regsAreCompatible(FromRegB, ToRegA, TRI);
 527     bool CComp = !FromRegC || regsAreCompatible(FromRegC, ToRegA, TRI);
 528     if (BComp != CComp)
 529       return !BComp && CComp;
 530   }
 531
 532   // If there is a use of regC between its last def (could be livein) and this
 533   // instruction, then bail.
 534   unsigned LastDefC = 0;
 535   if (!noUseAfterLastDef(regC, Dist, LastDefC))
 536     return false;
 537
 538   // If there is a use of regB between its last def (could be livein) and this
 539   // instruction, then go ahead and make this transformation.
 540   unsigned LastDefB = 0;
 541   if (!noUseAfterLastDef(regB, Dist, LastDefB))
 542     return true;
 543
 544   // Since there are no intervening uses for both registers, then commute
 545   // if the def of regC is closer. Its live interval is shorter.
 546   return LastDefB && LastDefC && LastDefC > LastDefB;
 547 }
 548
 549 /// commuteInstruction - Commute a two-address instruction and update the basic
 550 /// block, distance map, and live variables if needed. Return true if it is
 551 /// successful.
 552 bool TwoAddressInstructionPass::
 553 commuteInstruction(MachineBasicBlock::iterator &mi,
 554                    unsigned RegB, unsigned RegC, unsigned Dist) {
 555   MachineInstr *MI = mi;
 556   DEBUG(dbgs() << "2addr: COMMUTING  : " << *MI);
 557   MachineInstr *NewMI = TII->commuteInstruction(MI);
 558
 559   if (NewMI == 0) {
 560     DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
 561     return false;
 562   }
 563
 564   DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
 565   // If the instruction changed to commute it, update livevar.
 566   if (NewMI != MI) {
 567     if (LV)
 568       // Update live variables
 569       LV->replaceKillInstruction(RegC, MI, NewMI);
 570     if (LIS)
 571       LIS->ReplaceMachineInstrInMaps(MI, NewMI);
 572
 573     MBB->insert(mi, NewMI);           // Insert the new inst
 574     MBB->erase(mi);                   // Nuke the old inst.
 575     mi = NewMI;
 576     DistanceMap.insert(std::make_pair(NewMI, Dist));
 577   }
 578
 579   // Update source register map.
 580   unsigned FromRegC = getMappedReg(RegC, SrcRegMap);
 581   if (FromRegC) {
 582     unsigned RegA = MI->getOperand(0).getReg();
 583     SrcRegMap[RegA] = FromRegC;
 584   }
 585
 586   return true;
 587 }
 588
 589 /// isProfitableToConv3Addr - Return true if it is profitable to convert the
 590 /// given 2-address instruction to a 3-address one.
 591 bool
 592 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){
 593   // Look for situations like this:
 594   // %reg1024<def> = MOV r1
 595   // %reg1025<def> = MOV r0
 596   // %reg1026<def> = ADD %reg1024, %reg1025
 597   // r2            = MOV %reg1026
 598   // Turn ADD into a 3-address instruction to avoid a copy.
 599   unsigned FromRegB = getMappedReg(RegB, SrcRegMap);
 600   if (!FromRegB)
 601     return false;
 602   unsigned ToRegA = getMappedReg(RegA, DstRegMap);
 603   return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI));
 604 }
 605
 606 /// convertInstTo3Addr - Convert the specified two-address instruction into a
 607 /// three address one. Return true if this transformation was successful.
 608 bool
 609 TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi,
 610                                               MachineBasicBlock::iterator &nmi,
 611                                               unsigned RegA, unsigned RegB,
 612                                               unsigned Dist) {
 613   // FIXME: Why does convertToThreeAddress() need an iterator reference?
 614   MachineFunction::iterator MFI = MBB;
 615   MachineInstr *NewMI = TII->convertToThreeAddress(MFI, mi, LV);
 616   assert(MBB == MFI && "convertToThreeAddress changed iterator reference");
 617   if (!NewMI)
 618     return false;
 619
 620   DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
 621   DEBUG(dbgs() << "2addr:         TO 3-ADDR: " << *NewMI);
 622   bool Sunk = false;
 623
 624   if (LIS)
 625     LIS->ReplaceMachineInstrInMaps(mi, NewMI);
 626
 627   if (NewMI->findRegisterUseOperand(RegB, false, TRI))
 628     // FIXME: Temporary workaround. If the new instruction doesn't
 629     // uses RegB, convertToThreeAddress must have created more
 630     // then one instruction.
 631     Sunk = sink3AddrInstruction(NewMI, RegB, mi);
 632
 633   MBB->erase(mi); // Nuke the old inst.
 634
 635   if (!Sunk) {
 636     DistanceMap.insert(std::make_pair(NewMI, Dist));
 637     mi = NewMI;
 638     nmi = llvm::next(mi);
 639   }
 640
 641   // Update source and destination register maps.
 642   SrcRegMap.erase(RegA);
 643   DstRegMap.erase(RegB);
 644   return true;
 645 }
 646
 647 /// scanUses - Scan forward recursively for only uses, update maps if the use
 648 /// is a copy or a two-address instruction.
 649 void
 650 TwoAddressInstructionPass::scanUses(unsigned DstReg) {
 651   SmallVector<unsigned, 4> VirtRegPairs;
 652   bool IsDstPhys;
 653   bool IsCopy = false;
 654   unsigned NewReg = 0;
 655   unsigned Reg = DstReg;
 656   while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy,
 657                                                       NewReg, IsDstPhys)) {
 658     if (IsCopy && !Processed.insert(UseMI))
 659       break;
 660
 661     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
 662     if (DI != DistanceMap.end())
 663       // Earlier in the same MBB.Reached via a back edge.
 664       break;
 665
 666     if (IsDstPhys) {
 667       VirtRegPairs.push_back(NewReg);
 668       break;
 669     }
 670     bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second;
 671     if (!isNew)
 672       assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!");
 673     VirtRegPairs.push_back(NewReg);
 674     Reg = NewReg;
 675   }
 676
 677   if (!VirtRegPairs.empty()) {
 678     unsigned ToReg = VirtRegPairs.back();
 679     VirtRegPairs.pop_back();
 680     while (!VirtRegPairs.empty()) {
 681       unsigned FromReg = VirtRegPairs.back();
 682       VirtRegPairs.pop_back();
 683       bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
 684       if (!isNew)
 685         assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
 686       ToReg = FromReg;
 687     }
 688     bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second;
 689     if (!isNew)
 690       assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
 691   }
 692 }
 693
 694 /// processCopy - If the specified instruction is not yet processed, process it
 695 /// if it's a copy. For a copy instruction, we find the physical registers the
 696 /// source and destination registers might be mapped to. These are kept in
 697 /// point-to maps used to determine future optimizations. e.g.
 698 /// v1024 = mov r0
 699 /// v1025 = mov r1
 700 /// v1026 = add v1024, v1025
 701 /// r1    = mov r1026
 702 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially
 703 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
 704 /// potentially joined with r1 on the output side. It's worthwhile to commute
 705 /// 'add' to eliminate a copy.
 706 void TwoAddressInstructionPass::processCopy(MachineInstr *MI) {
 707   if (Processed.count(MI))
 708     return;
 709
 710   bool IsSrcPhys, IsDstPhys;
 711   unsigned SrcReg, DstReg;
 712   if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
 713     return;
 714
 715   if (IsDstPhys && !IsSrcPhys)
 716     DstRegMap.insert(std::make_pair(SrcReg, DstReg));
 717   else if (!IsDstPhys && IsSrcPhys) {
 718     bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
 719     if (!isNew)
 720       assert(SrcRegMap[DstReg] == SrcReg &&
 721              "Can't map to two src physical registers!");
 722
 723     scanUses(DstReg);
 724   }
 725
 726   Processed.insert(MI);
 727   return;
 728 }
 729
 730 /// rescheduleMIBelowKill - If there is one more local instruction that reads
 731 /// 'Reg' and it kills 'Reg, consider moving the instruction below the kill
 732 /// instruction in order to eliminate the need for the copy.
 733 bool TwoAddressInstructionPass::
 734 rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
 735                       MachineBasicBlock::iterator &nmi,
 736                       unsigned Reg) {
 737   // Bail immediately if we don't have LV or LIS available. We use them to find
 738   // kills efficiently.
 739   if (!LV && !LIS)
 740     return false;
 741
 742   MachineInstr *MI = &*mi;
 743   DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
 744   if (DI == DistanceMap.end())
 745     // Must be created from unfolded load. Don't waste time trying this.
 746     return false;
 747
 748   MachineInstr *KillMI = 0;
 749   if (LIS) {
 750     LiveInterval &LI = LIS->getInterval(Reg);
 751     assert(LI.end() != LI.begin() &&
 752            "Reg should not have empty live interval.");
 753
 754     SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
 755     LiveInterval::const_iterator I = LI.find(MBBEndIdx);
 756     if (I != LI.end() && I->start < MBBEndIdx)
 757       return false;
 758
 759     --I;
 760     KillMI = LIS->getInstructionFromIndex(I->end);
 761   } else {
 762     KillMI = LV->getVarInfo(Reg).findKill(MBB);
 763   }
 764   if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
 765     // Don't mess with copies, they may be coalesced later.
 766     return false;
 767
 768   if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
 769       KillMI->isBranch() || KillMI->isTerminator())
 770     // Don't move pass calls, etc.
 771     return false;
 772
 773   unsigned DstReg;
 774   if (isTwoAddrUse(*KillMI, Reg, DstReg))
 775     return false;
 776
 777   bool SeenStore = true;
 778   if (!MI->isSafeToMove(TII, AA, SeenStore))
 779     return false;
 780
 781   if (TII->getInstrLatency(InstrItins, MI) > 1)
 782     // FIXME: Needs more sophisticated heuristics.
 783     return false;
 784
 785   SmallSet<unsigned, 2> Uses;
 786   SmallSet<unsigned, 2> Kills;
 787   SmallSet<unsigned, 2> Defs;
 788   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 789     const MachineOperand &MO = MI->getOperand(i);
 790     if (!MO.isReg())
 791       continue;
 792     unsigned MOReg = MO.getReg();
 793     if (!MOReg)
 794       continue;
 795     if (MO.isDef())
 796       Defs.insert(MOReg);
 797     else {
 798       Uses.insert(MOReg);
 799       if (MOReg != Reg && (MO.isKill() ||
 800                            (LIS && isPlainlyKilled(MI, MOReg, LIS))))
 801         Kills.insert(MOReg);
 802     }
 803   }
 804
 805   // Move the copies connected to MI down as well.
 806   MachineBasicBlock::iterator Begin = MI;
 807   MachineBasicBlock::iterator AfterMI = llvm::next(Begin);
 808
 809   MachineBasicBlock::iterator End = AfterMI;
 810   while (End->isCopy() && Defs.count(End->getOperand(1).getReg())) {
 811     Defs.insert(End->getOperand(0).getReg());
 812     ++End;
 813   }
 814
 815   // Check if the reschedule will not break depedencies.
 816   unsigned NumVisited = 0;
 817   MachineBasicBlock::iterator KillPos = KillMI;
 818   ++KillPos;
 819   for (MachineBasicBlock::iterator I = End; I != KillPos; ++I) {
 820     MachineInstr *OtherMI = I;
 821     // DBG_VALUE cannot be counted against the limit.
 822     if (OtherMI->isDebugValue())
 823       continue;
 824     if (NumVisited > 10)  // FIXME: Arbitrary limit to reduce compile time cost.
 825       return false;
 826     ++NumVisited;
 827     if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() ||
 828         OtherMI->isBranch() || OtherMI->isTerminator())
 829       // Don't move pass calls, etc.
 830       return false;
 831     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 832       const MachineOperand &MO = OtherMI->getOperand(i);
 833       if (!MO.isReg())
 834         continue;
 835       unsigned MOReg = MO.getReg();
 836       if (!MOReg)
 837         continue;
 838       if (MO.isDef()) {
 839         if (Uses.count(MOReg))
 840           // Physical register use would be clobbered.
 841           return false;
 842         if (!MO.isDead() && Defs.count(MOReg))
 843           // May clobber a physical register def.
 844           // FIXME: This may be too conservative. It's ok if the instruction
 845           // is sunken completely below the use.
 846           return false;
 847       } else {
 848         if (Defs.count(MOReg))
 849           return false;
 850         bool isKill = MO.isKill() ||
 851                       (LIS && isPlainlyKilled(OtherMI, MOReg, LIS));
 852         if (MOReg != Reg &&
 853             ((isKill && Uses.count(MOReg)) || Kills.count(MOReg)))
 854           // Don't want to extend other live ranges and update kills.
 855           return false;
 856         if (MOReg == Reg && !isKill)
 857           // We can't schedule across a use of the register in question.
 858           return false;
 859         // Ensure that if this is register in question, its the kill we expect.
 860         assert((MOReg != Reg || OtherMI == KillMI) &&
 861                "Found multiple kills of a register in a basic block");
 862       }
 863     }
 864   }
 865
 866   // Move debug info as well.
 867   while (Begin != MBB->begin() && llvm::prior(Begin)->isDebugValue())
 868     --Begin;
 869
 870   nmi = End;
 871   MachineBasicBlock::iterator InsertPos = KillPos;
 872   if (LIS) {
 873     // We have to move the copies first so that the MBB is still well-formed
 874     // when calling handleMove().
 875     for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) {
 876       MachineInstr *CopyMI = MBBI;
 877       ++MBBI;
 878       MBB->splice(InsertPos, MBB, CopyMI);
 879       LIS->handleMove(CopyMI);
 880       InsertPos = CopyMI;
 881     }
 882     End = llvm::next(MachineBasicBlock::iterator(MI));
 883   }
 884
 885   // Copies following MI may have been moved as well.
 886   MBB->splice(InsertPos, MBB, Begin, End);
 887   DistanceMap.erase(DI);
 888
 889   // Update live variables
 890   if (LIS) {
 891     LIS->handleMove(MI);
 892   } else {
 893     LV->removeVirtualRegisterKilled(Reg, KillMI);
 894     LV->addVirtualRegisterKilled(Reg, MI);
 895   }
 896
 897   DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI);
 898   return true;
 899 }
 900
 901 /// isDefTooClose - Return true if the re-scheduling will put the given
 902 /// instruction too close to the defs of its register dependencies.
 903 bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist,
 904                                               MachineInstr *MI) {
 905   for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(Reg),
 906          DE = MRI->def_end(); DI != DE; ++DI) {
 907     MachineInstr *DefMI = &*DI;
 908     if (DefMI->getParent() != MBB || DefMI->isCopy() || DefMI->isCopyLike())
 909       continue;
 910     if (DefMI == MI)
 911       return true; // MI is defining something KillMI uses
 912     DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(DefMI);
 913     if (DDI == DistanceMap.end())
 914       return true;  // Below MI
 915     unsigned DefDist = DDI->second;
 916     assert(Dist > DefDist && "Visited def already?");
 917     if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
 918       return true;
 919   }
 920   return false;
 921 }
 922
 923 /// rescheduleKillAboveMI - If there is one more local instruction that reads
 924 /// 'Reg' and it kills 'Reg, consider moving the kill instruction above the
 925 /// current two-address instruction in order to eliminate the need for the
 926 /// copy.
 927 bool TwoAddressInstructionPass::
 928 rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
 929                       MachineBasicBlock::iterator &nmi,
 930                       unsigned Reg) {
 931   // Bail immediately if we don't have LV or LIS available. We use them to find
 932   // kills efficiently.
 933   if (!LV && !LIS)
 934     return false;
 935
 936   MachineInstr *MI = &*mi;
 937   DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
 938   if (DI == DistanceMap.end())
 939     // Must be created from unfolded load. Don't waste time trying this.
 940     return false;
 941
 942   MachineInstr *KillMI = 0;
 943   if (LIS) {
 944     LiveInterval &LI = LIS->getInterval(Reg);
 945     assert(LI.end() != LI.begin() &&
 946            "Reg should not have empty live interval.");
 947
 948     SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
 949     LiveInterval::const_iterator I = LI.find(MBBEndIdx);
 950     if (I != LI.end() && I->start < MBBEndIdx)
 951       return false;
 952
 953     --I;
 954     KillMI = LIS->getInstructionFromIndex(I->end);
 955   } else {
 956     KillMI = LV->getVarInfo(Reg).findKill(MBB);
 957   }
 958   if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
 959     // Don't mess with copies, they may be coalesced later.
 960     return false;
 961
 962   unsigned DstReg;
 963   if (isTwoAddrUse(*KillMI, Reg, DstReg))
 964     return false;
 965
 966   bool SeenStore = true;
 967   if (!KillMI->isSafeToMove(TII, AA, SeenStore))
 968     return false;
 969
 970   SmallSet<unsigned, 2> Uses;
 971   SmallSet<unsigned, 2> Kills;
 972   SmallSet<unsigned, 2> Defs;
 973   SmallSet<unsigned, 2> LiveDefs;
 974   for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) {
 975     const MachineOperand &MO = KillMI->getOperand(i);
 976     if (!MO.isReg())
 977       continue;
 978     unsigned MOReg = MO.getReg();
 979     if (MO.isUse()) {
 980       if (!MOReg)
 981         continue;
 982       if (isDefTooClose(MOReg, DI->second, MI))
 983         return false;
 984       bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS));
 985       if (MOReg == Reg && !isKill)
 986         return false;
 987       Uses.insert(MOReg);
 988       if (isKill && MOReg != Reg)
 989         Kills.insert(MOReg);
 990     } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
 991       Defs.insert(MOReg);
 992       if (!MO.isDead())
 993         LiveDefs.insert(MOReg);
 994     }
 995   }
 996
 997   // Check if the reschedule will not break depedencies.
 998   unsigned NumVisited = 0;
 999   MachineBasicBlock::iterator KillPos = KillMI;
1000   for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) {
1001     MachineInstr *OtherMI = I;
1002     // DBG_VALUE cannot be counted against the limit.
1003     if (OtherMI->isDebugValue())
1004       continue;
1005     if (NumVisited > 10)  // FIXME: Arbitrary limit to reduce compile time cost.
1006       return false;
1007     ++NumVisited;
1008     if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() ||
1009         OtherMI->isBranch() || OtherMI->isTerminator())
1010       // Don't move pass calls, etc.
1011       return false;
1012     SmallVector<unsigned, 2> OtherDefs;
1013     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
1014       const MachineOperand &MO = OtherMI->getOperand(i);
1015       if (!MO.isReg())
1016         continue;
1017       unsigned MOReg = MO.getReg();
1018       if (!MOReg)
1019         continue;
1020       if (MO.isUse()) {
1021         if (Defs.count(MOReg))
1022           // Moving KillMI can clobber the physical register if the def has
1023           // not been seen.
1024           return false;
1025         if (Kills.count(MOReg))
1026           // Don't want to extend other live ranges and update kills.
1027           return false;
1028         if (OtherMI != MI && MOReg == Reg &&
1029             !(MO.isKill() || (LIS && isPlainlyKilled(OtherMI, MOReg, LIS))))
1030           // We can't schedule across a use of the register in question.
1031           return false;
1032       } else {
1033         OtherDefs.push_back(MOReg);
1034       }
1035     }
1036
1037     for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) {
1038       unsigned MOReg = OtherDefs[i];
1039       if (Uses.count(MOReg))
1040         return false;
1041       if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
1042           LiveDefs.count(MOReg))
1043         return false;
1044       // Physical register def is seen.
1045       Defs.erase(MOReg);
1046     }
1047   }
1048
1049   // Move the old kill above MI, don't forget to move debug info as well.
1050   MachineBasicBlock::iterator InsertPos = mi;
1051   while (InsertPos != MBB->begin() && llvm::prior(InsertPos)->isDebugValue())
1052     --InsertPos;
1053   MachineBasicBlock::iterator From = KillMI;
1054   MachineBasicBlock::iterator To = llvm::next(From);
1055   while (llvm::prior(From)->isDebugValue())
1056     --From;
1057   MBB->splice(InsertPos, MBB, From, To);
1058
1059   nmi = llvm::prior(InsertPos); // Backtrack so we process the moved instr.
1060   DistanceMap.erase(DI);
1061
1062   // Update live variables
1063   if (LIS) {
1064     LIS->handleMove(KillMI);
1065   } else {
1066     LV->removeVirtualRegisterKilled(Reg, KillMI);
1067     LV->addVirtualRegisterKilled(Reg, MI);
1068   }
1069
1070   DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1071   return true;
1072 }
1073
1074 /// tryInstructionTransform - For the case where an instruction has a single
1075 /// pair of tied register operands, attempt some transformations that may
1076 /// either eliminate the tied operands or improve the opportunities for
1077 /// coalescing away the register copy.  Returns true if no copy needs to be
1078 /// inserted to untie mi's operands (either because they were untied, or
1079 /// because mi was rescheduled, and will be visited again later).
1080 bool TwoAddressInstructionPass::
1081 tryInstructionTransform(MachineBasicBlock::iterator &mi,
1082                         MachineBasicBlock::iterator &nmi,
1083                         unsigned SrcIdx, unsigned DstIdx, unsigned Dist) {
1084   if (OptLevel == CodeGenOpt::None)
1085     return false;
1086
1087   MachineInstr &MI = *mi;
1088   unsigned regA = MI.getOperand(DstIdx).getReg();
1089   unsigned regB = MI.getOperand(SrcIdx).getReg();
1090
1091   assert(TargetRegisterInfo::isVirtualRegister(regB) &&
1092          "cannot make instruction into two-address form");
1093   bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true);
1094
1095   if (TargetRegisterInfo::isVirtualRegister(regA))
1096     scanUses(regA);
1097
1098   // Check if it is profitable to commute the operands.
1099   unsigned SrcOp1, SrcOp2;
1100   unsigned regC = 0;
1101   unsigned regCIdx = ~0U;
1102   bool TryCommute = false;
1103   bool AggressiveCommute = false;
1104   if (MI.isCommutable() && MI.getNumOperands() >= 3 &&
1105       TII->findCommutedOpIndices(&MI, SrcOp1, SrcOp2)) {
1106     if (SrcIdx == SrcOp1)
1107       regCIdx = SrcOp2;
1108     else if (SrcIdx == SrcOp2)
1109       regCIdx = SrcOp1;
1110
1111     if (regCIdx != ~0U) {
1112       regC = MI.getOperand(regCIdx).getReg();
1113       if (!regBKilled && isKilled(MI, regC, MRI, TII, LIS, false))
1114         // If C dies but B does not, swap the B and C operands.
1115         // This makes the live ranges of A and C joinable.
1116         TryCommute = true;
1117       else if (isProfitableToCommute(regA, regB, regC, &MI, Dist)) {
1118         TryCommute = true;
1119         AggressiveCommute = true;
1120       }
1121     }
1122   }
1123
1124   // If it's profitable to commute, try to do so.
1125   if (TryCommute && commuteInstruction(mi, regB, regC, Dist)) {
1126     ++NumCommuted;
1127     if (AggressiveCommute)
1128       ++NumAggrCommuted;
1129     return false;
1130   }
1131
1132   // If there is one more use of regB later in the same MBB, consider
1133   // re-schedule this MI below it.
1134   if (rescheduleMIBelowKill(mi, nmi, regB)) {
1135     ++NumReSchedDowns;
1136     return true;
1137   }
1138
1139   if (MI.isConvertibleTo3Addr()) {
1140     // This instruction is potentially convertible to a true
1141     // three-address instruction.  Check if it is profitable.
1142     if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1143       // Try to convert it.
1144       if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
1145         ++NumConvertedTo3Addr;
1146         return true; // Done with this instruction.
1147       }
1148     }
1149   }
1150
1151   // If there is one more use of regB later in the same MBB, consider
1152   // re-schedule it before this MI if it's legal.
1153   if (rescheduleKillAboveMI(mi, nmi, regB)) {
1154     ++NumReSchedUps;
1155     return true;
1156   }
1157
1158   // If this is an instruction with a load folded into it, try unfolding
1159   // the load, e.g. avoid this:
1160   //   movq %rdx, %rcx
1161   //   addq (%rax), %rcx
1162   // in favor of this:
1163   //   movq (%rax), %rcx
1164   //   addq %rdx, %rcx
1165   // because it's preferable to schedule a load than a register copy.
1166   if (MI.mayLoad() && !regBKilled) {
1167     // Determine if a load can be unfolded.
1168     unsigned LoadRegIndex;
1169     unsigned NewOpc =
1170       TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
1171                                       /*UnfoldLoad=*/true,
1172                                       /*UnfoldStore=*/false,
1173                                       &LoadRegIndex);
1174     if (NewOpc != 0) {
1175       const MCInstrDesc &UnfoldMCID = TII->get(NewOpc);
1176       if (UnfoldMCID.getNumDefs() == 1) {
1177         // Unfold the load.
1178         DEBUG(dbgs() << "2addr:   UNFOLDING: " << MI);
1179         const TargetRegisterClass *RC =
1180           TRI->getAllocatableClass(
1181             TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF));
1182         unsigned Reg = MRI->createVirtualRegister(RC);
1183         SmallVector<MachineInstr *, 2> NewMIs;
1184         if (!TII->unfoldMemoryOperand(*MF, &MI, Reg,
1185                                       /*UnfoldLoad=*/true,/*UnfoldStore=*/false,
1186                                       NewMIs)) {
1187           DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1188           return false;
1189         }
1190         assert(NewMIs.size() == 2 &&
1191                "Unfolded a load into multiple instructions!");
1192         // The load was previously folded, so this is the only use.
1193         NewMIs[1]->addRegisterKilled(Reg, TRI);
1194
1195         // Tentatively insert the instructions into the block so that they
1196         // look "normal" to the transformation logic.
1197         MBB->insert(mi, NewMIs[0]);
1198         MBB->insert(mi, NewMIs[1]);
1199
1200         DEBUG(dbgs() << "2addr:    NEW LOAD: " << *NewMIs[0]
1201                      << "2addr:    NEW INST: " << *NewMIs[1]);
1202
1203         // Transform the instruction, now that it no longer has a load.
1204         unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA);
1205         unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB);
1206         MachineBasicBlock::iterator NewMI = NewMIs[1];
1207         bool TransformSuccess =
1208           tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist);
1209         if (TransformSuccess ||
1210             NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1211           // Success, or at least we made an improvement. Keep the unfolded
1212           // instructions and discard the original.
1213           if (LV) {
1214             for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1215               MachineOperand &MO = MI.getOperand(i);
1216               if (MO.isReg() &&
1217                   TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
1218                 if (MO.isUse()) {
1219                   if (MO.isKill()) {
1220                     if (NewMIs[0]->killsRegister(MO.getReg()))
1221                       LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]);
1222                     else {
1223                       assert(NewMIs[1]->killsRegister(MO.getReg()) &&
1224                              "Kill missing after load unfold!");
1225                       LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]);
1226                     }
1227                   }
1228                 } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) {
1229                   if (NewMIs[1]->registerDefIsDead(MO.getReg()))
1230                     LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]);
1231                   else {
1232                     assert(NewMIs[0]->registerDefIsDead(MO.getReg()) &&
1233                            "Dead flag missing after load unfold!");
1234                     LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]);
1235                   }
1236                 }
1237               }
1238             }
1239             LV->addVirtualRegisterKilled(Reg, NewMIs[1]);
1240           }
1241
1242           SmallVector<unsigned, 4> OrigRegs;
1243           if (LIS) {
1244             for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
1245                  MOE = MI.operands_end(); MOI != MOE; ++MOI) {
1246               if (MOI->isReg())
1247                 OrigRegs.push_back(MOI->getReg());
1248             }
1249           }
1250
1251           MI.eraseFromParent();
1252
1253           // Update LiveIntervals.
1254           if (LIS) {
1255             MachineBasicBlock::iterator Begin(NewMIs[0]);
1256             MachineBasicBlock::iterator End(NewMIs[1]);
1257             LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1258           }
1259
1260           mi = NewMIs[1];
1261           if (TransformSuccess)
1262             return true;
1263         } else {
1264           // Transforming didn't eliminate the tie and didn't lead to an
1265           // improvement. Clean up the unfolded instructions and keep the
1266           // original.
1267           DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1268           NewMIs[0]->eraseFromParent();
1269           NewMIs[1]->eraseFromParent();
1270         }
1271       }
1272     }
1273   }
1274
1275   return false;
1276 }
1277
1278 // Collect tied operands of MI that need to be handled.
1279 // Rewrite trivial cases immediately.
1280 // Return true if any tied operands where found, including the trivial ones.
1281 bool TwoAddressInstructionPass::
1282 collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
1283   const MCInstrDesc &MCID = MI->getDesc();
1284   bool AnyOps = false;
1285   unsigned NumOps = MI->getNumOperands();
1286
1287   for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1288     unsigned DstIdx = 0;
1289     if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1290       continue;
1291     AnyOps = true;
1292     MachineOperand &SrcMO = MI->getOperand(SrcIdx);
1293     MachineOperand &DstMO = MI->getOperand(DstIdx);
1294     unsigned SrcReg = SrcMO.getReg();
1295     unsigned DstReg = DstMO.getReg();
1296     // Tied constraint already satisfied?
1297     if (SrcReg == DstReg)
1298       continue;
1299
1300     assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1301
1302     // Deal with <undef> uses immediately - simply rewrite the src operand.
1303     if (SrcMO.isUndef()) {
1304       // Constrain the DstReg register class if required.
1305       if (TargetRegisterInfo::isVirtualRegister(DstReg))
1306         if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
1307                                                              TRI, *MF))
1308           MRI->constrainRegClass(DstReg, RC);
1309       SrcMO.setReg(DstReg);
1310       DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1311       continue;
1312     }
1313     TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1314   }
1315   return AnyOps;
1316 }
1317
1318 // Process a list of tied MI operands that all use the same source register.
1319 // The tied pairs are of the form (SrcIdx, DstIdx).
1320 void
1321 TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
1322                                             TiedPairList &TiedPairs,
1323                                             unsigned &Dist) {
1324   bool IsEarlyClobber = false;
1325   for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1326     const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second);
1327     IsEarlyClobber |= DstMO.isEarlyClobber();
1328   }
1329
1330   bool RemovedKillFlag = false;
1331   bool AllUsesCopied = true;
1332   unsigned LastCopiedReg = 0;
1333   SlotIndex LastCopyIdx;
1334   unsigned RegB = 0;
1335   for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1336     unsigned SrcIdx = TiedPairs[tpi].first;
1337     unsigned DstIdx = TiedPairs[tpi].second;
1338
1339     const MachineOperand &DstMO = MI->getOperand(DstIdx);
1340     unsigned RegA = DstMO.getReg();
1341
1342     // Grab RegB from the instruction because it may have changed if the
1343     // instruction was commuted.
1344     RegB = MI->getOperand(SrcIdx).getReg();
1345
1346     if (RegA == RegB) {
1347       // The register is tied to multiple destinations (or else we would
1348       // not have continued this far), but this use of the register
1349       // already matches the tied destination.  Leave it.
1350       AllUsesCopied = false;
1351       continue;
1352     }
1353     LastCopiedReg = RegA;
1354
1355     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
1356            "cannot make instruction into two-address form");
1357
1358 #ifndef NDEBUG
1359     // First, verify that we don't have a use of "a" in the instruction
1360     // (a = b + a for example) because our transformation will not
1361     // work. This should never occur because we are in SSA form.
1362     for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1363       assert(i == DstIdx ||
1364              !MI->getOperand(i).isReg() ||
1365              MI->getOperand(i).getReg() != RegA);
1366 #endif
1367
1368     // Emit a copy.
1369     BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1370             TII->get(TargetOpcode::COPY), RegA).addReg(RegB);
1371
1372     // Update DistanceMap.
1373     MachineBasicBlock::iterator PrevMI = MI;
1374     --PrevMI;
1375     DistanceMap.insert(std::make_pair(PrevMI, Dist));
1376     DistanceMap[MI] = ++Dist;
1377
1378     if (LIS) {
1379       LastCopyIdx = LIS->InsertMachineInstrInMaps(PrevMI).getRegSlot();
1380
1381       if (TargetRegisterInfo::isVirtualRegister(RegA)) {
1382         LiveInterval &LI = LIS->getInterval(RegA);
1383         VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1384         SlotIndex endIdx =
1385           LIS->getInstructionIndex(MI).getRegSlot(IsEarlyClobber);
1386         LI.addRange(LiveRange(LastCopyIdx, endIdx, VNI));
1387       }
1388     }
1389
1390     DEBUG(dbgs() << "\t\tprepend:\t" << *PrevMI);
1391
1392     MachineOperand &MO = MI->getOperand(SrcIdx);
1393     assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1394            "inconsistent operand info for 2-reg pass");
1395     if (MO.isKill()) {
1396       MO.setIsKill(false);
1397       RemovedKillFlag = true;
1398     }
1399
1400     // Make sure regA is a legal regclass for the SrcIdx operand.
1401     if (TargetRegisterInfo::isVirtualRegister(RegA) &&
1402         TargetRegisterInfo::isVirtualRegister(RegB))
1403       MRI->constrainRegClass(RegA, MRI->getRegClass(RegB));
1404
1405     MO.setReg(RegA);
1406
1407     // Propagate SrcRegMap.
1408     SrcRegMap[RegA] = RegB;
1409   }
1410
1411
1412   if (AllUsesCopied) {
1413     if (!IsEarlyClobber) {
1414       // Replace other (un-tied) uses of regB with LastCopiedReg.
1415       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1416         MachineOperand &MO = MI->getOperand(i);
1417         if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1418           if (MO.isKill()) {
1419             MO.setIsKill(false);
1420             RemovedKillFlag = true;
1421           }
1422           MO.setReg(LastCopiedReg);
1423         }
1424       }
1425     }
1426
1427     // Update live variables for regB.
1428     if (RemovedKillFlag && LV && LV->getVarInfo(RegB).removeKill(MI)) {
1429       MachineBasicBlock::iterator PrevMI = MI;
1430       --PrevMI;
1431       LV->addVirtualRegisterKilled(RegB, PrevMI);
1432     }
1433
1434     // Update LiveIntervals.
1435     if (LIS) {
1436       LiveInterval &LI = LIS->getInterval(RegB);
1437       SlotIndex MIIdx = LIS->getInstructionIndex(MI);
1438       LiveInterval::const_iterator I = LI.find(MIIdx);
1439       assert(I != LI.end() && "RegB must be live-in to use.");
1440
1441       SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber);
1442       if (I->end == UseIdx)
1443         LI.removeRange(LastCopyIdx, UseIdx);
1444     }
1445
1446   } else if (RemovedKillFlag) {
1447     // Some tied uses of regB matched their destination registers, so
1448     // regB is still used in this instruction, but a kill flag was
1449     // removed from a different tied use of regB, so now we need to add
1450     // a kill flag to one of the remaining uses of regB.
1451     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1452       MachineOperand &MO = MI->getOperand(i);
1453       if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1454         MO.setIsKill(true);
1455         break;
1456       }
1457     }
1458   }
1459 }
1460
1461 /// runOnMachineFunction - Reduce two-address instructions to two operands.
1462 ///
1463 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
1464   MF = &Func;
1465   const TargetMachine &TM = MF->getTarget();
1466   MRI = &MF->getRegInfo();
1467   TII = TM.getInstrInfo();
1468   TRI = TM.getRegisterInfo();
1469   InstrItins = TM.getInstrItineraryData();
1470   LV = getAnalysisIfAvailable<LiveVariables>();
1471   LIS = getAnalysisIfAvailable<LiveIntervals>();
1472   AA = &getAnalysis<AliasAnalysis>();
1473   OptLevel = TM.getOptLevel();
1474
1475   bool MadeChange = false;
1476
1477   DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1478   DEBUG(dbgs() << "********** Function: "
1479         << MF->getName() << '\n');
1480
1481   // This pass takes the function out of SSA form.
1482   MRI->leaveSSA();
1483
1484   TiedOperandMap TiedOperands;
1485   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
1486        MBBI != MBBE; ++MBBI) {
1487     MBB = MBBI;
1488     unsigned Dist = 0;
1489     DistanceMap.clear();
1490     SrcRegMap.clear();
1491     DstRegMap.clear();
1492     Processed.clear();
1493     for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1494          mi != me; ) {
1495       MachineBasicBlock::iterator nmi = llvm::next(mi);
1496       if (mi->isDebugValue()) {
1497         mi = nmi;
1498         continue;
1499       }
1500
1501       // Expand REG_SEQUENCE instructions. This will position mi at the first
1502       // expanded instruction.
1503       if (mi->isRegSequence())
1504         eliminateRegSequence(mi);
1505
1506       DistanceMap.insert(std::make_pair(mi, ++Dist));
1507
1508       processCopy(&*mi);
1509
1510       // First scan through all the tied register uses in this instruction
1511       // and record a list of pairs of tied operands for each register.
1512       if (!collectTiedOperands(mi, TiedOperands)) {
1513         mi = nmi;
1514         continue;
1515       }
1516
1517       ++NumTwoAddressInstrs;
1518       MadeChange = true;
1519       DEBUG(dbgs() << '\t' << *mi);
1520
1521       // If the instruction has a single pair of tied operands, try some
1522       // transformations that may either eliminate the tied operands or
1523       // improve the opportunities for coalescing away the register copy.
1524       if (TiedOperands.size() == 1) {
1525         SmallVector<std::pair<unsigned, unsigned>, 4> &TiedPairs
1526           = TiedOperands.begin()->second;
1527         if (TiedPairs.size() == 1) {
1528           unsigned SrcIdx = TiedPairs[0].first;
1529           unsigned DstIdx = TiedPairs[0].second;
1530           unsigned SrcReg = mi->getOperand(SrcIdx).getReg();
1531           unsigned DstReg = mi->getOperand(DstIdx).getReg();
1532           if (SrcReg != DstReg &&
1533               tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist)) {
1534             // The tied operands have been eliminated or shifted further down the
1535             // block to ease elimination. Continue processing with 'nmi'.
1536             TiedOperands.clear();
1537             mi = nmi;
1538             continue;
1539           }
1540         }
1541       }
1542
1543       // Now iterate over the information collected above.
1544       for (TiedOperandMap::iterator OI = TiedOperands.begin(),
1545              OE = TiedOperands.end(); OI != OE; ++OI) {
1546         processTiedPairs(mi, OI->second, Dist);
1547         DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1548       }
1549
1550       // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1551       if (mi->isInsertSubreg()) {
1552         // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1553         // To   %reg:subidx = COPY %subreg
1554         unsigned SubIdx = mi->getOperand(3).getImm();
1555         mi->RemoveOperand(3);
1556         assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1557         mi->getOperand(0).setSubReg(SubIdx);
1558         mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1559         mi->RemoveOperand(1);
1560         mi->setDesc(TII->get(TargetOpcode::COPY));
1561         DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1562       }
1563
1564       // Clear TiedOperands here instead of at the top of the loop
1565       // since most instructions do not have tied operands.
1566       TiedOperands.clear();
1567       mi = nmi;
1568     }
1569   }
1570
1571   if (LIS)
1572     MF->verify(this, "After two-address instruction pass");
1573
1574   return MadeChange;
1575 }
1576
1577 /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1578 ///
1579 /// The instruction is turned into a sequence of sub-register copies:
1580 ///
1581 ///   %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1582 ///
1583 /// Becomes:
1584 ///
1585 ///   %dst:ssub0<def,undef> = COPY %v1
1586 ///   %dst:ssub1<def> = COPY %v2
1587 ///
1588 void TwoAddressInstructionPass::
1589 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1590   MachineInstr *MI = MBBI;
1591   unsigned DstReg = MI->getOperand(0).getReg();
1592   if (MI->getOperand(0).getSubReg() ||
1593       TargetRegisterInfo::isPhysicalRegister(DstReg) ||
1594       !(MI->getNumOperands() & 1)) {
1595     DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
1596     llvm_unreachable(0);
1597   }
1598
1599   SmallVector<unsigned, 4> OrigRegs;
1600   if (LIS) {
1601     OrigRegs.push_back(MI->getOperand(0).getReg());
1602     for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2)
1603       OrigRegs.push_back(MI->getOperand(i).getReg());
1604   }
1605
1606   bool DefEmitted = false;
1607   for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
1608     MachineOperand &UseMO = MI->getOperand(i);
1609     unsigned SrcReg = UseMO.getReg();
1610     unsigned SubIdx = MI->getOperand(i+1).getImm();
1611     // Nothing needs to be inserted for <undef> operands.
1612     if (UseMO.isUndef())
1613       continue;
1614
1615     // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1616     // might insert a COPY that uses SrcReg after is was killed.
1617     bool isKill = UseMO.isKill();
1618     if (isKill)
1619       for (unsigned j = i + 2; j < e; j += 2)
1620         if (MI->getOperand(j).getReg() == SrcReg) {
1621           MI->getOperand(j).setIsKill();
1622           UseMO.setIsKill(false);
1623           isKill = false;
1624           break;
1625         }
1626
1627     // Insert the sub-register copy.
1628     MachineInstr *CopyMI = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1629                                    TII->get(TargetOpcode::COPY))
1630       .addReg(DstReg, RegState::Define, SubIdx)
1631       .addOperand(UseMO);
1632
1633     // The first def needs an <undef> flag because there is no live register
1634     // before it.
1635     if (!DefEmitted) {
1636       CopyMI->getOperand(0).setIsUndef(true);
1637       // Return an iterator pointing to the first inserted instr.
1638       MBBI = CopyMI;
1639     }
1640     DefEmitted = true;
1641
1642     // Update LiveVariables' kill info.
1643     if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg))
1644       LV->replaceKillInstruction(SrcReg, MI, CopyMI);
1645
1646     DEBUG(dbgs() << "Inserted: " << *CopyMI);
1647   }
1648
1649   MachineBasicBlock::iterator EndMBBI =
1650       llvm::next(MachineBasicBlock::iterator(MI));
1651
1652   if (!DefEmitted) {
1653     DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");
1654     MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1655     for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
1656       MI->RemoveOperand(j);
1657   } else {
1658     DEBUG(dbgs() << "Eliminated: " << *MI);
1659     MI->eraseFromParent();
1660   }
1661
1662   // Udpate LiveIntervals.
1663   if (LIS)
1664     LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
1665 }