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