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