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