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