1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is an extremely simple MachineInstr-level copy propagation pass.
10 //
11 // This pass forwards the source of COPYs to the users of their destinations
12 // when doing so is legal. For example:
13 //
14 // %reg1 = COPY %reg0
15 // ...
16 // ... = OP %reg1
17 //
18 // If
19 // - %reg0 has not been clobbered by the time of the use of %reg1
20 // - the register class constraints are satisfied
21 // - the COPY def is the only value that reaches OP
22 // then this pass replaces the above with:
23 //
24 // %reg1 = COPY %reg0
25 // ...
26 // ... = OP %reg0
27 //
28 // This pass also removes some redundant COPYs. For example:
29 //
30 // %R1 = COPY %R0
31 // ... // No clobber of %R1
32 // %R0 = COPY %R1 <<< Removed
33 //
34 // or
35 //
36 // %R1 = COPY %R0
37 // ... // No clobber of %R0
38 // %R1 = COPY %R0 <<< Removed
39 //
40 // or
41 //
42 // $R0 = OP ...
43 // ... // No read/clobber of $R0 and $R1
44 // $R1 = COPY $R0 // $R0 is killed
45 // Replace $R0 with $R1 and remove the COPY
46 // $R1 = OP ...
47 // ...
48 //
49 //===----------------------------------------------------------------------===//
50
51 #include "llvm/ADT/DenseMap.h"
52 #include "llvm/ADT/STLExtras.h"
53 #include "llvm/ADT/SetVector.h"
54 #include "llvm/ADT/SmallSet.h"
55 #include "llvm/ADT/SmallVector.h"
56 #include "llvm/ADT/Statistic.h"
57 #include "llvm/ADT/iterator_range.h"
58 #include "llvm/CodeGen/MachineBasicBlock.h"
59 #include "llvm/CodeGen/MachineFunction.h"
60 #include "llvm/CodeGen/MachineFunctionPass.h"
61 #include "llvm/CodeGen/MachineInstr.h"
62 #include "llvm/CodeGen/MachineOperand.h"
63 #include "llvm/CodeGen/MachineRegisterInfo.h"
64 #include "llvm/CodeGen/TargetInstrInfo.h"
65 #include "llvm/CodeGen/TargetRegisterInfo.h"
66 #include "llvm/CodeGen/TargetSubtargetInfo.h"
67 #include "llvm/InitializePasses.h"
68 #include "llvm/MC/MCRegisterInfo.h"
69 #include "llvm/Pass.h"
70 #include "llvm/Support/Debug.h"
71 #include "llvm/Support/DebugCounter.h"
72 #include "llvm/Support/raw_ostream.h"
73 #include <cassert>
74 #include <iterator>
75
76 using namespace llvm;
77
78 #define DEBUG_TYPE "machine-cp"
79
80 STATISTIC(NumDeletes, "Number of dead copies deleted");
81 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
82 STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");
83 STATISTIC(SpillageChainsLength, "Length of spillage chains");
84 STATISTIC(NumSpillageChains, "Number of spillage chains");
85 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
86 "Controls which register COPYs are forwarded");
87
88 static cl::opt<bool> MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false),
89 cl::Hidden);
90 static cl::opt<cl::boolOrDefault>
91 EnableSpillageCopyElimination("enable-spill-copy-elim", cl::Hidden);
92
93 namespace {
94
isCopyInstr(const MachineInstr & MI,const TargetInstrInfo & TII,bool UseCopyInstr)95 static 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
108 class CopyTracker {
109 struct CopyInfo {
110 MachineInstr *MI, *LastSeenUseInCopy;
111 SmallVector<MCRegister, 4> DefRegs;
112 bool Avail;
113 };
114
115 DenseMap<MCRegister, CopyInfo> Copies;
116
117 public:
118 /// Mark all of the given registers and their subregisters as unavailable for
119 /// copying.
markRegsUnavailable(ArrayRef<MCRegister> Regs,const TargetRegisterInfo & TRI)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.
invalidateRegister(MCRegister Reg,const TargetRegisterInfo & TRI,const TargetInstrInfo & TII,bool UseCopyInstr)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.
clobberRegister(MCRegister Reg,const TargetRegisterInfo & TRI,const TargetInstrInfo & TII,bool UseCopyInstr)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.
trackCopy(MachineInstr * MI,const TargetRegisterInfo & TRI,const TargetInstrInfo & TII,bool UseCopyInstr)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
hasAnyCopies()250 bool hasAnyCopies() {
251 return !Copies.empty();
252 }
253
findCopyForUnit(MCRegister RegUnit,const TargetRegisterInfo & TRI,bool MustBeAvailable=false)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
findCopyDefViaUnit(MCRegister RegUnit,const TargetRegisterInfo & TRI)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
findAvailBackwardCopy(MachineInstr & I,MCRegister Reg,const TargetRegisterInfo & TRI,const TargetInstrInfo & TII,bool UseCopyInstr)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
findAvailCopy(MachineInstr & DestCopy,MCRegister Reg,const TargetRegisterInfo & TRI,const TargetInstrInfo & TII,bool UseCopyInstr)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.
findLastSeenDefInCopy(const MachineInstr & Current,MCRegister Reg,const TargetRegisterInfo & TRI,const TargetInstrInfo & TII,bool UseCopyInstr)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.
findLastSeenUseInCopy(MCRegister Reg,const TargetRegisterInfo & TRI)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
clear()377 void clear() {
378 Copies.clear();
379 }
380 };
381
382 class 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
390 public:
391 static char ID; // Pass identification, replacement for typeid
392
MachineCopyPropagation(bool CopyInstr=false)393 MachineCopyPropagation(bool CopyInstr = false)
394 : MachineFunctionPass(ID), UseCopyInstr(CopyInstr || MCPUseCopyInstr) {
395 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
396 }
397
getAnalysisUsage(AnalysisUsage & AU) const398 void getAnalysisUsage(AnalysisUsage &AU) const override {
399 AU.setPreservesCFG();
400 MachineFunctionPass::getAnalysisUsage(AU);
401 }
402
403 bool runOnMachineFunction(MachineFunction &MF) override;
404
getRequiredProperties() const405 MachineFunctionProperties getRequiredProperties() const override {
406 return MachineFunctionProperties().set(
407 MachineFunctionProperties::Property::NoVRegs);
408 }
409
410 private:
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
433 DenseMap<MachineInstr *, SmallSet<MachineInstr *, 2>> CopyDbgUsers;
434
435 CopyTracker Tracker;
436
437 bool Changed = false;
438 };
439
440 } // end anonymous namespace
441
442 char MachineCopyPropagation::ID = 0;
443
444 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
445
446 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
447 "Machine Copy Propagation Pass", false, false)
448
ReadRegister(MCRegister Reg,MachineInstr & Reader,DebugType DT)449 void 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
isNopCopy(const MachineInstr & PreviousCopy,MCRegister Src,MCRegister Def,const TargetRegisterInfo * TRI,const TargetInstrInfo * TII,bool UseCopyInstr)472 static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src,
473 MCRegister Def, const TargetRegisterInfo *TRI,
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.
eraseIfRedundant(MachineInstr & Copy,MCRegister Src,MCRegister Def)491 bool 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
isBackwardPropagatableRegClassCopy(const MachineInstr & Copy,const MachineInstr & UseI,unsigned UseIdx)537 bool 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.
isForwardableRegClassCopy(const MachineInstr & Copy,const MachineInstr & UseI,unsigned UseIdx)555 bool 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.
hasImplicitOverlap(const MachineInstr & MI,const MachineOperand & Use)627 bool 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.
hasOverlappingMultipleDef(const MachineInstr & MI,const MachineOperand & MODef,Register Def)641 bool 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.
forwardUses(MachineInstr & MI)654 void 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
ForwardCopyPropagateBlock(MachineBasicBlock & MBB)756 void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) {
757 LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName()
758 << "\n");
759
760 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) {
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.
856 SmallVector<Register, 4> Defs;
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.
882 for (SmallSetVector<MachineInstr *, 8>::iterator DI =
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
isBackwardPropagatableCopy(const DestSourcePair & CopyOperands,const MachineRegisterInfo & MRI,const TargetInstrInfo & TII)950 static bool isBackwardPropagatableCopy(const DestSourcePair &CopyOperands,
951 const MachineRegisterInfo &MRI,
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
propagateDefs(MachineInstr & MI)965 void 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
BackwardCopyPropagateBlock(MachineBasicBlock & MBB)1023 void MachineCopyPropagation::BackwardCopyPropagateBlock(
1024 MachineBasicBlock &MBB) {
1025 LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName()
1026 << "\n");
1027
1028 for (MachineInstr &MI : llvm::make_early_inc_range(llvm::reverse(MBB))) {
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
printSpillReloadChain(DenseMap<MachineInstr *,SmallVector<MachineInstr * >> & SpillChain,DenseMap<MachineInstr *,SmallVector<MachineInstr * >> & ReloadChain,MachineInstr * Leader)1107 static void LLVM_ATTRIBUTE_UNUSED printSpillReloadChain(
1108 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &SpillChain,
1109 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &ReloadChain,
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, ...).
EliminateSpillageCopies(MachineBasicBlock & MBB)1157 void 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.
1160 DenseMap<MachineInstr *, MachineInstr *> ChainLeader;
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.
1165 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> SpillChain, ReloadChain;
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,
1172 const SmallVectorImpl<MachineInstr *> &RC) {
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
1281 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) {
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
runOnMachineFunction(MachineFunction & MF)1428 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
1429 if (skipFunction(MF.getFunction()))
1430 return false;
1431
1432 bool isSpillageCopyElimEnabled = false;
1433 switch (EnableSpillageCopyElimination) {
1434 case cl::BOU_UNSET:
1435 isSpillageCopyElimEnabled =
1436 MF.getSubtarget().enableSpillageCopyElimination();
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
1448 TRI = MF.getSubtarget().getRegisterInfo();
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
1462 MachineFunctionPass *
createMachineCopyPropagationPass(bool UseCopyInstr=false)1463 llvm::createMachineCopyPropagationPass(bool UseCopyInstr = false) {
1464 return new MachineCopyPropagation(UseCopyInstr);
1465 }
1466