LLVM  6.0.0svn
TwoAddressInstructionPass.cpp
Go to the documentation of this file.
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 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallSet.h"
33 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/ADT/Statistic.h"
47 #include "llvm/CodeGen/Passes.h"
53 #include "llvm/MC/MCInstrDesc.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/CodeGen.h"
58 #include "llvm/Support/Debug.h"
62 #include <cassert>
63 #include <iterator>
64 #include <utility>
65 
66 using namespace llvm;
67 
68 #define DEBUG_TYPE "twoaddressinstruction"
69 
70 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
71 STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
72 STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
73 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
74 STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk");
75 STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up");
76 STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down");
77 
78 // Temporary flag to disable rescheduling.
79 static cl::opt<bool>
80 EnableRescheduling("twoaddr-reschedule",
81  cl::desc("Coalesce copies by rescheduling (default=true)"),
82  cl::init(true), cl::Hidden);
83 
84 // Limit the number of dataflow edges to traverse when evaluating the benefit
85 // of commuting operands.
87  "dataflow-edge-limit", cl::Hidden, cl::init(3),
88  cl::desc("Maximum number of dataflow edges to traverse when evaluating "
89  "the benefit of commuting operands"));
90 
91 namespace {
92 
93 class TwoAddressInstructionPass : public MachineFunctionPass {
94  MachineFunction *MF;
95  const TargetInstrInfo *TII;
96  const TargetRegisterInfo *TRI;
97  const InstrItineraryData *InstrItins;
99  LiveVariables *LV;
100  LiveIntervals *LIS;
101  AliasAnalysis *AA;
102  CodeGenOpt::Level OptLevel;
103 
104  // The current basic block being processed.
105  MachineBasicBlock *MBB;
106 
107  // Keep track the distance of a MI from the start of the current basic block.
109 
110  // Set of already processed instructions in the current block.
112 
113  // A map from virtual registers to physical registers which are likely targets
114  // to be coalesced to due to copies from physical registers to virtual
115  // registers. e.g. v1024 = move r0.
117 
118  // A map from virtual registers to physical registers which are likely targets
119  // to be coalesced to due to copies to physical registers from virtual
120  // registers. e.g. r1 = move v1024.
122 
123  bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg,
125 
126  bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen);
127 
128  bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef);
129 
130  bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
131  MachineInstr *MI, unsigned Dist);
132 
133  bool commuteInstruction(MachineInstr *MI, unsigned DstIdx,
134  unsigned RegBIdx, unsigned RegCIdx, unsigned Dist);
135 
136  bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB);
137 
138  bool convertInstTo3Addr(MachineBasicBlock::iterator &mi,
140  unsigned RegA, unsigned RegB, unsigned Dist);
141 
142  bool isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI);
143 
144  bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
146  unsigned Reg);
147  bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
149  unsigned Reg);
150 
151  bool tryInstructionTransform(MachineBasicBlock::iterator &mi,
153  unsigned SrcIdx, unsigned DstIdx,
154  unsigned Dist, bool shouldOnlyCommute);
155 
156  bool tryInstructionCommute(MachineInstr *MI,
157  unsigned DstOpIdx,
158  unsigned BaseOpIdx,
159  bool BaseOpKilled,
160  unsigned Dist);
161  void scanUses(unsigned DstReg);
162 
163  void processCopy(MachineInstr *MI);
164 
165  using TiedPairList = SmallVector<std::pair<unsigned, unsigned>, 4>;
166  using TiedOperandMap = SmallDenseMap<unsigned, TiedPairList>;
167 
168  bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&);
169  void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist);
170  void eliminateRegSequence(MachineBasicBlock::iterator&);
171 
172 public:
173  static char ID; // Pass identification, replacement for typeid
174 
175  TwoAddressInstructionPass() : MachineFunctionPass(ID) {
177  }
178 
179  void getAnalysisUsage(AnalysisUsage &AU) const override {
180  AU.setPreservesCFG();
189  }
190 
191  /// Pass entry point.
192  bool runOnMachineFunction(MachineFunction&) override;
193 };
194 
195 } // end anonymous namespace
196 
198 
200 
201 INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, DEBUG_TYPE,
202  "Two-Address instruction pass", false, false)
204 INITIALIZE_PASS_END(TwoAddressInstructionPass, DEBUG_TYPE,
205  "Two-Address instruction pass", false, false)
206 
207 static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS);
208 
209 /// A two-address instruction has been converted to a three-address instruction
210 /// to avoid clobbering a register. Try to sink it past the instruction that
211 /// would kill the above mentioned register to reduce register pressure.
212 bool TwoAddressInstructionPass::
213 sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg,
214  MachineBasicBlock::iterator OldPos) {
215  // FIXME: Shouldn't we be trying to do this before we three-addressify the
216  // instruction? After this transformation is done, we no longer need
217  // the instruction to be in three-address form.
218 
219  // Check if it's safe to move this instruction.
220  bool SeenStore = true; // Be conservative.
221  if (!MI->isSafeToMove(AA, SeenStore))
222  return false;
223 
224  unsigned DefReg = 0;
225  SmallSet<unsigned, 4> UseRegs;
226 
227  for (const MachineOperand &MO : MI->operands()) {
228  if (!MO.isReg())
229  continue;
230  unsigned MOReg = MO.getReg();
231  if (!MOReg)
232  continue;
233  if (MO.isUse() && MOReg != SavedReg)
234  UseRegs.insert(MO.getReg());
235  if (!MO.isDef())
236  continue;
237  if (MO.isImplicit())
238  // Don't try to move it if it implicitly defines a register.
239  return false;
240  if (DefReg)
241  // For now, don't move any instructions that define multiple registers.
242  return false;
243  DefReg = MO.getReg();
244  }
245 
246  // Find the instruction that kills SavedReg.
247  MachineInstr *KillMI = nullptr;
248  if (LIS) {
249  LiveInterval &LI = LIS->getInterval(SavedReg);
250  assert(LI.end() != LI.begin() &&
251  "Reg should not have empty live interval.");
252 
253  SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
254  LiveInterval::const_iterator I = LI.find(MBBEndIdx);
255  if (I != LI.end() && I->start < MBBEndIdx)
256  return false;
257 
258  --I;
259  KillMI = LIS->getInstructionFromIndex(I->end);
260  }
261  if (!KillMI) {
262  for (MachineOperand &UseMO : MRI->use_nodbg_operands(SavedReg)) {
263  if (!UseMO.isKill())
264  continue;
265  KillMI = UseMO.getParent();
266  break;
267  }
268  }
269 
270  // If we find the instruction that kills SavedReg, and it is in an
271  // appropriate location, we can try to sink the current instruction
272  // past it.
273  if (!KillMI || KillMI->getParent() != MBB || KillMI == MI ||
274  MachineBasicBlock::iterator(KillMI) == OldPos || KillMI->isTerminator())
275  return false;
276 
277  // If any of the definitions are used by another instruction between the
278  // position and the kill use, then it's not safe to sink it.
279  //
280  // FIXME: This can be sped up if there is an easy way to query whether an
281  // instruction is before or after another instruction. Then we can use
282  // MachineRegisterInfo def / use instead.
283  MachineOperand *KillMO = nullptr;
284  MachineBasicBlock::iterator KillPos = KillMI;
285  ++KillPos;
286 
287  unsigned NumVisited = 0;
288  for (MachineInstr &OtherMI : make_range(std::next(OldPos), KillPos)) {
289  // DBG_VALUE cannot be counted against the limit.
290  if (OtherMI.isDebugValue())
291  continue;
292  if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost.
293  return false;
294  ++NumVisited;
295  for (unsigned i = 0, e = OtherMI.getNumOperands(); i != e; ++i) {
296  MachineOperand &MO = OtherMI.getOperand(i);
297  if (!MO.isReg())
298  continue;
299  unsigned MOReg = MO.getReg();
300  if (!MOReg)
301  continue;
302  if (DefReg == MOReg)
303  return false;
304 
305  if (MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS))) {
306  if (&OtherMI == KillMI && MOReg == SavedReg)
307  // Save the operand that kills the register. We want to unset the kill
308  // marker if we can sink MI past it.
309  KillMO = &MO;
310  else if (UseRegs.count(MOReg))
311  // One of the uses is killed before the destination.
312  return false;
313  }
314  }
315  }
316  assert(KillMO && "Didn't find kill");
317 
318  if (!LIS) {
319  // Update kill and LV information.
320  KillMO->setIsKill(false);
321  KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
322  KillMO->setIsKill(true);
323 
324  if (LV)
325  LV->replaceKillInstruction(SavedReg, *KillMI, *MI);
326  }
327 
328  // Move instruction to its destination.
329  MBB->remove(MI);
330  MBB->insert(KillPos, MI);
331 
332  if (LIS)
333  LIS->handleMove(*MI);
334 
335  ++Num3AddrSunk;
336  return true;
337 }
338 
339 /// Return the MachineInstr* if it is the single def of the Reg in current BB.
341  const MachineRegisterInfo *MRI) {
342  MachineInstr *Ret = nullptr;
343  for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
344  if (DefMI.getParent() != BB || DefMI.isDebugValue())
345  continue;
346  if (!Ret)
347  Ret = &DefMI;
348  else if (Ret != &DefMI)
349  return nullptr;
350  }
351  return Ret;
352 }
353 
354 /// Check if there is a reversed copy chain from FromReg to ToReg:
355 /// %Tmp1 = copy %Tmp2;
356 /// %FromReg = copy %Tmp1;
357 /// %ToReg = add %FromReg ...
358 /// %Tmp2 = copy %ToReg;
359 /// MaxLen specifies the maximum length of the copy chain the func
360 /// can walk through.
361 bool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg,
362  int Maxlen) {
363  unsigned TmpReg = FromReg;
364  for (int i = 0; i < Maxlen; i++) {
365  MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI);
366  if (!Def || !Def->isCopy())
367  return false;
368 
369  TmpReg = Def->getOperand(1).getReg();
370 
371  if (TmpReg == ToReg)
372  return true;
373  }
374  return false;
375 }
376 
377 /// Return true if there are no intervening uses between the last instruction
378 /// in the MBB that defines the specified register and the two-address
379 /// instruction which is being processed. It also returns the last def location
380 /// by reference.
381 bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist,
382  unsigned &LastDef) {
383  LastDef = 0;
384  unsigned LastUse = Dist;
385  for (MachineOperand &MO : MRI->reg_operands(Reg)) {
386  MachineInstr *MI = MO.getParent();
387  if (MI->getParent() != MBB || MI->isDebugValue())
388  continue;
390  if (DI == DistanceMap.end())
391  continue;
392  if (MO.isUse() && DI->second < LastUse)
393  LastUse = DI->second;
394  if (MO.isDef() && DI->second > LastDef)
395  LastDef = DI->second;
396  }
397 
398  return !(LastUse > LastDef && LastUse < Dist);
399 }
400 
401 /// Return true if the specified MI is a copy instruction or an extract_subreg
402 /// instruction. It also returns the source and destination registers and
403 /// whether they are physical registers by reference.
404 static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
405  unsigned &SrcReg, unsigned &DstReg,
406  bool &IsSrcPhys, bool &IsDstPhys) {
407  SrcReg = 0;
408  DstReg = 0;
409  if (MI.isCopy()) {
410  DstReg = MI.getOperand(0).getReg();
411  SrcReg = MI.getOperand(1).getReg();
412  } else if (MI.isInsertSubreg() || MI.isSubregToReg()) {
413  DstReg = MI.getOperand(0).getReg();
414  SrcReg = MI.getOperand(2).getReg();
415  } else
416  return false;
417 
418  IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
419  IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
420  return true;
421 }
422 
423 /// Test if the given register value, which is used by the
424 /// given instruction, is killed by the given instruction.
425 static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg,
426  LiveIntervals *LIS) {
427  if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) &&
428  !LIS->isNotInMIMap(*MI)) {
429  // FIXME: Sometimes tryInstructionTransform() will add instructions and
430  // test whether they can be folded before keeping them. In this case it
431  // sets a kill before recursively calling tryInstructionTransform() again.
432  // If there is no interval available, we assume that this instruction is
433  // one of those. A kill flag is manually inserted on the operand so the
434  // check below will handle it.
435  LiveInterval &LI = LIS->getInterval(Reg);
436  // This is to match the kill flag version where undefs don't have kill
437  // flags.
438  if (!LI.hasAtLeastOneValue())
439  return false;
440 
441  SlotIndex useIdx = LIS->getInstructionIndex(*MI);
442  LiveInterval::const_iterator I = LI.find(useIdx);
443  assert(I != LI.end() && "Reg must be live-in to use.");
444  return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx);
445  }
446 
447  return MI->killsRegister(Reg);
448 }
449 
450 /// Test if the given register value, which is used by the given
451 /// instruction, is killed by the given instruction. This looks through
452 /// coalescable copies to see if the original value is potentially not killed.
453 ///
454 /// For example, in this code:
455 ///
456 /// %reg1034 = copy %reg1024
457 /// %reg1035 = copy %reg1025<kill>
458 /// %reg1036 = add %reg1034<kill>, %reg1035<kill>
459 ///
460 /// %reg1034 is not considered to be killed, since it is copied from a
461 /// register which is not killed. Treating it as not killed lets the
462 /// normal heuristics commute the (two-address) add, which lets
463 /// coalescing eliminate the extra copy.
464 ///
465 /// If allowFalsePositives is true then likely kills are treated as kills even
466 /// if it can't be proven that they are kills.
467 static bool isKilled(MachineInstr &MI, unsigned Reg,
468  const MachineRegisterInfo *MRI,
469  const TargetInstrInfo *TII,
470  LiveIntervals *LIS,
471  bool allowFalsePositives) {
472  MachineInstr *DefMI = &MI;
473  while (true) {
474  // All uses of physical registers are likely to be kills.
476  (allowFalsePositives || MRI->hasOneUse(Reg)))
477  return true;
478  if (!isPlainlyKilled(DefMI, Reg, LIS))
479  return false;
481  return true;
483  // If there are multiple defs, we can't do a simple analysis, so just
484  // go with what the kill flag says.
485  if (std::next(Begin) != MRI->def_end())
486  return true;
487  DefMI = Begin->getParent();
488  bool IsSrcPhys, IsDstPhys;
489  unsigned SrcReg, DstReg;
490  // If the def is something other than a copy, then it isn't going to
491  // be coalesced, so follow the kill flag.
492  if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
493  return true;
494  Reg = SrcReg;
495  }
496 }
497 
498 /// Return true if the specified MI uses the specified register as a two-address
499 /// use. If so, return the destination register by reference.
500 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
501  for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) {
502  const MachineOperand &MO = MI.getOperand(i);
503  if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
504  continue;
505  unsigned ti;
506  if (MI.isRegTiedToDefOperand(i, &ti)) {
507  DstReg = MI.getOperand(ti).getReg();
508  return true;
509  }
510  }
511  return false;
512 }
513 
514 /// Given a register, if has a single in-basic block use, return the use
515 /// instruction if it's a copy or a two-address use.
516 static
518  MachineRegisterInfo *MRI,
519  const TargetInstrInfo *TII,
520  bool &IsCopy,
521  unsigned &DstReg, bool &IsDstPhys) {
522  if (!MRI->hasOneNonDBGUse(Reg))
523  // None or more than one use.
524  return nullptr;
526  if (UseMI.getParent() != MBB)
527  return nullptr;
528  unsigned SrcReg;
529  bool IsSrcPhys;
530  if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
531  IsCopy = true;
532  return &UseMI;
533  }
534  IsDstPhys = false;
535  if (isTwoAddrUse(UseMI, Reg, DstReg)) {
536  IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
537  return &UseMI;
538  }
539  return nullptr;
540 }
541 
542 /// Return the physical register the specified virtual register might be mapped
543 /// to.
544 static unsigned
548  if (SI == RegMap.end())
549  return 0;
550  Reg = SI->second;
551  }
553  return Reg;
554  return 0;
555 }
556 
557 /// Return true if the two registers are equal or aliased.
558 static bool
559 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
560  if (RegA == RegB)
561  return true;
562  if (!RegA || !RegB)
563  return false;
564  return TRI->regsOverlap(RegA, RegB);
565 }
566 
567 // Returns true if Reg is equal or aliased to at least one register in Set.
568 static bool regOverlapsSet(const SmallVectorImpl<unsigned> &Set, unsigned Reg,
569  const TargetRegisterInfo *TRI) {
570  for (unsigned R : Set)
571  if (TRI->regsOverlap(R, Reg))
572  return true;
573 
574  return false;
575 }
576 
577 /// Return true if it's potentially profitable to commute the two-address
578 /// instruction that's being processed.
579 bool
580 TwoAddressInstructionPass::
581 isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
582  MachineInstr *MI, unsigned Dist) {
583  if (OptLevel == CodeGenOpt::None)
584  return false;
585 
586  // Determine if it's profitable to commute this two address instruction. In
587  // general, we want no uses between this instruction and the definition of
588  // the two-address register.
589  // e.g.
590  // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
591  // %reg1029<def> = MOV8rr %reg1028
592  // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
593  // insert => %reg1030<def> = MOV8rr %reg1028
594  // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
595  // In this case, it might not be possible to coalesce the second MOV8rr
596  // instruction if the first one is coalesced. So it would be profitable to
597  // commute it:
598  // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
599  // %reg1029<def> = MOV8rr %reg1028
600  // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
601  // insert => %reg1030<def> = MOV8rr %reg1029
602  // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
603 
604  if (!isPlainlyKilled(MI, regC, LIS))
605  return false;
606 
607  // Ok, we have something like:
608  // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
609  // let's see if it's worth commuting it.
610 
611  // Look for situations like this:
612  // %reg1024<def> = MOV r1
613  // %reg1025<def> = MOV r0
614  // %reg1026<def> = ADD %reg1024, %reg1025
615  // r0 = MOV %reg1026
616  // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
617  unsigned ToRegA = getMappedReg(regA, DstRegMap);
618  if (ToRegA) {
619  unsigned FromRegB = getMappedReg(regB, SrcRegMap);
620  unsigned FromRegC = getMappedReg(regC, SrcRegMap);
621  bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI);
622  bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI);
623 
624  // Compute if any of the following are true:
625  // -RegB is not tied to a register and RegC is compatible with RegA.
626  // -RegB is tied to the wrong physical register, but RegC is.
627  // -RegB is tied to the wrong physical register, and RegC isn't tied.
628  if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC)))
629  return true;
630  // Don't compute if any of the following are true:
631  // -RegC is not tied to a register and RegB is compatible with RegA.
632  // -RegC is tied to the wrong physical register, but RegB is.
633  // -RegC is tied to the wrong physical register, and RegB isn't tied.
634  if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB)))
635  return false;
636  }
637 
638  // If there is a use of regC between its last def (could be livein) and this
639  // instruction, then bail.
640  unsigned LastDefC = 0;
641  if (!noUseAfterLastDef(regC, Dist, LastDefC))
642  return false;
643 
644  // If there is a use of regB between its last def (could be livein) and this
645  // instruction, then go ahead and make this transformation.
646  unsigned LastDefB = 0;
647  if (!noUseAfterLastDef(regB, Dist, LastDefB))
648  return true;
649 
650  // Look for situation like this:
651  // %reg101 = MOV %reg100
652  // %reg102 = ...
653  // %reg103 = ADD %reg102, %reg101
654  // ... = %reg103 ...
655  // %reg100 = MOV %reg103
656  // If there is a reversed copy chain from reg101 to reg103, commute the ADD
657  // to eliminate an otherwise unavoidable copy.
658  // FIXME:
659  // We can extend the logic further: If an pair of operands in an insn has
660  // been merged, the insn could be regarded as a virtual copy, and the virtual
661  // copy could also be used to construct a copy chain.
662  // To more generally minimize register copies, ideally the logic of two addr
663  // instruction pass should be integrated with register allocation pass where
664  // interference graph is available.
665  if (isRevCopyChain(regC, regA, MaxDataFlowEdge))
666  return true;
667 
668  if (isRevCopyChain(regB, regA, MaxDataFlowEdge))
669  return false;
670 
671  // Since there are no intervening uses for both registers, then commute
672  // if the def of regC is closer. Its live interval is shorter.
673  return LastDefB && LastDefC && LastDefC > LastDefB;
674 }
675 
676 /// Commute a two-address instruction and update the basic block, distance map,
677 /// and live variables if needed. Return true if it is successful.
678 bool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI,
679  unsigned DstIdx,
680  unsigned RegBIdx,
681  unsigned RegCIdx,
682  unsigned Dist) {
683  unsigned RegC = MI->getOperand(RegCIdx).getReg();
684  DEBUG(dbgs() << "2addr: COMMUTING : " << *MI);
685  MachineInstr *NewMI = TII->commuteInstruction(*MI, false, RegBIdx, RegCIdx);
686 
687  if (NewMI == nullptr) {
688  DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
689  return false;
690  }
691 
692  DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
693  assert(NewMI == MI &&
694  "TargetInstrInfo::commuteInstruction() should not return a new "
695  "instruction unless it was requested.");
696 
697  // Update source register map.
698  unsigned FromRegC = getMappedReg(RegC, SrcRegMap);
699  if (FromRegC) {
700  unsigned RegA = MI->getOperand(DstIdx).getReg();
701  SrcRegMap[RegA] = FromRegC;
702  }
703 
704  return true;
705 }
706 
707 /// Return true if it is profitable to convert the given 2-address instruction
708 /// to a 3-address one.
709 bool
710 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){
711  // Look for situations like this:
712  // %reg1024<def> = MOV r1
713  // %reg1025<def> = MOV r0
714  // %reg1026<def> = ADD %reg1024, %reg1025
715  // r2 = MOV %reg1026
716  // Turn ADD into a 3-address instruction to avoid a copy.
717  unsigned FromRegB = getMappedReg(RegB, SrcRegMap);
718  if (!FromRegB)
719  return false;
720  unsigned ToRegA = getMappedReg(RegA, DstRegMap);
721  return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI));
722 }
723 
724 /// Convert the specified two-address instruction into a three address one.
725 /// Return true if this transformation was successful.
726 bool
727 TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi,
729  unsigned RegA, unsigned RegB,
730  unsigned Dist) {
731  // FIXME: Why does convertToThreeAddress() need an iterator reference?
733  MachineInstr *NewMI = TII->convertToThreeAddress(MFI, *mi, LV);
734  assert(MBB->getIterator() == MFI &&
735  "convertToThreeAddress changed iterator reference");
736  if (!NewMI)
737  return false;
738 
739  DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
740  DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI);
741  bool Sunk = false;
742 
743  if (LIS)
744  LIS->ReplaceMachineInstrInMaps(*mi, *NewMI);
745 
746  if (NewMI->findRegisterUseOperand(RegB, false, TRI))
747  // FIXME: Temporary workaround. If the new instruction doesn't
748  // uses RegB, convertToThreeAddress must have created more
749  // then one instruction.
750  Sunk = sink3AddrInstruction(NewMI, RegB, mi);
751 
752  MBB->erase(mi); // Nuke the old inst.
753 
754  if (!Sunk) {
755  DistanceMap.insert(std::make_pair(NewMI, Dist));
756  mi = NewMI;
757  nmi = std::next(mi);
758  }
759 
760  // Update source and destination register maps.
761  SrcRegMap.erase(RegA);
762  DstRegMap.erase(RegB);
763  return true;
764 }
765 
766 /// Scan forward recursively for only uses, update maps if the use is a copy or
767 /// a two-address instruction.
768 void
769 TwoAddressInstructionPass::scanUses(unsigned DstReg) {
770  SmallVector<unsigned, 4> VirtRegPairs;
771  bool IsDstPhys;
772  bool IsCopy = false;
773  unsigned NewReg = 0;
774  unsigned Reg = DstReg;
775  while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy,
776  NewReg, IsDstPhys)) {
777  if (IsCopy && !Processed.insert(UseMI).second)
778  break;
779 
781  if (DI != DistanceMap.end())
782  // Earlier in the same MBB.Reached via a back edge.
783  break;
784 
785  if (IsDstPhys) {
786  VirtRegPairs.push_back(NewReg);
787  break;
788  }
789  bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second;
790  if (!isNew)
791  assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!");
792  VirtRegPairs.push_back(NewReg);
793  Reg = NewReg;
794  }
795 
796  if (!VirtRegPairs.empty()) {
797  unsigned ToReg = VirtRegPairs.back();
798  VirtRegPairs.pop_back();
799  while (!VirtRegPairs.empty()) {
800  unsigned FromReg = VirtRegPairs.back();
801  VirtRegPairs.pop_back();
802  bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
803  if (!isNew)
804  assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
805  ToReg = FromReg;
806  }
807  bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second;
808  if (!isNew)
809  assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
810  }
811 }
812 
813 /// If the specified instruction is not yet processed, process it if it's a
814 /// copy. For a copy instruction, we find the physical registers the
815 /// source and destination registers might be mapped to. These are kept in
816 /// point-to maps used to determine future optimizations. e.g.
817 /// v1024 = mov r0
818 /// v1025 = mov r1
819 /// v1026 = add v1024, v1025
820 /// r1 = mov r1026
821 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially
822 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
823 /// potentially joined with r1 on the output side. It's worthwhile to commute
824 /// 'add' to eliminate a copy.
825 void TwoAddressInstructionPass::processCopy(MachineInstr *MI) {
826  if (Processed.count(MI))
827  return;
828 
829  bool IsSrcPhys, IsDstPhys;
830  unsigned SrcReg, DstReg;
831  if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
832  return;
833 
834  if (IsDstPhys && !IsSrcPhys)
835  DstRegMap.insert(std::make_pair(SrcReg, DstReg));
836  else if (!IsDstPhys && IsSrcPhys) {
837  bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
838  if (!isNew)
839  assert(SrcRegMap[DstReg] == SrcReg &&
840  "Can't map to two src physical registers!");
841 
842  scanUses(DstReg);
843  }
844 
845  Processed.insert(MI);
846 }
847 
848 /// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
849 /// consider moving the instruction below the kill instruction in order to
850 /// eliminate the need for the copy.
851 bool TwoAddressInstructionPass::
852 rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
854  unsigned Reg) {
855  // Bail immediately if we don't have LV or LIS available. We use them to find
856  // kills efficiently.
857  if (!LV && !LIS)
858  return false;
859 
860  MachineInstr *MI = &*mi;
862  if (DI == DistanceMap.end())
863  // Must be created from unfolded load. Don't waste time trying this.
864  return false;
865 
866  MachineInstr *KillMI = nullptr;
867  if (LIS) {
868  LiveInterval &LI = LIS->getInterval(Reg);
869  assert(LI.end() != LI.begin() &&
870  "Reg should not have empty live interval.");
871 
872  SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
873  LiveInterval::const_iterator I = LI.find(MBBEndIdx);
874  if (I != LI.end() && I->start < MBBEndIdx)
875  return false;
876 
877  --I;
878  KillMI = LIS->getInstructionFromIndex(I->end);
879  } else {
880  KillMI = LV->getVarInfo(Reg).findKill(MBB);
881  }
882  if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
883  // Don't mess with copies, they may be coalesced later.
884  return false;
885 
886  if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
887  KillMI->isBranch() || KillMI->isTerminator())
888  // Don't move pass calls, etc.
889  return false;
890 
891  unsigned DstReg;
892  if (isTwoAddrUse(*KillMI, Reg, DstReg))
893  return false;
894 
895  bool SeenStore = true;
896  if (!MI->isSafeToMove(AA, SeenStore))
897  return false;
898 
899  if (TII->getInstrLatency(InstrItins, *MI) > 1)
900  // FIXME: Needs more sophisticated heuristics.
901  return false;
902 
906  for (const MachineOperand &MO : MI->operands()) {
907  if (!MO.isReg())
908  continue;
909  unsigned MOReg = MO.getReg();
910  if (!MOReg)
911  continue;
912  if (MO.isDef())
913  Defs.push_back(MOReg);
914  else {
915  Uses.push_back(MOReg);
916  if (MOReg != Reg && (MO.isKill() ||
917  (LIS && isPlainlyKilled(MI, MOReg, LIS))))
918  Kills.push_back(MOReg);
919  }
920  }
921 
922  // Move the copies connected to MI down as well.
924  MachineBasicBlock::iterator AfterMI = std::next(Begin);
926  while (End->isCopy() &&
927  regOverlapsSet(Defs, End->getOperand(1).getReg(), TRI)) {
928  Defs.push_back(End->getOperand(0).getReg());
929  ++End;
930  }
931 
932  // Check if the reschedule will not break dependencies.
933  unsigned NumVisited = 0;
934  MachineBasicBlock::iterator KillPos = KillMI;
935  ++KillPos;
936  for (MachineInstr &OtherMI : make_range(End, KillPos)) {
937  // DBG_VALUE cannot be counted against the limit.
938  if (OtherMI.isDebugValue())
939  continue;
940  if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
941  return false;
942  ++NumVisited;
943  if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
944  OtherMI.isBranch() || OtherMI.isTerminator())
945  // Don't move pass calls, etc.
946  return false;
947  for (const MachineOperand &MO : OtherMI.operands()) {
948  if (!MO.isReg())
949  continue;
950  unsigned MOReg = MO.getReg();
951  if (!MOReg)
952  continue;
953  if (MO.isDef()) {
954  if (regOverlapsSet(Uses, MOReg, TRI))
955  // Physical register use would be clobbered.
956  return false;
957  if (!MO.isDead() && regOverlapsSet(Defs, MOReg, TRI))
958  // May clobber a physical register def.
959  // FIXME: This may be too conservative. It's ok if the instruction
960  // is sunken completely below the use.
961  return false;
962  } else {
963  if (regOverlapsSet(Defs, MOReg, TRI))
964  return false;
965  bool isKill =
966  MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS));
967  if (MOReg != Reg && ((isKill && regOverlapsSet(Uses, MOReg, TRI)) ||
968  regOverlapsSet(Kills, MOReg, TRI)))
969  // Don't want to extend other live ranges and update kills.
970  return false;
971  if (MOReg == Reg && !isKill)
972  // We can't schedule across a use of the register in question.
973  return false;
974  // Ensure that if this is register in question, its the kill we expect.
975  assert((MOReg != Reg || &OtherMI == KillMI) &&
976  "Found multiple kills of a register in a basic block");
977  }
978  }
979  }
980 
981  // Move debug info as well.
982  while (Begin != MBB->begin() && std::prev(Begin)->isDebugValue())
983  --Begin;
984 
985  nmi = End;
986  MachineBasicBlock::iterator InsertPos = KillPos;
987  if (LIS) {
988  // We have to move the copies first so that the MBB is still well-formed
989  // when calling handleMove().
990  for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) {
991  auto CopyMI = MBBI++;
992  MBB->splice(InsertPos, MBB, CopyMI);
993  LIS->handleMove(*CopyMI);
994  InsertPos = CopyMI;
995  }
996  End = std::next(MachineBasicBlock::iterator(MI));
997  }
998 
999  // Copies following MI may have been moved as well.
1000  MBB->splice(InsertPos, MBB, Begin, End);
1001  DistanceMap.erase(DI);
1002 
1003  // Update live variables
1004  if (LIS) {
1005  LIS->handleMove(*MI);
1006  } else {
1007  LV->removeVirtualRegisterKilled(Reg, *KillMI);
1008  LV->addVirtualRegisterKilled(Reg, *MI);
1009  }
1010 
1011  DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI);
1012  return true;
1013 }
1014 
1015 /// Return true if the re-scheduling will put the given instruction too close
1016 /// to the defs of its register dependencies.
1017 bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist,
1018  MachineInstr *MI) {
1019  for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
1020  if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike())
1021  continue;
1022  if (&DefMI == MI)
1023  return true; // MI is defining something KillMI uses
1025  if (DDI == DistanceMap.end())
1026  return true; // Below MI
1027  unsigned DefDist = DDI->second;
1028  assert(Dist > DefDist && "Visited def already?");
1029  if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
1030  return true;
1031  }
1032  return false;
1033 }
1034 
1035 /// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
1036 /// consider moving the kill instruction above the current two-address
1037 /// instruction in order to eliminate the need for the copy.
1038 bool TwoAddressInstructionPass::
1039 rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
1041  unsigned Reg) {
1042  // Bail immediately if we don't have LV or LIS available. We use them to find
1043  // kills efficiently.
1044  if (!LV && !LIS)
1045  return false;
1046 
1047  MachineInstr *MI = &*mi;
1049  if (DI == DistanceMap.end())
1050  // Must be created from unfolded load. Don't waste time trying this.
1051  return false;
1052 
1053  MachineInstr *KillMI = nullptr;
1054  if (LIS) {
1055  LiveInterval &LI = LIS->getInterval(Reg);
1056  assert(LI.end() != LI.begin() &&
1057  "Reg should not have empty live interval.");
1058 
1059  SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
1060  LiveInterval::const_iterator I = LI.find(MBBEndIdx);
1061  if (I != LI.end() && I->start < MBBEndIdx)
1062  return false;
1063 
1064  --I;
1065  KillMI = LIS->getInstructionFromIndex(I->end);
1066  } else {
1067  KillMI = LV->getVarInfo(Reg).findKill(MBB);
1068  }
1069  if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
1070  // Don't mess with copies, they may be coalesced later.
1071  return false;
1072 
1073  unsigned DstReg;
1074  if (isTwoAddrUse(*KillMI, Reg, DstReg))
1075  return false;
1076 
1077  bool SeenStore = true;
1078  if (!KillMI->isSafeToMove(AA, SeenStore))
1079  return false;
1080 
1081  SmallSet<unsigned, 2> Uses;
1082  SmallSet<unsigned, 2> Kills;
1083  SmallSet<unsigned, 2> Defs;
1084  SmallSet<unsigned, 2> LiveDefs;
1085  for (const MachineOperand &MO : KillMI->operands()) {
1086  if (!MO.isReg())
1087  continue;
1088  unsigned MOReg = MO.getReg();
1089  if (MO.isUse()) {
1090  if (!MOReg)
1091  continue;
1092  if (isDefTooClose(MOReg, DI->second, MI))
1093  return false;
1094  bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS));
1095  if (MOReg == Reg && !isKill)
1096  return false;
1097  Uses.insert(MOReg);
1098  if (isKill && MOReg != Reg)
1099  Kills.insert(MOReg);
1100  } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
1101  Defs.insert(MOReg);
1102  if (!MO.isDead())
1103  LiveDefs.insert(MOReg);
1104  }
1105  }
1106 
1107  // Check if the reschedule will not break depedencies.
1108  unsigned NumVisited = 0;
1109  for (MachineInstr &OtherMI :
1110  make_range(mi, MachineBasicBlock::iterator(KillMI))) {
1111  // DBG_VALUE cannot be counted against the limit.
1112  if (OtherMI.isDebugValue())
1113  continue;
1114  if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
1115  return false;
1116  ++NumVisited;
1117  if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
1118  OtherMI.isBranch() || OtherMI.isTerminator())
1119  // Don't move pass calls, etc.
1120  return false;
1121  SmallVector<unsigned, 2> OtherDefs;
1122  for (const MachineOperand &MO : OtherMI.operands()) {
1123  if (!MO.isReg())
1124  continue;
1125  unsigned MOReg = MO.getReg();
1126  if (!MOReg)
1127  continue;
1128  if (MO.isUse()) {
1129  if (Defs.count(MOReg))
1130  // Moving KillMI can clobber the physical register if the def has
1131  // not been seen.
1132  return false;
1133  if (Kills.count(MOReg))
1134  // Don't want to extend other live ranges and update kills.
1135  return false;
1136  if (&OtherMI != MI && MOReg == Reg &&
1137  !(MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS))))
1138  // We can't schedule across a use of the register in question.
1139  return false;
1140  } else {
1141  OtherDefs.push_back(MOReg);
1142  }
1143  }
1144 
1145  for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) {
1146  unsigned MOReg = OtherDefs[i];
1147  if (Uses.count(MOReg))
1148  return false;
1150  LiveDefs.count(MOReg))
1151  return false;
1152  // Physical register def is seen.
1153  Defs.erase(MOReg);
1154  }
1155  }
1156 
1157  // Move the old kill above MI, don't forget to move debug info as well.
1158  MachineBasicBlock::iterator InsertPos = mi;
1159  while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugValue())
1160  --InsertPos;
1161  MachineBasicBlock::iterator From = KillMI;
1162  MachineBasicBlock::iterator To = std::next(From);
1163  while (std::prev(From)->isDebugValue())
1164  --From;
1165  MBB->splice(InsertPos, MBB, From, To);
1166 
1167  nmi = std::prev(InsertPos); // Backtrack so we process the moved instr.
1168  DistanceMap.erase(DI);
1169 
1170  // Update live variables
1171  if (LIS) {
1172  LIS->handleMove(*KillMI);
1173  } else {
1174  LV->removeVirtualRegisterKilled(Reg, *KillMI);
1175  LV->addVirtualRegisterKilled(Reg, *MI);
1176  }
1177 
1178  DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1179  return true;
1180 }
1181 
1182 /// Tries to commute the operand 'BaseOpIdx' and some other operand in the
1183 /// given machine instruction to improve opportunities for coalescing and
1184 /// elimination of a register to register copy.
1185 ///
1186 /// 'DstOpIdx' specifies the index of MI def operand.
1187 /// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx'
1188 /// operand is killed by the given instruction.
1189 /// The 'Dist' arguments provides the distance of MI from the start of the
1190 /// current basic block and it is used to determine if it is profitable
1191 /// to commute operands in the instruction.
1192 ///
1193 /// Returns true if the transformation happened. Otherwise, returns false.
1194 bool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI,
1195  unsigned DstOpIdx,
1196  unsigned BaseOpIdx,
1197  bool BaseOpKilled,
1198  unsigned Dist) {
1199  if (!MI->isCommutable())
1200  return false;
1201 
1202  unsigned DstOpReg = MI->getOperand(DstOpIdx).getReg();
1203  unsigned BaseOpReg = MI->getOperand(BaseOpIdx).getReg();
1204  unsigned OpsNum = MI->getDesc().getNumOperands();
1205  unsigned OtherOpIdx = MI->getDesc().getNumDefs();
1206  for (; OtherOpIdx < OpsNum; OtherOpIdx++) {
1207  // The call of findCommutedOpIndices below only checks if BaseOpIdx
1208  // and OtherOpIdx are commutable, it does not really search for
1209  // other commutable operands and does not change the values of passed
1210  // variables.
1211  if (OtherOpIdx == BaseOpIdx || !MI->getOperand(OtherOpIdx).isReg() ||
1212  !TII->findCommutedOpIndices(*MI, BaseOpIdx, OtherOpIdx))
1213  continue;
1214 
1215  unsigned OtherOpReg = MI->getOperand(OtherOpIdx).getReg();
1216  bool AggressiveCommute = false;
1217 
1218  // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp
1219  // operands. This makes the live ranges of DstOp and OtherOp joinable.
1220  bool DoCommute =
1221  !BaseOpKilled && isKilled(*MI, OtherOpReg, MRI, TII, LIS, false);
1222 
1223  if (!DoCommute &&
1224  isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) {
1225  DoCommute = true;
1226  AggressiveCommute = true;
1227  }
1228 
1229  // If it's profitable to commute, try to do so.
1230  if (DoCommute && commuteInstruction(MI, DstOpIdx, BaseOpIdx, OtherOpIdx,
1231  Dist)) {
1232  ++NumCommuted;
1233  if (AggressiveCommute)
1234  ++NumAggrCommuted;
1235  return true;
1236  }
1237  }
1238  return false;
1239 }
1240 
1241 /// For the case where an instruction has a single pair of tied register
1242 /// operands, attempt some transformations that may either eliminate the tied
1243 /// operands or improve the opportunities for coalescing away the register copy.
1244 /// Returns true if no copy needs to be inserted to untie mi's operands
1245 /// (either because they were untied, or because mi was rescheduled, and will
1246 /// be visited again later). If the shouldOnlyCommute flag is true, only
1247 /// instruction commutation is attempted.
1248 bool TwoAddressInstructionPass::
1249 tryInstructionTransform(MachineBasicBlock::iterator &mi,
1251  unsigned SrcIdx, unsigned DstIdx,
1252  unsigned Dist, bool shouldOnlyCommute) {
1253  if (OptLevel == CodeGenOpt::None)
1254  return false;
1255 
1256  MachineInstr &MI = *mi;
1257  unsigned regA = MI.getOperand(DstIdx).getReg();
1258  unsigned regB = MI.getOperand(SrcIdx).getReg();
1259 
1261  "cannot make instruction into two-address form");
1262  bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true);
1263 
1265  scanUses(regA);
1266 
1267  bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist);
1268 
1269  // If the instruction is convertible to 3 Addr, instead
1270  // of returning try 3 Addr transformation aggresively and
1271  // use this variable to check later. Because it might be better.
1272  // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret`
1273  // instead of the following code.
1274  // addl %esi, %edi
1275  // movl %edi, %eax
1276  // ret
1277  if (Commuted && !MI.isConvertibleTo3Addr())
1278  return false;
1279 
1280  if (shouldOnlyCommute)
1281  return false;
1282 
1283  // If there is one more use of regB later in the same MBB, consider
1284  // re-schedule this MI below it.
1285  if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
1286  ++NumReSchedDowns;
1287  return true;
1288  }
1289 
1290  // If we commuted, regB may have changed so we should re-sample it to avoid
1291  // confusing the three address conversion below.
1292  if (Commuted) {
1293  regB = MI.getOperand(SrcIdx).getReg();
1294  regBKilled = isKilled(MI, regB, MRI, TII, LIS, true);
1295  }
1296 
1297  if (MI.isConvertibleTo3Addr()) {
1298  // This instruction is potentially convertible to a true
1299  // three-address instruction. Check if it is profitable.
1300  if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1301  // Try to convert it.
1302  if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
1303  ++NumConvertedTo3Addr;
1304  return true; // Done with this instruction.
1305  }
1306  }
1307  }
1308 
1309  // Return if it is commuted but 3 addr conversion is failed.
1310  if (Commuted)
1311  return false;
1312 
1313  // If there is one more use of regB later in the same MBB, consider
1314  // re-schedule it before this MI if it's legal.
1315  if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) {
1316  ++NumReSchedUps;
1317  return true;
1318  }
1319 
1320  // If this is an instruction with a load folded into it, try unfolding
1321  // the load, e.g. avoid this:
1322  // movq %rdx, %rcx
1323  // addq (%rax), %rcx
1324  // in favor of this:
1325  // movq (%rax), %rcx
1326  // addq %rdx, %rcx
1327  // because it's preferable to schedule a load than a register copy.
1328  if (MI.mayLoad() && !regBKilled) {
1329  // Determine if a load can be unfolded.
1330  unsigned LoadRegIndex;
1331  unsigned NewOpc =
1333  /*UnfoldLoad=*/true,
1334  /*UnfoldStore=*/false,
1335  &LoadRegIndex);
1336  if (NewOpc != 0) {
1337  const MCInstrDesc &UnfoldMCID = TII->get(NewOpc);
1338  if (UnfoldMCID.getNumDefs() == 1) {
1339  // Unfold the load.
1340  DEBUG(dbgs() << "2addr: UNFOLDING: " << MI);
1341  const TargetRegisterClass *RC =
1342  TRI->getAllocatableClass(
1343  TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF));
1344  unsigned Reg = MRI->createVirtualRegister(RC);
1346  if (!TII->unfoldMemoryOperand(*MF, MI, Reg,
1347  /*UnfoldLoad=*/true,
1348  /*UnfoldStore=*/false, NewMIs)) {
1349  DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1350  return false;
1351  }
1352  assert(NewMIs.size() == 2 &&
1353  "Unfolded a load into multiple instructions!");
1354  // The load was previously folded, so this is the only use.
1355  NewMIs[1]->addRegisterKilled(Reg, TRI);
1356 
1357  // Tentatively insert the instructions into the block so that they
1358  // look "normal" to the transformation logic.
1359  MBB->insert(mi, NewMIs[0]);
1360  MBB->insert(mi, NewMIs[1]);
1361 
1362  DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0]
1363  << "2addr: NEW INST: " << *NewMIs[1]);
1364 
1365  // Transform the instruction, now that it no longer has a load.
1366  unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA);
1367  unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB);
1368  MachineBasicBlock::iterator NewMI = NewMIs[1];
1369  bool TransformResult =
1370  tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true);
1371  (void)TransformResult;
1372  assert(!TransformResult &&
1373  "tryInstructionTransform() should return false.");
1374  if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1375  // Success, or at least we made an improvement. Keep the unfolded
1376  // instructions and discard the original.
1377  if (LV) {
1378  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1379  MachineOperand &MO = MI.getOperand(i);
1380  if (MO.isReg() &&
1382  if (MO.isUse()) {
1383  if (MO.isKill()) {
1384  if (NewMIs[0]->killsRegister(MO.getReg()))
1385  LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[0]);
1386  else {
1387  assert(NewMIs[1]->killsRegister(MO.getReg()) &&
1388  "Kill missing after load unfold!");
1389  LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[1]);
1390  }
1391  }
1392  } else if (LV->removeVirtualRegisterDead(MO.getReg(), MI)) {
1393  if (NewMIs[1]->registerDefIsDead(MO.getReg()))
1394  LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[1]);
1395  else {
1396  assert(NewMIs[0]->registerDefIsDead(MO.getReg()) &&
1397  "Dead flag missing after load unfold!");
1398  LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[0]);
1399  }
1400  }
1401  }
1402  }
1403  LV->addVirtualRegisterKilled(Reg, *NewMIs[1]);
1404  }
1405 
1406  SmallVector<unsigned, 4> OrigRegs;
1407  if (LIS) {
1408  for (const MachineOperand &MO : MI.operands()) {
1409  if (MO.isReg())
1410  OrigRegs.push_back(MO.getReg());
1411  }
1412  }
1413 
1414  MI.eraseFromParent();
1415 
1416  // Update LiveIntervals.
1417  if (LIS) {
1418  MachineBasicBlock::iterator Begin(NewMIs[0]);
1419  MachineBasicBlock::iterator End(NewMIs[1]);
1420  LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1421  }
1422 
1423  mi = NewMIs[1];
1424  } else {
1425  // Transforming didn't eliminate the tie and didn't lead to an
1426  // improvement. Clean up the unfolded instructions and keep the
1427  // original.
1428  DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1429  NewMIs[0]->eraseFromParent();
1430  NewMIs[1]->eraseFromParent();
1431  }
1432  }
1433  }
1434  }
1435 
1436  return false;
1437 }
1438 
1439 // Collect tied operands of MI that need to be handled.
1440 // Rewrite trivial cases immediately.
1441 // Return true if any tied operands where found, including the trivial ones.
1442 bool TwoAddressInstructionPass::
1443 collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
1444  const MCInstrDesc &MCID = MI->getDesc();
1445  bool AnyOps = false;
1446  unsigned NumOps = MI->getNumOperands();
1447 
1448  for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1449  unsigned DstIdx = 0;
1450  if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1451  continue;
1452  AnyOps = true;
1453  MachineOperand &SrcMO = MI->getOperand(SrcIdx);
1454  MachineOperand &DstMO = MI->getOperand(DstIdx);
1455  unsigned SrcReg = SrcMO.getReg();
1456  unsigned DstReg = DstMO.getReg();
1457  // Tied constraint already satisfied?
1458  if (SrcReg == DstReg)
1459  continue;
1460 
1461  assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1462 
1463  // Deal with <undef> uses immediately - simply rewrite the src operand.
1464  if (SrcMO.isUndef() && !DstMO.getSubReg()) {
1465  // Constrain the DstReg register class if required.
1467  if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
1468  TRI, *MF))
1469  MRI->constrainRegClass(DstReg, RC);
1470  SrcMO.setReg(DstReg);
1471  SrcMO.setSubReg(0);
1472  DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1473  continue;
1474  }
1475  TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1476  }
1477  return AnyOps;
1478 }
1479 
1480 // Process a list of tied MI operands that all use the same source register.
1481 // The tied pairs are of the form (SrcIdx, DstIdx).
1482 void
1483 TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
1484  TiedPairList &TiedPairs,
1485  unsigned &Dist) {
1486  bool IsEarlyClobber = false;
1487  for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1488  const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second);
1489  IsEarlyClobber |= DstMO.isEarlyClobber();
1490  }
1491 
1492  bool RemovedKillFlag = false;
1493  bool AllUsesCopied = true;
1494  unsigned LastCopiedReg = 0;
1495  SlotIndex LastCopyIdx;
1496  unsigned RegB = 0;
1497  unsigned SubRegB = 0;
1498  for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) {
1499  unsigned SrcIdx = TiedPairs[tpi].first;
1500  unsigned DstIdx = TiedPairs[tpi].second;
1501 
1502  const MachineOperand &DstMO = MI->getOperand(DstIdx);
1503  unsigned RegA = DstMO.getReg();
1504 
1505  // Grab RegB from the instruction because it may have changed if the
1506  // instruction was commuted.
1507  RegB = MI->getOperand(SrcIdx).getReg();
1508  SubRegB = MI->getOperand(SrcIdx).getSubReg();
1509 
1510  if (RegA == RegB) {
1511  // The register is tied to multiple destinations (or else we would
1512  // not have continued this far), but this use of the register
1513  // already matches the tied destination. Leave it.
1514  AllUsesCopied = false;
1515  continue;
1516  }
1517  LastCopiedReg = RegA;
1518 
1520  "cannot make instruction into two-address form");
1521 
1522 #ifndef NDEBUG
1523  // First, verify that we don't have a use of "a" in the instruction
1524  // (a = b + a for example) because our transformation will not
1525  // work. This should never occur because we are in SSA form.
1526  for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1527  assert(i == DstIdx ||
1528  !MI->getOperand(i).isReg() ||
1529  MI->getOperand(i).getReg() != RegA);
1530 #endif
1531 
1532  // Emit a copy.
1533  MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1534  TII->get(TargetOpcode::COPY), RegA);
1535  // If this operand is folding a truncation, the truncation now moves to the
1536  // copy so that the register classes remain valid for the operands.
1537  MIB.addReg(RegB, 0, SubRegB);
1538  const TargetRegisterClass *RC = MRI->getRegClass(RegB);
1539  if (SubRegB) {
1541  assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA),
1542  SubRegB) &&
1543  "tied subregister must be a truncation");
1544  // The superreg class will not be used to constrain the subreg class.
1545  RC = nullptr;
1546  }
1547  else {
1548  assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB))
1549  && "tied subregister must be a truncation");
1550  }
1551  }
1552 
1553  // Update DistanceMap.
1555  --PrevMI;
1556  DistanceMap.insert(std::make_pair(&*PrevMI, Dist));
1557  DistanceMap[MI] = ++Dist;
1558 
1559  if (LIS) {
1560  LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot();
1561 
1563  LiveInterval &LI = LIS->getInterval(RegA);
1564  VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1565  SlotIndex endIdx =
1566  LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber);
1567  LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI));
1568  }
1569  }
1570 
1571  DEBUG(dbgs() << "\t\tprepend:\t" << *MIB);
1572 
1573  MachineOperand &MO = MI->getOperand(SrcIdx);
1574  assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1575  "inconsistent operand info for 2-reg pass");
1576  if (MO.isKill()) {
1577  MO.setIsKill(false);
1578  RemovedKillFlag = true;
1579  }
1580 
1581  // Make sure regA is a legal regclass for the SrcIdx operand.
1584  MRI->constrainRegClass(RegA, RC);
1585  MO.setReg(RegA);
1586  // The getMatchingSuper asserts guarantee that the register class projected
1587  // by SubRegB is compatible with RegA with no subregister. So regardless of
1588  // whether the dest oper writes a subreg, the source oper should not.
1589  MO.setSubReg(0);
1590 
1591  // Propagate SrcRegMap.
1592  SrcRegMap[RegA] = RegB;
1593  }
1594 
1595  if (AllUsesCopied) {
1596  if (!IsEarlyClobber) {
1597  // Replace other (un-tied) uses of regB with LastCopiedReg.
1598  for (MachineOperand &MO : MI->operands()) {
1599  if (MO.isReg() && MO.getReg() == RegB &&
1600  MO.isUse()) {
1601  if (MO.isKill()) {
1602  MO.setIsKill(false);
1603  RemovedKillFlag = true;
1604  }
1605  MO.setReg(LastCopiedReg);
1606  MO.setSubReg(MO.getSubReg());
1607  }
1608  }
1609  }
1610 
1611  // Update live variables for regB.
1612  if (RemovedKillFlag && LV && LV->getVarInfo(RegB).removeKill(*MI)) {
1614  --PrevMI;
1615  LV->addVirtualRegisterKilled(RegB, *PrevMI);
1616  }
1617 
1618  // Update LiveIntervals.
1619  if (LIS) {
1620  LiveInterval &LI = LIS->getInterval(RegB);
1621  SlotIndex MIIdx = LIS->getInstructionIndex(*MI);
1622  LiveInterval::const_iterator I = LI.find(MIIdx);
1623  assert(I != LI.end() && "RegB must be live-in to use.");
1624 
1625  SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber);
1626  if (I->end == UseIdx)
1627  LI.removeSegment(LastCopyIdx, UseIdx);
1628  }
1629  } else if (RemovedKillFlag) {
1630  // Some tied uses of regB matched their destination registers, so
1631  // regB is still used in this instruction, but a kill flag was
1632  // removed from a different tied use of regB, so now we need to add
1633  // a kill flag to one of the remaining uses of regB.
1634  for (MachineOperand &MO : MI->operands()) {
1635  if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1636  MO.setIsKill(true);
1637  break;
1638  }
1639  }
1640  }
1641 }
1642 
1643 /// Reduce two-address instructions to two operands.
1644 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
1645  MF = &Func;
1646  const TargetMachine &TM = MF->getTarget();
1647  MRI = &MF->getRegInfo();
1648  TII = MF->getSubtarget().getInstrInfo();
1649  TRI = MF->getSubtarget().getRegisterInfo();
1650  InstrItins = MF->getSubtarget().getInstrItineraryData();
1651  LV = getAnalysisIfAvailable<LiveVariables>();
1652  LIS = getAnalysisIfAvailable<LiveIntervals>();
1653  if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>())
1654  AA = &AAPass->getAAResults();
1655  else
1656  AA = nullptr;
1657  OptLevel = TM.getOptLevel();
1658 
1659  bool MadeChange = false;
1660 
1661  DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1662  DEBUG(dbgs() << "********** Function: "
1663  << MF->getName() << '\n');
1664 
1665  // This pass takes the function out of SSA form.
1666  MRI->leaveSSA();
1667 
1668  TiedOperandMap TiedOperands;
1669  for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
1670  MBBI != MBBE; ++MBBI) {
1671  MBB = &*MBBI;
1672  unsigned Dist = 0;
1673  DistanceMap.clear();
1674  SrcRegMap.clear();
1675  DstRegMap.clear();
1676  Processed.clear();
1677  for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1678  mi != me; ) {
1679  MachineBasicBlock::iterator nmi = std::next(mi);
1680  if (mi->isDebugValue()) {
1681  mi = nmi;
1682  continue;
1683  }
1684 
1685  // Expand REG_SEQUENCE instructions. This will position mi at the first
1686  // expanded instruction.
1687  if (mi->isRegSequence())
1688  eliminateRegSequence(mi);
1689 
1690  DistanceMap.insert(std::make_pair(&*mi, ++Dist));
1691 
1692  processCopy(&*mi);
1693 
1694  // First scan through all the tied register uses in this instruction
1695  // and record a list of pairs of tied operands for each register.
1696  if (!collectTiedOperands(&*mi, TiedOperands)) {
1697  mi = nmi;
1698  continue;
1699  }
1700 
1701  ++NumTwoAddressInstrs;
1702  MadeChange = true;
1703  DEBUG(dbgs() << '\t' << *mi);
1704 
1705  // If the instruction has a single pair of tied operands, try some
1706  // transformations that may either eliminate the tied operands or
1707  // improve the opportunities for coalescing away the register copy.
1708  if (TiedOperands.size() == 1) {
1710  = TiedOperands.begin()->second;
1711  if (TiedPairs.size() == 1) {
1712  unsigned SrcIdx = TiedPairs[0].first;
1713  unsigned DstIdx = TiedPairs[0].second;
1714  unsigned SrcReg = mi->getOperand(SrcIdx).getReg();
1715  unsigned DstReg = mi->getOperand(DstIdx).getReg();
1716  if (SrcReg != DstReg &&
1717  tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) {
1718  // The tied operands have been eliminated or shifted further down
1719  // the block to ease elimination. Continue processing with 'nmi'.
1720  TiedOperands.clear();
1721  mi = nmi;
1722  continue;
1723  }
1724  }
1725  }
1726 
1727  // Now iterate over the information collected above.
1728  for (auto &TO : TiedOperands) {
1729  processTiedPairs(&*mi, TO.second, Dist);
1730  DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1731  }
1732 
1733  // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1734  if (mi->isInsertSubreg()) {
1735  // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1736  // To %reg:subidx = COPY %subreg
1737  unsigned SubIdx = mi->getOperand(3).getImm();
1738  mi->RemoveOperand(3);
1739  assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1740  mi->getOperand(0).setSubReg(SubIdx);
1741  mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1742  mi->RemoveOperand(1);
1743  mi->setDesc(TII->get(TargetOpcode::COPY));
1744  DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1745  }
1746 
1747  // Clear TiedOperands here instead of at the top of the loop
1748  // since most instructions do not have tied operands.
1749  TiedOperands.clear();
1750  mi = nmi;
1751  }
1752  }
1753 
1754  if (LIS)
1755  MF->verify(this, "After two-address instruction pass");
1756 
1757  return MadeChange;
1758 }
1759 
1760 /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1761 ///
1762 /// The instruction is turned into a sequence of sub-register copies:
1763 ///
1764 /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1765 ///
1766 /// Becomes:
1767 ///
1768 /// %dst:ssub0<def,undef> = COPY %v1
1769 /// %dst:ssub1<def> = COPY %v2
1770 void TwoAddressInstructionPass::
1771 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1772  MachineInstr &MI = *MBBI;
1773  unsigned DstReg = MI.getOperand(0).getReg();
1774  if (MI.getOperand(0).getSubReg() ||
1776  !(MI.getNumOperands() & 1)) {
1777  DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI);
1778  llvm_unreachable(nullptr);
1779  }
1780 
1781  SmallVector<unsigned, 4> OrigRegs;
1782  if (LIS) {
1783  OrigRegs.push_back(MI.getOperand(0).getReg());
1784  for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2)
1785  OrigRegs.push_back(MI.getOperand(i).getReg());
1786  }
1787 
1788  bool DefEmitted = false;
1789  for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
1790  MachineOperand &UseMO = MI.getOperand(i);
1791  unsigned SrcReg = UseMO.getReg();
1792  unsigned SubIdx = MI.getOperand(i+1).getImm();
1793  // Nothing needs to be inserted for <undef> operands.
1794  if (UseMO.isUndef())
1795  continue;
1796 
1797  // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1798  // might insert a COPY that uses SrcReg after is was killed.
1799  bool isKill = UseMO.isKill();
1800  if (isKill)
1801  for (unsigned j = i + 2; j < e; j += 2)
1802  if (MI.getOperand(j).getReg() == SrcReg) {
1803  MI.getOperand(j).setIsKill();
1804  UseMO.setIsKill(false);
1805  isKill = false;
1806  break;
1807  }
1808 
1809  // Insert the sub-register copy.
1810  MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
1811  TII->get(TargetOpcode::COPY))
1812  .addReg(DstReg, RegState::Define, SubIdx)
1813  .add(UseMO);
1814 
1815  // The first def needs an <undef> flag because there is no live register
1816  // before it.
1817  if (!DefEmitted) {
1818  CopyMI->getOperand(0).setIsUndef(true);
1819  // Return an iterator pointing to the first inserted instr.
1820  MBBI = CopyMI;
1821  }
1822  DefEmitted = true;
1823 
1824  // Update LiveVariables' kill info.
1825  if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg))
1826  LV->replaceKillInstruction(SrcReg, MI, *CopyMI);
1827 
1828  DEBUG(dbgs() << "Inserted: " << *CopyMI);
1829  }
1830 
1831  MachineBasicBlock::iterator EndMBBI =
1832  std::next(MachineBasicBlock::iterator(MI));
1833 
1834  if (!DefEmitted) {
1835  DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF");
1836  MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1837  for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j)
1838  MI.RemoveOperand(j);
1839  } else {
1840  DEBUG(dbgs() << "Eliminated: " << MI);
1841  MI.eraseFromParent();
1842  }
1843 
1844  // Udpate LiveIntervals.
1845  if (LIS)
1846  LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
1847 }
bool removeVirtualRegisterKilled(unsigned reg, MachineInstr &MI)
removeVirtualRegisterKilled - Remove the specified kill of the virtual register from the live variabl...
void push_back(const T &Elt)
Definition: SmallVector.h:212
const MachineInstrBuilder & add(const MachineOperand &MO) const
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:458
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static MachineInstr * getSingleDef(unsigned Reg, MachineBasicBlock *BB, const MachineRegisterInfo *MRI)
Return the MachineInstr* if it is the single def of the Reg in current BB.
static unsigned getMappedReg(unsigned Reg, DenseMap< unsigned, unsigned > &RegMap)
Return the physical register the specified virtual register might be mapped to.
static bool isKilled(MachineInstr &MI, unsigned Reg, const MachineRegisterInfo *MRI, const TargetInstrInfo *TII, LiveIntervals *LIS, bool allowFalsePositives)
Test if the given register value, which is used by the given instruction, is killed by the given inst...
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned createVirtualRegister(const TargetRegisterClass *RegClass)
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
bool isSubregToReg() const
Definition: MachineInstr.h:845
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:268
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
iterator_range< use_nodbg_iterator > use_nodbg_operands(unsigned Reg) const
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getReg() const
getReg - Returns the register number.
void setIsUndef(bool Val=true)
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
MachineOperand * findRegisterUseOperand(unsigned Reg, bool isKill=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterUseOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
Definition: MachineInstr.h:989
MachineInstr * commuteInstruction(MachineInstr &MI, bool NewMI=false, unsigned OpIdx1=CommuteAnyOperandIndex, unsigned OpIdx2=CommuteAnyOperandIndex) const
This method commutes the operands of the given machine instruction MI.
unsigned getSubReg() const
static cl::opt< bool > EnableRescheduling("twoaddr-reschedule", cl::desc("Coalesce copies by rescheduling (default=true)"), cl::init(true), cl::Hidden)
iterator_range< reg_iterator > reg_operands(unsigned Reg) const
unsigned second
STATISTIC(NumFunctions, "Total number of functions")
bool removeVirtualRegisterDead(unsigned reg, MachineInstr &MI)
removeVirtualRegisterDead - Remove the specified kill of the virtual register from the live variable ...
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:332
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Definition: MachineInstr.h:871
bool erase(const T &V)
Definition: SmallSet.h:108
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
Definition: LiveVariables.h:94
bool isEarlyClobber() const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
bool isNotInMIMap(const MachineInstr &Instr) const
Returns true if the specified machine instr has been removed or was never entered in the map...
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:210
const HexagonInstrInfo * TII
static bool regOverlapsSet(const SmallVectorImpl< unsigned > &Set, unsigned Reg, const TargetRegisterInfo *TRI)
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
iterator end()
Definition: LiveInterval.h:212
VNInfo::Allocator & getVNInfoAllocator()
virtual bool unfoldMemoryOperand(MachineFunction &MF, MachineInstr &MI, unsigned Reg, bool UnfoldLoad, bool UnfoldStore, SmallVectorImpl< MachineInstr *> &NewMIs) const
unfoldMemoryOperand - Separate a single instruction which folded a load or a store or a load and a st...
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
Reg
All possible values of the reg field in the ModR/M byte.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:474
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:290
void initializeTwoAddressInstructionPassPass(PassRegistry &)
virtual MachineInstr * convertToThreeAddress(MachineFunction::iterator &MFI, MachineInstr &MI, LiveVariables *LV) const
This method must be implemented by targets that set the M_CONVERTIBLE_TO_3_ADDR flag.
def_iterator def_begin(unsigned RegNo) const
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
void RemoveOperand(unsigned i)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
MCInst const & instruction(MCInst const &MCB, size_t Index)
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
static bool regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI)
Return true if the two registers are equal or aliased.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:287
SlotIndexes pass.
Definition: SlotIndexes.h:331
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
Definition: SlotIndexes.h:255
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
virtual unsigned getInstrLatency(const InstrItineraryData *ItinData, const MachineInstr &MI, unsigned *PredCost=nullptr) const
Compute the instruction latency of a given instruction.
const TargetRegisterClass * getRegClass(const MCInstrDesc &TID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum...
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
#define DEBUG_TYPE
AnalysisUsage & addPreservedID(const void *ID)
Itinerary data supplied by a subtarget to be used by a target.
virtual const TargetInstrInfo * getInstrInfo() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:482
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
virtual const InstrItineraryData * getInstrItineraryData() const
getInstrItineraryData - Returns instruction itinerary data for the target or specific subtarget...
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
bool erase(const KeyT &Val)
Definition: DenseMap.h:268
MachineInstrBundleIterator< MachineInstr > iterator
bool isConvertibleTo3Addr(QueryType Type=IgnoreBundle) const
Return true if this is a 2-address instruction which can be changed into a 3-address instruction if n...
Definition: MachineInstr.h:685
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
CodeGenOpt::Level getOptLevel() const
Returns the optimization level: None, Less, Default, or Aggressive.
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineInstrBuilder & UseMI
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Two Address instruction pass
Represent the analysis usage information of a pass.
static const unsigned End
bool isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx=nullptr) const
Return true if the use operand of the specified index is tied to a def operand.
virtual const TargetRegisterClass * getMatchingSuperRegClass(const TargetRegisterClass *A, const TargetRegisterClass *B, unsigned Idx) const
Return a subclass of the specified register class A so that each register in it has a sub-register of...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
static MachineInstr * findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, MachineRegisterInfo *MRI, const TargetInstrInfo *TII, bool &IsCopy, unsigned &DstReg, bool &IsDstPhys)
Given a register, if has a single in-basic block use, return the use instruction if it&#39;s a copy or a ...
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< unsigned > OrigRegs)
Update live intervals for instructions in a range of iterators.
bool isCopy() const
Definition: MachineInstr.h:857
char & TwoAddressInstructionPassID
TwoAddressInstruction - This pass reduces two-address instructions to use two operands.
VarInfo & getVarInfo(unsigned RegIdx)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setIsKill(bool Val=true)
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Iterator for intrusive lists based on ilist_node.
void replaceKillInstruction(unsigned Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one...
static cl::opt< unsigned > MaxDataFlowEdge("dataflow-edge-limit", cl::Hidden, cl::init(3), cl::desc("Maximum number of dataflow edges to traverse when evaluating " "the benefit of commuting operands"))
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:198
bool regsOverlap(unsigned regA, unsigned regB) const
Returns true if the two registers are equal or alias each other.
static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, unsigned &SrcReg, unsigned &DstReg, bool &IsSrcPhys, bool &IsDstPhys)
Return true if the specified MI is a copy instruction or an extract_subreg instruction.
Segments::const_iterator const_iterator
Definition: LiveInterval.h:209
bool isDebugValue() const
Definition: MachineInstr.h:816
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool isInsertSubreg() const
Definition: MachineInstr.h:841
MachineInstrBuilder MachineInstrBuilder & DefMI
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:225
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
LiveInterval & getInterval(unsigned Reg)
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
int64_t getImm() const
virtual bool findCommutedOpIndices(MachineInstr &MI, unsigned &SrcOpIdx1, unsigned &SrcOpIdx2) const
Returns true iff the routine could find two commutable operands in the given machine instruction...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool hasAtLeastOneValue() const
Definition: LiveInterval.h:297
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, DEBUG_TYPE, "Two-Address instruction pass", false, false) INITIALIZE_PASS_END(TwoAddressInstructionPass
Representation of each machine instruction.
Definition: MachineInstr.h:59
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
bool killsRegister(unsigned Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr kills the specified register.
Definition: MachineInstr.h:948
void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr &MI, bool AddIfNotFound=false)
addVirtualRegisterDead - Add information about the fact that the specified register is dead after bei...
bool hasOneUse(unsigned RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, const TargetRegisterClass *RC) const
Return a super-register of the specified register Reg so its sub-register of index SubIdx is Reg...
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
void setSubReg(unsigned subReg)
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug instruction using the specified regis...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Two Address instruction static false bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS)
Test if the given register value, which is used by the given instruction, is killed by the given inst...
iterator begin()
Definition: LiveInterval.h:211
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:319
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:626
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static def_iterator def_end()
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
use_instr_nodbg_iterator use_instr_nodbg_begin(unsigned RegNo) const
const TargetRegisterClass * getAllocatableClass(const TargetRegisterClass *RC) const
Return the maximal subclass of the given register class that is allocatable or NULL.
iterator_range< def_instr_iterator > def_instructions(unsigned Reg) const
#define DEBUG(X)
Definition: Debug.h:118
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:57
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
virtual unsigned getOpcodeAfterMemoryUnfold(unsigned Opc, bool UnfoldLoad, bool UnfoldStore, unsigned *LoadRegIndex=nullptr) const
Returns the opcode of the would be new instruction after load / store are unfolded from an instructio...
bool isSafeToMove(AliasAnalysis *AA, bool &SawStore) const
Return true if it is safe to move this instruction.
bool isCommutable(QueryType Type=IgnoreBundle) const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z, ..."), which produces the same result if Y and Z are exchanged.
Definition: MachineInstr.h:667
void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr &MI, bool AddIfNotFound=false)
addVirtualRegisterKilled - Add information about the fact that the specified register is killed after...
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block...
static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg)
Return true if the specified MI uses the specified register as a two-address use. ...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:65