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