lib/CodeGen/TwoAddressInstructionPass.cpp

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