TwoAddressInstructionPass.cpp revision 68fc2daf8fa446be04d2ed2b3cbb1b00c382458f
1//===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the TwoAddress instruction pass which is used
11// by most register allocators. Two-Address instructions are rewritten
12// from:
13//
14//     A = B op C
15//
16// to:
17//
18//     A = B
19//     A op= C
20//
21// Note that if a register allocator chooses to use this pass, that it
22// has to be capable of handling the non-SSA nature of these rewritten
23// virtual registers.
24//
25// It is also worth noting that the duplicate operand of the two
26// address instruction is removed.
27//
28//===----------------------------------------------------------------------===//
29
30#define DEBUG_TYPE "twoaddrinstr"
31#include "llvm/CodeGen/Passes.h"
32#include "llvm/Function.h"
33#include "llvm/CodeGen/LiveVariables.h"
34#include "llvm/CodeGen/MachineFunctionPass.h"
35#include "llvm/CodeGen/MachineInstr.h"
36#include "llvm/CodeGen/MachineRegisterInfo.h"
37#include "llvm/Analysis/AliasAnalysis.h"
38#include "llvm/Target/TargetRegisterInfo.h"
39#include "llvm/Target/TargetInstrInfo.h"
40#include "llvm/Target/TargetMachine.h"
41#include "llvm/Target/TargetOptions.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/ErrorHandling.h"
44#include "llvm/ADT/BitVector.h"
45#include "llvm/ADT/DenseMap.h"
46#include "llvm/ADT/SmallSet.h"
47#include "llvm/ADT/Statistic.h"
48#include "llvm/ADT/STLExtras.h"
49using namespace llvm;
50
51STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
52STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
53STATISTIC(NumAggrCommuted    , "Number of instructions aggressively commuted");
54STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
55STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
56STATISTIC(NumReMats,           "Number of instructions re-materialized");
57STATISTIC(NumDeletes,          "Number of dead instructions deleted");
58
59namespace {
60  class TwoAddressInstructionPass : public MachineFunctionPass {
61    const TargetInstrInfo *TII;
62    const TargetRegisterInfo *TRI;
63    MachineRegisterInfo *MRI;
64    LiveVariables *LV;
65    AliasAnalysis *AA;
66
67    // DistanceMap - Keep track the distance of a MI from the start of the
68    // current basic block.
69    DenseMap<MachineInstr*, unsigned> DistanceMap;
70
71    // SrcRegMap - A map from virtual registers to physical registers which
72    // are likely targets to be coalesced to due to copies from physical
73    // registers to virtual registers. e.g. v1024 = move r0.
74    DenseMap<unsigned, unsigned> SrcRegMap;
75
76    // DstRegMap - A map from virtual registers to physical registers which
77    // are likely targets to be coalesced to due to copies to physical
78    // registers from virtual registers. e.g. r1 = move v1024.
79    DenseMap<unsigned, unsigned> DstRegMap;
80
81    /// RegSequences - Keep track the list of REG_SEQUENCE instructions seen
82    /// during the initial walk of the machine function.
83    SmallVector<MachineInstr*, 16> RegSequences;
84
85    bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
86                              unsigned Reg,
87                              MachineBasicBlock::iterator OldPos);
88
89    bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
90                             MachineInstr *MI, MachineInstr *DefMI,
91                             MachineBasicBlock *MBB, unsigned Loc);
92
93    bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist,
94                           unsigned &LastDef);
95
96    MachineInstr *FindLastUseInMBB(unsigned Reg, MachineBasicBlock *MBB,
97                                   unsigned Dist);
98
99    bool isProfitableToCommute(unsigned regB, unsigned regC,
100                               MachineInstr *MI, MachineBasicBlock *MBB,
101                               unsigned Dist);
102
103    bool CommuteInstruction(MachineBasicBlock::iterator &mi,
104                            MachineFunction::iterator &mbbi,
105                            unsigned RegB, unsigned RegC, unsigned Dist);
106
107    bool isProfitableToConv3Addr(unsigned RegA);
108
109    bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
110                            MachineBasicBlock::iterator &nmi,
111                            MachineFunction::iterator &mbbi,
112                            unsigned RegB, unsigned Dist);
113
114    typedef std::pair<std::pair<unsigned, bool>, MachineInstr*> NewKill;
115    bool canUpdateDeletedKills(SmallVector<unsigned, 4> &Kills,
116                               SmallVector<NewKill, 4> &NewKills,
117                               MachineBasicBlock *MBB, unsigned Dist);
118    bool DeleteUnusedInstr(MachineBasicBlock::iterator &mi,
119                           MachineBasicBlock::iterator &nmi,
120                           MachineFunction::iterator &mbbi, unsigned Dist);
121
122    bool TryInstructionTransform(MachineBasicBlock::iterator &mi,
123                                 MachineBasicBlock::iterator &nmi,
124                                 MachineFunction::iterator &mbbi,
125                                 unsigned SrcIdx, unsigned DstIdx,
126                                 unsigned Dist);
127
128    void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB,
129                     SmallPtrSet<MachineInstr*, 8> &Processed);
130
131    void CoalesceExtSubRegs(SmallVector<unsigned,4> &Srcs, unsigned DstReg);
132
133    /// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part
134    /// of the de-ssa process. This replaces sources of REG_SEQUENCE as
135    /// sub-register references of the register defined by REG_SEQUENCE.
136    bool EliminateRegSequences();
137
138  public:
139    static char ID; // Pass identification, replacement for typeid
140    TwoAddressInstructionPass() : MachineFunctionPass(&ID) {}
141
142    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
143      AU.setPreservesCFG();
144      AU.addRequired<AliasAnalysis>();
145      AU.addPreserved<LiveVariables>();
146      AU.addPreservedID(MachineLoopInfoID);
147      AU.addPreservedID(MachineDominatorsID);
148      if (StrongPHIElim)
149        AU.addPreservedID(StrongPHIEliminationID);
150      else
151        AU.addPreservedID(PHIEliminationID);
152      MachineFunctionPass::getAnalysisUsage(AU);
153    }
154
155    /// runOnMachineFunction - Pass entry point.
156    bool runOnMachineFunction(MachineFunction&);
157  };
158}
159
160char TwoAddressInstructionPass::ID = 0;
161static RegisterPass<TwoAddressInstructionPass>
162X("twoaddressinstruction", "Two-Address instruction pass");
163
164const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
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.
170bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
171                                           MachineInstr *MI, unsigned SavedReg,
172                                           MachineBasicBlock::iterator OldPos) {
173  // Check if it's safe to move this instruction.
174  bool SeenStore = true; // Be conservative.
175  if (!MI->isSafeToMove(TII, AA, SeenStore))
176    return false;
177
178  unsigned DefReg = 0;
179  SmallSet<unsigned, 4> UseRegs;
180
181  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
182    const MachineOperand &MO = MI->getOperand(i);
183    if (!MO.isReg())
184      continue;
185    unsigned MOReg = MO.getReg();
186    if (!MOReg)
187      continue;
188    if (MO.isUse() && MOReg != SavedReg)
189      UseRegs.insert(MO.getReg());
190    if (!MO.isDef())
191      continue;
192    if (MO.isImplicit())
193      // Don't try to move it if it implicitly defines a register.
194      return false;
195    if (DefReg)
196      // For now, don't move any instructions that define multiple registers.
197      return false;
198    DefReg = MO.getReg();
199  }
200
201  // Find the instruction that kills SavedReg.
202  MachineInstr *KillMI = NULL;
203  for (MachineRegisterInfo::use_nodbg_iterator
204         UI = MRI->use_nodbg_begin(SavedReg),
205         UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
206    MachineOperand &UseMO = UI.getOperand();
207    if (!UseMO.isKill())
208      continue;
209    KillMI = UseMO.getParent();
210    break;
211  }
212
213  if (!KillMI || KillMI->getParent() != MBB || KillMI == MI)
214    return false;
215
216  // If any of the definitions are used by another instruction between the
217  // position and the kill use, then it's not safe to sink it.
218  //
219  // FIXME: This can be sped up if there is an easy way to query whether an
220  // instruction is before or after another instruction. Then we can use
221  // MachineRegisterInfo def / use instead.
222  MachineOperand *KillMO = NULL;
223  MachineBasicBlock::iterator KillPos = KillMI;
224  ++KillPos;
225
226  unsigned NumVisited = 0;
227  for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) {
228    MachineInstr *OtherMI = I;
229    // DBG_VALUE cannot be counted against the limit.
230    if (OtherMI->isDebugValue())
231      continue;
232    if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
233      return false;
234    ++NumVisited;
235    for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
236      MachineOperand &MO = OtherMI->getOperand(i);
237      if (!MO.isReg())
238        continue;
239      unsigned MOReg = MO.getReg();
240      if (!MOReg)
241        continue;
242      if (DefReg == MOReg)
243        return false;
244
245      if (MO.isKill()) {
246        if (OtherMI == KillMI && MOReg == SavedReg)
247          // Save the operand that kills the register. We want to unset the kill
248          // marker if we can sink MI past it.
249          KillMO = &MO;
250        else if (UseRegs.count(MOReg))
251          // One of the uses is killed before the destination.
252          return false;
253      }
254    }
255  }
256
257  // Update kill and LV information.
258  KillMO->setIsKill(false);
259  KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
260  KillMO->setIsKill(true);
261
262  if (LV)
263    LV->replaceKillInstruction(SavedReg, KillMI, MI);
264
265  // Move instruction to its destination.
266  MBB->remove(MI);
267  MBB->insert(KillPos, MI);
268
269  ++Num3AddrSunk;
270  return true;
271}
272
273/// isTwoAddrUse - Return true if the specified MI is using the specified
274/// register as a two-address operand.
275static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
276  const TargetInstrDesc &TID = UseMI->getDesc();
277  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
278    MachineOperand &MO = UseMI->getOperand(i);
279    if (MO.isReg() && MO.getReg() == Reg &&
280        (MO.isDef() || UseMI->isRegTiedToDefOperand(i)))
281      // Earlier use is a two-address one.
282      return true;
283  }
284  return false;
285}
286
287/// isProfitableToReMat - Return true if the heuristics determines it is likely
288/// to be profitable to re-materialize the definition of Reg rather than copy
289/// the register.
290bool
291TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
292                                         const TargetRegisterClass *RC,
293                                         MachineInstr *MI, MachineInstr *DefMI,
294                                         MachineBasicBlock *MBB, unsigned Loc) {
295  bool OtherUse = false;
296  for (MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(Reg),
297         UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
298    MachineOperand &UseMO = UI.getOperand();
299    MachineInstr *UseMI = UseMO.getParent();
300    MachineBasicBlock *UseMBB = UseMI->getParent();
301    if (UseMBB == MBB) {
302      DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
303      if (DI != DistanceMap.end() && DI->second == Loc)
304        continue;  // Current use.
305      OtherUse = true;
306      // There is at least one other use in the MBB that will clobber the
307      // register.
308      if (isTwoAddrUse(UseMI, Reg))
309        return true;
310    }
311  }
312
313  // If other uses in MBB are not two-address uses, then don't remat.
314  if (OtherUse)
315    return false;
316
317  // No other uses in the same block, remat if it's defined in the same
318  // block so it does not unnecessarily extend the live range.
319  return MBB == DefMI->getParent();
320}
321
322/// NoUseAfterLastDef - Return true if there are no intervening uses between the
323/// last instruction in the MBB that defines the specified register and the
324/// two-address instruction which is being processed. It also returns the last
325/// def location by reference
326bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg,
327                                           MachineBasicBlock *MBB, unsigned Dist,
328                                           unsigned &LastDef) {
329  LastDef = 0;
330  unsigned LastUse = Dist;
331  for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
332         E = MRI->reg_end(); I != E; ++I) {
333    MachineOperand &MO = I.getOperand();
334    MachineInstr *MI = MO.getParent();
335    if (MI->getParent() != MBB || MI->isDebugValue())
336      continue;
337    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
338    if (DI == DistanceMap.end())
339      continue;
340    if (MO.isUse() && DI->second < LastUse)
341      LastUse = DI->second;
342    if (MO.isDef() && DI->second > LastDef)
343      LastDef = DI->second;
344  }
345
346  return !(LastUse > LastDef && LastUse < Dist);
347}
348
349MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg,
350                                                         MachineBasicBlock *MBB,
351                                                         unsigned Dist) {
352  unsigned LastUseDist = 0;
353  MachineInstr *LastUse = 0;
354  for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
355         E = MRI->reg_end(); I != E; ++I) {
356    MachineOperand &MO = I.getOperand();
357    MachineInstr *MI = MO.getParent();
358    if (MI->getParent() != MBB || MI->isDebugValue())
359      continue;
360    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
361    if (DI == DistanceMap.end())
362      continue;
363    if (DI->second >= Dist)
364      continue;
365
366    if (MO.isUse() && DI->second > LastUseDist) {
367      LastUse = DI->first;
368      LastUseDist = DI->second;
369    }
370  }
371  return LastUse;
372}
373
374/// isCopyToReg - Return true if the specified MI is a copy instruction or
375/// a extract_subreg instruction. It also returns the source and destination
376/// registers and whether they are physical registers by reference.
377static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
378                        unsigned &SrcReg, unsigned &DstReg,
379                        bool &IsSrcPhys, bool &IsDstPhys) {
380  SrcReg = 0;
381  DstReg = 0;
382  unsigned SrcSubIdx, DstSubIdx;
383  if (!TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
384    if (MI.isExtractSubreg()) {
385      DstReg = MI.getOperand(0).getReg();
386      SrcReg = MI.getOperand(1).getReg();
387    } else if (MI.isInsertSubreg()) {
388      DstReg = MI.getOperand(0).getReg();
389      SrcReg = MI.getOperand(2).getReg();
390    } else if (MI.isSubregToReg()) {
391      DstReg = MI.getOperand(0).getReg();
392      SrcReg = MI.getOperand(2).getReg();
393    }
394  }
395
396  if (DstReg) {
397    IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
398    IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
399    return true;
400  }
401  return false;
402}
403
404/// isKilled - Test if the given register value, which is used by the given
405/// instruction, is killed by the given instruction. This looks through
406/// coalescable copies to see if the original value is potentially not killed.
407///
408/// For example, in this code:
409///
410///   %reg1034 = copy %reg1024
411///   %reg1035 = copy %reg1025<kill>
412///   %reg1036 = add %reg1034<kill>, %reg1035<kill>
413///
414/// %reg1034 is not considered to be killed, since it is copied from a
415/// register which is not killed. Treating it as not killed lets the
416/// normal heuristics commute the (two-address) add, which lets
417/// coalescing eliminate the extra copy.
418///
419static bool isKilled(MachineInstr &MI, unsigned Reg,
420                     const MachineRegisterInfo *MRI,
421                     const TargetInstrInfo *TII) {
422  MachineInstr *DefMI = &MI;
423  for (;;) {
424    if (!DefMI->killsRegister(Reg))
425      return false;
426    if (TargetRegisterInfo::isPhysicalRegister(Reg))
427      return true;
428    MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
429    // If there are multiple defs, we can't do a simple analysis, so just
430    // go with what the kill flag says.
431    if (llvm::next(Begin) != MRI->def_end())
432      return true;
433    DefMI = &*Begin;
434    bool IsSrcPhys, IsDstPhys;
435    unsigned SrcReg,  DstReg;
436    // If the def is something other than a copy, then it isn't going to
437    // be coalesced, so follow the kill flag.
438    if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
439      return true;
440    Reg = SrcReg;
441  }
442}
443
444/// isTwoAddrUse - Return true if the specified MI uses the specified register
445/// as a two-address use. If so, return the destination register by reference.
446static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
447  const TargetInstrDesc &TID = MI.getDesc();
448  unsigned NumOps = MI.isInlineAsm() ? MI.getNumOperands():TID.getNumOperands();
449  for (unsigned i = 0; i != NumOps; ++i) {
450    const MachineOperand &MO = MI.getOperand(i);
451    if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
452      continue;
453    unsigned ti;
454    if (MI.isRegTiedToDefOperand(i, &ti)) {
455      DstReg = MI.getOperand(ti).getReg();
456      return true;
457    }
458  }
459  return false;
460}
461
462/// findOnlyInterestingUse - Given a register, if has a single in-basic block
463/// use, return the use instruction if it's a copy or a two-address use.
464static
465MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
466                                     MachineRegisterInfo *MRI,
467                                     const TargetInstrInfo *TII,
468                                     bool &IsCopy,
469                                     unsigned &DstReg, bool &IsDstPhys) {
470  if (!MRI->hasOneNonDBGUse(Reg))
471    // None or more than one use.
472    return 0;
473  MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg);
474  if (UseMI.getParent() != MBB)
475    return 0;
476  unsigned SrcReg;
477  bool IsSrcPhys;
478  if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
479    IsCopy = true;
480    return &UseMI;
481  }
482  IsDstPhys = false;
483  if (isTwoAddrUse(UseMI, Reg, DstReg)) {
484    IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
485    return &UseMI;
486  }
487  return 0;
488}
489
490/// getMappedReg - Return the physical register the specified virtual register
491/// might be mapped to.
492static unsigned
493getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) {
494  while (TargetRegisterInfo::isVirtualRegister(Reg))  {
495    DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg);
496    if (SI == RegMap.end())
497      return 0;
498    Reg = SI->second;
499  }
500  if (TargetRegisterInfo::isPhysicalRegister(Reg))
501    return Reg;
502  return 0;
503}
504
505/// regsAreCompatible - Return true if the two registers are equal or aliased.
506///
507static bool
508regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
509  if (RegA == RegB)
510    return true;
511  if (!RegA || !RegB)
512    return false;
513  return TRI->regsOverlap(RegA, RegB);
514}
515
516
517/// isProfitableToReMat - Return true if it's potentially profitable to commute
518/// the two-address instruction that's being processed.
519bool
520TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC,
521                                       MachineInstr *MI, MachineBasicBlock *MBB,
522                                       unsigned Dist) {
523  // Determine if it's profitable to commute this two address instruction. In
524  // general, we want no uses between this instruction and the definition of
525  // the two-address register.
526  // e.g.
527  // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
528  // %reg1029<def> = MOV8rr %reg1028
529  // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
530  // insert => %reg1030<def> = MOV8rr %reg1028
531  // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
532  // In this case, it might not be possible to coalesce the second MOV8rr
533  // instruction if the first one is coalesced. So it would be profitable to
534  // commute it:
535  // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
536  // %reg1029<def> = MOV8rr %reg1028
537  // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
538  // insert => %reg1030<def> = MOV8rr %reg1029
539  // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
540
541  if (!MI->killsRegister(regC))
542    return false;
543
544  // Ok, we have something like:
545  // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
546  // let's see if it's worth commuting it.
547
548  // Look for situations like this:
549  // %reg1024<def> = MOV r1
550  // %reg1025<def> = MOV r0
551  // %reg1026<def> = ADD %reg1024, %reg1025
552  // r0            = MOV %reg1026
553  // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
554  unsigned FromRegB = getMappedReg(regB, SrcRegMap);
555  unsigned FromRegC = getMappedReg(regC, SrcRegMap);
556  unsigned ToRegB = getMappedReg(regB, DstRegMap);
557  unsigned ToRegC = getMappedReg(regC, DstRegMap);
558  if (!regsAreCompatible(FromRegB, ToRegB, TRI) &&
559      (regsAreCompatible(FromRegB, ToRegC, TRI) ||
560       regsAreCompatible(FromRegC, ToRegB, TRI)))
561    return true;
562
563  // If there is a use of regC between its last def (could be livein) and this
564  // instruction, then bail.
565  unsigned LastDefC = 0;
566  if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC))
567    return false;
568
569  // If there is a use of regB between its last def (could be livein) and this
570  // instruction, then go ahead and make this transformation.
571  unsigned LastDefB = 0;
572  if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB))
573    return true;
574
575  // Since there are no intervening uses for both registers, then commute
576  // if the def of regC is closer. Its live interval is shorter.
577  return LastDefB && LastDefC && LastDefC > LastDefB;
578}
579
580/// CommuteInstruction - Commute a two-address instruction and update the basic
581/// block, distance map, and live variables if needed. Return true if it is
582/// successful.
583bool
584TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi,
585                               MachineFunction::iterator &mbbi,
586                               unsigned RegB, unsigned RegC, unsigned Dist) {
587  MachineInstr *MI = mi;
588  DEBUG(dbgs() << "2addr: COMMUTING  : " << *MI);
589  MachineInstr *NewMI = TII->commuteInstruction(MI);
590
591  if (NewMI == 0) {
592    DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
593    return false;
594  }
595
596  DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
597  // If the instruction changed to commute it, update livevar.
598  if (NewMI != MI) {
599    if (LV)
600      // Update live variables
601      LV->replaceKillInstruction(RegC, MI, NewMI);
602
603    mbbi->insert(mi, NewMI);           // Insert the new inst
604    mbbi->erase(mi);                   // Nuke the old inst.
605    mi = NewMI;
606    DistanceMap.insert(std::make_pair(NewMI, Dist));
607  }
608
609  // Update source register map.
610  unsigned FromRegC = getMappedReg(RegC, SrcRegMap);
611  if (FromRegC) {
612    unsigned RegA = MI->getOperand(0).getReg();
613    SrcRegMap[RegA] = FromRegC;
614  }
615
616  return true;
617}
618
619/// isProfitableToConv3Addr - Return true if it is profitable to convert the
620/// given 2-address instruction to a 3-address one.
621bool
622TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) {
623  // Look for situations like this:
624  // %reg1024<def> = MOV r1
625  // %reg1025<def> = MOV r0
626  // %reg1026<def> = ADD %reg1024, %reg1025
627  // r2            = MOV %reg1026
628  // Turn ADD into a 3-address instruction to avoid a copy.
629  unsigned FromRegA = getMappedReg(RegA, SrcRegMap);
630  unsigned ToRegA = getMappedReg(RegA, DstRegMap);
631  return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI));
632}
633
634/// ConvertInstTo3Addr - Convert the specified two-address instruction into a
635/// three address one. Return true if this transformation was successful.
636bool
637TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
638                                              MachineBasicBlock::iterator &nmi,
639                                              MachineFunction::iterator &mbbi,
640                                              unsigned RegB, unsigned Dist) {
641  MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
642  if (NewMI) {
643    DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
644    DEBUG(dbgs() << "2addr:         TO 3-ADDR: " << *NewMI);
645    bool Sunk = false;
646
647    if (NewMI->findRegisterUseOperand(RegB, false, TRI))
648      // FIXME: Temporary workaround. If the new instruction doesn't
649      // uses RegB, convertToThreeAddress must have created more
650      // then one instruction.
651      Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi);
652
653    mbbi->erase(mi); // Nuke the old inst.
654
655    if (!Sunk) {
656      DistanceMap.insert(std::make_pair(NewMI, Dist));
657      mi = NewMI;
658      nmi = llvm::next(mi);
659    }
660    return true;
661  }
662
663  return false;
664}
665
666/// ProcessCopy - If the specified instruction is not yet processed, process it
667/// if it's a copy. For a copy instruction, we find the physical registers the
668/// source and destination registers might be mapped to. These are kept in
669/// point-to maps used to determine future optimizations. e.g.
670/// v1024 = mov r0
671/// v1025 = mov r1
672/// v1026 = add v1024, v1025
673/// r1    = mov r1026
674/// If 'add' is a two-address instruction, v1024, v1026 are both potentially
675/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
676/// potentially joined with r1 on the output side. It's worthwhile to commute
677/// 'add' to eliminate a copy.
678void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI,
679                                     MachineBasicBlock *MBB,
680                                     SmallPtrSet<MachineInstr*, 8> &Processed) {
681  if (Processed.count(MI))
682    return;
683
684  bool IsSrcPhys, IsDstPhys;
685  unsigned SrcReg, DstReg;
686  if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
687    return;
688
689  if (IsDstPhys && !IsSrcPhys)
690    DstRegMap.insert(std::make_pair(SrcReg, DstReg));
691  else if (!IsDstPhys && IsSrcPhys) {
692    bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
693    if (!isNew)
694      assert(SrcRegMap[DstReg] == SrcReg &&
695             "Can't map to two src physical registers!");
696
697    SmallVector<unsigned, 4> VirtRegPairs;
698    bool IsCopy = false;
699    unsigned NewReg = 0;
700    while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII,
701                                                   IsCopy, NewReg, IsDstPhys)) {
702      if (IsCopy) {
703        if (!Processed.insert(UseMI))
704          break;
705      }
706
707      DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
708      if (DI != DistanceMap.end())
709        // Earlier in the same MBB.Reached via a back edge.
710        break;
711
712      if (IsDstPhys) {
713        VirtRegPairs.push_back(NewReg);
714        break;
715      }
716      bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second;
717      if (!isNew)
718        assert(SrcRegMap[NewReg] == DstReg &&
719               "Can't map to two src physical registers!");
720      VirtRegPairs.push_back(NewReg);
721      DstReg = NewReg;
722    }
723
724    if (!VirtRegPairs.empty()) {
725      unsigned ToReg = VirtRegPairs.back();
726      VirtRegPairs.pop_back();
727      while (!VirtRegPairs.empty()) {
728        unsigned FromReg = VirtRegPairs.back();
729        VirtRegPairs.pop_back();
730        bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
731        if (!isNew)
732          assert(DstRegMap[FromReg] == ToReg &&
733                 "Can't map to two dst physical registers!");
734        ToReg = FromReg;
735      }
736    }
737  }
738
739  Processed.insert(MI);
740}
741
742/// isSafeToDelete - If the specified instruction does not produce any side
743/// effects and all of its defs are dead, then it's safe to delete.
744static bool isSafeToDelete(MachineInstr *MI,
745                           const TargetInstrInfo *TII,
746                           SmallVector<unsigned, 4> &Kills) {
747  const TargetInstrDesc &TID = MI->getDesc();
748  if (TID.mayStore() || TID.isCall())
749    return false;
750  if (TID.isTerminator() || TID.hasUnmodeledSideEffects())
751    return false;
752
753  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
754    MachineOperand &MO = MI->getOperand(i);
755    if (!MO.isReg())
756      continue;
757    if (MO.isDef() && !MO.isDead())
758      return false;
759    if (MO.isUse() && MO.isKill())
760      Kills.push_back(MO.getReg());
761  }
762  return true;
763}
764
765/// canUpdateDeletedKills - Check if all the registers listed in Kills are
766/// killed by instructions in MBB preceding the current instruction at
767/// position Dist.  If so, return true and record information about the
768/// preceding kills in NewKills.
769bool TwoAddressInstructionPass::
770canUpdateDeletedKills(SmallVector<unsigned, 4> &Kills,
771                      SmallVector<NewKill, 4> &NewKills,
772                      MachineBasicBlock *MBB, unsigned Dist) {
773  while (!Kills.empty()) {
774    unsigned Kill = Kills.back();
775    Kills.pop_back();
776    if (TargetRegisterInfo::isPhysicalRegister(Kill))
777      return false;
778
779    MachineInstr *LastKill = FindLastUseInMBB(Kill, MBB, Dist);
780    if (!LastKill)
781      return false;
782
783    bool isModRef = LastKill->definesRegister(Kill);
784    NewKills.push_back(std::make_pair(std::make_pair(Kill, isModRef),
785                                      LastKill));
786  }
787  return true;
788}
789
790/// DeleteUnusedInstr - If an instruction with a tied register operand can
791/// be safely deleted, just delete it.
792bool
793TwoAddressInstructionPass::DeleteUnusedInstr(MachineBasicBlock::iterator &mi,
794                                             MachineBasicBlock::iterator &nmi,
795                                             MachineFunction::iterator &mbbi,
796                                             unsigned Dist) {
797  // Check if the instruction has no side effects and if all its defs are dead.
798  SmallVector<unsigned, 4> Kills;
799  if (!isSafeToDelete(mi, TII, Kills))
800    return false;
801
802  // If this instruction kills some virtual registers, we need to
803  // update the kill information. If it's not possible to do so,
804  // then bail out.
805  SmallVector<NewKill, 4> NewKills;
806  if (!canUpdateDeletedKills(Kills, NewKills, &*mbbi, Dist))
807    return false;
808
809  if (LV) {
810    while (!NewKills.empty()) {
811      MachineInstr *NewKill = NewKills.back().second;
812      unsigned Kill = NewKills.back().first.first;
813      bool isDead = NewKills.back().first.second;
814      NewKills.pop_back();
815      if (LV->removeVirtualRegisterKilled(Kill, mi)) {
816        if (isDead)
817          LV->addVirtualRegisterDead(Kill, NewKill);
818        else
819          LV->addVirtualRegisterKilled(Kill, NewKill);
820      }
821    }
822  }
823
824  mbbi->erase(mi); // Nuke the old inst.
825  mi = nmi;
826  return true;
827}
828
829/// TryInstructionTransform - For the case where an instruction has a single
830/// pair of tied register operands, attempt some transformations that may
831/// either eliminate the tied operands or improve the opportunities for
832/// coalescing away the register copy.  Returns true if the tied operands
833/// are eliminated altogether.
834bool TwoAddressInstructionPass::
835TryInstructionTransform(MachineBasicBlock::iterator &mi,
836                        MachineBasicBlock::iterator &nmi,
837                        MachineFunction::iterator &mbbi,
838                        unsigned SrcIdx, unsigned DstIdx, unsigned Dist) {
839  const TargetInstrDesc &TID = mi->getDesc();
840  unsigned regA = mi->getOperand(DstIdx).getReg();
841  unsigned regB = mi->getOperand(SrcIdx).getReg();
842
843  assert(TargetRegisterInfo::isVirtualRegister(regB) &&
844         "cannot make instruction into two-address form");
845
846  // If regA is dead and the instruction can be deleted, just delete
847  // it so it doesn't clobber regB.
848  bool regBKilled = isKilled(*mi, regB, MRI, TII);
849  if (!regBKilled && mi->getOperand(DstIdx).isDead() &&
850      DeleteUnusedInstr(mi, nmi, mbbi, Dist)) {
851    ++NumDeletes;
852    return true; // Done with this instruction.
853  }
854
855  // Check if it is profitable to commute the operands.
856  unsigned SrcOp1, SrcOp2;
857  unsigned regC = 0;
858  unsigned regCIdx = ~0U;
859  bool TryCommute = false;
860  bool AggressiveCommute = false;
861  if (TID.isCommutable() && mi->getNumOperands() >= 3 &&
862      TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) {
863    if (SrcIdx == SrcOp1)
864      regCIdx = SrcOp2;
865    else if (SrcIdx == SrcOp2)
866      regCIdx = SrcOp1;
867
868    if (regCIdx != ~0U) {
869      regC = mi->getOperand(regCIdx).getReg();
870      if (!regBKilled && isKilled(*mi, regC, MRI, TII))
871        // If C dies but B does not, swap the B and C operands.
872        // This makes the live ranges of A and C joinable.
873        TryCommute = true;
874      else if (isProfitableToCommute(regB, regC, mi, mbbi, Dist)) {
875        TryCommute = true;
876        AggressiveCommute = true;
877      }
878    }
879  }
880
881  // If it's profitable to commute, try to do so.
882  if (TryCommute && CommuteInstruction(mi, mbbi, regB, regC, Dist)) {
883    ++NumCommuted;
884    if (AggressiveCommute)
885      ++NumAggrCommuted;
886    return false;
887  }
888
889  if (TID.isConvertibleTo3Addr()) {
890    // This instruction is potentially convertible to a true
891    // three-address instruction.  Check if it is profitable.
892    if (!regBKilled || isProfitableToConv3Addr(regA)) {
893      // Try to convert it.
894      if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) {
895        ++NumConvertedTo3Addr;
896        return true; // Done with this instruction.
897      }
898    }
899  }
900  return false;
901}
902
903/// runOnMachineFunction - Reduce two-address instructions to two operands.
904///
905bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
906  DEBUG(dbgs() << "Machine Function\n");
907  const TargetMachine &TM = MF.getTarget();
908  MRI = &MF.getRegInfo();
909  TII = TM.getInstrInfo();
910  TRI = TM.getRegisterInfo();
911  LV = getAnalysisIfAvailable<LiveVariables>();
912  AA = &getAnalysis<AliasAnalysis>();
913
914  bool MadeChange = false;
915
916  DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
917  DEBUG(dbgs() << "********** Function: "
918        << MF.getFunction()->getName() << '\n');
919
920  // ReMatRegs - Keep track of the registers whose def's are remat'ed.
921  BitVector ReMatRegs;
922  ReMatRegs.resize(MRI->getLastVirtReg()+1);
923
924  typedef DenseMap<unsigned, SmallVector<std::pair<unsigned, unsigned>, 4> >
925    TiedOperandMap;
926  TiedOperandMap TiedOperands(4);
927
928  SmallPtrSet<MachineInstr*, 8> Processed;
929  for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
930       mbbi != mbbe; ++mbbi) {
931    unsigned Dist = 0;
932    DistanceMap.clear();
933    SrcRegMap.clear();
934    DstRegMap.clear();
935    Processed.clear();
936    for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
937         mi != me; ) {
938      MachineBasicBlock::iterator nmi = llvm::next(mi);
939      if (mi->isDebugValue()) {
940        mi = nmi;
941        continue;
942      }
943
944      // Remember REG_SEQUENCE instructions, we'll deal with them later.
945      if (mi->isRegSequence())
946        RegSequences.push_back(&*mi);
947
948      const TargetInstrDesc &TID = mi->getDesc();
949      bool FirstTied = true;
950
951      DistanceMap.insert(std::make_pair(mi, ++Dist));
952
953      ProcessCopy(&*mi, &*mbbi, Processed);
954
955      // First scan through all the tied register uses in this instruction
956      // and record a list of pairs of tied operands for each register.
957      unsigned NumOps = mi->isInlineAsm()
958        ? mi->getNumOperands() : TID.getNumOperands();
959      for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
960        unsigned DstIdx = 0;
961        if (!mi->isRegTiedToDefOperand(SrcIdx, &DstIdx))
962          continue;
963
964        if (FirstTied) {
965          FirstTied = false;
966          ++NumTwoAddressInstrs;
967          DEBUG(dbgs() << '\t' << *mi);
968        }
969
970        assert(mi->getOperand(SrcIdx).isReg() &&
971               mi->getOperand(SrcIdx).getReg() &&
972               mi->getOperand(SrcIdx).isUse() &&
973               "two address instruction invalid");
974
975        unsigned regB = mi->getOperand(SrcIdx).getReg();
976        TiedOperandMap::iterator OI = TiedOperands.find(regB);
977        if (OI == TiedOperands.end()) {
978          SmallVector<std::pair<unsigned, unsigned>, 4> TiedPair;
979          OI = TiedOperands.insert(std::make_pair(regB, TiedPair)).first;
980        }
981        OI->second.push_back(std::make_pair(SrcIdx, DstIdx));
982      }
983
984      // Now iterate over the information collected above.
985      for (TiedOperandMap::iterator OI = TiedOperands.begin(),
986             OE = TiedOperands.end(); OI != OE; ++OI) {
987        SmallVector<std::pair<unsigned, unsigned>, 4> &TiedPairs = OI->second;
988
989        // If the instruction has a single pair of tied operands, try some
990        // transformations that may either eliminate the tied operands or
991        // improve the opportunities for coalescing away the register copy.
992        if (TiedOperands.size() == 1 && TiedPairs.size() == 1) {
993          unsigned SrcIdx = TiedPairs[0].first;
994          unsigned DstIdx = TiedPairs[0].second;
995
996          // If the registers are already equal, nothing needs to be done.
997          if (mi->getOperand(SrcIdx).getReg() ==
998              mi->getOperand(DstIdx).getReg())
999            break; // Done with this instruction.
1000
1001          if (TryInstructionTransform(mi, nmi, mbbi, SrcIdx, DstIdx, Dist))
1002            break; // The tied operands have been eliminated.
1003        }
1004
1005        bool RemovedKillFlag = false;
1006        bool AllUsesCopied = true;
1007        unsigned LastCopiedReg = 0;
1008        unsigned regB = OI->first;
1009        for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1010          unsigned SrcIdx = TiedPairs[tpi].first;
1011          unsigned DstIdx = TiedPairs[tpi].second;
1012          unsigned regA = mi->getOperand(DstIdx).getReg();
1013          // Grab regB from the instruction because it may have changed if the
1014          // instruction was commuted.
1015          regB = mi->getOperand(SrcIdx).getReg();
1016
1017          if (regA == regB) {
1018            // The register is tied to multiple destinations (or else we would
1019            // not have continued this far), but this use of the register
1020            // already matches the tied destination.  Leave it.
1021            AllUsesCopied = false;
1022            continue;
1023          }
1024          LastCopiedReg = regA;
1025
1026          assert(TargetRegisterInfo::isVirtualRegister(regB) &&
1027                 "cannot make instruction into two-address form");
1028
1029#ifndef NDEBUG
1030          // First, verify that we don't have a use of "a" in the instruction
1031          // (a = b + a for example) because our transformation will not
1032          // work. This should never occur because we are in SSA form.
1033          for (unsigned i = 0; i != mi->getNumOperands(); ++i)
1034            assert(i == DstIdx ||
1035                   !mi->getOperand(i).isReg() ||
1036                   mi->getOperand(i).getReg() != regA);
1037#endif
1038
1039          // Emit a copy or rematerialize the definition.
1040          const TargetRegisterClass *rc = MRI->getRegClass(regB);
1041          MachineInstr *DefMI = MRI->getVRegDef(regB);
1042          // If it's safe and profitable, remat the definition instead of
1043          // copying it.
1044          if (DefMI &&
1045              DefMI->getDesc().isAsCheapAsAMove() &&
1046              DefMI->isSafeToReMat(TII, AA, regB) &&
1047              isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){
1048            DEBUG(dbgs() << "2addr: REMATTING : " << *DefMI << "\n");
1049            unsigned regASubIdx = mi->getOperand(DstIdx).getSubReg();
1050            TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI, *TRI);
1051            ReMatRegs.set(regB);
1052            ++NumReMats;
1053          } else {
1054            bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc,
1055                                             mi->getDebugLoc());
1056            (void)Emitted;
1057            assert(Emitted && "Unable to issue a copy instruction!\n");
1058          }
1059
1060          MachineBasicBlock::iterator prevMI = prior(mi);
1061          // Update DistanceMap.
1062          DistanceMap.insert(std::make_pair(prevMI, Dist));
1063          DistanceMap[mi] = ++Dist;
1064
1065          DEBUG(dbgs() << "\t\tprepend:\t" << *prevMI);
1066
1067          MachineOperand &MO = mi->getOperand(SrcIdx);
1068          assert(MO.isReg() && MO.getReg() == regB && MO.isUse() &&
1069                 "inconsistent operand info for 2-reg pass");
1070          if (MO.isKill()) {
1071            MO.setIsKill(false);
1072            RemovedKillFlag = true;
1073          }
1074          MO.setReg(regA);
1075        }
1076
1077        if (AllUsesCopied) {
1078          // Replace other (un-tied) uses of regB with LastCopiedReg.
1079          for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
1080            MachineOperand &MO = mi->getOperand(i);
1081            if (MO.isReg() && MO.getReg() == regB && MO.isUse()) {
1082              if (MO.isKill()) {
1083                MO.setIsKill(false);
1084                RemovedKillFlag = true;
1085              }
1086              MO.setReg(LastCopiedReg);
1087            }
1088          }
1089
1090          // Update live variables for regB.
1091          if (RemovedKillFlag && LV && LV->getVarInfo(regB).removeKill(mi))
1092            LV->addVirtualRegisterKilled(regB, prior(mi));
1093
1094        } else if (RemovedKillFlag) {
1095          // Some tied uses of regB matched their destination registers, so
1096          // regB is still used in this instruction, but a kill flag was
1097          // removed from a different tied use of regB, so now we need to add
1098          // a kill flag to one of the remaining uses of regB.
1099          for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
1100            MachineOperand &MO = mi->getOperand(i);
1101            if (MO.isReg() && MO.getReg() == regB && MO.isUse()) {
1102              MO.setIsKill(true);
1103              break;
1104            }
1105          }
1106        }
1107
1108        // Schedule the source copy / remat inserted to form two-address
1109        // instruction. FIXME: Does it matter the distance map may not be
1110        // accurate after it's scheduled?
1111        TII->scheduleTwoAddrSource(prior(mi), mi, *TRI);
1112
1113        MadeChange = true;
1114
1115        DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1116      }
1117
1118      // Clear TiedOperands here instead of at the top of the loop
1119      // since most instructions do not have tied operands.
1120      TiedOperands.clear();
1121      mi = nmi;
1122    }
1123  }
1124
1125  // Some remat'ed instructions are dead.
1126  int VReg = ReMatRegs.find_first();
1127  while (VReg != -1) {
1128    if (MRI->use_nodbg_empty(VReg)) {
1129      MachineInstr *DefMI = MRI->getVRegDef(VReg);
1130      DefMI->eraseFromParent();
1131    }
1132    VReg = ReMatRegs.find_next(VReg);
1133  }
1134
1135  // Eliminate REG_SEQUENCE instructions. Their whole purpose was to preseve
1136  // SSA form. It's now safe to de-SSA.
1137  MadeChange |= EliminateRegSequences();
1138
1139  return MadeChange;
1140}
1141
1142static void UpdateRegSequenceSrcs(unsigned SrcReg,
1143                                  unsigned DstReg, unsigned SubIdx,
1144                                  MachineRegisterInfo *MRI,
1145                                  const TargetRegisterInfo &TRI) {
1146  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
1147         RE = MRI->reg_end(); RI != RE; ) {
1148    MachineOperand &MO = RI.getOperand();
1149    ++RI;
1150    MO.substVirtReg(DstReg, SubIdx, TRI);
1151  }
1152}
1153
1154/// CoalesceExtSubRegs - If a number of sources of the REG_SEQUENCE are
1155/// EXTRACT_SUBREG from the same register and to the same virtual register
1156/// with different sub-register indices, attempt to combine the
1157/// EXTRACT_SUBREGs and pre-coalesce them. e.g.
1158/// %reg1026<def> = VLDMQ %reg1025<kill>, 260, pred:14, pred:%reg0
1159/// %reg1029:6<def> = EXTRACT_SUBREG %reg1026, 6
1160/// %reg1029:5<def> = EXTRACT_SUBREG %reg1026<kill>, 5
1161/// Since D subregs 5, 6 can combine to a Q register, we can coalesce
1162/// reg1026 to reg1029.
1163void
1164TwoAddressInstructionPass::CoalesceExtSubRegs(SmallVector<unsigned,4> &Srcs,
1165                                              unsigned DstReg) {
1166  SmallSet<unsigned, 4> Seen;
1167  for (unsigned i = 0, e = Srcs.size(); i != e; ++i) {
1168    unsigned SrcReg = Srcs[i];
1169    if (!Seen.insert(SrcReg))
1170      continue;
1171
1172    // Check that the instructions are all in the same basic block.
1173    MachineInstr *SrcDefMI = MRI->getVRegDef(SrcReg);
1174    MachineInstr *DstDefMI = MRI->getVRegDef(DstReg);
1175    if (SrcDefMI->getParent() != DstDefMI->getParent())
1176      continue;
1177
1178    // If there are no other uses than extract_subreg which feed into
1179    // the reg_sequence, then we might be able to coalesce them.
1180    bool CanCoalesce = true;
1181    SmallVector<unsigned, 4> SubIndices;
1182    for (MachineRegisterInfo::use_nodbg_iterator
1183           UI = MRI->use_nodbg_begin(SrcReg),
1184           UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
1185      MachineInstr *UseMI = &*UI;
1186      // FIXME: For now require that the destination subregs match the subregs
1187      // being extracted.
1188      if (!UseMI->isExtractSubreg() ||
1189          UseMI->getOperand(0).getReg() != DstReg ||
1190          UseMI->getOperand(0).getSubReg() != UseMI->getOperand(2).getImm() ||
1191          UseMI->getOperand(1).getSubReg() != 0) {
1192        CanCoalesce = false;
1193        break;
1194      }
1195      SubIndices.push_back(UseMI->getOperand(2).getImm());
1196    }
1197
1198    if (!CanCoalesce || SubIndices.size() < 2)
1199      continue;
1200
1201    // FIXME: For now require that the src and dst registers are in the
1202    // same regclass.
1203    if (MRI->getRegClass(SrcReg) != MRI->getRegClass(DstReg))
1204      continue;
1205
1206    std::sort(SubIndices.begin(), SubIndices.end());
1207    unsigned NewSubIdx = 0;
1208    if (TRI->canCombineSubRegIndices(MRI->getRegClass(SrcReg), SubIndices,
1209                                     NewSubIdx)) {
1210      bool Proceed = true;
1211      if (NewSubIdx)
1212        for (MachineRegisterInfo::reg_nodbg_iterator
1213               RI = MRI->reg_nodbg_begin(SrcReg), RE = MRI->reg_nodbg_end();
1214             RI != RE; ) {
1215          MachineOperand &MO = RI.getOperand();
1216          ++RI;
1217          // FIXME: If the sub-registers do not combine to the whole
1218          // super-register, i.e. NewSubIdx != 0, and any of the use has a
1219          // sub-register index, then abort the coalescing attempt.
1220          if (MO.getSubReg()) {
1221            Proceed = false;
1222            break;
1223          }
1224        }
1225      if (Proceed)
1226        for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
1227               RE = MRI->reg_end(); RI != RE; ) {
1228          MachineOperand &MO = RI.getOperand();
1229          ++RI;
1230          MO.setReg(DstReg);
1231          if (NewSubIdx)
1232            MO.setSubReg(NewSubIdx);
1233        }
1234      }
1235  }
1236}
1237
1238static bool HasOtherRegSequenceUses(unsigned Reg, MachineInstr *RegSeq,
1239                                    MachineRegisterInfo *MRI) {
1240  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
1241         UE = MRI->use_end(); UI != UE; ++UI) {
1242    MachineInstr *UseMI = &*UI;
1243    if (UseMI != RegSeq && UseMI->isRegSequence())
1244      return true;
1245  }
1246  return false;
1247}
1248
1249/// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part
1250/// of the de-ssa process. This replaces sources of REG_SEQUENCE as
1251/// sub-register references of the register defined by REG_SEQUENCE. e.g.
1252///
1253/// %reg1029<def>, %reg1030<def> = VLD1q16 %reg1024<kill>, ...
1254/// %reg1031<def> = REG_SEQUENCE %reg1029<kill>, 5, %reg1030<kill>, 6
1255/// =>
1256/// %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
1257bool TwoAddressInstructionPass::EliminateRegSequences() {
1258  if (RegSequences.empty())
1259    return false;
1260
1261  for (unsigned i = 0, e = RegSequences.size(); i != e; ++i) {
1262    MachineInstr *MI = RegSequences[i];
1263    unsigned DstReg = MI->getOperand(0).getReg();
1264    if (MI->getOperand(0).getSubReg() ||
1265        TargetRegisterInfo::isPhysicalRegister(DstReg) ||
1266        !(MI->getNumOperands() & 1)) {
1267      DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
1268      llvm_unreachable(0);
1269    }
1270
1271    bool IsImpDef = true;
1272    SmallVector<unsigned, 4> RealSrcs;
1273    SmallSet<unsigned, 4> Seen;
1274    for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
1275      unsigned SrcReg = MI->getOperand(i).getReg();
1276      if (MI->getOperand(i).getSubReg() ||
1277          TargetRegisterInfo::isPhysicalRegister(SrcReg)) {
1278        DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
1279        llvm_unreachable(0);
1280      }
1281
1282      MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
1283      if (DefMI->isImplicitDef()) {
1284        DefMI->eraseFromParent();
1285        continue;
1286      }
1287      IsImpDef = false;
1288
1289      // Remember EXTRACT_SUBREG sources. These might be candidate for
1290      // coalescing.
1291      if (DefMI->isExtractSubreg())
1292        RealSrcs.push_back(DefMI->getOperand(1).getReg());
1293
1294      if (!Seen.insert(SrcReg) ||
1295          MI->getParent() != DefMI->getParent() ||
1296          !MI->getOperand(i).isKill() ||
1297          HasOtherRegSequenceUses(SrcReg, MI, MRI)) {
1298        // REG_SEQUENCE cannot have duplicated operands, add a copy.
1299        // Also add an copy if the source is live-in the block. We don't want
1300        // to end up with a partial-redef of a livein, e.g.
1301        // BB0:
1302        // reg1051:10<def> =
1303        // ...
1304        // BB1:
1305        // ... = reg1051:10
1306        // BB2:
1307        // reg1051:9<def> =
1308        // LiveIntervalAnalysis won't like it.
1309        //
1310        // If the REG_SEQUENCE doesn't kill its source, keeping live variables
1311        // correctly up to date becomes very difficult. Insert a copy.
1312        //
1313        const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
1314        unsigned NewReg = MRI->createVirtualRegister(RC);
1315        MachineBasicBlock::iterator InsertLoc = MI;
1316        bool Emitted =
1317          TII->copyRegToReg(*MI->getParent(), InsertLoc, NewReg, SrcReg, RC, RC,
1318                            MI->getDebugLoc());
1319        (void)Emitted;
1320        assert(Emitted && "Unable to issue a copy instruction!\n");
1321        MI->getOperand(i).setReg(NewReg);
1322        if (MI->getOperand(i).isKill()) {
1323          MachineBasicBlock::iterator CopyMI = prior(InsertLoc);
1324          MachineOperand *KillMO = CopyMI->findRegisterUseOperand(SrcReg);
1325          KillMO->setIsKill();
1326          if (LV)
1327            // Update live variables
1328            LV->replaceKillInstruction(SrcReg, MI, &*CopyMI);
1329        }
1330      }
1331    }
1332
1333    for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
1334      unsigned SrcReg = MI->getOperand(i).getReg();
1335      unsigned SubIdx = MI->getOperand(i+1).getImm();
1336      UpdateRegSequenceSrcs(SrcReg, DstReg, SubIdx, MRI, *TRI);
1337    }
1338
1339    if (IsImpDef) {
1340      DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");
1341      MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1342      for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
1343        MI->RemoveOperand(j);
1344    } else {
1345      DEBUG(dbgs() << "Eliminated: " << *MI);
1346      MI->eraseFromParent();
1347    }
1348
1349    // Try coalescing some EXTRACT_SUBREG instructions.
1350    CoalesceExtSubRegs(RealSrcs, DstReg);
1351  }
1352
1353  RegSequences.clear();
1354  return true;
1355}
1356