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