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 /// isKilled - Test if the given register value, which is used by the given
 334 /// instruction, is killed by the given instruction. This looks through
 335 /// coalescable copies to see if the original value is potentially not killed.
 336 ///
 337 /// For example, in this code:
 338 ///
 339 ///   %reg1034 = copy %reg1024
 340 ///   %reg1035 = copy %reg1025<kill>
 341 ///   %reg1036 = add %reg1034<kill>, %reg1035<kill>
 342 ///
 343 /// %reg1034 is not considered to be killed, since it is copied from a
 344 /// register which is not killed. Treating it as not killed lets the
 345 /// normal heuristics commute the (two-address) add, which lets
 346 /// coalescing eliminate the extra copy.
 347 ///
 348 static bool isKilled(MachineInstr &MI, unsigned Reg,
 349                      const MachineRegisterInfo *MRI,
 350                      const TargetInstrInfo *TII,
 351                      LiveIntervals *LIS) {
 352   MachineInstr *DefMI = &MI;
 353   for (;;) {
 354     if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) &&
 355         !LIS->isNotInMIMap(DefMI)) {
 356       // FIXME: Sometimes tryInstructionTransform() will add instructions and
 357       // test whether they can be folded before keeping them. In this case it
 358       // sets a kill before recursively calling tryInstructionTransform() again.
 359       // If there is no interval available, we assume that this instruction is
 360       // one of those. A kill flag is manually inserted on the operand so the
 361       // check below will handle it.
 362       LiveInterval &LI = LIS->getInterval(Reg);
 363       // This is to match the kill flag version where undefs don't have kill
 364       // flags.
 365       if (!LI.hasAtLeastOneValue())
 366         return false;
 367
 368       SlotIndex useIdx = LIS->getInstructionIndex(DefMI);
 369       LiveInterval::const_iterator I = LI.find(useIdx);
 370       assert(I != LI.end() && "Reg must be live-in to use.");
 371       if (!SlotIndex::isSameInstr(I->end, useIdx))
 372         return false;
 373     } else if (!DefMI->killsRegister(Reg)) {
 374       return false;
 375     }
 376
 377     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 378       return true;
 379     MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
 380     // If there are multiple defs, we can't do a simple analysis, so just
 381     // go with what the kill flag says.
 382     if (llvm::next(Begin) != MRI->def_end())
 383       return true;
 384     DefMI = &*Begin;
 385     bool IsSrcPhys, IsDstPhys;
 386     unsigned SrcReg,  DstReg;
 387     // If the def is something other than a copy, then it isn't going to
 388     // be coalesced, so follow the kill flag.
 389     if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
 390       return true;
 391     Reg = SrcReg;
 392   }
 393 }
 394
 395 /// isTwoAddrUse - Return true if the specified MI uses the specified register
 396 /// as a two-address use. If so, return the destination register by reference.
 397 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
 398   const MCInstrDesc &MCID = MI.getDesc();
 399   unsigned NumOps = MI.isInlineAsm()
 400     ? MI.getNumOperands() : MCID.getNumOperands();
 401   for (unsigned i = 0; i != NumOps; ++i) {
 402     const MachineOperand &MO = MI.getOperand(i);
 403     if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
 404       continue;
 405     unsigned ti;
 406     if (MI.isRegTiedToDefOperand(i, &ti)) {
 407       DstReg = MI.getOperand(ti).getReg();
 408       return true;
 409     }
 410   }
 411   return false;
 412 }
 413
 414 /// findOnlyInterestingUse - Given a register, if has a single in-basic block
 415 /// use, return the use instruction if it's a copy or a two-address use.
 416 static
 417 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
 418                                      MachineRegisterInfo *MRI,
 419                                      const TargetInstrInfo *TII,
 420                                      bool &IsCopy,
 421                                      unsigned &DstReg, bool &IsDstPhys) {
 422   if (!MRI->hasOneNonDBGUse(Reg))
 423     // None or more than one use.
 424     return 0;
 425   MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg);
 426   if (UseMI.getParent() != MBB)
 427     return 0;
 428   unsigned SrcReg;
 429   bool IsSrcPhys;
 430   if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
 431     IsCopy = true;
 432     return &UseMI;
 433   }
 434   IsDstPhys = false;
 435   if (isTwoAddrUse(UseMI, Reg, DstReg)) {
 436     IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 437     return &UseMI;
 438   }
 439   return 0;
 440 }
 441
 442 /// getMappedReg - Return the physical register the specified virtual register
 443 /// might be mapped to.
 444 static unsigned
 445 getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) {
 446   while (TargetRegisterInfo::isVirtualRegister(Reg))  {
 447     DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg);
 448     if (SI == RegMap.end())
 449       return 0;
 450     Reg = SI->second;
 451   }
 452   if (TargetRegisterInfo::isPhysicalRegister(Reg))
 453     return Reg;
 454   return 0;
 455 }
 456
 457 /// regsAreCompatible - Return true if the two registers are equal or aliased.
 458 ///
 459 static bool
 460 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
 461   if (RegA == RegB)
 462     return true;
 463   if (!RegA || !RegB)
 464     return false;
 465   return TRI->regsOverlap(RegA, RegB);
 466 }
 467
 468
 469 /// isProfitableToCommute - Return true if it's potentially profitable to commute
 470 /// the two-address instruction that's being processed.
 471 bool
 472 TwoAddressInstructionPass::
 473 isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
 474                       MachineInstr *MI, unsigned Dist) {
 475   if (OptLevel == CodeGenOpt::None)
 476     return false;
 477
 478   // Determine if it's profitable to commute this two address instruction. In
 479   // general, we want no uses between this instruction and the definition of
 480   // the two-address register.
 481   // e.g.
 482   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 483   // %reg1029<def> = MOV8rr %reg1028
 484   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 485   // insert => %reg1030<def> = MOV8rr %reg1028
 486   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 487   // In this case, it might not be possible to coalesce the second MOV8rr
 488   // instruction if the first one is coalesced. So it would be profitable to
 489   // commute it:
 490   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 491   // %reg1029<def> = MOV8rr %reg1028
 492   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 493   // insert => %reg1030<def> = MOV8rr %reg1029
 494   // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
 495
 496   if (!MI->killsRegister(regC))
 497     return false;
 498
 499   // Ok, we have something like:
 500   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 501   // let's see if it's worth commuting it.
 502
 503   // Look for situations like this:
 504   // %reg1024<def> = MOV r1
 505   // %reg1025<def> = MOV r0
 506   // %reg1026<def> = ADD %reg1024, %reg1025
 507   // r0            = MOV %reg1026
 508   // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
 509   unsigned ToRegA = getMappedReg(regA, DstRegMap);
 510   if (ToRegA) {
 511     unsigned FromRegB = getMappedReg(regB, SrcRegMap);
 512     unsigned FromRegC = getMappedReg(regC, SrcRegMap);
 513     bool BComp = !FromRegB || regsAreCompatible(FromRegB, ToRegA, TRI);
 514     bool CComp = !FromRegC || regsAreCompatible(FromRegC, ToRegA, TRI);
 515     if (BComp != CComp)
 516       return !BComp && CComp;
 517   }
 518
 519   // If there is a use of regC between its last def (could be livein) and this
 520   // instruction, then bail.
 521   unsigned LastDefC = 0;
 522   if (!noUseAfterLastDef(regC, Dist, LastDefC))
 523     return false;
 524
 525   // If there is a use of regB between its last def (could be livein) and this
 526   // instruction, then go ahead and make this transformation.
 527   unsigned LastDefB = 0;
 528   if (!noUseAfterLastDef(regB, Dist, LastDefB))
 529     return true;
 530
 531   // Since there are no intervening uses for both registers, then commute
 532   // if the def of regC is closer. Its live interval is shorter.
 533   return LastDefB && LastDefC && LastDefC > LastDefB;
 534 }
 535
 536 /// commuteInstruction - Commute a two-address instruction and update the basic
 537 /// block, distance map, and live variables if needed. Return true if it is
 538 /// successful.
 539 bool TwoAddressInstructionPass::
 540 commuteInstruction(MachineBasicBlock::iterator &mi,
 541                    unsigned RegB, unsigned RegC, unsigned Dist) {
 542   MachineInstr *MI = mi;
 543   DEBUG(dbgs() << "2addr: COMMUTING  : " << *MI);
 544   MachineInstr *NewMI = TII->commuteInstruction(MI);
 545
 546   if (NewMI == 0) {
 547     DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
 548     return false;
 549   }
 550
 551   DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
 552   // If the instruction changed to commute it, update livevar.
 553   if (NewMI != MI) {
 554     if (LV)
 555       // Update live variables
 556       LV->replaceKillInstruction(RegC, MI, NewMI);
 557     if (LIS)
 558       LIS->ReplaceMachineInstrInMaps(MI, NewMI);
 559
 560     MBB->insert(mi, NewMI);           // Insert the new inst
 561     MBB->erase(mi);                   // Nuke the old inst.
 562     mi = NewMI;
 563     DistanceMap.insert(std::make_pair(NewMI, Dist));
 564   }
 565
 566   // Update source register map.
 567   unsigned FromRegC = getMappedReg(RegC, SrcRegMap);
 568   if (FromRegC) {
 569     unsigned RegA = MI->getOperand(0).getReg();
 570     SrcRegMap[RegA] = FromRegC;
 571   }
 572
 573   return true;
 574 }
 575
 576 /// isProfitableToConv3Addr - Return true if it is profitable to convert the
 577 /// given 2-address instruction to a 3-address one.
 578 bool
 579 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){
 580   // Look for situations like this:
 581   // %reg1024<def> = MOV r1
 582   // %reg1025<def> = MOV r0
 583   // %reg1026<def> = ADD %reg1024, %reg1025
 584   // r2            = MOV %reg1026
 585   // Turn ADD into a 3-address instruction to avoid a copy.
 586   unsigned FromRegB = getMappedReg(RegB, SrcRegMap);
 587   if (!FromRegB)
 588     return false;
 589   unsigned ToRegA = getMappedReg(RegA, DstRegMap);
 590   return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI));
 591 }
 592
 593 /// convertInstTo3Addr - Convert the specified two-address instruction into a
 594 /// three address one. Return true if this transformation was successful.
 595 bool
 596 TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi,
 597                                               MachineBasicBlock::iterator &nmi,
 598                                               unsigned RegA, unsigned RegB,
 599                                               unsigned Dist) {
 600   // FIXME: Why does convertToThreeAddress() need an iterator reference?
 601   MachineFunction::iterator MFI = MBB;
 602   MachineInstr *NewMI = TII->convertToThreeAddress(MFI, mi, LV);
 603   assert(MBB == MFI && "convertToThreeAddress changed iterator reference");
 604   if (!NewMI)
 605     return false;
 606
 607   DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
 608   DEBUG(dbgs() << "2addr:         TO 3-ADDR: " << *NewMI);
 609   bool Sunk = false;
 610
 611   if (LIS)
 612     LIS->ReplaceMachineInstrInMaps(mi, NewMI);
 613
 614   if (NewMI->findRegisterUseOperand(RegB, false, TRI))
 615     // FIXME: Temporary workaround. If the new instruction doesn't
 616     // uses RegB, convertToThreeAddress must have created more
 617     // then one instruction.
 618     Sunk = sink3AddrInstruction(NewMI, RegB, mi);
 619
 620   MBB->erase(mi); // Nuke the old inst.
 621
 622   if (!Sunk) {
 623     DistanceMap.insert(std::make_pair(NewMI, Dist));
 624     mi = NewMI;
 625     nmi = llvm::next(mi);
 626   }
 627
 628   // Update source and destination register maps.
 629   SrcRegMap.erase(RegA);
 630   DstRegMap.erase(RegB);
 631   return true;
 632 }
 633
 634 /// scanUses - Scan forward recursively for only uses, update maps if the use
 635 /// is a copy or a two-address instruction.
 636 void
 637 TwoAddressInstructionPass::scanUses(unsigned DstReg) {
 638   SmallVector<unsigned, 4> VirtRegPairs;
 639   bool IsDstPhys;
 640   bool IsCopy = false;
 641   unsigned NewReg = 0;
 642   unsigned Reg = DstReg;
 643   while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy,
 644                                                       NewReg, IsDstPhys)) {
 645     if (IsCopy && !Processed.insert(UseMI))
 646       break;
 647
 648     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
 649     if (DI != DistanceMap.end())
 650       // Earlier in the same MBB.Reached via a back edge.
 651       break;
 652
 653     if (IsDstPhys) {
 654       VirtRegPairs.push_back(NewReg);
 655       break;
 656     }
 657     bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second;
 658     if (!isNew)
 659       assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!");
 660     VirtRegPairs.push_back(NewReg);
 661     Reg = NewReg;
 662   }
 663
 664   if (!VirtRegPairs.empty()) {
 665     unsigned ToReg = VirtRegPairs.back();
 666     VirtRegPairs.pop_back();
 667     while (!VirtRegPairs.empty()) {
 668       unsigned FromReg = VirtRegPairs.back();
 669       VirtRegPairs.pop_back();
 670       bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
 671       if (!isNew)
 672         assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
 673       ToReg = FromReg;
 674     }
 675     bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second;
 676     if (!isNew)
 677       assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
 678   }
 679 }
 680
 681 /// processCopy - If the specified instruction is not yet processed, process it
 682 /// if it's a copy. For a copy instruction, we find the physical registers the
 683 /// source and destination registers might be mapped to. These are kept in
 684 /// point-to maps used to determine future optimizations. e.g.
 685 /// v1024 = mov r0
 686 /// v1025 = mov r1
 687 /// v1026 = add v1024, v1025
 688 /// r1    = mov r1026
 689 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially
 690 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
 691 /// potentially joined with r1 on the output side. It's worthwhile to commute
 692 /// 'add' to eliminate a copy.
 693 void TwoAddressInstructionPass::processCopy(MachineInstr *MI) {
 694   if (Processed.count(MI))
 695     return;
 696
 697   bool IsSrcPhys, IsDstPhys;
 698   unsigned SrcReg, DstReg;
 699   if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
 700     return;
 701
 702   if (IsDstPhys && !IsSrcPhys)
 703     DstRegMap.insert(std::make_pair(SrcReg, DstReg));
 704   else if (!IsDstPhys && IsSrcPhys) {
 705     bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
 706     if (!isNew)
 707       assert(SrcRegMap[DstReg] == SrcReg &&
 708              "Can't map to two src physical registers!");
 709
 710     scanUses(DstReg);
 711   }
 712
 713   Processed.insert(MI);
 714   return;
 715 }
 716
 717 /// rescheduleMIBelowKill - If there is one more local instruction that reads
 718 /// 'Reg' and it kills 'Reg, consider moving the instruction below the kill
 719 /// instruction in order to eliminate the need for the copy.
 720 bool TwoAddressInstructionPass::
 721 rescheduleMIBelowKill(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   for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(Reg),
 857          DE = MRI->def_end(); DI != DE; ++DI) {
 858     MachineInstr *DefMI = &*DI;
 859     if (DefMI->getParent() != MBB || DefMI->isCopy() || DefMI->isCopyLike())
 860       continue;
 861     if (DefMI == MI)
 862       return true; // MI is defining something KillMI uses
 863     DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(DefMI);
 864     if (DDI == DistanceMap.end())
 865       return true;  // Below MI
 866     unsigned DefDist = DDI->second;
 867     assert(Dist > DefDist && "Visited def already?");
 868     if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
 869       return true;
 870   }
 871   return false;
 872 }
 873
 874 /// rescheduleKillAboveMI - If there is one more local instruction that reads
 875 /// 'Reg' and it kills 'Reg, consider moving the kill instruction above the
 876 /// current two-address instruction in order to eliminate the need for the
 877 /// copy.
 878 bool TwoAddressInstructionPass::
 879 rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
 880                       MachineBasicBlock::iterator &nmi,
 881                       unsigned Reg) {
 882   // Bail immediately if we don't have LV available. We use it to find kills
 883   // efficiently.
 884   if (!LV)
 885     return false;
 886
 887   MachineInstr *MI = &*mi;
 888   DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
 889   if (DI == DistanceMap.end())
 890     // Must be created from unfolded load. Don't waste time trying this.
 891     return false;
 892
 893   MachineInstr *KillMI = LV->getVarInfo(Reg).findKill(MBB);
 894   if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
 895     // Don't mess with copies, they may be coalesced later.
 896     return false;
 897
 898   unsigned DstReg;
 899   if (isTwoAddrUse(*KillMI, Reg, DstReg))
 900     return false;
 901
 902   bool SeenStore = true;
 903   if (!KillMI->isSafeToMove(TII, AA, SeenStore))
 904     return false;
 905
 906   SmallSet<unsigned, 2> Uses;
 907   SmallSet<unsigned, 2> Kills;
 908   SmallSet<unsigned, 2> Defs;
 909   SmallSet<unsigned, 2> LiveDefs;
 910   for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) {
 911     const MachineOperand &MO = KillMI->getOperand(i);
 912     if (!MO.isReg())
 913       continue;
 914     unsigned MOReg = MO.getReg();
 915     if (MO.isUse()) {
 916       if (!MOReg)
 917         continue;
 918       if (isDefTooClose(MOReg, DI->second, MI))
 919         return false;
 920       if (MOReg == Reg && !MO.isKill())
 921         return false;
 922       Uses.insert(MOReg);
 923       if (MO.isKill() && MOReg != Reg)
 924         Kills.insert(MOReg);
 925     } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
 926       Defs.insert(MOReg);
 927       if (!MO.isDead())
 928         LiveDefs.insert(MOReg);
 929     }
 930   }
 931
 932   // Check if the reschedule will not break depedencies.
 933   unsigned NumVisited = 0;
 934   MachineBasicBlock::iterator KillPos = KillMI;
 935   for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) {
 936     MachineInstr *OtherMI = I;
 937     // DBG_VALUE cannot be counted against the limit.
 938     if (OtherMI->isDebugValue())
 939       continue;
 940     if (NumVisited > 10)  // FIXME: Arbitrary limit to reduce compile time cost.
 941       return false;
 942     ++NumVisited;
 943     if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() ||
 944         OtherMI->isBranch() || OtherMI->isTerminator())
 945       // Don't move pass calls, etc.
 946       return false;
 947     SmallVector<unsigned, 2> OtherDefs;
 948     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 949       const MachineOperand &MO = OtherMI->getOperand(i);
 950       if (!MO.isReg())
 951         continue;
 952       unsigned MOReg = MO.getReg();
 953       if (!MOReg)
 954         continue;
 955       if (MO.isUse()) {
 956         if (Defs.count(MOReg))
 957           // Moving KillMI can clobber the physical register if the def has
 958           // not been seen.
 959           return false;
 960         if (Kills.count(MOReg))
 961           // Don't want to extend other live ranges and update kills.
 962           return false;
 963         if (OtherMI != MI && MOReg == Reg && !MO.isKill())
 964           // We can't schedule across a use of the register in question.
 965           return false;
 966       } else {
 967         OtherDefs.push_back(MOReg);
 968       }
 969     }
 970
 971     for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) {
 972       unsigned MOReg = OtherDefs[i];
 973       if (Uses.count(MOReg))
 974         return false;
 975       if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
 976           LiveDefs.count(MOReg))
 977         return false;
 978       // Physical register def is seen.
 979       Defs.erase(MOReg);
 980     }
 981   }
 982
 983   // Move the old kill above MI, don't forget to move debug info as well.
 984   MachineBasicBlock::iterator InsertPos = mi;
 985   while (InsertPos != MBB->begin() && llvm::prior(InsertPos)->isDebugValue())
 986     --InsertPos;
 987   MachineBasicBlock::iterator From = KillMI;
 988   MachineBasicBlock::iterator To = llvm::next(From);
 989   while (llvm::prior(From)->isDebugValue())
 990     --From;
 991   MBB->splice(InsertPos, MBB, From, To);
 992
 993   nmi = llvm::prior(InsertPos); // Backtrack so we process the moved instr.
 994   DistanceMap.erase(DI);
 995
 996   // Update live variables
 997   LV->removeVirtualRegisterKilled(Reg, KillMI);
 998   LV->addVirtualRegisterKilled(Reg, MI);
 999   if (LIS)
