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