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