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