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