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