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 ForwardCopyPropagateBlock(MachineBasicBlock &MBB);
415 void BackwardCopyPropagateBlock(MachineBasicBlock &MBB);
416 void EliminateSpillageCopies(MachineBasicBlock &MBB);
417 bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def);
418 void forwardUses(MachineInstr &MI);
419 void propagateDefs(MachineInstr &MI);
420 bool isForwardableRegClassCopy(const MachineInstr &Copy,
421 const MachineInstr &UseI, unsigned UseIdx);
422 bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
423 const MachineInstr &UseI,
424 unsigned UseIdx);
425 bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
426 bool hasOverlappingMultipleDef(const MachineInstr &MI,
427 const MachineOperand &MODef, Register Def);
428
429 /// Candidates for deletion.
430 SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
431
432 /// Multimap tracking debug users in current BB
434
435 CopyTracker Tracker;
436
437 bool Changed = false;
438};
439
440} // end anonymous namespace
441
442char MachineCopyPropagation::ID = 0;
443
444char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
445
446INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
447 "Machine Copy Propagation Pass", false, false)
448
449void MachineCopyPropagation::ReadRegister(MCRegister Reg, MachineInstr &Reader,
450 DebugType DT) {
451 // If 'Reg' is defined by a copy, the copy is no longer a candidate
452 // for elimination. If a copy is "read" by a debug user, record the user
453 // for propagation.
454 for (MCRegUnit Unit : TRI->regunits(Reg)) {
455 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI)) {
456 if (DT == RegularUse) {
457 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
458 MaybeDeadCopies.remove(Copy);
459 } else {
460 CopyDbgUsers[Copy].insert(&Reader);
461 }
462 }
463 }
464}
465
466/// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
467/// This fact may have been obscured by sub register usage or may not be true at
468/// all even though Src and Def are subregisters of the registers used in
469/// PreviousCopy. e.g.
470/// isNopCopy("ecx = COPY eax", AX, CX) == true
471/// isNopCopy("ecx = COPY eax", AH, CL) == false
472static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src,
474 const TargetInstrInfo *TII, bool UseCopyInstr) {
475
476 std::optional<DestSourcePair> CopyOperands =
477 isCopyInstr(PreviousCopy, *TII, UseCopyInstr);
478 MCRegister PreviousSrc = CopyOperands->Source->getReg().asMCReg();
479 MCRegister PreviousDef = CopyOperands->Destination->getReg().asMCReg();
480 if (Src == PreviousSrc && Def == PreviousDef)
481 return true;
482 if (!TRI->isSubRegister(PreviousSrc, Src))
483 return false;
484 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
485 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
486}
487
488/// Remove instruction \p Copy if there exists a previous copy that copies the
489/// register \p Src to the register \p Def; This may happen indirectly by
490/// copying the super registers.
491bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy,
492 MCRegister Src, MCRegister Def) {
493 // Avoid eliminating a copy from/to a reserved registers as we cannot predict
494 // the value (Example: The sparc zero register is writable but stays zero).
495 if (MRI->isReserved(Src) || MRI->isReserved(Def))
496 return false;
497
498 // Search for an existing copy.
499 MachineInstr *PrevCopy =
500 Tracker.findAvailCopy(Copy, Def, *TRI, *TII, UseCopyInstr);
501 if (!PrevCopy)
502 return false;
503
504 auto PrevCopyOperands = isCopyInstr(*PrevCopy, *TII, UseCopyInstr);
505 // Check that the existing copy uses the correct sub registers.
506 if (PrevCopyOperands->Destination->isDead())
507 return false;
508 if (!isNopCopy(*PrevCopy, Src, Def, TRI, TII, UseCopyInstr))
509 return false;
510
511 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
512
513 // Copy was redundantly redefining either Src or Def. Remove earlier kill
514 // flags between Copy and PrevCopy because the value will be reused now.
515 std::optional<DestSourcePair> CopyOperands =
516 isCopyInstr(Copy, *TII, UseCopyInstr);
517 assert(CopyOperands);
518
519 Register CopyDef = CopyOperands->Destination->getReg();
520 assert(CopyDef == Src || CopyDef == Def);
521 for (MachineInstr &MI :
522 make_range(PrevCopy->getIterator(), Copy.getIterator()))
523 MI.clearRegisterKills(CopyDef, TRI);
524
525 // Clear undef flag from remaining copy if needed.
526 if (!CopyOperands->Source->isUndef()) {
527 PrevCopy->getOperand(PrevCopyOperands->Source->getOperandNo())
528 .setIsUndef(false);
529 }
530
531 Copy.eraseFromParent();
532 Changed = true;
533 ++NumDeletes;
534 return true;
535}
536
537bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(
538 const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) {
539 std::optional<DestSourcePair> CopyOperands =
540 isCopyInstr(Copy, *TII, UseCopyInstr);
541 Register Def = CopyOperands->Destination->getReg();
542
543 if (const TargetRegisterClass *URC =
544 UseI.getRegClassConstraint(UseIdx, TII, TRI))
545 return URC->contains(Def);
546
547 // We don't process further if UseI is a COPY, since forward copy propagation
548 // should handle that.
549 return false;
550}
551
552/// Decide whether we should forward the source of \param Copy to its use in
553/// \param UseI based on the physical register class constraints of the opcode
554/// and avoiding introducing more cross-class COPYs.
555bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
556 const MachineInstr &UseI,
557 unsigned UseIdx) {
558 std::optional<DestSourcePair> CopyOperands =
559 isCopyInstr(Copy, *TII, UseCopyInstr);
560 Register CopySrcReg = CopyOperands->Source->getReg();
561
562 // If the new register meets the opcode register constraints, then allow
563 // forwarding.
564 if (const TargetRegisterClass *URC =
565 UseI.getRegClassConstraint(UseIdx, TII, TRI))
566 return URC->contains(CopySrcReg);
567
568 auto UseICopyOperands = isCopyInstr(UseI, *TII, UseCopyInstr);
569 if (!UseICopyOperands)
570 return false;
571
572 /// COPYs don't have register class constraints, so if the user instruction
573 /// is a COPY, we just try to avoid introducing additional cross-class
574 /// COPYs. For example:
575 ///
576 /// RegClassA = COPY RegClassB // Copy parameter
577 /// ...
578 /// RegClassB = COPY RegClassA // UseI parameter
579 ///
580 /// which after forwarding becomes
581 ///
582 /// RegClassA = COPY RegClassB
583 /// ...
584 /// RegClassB = COPY RegClassB
585 ///
586 /// so we have reduced the number of cross-class COPYs and potentially
587 /// introduced a nop COPY that can be removed.
588
589 // Allow forwarding if src and dst belong to any common class, so long as they
590 // don't belong to any (possibly smaller) common class that requires copies to
591 // go via a different class.
592 Register UseDstReg = UseICopyOperands->Destination->getReg();
593 bool Found = false;
594 bool IsCrossClass = false;
595 for (const TargetRegisterClass *RC : TRI->regclasses()) {
596 if (RC->contains(CopySrcReg) && RC->contains(UseDstReg)) {
597 Found = true;
598 if (TRI->getCrossCopyRegClass(RC) != RC) {
599 IsCrossClass = true;
600 break;
601 }
602 }
603 }
604 if (!Found)
605 return false;
606 if (!IsCrossClass)
607 return true;
608 // The forwarded copy would be cross-class. Only do this if the original copy
609 // was also cross-class.
610 Register CopyDstReg = CopyOperands->Destination->getReg();
611 for (const TargetRegisterClass *RC : TRI->regclasses()) {
612 if (RC->contains(CopySrcReg) && RC->contains(CopyDstReg) &&
613 TRI->getCrossCopyRegClass(RC) != RC)
614 return true;
615 }
616 return false;
617}
618
619/// Check that \p MI does not have implicit uses that overlap with it's \p Use
620/// operand (the register being replaced), since these can sometimes be
621/// implicitly tied to other operands. For example, on AMDGPU:
622///
623/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
624///
625/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
626/// way of knowing we need to update the latter when updating the former.
627bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
628 const MachineOperand &Use) {
629 for (const MachineOperand &MIUse : MI.uses())
630 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
631 MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
632 return true;
633
634 return false;
635}
636
637/// For an MI that has multiple definitions, check whether \p MI has
638/// a definition that overlaps with another of its definitions.
639/// For example, on ARM: umull r9, r9, lr, r0
640/// The umull instruction is unpredictable unless RdHi and RdLo are different.
641bool MachineCopyPropagation::hasOverlappingMultipleDef(
642 const MachineInstr &MI, const MachineOperand &MODef, Register Def) {
643 for (const MachineOperand &MIDef : MI.defs()) {
644 if ((&MIDef != &MODef) && MIDef.isReg() &&
645 TRI->regsOverlap(Def, MIDef.getReg()))
646 return true;
647 }
648
649 return false;
650}
651
652/// Look for available copies whose destination register is used by \p MI and
653/// replace the use in \p MI with the copy's source register.
654void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
655 if (!Tracker.hasAnyCopies())
656 return;
657
658 // Look for non-tied explicit vreg uses that have an active COPY
659 // instruction that defines the physical register allocated to them.
660 // Replace the vreg with the source of the active COPY.
661 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
662 ++OpIdx) {
663 MachineOperand &MOUse = MI.getOperand(OpIdx);
664 // Don't forward into undef use operands since doing so can cause problems
665 // with the machine verifier, since it doesn't treat undef reads as reads,
666 // so we can end up with a live range that ends on an undef read, leading to
667 // an error that the live range doesn't end on a read of the live range
668 // register.
669 if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
670 MOUse.isImplicit())
671 continue;
672
673 if (!MOUse.getReg())
674 continue;
675
676 // Check that the register is marked 'renamable' so we know it is safe to
677 // rename it without violating any constraints that aren't expressed in the
678 // IR (e.g. ABI or opcode requirements).
679 if (!MOUse.isRenamable())
680 continue;
681
682 MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg().asMCReg(),
683 *TRI, *TII, UseCopyInstr);
684 if (!Copy)
685 continue;
686
687 std::optional<DestSourcePair> CopyOperands =
688 isCopyInstr(*Copy, *TII, UseCopyInstr);
689 Register CopyDstReg = CopyOperands->Destination->getReg();
690 const MachineOperand &CopySrc = *CopyOperands->Source;
691 Register CopySrcReg = CopySrc.getReg();
692
693 Register ForwardedReg = CopySrcReg;
694 // MI might use a sub-register of the Copy destination, in which case the
695 // forwarded register is the matching sub-register of the Copy source.
696 if (MOUse.getReg() != CopyDstReg) {
697 unsigned SubRegIdx = TRI->getSubRegIndex(CopyDstReg, MOUse.getReg());
698 assert(SubRegIdx &&
699 "MI source is not a sub-register of Copy destination");
700 ForwardedReg = TRI->getSubReg(CopySrcReg, SubRegIdx);
701 if (!ForwardedReg) {
702 LLVM_DEBUG(dbgs() << "MCP: Copy source does not have sub-register "
703 << TRI->getSubRegIndexName(SubRegIdx) << '\n');
704 continue;
705 }
706 }
707
708 // Don't forward COPYs of reserved regs unless they are constant.
709 if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
710 continue;
711
712 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
713 continue;
714
715 if (hasImplicitOverlap(MI, MOUse))
716 continue;
717
718 // Check that the instruction is not a copy that partially overwrites the
719 // original copy source that we are about to use. The tracker mechanism
720 // cannot cope with that.
721 if (isCopyInstr(MI, *TII, UseCopyInstr) &&
722 MI.modifiesRegister(CopySrcReg, TRI) &&
723 !MI.definesRegister(CopySrcReg)) {
724 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI);
725 continue;
726 }
727
728 if (!DebugCounter::shouldExecute(FwdCounter)) {
729 LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "
730 << MI);
731 continue;
732 }
733
734 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
735 << "\n with " << printReg(ForwardedReg, TRI)
736 << "\n in " << MI << " from " << *Copy);
737
738 MOUse.setReg(ForwardedReg);
739
740 if (!CopySrc.isRenamable())
741 MOUse.setIsRenamable(false);
742 MOUse.setIsUndef(CopySrc.isUndef());
743
744 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
745
746 // Clear kill markers that may have been invalidated.
747 for (MachineInstr &KMI :
748 make_range(Copy->getIterator(), std::next(MI.getIterator())))
749 KMI.clearRegisterKills(CopySrcReg, TRI);
750
751 ++NumCopyForwards;
752 Changed = true;
753 }
754}
755
756void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) {
757 LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName()
758 << "\n");
759
761 // Analyze copies (which don't overlap themselves).
762 std::optional<DestSourcePair> CopyOperands =
763 isCopyInstr(MI, *TII, UseCopyInstr);
764 if (CopyOperands) {
765
766 Register RegSrc = CopyOperands->Source->getReg();
767 Register RegDef = CopyOperands->Destination->getReg();
768
769 if (!TRI->regsOverlap(RegDef, RegSrc)) {
770 assert(RegDef.isPhysical() && RegSrc.isPhysical() &&
771 "MachineCopyPropagation should be run after register allocation!");
772
773 MCRegister Def = RegDef.asMCReg();
774 MCRegister Src = RegSrc.asMCReg();
775
776 // The two copies cancel out and the source of the first copy
777 // hasn't been overridden, eliminate the second one. e.g.
778 // %ecx = COPY %eax
779 // ... nothing clobbered eax.
780 // %eax = COPY %ecx
781 // =>
782 // %ecx = COPY %eax
783 //
784 // or
785 //
786 // %ecx = COPY %eax
787 // ... nothing clobbered eax.
788 // %ecx = COPY %eax
789 // =>
790 // %ecx = COPY %eax
791 if (eraseIfRedundant(MI, Def, Src) || eraseIfRedundant(MI, Src, Def))
792 continue;
793
794 forwardUses(MI);
795
796 // Src may have been changed by forwardUses()
797 CopyOperands = isCopyInstr(MI, *TII, UseCopyInstr);
798 Src = CopyOperands->Source->getReg().asMCReg();
799
800 // If Src is defined by a previous copy, the previous copy cannot be
801 // eliminated.
802 ReadRegister(Src, MI, RegularUse);
803 for (const MachineOperand &MO : MI.implicit_operands()) {
804 if (!MO.isReg() || !MO.readsReg())
805 continue;
806 MCRegister Reg = MO.getReg().asMCReg();
807 if (!Reg)
808 continue;
809 ReadRegister(Reg, MI, RegularUse);
810 }
811
812 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI.dump());
813
814 // Copy is now a candidate for deletion.
815 if (!MRI->isReserved(Def))
816 MaybeDeadCopies.insert(&MI);
817
818 // If 'Def' is previously source of another copy, then this earlier copy's
819 // source is no longer available. e.g.
820 // %xmm9 = copy %xmm2
821 // ...
822 // %xmm2 = copy %xmm0
823 // ...
824 // %xmm2 = copy %xmm9
825 Tracker.clobberRegister(Def, *TRI, *TII, UseCopyInstr);
826 for (const MachineOperand &MO : MI.implicit_operands()) {
827 if (!MO.isReg() || !MO.isDef())
828 continue;
829 MCRegister Reg = MO.getReg().asMCReg();
830 if (!Reg)
831 continue;
832 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
833 }
834
835 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);
836
837 continue;
838 }
839 }
840
841 // Clobber any earlyclobber regs first.
842 for (const MachineOperand &MO : MI.operands())
843 if (MO.isReg() && MO.isEarlyClobber()) {
844 MCRegister Reg = MO.getReg().asMCReg();
845 // If we have a tied earlyclobber, that means it is also read by this
846 // instruction, so we need to make sure we don't remove it as dead
847 // later.
848 if (MO.isTied())
849 ReadRegister(Reg, MI, RegularUse);
850 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
851 }
852
853 forwardUses(MI);
854
855 // Not a copy.
857 const MachineOperand *RegMask = nullptr;
858 for (const MachineOperand &MO : MI.operands()) {
859 if (MO.isRegMask())
860 RegMask = &MO;
861 if (!MO.isReg())
862 continue;
863 Register Reg = MO.getReg();
864 if (!Reg)
865 continue;
866
867 assert(!Reg.isVirtual() &&
868 "MachineCopyPropagation should be run after register allocation!");
869
870 if (MO.isDef() && !MO.isEarlyClobber()) {
871 Defs.push_back(Reg.asMCReg());
872 continue;
873 } else if (MO.readsReg())
874 ReadRegister(Reg.asMCReg(), MI, MO.isDebug() ? DebugUse : RegularUse);
875 }
876
877 // The instruction has a register mask operand which means that it clobbers
878 // a large set of registers. Treat clobbered registers the same way as
879 // defined registers.
880 if (RegMask) {
881 // Erase any MaybeDeadCopies whose destination register is clobbered.
883 MaybeDeadCopies.begin();
884 DI != MaybeDeadCopies.end();) {
885 MachineInstr *MaybeDead = *DI;
886 std::optional<DestSourcePair> CopyOperands =
887 isCopyInstr(*MaybeDead, *TII, UseCopyInstr);
888 MCRegister Reg = CopyOperands->Destination->getReg().asMCReg();
889 assert(!MRI->isReserved(Reg));
890
891 if (!RegMask->clobbersPhysReg(Reg)) {
892 ++DI;
893 continue;
894 }
895
896 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
897 MaybeDead->dump());
898
899 // Make sure we invalidate any entries in the copy maps before erasing
900 // the instruction.
901 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
902
903 // erase() will return the next valid iterator pointing to the next
904 // element after the erased one.
905 DI = MaybeDeadCopies.erase(DI);
906 MaybeDead->eraseFromParent();
907 Changed = true;
908 ++NumDeletes;
909 }
910 }
911
912 // Any previous copy definition or reading the Defs is no longer available.
913 for (MCRegister Reg : Defs)
914 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
915 }
916
917 // If MBB doesn't have successors, delete the copies whose defs are not used.
918 // If MBB does have successors, then conservative assume the defs are live-out
919 // since we don't want to trust live-in lists.
920 if (MBB.succ_empty()) {
921 for (MachineInstr *MaybeDead : MaybeDeadCopies) {
922 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
923 MaybeDead->dump());
924
925 std::optional<DestSourcePair> CopyOperands =
926 isCopyInstr(*MaybeDead, *TII, UseCopyInstr);
927 assert(CopyOperands);
928
929 Register SrcReg = CopyOperands->Source->getReg();
930 Register DestReg = CopyOperands->Destination->getReg();
931 assert(!MRI->isReserved(DestReg));
932
933 // Update matching debug values, if any.
934 SmallVector<MachineInstr *> MaybeDeadDbgUsers(
935 CopyDbgUsers[MaybeDead].begin(), CopyDbgUsers[MaybeDead].end());
936 MRI->updateDbgUsersToReg(DestReg.asMCReg(), SrcReg.asMCReg(),
937 MaybeDeadDbgUsers);
938
939 MaybeDead->eraseFromParent();
940 Changed = true;
941 ++NumDeletes;
942 }
943 }
944
945 MaybeDeadCopies.clear();
946 CopyDbgUsers.clear();
947 Tracker.clear();
948}
949
950static bool isBackwardPropagatableCopy(const DestSourcePair &CopyOperands,
952 const TargetInstrInfo &TII) {
953 Register Def = CopyOperands.Destination->getReg();
954 Register Src = CopyOperands.Source->getReg();
955
956 if (!Def || !Src)
957 return false;
958
959 if (MRI.isReserved(Def) || MRI.isReserved(Src))
960 return false;
961
962 return CopyOperands.Source->isRenamable() && CopyOperands.Source->isKill();
963}
964
965void MachineCopyPropagation::propagateDefs(MachineInstr &MI) {
966 if (!Tracker.hasAnyCopies())
967 return;
968
969 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd;
970 ++OpIdx) {
971 MachineOperand &MODef = MI.getOperand(OpIdx);
972
973 if (!MODef.isReg() || MODef.isUse())
974 continue;
975
976 // Ignore non-trivial cases.
977 if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit())
978 continue;
979
980 if (!MODef.getReg())
981 continue;
982
983 // We only handle if the register comes from a vreg.
984 if (!MODef.isRenamable())
985 continue;
986
987 MachineInstr *Copy = Tracker.findAvailBackwardCopy(
988 MI, MODef.getReg().asMCReg(), *TRI, *TII, UseCopyInstr);
989 if (!Copy)
990 continue;
991
992 std::optional<DestSourcePair> CopyOperands =
993 isCopyInstr(*Copy, *TII, UseCopyInstr);
994 Register Def = CopyOperands->Destination->getReg();
995 Register Src = CopyOperands->Source->getReg();
996
997 if (MODef.getReg() != Src)
998 continue;
999
1000 if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx))
1001 continue;
1002
1003 if (hasImplicitOverlap(MI, MODef))
1004 continue;
1005
1006 if (hasOverlappingMultipleDef(MI, MODef, Def))
1007 continue;
1008
1009 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI)
1010 << "\n with " << printReg(Def, TRI) << "\n in "
1011 << MI << " from " << *Copy);
1012
1013 MODef.setReg(Def);
1014 MODef.setIsRenamable(CopyOperands->Destination->isRenamable());
1015
1016 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
1017 MaybeDeadCopies.insert(Copy);
1018 Changed = true;
1019 ++NumCopyBackwardPropagated;
1020 }
1021}
1022
1023void MachineCopyPropagation::BackwardCopyPropagateBlock(
1025 LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName()
1026 << "\n");
1027
1029 // Ignore non-trivial COPYs.
1030 std::optional<DestSourcePair> CopyOperands =
1031 isCopyInstr(MI, *TII, UseCopyInstr);
1032 if (CopyOperands && MI.getNumOperands() == 2) {
1033 Register DefReg = CopyOperands->Destination->getReg();
1034 Register SrcReg = CopyOperands->Source->getReg();
1035
1036 if (!TRI->regsOverlap(DefReg, SrcReg)) {
1037 // Unlike forward cp, we don't invoke propagateDefs here,
1038 // just let forward cp do COPY-to-COPY propagation.
1039 if (isBackwardPropagatableCopy(*CopyOperands, *MRI, *TII)) {
1040 Tracker.invalidateRegister(SrcReg.asMCReg(), *TRI, *TII,
1041 UseCopyInstr);
1042 Tracker.invalidateRegister(DefReg.asMCReg(), *TRI, *TII,
1043 UseCopyInstr);
1044 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);
1045 continue;
1046 }
1047 }
1048 }
1049
1050 // Invalidate any earlyclobber regs first.
1051 for (const MachineOperand &MO : MI.operands())
1052 if (MO.isReg() && MO.isEarlyClobber()) {
1053 MCRegister Reg = MO.getReg().asMCReg();
1054 if (!Reg)
1055 continue;
1056 Tracker.invalidateRegister(Reg, *TRI, *TII, UseCopyInstr);
1057 }
1058
1059 propagateDefs(MI);
1060 for (const MachineOperand &MO : MI.operands()) {
1061 if (!MO.isReg())
1062 continue;
1063
1064 if (!MO.getReg())
1065 continue;
1066
1067 if (MO.isDef())
1068 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII,
1069 UseCopyInstr);
1070
1071 if (MO.readsReg()) {
1072 if (MO.isDebug()) {
1073 // Check if the register in the debug instruction is utilized
1074 // in a copy instruction, so we can update the debug info if the
1075 // register is changed.
1076 for (MCRegUnit Unit : TRI->regunits(MO.getReg().asMCReg())) {
1077 if (auto *Copy = Tracker.findCopyDefViaUnit(Unit, *TRI)) {
1078 CopyDbgUsers[Copy].insert(&MI);
1079 }
1080 }
1081 } else {
1082 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII,
1083 UseCopyInstr);
1084 }
1085 }
1086 }
1087 }
1088
1089 for (auto *Copy : MaybeDeadCopies) {
1090 std::optional<DestSourcePair> CopyOperands =
1091 isCopyInstr(*Copy, *TII, UseCopyInstr);
1092 Register Src = CopyOperands->Source->getReg();
1093 Register Def = CopyOperands->Destination->getReg();
1094 SmallVector<MachineInstr *> MaybeDeadDbgUsers(CopyDbgUsers[Copy].begin(),
1095 CopyDbgUsers[Copy].end());
1096
1097 MRI->updateDbgUsersToReg(Src.asMCReg(), Def.asMCReg(), MaybeDeadDbgUsers);
1098 Copy->eraseFromParent();
1099 ++NumDeletes;
1100 }
1101
1102 MaybeDeadCopies.clear();
1103 CopyDbgUsers.clear();
1104 Tracker.clear();
1105}
1106
1110 MachineInstr *Leader) {
1111 auto &SC = SpillChain[Leader];
1112 auto &RC = ReloadChain[Leader];
1113 for (auto I = SC.rbegin(), E = SC.rend(); I != E; ++I)
1114 (*I)->dump();
1115 for (MachineInstr *MI : RC)
1116 MI->dump();
1117}
1118
1119// Remove spill-reload like copy chains. For example
1120// r0 = COPY r1
1121// r1 = COPY r2
1122// r2 = COPY r3
1123// r3 = COPY r4
1124// <def-use r4>
1125// r4 = COPY r3
1126// r3 = COPY r2
1127// r2 = COPY r1
1128// r1 = COPY r0
1129// will be folded into
1130// r0 = COPY r1
1131// r1 = COPY r4
1132// <def-use r4>
1133// r4 = COPY r1
1134// r1 = COPY r0
1135// TODO: Currently we don't track usage of r0 outside the chain, so we
1136// conservatively keep its value as it was before the rewrite.
1137//
1138// The algorithm is trying to keep
1139// property#1: No Def of spill COPY in the chain is used or defined until the
1140// paired reload COPY in the chain uses the Def.
1141//
1142// property#2: NO Source of COPY in the chain is used or defined until the next
1143// COPY in the chain defines the Source, except the innermost spill-reload
1144// pair.
1145//
1146// The algorithm is conducted by checking every COPY inside the MBB, assuming
1147// the COPY is a reload COPY, then try to find paired spill COPY by searching
1148// the COPY defines the Src of the reload COPY backward. If such pair is found,
1149// it either belongs to an existing chain or a new chain depends on
1150// last available COPY uses the Def of the reload COPY.
1151// Implementation notes, we use CopyTracker::findLastDefCopy(Reg, ...) to find
1152// out last COPY that defines Reg; we use CopyTracker::findLastUseCopy(Reg, ...)
1153// to find out last COPY that uses Reg. When we are encountered with a Non-COPY
1154// instruction, we check registers in the operands of this instruction. If this
1155// Reg is defined by a COPY, we untrack this Reg via
1156// CopyTracker::clobberRegister(Reg, ...).
1157void MachineCopyPropagation::EliminateSpillageCopies(MachineBasicBlock &MBB) {
1158 // ChainLeader maps MI inside a spill-reload chain to its innermost reload COPY.
1159 // Thus we can track if a MI belongs to an existing spill-reload chain.
1161 // SpillChain maps innermost reload COPY of a spill-reload chain to a sequence
1162 // of COPYs that forms spills of a spill-reload chain.
1163 // ReloadChain maps innermost reload COPY of a spill-reload chain to a
1164 // sequence of COPYs that forms reloads of a spill-reload chain.
1166 // If a COPY's Source has use or def until next COPY defines the Source,
1167 // we put the COPY in this set to keep property#2.
1168 DenseSet<const MachineInstr *> CopySourceInvalid;
1169
1170 auto TryFoldSpillageCopies =
1171 [&, this](const SmallVectorImpl<MachineInstr *> &SC,
1173 assert(SC.size() == RC.size() && "Spill-reload should be paired");
1174
1175 // We need at least 3 pairs of copies for the transformation to apply,
1176 // because the first outermost pair cannot be removed since we don't
1177 // recolor outside of the chain and that we need at least one temporary
1178 // spill slot to shorten the chain. If we only have a chain of two
1179 // pairs, we already have the shortest sequence this code can handle:
1180 // the outermost pair for the temporary spill slot, and the pair that
1181 // use that temporary spill slot for the other end of the chain.
1182 // TODO: We might be able to simplify to one spill-reload pair if collecting
1183 // more infomation about the outermost COPY.
1184 if (SC.size() <= 2)
1185 return;
1186
1187 // If violate property#2, we don't fold the chain.
1188 for (const MachineInstr *Spill : drop_begin(SC))
1189 if (CopySourceInvalid.count(Spill))
1190 return;
1191
1192 for (const MachineInstr *Reload : drop_end(RC))
1193 if (CopySourceInvalid.count(Reload))
1194 return;
1195
1196 auto CheckCopyConstraint = [this](Register Def, Register Src) {
1197 for (const TargetRegisterClass *RC : TRI->regclasses()) {
1198 if (RC->contains(Def) && RC->contains(Src))
1199 return true;
1200 }
1201 return false;
1202 };
1203
1204 auto UpdateReg = [](MachineInstr *MI, const MachineOperand *Old,
1205 const MachineOperand *New) {
1206 for (MachineOperand &MO : MI->operands()) {
1207 if (&MO == Old)
1208 MO.setReg(New->getReg());
1209 }
1210 };
1211
1212 std::optional<DestSourcePair> InnerMostSpillCopy =
1213 isCopyInstr(*SC[0], *TII, UseCopyInstr);
1214 std::optional<DestSourcePair> OuterMostSpillCopy =
1215 isCopyInstr(*SC.back(), *TII, UseCopyInstr);
1216 std::optional<DestSourcePair> InnerMostReloadCopy =
1217 isCopyInstr(*RC[0], *TII, UseCopyInstr);
1218 std::optional<DestSourcePair> OuterMostReloadCopy =
1219 isCopyInstr(*RC.back(), *TII, UseCopyInstr);
1220 if (!CheckCopyConstraint(OuterMostSpillCopy->Source->getReg(),
1221 InnerMostSpillCopy->Source->getReg()) ||
1222 !CheckCopyConstraint(InnerMostReloadCopy->Destination->getReg(),
1223 OuterMostReloadCopy->Destination->getReg()))
1224 return;
1225
1226 SpillageChainsLength += SC.size() + RC.size();
1227 NumSpillageChains += 1;
1228 UpdateReg(SC[0], InnerMostSpillCopy->Destination,
1229 OuterMostSpillCopy->Source);
1230 UpdateReg(RC[0], InnerMostReloadCopy->Source,
1231 OuterMostReloadCopy->Destination);
1232
1233 for (size_t I = 1; I < SC.size() - 1; ++I) {
1234 SC[I]->eraseFromParent();
1235 RC[I]->eraseFromParent();
1236 NumDeletes += 2;
1237 }
1238 };
1239
1240 auto IsFoldableCopy = [this](const MachineInstr &MaybeCopy) {
1241 if (MaybeCopy.getNumImplicitOperands() > 0)
1242 return false;
1243 std::optional<DestSourcePair> CopyOperands =
1244 isCopyInstr(MaybeCopy, *TII, UseCopyInstr);
1245 if (!CopyOperands)
1246 return false;
1247 Register Src = CopyOperands->Source->getReg();
1248 Register Def = CopyOperands->Destination->getReg();
1249 return Src && Def && !TRI->regsOverlap(Src, Def) &&
1250 CopyOperands->Source->isRenamable() &&
1251 CopyOperands->Destination->isRenamable();
1252 };
1253
1254 auto IsSpillReloadPair = [&, this](const MachineInstr &Spill,
1255 const MachineInstr &Reload) {
1256 if (!IsFoldableCopy(Spill) || !IsFoldableCopy(Reload))
1257 return false;
1258 std::optional<DestSourcePair> SpillCopy =
1259 isCopyInstr(Spill, *TII, UseCopyInstr);
1260 std::optional<DestSourcePair> ReloadCopy =
1261 isCopyInstr(Reload, *TII, UseCopyInstr);
1262 if (!SpillCopy || !ReloadCopy)
1263 return false;
1264 return SpillCopy->Source->getReg() == ReloadCopy->Destination->getReg() &&
1265 SpillCopy->Destination->getReg() == ReloadCopy->Source->getReg();
1266 };
1267
1268 auto IsChainedCopy = [&, this](const MachineInstr &Prev,
1269 const MachineInstr &Current) {
1270 if (!IsFoldableCopy(Prev) || !IsFoldableCopy(Current))
1271 return false;
1272 std::optional<DestSourcePair> PrevCopy =
1273 isCopyInstr(Prev, *TII, UseCopyInstr);
1274 std::optional<DestSourcePair> CurrentCopy =
1275 isCopyInstr(Current, *TII, UseCopyInstr);
1276 if (!PrevCopy || !CurrentCopy)
1277 return false;
1278 return PrevCopy->Source->getReg() == CurrentCopy->Destination->getReg();
1279 };
1280
1282 std::optional<DestSourcePair> CopyOperands =
1283 isCopyInstr(MI, *TII, UseCopyInstr);
1284
1285 // Update track information via non-copy instruction.
1286 SmallSet<Register, 8> RegsToClobber;
1287 if (!CopyOperands) {
1288 for (const MachineOperand &MO : MI.operands()) {
1289 if (!MO.isReg())
1290 continue;
1291 Register Reg = MO.getReg();
1292 if (!Reg)
1293 continue;
1294 MachineInstr *LastUseCopy =
1295 Tracker.findLastSeenUseInCopy(Reg.asMCReg(), *TRI);
1296 if (LastUseCopy) {
1297 LLVM_DEBUG(dbgs() << "MCP: Copy source of\n");
1298 LLVM_DEBUG(LastUseCopy->dump());
1299 LLVM_DEBUG(dbgs() << "might be invalidated by\n");
1300 LLVM_DEBUG(MI.dump());
1301 CopySourceInvalid.insert(LastUseCopy);
1302 }
1303 // Must be noted Tracker.clobberRegister(Reg, ...) removes tracking of
1304 // Reg, i.e, COPY that defines Reg is removed from the mapping as well
1305 // as marking COPYs that uses Reg unavailable.
1306 // We don't invoke CopyTracker::clobberRegister(Reg, ...) if Reg is not
1307 // defined by a previous COPY, since we don't want to make COPYs uses
1308 // Reg unavailable.
1309 if (Tracker.findLastSeenDefInCopy(MI, Reg.asMCReg(), *TRI, *TII,
1310 UseCopyInstr))
1311 // Thus we can keep the property#1.
1312 RegsToClobber.insert(Reg);
1313 }
1314 for (Register Reg : RegsToClobber) {
1315 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
1316 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Reg, TRI)
1317 << "\n");
1318 }
1319 continue;
1320 }
1321
1322 Register Src = CopyOperands->Source->getReg();
1323 Register Def = CopyOperands->Destination->getReg();
1324 // Check if we can find a pair spill-reload copy.
1325 LLVM_DEBUG(dbgs() << "MCP: Searching paired spill for reload: ");
1326 LLVM_DEBUG(MI.dump());
1327 MachineInstr *MaybeSpill =
1328 Tracker.findLastSeenDefInCopy(MI, Src.asMCReg(), *TRI, *TII, UseCopyInstr);
1329 bool MaybeSpillIsChained = ChainLeader.count(MaybeSpill);
1330 if (!MaybeSpillIsChained && MaybeSpill &&
1331 IsSpillReloadPair(*MaybeSpill, MI)) {
1332 // Check if we already have an existing chain. Now we have a
1333 // spill-reload pair.
1334 // L2: r2 = COPY r3
1335 // L5: r3 = COPY r2
1336 // Looking for a valid COPY before L5 which uses r3.
1337 // This can be serverial cases.
1338 // Case #1:
1339 // No COPY is found, which can be r3 is def-use between (L2, L5), we
1340 // create a new chain for L2 and L5.
1341 // Case #2:
1342 // L2: r2 = COPY r3
1343 // L5: r3 = COPY r2
1344 // Such COPY is found and is L2, we create a new chain for L2 and L5.
1345 // Case #3:
1346 // L2: r2 = COPY r3
1347 // L3: r1 = COPY r3
1348 // L5: r3 = COPY r2
1349 // we create a new chain for L2 and L5.
1350 // Case #4:
1351 // L2: r2 = COPY r3
1352 // L3: r1 = COPY r3
1353 // L4: r3 = COPY r1
1354 // L5: r3 = COPY r2
1355 // Such COPY won't be found since L4 defines r3. we create a new chain
1356 // for L2 and L5.
1357 // Case #5:
1358 // L2: r2 = COPY r3
1359 // L3: r3 = COPY r1
1360 // L4: r1 = COPY r3
1361 // L5: r3 = COPY r2
1362 // COPY is found and is L4 which belongs to an existing chain, we add
1363 // L2 and L5 to this chain.
1364 LLVM_DEBUG(dbgs() << "MCP: Found spill: ");
1365 LLVM_DEBUG(MaybeSpill->dump());
1366 MachineInstr *MaybePrevReload =
1367 Tracker.findLastSeenUseInCopy(Def.asMCReg(), *TRI);
1368 auto Leader = ChainLeader.find(MaybePrevReload);
1369 MachineInstr *L = nullptr;
1370 if (Leader == ChainLeader.end() ||
1371 (MaybePrevReload && !IsChainedCopy(*MaybePrevReload, MI))) {
1372 L = &MI;
1373 assert(!SpillChain.count(L) &&
1374 "SpillChain should not have contained newly found chain");
1375 } else {
1376 assert(MaybePrevReload &&
1377 "Found a valid leader through nullptr should not happend");
1378 L = Leader->second;
1379 assert(SpillChain[L].size() > 0 &&
1380 "Existing chain's length should be larger than zero");
1381 }
1382 assert(!ChainLeader.count(&MI) && !ChainLeader.count(MaybeSpill) &&
1383 "Newly found paired spill-reload should not belong to any chain "
1384 "at this point");
1385 ChainLeader.insert({MaybeSpill, L});
1386 ChainLeader.insert({&MI, L});
1387 SpillChain[L].push_back(MaybeSpill);
1388 ReloadChain[L].push_back(&MI);
1389 LLVM_DEBUG(dbgs() << "MCP: Chain " << L << " now is:\n");
1390 LLVM_DEBUG(printSpillReloadChain(SpillChain, ReloadChain, L));
1391 } else if (MaybeSpill && !MaybeSpillIsChained) {
1392 // MaybeSpill is unable to pair with MI. That's to say adding MI makes
1393 // the chain invalid.
1394 // The COPY defines Src is no longer considered as a candidate of a
1395 // valid chain. Since we expect the Def of a spill copy isn't used by
1396 // any COPY instruction until a reload copy. For example:
1397 // L1: r1 = COPY r2
1398 // L2: r3 = COPY r1
1399 // If we later have
1400 // L1: r1 = COPY r2
1401 // L2: r3 = COPY r1
1402 // L3: r2 = COPY r1
1403 // L1 and L3 can't be a valid spill-reload pair.
1404 // Thus we keep the property#1.
1405 LLVM_DEBUG(dbgs() << "MCP: Not paired spill-reload:\n");
1406 LLVM_DEBUG(MaybeSpill->dump());
1407 LLVM_DEBUG(MI.dump());
1408 Tracker.clobberRegister(Src.asMCReg(), *TRI, *TII, UseCopyInstr);
1409 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Src, TRI)
1410 << "\n");
1411 }
1412 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);
1413 }
1414
1415 for (auto I = SpillChain.begin(), E = SpillChain.end(); I != E; ++I) {
1416 auto &SC = I->second;
1417 assert(ReloadChain.count(I->first) &&
1418 "Reload chain of the same leader should exist");
1419 auto &RC = ReloadChain[I->first];
1420 TryFoldSpillageCopies(SC, RC);
1421 }
1422
1423 MaybeDeadCopies.clear();
1424 CopyDbgUsers.clear();
1425 Tracker.clear();
1426}
1427
1428bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
1429 if (skipFunction(MF.getFunction()))
1430 return false;
1431
1432 bool isSpillageCopyElimEnabled = false;
1434 case cl::BOU_UNSET:
1435 isSpillageCopyElimEnabled =
1437 break;
1438 case cl::BOU_TRUE:
1439 isSpillageCopyElimEnabled = true;
1440 break;
1441 case cl::BOU_FALSE:
1442 isSpillageCopyElimEnabled = false;
1443 break;
1444 }
1445
1446 Changed = false;
1447
1449 TII = MF.getSubtarget().getInstrInfo();
1450 MRI = &MF.getRegInfo();
1451
1452 for (MachineBasicBlock &MBB : MF) {
1453 if (isSpillageCopyElimEnabled)
1454 EliminateSpillageCopies(MBB);
1455 BackwardCopyPropagateBlock(MBB);
1456 ForwardCopyPropagateBlock(MBB);
1457 }
1458
1459 return Changed;
1460}
1461
1463llvm::createMachineCopyPropagationPass(bool UseCopyInstr = false) {
1464 return new MachineCopyPropagation(UseCopyInstr);
1465}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#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:182
#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, const TargetInstrInfo &TII)
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:72
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
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:554
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:1689
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:665
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
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:1888
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