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