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