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