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