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