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