1000     LIS->handleMove(KillMI);
1001
1002   DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1003   return true;
1004 }
1005
1006 /// tryInstructionTransform - For the case where an instruction has a single
1007 /// pair of tied register operands, attempt some transformations that may
1008 /// either eliminate the tied operands or improve the opportunities for
1009 /// coalescing away the register copy.  Returns true if no copy needs to be
1010 /// inserted to untie mi's operands (either because they were untied, or
1011 /// because mi was rescheduled, and will be visited again later).
1012 bool TwoAddressInstructionPass::
1013 tryInstructionTransform(MachineBasicBlock::iterator &mi,
1014                         MachineBasicBlock::iterator &nmi,
1015                         unsigned SrcIdx, unsigned DstIdx, unsigned Dist) {
1016   if (OptLevel == CodeGenOpt::None)
1017     return false;
1018
1019   MachineInstr &MI = *mi;
1020   unsigned regA = MI.getOperand(DstIdx).getReg();
1021   unsigned regB = MI.getOperand(SrcIdx).getReg();
1022
1023   assert(TargetRegisterInfo::isVirtualRegister(regB) &&
1024          "cannot make instruction into two-address form");
1025   bool regBKilled = isKilled(MI, regB, MRI, TII, LIS);
1026
1027   if (TargetRegisterInfo::isVirtualRegister(regA))
1028     scanUses(regA);
1029
1030   // Check if it is profitable to commute the operands.
1031   unsigned SrcOp1, SrcOp2;
1032   unsigned regC = 0;
1033   unsigned regCIdx = ~0U;
1034   bool TryCommute = false;
1035   bool AggressiveCommute = false;
1036   if (MI.isCommutable() && MI.getNumOperands() >= 3 &&
1037       TII->findCommutedOpIndices(&MI, SrcOp1, SrcOp2)) {
1038     if (SrcIdx == SrcOp1)
1039       regCIdx = SrcOp2;
1040     else if (SrcIdx == SrcOp2)
1041       regCIdx = SrcOp1;
1042
1043     if (regCIdx != ~0U) {
1044       regC = MI.getOperand(regCIdx).getReg();
1045       if (!regBKilled && isKilled(MI, regC, MRI, TII, LIS))
1046         // If C dies but B does not, swap the B and C operands.
1047         // This makes the live ranges of A and C joinable.
1048         TryCommute = true;
1049       else if (isProfitableToCommute(regA, regB, regC, &MI, Dist)) {
1050         TryCommute = true;
1051         AggressiveCommute = true;
1052       }
1053     }
1054   }
1055
1056   // If it's profitable to commute, try to do so.
1057   if (TryCommute && commuteInstruction(mi, regB, regC, Dist)) {
1058     ++NumCommuted;
1059     if (AggressiveCommute)
1060       ++NumAggrCommuted;
1061     return false;
1062   }
1063
1064   // If there is one more use of regB later in the same MBB, consider
1065   // re-schedule this MI below it.
1066   if (rescheduleMIBelowKill(mi, nmi, regB)) {
1067     ++NumReSchedDowns;
1068     return true;
1069   }
1070
1071   if (MI.isConvertibleTo3Addr()) {
1072     // This instruction is potentially convertible to a true
1073     // three-address instruction.  Check if it is profitable.
1074     if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1075       // Try to convert it.
1076       if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
1077         ++NumConvertedTo3Addr;
1078         return true; // Done with this instruction.
1079       }
1080     }
1081   }
1082
1083   // If there is one more use of regB later in the same MBB, consider
1084   // re-schedule it before this MI if it's legal.
1085   if (rescheduleKillAboveMI(mi, nmi, regB)) {
1086     ++NumReSchedUps;
1087     return true;
1088   }
1089
1090   // If this is an instruction with a load folded into it, try unfolding
1091   // the load, e.g. avoid this:
1092   //   movq %rdx, %rcx
1093   //   addq (%rax), %rcx
1094   // in favor of this:
1095   //   movq (%rax), %rcx
1096   //   addq %rdx, %rcx
1097   // because it's preferable to schedule a load than a register copy.
1098   if (MI.mayLoad() && !regBKilled) {
1099     // Determine if a load can be unfolded.
1100     unsigned LoadRegIndex;
1101     unsigned NewOpc =
1102       TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
1103                                       /*UnfoldLoad=*/true,
1104                                       /*UnfoldStore=*/false,
1105                                       &LoadRegIndex);
1106     if (NewOpc != 0) {
1107       const MCInstrDesc &UnfoldMCID = TII->get(NewOpc);
1108       if (UnfoldMCID.getNumDefs() == 1) {
1109         // Unfold the load.
1110         DEBUG(dbgs() << "2addr:   UNFOLDING: " << MI);
1111         const TargetRegisterClass *RC =
1112           TRI->getAllocatableClass(
1113             TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF));
1114         unsigned Reg = MRI->createVirtualRegister(RC);
1115         SmallVector<MachineInstr *, 2> NewMIs;
1116         if (!TII->unfoldMemoryOperand(*MF, &MI, Reg,
1117                                       /*UnfoldLoad=*/true,/*UnfoldStore=*/false,
1118                                       NewMIs)) {
1119           DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1120           return false;
1121         }
1122         assert(NewMIs.size() == 2 &&
1123                "Unfolded a load into multiple instructions!");
1124         // The load was previously folded, so this is the only use.
1125         NewMIs[1]->addRegisterKilled(Reg, TRI);
1126
1127         // Tentatively insert the instructions into the block so that they
1128         // look "normal" to the transformation logic.
1129         MBB->insert(mi, NewMIs[0]);
1130         MBB->insert(mi, NewMIs[1]);
1131
1132         DEBUG(dbgs() << "2addr:    NEW LOAD: " << *NewMIs[0]
1133                      << "2addr:    NEW INST: " << *NewMIs[1]);
1134
1135         // Transform the instruction, now that it no longer has a load.
1136         unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA);
1137         unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB);
1138         MachineBasicBlock::iterator NewMI = NewMIs[1];
1139         bool TransformSuccess =
1140           tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist);
1141         if (TransformSuccess ||
1142             NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1143           // Success, or at least we made an improvement. Keep the unfolded
1144           // instructions and discard the original.
1145           if (LV) {
1146             for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1147               MachineOperand &MO = MI.getOperand(i);
1148               if (MO.isReg() &&
1149                   TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
1150                 if (MO.isUse()) {
1151                   if (MO.isKill()) {
1152                     if (NewMIs[0]->killsRegister(MO.getReg()))
1153                       LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]);
1154                     else {
1155                       assert(NewMIs[1]->killsRegister(MO.getReg()) &&
1156                              "Kill missing after load unfold!");
1157                       LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]);
1158                     }
1159                   }
1160                 } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) {
1161                   if (NewMIs[1]->registerDefIsDead(MO.getReg()))
1162                     LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]);
1163                   else {
1164                     assert(NewMIs[0]->registerDefIsDead(MO.getReg()) &&
1165                            "Dead flag missing after load unfold!");
1166                     LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]);
1167                   }
1168                 }
1169               }
1170             }
1171             LV->addVirtualRegisterKilled(Reg, NewMIs[1]);
1172           }
1173
1174           SmallVector<unsigned, 4> OrigRegs;
1175           if (LIS) {
1176             for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
1177                  MOE = MI.operands_end(); MOI != MOE; ++MOI) {
1178               if (MOI->isReg())
1179                 OrigRegs.push_back(MOI->getReg());
1180             }
1181           }
1182
1183           MI.eraseFromParent();
1184
1185           // Update LiveIntervals.
1186           if (LIS) {
1187             MachineBasicBlock::iterator Begin(NewMIs[0]);
1188             MachineBasicBlock::iterator End(NewMIs[1]);
1189             LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1190           }
1191
1192           mi = NewMIs[1];
1193           if (TransformSuccess)
1194             return true;
1195         } else {
1196           // Transforming didn't eliminate the tie and didn't lead to an
1197           // improvement. Clean up the unfolded instructions and keep the
1198           // original.
1199           DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1200           NewMIs[0]->eraseFromParent();
1201           NewMIs[1]->eraseFromParent();
1202         }
1203       }
1204     }
1205   }
1206
1207   return false;
1208 }
1209
1210 // Collect tied operands of MI that need to be handled.
1211 // Rewrite trivial cases immediately.
1212 // Return true if any tied operands where found, including the trivial ones.
1213 bool TwoAddressInstructionPass::
1214 collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
1215   const MCInstrDesc &MCID = MI->getDesc();
1216   bool AnyOps = false;
1217   unsigned NumOps = MI->getNumOperands();
1218
1219   for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1220     unsigned DstIdx = 0;
1221     if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1222       continue;
1223     AnyOps = true;
1224     MachineOperand &SrcMO = MI->getOperand(SrcIdx);
1225     MachineOperand &DstMO = MI->getOperand(DstIdx);
1226     unsigned SrcReg = SrcMO.getReg();
1227     unsigned DstReg = DstMO.getReg();
1228     // Tied constraint already satisfied?
1229     if (SrcReg == DstReg)
1230       continue;
1231
1232     assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1233
1234     // Deal with <undef> uses immediately - simply rewrite the src operand.
1235     if (SrcMO.isUndef()) {
1236       // Constrain the DstReg register class if required.
1237       if (TargetRegisterInfo::isVirtualRegister(DstReg))
1238         if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
1239                                                              TRI, *MF))
1240           MRI->constrainRegClass(DstReg, RC);
1241       SrcMO.setReg(DstReg);
1242       DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1243       continue;
1244     }
1245     TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1246   }
1247   return AnyOps;
1248 }
1249
1250 // Process a list of tied MI operands that all use the same source register.
1251 // The tied pairs are of the form (SrcIdx, DstIdx).
1252 void
1253 TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
1254                                             TiedPairList &TiedPairs,
1255                                             unsigned &Dist) {
1256   bool IsEarlyClobber = false;
1257   for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1258     const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second);
1259     IsEarlyClobber |= DstMO.isEarlyClobber();
1260   }
1261
1262   bool RemovedKillFlag = false;
1263   bool AllUsesCopied = true;
1264   unsigned LastCopiedReg = 0;
1265   SlotIndex LastCopyIdx;
1266   unsigned RegB = 0;
1267   for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1268     unsigned SrcIdx = TiedPairs[tpi].first;
1269     unsigned DstIdx = TiedPairs[tpi].second;
1270
1271     const MachineOperand &DstMO = MI->getOperand(DstIdx);
1272     unsigned RegA = DstMO.getReg();
1273
1274     // Grab RegB from the instruction because it may have changed if the
1275     // instruction was commuted.
1276     RegB = MI->getOperand(SrcIdx).getReg();
1277
1278     if (RegA == RegB) {
1279       // The register is tied to multiple destinations (or else we would
1280       // not have continued this far), but this use of the register
1281       // already matches the tied destination.  Leave it.
1282       AllUsesCopied = false;
1283       continue;
1284     }
1285     LastCopiedReg = RegA;
1286
1287     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
1288            "cannot make instruction into two-address form");
1289
1290 #ifndef NDEBUG
1291     // First, verify that we don't have a use of "a" in the instruction
1292     // (a = b + a for example) because our transformation will not
1293     // work. This should never occur because we are in SSA form.
1294     for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1295       assert(i == DstIdx ||
1296              !MI->getOperand(i).isReg() ||
1297              MI->getOperand(i).getReg() != RegA);
1298 #endif
1299
1300     // Emit a copy.
1301     BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1302             TII->get(TargetOpcode::COPY), RegA).addReg(RegB);
1303
1304     // Update DistanceMap.
1305     MachineBasicBlock::iterator PrevMI = MI;
1306     --PrevMI;
1307     DistanceMap.insert(std::make_pair(PrevMI, Dist));
1308     DistanceMap[MI] = ++Dist;
1309
1310     if (LIS) {
1311       LastCopyIdx = LIS->InsertMachineInstrInMaps(PrevMI).getRegSlot();
1312
1313       if (TargetRegisterInfo::isVirtualRegister(RegA)) {
1314         LiveInterval &LI = LIS->getInterval(RegA);
1315         VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1316         SlotIndex endIdx =
1317           LIS->getInstructionIndex(MI).getRegSlot(IsEarlyClobber);
1318         LI.addRange(LiveRange(LastCopyIdx, endIdx, VNI));
1319       }
1320     }
1321
1322     DEBUG(dbgs() << "\t\tprepend:\t" << *PrevMI);
1323
1324     MachineOperand &MO = MI->getOperand(SrcIdx);
1325     assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1326            "inconsistent operand info for 2-reg pass");
1327     if (MO.isKill()) {
1328       MO.setIsKill(false);
1329       RemovedKillFlag = true;
1330     }
1331
1332     // Make sure regA is a legal regclass for the SrcIdx operand.
1333     if (TargetRegisterInfo::isVirtualRegister(RegA) &&
1334         TargetRegisterInfo::isVirtualRegister(RegB))
1335       MRI->constrainRegClass(RegA, MRI->getRegClass(RegB));
1336
1337     MO.setReg(RegA);
1338
1339     // Propagate SrcRegMap.
1340     SrcRegMap[RegA] = RegB;
1341   }
1342
1343
1344   if (AllUsesCopied) {
1345     if (!IsEarlyClobber) {
1346       // Replace other (un-tied) uses of regB with LastCopiedReg.
1347       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1348         MachineOperand &MO = MI->getOperand(i);
1349         if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1350           if (MO.isKill()) {
1351             MO.setIsKill(false);
1352             RemovedKillFlag = true;
1353           }
1354           MO.setReg(LastCopiedReg);
1355         }
1356       }
1357     }
1358
1359     // Update live variables for regB.
1360     if (RemovedKillFlag && LV && LV->getVarInfo(RegB).removeKill(MI)) {
1361       MachineBasicBlock::iterator PrevMI = MI;
1362       --PrevMI;
1363       LV->addVirtualRegisterKilled(RegB, PrevMI);
1364     }
1365
1366     // Update LiveIntervals.
1367     if (LIS) {
1368       LiveInterval &LI = LIS->getInterval(RegB);
1369       SlotIndex MIIdx = LIS->getInstructionIndex(MI);
1370       LiveInterval::const_iterator I = LI.find(MIIdx);
1371       assert(I != LI.end() && "RegB must be live-in to use.");
1372
1373       SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber);
1374       if (I->end == UseIdx)
1375         LI.removeRange(LastCopyIdx, UseIdx);
1376     }
1377
1378   } else if (RemovedKillFlag) {
1379     // Some tied uses of regB matched their destination registers, so
1380     // regB is still used in this instruction, but a kill flag was
1381     // removed from a different tied use of regB, so now we need to add
1382     // a kill flag to one of the remaining uses of regB.
1383     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1384       MachineOperand &MO = MI->getOperand(i);
1385       if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1386         MO.setIsKill(true);
1387         break;
1388       }
1389     }
1390   }
1391 }
1392
1393 /// runOnMachineFunction - Reduce two-address instructions to two operands.
1394 ///
1395 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
1396   MF = &Func;
1397   const TargetMachine &TM = MF->getTarget();
1398   MRI = &MF->getRegInfo();
1399   TII = TM.getInstrInfo();
1400   TRI = TM.getRegisterInfo();
1401   InstrItins = TM.getInstrItineraryData();
1402   LV = getAnalysisIfAvailable<LiveVariables>();
1403   LIS = getAnalysisIfAvailable<LiveIntervals>();
1404   AA = &getAnalysis<AliasAnalysis>();
1405   OptLevel = TM.getOptLevel();
1406
1407   bool MadeChange = false;
1408
1409   DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1410   DEBUG(dbgs() << "********** Function: "
1411         << MF->getName() << '\n');
1412
1413   // This pass takes the function out of SSA form.
1414   MRI->leaveSSA();
1415
1416   TiedOperandMap TiedOperands;
1417   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
1418        MBBI != MBBE; ++MBBI) {
1419     MBB = MBBI;
1420     unsigned Dist = 0;
1421     DistanceMap.clear();
1422     SrcRegMap.clear();
1423     DstRegMap.clear();
1424     Processed.clear();
1425     for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1426          mi != me; ) {
1427       MachineBasicBlock::iterator nmi = llvm::next(mi);
1428       if (mi->isDebugValue()) {
1429         mi = nmi;
1430         continue;
1431       }
1432
1433       // Expand REG_SEQUENCE instructions. This will position mi at the first
1434       // expanded instruction.
1435       if (mi->isRegSequence())
1436         eliminateRegSequence(mi);
1437
1438       DistanceMap.insert(std::make_pair(mi, ++Dist));
1439
1440       processCopy(&*mi);
1441
1442       // First scan through all the tied register uses in this instruction
1443       // and record a list of pairs of tied operands for each register.
1444       if (!collectTiedOperands(mi, TiedOperands)) {
1445         mi = nmi;
1446         continue;
1447       }
1448
1449       ++NumTwoAddressInstrs;
1450       MadeChange = true;
1451       DEBUG(dbgs() << '\t' << *mi);
1452
1453       // If the instruction has a single pair of tied operands, try some
1454       // transformations that may either eliminate the tied operands or
1455       // improve the opportunities for coalescing away the register copy.
1456       if (TiedOperands.size() == 1) {
1457         SmallVector<std::pair<unsigned, unsigned>, 4> &TiedPairs
1458           = TiedOperands.begin()->second;
1459         if (TiedPairs.size() == 1) {
1460           unsigned SrcIdx = TiedPairs[0].first;
1461           unsigned DstIdx = TiedPairs[0].second;
1462           unsigned SrcReg = mi->getOperand(SrcIdx).getReg();
1463           unsigned DstReg = mi->getOperand(DstIdx).getReg();
1464           if (SrcReg != DstReg &&
1465               tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist)) {
1466             // The tied operands have been eliminated or shifted further down the
1467             // block to ease elimination. Continue processing with 'nmi'.
1468             TiedOperands.clear();
1469             mi = nmi;
1470             continue;
1471           }
1472         }
1473       }
1474
1475       // Now iterate over the information collected above.
1476       for (TiedOperandMap::iterator OI = TiedOperands.begin(),
1477              OE = TiedOperands.end(); OI != OE; ++OI) {
1478         processTiedPairs(mi, OI->second, Dist);
1479         DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1480       }
1481
1482       // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1483       if (mi->isInsertSubreg()) {
1484         // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1485         // To   %reg:subidx = COPY %subreg
1486         unsigned SubIdx = mi->getOperand(3).getImm();
1487         mi->RemoveOperand(3);
1488         assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1489         mi->getOperand(0).setSubReg(SubIdx);
1490         mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1491         mi->RemoveOperand(1);
1492         mi->setDesc(TII->get(TargetOpcode::COPY));
1493         DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1494       }
1495
1496       // Clear TiedOperands here instead of at the top of the loop
1497       // since most instructions do not have tied operands.
1498       TiedOperands.clear();
1499       mi = nmi;
1500     }
1501   }
1502
1503   if (LIS)
1504     MF->verify(this, "After two-address instruction pass");
1505
1506   return MadeChange;
1507 }
1508
1509 /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1510 ///
1511 /// The instruction is turned into a sequence of sub-register copies:
1512 ///
1513 ///   %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1514 ///
1515 /// Becomes:
1516 ///
1517 ///   %dst:ssub0<def,undef> = COPY %v1
1518 ///   %dst:ssub1<def> = COPY %v2
1519 ///
1520 void TwoAddressInstructionPass::
1521 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1522   MachineInstr *MI = MBBI;
1523   unsigned DstReg = MI->getOperand(0).getReg();
1524   if (MI->getOperand(0).getSubReg() ||
1525       TargetRegisterInfo::isPhysicalRegister(DstReg) ||
1526       !(MI->getNumOperands() & 1)) {
1527     DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
1528     llvm_unreachable(0);
1529   }
1530
1531   SmallVector<unsigned, 4> OrigRegs;
1532   if (LIS) {
1533     OrigRegs.push_back(MI->getOperand(0).getReg());
1534     for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2)
1535       OrigRegs.push_back(MI->getOperand(i).getReg());
1536   }
1537
1538   bool DefEmitted = false;
1539   for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
1540     MachineOperand &UseMO = MI->getOperand(i);
1541     unsigned SrcReg = UseMO.getReg();
1542     unsigned SubIdx = MI->getOperand(i+1).getImm();
1543     // Nothing needs to be inserted for <undef> operands.
1544     if (UseMO.isUndef())
1545       continue;
1546
1547     // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1548     // might insert a COPY that uses SrcReg after is was killed.
1549     bool isKill = UseMO.isKill();
1550     if (isKill)
1551       for (unsigned j = i + 2; j < e; j += 2)
1552         if (MI->getOperand(j).getReg() == SrcReg) {
1553           MI->getOperand(j).setIsKill();
1554           UseMO.setIsKill(false);
1555           isKill = false;
1556           break;
1557         }
1558
1559     // Insert the sub-register copy.
1560     MachineInstr *CopyMI = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1561                                    TII->get(TargetOpcode::COPY))
1562       .addReg(DstReg, RegState::Define, SubIdx)
1563       .addOperand(UseMO);
1564
1565     // The first def needs an <undef> flag because there is no live register
1566     // before it.
1567     if (!DefEmitted) {
1568       CopyMI->getOperand(0).setIsUndef(true);
1569       // Return an iterator pointing to the first inserted instr.
1570       MBBI = CopyMI;
1571     }
1572     DefEmitted = true;
1573
1574     // Update LiveVariables' kill info.
1575     if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg))
1576       LV->replaceKillInstruction(SrcReg, MI, CopyMI);
1577
1578     DEBUG(dbgs() << "Inserted: " << *CopyMI);
1579   }
1580
1581   MachineBasicBlock::iterator EndMBBI =
1582       llvm::next(MachineBasicBlock::iterator(MI));
1583
1584   if (!DefEmitted) {
1585     DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");
1586     MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1587     for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
1588       MI->RemoveOperand(j);
1589   } else {
1590     DEBUG(dbgs() << "Eliminated: " << *MI);
1591     MI->eraseFromParent();
1592   }
1593
1594   // Udpate LiveIntervals.
1595   if (LIS)
1596     LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
1597 }