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