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