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