1//===- MachineCopyPropagation.cpp - Machine Copy Propagation 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 is an extremely simple MachineInstr-level copy propagation pass.
10//
11// This pass forwards the source of COPYs to the users of their destinations
12// when doing so is legal. For example:
13//
14// %reg1 = COPY %reg0
15// ...
16// ... = OP %reg1
17//
18// If
19// - %reg0 has not been clobbered by the time of the use of %reg1
20// - the register class constraints are satisfied
21// - the COPY def is the only value that reaches OP
22// then this pass replaces the above with:
23//
24// %reg1 = COPY %reg0
25// ...
26// ... = OP %reg0
27//
28// This pass also removes some redundant COPYs. For example:
29//
30// %R1 = COPY %R0
31// ... // No clobber of %R1
32// %R0 = COPY %R1 <<< Removed
33//
34// or
35//
36// %R1 = COPY %R0
37// ... // No clobber of %R0
38// %R1 = COPY %R0 <<< Removed
39//
40// or
41//
42// $R0 = OP ...
43// ... // No read/clobber of $R0 and $R1
44// $R1 = COPY $R0 // $R0 is killed
45// Replace $R0 with $R1 and remove the COPY
46// $R1 = OP ...
47// ...
48//
49//===----------------------------------------------------------------------===//
50
51#include "llvm/ADT/DenseMap.h"
52#include "llvm/ADT/STLExtras.h"
53#include "llvm/ADT/SetVector.h"
54#include "llvm/ADT/SmallSet.h"
55#include "llvm/ADT/SmallVector.h"
56#include "llvm/ADT/Statistic.h"
57#include "llvm/ADT/iterator_range.h"
58#include "llvm/CodeGen/MachineBasicBlock.h"
59#include "llvm/CodeGen/MachineFunction.h"
60#include "llvm/CodeGen/MachineFunctionPass.h"
61#include "llvm/CodeGen/MachineInstr.h"
62#include "llvm/CodeGen/MachineOperand.h"
63#include "llvm/CodeGen/MachineRegisterInfo.h"
64#include "llvm/CodeGen/TargetInstrInfo.h"
65#include "llvm/CodeGen/TargetRegisterInfo.h"
66#include "llvm/CodeGen/TargetSubtargetInfo.h"
67#include "llvm/InitializePasses.h"
68#include "llvm/MC/MCRegister.h"
69#include "llvm/MC/MCRegisterInfo.h"
70#include "llvm/Pass.h"
71#include "llvm/Support/Debug.h"
72#include "llvm/Support/DebugCounter.h"
73#include "llvm/Support/raw_ostream.h"
74#include <cassert>
75#include <iterator>
76
77using namespace llvm;
78
79#define DEBUG_TYPE "machine-cp"
80
81STATISTIC(NumDeletes, "Number of dead copies deleted");
82STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
83STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");
84STATISTIC(SpillageChainsLength, "Length of spillage chains");
85STATISTIC(NumSpillageChains, "Number of spillage chains");
86DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
87 "Controls which register COPYs are forwarded");
88
89static cl::opt<bool> MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(Val: false),
90 cl::Hidden);
91static cl::opt<cl::boolOrDefault>
92 EnableSpillageCopyElimination("enable-spill-copy-elim", cl::Hidden);
93
94namespace {
95
96static std::optional<DestSourcePair> isCopyInstr(const MachineInstr &MI,
97 const TargetInstrInfo &TII,
98 bool UseCopyInstr) {
99 if (UseCopyInstr)
100 return TII.isCopyInstr(MI);
101
102 if (MI.isCopy())
103 return std::optional<DestSourcePair>(
104 DestSourcePair{MI.getOperand(i: 0), MI.getOperand(i: 1)});
105
106 return std::nullopt;
107}
108
109class CopyTracker {
110 struct CopyInfo {
111 MachineInstr *MI, *LastSeenUseInCopy;
112 SmallVector<MCRegister, 4> DefRegs;
113 bool Avail;
114 };
115
116 DenseMap<MCRegUnit, CopyInfo> Copies;
117
118public:
119 /// Mark all of the given registers and their subregisters as unavailable for
120 /// copying.
121 void markRegsUnavailable(ArrayRef<MCRegister> Regs,
122 const TargetRegisterInfo &TRI) {
123 for (MCRegister Reg : Regs) {
124 // Source of copy is no longer available for propagation.
125 for (MCRegUnit Unit : TRI.regunits(Reg)) {
126 auto CI = Copies.find(Val: Unit);
127 if (CI != Copies.end())
128 CI->second.Avail = false;
129 }
130 }
131 }
132
133 /// Remove register from copy maps.
134 void invalidateRegister(MCRegister Reg, const TargetRegisterInfo &TRI,
135 const TargetInstrInfo &TII, bool UseCopyInstr) {
136 // Since Reg might be a subreg of some registers, only invalidate Reg is not
137 // enough. We have to find the COPY defines Reg or registers defined by Reg
138 // and invalidate all of them. Similarly, we must invalidate all of the
139 // the subregisters used in the source of the COPY.
140 SmallSet<MCRegUnit, 8> RegUnitsToInvalidate;
141 auto InvalidateCopy = [&](MachineInstr *MI) {
142 std::optional<DestSourcePair> CopyOperands =
143 isCopyInstr(MI: *MI, TII, UseCopyInstr);
144 assert(CopyOperands && "Expect copy");
145
146 auto Dest = TRI.regunits(Reg: CopyOperands->Destination->getReg().asMCReg());
147 auto Src = TRI.regunits(Reg: CopyOperands->Source->getReg().asMCReg());
148 RegUnitsToInvalidate.insert(I: Dest.begin(), E: Dest.end());
149 RegUnitsToInvalidate.insert(I: Src.begin(), E: Src.end());
150 };
151
152 for (MCRegUnit Unit : TRI.regunits(Reg)) {
153 auto I = Copies.find(Val: Unit);
154 if (I != Copies.end()) {
155 if (MachineInstr *MI = I->second.MI)
156 InvalidateCopy(MI);
157 if (MachineInstr *MI = I->second.LastSeenUseInCopy)
158 InvalidateCopy(MI);
159 }
160 }
161 for (MCRegUnit Unit : RegUnitsToInvalidate)
162 Copies.erase(Val: Unit);
163 }
164
165 /// Clobber a single register, removing it from the tracker's copy maps.
166 void clobberRegister(MCRegister Reg, const TargetRegisterInfo &TRI,
167 const TargetInstrInfo &TII, bool UseCopyInstr) {
168 for (MCRegUnit Unit : TRI.regunits(Reg)) {
169 auto I = Copies.find(Val: Unit);
170 if (I != Copies.end()) {
171 // When we clobber the source of a copy, we need to clobber everything
172 // it defined.
173 markRegsUnavailable(Regs: I->second.DefRegs, TRI);
174 // When we clobber the destination of a copy, we need to clobber the
175 // whole register it defined.
176 if (MachineInstr *MI = I->second.MI) {
177 std::optional<DestSourcePair> CopyOperands =
178 isCopyInstr(MI: *MI, TII, UseCopyInstr);
179
180 MCRegister Def = CopyOperands->Destination->getReg().asMCReg();
181 MCRegister Src = CopyOperands->Source->getReg().asMCReg();
182
183 markRegsUnavailable(Regs: Def, TRI);
184
185 // Since we clobber the destination of a copy, the semantic of Src's
186 // "DefRegs" to contain Def is no longer effectual. We will also need
187 // to remove the record from the copy maps that indicates Src defined
188 // Def. Failing to do so might cause the target to miss some
189 // opportunities to further eliminate redundant copy instructions.
190 // Consider the following sequence during the
191 // ForwardCopyPropagateBlock procedure:
192 // L1: r0 = COPY r9 <- TrackMI
193 // L2: r0 = COPY r8 <- TrackMI (Remove r9 defined r0 from tracker)
194 // L3: use r0 <- Remove L2 from MaybeDeadCopies
195 // L4: early-clobber r9 <- Clobber r9 (L2 is still valid in tracker)
196 // L5: r0 = COPY r8 <- Remove NopCopy
197 for (MCRegUnit SrcUnit : TRI.regunits(Reg: Src)) {
198 auto SrcCopy = Copies.find(Val: SrcUnit);
199 if (SrcCopy != Copies.end() && SrcCopy->second.LastSeenUseInCopy) {
200 // If SrcCopy defines multiple values, we only need
201 // to erase the record for Def in DefRegs.
202 for (auto itr = SrcCopy->second.DefRegs.begin();
203 itr != SrcCopy->second.DefRegs.end(); itr++) {
204 if (*itr == Def) {
205 SrcCopy->second.DefRegs.erase(CI: itr);
206 // If DefReg becomes empty after removal, we can remove the
207 // SrcCopy from the tracker's copy maps. We only remove those
208 // entries solely record the Def is defined by Src. If an
209 // entry also contains the definition record of other Def'
210 // registers, it cannot be cleared.
211 if (SrcCopy->second.DefRegs.empty() && !SrcCopy->second.MI) {
212 Copies.erase(I: SrcCopy);
213 }
214 break;
215 }
216 }
217 }
218 }
219 }
220 // Now we can erase the copy.
221 Copies.erase(I);
222 }
223 }
224 }
225
226 /// Add this copy's registers into the tracker's copy maps.
227 void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI,
228 const TargetInstrInfo &TII, bool UseCopyInstr) {
229 std::optional<DestSourcePair> CopyOperands =
230 isCopyInstr(MI: *MI, TII, UseCopyInstr);
231 assert(CopyOperands && "Tracking non-copy?");
232
233 MCRegister Src = CopyOperands->Source->getReg().asMCReg();
234 MCRegister Def = CopyOperands->Destination->getReg().asMCReg();
235
236 // Remember Def is defined by the copy.
237 for (MCRegUnit Unit : TRI.regunits(Reg: Def))
238 Copies[Unit] = {.MI: MI, .LastSeenUseInCopy: nullptr, .DefRegs: {}, .Avail: true};
239
240 // Remember source that's copied to Def. Once it's clobbered, then
241 // it's no longer available for copy propagation.
242 for (MCRegUnit Unit : TRI.regunits(Reg: Src)) {
243 auto I = Copies.insert(KV: {Unit, {.MI: nullptr, .LastSeenUseInCopy: nullptr, .DefRegs: {}, .Avail: false}});
244 auto &Copy = I.first->second;
245 if (!is_contained(Range&: Copy.DefRegs, Element: Def))
246 Copy.DefRegs.push_back(Elt: Def);
247 Copy.LastSeenUseInCopy = MI;
248 }
249 }
250
251 bool hasAnyCopies() {
252 return !Copies.empty();
253 }
254
255 MachineInstr *findCopyForUnit(MCRegUnit RegUnit,
256 const TargetRegisterInfo &TRI,
257 bool MustBeAvailable = false) {
258 auto CI = Copies.find(Val: RegUnit);
259 if (CI == Copies.end())
260 return nullptr;
261 if (MustBeAvailable && !CI->second.Avail)
262 return nullptr;
263 return CI->second.MI;
264 }
265
266 MachineInstr *findCopyDefViaUnit(MCRegUnit RegUnit,
267 const TargetRegisterInfo &TRI) {
268 auto CI = Copies.find(Val: RegUnit);
269 if (CI == Copies.end())
270 return nullptr;
271 if (CI->second.DefRegs.size() != 1)
272 return nullptr;
273 MCRegUnit RU = *TRI.regunits(Reg: CI->second.DefRegs[0]).begin();
274 return findCopyForUnit(RegUnit: RU, TRI, MustBeAvailable: true);
275 }
276
277 MachineInstr *findAvailBackwardCopy(MachineInstr &I, MCRegister Reg,
278 const TargetRegisterInfo &TRI,
279 const TargetInstrInfo &TII,
280 bool UseCopyInstr) {
281 MCRegUnit RU = *TRI.regunits(Reg).begin();
282 MachineInstr *AvailCopy = findCopyDefViaUnit(RegUnit: RU, TRI);
283
284 if (!AvailCopy)
285 return nullptr;
286
287 std::optional<DestSourcePair> CopyOperands =
288 isCopyInstr(MI: *AvailCopy, TII, UseCopyInstr);
289 Register AvailSrc = CopyOperands->Source->getReg();
290 Register AvailDef = CopyOperands->Destination->getReg();
291 if (!TRI.isSubRegisterEq(RegA: AvailSrc, RegB: Reg))
292 return nullptr;
293
294 for (const MachineInstr &MI :
295 make_range(x: AvailCopy->getReverseIterator(), y: I.getReverseIterator()))
296 for (const MachineOperand &MO : MI.operands())
297 if (MO.isRegMask())
298 // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef?
299 if (MO.clobbersPhysReg(PhysReg: AvailSrc) || MO.clobbersPhysReg(PhysReg: AvailDef))
300 return nullptr;
301
302 return AvailCopy;
303 }
304
305 MachineInstr *findAvailCopy(MachineInstr &DestCopy, MCRegister Reg,
306 const TargetRegisterInfo &TRI,
307 const TargetInstrInfo &TII, bool UseCopyInstr) {
308 // We check the first RegUnit here, since we'll only be interested in the
309 // copy if it copies the entire register anyway.
310 MCRegUnit RU = *TRI.regunits(Reg).begin();
311 MachineInstr *AvailCopy =
312 findCopyForUnit(RegUnit: RU, TRI, /*MustBeAvailable=*/true);
313
314 if (!AvailCopy)
315 return nullptr;
316
317 std::optional<DestSourcePair> CopyOperands =
318 isCopyInstr(MI: *AvailCopy, TII, UseCopyInstr);
319 Register AvailSrc = CopyOperands->Source->getReg();
320 Register AvailDef = CopyOperands->Destination->getReg();
321 if (!TRI.isSubRegisterEq(RegA: AvailDef, RegB: Reg))
322 return nullptr;
323
324 // Check that the available copy isn't clobbered by any regmasks between
325 // itself and the destination.
326 for (const MachineInstr &MI :
327 make_range(x: AvailCopy->getIterator(), y: DestCopy.getIterator()))
328 for (const MachineOperand &MO : MI.operands())
329 if (MO.isRegMask())
330 if (MO.clobbersPhysReg(PhysReg: AvailSrc) || MO.clobbersPhysReg(PhysReg: AvailDef))
331 return nullptr;
332
333 return AvailCopy;
334 }
335
336 // Find last COPY that defines Reg before Current MachineInstr.
337 MachineInstr *findLastSeenDefInCopy(const MachineInstr &Current,
338 MCRegister Reg,
339 const TargetRegisterInfo &TRI,
340 const TargetInstrInfo &TII,
341 bool UseCopyInstr) {
342 MCRegUnit RU = *TRI.regunits(Reg).begin();
343 auto CI = Copies.find(Val: RU);
344 if (CI == Copies.end() || !CI->second.Avail)
345 return nullptr;
346
347 MachineInstr *DefCopy = CI->second.MI;
348 std::optional<DestSourcePair> CopyOperands =
349 isCopyInstr(MI: *DefCopy, TII, UseCopyInstr);
350 Register Def = CopyOperands->Destination->getReg();
351 if (!TRI.isSubRegisterEq(RegA: Def, RegB: Reg))
352 return nullptr;
353
354 for (const MachineInstr &MI :
355 make_range(x: static_cast<const MachineInstr *>(DefCopy)->getIterator(),
356 y: Current.getIterator()))
357 for (const MachineOperand &MO : MI.operands())
358 if (MO.isRegMask())
359 if (MO.clobbersPhysReg(PhysReg: Def)) {
360 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of "
361 << printReg(Def, &TRI) << "\n");
362 return nullptr;
363 }
364
365 return DefCopy;
366 }
367
368 // Find last COPY that uses Reg.
369 MachineInstr *findLastSeenUseInCopy(MCRegister Reg,
370 const TargetRegisterInfo &TRI) {
371 MCRegUnit RU = *TRI.regunits(Reg).begin();
372 auto CI = Copies.find(Val: RU);
373 if (CI == Copies.end())
374 return nullptr;
375 return CI->second.LastSeenUseInCopy;
376 }
377
378 void clear() {
379 Copies.clear();
380 }
381};
382
383class MachineCopyPropagation : public MachineFunctionPass {
384 const TargetRegisterInfo *TRI = nullptr;
385 const TargetInstrInfo *TII = nullptr;
386 const MachineRegisterInfo *MRI = nullptr;
387
388 // Return true if this is a copy instruction and false otherwise.
389 bool UseCopyInstr;
390
391public:
392 static char ID; // Pass identification, replacement for typeid
393
394 MachineCopyPropagation(bool CopyInstr = false)
395 : MachineFunctionPass(ID), UseCopyInstr(CopyInstr || MCPUseCopyInstr) {
396 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
397 }
398
399 void getAnalysisUsage(AnalysisUsage &AU) const override {
400 AU.setPreservesCFG();
401 MachineFunctionPass::getAnalysisUsage(AU);
402 }
403
404 bool runOnMachineFunction(MachineFunction &MF) override;
405
406 MachineFunctionProperties getRequiredProperties() const override {
407 return MachineFunctionProperties().set(
408 MachineFunctionProperties::Property::NoVRegs);
409 }
410
411private:
412 typedef enum { DebugUse = false, RegularUse = true } DebugType;
413
414 void ReadRegister(MCRegister Reg, MachineInstr &Reader, DebugType DT);
415 void readSuccessorLiveIns(const MachineBasicBlock &MBB);
416 void ForwardCopyPropagateBlock(MachineBasicBlock &MBB);
417 void BackwardCopyPropagateBlock(MachineBasicBlock &MBB);
418 void EliminateSpillageCopies(MachineBasicBlock &MBB);
419 bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def);
420 void forwardUses(MachineInstr &MI);
421 void propagateDefs(MachineInstr &MI);
422 bool isForwardableRegClassCopy(const MachineInstr &Copy,
423 const MachineInstr &UseI, unsigned UseIdx);
424 bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
425 const MachineInstr &UseI,
426 unsigned UseIdx);
427 bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
428 bool hasOverlappingMultipleDef(const MachineInstr &MI,
429 const MachineOperand &MODef, Register Def);
430
431 /// Candidates for deletion.
432 SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
433
434 /// Multimap tracking debug users in current BB
435 DenseMap<MachineInstr *, SmallSet<MachineInstr *, 2>> CopyDbgUsers;
436
437 CopyTracker Tracker;
438
439 bool Changed = false;
440};
441
442} // end anonymous namespace
443
444char MachineCopyPropagation::ID = 0;
445
446char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
447
448INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
449 "Machine Copy Propagation Pass", false, false)
450
451void MachineCopyPropagation::ReadRegister(MCRegister Reg, MachineInstr &Reader,
452 DebugType DT) {
453 // If 'Reg' is defined by a copy, the copy is no longer a candidate
454 // for elimination. If a copy is "read" by a debug user, record the user
455 // for propagation.
456 for (MCRegUnit Unit : TRI->regunits(Reg)) {
457 if (MachineInstr *Copy = Tracker.findCopyForUnit(RegUnit: Unit, TRI: *TRI)) {
458 if (DT == RegularUse) {
459 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
460 MaybeDeadCopies.remove(X: Copy);
461 } else {
462 CopyDbgUsers[Copy].insert(Ptr: &Reader);
463 }
464 }
465 }
466}
467
468void MachineCopyPropagation::readSuccessorLiveIns(
469 const MachineBasicBlock &MBB) {
470 if (MaybeDeadCopies.empty())
471 return;
472
473 // If a copy result is livein to a successor, it is not dead.
474 for (const MachineBasicBlock *Succ : MBB.successors()) {
475 for (const auto &LI : Succ->liveins()) {
476 for (MCRegUnit Unit : TRI->regunits(Reg: LI.PhysReg)) {
477 if (MachineInstr *Copy = Tracker.findCopyForUnit(RegUnit: Unit, TRI: *TRI))
478 MaybeDeadCopies.remove(X: Copy);
479 }
480 }
481 }
482}
483
484/// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
485/// This fact may have been obscured by sub register usage or may not be true at
486/// all even though Src and Def are subregisters of the registers used in
487/// PreviousCopy. e.g.
488/// isNopCopy("ecx = COPY eax", AX, CX) == true
489/// isNopCopy("ecx = COPY eax", AH, CL) == false
490static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src,
491 MCRegister Def, const TargetRegisterInfo *TRI,
492 const TargetInstrInfo *TII, bool UseCopyInstr) {
493
494 std::optional<DestSourcePair> CopyOperands =
495 isCopyInstr(MI: PreviousCopy, TII: *TII, UseCopyInstr);
496 MCRegister PreviousSrc = CopyOperands->Source->getReg().asMCReg();
497 MCRegister PreviousDef = CopyOperands->Destination->getReg().asMCReg();
498 if (Src == PreviousSrc && Def == PreviousDef)
499 return true;
500 if (!TRI->isSubRegister(RegA: PreviousSrc, RegB: Src))
501 return false;
502 unsigned SubIdx = TRI->getSubRegIndex(RegNo: PreviousSrc, SubRegNo: Src);
503 return SubIdx == TRI->getSubRegIndex(RegNo: PreviousDef, SubRegNo: Def);
504}
505
506/// Remove instruction \p Copy if there exists a previous copy that copies the
507/// register \p Src to the register \p Def; This may happen indirectly by
508/// copying the super registers.
509bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy,
510 MCRegister Src, MCRegister Def) {
511 // Avoid eliminating a copy from/to a reserved registers as we cannot predict
512 // the value (Example: The sparc zero register is writable but stays zero).
513 if (MRI->isReserved(PhysReg: Src) || MRI->isReserved(PhysReg: Def))
514 return false;
515
516 // Search for an existing copy.
517 MachineInstr *PrevCopy =
518 Tracker.findAvailCopy(DestCopy&: Copy, Reg: Def, TRI: *TRI, TII: *TII, UseCopyInstr);
519 if (!PrevCopy)
520 return false;
521
522 auto PrevCopyOperands = isCopyInstr(MI: *PrevCopy, TII: *TII, UseCopyInstr);
523 // Check that the existing copy uses the correct sub registers.
524 if (PrevCopyOperands->Destination->isDead())
525 return false;
526 if (!isNopCopy(PreviousCopy: *PrevCopy, Src, Def, TRI, TII, UseCopyInstr))
527 return false;
528
529 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
530
531 // Copy was redundantly redefining either Src or Def. Remove earlier kill
532 // flags between Copy and PrevCopy because the value will be reused now.
533 std::optional<DestSourcePair> CopyOperands =
534 isCopyInstr(MI: Copy, TII: *TII, UseCopyInstr);
535 assert(CopyOperands);
536
537 Register CopyDef = CopyOperands->Destination->getReg();
538 assert(CopyDef == Src || CopyDef == Def);
539 for (MachineInstr &MI :
540 make_range(x: PrevCopy->getIterator(), y: Copy.getIterator()))
541 MI.clearRegisterKills(Reg: CopyDef, RegInfo: TRI);
542
543 // Clear undef flag from remaining copy if needed.
544 if (!CopyOperands->Source->isUndef()) {
545 PrevCopy->getOperand(i: PrevCopyOperands->Source->getOperandNo())
546 .setIsUndef(false);
547 }
548
549 Copy.eraseFromParent();
550 Changed = true;
551 ++NumDeletes;
552 return true;
553}
554
555bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(
556 const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) {
557 std::optional<DestSourcePair> CopyOperands =
558 isCopyInstr(MI: Copy, TII: *TII, UseCopyInstr);
559 Register Def = CopyOperands->Destination->getReg();
560
561 if (const TargetRegisterClass *URC =
562 UseI.getRegClassConstraint(OpIdx: UseIdx, TII, TRI))
563 return URC->contains(Reg: Def);
564
565 // We don't process further if UseI is a COPY, since forward copy propagation
566 // should handle that.
567 return false;
568}
569
570/// Decide whether we should forward the source of \param Copy to its use in
571/// \param UseI based on the physical register class constraints of the opcode
572/// and avoiding introducing more cross-class COPYs.
573bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
574 const MachineInstr &UseI,
575 unsigned UseIdx) {
576 std::optional<DestSourcePair> CopyOperands =
577 isCopyInstr(MI: Copy, TII: *TII, UseCopyInstr);
578 Register CopySrcReg = CopyOperands->Source->getReg();
579
580 // If the new register meets the opcode register constraints, then allow
581 // forwarding.
582 if (const TargetRegisterClass *URC =
583 UseI.getRegClassConstraint(OpIdx: UseIdx, TII, TRI))
584 return URC->contains(Reg: CopySrcReg);
585
586 auto UseICopyOperands = isCopyInstr(MI: UseI, TII: *TII, UseCopyInstr);
587 if (!UseICopyOperands)
588 return false;
589
590 /// COPYs don't have register class constraints, so if the user instruction
591 /// is a COPY, we just try to avoid introducing additional cross-class
592 /// COPYs. For example:
593 ///
594 /// RegClassA = COPY RegClassB // Copy parameter
595 /// ...
596 /// RegClassB = COPY RegClassA // UseI parameter
597 ///
598 /// which after forwarding becomes
599 ///
600 /// RegClassA = COPY RegClassB
601 /// ...
602 /// RegClassB = COPY RegClassB
603 ///
604 /// so we have reduced the number of cross-class COPYs and potentially
605 /// introduced a nop COPY that can be removed.
606
607 // Allow forwarding if src and dst belong to any common class, so long as they
608 // don't belong to any (possibly smaller) common class that requires copies to
609 // go via a different class.
610 Register UseDstReg = UseICopyOperands->Destination->getReg();
611 bool Found = false;
612 bool IsCrossClass = false;
613 for (const TargetRegisterClass *RC : TRI->regclasses()) {
614 if (RC->contains(Reg: CopySrcReg) && RC->contains(Reg: UseDstReg)) {
615 Found = true;
616 if (TRI->getCrossCopyRegClass(RC) != RC) {
617 IsCrossClass = true;
618 break;
619 }
620 }
621 }
622 if (!Found)
623 return false;
624 if (!IsCrossClass)
625 return true;
626 // The forwarded copy would be cross-class. Only do this if the original copy
627 // was also cross-class.
628 Register CopyDstReg = CopyOperands->Destination->getReg();
629 for (const TargetRegisterClass *RC : TRI->regclasses()) {
630 if (RC->contains(Reg: CopySrcReg) && RC->contains(Reg: CopyDstReg) &&
631 TRI->getCrossCopyRegClass(RC) != RC)
632 return true;
633 }
634 return false;
635}
636
637/// Check that \p MI does not have implicit uses that overlap with it's \p Use
638/// operand (the register being replaced), since these can sometimes be
639/// implicitly tied to other operands. For example, on AMDGPU:
640///
641/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
642///
643/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
644/// way of knowing we need to update the latter when updating the former.
645bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
646 const MachineOperand &Use) {
647 for (const MachineOperand &MIUse : MI.uses())
648 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
649 MIUse.isUse() && TRI->regsOverlap(RegA: Use.getReg(), RegB: MIUse.getReg()))
650 return true;
651
652 return false;
653}
654
655/// For an MI that has multiple definitions, check whether \p MI has
656/// a definition that overlaps with another of its definitions.
657/// For example, on ARM: umull r9, r9, lr, r0
658/// The umull instruction is unpredictable unless RdHi and RdLo are different.
659bool MachineCopyPropagation::hasOverlappingMultipleDef(
660 const MachineInstr &MI, const MachineOperand &MODef, Register Def) {
661 for (const MachineOperand &MIDef : MI.all_defs()) {
662 if ((&MIDef != &MODef) && MIDef.isReg() &&
663 TRI->regsOverlap(RegA: Def, RegB: MIDef.getReg()))
664 return true;
665 }
666
667 return false;
668}
669
670/// Look for available copies whose destination register is used by \p MI and
671/// replace the use in \p MI with the copy's source register.
672void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
673 if (!Tracker.hasAnyCopies())
674 return;
675
676 // Look for non-tied explicit vreg uses that have an active COPY
677 // instruction that defines the physical register allocated to them.
678 // Replace the vreg with the source of the active COPY.
679 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
680 ++OpIdx) {
681 MachineOperand &MOUse = MI.getOperand(i: OpIdx);
682 // Don't forward into undef use operands since doing so can cause problems
683 // with the machine verifier, since it doesn't treat undef reads as reads,
684 // so we can end up with a live range that ends on an undef read, leading to
685 // an error that the live range doesn't end on a read of the live range
686 // register.
687 if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
688 MOUse.isImplicit())
689 continue;
690
691 if (!MOUse.getReg())
692 continue;
693
694 // Check that the register is marked 'renamable' so we know it is safe to
695 // rename it without violating any constraints that aren't expressed in the
696 // IR (e.g. ABI or opcode requirements).
697 if (!MOUse.isRenamable())
698 continue;
699
700 MachineInstr *Copy = Tracker.findAvailCopy(DestCopy&: MI, Reg: MOUse.getReg().asMCReg(),
701 TRI: *TRI, TII: *TII, UseCopyInstr);
702 if (!Copy)
703 continue;
704
705 std::optional<DestSourcePair> CopyOperands =
706 isCopyInstr(MI: *Copy, TII: *TII, UseCopyInstr);
707 Register CopyDstReg = CopyOperands->Destination->getReg();
708 const MachineOperand &CopySrc = *CopyOperands->Source;
709 Register CopySrcReg = CopySrc.getReg();
710
711 Register ForwardedReg = CopySrcReg;
712 // MI might use a sub-register of the Copy destination, in which case the
713 // forwarded register is the matching sub-register of the Copy source.
714 if (MOUse.getReg() != CopyDstReg) {
715 unsigned SubRegIdx = TRI->getSubRegIndex(RegNo: CopyDstReg, SubRegNo: MOUse.getReg());
716 assert(SubRegIdx &&
717 "MI source is not a sub-register of Copy destination");
718 ForwardedReg = TRI->getSubReg(Reg: CopySrcReg, Idx: SubRegIdx);
719 if (!ForwardedReg) {
720 LLVM_DEBUG(dbgs() << "MCP: Copy source does not have sub-register "
721 << TRI->getSubRegIndexName(SubRegIdx) << '\n');
722 continue;
723 }
724 }
725
726 // Don't forward COPYs of reserved regs unless they are constant.
727 if (MRI->isReserved(PhysReg: CopySrcReg) && !MRI->isConstantPhysReg(PhysReg: CopySrcReg))
728 continue;
729
730 if (!isForwardableRegClassCopy(Copy: *Copy, UseI: MI, UseIdx: OpIdx))
731 continue;
732
733 if (hasImplicitOverlap(MI, Use: MOUse))
734 continue;
735
736 // Check that the instruction is not a copy that partially overwrites the
737 // original copy source that we are about to use. The tracker mechanism
738 // cannot cope with that.
739 if (isCopyInstr(MI, TII: *TII, UseCopyInstr) &&
740 MI.modifiesRegister(Reg: CopySrcReg, TRI) &&
741 !MI.definesRegister(Reg: CopySrcReg, /*TRI=*/nullptr)) {
742 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI);
743 continue;
744 }
745
746 if (!DebugCounter::shouldExecute(CounterName: FwdCounter)) {
747 LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "
748 << MI);
749 continue;
750 }
751
752 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
753 << "\n with " << printReg(ForwardedReg, TRI)
754 << "\n in " << MI << " from " << *Copy);
755
756 MOUse.setReg(ForwardedReg);
757
758 if (!CopySrc.isRenamable())
759 MOUse.setIsRenamable(false);
760 MOUse.setIsUndef(CopySrc.isUndef());
761
762 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
763
764 // Clear kill markers that may have been invalidated.
765 for (MachineInstr &KMI :
766 make_range(x: Copy->getIterator(), y: std::next(x: MI.getIterator())))
767 KMI.clearRegisterKills(Reg: CopySrcReg, RegInfo: TRI);
768
769 ++NumCopyForwards;
770 Changed = true;
771 }
772}
773
774void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) {
775 LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName()
776 << "\n");
777
778 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: MBB)) {
779 // Analyze copies (which don't overlap themselves).
780 std::optional<DestSourcePair> CopyOperands =
781 isCopyInstr(MI, TII: *TII, UseCopyInstr);
782 if (CopyOperands) {
783
784 Register RegSrc = CopyOperands->Source->getReg();
785 Register RegDef = CopyOperands->Destination->getReg();
786
787 if (!TRI->regsOverlap(RegA: RegDef, RegB: RegSrc)) {
788 assert(RegDef.isPhysical() && RegSrc.isPhysical() &&
789 "MachineCopyPropagation should be run after register allocation!");
790
791 MCRegister Def = RegDef.asMCReg();
792 MCRegister Src = RegSrc.asMCReg();
793
794 // The two copies cancel out and the source of the first copy
795 // hasn't been overridden, eliminate the second one. e.g.
796 // %ecx = COPY %eax
797 // ... nothing clobbered eax.
798 // %eax = COPY %ecx
799 // =>
800 // %ecx = COPY %eax
801 //
802 // or
803 //
804 // %ecx = COPY %eax
805 // ... nothing clobbered eax.
806 // %ecx = COPY %eax
807 // =>
808 // %ecx = COPY %eax
809 if (eraseIfRedundant(Copy&: MI, Src: Def, Def: Src) || eraseIfRedundant(Copy&: MI, Src, Def))
810 continue;
811
812 forwardUses(MI);
813
814 // Src may have been changed by forwardUses()
815 CopyOperands = isCopyInstr(MI, TII: *TII, UseCopyInstr);
816 Src = CopyOperands->Source->getReg().asMCReg();
817
818 // If Src is defined by a previous copy, the previous copy cannot be
819 // eliminated.
820 ReadRegister(Reg: Src, Reader&: MI, DT: RegularUse);
821 for (const MachineOperand &MO : MI.implicit_operands()) {
822 if (!MO.isReg() || !MO.readsReg())
823 continue;
824 MCRegister Reg = MO.getReg().asMCReg();
825 if (!Reg)
826 continue;
827 ReadRegister(Reg, Reader&: MI, DT: RegularUse);
828 }
829
830 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI.dump());
831
832 // Copy is now a candidate for deletion.
833 if (!MRI->isReserved(PhysReg: Def))
834 MaybeDeadCopies.insert(X: &MI);
835
836 // If 'Def' is previously source of another copy, then this earlier copy's
837 // source is no longer available. e.g.
838 // %xmm9 = copy %xmm2
839 // ...
840 // %xmm2 = copy %xmm0
841 // ...
842 // %xmm2 = copy %xmm9
843 Tracker.clobberRegister(Reg: Def, TRI: *TRI, TII: *TII, UseCopyInstr);
844 for (const MachineOperand &MO : MI.implicit_operands()) {
845 if (!MO.isReg() || !MO.isDef())
846 continue;
847 MCRegister Reg = MO.getReg().asMCReg();
848 if (!Reg)
849 continue;
850 Tracker.clobberRegister(Reg, TRI: *TRI, TII: *TII, UseCopyInstr);
851 }
852
853 Tracker.trackCopy(MI: &MI, TRI: *TRI, TII: *TII, UseCopyInstr);
854
855 continue;
856 }
857 }
858
859 // Clobber any earlyclobber regs first.
860 for (const MachineOperand &MO : MI.operands())
861 if (MO.isReg() && MO.isEarlyClobber()) {
862 MCRegister Reg = MO.getReg().asMCReg();
863 // If we have a tied earlyclobber, that means it is also read by this
864 // instruction, so we need to make sure we don't remove it as dead
865 // later.
866 if (MO.isTied())
867 ReadRegister(Reg, Reader&: MI, DT: RegularUse);
868 Tracker.clobberRegister(Reg, TRI: *TRI, TII: *TII, UseCopyInstr);
869 }
870
871 forwardUses(MI);
872
873 // Not a copy.
874 SmallVector<Register, 4> Defs;
875 const MachineOperand *RegMask = nullptr;
876 for (const MachineOperand &MO : MI.operands()) {
877 if (MO.isRegMask())
878 RegMask = &MO;
879 if (!MO.isReg())
880 continue;
881 Register Reg = MO.getReg();
882 if (!Reg)
883 continue;
884
885 assert(!Reg.isVirtual() &&
886 "MachineCopyPropagation should be run after register allocation!");
887
888 if (MO.isDef() && !MO.isEarlyClobber()) {
889 Defs.push_back(Elt: Reg.asMCReg());
890 continue;
891 } else if (MO.readsReg())
892 ReadRegister(Reg: Reg.asMCReg(), Reader&: MI, DT: MO.isDebug() ? DebugUse : RegularUse);
893 }
894
895 // The instruction has a register mask operand which means that it clobbers
896 // a large set of registers. Treat clobbered registers the same way as
897 // defined registers.
898 if (RegMask) {
899 // Erase any MaybeDeadCopies whose destination register is clobbered.
900 for (SmallSetVector<MachineInstr *, 8>::iterator DI =
901 MaybeDeadCopies.begin();
902 DI != MaybeDeadCopies.end();) {
903 MachineInstr *MaybeDead = *DI;
904 std::optional<DestSourcePair> CopyOperands =
905 isCopyInstr(MI: *MaybeDead, TII: *TII, UseCopyInstr);
906 MCRegister Reg = CopyOperands->Destination->getReg().asMCReg();
907 assert(!MRI->isReserved(Reg));
908
909 if (!RegMask->clobbersPhysReg(PhysReg: Reg)) {
910 ++DI;
911 continue;
912 }
913
914 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
915 MaybeDead->dump());
916
917 // Make sure we invalidate any entries in the copy maps before erasing
918 // the instruction.
919 Tracker.clobberRegister(Reg, TRI: *TRI, TII: *TII, UseCopyInstr);
920
921 // erase() will return the next valid iterator pointing to the next
922 // element after the erased one.
923 DI = MaybeDeadCopies.erase(I: DI);
924 MaybeDead->eraseFromParent();
925 Changed = true;
926 ++NumDeletes;
927 }
928 }
929
930 // Any previous copy definition or reading the Defs is no longer available.
931 for (MCRegister Reg : Defs)
932 Tracker.clobberRegister(Reg, TRI: *TRI, TII: *TII, UseCopyInstr);
933 }
934
935 bool TracksLiveness = MRI->tracksLiveness();
936
937 // If liveness is tracked, we can use the live-in lists to know which
938 // copies aren't dead.
939 if (TracksLiveness)
940 readSuccessorLiveIns(MBB);
941
942 // If MBB doesn't have succesor, delete copies whose defs are not used.
943 // If MBB does have successors, we can only delete copies if we are able to
944 // use liveness information from successors to confirm they are really dead.
945 if (MBB.succ_empty() || TracksLiveness) {
946 for (MachineInstr *MaybeDead : MaybeDeadCopies) {
947 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
948 MaybeDead->dump());
949
950 std::optional<DestSourcePair> CopyOperands =
951 isCopyInstr(MI: *MaybeDead, TII: *TII, UseCopyInstr);
952 assert(CopyOperands);
953
954 Register SrcReg = CopyOperands->Source->getReg();
955 Register DestReg = CopyOperands->Destination->getReg();
956 assert(!MRI->isReserved(DestReg));
957
958 // Update matching debug values, if any.
959 SmallVector<MachineInstr *> MaybeDeadDbgUsers(
960 CopyDbgUsers[MaybeDead].begin(), CopyDbgUsers[MaybeDead].end());
961 MRI->updateDbgUsersToReg(OldReg: DestReg.asMCReg(), NewReg: SrcReg.asMCReg(),
962 Users: MaybeDeadDbgUsers);
963
964 MaybeDead->eraseFromParent();
965 Changed = true;
966 ++NumDeletes;
967 }
968 }
969
970 MaybeDeadCopies.clear();
971 CopyDbgUsers.clear();
972 Tracker.clear();
973}
974
975static bool isBackwardPropagatableCopy(const DestSourcePair &CopyOperands,
976 const MachineRegisterInfo &MRI) {
977 Register Def = CopyOperands.Destination->getReg();
978 Register Src = CopyOperands.Source->getReg();
979
980 if (!Def || !Src)
981 return false;
982
983 if (MRI.isReserved(PhysReg: Def) || MRI.isReserved(PhysReg: Src))
984 return false;
985
986 return CopyOperands.Source->isRenamable() && CopyOperands.Source->isKill();
987}
988
989void MachineCopyPropagation::propagateDefs(MachineInstr &MI) {
990 if (!Tracker.hasAnyCopies())
991 return;
992
993 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd;
994 ++OpIdx) {
995 MachineOperand &MODef = MI.getOperand(i: OpIdx);
996
997 if (!MODef.isReg() || MODef.isUse())
998 continue;
999
1000 // Ignore non-trivial cases.
1001 if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit())
1002 continue;
1003
1004 if (!MODef.getReg())
1005 continue;
1006
1007 // We only handle if the register comes from a vreg.
1008 if (!MODef.isRenamable())
1009 continue;
1010
1011 MachineInstr *Copy = Tracker.findAvailBackwardCopy(
1012 I&: MI, Reg: MODef.getReg().asMCReg(), TRI: *TRI, TII: *TII, UseCopyInstr);
1013 if (!Copy)
1014 continue;
1015
1016 std::optional<DestSourcePair> CopyOperands =
1017 isCopyInstr(MI: *Copy, TII: *TII, UseCopyInstr);
1018 Register Def = CopyOperands->Destination->getReg();
1019 Register Src = CopyOperands->Source->getReg();
1020
1021 if (MODef.getReg() != Src)
1022 continue;
1023
1024 if (!isBackwardPropagatableRegClassCopy(Copy: *Copy, UseI: MI, UseIdx: OpIdx))
1025 continue;
1026
1027 if (hasImplicitOverlap(MI, Use: MODef))
1028 continue;
1029
1030 if (hasOverlappingMultipleDef(MI, MODef, Def))
1031 continue;
1032
1033 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI)
1034 << "\n with " << printReg(Def, TRI) << "\n in "
1035 << MI << " from " << *Copy);
1036
1037 MODef.setReg(Def);
1038 MODef.setIsRenamable(CopyOperands->Destination->isRenamable());
1039
1040 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
1041 MaybeDeadCopies.insert(X: Copy);
1042 Changed = true;
1043 ++NumCopyBackwardPropagated;
1044 }
1045}
1046
1047void MachineCopyPropagation::BackwardCopyPropagateBlock(
1048 MachineBasicBlock &MBB) {
1049 LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName()
1050 << "\n");
1051
1052 for (MachineInstr &MI : llvm::make_early_inc_range(Range: llvm::reverse(C&: MBB))) {
1053 // Ignore non-trivial COPYs.
1054 std::optional<DestSourcePair> CopyOperands =
1055 isCopyInstr(MI, TII: *TII, UseCopyInstr);
1056 if (CopyOperands && MI.getNumOperands() == 2) {
1057 Register DefReg = CopyOperands->Destination->getReg();
1058 Register SrcReg = CopyOperands->Source->getReg();
1059
1060 if (!TRI->regsOverlap(RegA: DefReg, RegB: SrcReg)) {
1061 // Unlike forward cp, we don't invoke propagateDefs here,
1062 // just let forward cp do COPY-to-COPY propagation.
1063 if (isBackwardPropagatableCopy(CopyOperands: *CopyOperands, MRI: *MRI)) {
1064 Tracker.invalidateRegister(Reg: SrcReg.asMCReg(), TRI: *TRI, TII: *TII,
1065 UseCopyInstr);
1066 Tracker.invalidateRegister(Reg: DefReg.asMCReg(), TRI: *TRI, TII: *TII,
1067 UseCopyInstr);
1068 Tracker.trackCopy(MI: &MI, TRI: *TRI, TII: *TII, UseCopyInstr);
1069 continue;
1070 }
1071 }
1072 }
1073
1074 // Invalidate any earlyclobber regs first.
1075 for (const MachineOperand &MO : MI.operands())
1076 if (MO.isReg() && MO.isEarlyClobber()) {
1077 MCRegister Reg = MO.getReg().asMCReg();
1078 if (!Reg)
1079 continue;
1080 Tracker.invalidateRegister(Reg, TRI: *TRI, TII: *TII, UseCopyInstr);
1081 }
1082
1083 propagateDefs(MI);
1084 for (const MachineOperand &MO : MI.operands()) {
1085 if (!MO.isReg())
1086 continue;
1087
1088 if (!MO.getReg())
1089 continue;
1090
1091 if (MO.isDef())
1092 Tracker.invalidateRegister(Reg: MO.getReg().asMCReg(), TRI: *TRI, TII: *TII,
1093 UseCopyInstr);
1094
1095 if (MO.readsReg()) {
1096 if (MO.isDebug()) {
1097 // Check if the register in the debug instruction is utilized
1098 // in a copy instruction, so we can update the debug info if the
1099 // register is changed.
1100 for (MCRegUnit Unit : TRI->regunits(Reg: MO.getReg().asMCReg())) {
1101 if (auto *Copy = Tracker.findCopyDefViaUnit(RegUnit: Unit, TRI: *TRI)) {
1102 CopyDbgUsers[Copy].insert(Ptr: &MI);
1103 }
1104 }
1105 } else {
1106 Tracker.invalidateRegister(Reg: MO.getReg().asMCReg(), TRI: *TRI, TII: *TII,
1107 UseCopyInstr);
1108 }
1109 }
1110 }
1111 }
1112
1113 for (auto *Copy : MaybeDeadCopies) {
1114 std::optional<DestSourcePair> CopyOperands =
1115 isCopyInstr(MI: *Copy, TII: *TII, UseCopyInstr);
1116 Register Src = CopyOperands->Source->getReg();
1117 Register Def = CopyOperands->Destination->getReg();
1118 SmallVector<MachineInstr *> MaybeDeadDbgUsers(CopyDbgUsers[Copy].begin(),
1119 CopyDbgUsers[Copy].end());
1120
1121 MRI->updateDbgUsersToReg(OldReg: Src.asMCReg(), NewReg: Def.asMCReg(), Users: MaybeDeadDbgUsers);
1122 Copy->eraseFromParent();
1123 ++NumDeletes;
1124 }
1125
1126 MaybeDeadCopies.clear();
1127 CopyDbgUsers.clear();
1128 Tracker.clear();
1129}
1130
1131static void LLVM_ATTRIBUTE_UNUSED printSpillReloadChain(
1132 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &SpillChain,
1133 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &ReloadChain,
1134 MachineInstr *Leader) {
1135 auto &SC = SpillChain[Leader];
1136 auto &RC = ReloadChain[Leader];
1137 for (auto I = SC.rbegin(), E = SC.rend(); I != E; ++I)
1138 (*I)->dump();
1139 for (MachineInstr *MI : RC)
1140 MI->dump();
1141}
1142
1143// Remove spill-reload like copy chains. For example
1144// r0 = COPY r1
1145// r1 = COPY r2
1146// r2 = COPY r3
1147// r3 = COPY r4
1148// <def-use r4>
1149// r4 = COPY r3
1150// r3 = COPY r2
1151// r2 = COPY r1
1152// r1 = COPY r0
1153// will be folded into
1154// r0 = COPY r1
1155// r1 = COPY r4
1156// <def-use r4>
1157// r4 = COPY r1
1158// r1 = COPY r0
1159// TODO: Currently we don't track usage of r0 outside the chain, so we
1160// conservatively keep its value as it was before the rewrite.
1161//
1162// The algorithm is trying to keep
1163// property#1: No Def of spill COPY in the chain is used or defined until the
1164// paired reload COPY in the chain uses the Def.
1165//
1166// property#2: NO Source of COPY in the chain is used or defined until the next
1167// COPY in the chain defines the Source, except the innermost spill-reload
1168// pair.
1169//
1170// The algorithm is conducted by checking every COPY inside the MBB, assuming
1171// the COPY is a reload COPY, then try to find paired spill COPY by searching
1172// the COPY defines the Src of the reload COPY backward. If such pair is found,
1173// it either belongs to an existing chain or a new chain depends on
1174// last available COPY uses the Def of the reload COPY.
1175// Implementation notes, we use CopyTracker::findLastDefCopy(Reg, ...) to find
1176// out last COPY that defines Reg; we use CopyTracker::findLastUseCopy(Reg, ...)
1177// to find out last COPY that uses Reg. When we are encountered with a Non-COPY
1178// instruction, we check registers in the operands of this instruction. If this
1179// Reg is defined by a COPY, we untrack this Reg via
1180// CopyTracker::clobberRegister(Reg, ...).
1181void MachineCopyPropagation::EliminateSpillageCopies(MachineBasicBlock &MBB) {
1182 // ChainLeader maps MI inside a spill-reload chain to its innermost reload COPY.
1183 // Thus we can track if a MI belongs to an existing spill-reload chain.
1184 DenseMap<MachineInstr *, MachineInstr *> ChainLeader;
1185 // SpillChain maps innermost reload COPY of a spill-reload chain to a sequence
1186 // of COPYs that forms spills of a spill-reload chain.
1187 // ReloadChain maps innermost reload COPY of a spill-reload chain to a
1188 // sequence of COPYs that forms reloads of a spill-reload chain.
1189 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> SpillChain, ReloadChain;
1190 // If a COPY's Source has use or def until next COPY defines the Source,
1191 // we put the COPY in this set to keep property#2.
1192 DenseSet<const MachineInstr *> CopySourceInvalid;
1193
1194 auto TryFoldSpillageCopies =
1195 [&, this](const SmallVectorImpl<MachineInstr *> &SC,
1196 const SmallVectorImpl<MachineInstr *> &RC) {
1197 assert(SC.size() == RC.size() && "Spill-reload should be paired");
1198
1199 // We need at least 3 pairs of copies for the transformation to apply,
1200 // because the first outermost pair cannot be removed since we don't
1201 // recolor outside of the chain and that we need at least one temporary
1202 // spill slot to shorten the chain. If we only have a chain of two
1203 // pairs, we already have the shortest sequence this code can handle:
1204 // the outermost pair for the temporary spill slot, and the pair that
1205 // use that temporary spill slot for the other end of the chain.
1206 // TODO: We might be able to simplify to one spill-reload pair if collecting
1207 // more infomation about the outermost COPY.
1208 if (SC.size() <= 2)
1209 return;
1210
1211 // If violate property#2, we don't fold the chain.
1212 for (const MachineInstr *Spill : drop_begin(RangeOrContainer: SC))
1213 if (CopySourceInvalid.count(V: Spill))
1214 return;
1215
1216 for (const MachineInstr *Reload : drop_end(RangeOrContainer: RC))
1217 if (CopySourceInvalid.count(V: Reload))
1218 return;
1219
1220 auto CheckCopyConstraint = [this](Register Def, Register Src) {
1221 for (const TargetRegisterClass *RC : TRI->regclasses()) {
1222 if (RC->contains(Reg: Def) && RC->contains(Reg: Src))
1223 return true;
1224 }
1225 return false;
1226 };
1227
1228 auto UpdateReg = [](MachineInstr *MI, const MachineOperand *Old,
1229 const MachineOperand *New) {
1230 for (MachineOperand &MO : MI->operands()) {
1231 if (&MO == Old)
1232 MO.setReg(New->getReg());
1233 }
1234 };
1235
1236 std::optional<DestSourcePair> InnerMostSpillCopy =
1237 isCopyInstr(MI: *SC[0], TII: *TII, UseCopyInstr);
1238 std::optional<DestSourcePair> OuterMostSpillCopy =
1239 isCopyInstr(MI: *SC.back(), TII: *TII, UseCopyInstr);
1240 std::optional<DestSourcePair> InnerMostReloadCopy =
1241 isCopyInstr(MI: *RC[0], TII: *TII, UseCopyInstr);
1242 std::optional<DestSourcePair> OuterMostReloadCopy =
1243 isCopyInstr(MI: *RC.back(), TII: *TII, UseCopyInstr);
1244 if (!CheckCopyConstraint(OuterMostSpillCopy->Source->getReg(),
1245 InnerMostSpillCopy->Source->getReg()) ||
1246 !CheckCopyConstraint(InnerMostReloadCopy->Destination->getReg(),
1247 OuterMostReloadCopy->Destination->getReg()))
1248 return;
1249
1250 SpillageChainsLength += SC.size() + RC.size();
1251 NumSpillageChains += 1;
1252 UpdateReg(SC[0], InnerMostSpillCopy->Destination,
1253 OuterMostSpillCopy->Source);
1254 UpdateReg(RC[0], InnerMostReloadCopy->Source,
1255 OuterMostReloadCopy->Destination);
1256
1257 for (size_t I = 1; I < SC.size() - 1; ++I) {
1258 SC[I]->eraseFromParent();
1259 RC[I]->eraseFromParent();
1260 NumDeletes += 2;
1261 }
1262 };
1263
1264 auto IsFoldableCopy = [this](const MachineInstr &MaybeCopy) {
1265 if (MaybeCopy.getNumImplicitOperands() > 0)
1266 return false;
1267 std::optional<DestSourcePair> CopyOperands =
1268 isCopyInstr(MI: MaybeCopy, TII: *TII, UseCopyInstr);
1269 if (!CopyOperands)
1270 return false;
1271 Register Src = CopyOperands->Source->getReg();
1272 Register Def = CopyOperands->Destination->getReg();
1273 return Src && Def && !TRI->regsOverlap(RegA: Src, RegB: Def) &&
1274 CopyOperands->Source->isRenamable() &&
1275 CopyOperands->Destination->isRenamable();
1276 };
1277
1278 auto IsSpillReloadPair = [&, this](const MachineInstr &Spill,
1279 const MachineInstr &Reload) {
1280 if (!IsFoldableCopy(Spill) || !IsFoldableCopy(Reload))
1281 return false;
1282 std::optional<DestSourcePair> SpillCopy =
1283 isCopyInstr(MI: Spill, TII: *TII, UseCopyInstr);
1284 std::optional<DestSourcePair> ReloadCopy =
1285 isCopyInstr(MI: Reload, TII: *TII, UseCopyInstr);
1286 if (!SpillCopy || !ReloadCopy)
1287 return false;
1288 return SpillCopy->Source->getReg() == ReloadCopy->Destination->getReg() &&
1289 SpillCopy->Destination->getReg() == ReloadCopy->Source->getReg();
1290 };
1291
1292 auto IsChainedCopy = [&, this](const MachineInstr &Prev,
1293 const MachineInstr &Current) {
1294 if (!IsFoldableCopy(Prev) || !IsFoldableCopy(Current))
1295 return false;
1296 std::optional<DestSourcePair> PrevCopy =
1297 isCopyInstr(MI: Prev, TII: *TII, UseCopyInstr);
1298 std::optional<DestSourcePair> CurrentCopy =
1299 isCopyInstr(MI: Current, TII: *TII, UseCopyInstr);
1300 if (!PrevCopy || !CurrentCopy)
1301 return false;
1302 return PrevCopy->Source->getReg() == CurrentCopy->Destination->getReg();
1303 };
1304
1305 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: MBB)) {
1306 std::optional<DestSourcePair> CopyOperands =
1307 isCopyInstr(MI, TII: *TII, UseCopyInstr);
1308
1309 // Update track information via non-copy instruction.
1310 SmallSet<Register, 8> RegsToClobber;
1311 if (!CopyOperands) {
1312 for (const MachineOperand &MO : MI.operands()) {
1313 if (!MO.isReg())
1314 continue;
1315 Register Reg = MO.getReg();
1316 if (!Reg)
1317 continue;
1318 MachineInstr *LastUseCopy =
1319 Tracker.findLastSeenUseInCopy(Reg: Reg.asMCReg(), TRI: *TRI);
1320 if (LastUseCopy) {
1321 LLVM_DEBUG(dbgs() << "MCP: Copy source of\n");
1322 LLVM_DEBUG(LastUseCopy->dump());
1323 LLVM_DEBUG(dbgs() << "might be invalidated by\n");
1324 LLVM_DEBUG(MI.dump());
1325 CopySourceInvalid.insert(V: LastUseCopy);
1326 }
1327 // Must be noted Tracker.clobberRegister(Reg, ...) removes tracking of
1328 // Reg, i.e, COPY that defines Reg is removed from the mapping as well
1329 // as marking COPYs that uses Reg unavailable.
1330 // We don't invoke CopyTracker::clobberRegister(Reg, ...) if Reg is not
1331 // defined by a previous COPY, since we don't want to make COPYs uses
1332 // Reg unavailable.
1333 if (Tracker.findLastSeenDefInCopy(Current: MI, Reg: Reg.asMCReg(), TRI: *TRI, TII: *TII,
1334 UseCopyInstr))
1335 // Thus we can keep the property#1.
1336 RegsToClobber.insert(V: Reg);
1337 }
1338 for (Register Reg : RegsToClobber) {
1339 Tracker.clobberRegister(Reg, TRI: *TRI, TII: *TII, UseCopyInstr);
1340 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Reg, TRI)
1341 << "\n");
1342 }
1343 continue;
1344 }
1345
1346 Register Src = CopyOperands->Source->getReg();
1347 Register Def = CopyOperands->Destination->getReg();
1348 // Check if we can find a pair spill-reload copy.
1349 LLVM_DEBUG(dbgs() << "MCP: Searching paired spill for reload: ");
1350 LLVM_DEBUG(MI.dump());
1351 MachineInstr *MaybeSpill =
1352 Tracker.findLastSeenDefInCopy(Current: MI, Reg: Src.asMCReg(), TRI: *TRI, TII: *TII, UseCopyInstr);
1353 bool MaybeSpillIsChained = ChainLeader.count(Val: MaybeSpill);
1354 if (!MaybeSpillIsChained && MaybeSpill &&
1355 IsSpillReloadPair(*MaybeSpill, MI)) {
1356 // Check if we already have an existing chain. Now we have a
1357 // spill-reload pair.
1358 // L2: r2 = COPY r3
1359 // L5: r3 = COPY r2
1360 // Looking for a valid COPY before L5 which uses r3.
1361 // This can be serverial cases.
1362 // Case #1:
1363 // No COPY is found, which can be r3 is def-use between (L2, L5), we
1364 // create a new chain for L2 and L5.
1365 // Case #2:
1366 // L2: r2 = COPY r3
1367 // L5: r3 = COPY r2
1368 // Such COPY is found and is L2, we create a new chain for L2 and L5.
1369 // Case #3:
1370 // L2: r2 = COPY r3
1371 // L3: r1 = COPY r3
1372 // L5: r3 = COPY r2
1373 // we create a new chain for L2 and L5.
1374 // Case #4:
1375 // L2: r2 = COPY r3
1376 // L3: r1 = COPY r3
1377 // L4: r3 = COPY r1
1378 // L5: r3 = COPY r2
1379 // Such COPY won't be found since L4 defines r3. we create a new chain
1380 // for L2 and L5.
1381 // Case #5:
1382 // L2: r2 = COPY r3
1383 // L3: r3 = COPY r1
1384 // L4: r1 = COPY r3
1385 // L5: r3 = COPY r2
1386 // COPY is found and is L4 which belongs to an existing chain, we add
1387 // L2 and L5 to this chain.
1388 LLVM_DEBUG(dbgs() << "MCP: Found spill: ");
1389 LLVM_DEBUG(MaybeSpill->dump());
1390 MachineInstr *MaybePrevReload =
1391 Tracker.findLastSeenUseInCopy(Reg: Def.asMCReg(), TRI: *TRI);
1392 auto Leader = ChainLeader.find(Val: MaybePrevReload);
1393 MachineInstr *L = nullptr;
1394 if (Leader == ChainLeader.end() ||
1395 (MaybePrevReload && !IsChainedCopy(*MaybePrevReload, MI))) {
1396 L = &MI;
1397 assert(!SpillChain.count(L) &&
1398 "SpillChain should not have contained newly found chain");
1399 } else {
1400 assert(MaybePrevReload &&
1401 "Found a valid leader through nullptr should not happend");
1402 L = Leader->second;
1403 assert(SpillChain[L].size() > 0 &&
1404 "Existing chain's length should be larger than zero");
1405 }
1406 assert(!ChainLeader.count(&MI) && !ChainLeader.count(MaybeSpill) &&
1407 "Newly found paired spill-reload should not belong to any chain "
1408 "at this point");
1409 ChainLeader.insert(KV: {MaybeSpill, L});
1410 ChainLeader.insert(KV: {&MI, L});
1411 SpillChain[L].push_back(Elt: MaybeSpill);
1412 ReloadChain[L].push_back(Elt: &MI);
1413 LLVM_DEBUG(dbgs() << "MCP: Chain " << L << " now is:\n");
1414 LLVM_DEBUG(printSpillReloadChain(SpillChain, ReloadChain, L));
1415 } else if (MaybeSpill && !MaybeSpillIsChained) {
1416 // MaybeSpill is unable to pair with MI. That's to say adding MI makes
1417 // the chain invalid.
1418 // The COPY defines Src is no longer considered as a candidate of a
1419 // valid chain. Since we expect the Def of a spill copy isn't used by
1420 // any COPY instruction until a reload copy. For example:
1421 // L1: r1 = COPY r2
1422 // L2: r3 = COPY r1
1423 // If we later have
1424 // L1: r1 = COPY r2
1425 // L2: r3 = COPY r1
1426 // L3: r2 = COPY r1
1427 // L1 and L3 can't be a valid spill-reload pair.
1428 // Thus we keep the property#1.
1429 LLVM_DEBUG(dbgs() << "MCP: Not paired spill-reload:\n");
1430 LLVM_DEBUG(MaybeSpill->dump());
1431 LLVM_DEBUG(MI.dump());
1432 Tracker.clobberRegister(Reg: Src.asMCReg(), TRI: *TRI, TII: *TII, UseCopyInstr);
1433 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Src, TRI)
1434 << "\n");
1435 }
1436 Tracker.trackCopy(MI: &MI, TRI: *TRI, TII: *TII, UseCopyInstr);
1437 }
1438
1439 for (auto I = SpillChain.begin(), E = SpillChain.end(); I != E; ++I) {
1440 auto &SC = I->second;
1441 assert(ReloadChain.count(I->first) &&
1442 "Reload chain of the same leader should exist");
1443 auto &RC = ReloadChain[I->first];
1444 TryFoldSpillageCopies(SC, RC);
1445 }
1446
1447 MaybeDeadCopies.clear();
1448 CopyDbgUsers.clear();
1449 Tracker.clear();
1450}
1451
1452bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
1453 if (skipFunction(F: MF.getFunction()))
1454 return false;
1455
1456 bool isSpillageCopyElimEnabled = false;
1457 switch (EnableSpillageCopyElimination) {
1458 case cl::BOU_UNSET:
1459 isSpillageCopyElimEnabled =
1460 MF.getSubtarget().enableSpillageCopyElimination();
1461 break;
1462 case cl::BOU_TRUE:
1463 isSpillageCopyElimEnabled = true;
1464 break;
1465 case cl::BOU_FALSE:
1466 isSpillageCopyElimEnabled = false;
1467 break;
1468 }
1469
1470 Changed = false;
1471
1472 TRI = MF.getSubtarget().getRegisterInfo();
1473 TII = MF.getSubtarget().getInstrInfo();
1474 MRI = &MF.getRegInfo();
1475
1476 for (MachineBasicBlock &MBB : MF) {
1477 if (isSpillageCopyElimEnabled)
1478 EliminateSpillageCopies(MBB);
1479 BackwardCopyPropagateBlock(MBB);
1480 ForwardCopyPropagateBlock(MBB);
1481 }
1482
1483 return Changed;
1484}
1485
1486MachineFunctionPass *
1487llvm::createMachineCopyPropagationPass(bool UseCopyInstr = false) {
1488 return new MachineCopyPropagation(UseCopyInstr);
1489}
1490