LLVM  13.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  // Since there are no intervening uses for both registers, then commute
531  // if the def of RegC is closer. Its live interval is shorter.
532  return LastDefB && LastDefC && LastDefC > LastDefB;
533 }
534 
535 /// Commute a two-address instruction and update the basic block, distance map,
536 /// and live variables if needed. Return true if it is successful.
537 bool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI,
538  unsigned DstIdx,
539  unsigned RegBIdx,
540  unsigned RegCIdx,
541  unsigned Dist) {
542  Register RegC = MI->getOperand(RegCIdx).getReg();
543  LLVM_DEBUG(dbgs() << "2addr: COMMUTING : " << *MI);
544  MachineInstr *NewMI = TII->commuteInstruction(*MI, false, RegBIdx, RegCIdx);
545 
546  if (NewMI == nullptr) {
547  LLVM_DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
548  return false;
549  }
550 
551  LLVM_DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
552  assert(NewMI == MI &&
553  "TargetInstrInfo::commuteInstruction() should not return a new "
554  "instruction unless it was requested.");
555 
556  // Update source register map.
557  MCRegister FromRegC = getMappedReg(RegC, SrcRegMap);
558  if (FromRegC) {
559  Register RegA = MI->getOperand(DstIdx).getReg();
560  SrcRegMap[RegA] = FromRegC;
561  }
562 
563  return true;
564 }
565 
566 /// Return true if it is profitable to convert the given 2-address instruction
567 /// to a 3-address one.
568 bool TwoAddressInstructionPass::isProfitableToConv3Addr(Register RegA,
569  Register RegB) {
570  // Look for situations like this:
571  // %reg1024 = MOV r1
572  // %reg1025 = MOV r0
573  // %reg1026 = ADD %reg1024, %reg1025
574  // r2 = MOV %reg1026
575  // Turn ADD into a 3-address instruction to avoid a copy.
576  MCRegister FromRegB = getMappedReg(RegB, SrcRegMap);
577  if (!FromRegB)
578  return false;
579  MCRegister ToRegA = getMappedReg(RegA, DstRegMap);
580  return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI));
581 }
582 
583 /// Convert the specified two-address instruction into a three address one.
584 /// Return true if this transformation was successful.
585 bool TwoAddressInstructionPass::convertInstTo3Addr(
587  Register RegA, Register RegB, unsigned Dist) {
588  // FIXME: Why does convertToThreeAddress() need an iterator reference?
590  MachineInstr *NewMI = TII->convertToThreeAddress(MFI, *mi, LV);
591  assert(MBB->getIterator() == MFI &&
592  "convertToThreeAddress changed iterator reference");
593  if (!NewMI)
594  return false;
595 
596  LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
597  LLVM_DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI);
598 
599  if (LIS)
600  LIS->ReplaceMachineInstrInMaps(*mi, *NewMI);
601 
602  // If the old instruction is debug value tracked, an update is required.
603  if (auto OldInstrNum = mi->peekDebugInstrNum()) {
604  // Sanity check.
605  assert(mi->getNumExplicitDefs() == 1);
606  assert(NewMI->getNumExplicitDefs() == 1);
607 
608  // Find the old and new def location.
609  auto OldIt = mi->defs().begin();
610  auto NewIt = NewMI->defs().begin();
611  unsigned OldIdx = mi->getOperandNo(OldIt);
612  unsigned NewIdx = NewMI->getOperandNo(NewIt);
613 
614  // Record that one def has been replaced by the other.
615  unsigned NewInstrNum = NewMI->getDebugInstrNum();
616  MF->makeDebugValueSubstitution(std::make_pair(OldInstrNum, OldIdx),
617  std::make_pair(NewInstrNum, NewIdx));
618  }
619 
620  MBB->erase(mi); // Nuke the old inst.
621 
622  DistanceMap.insert(std::make_pair(NewMI, Dist));
623  mi = NewMI;
624  nmi = std::next(mi);
625 
626  // Update source and destination register maps.
627  SrcRegMap.erase(RegA);
628  DstRegMap.erase(RegB);
629  return true;
630 }
631 
632 /// Scan forward recursively for only uses, update maps if the use is a copy or
633 /// a two-address instruction.
634 void TwoAddressInstructionPass::scanUses(Register DstReg) {
635  SmallVector<Register, 4> VirtRegPairs;
636  bool IsDstPhys;
637  bool IsCopy = false;
638  Register NewReg;
639  Register Reg = DstReg;
640  while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy,
641  NewReg, IsDstPhys)) {
642  if (IsCopy && !Processed.insert(UseMI).second)
643  break;
644 
646  if (DI != DistanceMap.end())
647  // Earlier in the same MBB.Reached via a back edge.
648  break;
649 
650  if (IsDstPhys) {
651  VirtRegPairs.push_back(NewReg);
652  break;
653  }
654  bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second;
655  if (!isNew)
656  assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!");
657  VirtRegPairs.push_back(NewReg);
658  Reg = NewReg;
659  }
660 
661  if (!VirtRegPairs.empty()) {
662  unsigned ToReg = VirtRegPairs.back();
663  VirtRegPairs.pop_back();
664  while (!VirtRegPairs.empty()) {
665  unsigned FromReg = VirtRegPairs.back();
666  VirtRegPairs.pop_back();
667  bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
668  if (!isNew)
669  assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
670  ToReg = FromReg;
671  }
672  bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second;
673  if (!isNew)
674  assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
675  }
676 }
677 
678 /// If the specified instruction is not yet processed, process it if it's a
679 /// copy. For a copy instruction, we find the physical registers the
680 /// source and destination registers might be mapped to. These are kept in
681 /// point-to maps used to determine future optimizations. e.g.
682 /// v1024 = mov r0
683 /// v1025 = mov r1
684 /// v1026 = add v1024, v1025
685 /// r1 = mov r1026
686 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially
687 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
688 /// potentially joined with r1 on the output side. It's worthwhile to commute
689 /// 'add' to eliminate a copy.
690 void TwoAddressInstructionPass::processCopy(MachineInstr *MI) {
691  if (Processed.count(MI))
692  return;
693 
694  bool IsSrcPhys, IsDstPhys;
695  Register SrcReg, DstReg;
696  if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
697  return;
698 
699  if (IsDstPhys && !IsSrcPhys) {
700  DstRegMap.insert(std::make_pair(SrcReg, DstReg));
701  } else if (!IsDstPhys && IsSrcPhys) {
702  bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
703  if (!isNew)
704  assert(SrcRegMap[DstReg] == SrcReg &&
705  "Can't map to two src physical registers!");
706 
707  scanUses(DstReg);
708  }
709 
710  Processed.insert(MI);
711 }
712 
713 /// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
714 /// consider moving the instruction below the kill instruction in order to
715 /// eliminate the need for the copy.
716 bool TwoAddressInstructionPass::rescheduleMIBelowKill(
718  Register Reg) {
719  // Bail immediately if we don't have LV or LIS available. We use them to find
720  // kills efficiently.
721  if (!LV && !LIS)
722  return false;
723 
724  MachineInstr *MI = &*mi;
726  if (DI == DistanceMap.end())
727  // Must be created from unfolded load. Don't waste time trying this.
728  return false;
729 
730  MachineInstr *KillMI = nullptr;
731  if (LIS) {
732  LiveInterval &LI = LIS->getInterval(Reg);
733  assert(LI.end() != LI.begin() &&
734  "Reg should not have empty live interval.");
735 
736  SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
737  LiveInterval::const_iterator I = LI.find(MBBEndIdx);
738  if (I != LI.end() && I->start < MBBEndIdx)
739  return false;
740 
741  --I;
742  KillMI = LIS->getInstructionFromIndex(I->end);
743  } else {
744  KillMI = LV->getVarInfo(Reg).findKill(MBB);
745  }
746  if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
747  // Don't mess with copies, they may be coalesced later.
748  return false;
749 
750  if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
751  KillMI->isBranch() || KillMI->isTerminator())
752  // Don't move pass calls, etc.
753  return false;
754 
755  Register DstReg;
756  if (isTwoAddrUse(*KillMI, Reg, DstReg))
757  return false;
758 
759  bool SeenStore = true;
760  if (!MI->isSafeToMove(AA, SeenStore))
761  return false;
762 
763  if (TII->getInstrLatency(InstrItins, *MI) > 1)
764  // FIXME: Needs more sophisticated heuristics.
765  return false;
766 
770  for (const MachineOperand &MO : MI->operands()) {
771  if (!MO.isReg())
772  continue;
773  Register MOReg = MO.getReg();
774  if (!MOReg)
775  continue;
776  if (MO.isDef())
777  Defs.push_back(MOReg);
778  else {
779  Uses.push_back(MOReg);
780  if (MOReg != Reg && (MO.isKill() ||
781  (LIS && isPlainlyKilled(MI, MOReg, LIS))))
782  Kills.push_back(MOReg);
783  }
784  }
785 
786  // Move the copies connected to MI down as well.
788  MachineBasicBlock::iterator AfterMI = std::next(Begin);
789  MachineBasicBlock::iterator End = AfterMI;
790  while (End != MBB->end()) {
791  End = skipDebugInstructionsForward(End, MBB->end());
792  if (End->isCopy() && regOverlapsSet(Defs, End->getOperand(1).getReg(), TRI))
793  Defs.push_back(End->getOperand(0).getReg());
794  else
795  break;
796  ++End;
797  }
798 
799  // Check if the reschedule will not break dependencies.
800  unsigned NumVisited = 0;
801  MachineBasicBlock::iterator KillPos = KillMI;
802  ++KillPos;
803  for (MachineInstr &OtherMI : make_range(End, KillPos)) {
804  // Debug or pseudo instructions cannot be counted against the limit.
805  if (OtherMI.isDebugOrPseudoInstr())
806  continue;
807  if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
808  return false;
809  ++NumVisited;
810  if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
811  OtherMI.isBranch() || OtherMI.isTerminator())
812  // Don't move pass calls, etc.
813  return false;
814  for (const MachineOperand &MO : OtherMI.operands()) {
815  if (!MO.isReg())
816  continue;
817  Register MOReg = MO.getReg();
818  if (!MOReg)
819  continue;
820  if (MO.isDef()) {
821  if (regOverlapsSet(Uses, MOReg, TRI))
822  // Physical register use would be clobbered.
823  return false;
824  if (!MO.isDead() && regOverlapsSet(Defs, MOReg, TRI))
825  // May clobber a physical register def.
826  // FIXME: This may be too conservative. It's ok if the instruction
827  // is sunken completely below the use.
828  return false;
829  } else {
830  if (regOverlapsSet(Defs, MOReg, TRI))
831  return false;
832  bool isKill =
833  MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS));
834  if (MOReg != Reg && ((isKill && regOverlapsSet(Uses, MOReg, TRI)) ||
835  regOverlapsSet(Kills, MOReg, TRI)))
836  // Don't want to extend other live ranges and update kills.
837  return false;
838  if (MOReg == Reg && !isKill)
839  // We can't schedule across a use of the register in question.
840  return false;
841  // Ensure that if this is register in question, its the kill we expect.
842  assert((MOReg != Reg || &OtherMI == KillMI) &&
843  "Found multiple kills of a register in a basic block");
844  }
845  }
846  }
847 
848  // Move debug info as well.
849  while (Begin != MBB->begin() && std::prev(Begin)->isDebugInstr())
850  --Begin;
851 
852  nmi = End;
853  MachineBasicBlock::iterator InsertPos = KillPos;
854  if (LIS) {
855  // We have to move the copies first so that the MBB is still well-formed
856  // when calling handleMove().
857  for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) {
858  auto CopyMI = MBBI++;
859  MBB->splice(InsertPos, MBB, CopyMI);
860  LIS->handleMove(*CopyMI);
861  InsertPos = CopyMI;
862  }
863  End = std::next(MachineBasicBlock::iterator(MI));
864  }
865 
866  // Copies following MI may have been moved as well.
867  MBB->splice(InsertPos, MBB, Begin, End);
868  DistanceMap.erase(DI);
869 
870  // Update live variables
871  if (LIS) {
872  LIS->handleMove(*MI);
873  } else {
874  LV->removeVirtualRegisterKilled(Reg, *KillMI);
876  }
877 
878  LLVM_DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI);
879  return true;
880 }
881 
882 /// Return true if the re-scheduling will put the given instruction too close
883 /// to the defs of its register dependencies.
884 bool TwoAddressInstructionPass::isDefTooClose(Register Reg, unsigned Dist,
885  MachineInstr *MI) {
887  if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike())
888  continue;
889  if (&DefMI == MI)
890  return true; // MI is defining something KillMI uses
892  if (DDI == DistanceMap.end())
893  return true; // Below MI
894  unsigned DefDist = DDI->second;
895  assert(Dist > DefDist && "Visited def already?");
896  if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
897  return true;
898  }
899  return false;
900 }
901 
902 /// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
903 /// consider moving the kill instruction above the current two-address
904 /// instruction in order to eliminate the need for the copy.
905 bool TwoAddressInstructionPass::rescheduleKillAboveMI(
907  Register Reg) {
908  // Bail immediately if we don't have LV or LIS available. We use them to find
909  // kills efficiently.
910  if (!LV && !LIS)
911  return false;
912 
913  MachineInstr *MI = &*mi;
915  if (DI == DistanceMap.end())
916  // Must be created from unfolded load. Don't waste time trying this.
917  return false;
918 
919  MachineInstr *KillMI = nullptr;
920  if (LIS) {
921  LiveInterval &LI = LIS->getInterval(Reg);
922  assert(LI.end() != LI.begin() &&
923  "Reg should not have empty live interval.");
924 
925  SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
926  LiveInterval::const_iterator I = LI.find(MBBEndIdx);
927  if (I != LI.end() && I->start < MBBEndIdx)
928  return false;
929 
930  --I;
931  KillMI = LIS->getInstructionFromIndex(I->end);
932  } else {
933  KillMI = LV->getVarInfo(Reg).findKill(MBB);
934  }
935  if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
936  // Don't mess with copies, they may be coalesced later.
937  return false;
938 
939  Register DstReg;
940  if (isTwoAddrUse(*KillMI, Reg, DstReg))
941  return false;
942 
943  bool SeenStore = true;
944  if (!KillMI->isSafeToMove(AA, SeenStore))
945  return false;
946 
950  SmallVector<Register, 2> LiveDefs;
951  for (const MachineOperand &MO : KillMI->operands()) {
952  if (!MO.isReg())
953  continue;
954  Register MOReg = MO.getReg();
955  if (MO.isUse()) {
956  if (!MOReg)
957  continue;
958  if (isDefTooClose(MOReg, DI->second, MI))
959  return false;
960  bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS));
961  if (MOReg == Reg && !isKill)
962  return false;
963  Uses.push_back(MOReg);
964  if (isKill && MOReg != Reg)
965  Kills.push_back(MOReg);
966  } else if (MOReg.isPhysical()) {
967  Defs.push_back(MOReg);
968  if (!MO.isDead())
969  LiveDefs.push_back(MOReg);
970  }
971  }
972 
973  // Check if the reschedule will not break depedencies.
974  unsigned NumVisited = 0;
975  for (MachineInstr &OtherMI :
977  // Debug or pseudo instructions cannot be counted against the limit.
978  if (OtherMI.isDebugOrPseudoInstr())
979  continue;
980  if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
981  return false;
982  ++NumVisited;
983  if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
984  OtherMI.isBranch() || OtherMI.isTerminator())
985  // Don't move pass calls, etc.
986  return false;
987  SmallVector<Register, 2> OtherDefs;
988  for (const MachineOperand &MO : OtherMI.operands()) {
989  if (!MO.isReg())
990  continue;
991  Register MOReg = MO.getReg();
992  if (!MOReg)
993  continue;
994  if (MO.isUse()) {
995  if (regOverlapsSet(Defs, MOReg, TRI))
996  // Moving KillMI can clobber the physical register if the def has
997  // not been seen.
998  return false;
999  if (regOverlapsSet(Kills, MOReg, TRI))
1000  // Don't want to extend other live ranges and update kills.
1001  return false;
1002  if (&OtherMI != MI && MOReg == Reg &&
1003  !(MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS))))
1004  // We can't schedule across a use of the register in question.
1005  return false;
1006  } else {
1007  OtherDefs.push_back(MOReg);
1008  }
1009  }
1010 
1011  for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) {
1012  Register MOReg = OtherDefs[i];
1013  if (regOverlapsSet(Uses, MOReg, TRI))
1014  return false;
1015  if (MOReg.isPhysical() && regOverlapsSet(LiveDefs, MOReg, TRI))
1016  return false;
1017  // Physical register def is seen.
1018  llvm::erase_value(Defs, MOReg);
1019  }
1020  }
1021 
1022  // Move the old kill above MI, don't forget to move debug info as well.
1023  MachineBasicBlock::iterator InsertPos = mi;
1024  while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugInstr())
1025  --InsertPos;
1027  MachineBasicBlock::iterator To = std::next(From);
1028  while (std::prev(From)->isDebugInstr())
1029  --From;
1030  MBB->splice(InsertPos, MBB, From, To);
1031 
1032  nmi = std::prev(InsertPos); // Backtrack so we process the moved instr.
1033  DistanceMap.erase(DI);
1034 
1035  // Update live variables
1036  if (LIS) {
1037  LIS->handleMove(*KillMI);
1038  } else {
1039  LV->removeVirtualRegisterKilled(Reg, *KillMI);
1041  }
1042 
1043  LLVM_DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1044  return true;
1045 }
1046 
1047 /// Tries to commute the operand 'BaseOpIdx' and some other operand in the
1048 /// given machine instruction to improve opportunities for coalescing and
1049 /// elimination of a register to register copy.
1050 ///
1051 /// 'DstOpIdx' specifies the index of MI def operand.
1052 /// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx'
1053 /// operand is killed by the given instruction.
1054 /// The 'Dist' arguments provides the distance of MI from the start of the
1055 /// current basic block and it is used to determine if it is profitable
1056 /// to commute operands in the instruction.
1057 ///
1058 /// Returns true if the transformation happened. Otherwise, returns false.
1059 bool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI,
1060  unsigned DstOpIdx,
1061  unsigned BaseOpIdx,
1062  bool BaseOpKilled,
1063  unsigned Dist) {
1064  if (!MI->isCommutable())
1065  return false;
1066 
1067  bool MadeChange = false;
1068  Register DstOpReg = MI->getOperand(DstOpIdx).getReg();
1069  Register BaseOpReg = MI->getOperand(BaseOpIdx).getReg();
1070  unsigned OpsNum = MI->getDesc().getNumOperands();
1071  unsigned OtherOpIdx = MI->getDesc().getNumDefs();
1072  for (; OtherOpIdx < OpsNum; OtherOpIdx++) {
1073  // The call of findCommutedOpIndices below only checks if BaseOpIdx
1074  // and OtherOpIdx are commutable, it does not really search for
1075  // other commutable operands and does not change the values of passed
1076  // variables.
1077  if (OtherOpIdx == BaseOpIdx || !MI->getOperand(OtherOpIdx).isReg() ||
1078  !TII->findCommutedOpIndices(*MI, BaseOpIdx, OtherOpIdx))
1079  continue;
1080 
1081  Register OtherOpReg = MI->getOperand(OtherOpIdx).getReg();
1082  bool AggressiveCommute = false;
1083 
1084  // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp
1085  // operands. This makes the live ranges of DstOp and OtherOp joinable.
1086  bool OtherOpKilled = isKilled(*MI, OtherOpReg, MRI, TII, LIS, false);
1087  bool DoCommute = !BaseOpKilled && OtherOpKilled;
1088 
1089  if (!DoCommute &&
1090  isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) {
1091  DoCommute = true;
1092  AggressiveCommute = true;
1093  }
1094 
1095  // If it's profitable to commute, try to do so.
1096  if (DoCommute && commuteInstruction(MI, DstOpIdx, BaseOpIdx, OtherOpIdx,
1097  Dist)) {
1098  MadeChange = true;
1099  ++NumCommuted;
1100  if (AggressiveCommute)
1101  ++NumAggrCommuted;
1102 
1103  // There might be more than two commutable operands, update BaseOp and
1104  // continue scanning.
1105  // FIXME: This assumes that the new instruction's operands are in the
1106  // same positions and were simply swapped.
1107  BaseOpReg = OtherOpReg;
1108  BaseOpKilled = OtherOpKilled;
1109  // Resamples OpsNum in case the number of operands was reduced. This
1110  // happens with X86.
1111  OpsNum = MI->getDesc().getNumOperands();
1112  }
1113  }
1114  return MadeChange;
1115 }
1116 
1117 /// For the case where an instruction has a single pair of tied register
1118 /// operands, attempt some transformations that may either eliminate the tied
1119 /// operands or improve the opportunities for coalescing away the register copy.
1120 /// Returns true if no copy needs to be inserted to untie mi's operands
1121 /// (either because they were untied, or because mi was rescheduled, and will
1122 /// be visited again later). If the shouldOnlyCommute flag is true, only
1123 /// instruction commutation is attempted.
1124 bool TwoAddressInstructionPass::
1125 tryInstructionTransform(MachineBasicBlock::iterator &mi,
1127  unsigned SrcIdx, unsigned DstIdx,
1128  unsigned Dist, bool shouldOnlyCommute) {
1129  if (OptLevel == CodeGenOpt::None)
1130  return false;
1131 
1132  MachineInstr &MI = *mi;
1133  Register regA = MI.getOperand(DstIdx).getReg();
1134  Register regB = MI.getOperand(SrcIdx).getReg();
1135 
1136  assert(regB.isVirtual() && "cannot make instruction into two-address form");
1137  bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true);
1138 
1139  if (regA.isVirtual())
1140  scanUses(regA);
1141 
1142  bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist);
1143 
1144  // If the instruction is convertible to 3 Addr, instead
1145  // of returning try 3 Addr transformation aggressively and
1146  // use this variable to check later. Because it might be better.
1147  // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret`
1148  // instead of the following code.
1149  // addl %esi, %edi
1150  // movl %edi, %eax
1151  // ret
1152  if (Commuted && !MI.isConvertibleTo3Addr())
1153  return false;
1154 
1155  if (shouldOnlyCommute)
1156  return false;
1157 
1158  // If there is one more use of regB later in the same MBB, consider
1159  // re-schedule this MI below it.
1160  if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
1161  ++NumReSchedDowns;
1162  return true;
1163  }
1164 
1165  // If we commuted, regB may have changed so we should re-sample it to avoid
1166  // confusing the three address conversion below.
1167  if (Commuted) {
1168  regB = MI.getOperand(SrcIdx).getReg();
1169  regBKilled = isKilled(MI, regB, MRI, TII, LIS, true);
1170  }
1171 
1172  if (MI.isConvertibleTo3Addr()) {
1173  // This instruction is potentially convertible to a true
1174  // three-address instruction. Check if it is profitable.
1175  if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1176  // Try to convert it.
1177  if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
1178  ++NumConvertedTo3Addr;
1179  return true; // Done with this instruction.
1180  }
1181  }
1182  }
1183 
1184  // Return if it is commuted but 3 addr conversion is failed.
1185  if (Commuted)
1186  return false;
1187 
1188  // If there is one more use of regB later in the same MBB, consider
1189  // re-schedule it before this MI if it's legal.
1190  if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) {
1191  ++NumReSchedUps;
1192  return true;
1193  }
1194 
1195  // If this is an instruction with a load folded into it, try unfolding
1196  // the load, e.g. avoid this:
1197  // movq %rdx, %rcx
1198  // addq (%rax), %rcx
1199  // in favor of this:
1200  // movq (%rax), %rcx
1201  // addq %rdx, %rcx
1202  // because it's preferable to schedule a load than a register copy.
1203  if (MI.mayLoad() && !regBKilled) {
1204  // Determine if a load can be unfolded.
1205  unsigned LoadRegIndex;
1206  unsigned NewOpc =
1207  TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
1208  /*UnfoldLoad=*/true,
1209  /*UnfoldStore=*/false,
1210  &LoadRegIndex);
1211  if (NewOpc != 0) {
1212  const MCInstrDesc &UnfoldMCID = TII->get(NewOpc);
1213  if (UnfoldMCID.getNumDefs() == 1) {
1214  // Unfold the load.
1215  LLVM_DEBUG(dbgs() << "2addr: UNFOLDING: " << MI);
1216  const TargetRegisterClass *RC =
1218  TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF));
1221  if (!TII->unfoldMemoryOperand(*MF, MI, Reg,
1222  /*UnfoldLoad=*/true,
1223  /*UnfoldStore=*/false, NewMIs)) {
1224  LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1225  return false;
1226  }
1227  assert(NewMIs.size() == 2 &&
1228  "Unfolded a load into multiple instructions!");
1229  // The load was previously folded, so this is the only use.
1230  NewMIs[1]->addRegisterKilled(Reg, TRI);
1231 
1232  // Tentatively insert the instructions into the block so that they
1233  // look "normal" to the transformation logic.
1234  MBB->insert(mi, NewMIs[0]);
1235  MBB->insert(mi, NewMIs[1]);
1236 
1237  LLVM_DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0]
1238  << "2addr: NEW INST: " << *NewMIs[1]);
1239 
1240  // Transform the instruction, now that it no longer has a load.
1241  unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA);
1242  unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB);
1243  MachineBasicBlock::iterator NewMI = NewMIs[1];
1244  bool TransformResult =
1245  tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true);
1246  (void)TransformResult;
1247  assert(!TransformResult &&
1248  "tryInstructionTransform() should return false.");
1249  if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1250  // Success, or at least we made an improvement. Keep the unfolded
1251  // instructions and discard the original.
1252  if (LV) {
1253  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1254  MachineOperand &MO = MI.getOperand(i);
1255  if (MO.isReg() && MO.getReg().isVirtual()) {
1256  if (MO.isUse()) {
1257  if (MO.isKill()) {
1258  if (NewMIs[0]->killsRegister(MO.getReg()))
1259  LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[0]);
1260  else {
1261  assert(NewMIs[1]->killsRegister(MO.getReg()) &&
1262  "Kill missing after load unfold!");
1263  LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[1]);
1264  }
1265  }
1266  } else if (LV->removeVirtualRegisterDead(MO.getReg(), MI)) {
1267  if (NewMIs[1]->registerDefIsDead(MO.getReg()))
1268  LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[1]);
1269  else {
1270  assert(NewMIs[0]->registerDefIsDead(MO.getReg()) &&
1271  "Dead flag missing after load unfold!");
1272  LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[0]);
1273  }
1274  }
1275  }
1276  }
1277  LV->addVirtualRegisterKilled(Reg, *NewMIs[1]);
1278  }
1279 
1280  SmallVector<Register, 4> OrigRegs;
1281  if (LIS) {
1282  for (const MachineOperand &MO : MI.operands()) {
1283  if (MO.isReg())
1284  OrigRegs.push_back(MO.getReg());
1285  }
1286  }
1287 
1288  MI.eraseFromParent();
1289 
1290  // Update LiveIntervals.
1291  if (LIS) {
1292  MachineBasicBlock::iterator Begin(NewMIs[0]);
1293  MachineBasicBlock::iterator End(NewMIs[1]);
1294  LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1295  }
1296 
1297  mi = NewMIs[1];
1298  } else {
1299  // Transforming didn't eliminate the tie and didn't lead to an
1300  // improvement. Clean up the unfolded instructions and keep the
1301  // original.
1302  LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1303  NewMIs[0]->eraseFromParent();
1304  NewMIs[1]->eraseFromParent();
1305  }
1306  }
1307  }
1308  }
1309 
1310  return false;
1311 }
1312 
1313 // Collect tied operands of MI that need to be handled.
1314 // Rewrite trivial cases immediately.
1315 // Return true if any tied operands where found, including the trivial ones.
1316 bool TwoAddressInstructionPass::
1317 collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
1318  const MCInstrDesc &MCID = MI->getDesc();
1319  bool AnyOps = false;
1320  unsigned NumOps = MI->getNumOperands();
1321 
1322  for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1323  unsigned DstIdx = 0;
1324  if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1325  continue;
1326  AnyOps = true;
1327  MachineOperand &SrcMO = MI->getOperand(SrcIdx);
1328  MachineOperand &DstMO = MI->getOperand(DstIdx);
1329  Register SrcReg = SrcMO.getReg();
1330  Register DstReg = DstMO.getReg();
1331  // Tied constraint already satisfied?
1332  if (SrcReg == DstReg)
1333  continue;
1334 
1335  assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1336 
1337  // Deal with undef uses immediately - simply rewrite the src operand.
1338  if (SrcMO.isUndef() && !DstMO.getSubReg()) {
1339  // Constrain the DstReg register class if required.
1340  if (DstReg.isVirtual())
1341  if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
1342  TRI, *MF))
1343  MRI->constrainRegClass(DstReg, RC);
1344  SrcMO.setReg(DstReg);
1345  SrcMO.setSubReg(0);
1346  LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1347  continue;
1348  }
1349  TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1350  }
1351  return AnyOps;
1352 }
1353 
1354 // Process a list of tied MI operands that all use the same source register.
1355 // The tied pairs are of the form (SrcIdx, DstIdx).
1356 void
1357 TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
1358  TiedPairList &TiedPairs,
1359  unsigned &Dist) {
1360  bool IsEarlyClobber = llvm::find_if(TiedPairs, [MI](auto const &TP) {
1361  return MI->getOperand(TP.second).isEarlyClobber();
1362  }) != TiedPairs.end();
1363 
1364  bool RemovedKillFlag = false;
1365  bool AllUsesCopied = true;
1366  unsigned LastCopiedReg = 0;
1367  SlotIndex LastCopyIdx;
1368  Register RegB = 0;
1369  unsigned SubRegB = 0;
1370  for (auto &TP : TiedPairs) {
1371  unsigned SrcIdx = TP.first;
1372  unsigned DstIdx = TP.second;
1373 
1374  const MachineOperand &DstMO = MI->getOperand(DstIdx);
1375  Register RegA = DstMO.getReg();
1376 
1377  // Grab RegB from the instruction because it may have changed if the
1378  // instruction was commuted.
1379  RegB = MI->getOperand(SrcIdx).getReg();
1380  SubRegB = MI->getOperand(SrcIdx).getSubReg();
1381 
1382  if (RegA == RegB) {
1383  // The register is tied to multiple destinations (or else we would
1384  // not have continued this far), but this use of the register
1385  // already matches the tied destination. Leave it.
1386  AllUsesCopied = false;
1387  continue;
1388  }
1389  LastCopiedReg = RegA;
1390 
1391  assert(RegB.isVirtual() && "cannot make instruction into two-address form");
1392 
1393 #ifndef NDEBUG
1394  // First, verify that we don't have a use of "a" in the instruction
1395  // (a = b + a for example) because our transformation will not
1396  // work. This should never occur because we are in SSA form.
1397  for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1398  assert(i == DstIdx ||
1399  !MI->getOperand(i).isReg() ||
1400  MI->getOperand(i).getReg() != RegA);
1401 #endif
1402 
1403  // Emit a copy.
1404  MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1405  TII->get(TargetOpcode::COPY), RegA);
1406  // If this operand is folding a truncation, the truncation now moves to the
1407  // copy so that the register classes remain valid for the operands.
1408  MIB.addReg(RegB, 0, SubRegB);
1409  const TargetRegisterClass *RC = MRI->getRegClass(RegB);
1410  if (SubRegB) {
1411  if (RegA.isVirtual()) {
1413  SubRegB) &&
1414  "tied subregister must be a truncation");
1415  // The superreg class will not be used to constrain the subreg class.
1416  RC = nullptr;
1417  } else {
1418  assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB))
1419  && "tied subregister must be a truncation");
1420  }
1421  }
1422 
1423  // Update DistanceMap.
1425  --PrevMI;
1426  DistanceMap.insert(std::make_pair(&*PrevMI, Dist));
1427  DistanceMap[MI] = ++Dist;
1428 
1429  if (LIS) {
1430  LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot();
1431 
1432  if (RegA.isVirtual()) {
1433  LiveInterval &LI = LIS->getInterval(RegA);
1434  VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1435  SlotIndex endIdx =
1436  LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber);
1437  LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI));
1438  }
1439  }
1440 
1441  LLVM_DEBUG(dbgs() << "\t\tprepend:\t" << *MIB);
1442 
1443  MachineOperand &MO = MI->getOperand(SrcIdx);
1444  assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1445  "inconsistent operand info for 2-reg pass");
1446  if (MO.isKill()) {
1447  MO.setIsKill(false);
1448  RemovedKillFlag = true;
1449  }
1450 
1451  // Make sure regA is a legal regclass for the SrcIdx operand.
1452  if (RegA.isVirtual() && RegB.isVirtual())
1453  MRI->constrainRegClass(RegA, RC);
1454  MO.setReg(RegA);
1455  // The getMatchingSuper asserts guarantee that the register class projected
1456  // by SubRegB is compatible with RegA with no subregister. So regardless of
1457  // whether the dest oper writes a subreg, the source oper should not.
1458  MO.setSubReg(0);
1459 
1460  // Propagate SrcRegMap.
1461  SrcRegMap[RegA] = RegB;
1462  }
1463 
1464  if (AllUsesCopied) {
1465  bool ReplacedAllUntiedUses = true;
1466  if (!IsEarlyClobber) {
1467  // Replace other (un-tied) uses of regB with LastCopiedReg.
1468  for (MachineOperand &MO : MI->operands()) {
1469  if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1470  if (MO.getSubReg() == SubRegB) {
1471  if (MO.isKill()) {
1472  MO.setIsKill(false);
1473  RemovedKillFlag = true;
1474  }
1475  MO.setReg(LastCopiedReg);
1476  MO.setSubReg(0);
1477  } else {
1478  ReplacedAllUntiedUses = false;
1479  }
1480  }
1481  }
1482  }
1483 
1484  // Update live variables for regB.
1485  if (RemovedKillFlag && ReplacedAllUntiedUses &&
1486  LV && LV->getVarInfo(RegB).removeKill(*MI)) {
1488  --PrevMI;
1489  LV->addVirtualRegisterKilled(RegB, *PrevMI);
1490  }
1491 
1492  // Update LiveIntervals.
1493  if (LIS) {
1494  LiveInterval &LI = LIS->getInterval(RegB);
1495  SlotIndex MIIdx = LIS->getInstructionIndex(*MI);
1496  LiveInterval::const_iterator I = LI.find(MIIdx);
1497  assert(I != LI.end() && "RegB must be live-in to use.");
1498 
1499  SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber);
1500  if (I->end == UseIdx)
1501  LI.removeSegment(LastCopyIdx, UseIdx);
1502  }
1503  } else if (RemovedKillFlag) {
1504  // Some tied uses of regB matched their destination registers, so
1505  // regB is still used in this instruction, but a kill flag was
1506  // removed from a different tied use of regB, so now we need to add
1507  // a kill flag to one of the remaining uses of regB.
1508  for (MachineOperand &MO : MI->operands()) {
1509  if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
1510  MO.setIsKill(true);
1511  break;
1512  }
1513  }
1514  }
1515 }
1516 
1517 /// Reduce two-address instructions to two operands.
1518 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
1519  MF = &Func;
1520  const TargetMachine &TM = MF->getTarget();
1521  MRI = &MF->getRegInfo();
1522  TII = MF->getSubtarget().getInstrInfo();
1523  TRI = MF->getSubtarget().getRegisterInfo();
1524  InstrItins = MF->getSubtarget().getInstrItineraryData();
1525  LV = getAnalysisIfAvailable<LiveVariables>();
1526  LIS = getAnalysisIfAvailable<LiveIntervals>();
1527  if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>())
1528  AA = &AAPass->getAAResults();
1529  else
1530  AA = nullptr;
1531  OptLevel = TM.getOptLevel();
1532  // Disable optimizations if requested. We cannot skip the whole pass as some
1533  // fixups are necessary for correctness.
1534  if (skipFunction(Func.getFunction()))
1535  OptLevel = CodeGenOpt::None;
1536 
1537  bool MadeChange = false;
1538 
1539  LLVM_DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1540  LLVM_DEBUG(dbgs() << "********** Function: " << MF->getName() << '\n');
1541 
1542  // This pass takes the function out of SSA form.
1543  MRI->leaveSSA();
1544 
1545  // This pass will rewrite the tied-def to meet the RegConstraint.
1546  MF->getProperties()
1548 
1549  TiedOperandMap TiedOperands;
1550  for (MachineBasicBlock &MBBI : *MF) {
1551  MBB = &MBBI;
1552  unsigned Dist = 0;
1553  DistanceMap.clear();
1554  SrcRegMap.clear();
1555  DstRegMap.clear();
1556  Processed.clear();
1557  for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1558  mi != me; ) {
1559  MachineBasicBlock::iterator nmi = std::next(mi);
1560  // Skip debug instructions.
1561  if (mi->isDebugInstr()) {
1562  mi = nmi;
1563  continue;
1564  }
1565 
1566  // Expand REG_SEQUENCE instructions. This will position mi at the first
1567  // expanded instruction.
1568  if (mi->isRegSequence())
1569  eliminateRegSequence(mi);
1570 
1571  DistanceMap.insert(std::make_pair(&*mi, ++Dist));
1572 
1573  processCopy(&*mi);
1574 
1575  // First scan through all the tied register uses in this instruction
1576  // and record a list of pairs of tied operands for each register.
1577  if (!collectTiedOperands(&*mi, TiedOperands)) {
1578  mi = nmi;
1579  continue;
1580  }
1581 
1582  ++NumTwoAddressInstrs;
1583  MadeChange = true;
1584  LLVM_DEBUG(dbgs() << '\t' << *mi);
1585 
1586  // If the instruction has a single pair of tied operands, try some
1587  // transformations that may either eliminate the tied operands or
1588  // improve the opportunities for coalescing away the register copy.
1589  if (TiedOperands.size() == 1) {
1591  = TiedOperands.begin()->second;
1592  if (TiedPairs.size() == 1) {
1593  unsigned SrcIdx = TiedPairs[0].first;
1594  unsigned DstIdx = TiedPairs[0].second;
1595  Register SrcReg = mi->getOperand(SrcIdx).getReg();
1596  Register DstReg = mi->getOperand(DstIdx).getReg();
1597  if (SrcReg != DstReg &&
1598  tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) {
1599  // The tied operands have been eliminated or shifted further down
1600  // the block to ease elimination. Continue processing with 'nmi'.
1601  TiedOperands.clear();
1602  mi = nmi;
1603  continue;
1604  }
1605  }
1606  }
1607 
1608  // Now iterate over the information collected above.
1609  for (auto &TO : TiedOperands) {
1610  processTiedPairs(&*mi, TO.second, Dist);
1611  LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1612  }
1613 
1614  // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1615  if (mi->isInsertSubreg()) {
1616  // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1617  // To %reg:subidx = COPY %subreg
1618  unsigned SubIdx = mi->getOperand(3).getImm();
1619  mi->RemoveOperand(3);
1620  assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1621  mi->getOperand(0).setSubReg(SubIdx);
1622  mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1623  mi->RemoveOperand(1);
1624  mi->setDesc(TII->get(TargetOpcode::COPY));
1625  LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1626  }
1627 
1628  // Clear TiedOperands here instead of at the top of the loop
1629  // since most instructions do not have tied operands.
1630  TiedOperands.clear();
1631  mi = nmi;
1632  }
1633  }
1634 
1635  if (LIS)
1636  MF->verify(this, "After two-address instruction pass");
1637 
1638  return MadeChange;
1639 }
1640 
1641 /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1642 ///
1643 /// The instruction is turned into a sequence of sub-register copies:
1644 ///
1645 /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1646 ///
1647 /// Becomes:
1648 ///
1649 /// undef %dst:ssub0 = COPY %v1
1650 /// %dst:ssub1 = COPY %v2
1651 void TwoAddressInstructionPass::
1652 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1653  MachineInstr &MI = *MBBI;
1654  Register DstReg = MI.getOperand(0).getReg();
1655  if (MI.getOperand(0).getSubReg() || DstReg.isPhysical() ||
1656  !(MI.getNumOperands() & 1)) {
1657  LLVM_DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI);
1658  llvm_unreachable(nullptr);
1659  }
1660 
1661  SmallVector<Register, 4> OrigRegs;
1662  if (LIS) {
1663  OrigRegs.push_back(MI.getOperand(0).getReg());
1664  for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2)
1665  OrigRegs.push_back(MI.getOperand(i).getReg());
1666  }
1667 
1668  bool DefEmitted = false;
1669  for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
1670  MachineOperand &UseMO = MI.getOperand(i);
1671  Register SrcReg = UseMO.getReg();
1672  unsigned SubIdx = MI.getOperand(i+1).getImm();
1673  // Nothing needs to be inserted for undef operands.
1674  if (UseMO.isUndef())
1675  continue;
1676 
1677  // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1678  // might insert a COPY that uses SrcReg after is was killed.
1679  bool isKill = UseMO.isKill();
1680  if (isKill)
1681  for (unsigned j = i + 2; j < e; j += 2)
1682  if (MI.getOperand(j).getReg() == SrcReg) {
1683  MI.getOperand(j).setIsKill();
1684  UseMO.setIsKill(false);
1685  isKill = false;
1686  break;
1687  }
1688 
1689  // Insert the sub-register copy.
1690  MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
1691  TII->get(TargetOpcode::COPY))
1692  .addReg(DstReg, RegState::Define, SubIdx)
1693  .add(UseMO);
1694 
1695  // The first def needs an undef flag because there is no live register
1696  // before it.
1697  if (!DefEmitted) {
1698  CopyMI->getOperand(0).setIsUndef(true);
1699  // Return an iterator pointing to the first inserted instr.
1700  MBBI = CopyMI;
1701  }
1702  DefEmitted = true;
1703 
1704  // Update LiveVariables' kill info.
1705  if (LV && isKill && !SrcReg.isPhysical())
1706  LV->replaceKillInstruction(SrcReg, MI, *CopyMI);
1707 
1708  LLVM_DEBUG(dbgs() << "Inserted: " << *CopyMI);
1709  }
1710 
1711  MachineBasicBlock::iterator EndMBBI =
1712  std::next(MachineBasicBlock::iterator(MI));
1713 
1714  if (!DefEmitted) {
1715  LLVM_DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF");
1716  MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1717  for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j)
1718  MI.RemoveOperand(j);
1719  } else {
1720  LLVM_DEBUG(dbgs() << "Eliminated: " << MI);
1721  MI.eraseFromParent();
1722  }
1723 
1724  // Udpate LiveIntervals.
1725  if (LIS)
1726  LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
1727 }
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:244
llvm::MachineInstr::isBranch
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:844
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:100
llvm::MachineInstr::getOperandNo
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
Definition: MachineInstr.h:672
MachineInstr.h
llvm::MachineRegisterInfo::def_begin
def_iterator def_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:384
llvm
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:100
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::SystemZISD::TM
@ TM
Definition: SystemZISelLowering.h:65
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:225
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:497
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:140
llvm::MachineInstr::defs
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:644
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:231
DenseMap.h
TargetInstrInfo.h
llvm::MachineInstr::isCopy
bool isCopy() const
Definition: MachineInstr.h:1279
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::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
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
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:122
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:583
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:1507
llvm::MachineBasicBlock::erase
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
Definition: MachineBasicBlock.cpp:1322
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:387
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:565
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:812
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:367
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:488
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:468
SI
@ SI
Definition: SIInstrInfo.cpp:7342
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:646
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:676
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:196
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:166
pass
Two Address instruction pass
Definition: TwoAddressInstructionPass.cpp:198
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::MachineFunction::makeDebugValueSubstitution
void makeDebugValueSubstitution(DebugInstrOperandPair, DebugInstrOperandPair)
Create a substitution between one <instr,operand> value to a different, new value.
Definition: MachineFunction.cpp:952
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:402
llvm::RegState::Define
@ Define
Register definition.
Definition: MachineInstrBuilder.h:45
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:284
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:235
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:1682
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
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:555
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:392
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:318
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:70
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::skipDebugInstructionsForward
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=false)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Definition: MachineBasicBlock.h:1115
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:561
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:440
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:522
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::TargetMachine
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:77
llvm::elfabi::ELFSymbolType::Func
@ Func
iterator_range.h
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:98
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:357
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:227
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::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:859
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:508
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:836
llvm::MachineFunctionProperties::Property::TiedOpsRewritten
@ TiedOpsRewritten
llvm::CodeGenOpt::Level
Level
Definition: CodeGen.h:52
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:362
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:1532
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:1293
llvm::MachineFunction::getTarget
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
Definition: MachineFunction.h:551
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:1335
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:329
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:101
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1269
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
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:411
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:607
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:22
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:38