LLVM 17.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");
83DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
84 "Controls which register COPYs are forwarded");
85
86static cl::opt<bool> MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false),
88
89namespace {
90
91static std::optional<DestSourcePair> isCopyInstr(const MachineInstr &MI,
92 const TargetInstrInfo &TII,
93 bool UseCopyInstr) {
94 if (UseCopyInstr)
95 return TII.isCopyInstr(MI);
96
97 if (MI.isCopy())
98 return std::optional<DestSourcePair>(
99 DestSourcePair{MI.getOperand(0), MI.getOperand(1)});
100
101 return std::nullopt;
102}
103
104class CopyTracker {
105 struct CopyInfo {
108 bool Avail;
109 };
110
112
113public:
114 /// Mark all of the given registers and their subregisters as unavailable for
115 /// copying.
116 void markRegsUnavailable(ArrayRef<MCRegister> Regs,
117 const TargetRegisterInfo &TRI) {
118 for (MCRegister Reg : Regs) {
119 // Source of copy is no longer available for propagation.
120 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
121 auto CI = Copies.find(*RUI);
122 if (CI != Copies.end())
123 CI->second.Avail = false;
124 }
125 }
126 }
127
128 /// Remove register from copy maps.
129 void invalidateRegister(MCRegister Reg, const TargetRegisterInfo &TRI,
130 const TargetInstrInfo &TII, bool UseCopyInstr) {
131 // Since Reg might be a subreg of some registers, only invalidate Reg is not
132 // enough. We have to find the COPY defines Reg or registers defined by Reg
133 // and invalidate all of them.
134 SmallSet<MCRegister, 8> RegsToInvalidate;
135 RegsToInvalidate.insert(Reg);
136 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
137 auto I = Copies.find(*RUI);
138 if (I != Copies.end()) {
139 if (MachineInstr *MI = I->second.MI) {
140 std::optional<DestSourcePair> CopyOperands =
141 isCopyInstr(*MI, TII, UseCopyInstr);
142 assert(CopyOperands && "Expect copy");
143
144 RegsToInvalidate.insert(
145 CopyOperands->Destination->getReg().asMCReg());
146 RegsToInvalidate.insert(CopyOperands->Source->getReg().asMCReg());
147 }
148 RegsToInvalidate.insert(I->second.DefRegs.begin(),
149 I->second.DefRegs.end());
150 }
151 }
152 for (MCRegister InvalidReg : RegsToInvalidate)
153 for (MCRegUnitIterator RUI(InvalidReg, &TRI); RUI.isValid(); ++RUI)
154 Copies.erase(*RUI);
155 }
156
157 /// Clobber a single register, removing it from the tracker's copy maps.
158 void clobberRegister(MCRegister Reg, const TargetRegisterInfo &TRI,
159 const TargetInstrInfo &TII, bool UseCopyInstr) {
160 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
161 auto I = Copies.find(*RUI);
162 if (I != Copies.end()) {
163 // When we clobber the source of a copy, we need to clobber everything
164 // it defined.
165 markRegsUnavailable(I->second.DefRegs, TRI);
166 // When we clobber the destination of a copy, we need to clobber the
167 // whole register it defined.
168 if (MachineInstr *MI = I->second.MI) {
169 std::optional<DestSourcePair> CopyOperands =
170 isCopyInstr(*MI, TII, UseCopyInstr);
171 markRegsUnavailable({CopyOperands->Destination->getReg().asMCReg()},
172 TRI);
173 }
174 // Now we can erase the copy.
175 Copies.erase(I);
176 }
177 }
178 }
179
180 /// Add this copy's registers into the tracker's copy maps.
181 void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI,
182 const TargetInstrInfo &TII, bool UseCopyInstr) {
183 std::optional<DestSourcePair> CopyOperands =
184 isCopyInstr(*MI, TII, UseCopyInstr);
185 assert(CopyOperands && "Tracking non-copy?");
186
187 MCRegister Src = CopyOperands->Source->getReg().asMCReg();
188 MCRegister Def = CopyOperands->Destination->getReg().asMCReg();
189
190 // Remember Def is defined by the copy.
191 for (MCRegUnitIterator RUI(Def, &TRI); RUI.isValid(); ++RUI)
192 Copies[*RUI] = {MI, {}, true};
193
194 // Remember source that's copied to Def. Once it's clobbered, then
195 // it's no longer available for copy propagation.
196 for (MCRegUnitIterator RUI(Src, &TRI); RUI.isValid(); ++RUI) {
197 auto I = Copies.insert({*RUI, {nullptr, {}, false}});
198 auto &Copy = I.first->second;
199 if (!is_contained(Copy.DefRegs, Def))
200 Copy.DefRegs.push_back(Def);
201 }
202 }
203
204 bool hasAnyCopies() {
205 return !Copies.empty();
206 }
207
208 MachineInstr *findCopyForUnit(MCRegister RegUnit,
209 const TargetRegisterInfo &TRI,
210 bool MustBeAvailable = false) {
211 auto CI = Copies.find(RegUnit);
212 if (CI == Copies.end())
213 return nullptr;
214 if (MustBeAvailable && !CI->second.Avail)
215 return nullptr;
216 return CI->second.MI;
217 }
218
219 MachineInstr *findCopyDefViaUnit(MCRegister RegUnit,
220 const TargetRegisterInfo &TRI) {
221 auto CI = Copies.find(RegUnit);
222 if (CI == Copies.end())
223 return nullptr;
224 if (CI->second.DefRegs.size() != 1)
225 return nullptr;
226 MCRegUnitIterator RUI(CI->second.DefRegs[0], &TRI);
227 return findCopyForUnit(*RUI, TRI, true);
228 }
229
230 MachineInstr *findAvailBackwardCopy(MachineInstr &I, MCRegister Reg,
231 const TargetRegisterInfo &TRI,
232 const TargetInstrInfo &TII,
233 bool UseCopyInstr) {
234 MCRegUnitIterator RUI(Reg, &TRI);
235 MachineInstr *AvailCopy = findCopyDefViaUnit(*RUI, TRI);
236
237 if (!AvailCopy)
238 return nullptr;
239
240 std::optional<DestSourcePair> CopyOperands =
241 isCopyInstr(*AvailCopy, TII, UseCopyInstr);
242 Register AvailSrc = CopyOperands->Source->getReg();
243 Register AvailDef = CopyOperands->Destination->getReg();
244 if (!TRI.isSubRegisterEq(AvailSrc, Reg))
245 return nullptr;
246
247 for (const MachineInstr &MI :
248 make_range(AvailCopy->getReverseIterator(), I.getReverseIterator()))
249 for (const MachineOperand &MO : MI.operands())
250 if (MO.isRegMask())
251 // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef?
252 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
253 return nullptr;
254
255 return AvailCopy;
256 }
257
258 MachineInstr *findAvailCopy(MachineInstr &DestCopy, MCRegister Reg,
259 const TargetRegisterInfo &TRI,
260 const TargetInstrInfo &TII, bool UseCopyInstr) {
261 // We check the first RegUnit here, since we'll only be interested in the
262 // copy if it copies the entire register anyway.
263 MCRegUnitIterator RUI(Reg, &TRI);
264 MachineInstr *AvailCopy =
265 findCopyForUnit(*RUI, TRI, /*MustBeAvailable=*/true);
266
267 if (!AvailCopy)
268 return nullptr;
269
270 std::optional<DestSourcePair> CopyOperands =
271 isCopyInstr(*AvailCopy, TII, UseCopyInstr);
272 Register AvailSrc = CopyOperands->Source->getReg();
273 Register AvailDef = CopyOperands->Destination->getReg();
274 if (!TRI.isSubRegisterEq(AvailDef, Reg))
275 return nullptr;
276
277 // Check that the available copy isn't clobbered by any regmasks between
278 // itself and the destination.
279 for (const MachineInstr &MI :
280 make_range(AvailCopy->getIterator(), DestCopy.getIterator()))
281 for (const MachineOperand &MO : MI.operands())
282 if (MO.isRegMask())
283 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
284 return nullptr;
285
286 return AvailCopy;
287 }
288
289 void clear() {
290 Copies.clear();
291 }
292};
293
294class MachineCopyPropagation : public MachineFunctionPass {
295 const TargetRegisterInfo *TRI;
296 const TargetInstrInfo *TII;
298
299 // Return true if this is a copy instruction and false otherwise.
300 bool UseCopyInstr;
301
302public:
303 static char ID; // Pass identification, replacement for typeid
304
305 MachineCopyPropagation(bool CopyInstr = false)
306 : MachineFunctionPass(ID), UseCopyInstr(CopyInstr || MCPUseCopyInstr) {
308 }
309
310 void getAnalysisUsage(AnalysisUsage &AU) const override {
311 AU.setPreservesCFG();
313 }
314
315 bool runOnMachineFunction(MachineFunction &MF) override;
316
319 MachineFunctionProperties::Property::NoVRegs);
320 }
321
322private:
323 typedef enum { DebugUse = false, RegularUse = true } DebugType;
324
325 void ReadRegister(MCRegister Reg, MachineInstr &Reader, DebugType DT);
326 void ForwardCopyPropagateBlock(MachineBasicBlock &MBB);
327 void BackwardCopyPropagateBlock(MachineBasicBlock &MBB);
328 bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def);
329 void forwardUses(MachineInstr &MI);
330 void propagateDefs(MachineInstr &MI);
331 bool isForwardableRegClassCopy(const MachineInstr &Copy,
332 const MachineInstr &UseI, unsigned UseIdx);
333 bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
334 const MachineInstr &UseI,
335 unsigned UseIdx);
336 bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
337 bool hasOverlappingMultipleDef(const MachineInstr &MI,
338 const MachineOperand &MODef, Register Def);
339
340 /// Candidates for deletion.
341 SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
342
343 /// Multimap tracking debug users in current BB
345
346 CopyTracker Tracker;
347
348 bool Changed;
349};
350
351} // end anonymous namespace
352
353char MachineCopyPropagation::ID = 0;
354
355char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
356
357INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
358 "Machine Copy Propagation Pass", false, false)
359
360void MachineCopyPropagation::ReadRegister(MCRegister Reg, MachineInstr &Reader,
361 DebugType DT) {
362 // If 'Reg' is defined by a copy, the copy is no longer a candidate
363 // for elimination. If a copy is "read" by a debug user, record the user
364 // for propagation.
365 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
366 if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) {
367 if (DT == RegularUse) {
368 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
369 MaybeDeadCopies.remove(Copy);
370 } else {
371 CopyDbgUsers[Copy].insert(&Reader);
372 }
373 }
374 }
375}
376
377/// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
378/// This fact may have been obscured by sub register usage or may not be true at
379/// all even though Src and Def are subregisters of the registers used in
380/// PreviousCopy. e.g.
381/// isNopCopy("ecx = COPY eax", AX, CX) == true
382/// isNopCopy("ecx = COPY eax", AH, CL) == false
383static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src,
385 const TargetInstrInfo *TII, bool UseCopyInstr) {
386
387 std::optional<DestSourcePair> CopyOperands =
388 isCopyInstr(PreviousCopy, *TII, UseCopyInstr);
389 MCRegister PreviousSrc = CopyOperands->Source->getReg().asMCReg();
390 MCRegister PreviousDef = CopyOperands->Destination->getReg().asMCReg();
391 if (Src == PreviousSrc && Def == PreviousDef)
392 return true;
393 if (!TRI->isSubRegister(PreviousSrc, Src))
394 return false;
395 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
396 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
397}
398
399/// Remove instruction \p Copy if there exists a previous copy that copies the
400/// register \p Src to the register \p Def; This may happen indirectly by
401/// copying the super registers.
402bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy,
403 MCRegister Src, MCRegister Def) {
404 // Avoid eliminating a copy from/to a reserved registers as we cannot predict
405 // the value (Example: The sparc zero register is writable but stays zero).
406 if (MRI->isReserved(Src) || MRI->isReserved(Def))
407 return false;
408
409 // Search for an existing copy.
410 MachineInstr *PrevCopy =
411 Tracker.findAvailCopy(Copy, Def, *TRI, *TII, UseCopyInstr);
412 if (!PrevCopy)
413 return false;
414
415 auto PrevCopyOperands = isCopyInstr(*PrevCopy, *TII, UseCopyInstr);
416 // Check that the existing copy uses the correct sub registers.
417 if (PrevCopyOperands->Destination->isDead())
418 return false;
419 if (!isNopCopy(*PrevCopy, Src, Def, TRI, TII, UseCopyInstr))
420 return false;
421
422 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
423
424 // Copy was redundantly redefining either Src or Def. Remove earlier kill
425 // flags between Copy and PrevCopy because the value will be reused now.
426 std::optional<DestSourcePair> CopyOperands =
427 isCopyInstr(Copy, *TII, UseCopyInstr);
428 assert(CopyOperands);
429
430 Register CopyDef = CopyOperands->Destination->getReg();
431 assert(CopyDef == Src || CopyDef == Def);
432 for (MachineInstr &MI :
433 make_range(PrevCopy->getIterator(), Copy.getIterator()))
434 MI.clearRegisterKills(CopyDef, TRI);
435
436 Copy.eraseFromParent();
437 Changed = true;
438 ++NumDeletes;
439 return true;
440}
441
442bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(
443 const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) {
444 std::optional<DestSourcePair> CopyOperands =
445 isCopyInstr(Copy, *TII, UseCopyInstr);
446 Register Def = CopyOperands->Destination->getReg();
447
448 if (const TargetRegisterClass *URC =
449 UseI.getRegClassConstraint(UseIdx, TII, TRI))
450 return URC->contains(Def);
451
452 // We don't process further if UseI is a COPY, since forward copy propagation
453 // should handle that.
454 return false;
455}
456
457/// Decide whether we should forward the source of \param Copy to its use in
458/// \param UseI based on the physical register class constraints of the opcode
459/// and avoiding introducing more cross-class COPYs.
460bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
461 const MachineInstr &UseI,
462 unsigned UseIdx) {
463 std::optional<DestSourcePair> CopyOperands =
464 isCopyInstr(Copy, *TII, UseCopyInstr);
465 Register CopySrcReg = CopyOperands->Source->getReg();
466
467 // If the new register meets the opcode register constraints, then allow
468 // forwarding.
469 if (const TargetRegisterClass *URC =
470 UseI.getRegClassConstraint(UseIdx, TII, TRI))
471 return URC->contains(CopySrcReg);
472
473 auto UseICopyOperands = isCopyInstr(UseI, *TII, UseCopyInstr);
474 if (!UseICopyOperands)
475 return false;
476
477 /// COPYs don't have register class constraints, so if the user instruction
478 /// is a COPY, we just try to avoid introducing additional cross-class
479 /// COPYs. For example:
480 ///
481 /// RegClassA = COPY RegClassB // Copy parameter
482 /// ...
483 /// RegClassB = COPY RegClassA // UseI parameter
484 ///
485 /// which after forwarding becomes
486 ///
487 /// RegClassA = COPY RegClassB
488 /// ...
489 /// RegClassB = COPY RegClassB
490 ///
491 /// so we have reduced the number of cross-class COPYs and potentially
492 /// introduced a nop COPY that can be removed.
493
494 // Allow forwarding if src and dst belong to any common class, so long as they
495 // don't belong to any (possibly smaller) common class that requires copies to
496 // go via a different class.
497 Register UseDstReg = UseICopyOperands->Destination->getReg();
498 bool Found = false;
499 bool IsCrossClass = false;
500 for (const TargetRegisterClass *RC : TRI->regclasses()) {
501 if (RC->contains(CopySrcReg) && RC->contains(UseDstReg)) {
502 Found = true;
503 if (TRI->getCrossCopyRegClass(RC) != RC) {
504 IsCrossClass = true;
505 break;
506 }
507 }
508 }
509 if (!Found)
510 return false;
511 if (!IsCrossClass)
512 return true;
513 // The forwarded copy would be cross-class. Only do this if the original copy
514 // was also cross-class.
515 Register CopyDstReg = CopyOperands->Destination->getReg();
516 for (const TargetRegisterClass *RC : TRI->regclasses()) {
517 if (RC->contains(CopySrcReg) && RC->contains(CopyDstReg) &&
518 TRI->getCrossCopyRegClass(RC) != RC)
519 return true;
520 }
521 return false;
522}
523
524/// Check that \p MI does not have implicit uses that overlap with it's \p Use
525/// operand (the register being replaced), since these can sometimes be
526/// implicitly tied to other operands. For example, on AMDGPU:
527///
528/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
529///
530/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
531/// way of knowing we need to update the latter when updating the former.
532bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
533 const MachineOperand &Use) {
534 for (const MachineOperand &MIUse : MI.uses())
535 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
536 MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
537 return true;
538
539 return false;
540}
541
542/// For an MI that has multiple definitions, check whether \p MI has
543/// a definition that overlaps with another of its definitions.
544/// For example, on ARM: umull r9, r9, lr, r0
545/// The umull instruction is unpredictable unless RdHi and RdLo are different.
546bool MachineCopyPropagation::hasOverlappingMultipleDef(
547 const MachineInstr &MI, const MachineOperand &MODef, Register Def) {
548 for (const MachineOperand &MIDef : MI.defs()) {
549 if ((&MIDef != &MODef) && MIDef.isReg() &&
550 TRI->regsOverlap(Def, MIDef.getReg()))
551 return true;
552 }
553
554 return false;
555}
556
557/// Look for available copies whose destination register is used by \p MI and
558/// replace the use in \p MI with the copy's source register.
559void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
560 if (!Tracker.hasAnyCopies())
561 return;
562
563 // Look for non-tied explicit vreg uses that have an active COPY
564 // instruction that defines the physical register allocated to them.
565 // Replace the vreg with the source of the active COPY.
566 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
567 ++OpIdx) {
568 MachineOperand &MOUse = MI.getOperand(OpIdx);
569 // Don't forward into undef use operands since doing so can cause problems
570 // with the machine verifier, since it doesn't treat undef reads as reads,
571 // so we can end up with a live range that ends on an undef read, leading to
572 // an error that the live range doesn't end on a read of the live range
573 // register.
574 if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
575 MOUse.isImplicit())
576 continue;
577
578 if (!MOUse.getReg())
579 continue;
580
581 // Check that the register is marked 'renamable' so we know it is safe to
582 // rename it without violating any constraints that aren't expressed in the
583 // IR (e.g. ABI or opcode requirements).
584 if (!MOUse.isRenamable())
585 continue;
586
587 MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg().asMCReg(),
588 *TRI, *TII, UseCopyInstr);
589 if (!Copy)
590 continue;
591
592 std::optional<DestSourcePair> CopyOperands =
593 isCopyInstr(*Copy, *TII, UseCopyInstr);
594 Register CopyDstReg = CopyOperands->Destination->getReg();
595 const MachineOperand &CopySrc = *CopyOperands->Source;
596 Register CopySrcReg = CopySrc.getReg();
597
598 // When the use is a subregister of the COPY destination,
599 // record the subreg index.
600 unsigned SubregIdx = 0;
601
602 // This can only occur when we are dealing with physical registers.
603 if (MOUse.getReg() != CopyDstReg) {
604 SubregIdx = TRI->getSubRegIndex(CopyDstReg, MOUse.getReg());
605 if (!SubregIdx)
606 continue;
607 }
608
609 // Don't forward COPYs of reserved regs unless they are constant.
610 if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
611 continue;
612
613 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
614 continue;
615
616 if (hasImplicitOverlap(MI, MOUse))
617 continue;
618
619 // Check that the instruction is not a copy that partially overwrites the
620 // original copy source that we are about to use. The tracker mechanism
621 // cannot cope with that.
622 if (isCopyInstr(MI, *TII, UseCopyInstr) &&
623 MI.modifiesRegister(CopySrcReg, TRI) &&
624 !MI.definesRegister(CopySrcReg)) {
625 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI);
626 continue;
627 }
628
629 if (!DebugCounter::shouldExecute(FwdCounter)) {
630 LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "
631 << MI);
632 continue;
633 }
634
635 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
636 << "\n with " << printReg(CopySrcReg, TRI)
637 << "\n in " << MI << " from " << *Copy);
638
639 if (SubregIdx)
640 MOUse.setReg(TRI->getSubReg(CopySrcReg, SubregIdx));
641 else
642 MOUse.setReg(CopySrcReg);
643
644 if (!CopySrc.isRenamable())
645 MOUse.setIsRenamable(false);
646 MOUse.setIsUndef(CopySrc.isUndef());
647
648 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
649
650 // Clear kill markers that may have been invalidated.
651 for (MachineInstr &KMI :
652 make_range(Copy->getIterator(), std::next(MI.getIterator())))
653 KMI.clearRegisterKills(CopySrcReg, TRI);
654
655 ++NumCopyForwards;
656 Changed = true;
657 }
658}
659
660void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) {
661 LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName()
662 << "\n");
663
665 // Analyze copies (which don't overlap themselves).
666 std::optional<DestSourcePair> CopyOperands =
667 isCopyInstr(MI, *TII, UseCopyInstr);
668 if (CopyOperands) {
669
670 Register RegSrc = CopyOperands->Source->getReg();
671 Register RegDef = CopyOperands->Destination->getReg();
672
673 if (!TRI->regsOverlap(RegDef, RegSrc)) {
674 assert(RegDef.isPhysical() && RegSrc.isPhysical() &&
675 "MachineCopyPropagation should be run after register allocation!");
676
677 MCRegister Def = RegDef.asMCReg();
678 MCRegister Src = RegSrc.asMCReg();
679
680 // The two copies cancel out and the source of the first copy
681 // hasn't been overridden, eliminate the second one. e.g.
682 // %ecx = COPY %eax
683 // ... nothing clobbered eax.
684 // %eax = COPY %ecx
685 // =>
686 // %ecx = COPY %eax
687 //
688 // or
689 //
690 // %ecx = COPY %eax
691 // ... nothing clobbered eax.
692 // %ecx = COPY %eax
693 // =>
694 // %ecx = COPY %eax
695 if (eraseIfRedundant(MI, Def, Src) || eraseIfRedundant(MI, Src, Def))
696 continue;
697
698 forwardUses(MI);
699
700 // Src may have been changed by forwardUses()
701 CopyOperands = isCopyInstr(MI, *TII, UseCopyInstr);
702 Src = CopyOperands->Source->getReg().asMCReg();
703
704 // If Src is defined by a previous copy, the previous copy cannot be
705 // eliminated.
706 ReadRegister(Src, MI, RegularUse);
707 for (const MachineOperand &MO : MI.implicit_operands()) {
708 if (!MO.isReg() || !MO.readsReg())
709 continue;
710 MCRegister Reg = MO.getReg().asMCReg();
711 if (!Reg)
712 continue;
713 ReadRegister(Reg, MI, RegularUse);
714 }
715
716 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI.dump());
717
718 // Copy is now a candidate for deletion.
719 if (!MRI->isReserved(Def))
720 MaybeDeadCopies.insert(&MI);
721
722 // If 'Def' is previously source of another copy, then this earlier copy's
723 // source is no longer available. e.g.
724 // %xmm9 = copy %xmm2
725 // ...
726 // %xmm2 = copy %xmm0
727 // ...
728 // %xmm2 = copy %xmm9
729 Tracker.clobberRegister(Def, *TRI, *TII, UseCopyInstr);
730 for (const MachineOperand &MO : MI.implicit_operands()) {
731 if (!MO.isReg() || !MO.isDef())
732 continue;
733 MCRegister Reg = MO.getReg().asMCReg();
734 if (!Reg)
735 continue;
736 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
737 }
738
739 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);
740
741 continue;
742 }
743 }
744
745 // Clobber any earlyclobber regs first.
746 for (const MachineOperand &MO : MI.operands())
747 if (MO.isReg() && MO.isEarlyClobber()) {
748 MCRegister Reg = MO.getReg().asMCReg();
749 // If we have a tied earlyclobber, that means it is also read by this
750 // instruction, so we need to make sure we don't remove it as dead
751 // later.
752 if (MO.isTied())
753 ReadRegister(Reg, MI, RegularUse);
754 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
755 }
756
757 forwardUses(MI);
758
759 // Not a copy.
761 const MachineOperand *RegMask = nullptr;
762 for (const MachineOperand &MO : MI.operands()) {
763 if (MO.isRegMask())
764 RegMask = &MO;
765 if (!MO.isReg())
766 continue;
767 Register Reg = MO.getReg();
768 if (!Reg)
769 continue;
770
771 assert(!Reg.isVirtual() &&
772 "MachineCopyPropagation should be run after register allocation!");
773
774 if (MO.isDef() && !MO.isEarlyClobber()) {
775 Defs.push_back(Reg.asMCReg());
776 continue;
777 } else if (MO.readsReg())
778 ReadRegister(Reg.asMCReg(), MI, MO.isDebug() ? DebugUse : RegularUse);
779 }
780
781 // The instruction has a register mask operand which means that it clobbers
782 // a large set of registers. Treat clobbered registers the same way as
783 // defined registers.
784 if (RegMask) {
785 // Erase any MaybeDeadCopies whose destination register is clobbered.
787 MaybeDeadCopies.begin();
788 DI != MaybeDeadCopies.end();) {
789 MachineInstr *MaybeDead = *DI;
790 std::optional<DestSourcePair> CopyOperands =
791 isCopyInstr(*MaybeDead, *TII, UseCopyInstr);
792 MCRegister Reg = CopyOperands->Destination->getReg().asMCReg();
793 assert(!MRI->isReserved(Reg));
794
795 if (!RegMask->clobbersPhysReg(Reg)) {
796 ++DI;
797 continue;
798 }
799
800 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
801 MaybeDead->dump());
802
803 // Make sure we invalidate any entries in the copy maps before erasing
804 // the instruction.
805 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
806
807 // erase() will return the next valid iterator pointing to the next
808 // element after the erased one.
809 DI = MaybeDeadCopies.erase(DI);
810 MaybeDead->eraseFromParent();
811 Changed = true;
812 ++NumDeletes;
813 }
814 }
815
816 // Any previous copy definition or reading the Defs is no longer available.
817 for (MCRegister Reg : Defs)
818 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);
819 }
820
821 // If MBB doesn't have successors, delete the copies whose defs are not used.
822 // If MBB does have successors, then conservative assume the defs are live-out
823 // since we don't want to trust live-in lists.
824 if (MBB.succ_empty()) {
825 for (MachineInstr *MaybeDead : MaybeDeadCopies) {
826 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
827 MaybeDead->dump());
828
829 std::optional<DestSourcePair> CopyOperands =
830 isCopyInstr(*MaybeDead, *TII, UseCopyInstr);
831 assert(CopyOperands);
832
833 Register SrcReg = CopyOperands->Source->getReg();
834 Register DestReg = CopyOperands->Destination->getReg();
835 assert(!MRI->isReserved(DestReg));
836
837 // Update matching debug values, if any.
838 SmallVector<MachineInstr *> MaybeDeadDbgUsers(
839 CopyDbgUsers[MaybeDead].begin(), CopyDbgUsers[MaybeDead].end());
840 MRI->updateDbgUsersToReg(DestReg.asMCReg(), SrcReg.asMCReg(),
841 MaybeDeadDbgUsers);
842
843 MaybeDead->eraseFromParent();
844 Changed = true;
845 ++NumDeletes;
846 }
847 }
848
849 MaybeDeadCopies.clear();
850 CopyDbgUsers.clear();
851 Tracker.clear();
852}
853
856 const TargetInstrInfo &TII,
857 bool UseCopyInstr) {
858 std::optional<DestSourcePair> CopyOperands =
859 isCopyInstr(MI, TII, UseCopyInstr);
860 assert(CopyOperands && "MI is expected to be a COPY");
861
862 Register Def = CopyOperands->Destination->getReg();
863 Register Src = CopyOperands->Source->getReg();
864
865 if (!Def || !Src)
866 return false;
867
868 if (MRI.isReserved(Def) || MRI.isReserved(Src))
869 return false;
870
871 return CopyOperands->Source->isRenamable() && CopyOperands->Source->isKill();
872}
873
874void MachineCopyPropagation::propagateDefs(MachineInstr &MI) {
875 if (!Tracker.hasAnyCopies())
876 return;
877
878 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd;
879 ++OpIdx) {
880 MachineOperand &MODef = MI.getOperand(OpIdx);
881
882 if (!MODef.isReg() || MODef.isUse())
883 continue;
884
885 // Ignore non-trivial cases.
886 if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit())
887 continue;
888
889 if (!MODef.getReg())
890 continue;
891
892 // We only handle if the register comes from a vreg.
893 if (!MODef.isRenamable())
894 continue;
895
896 MachineInstr *Copy = Tracker.findAvailBackwardCopy(
897 MI, MODef.getReg().asMCReg(), *TRI, *TII, UseCopyInstr);
898 if (!Copy)
899 continue;
900
901 std::optional<DestSourcePair> CopyOperands =
902 isCopyInstr(*Copy, *TII, UseCopyInstr);
903 Register Def = CopyOperands->Destination->getReg();
904 Register Src = CopyOperands->Source->getReg();
905
906 if (MODef.getReg() != Src)
907 continue;
908
909 if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx))
910 continue;
911
912 if (hasImplicitOverlap(MI, MODef))
913 continue;
914
915 if (hasOverlappingMultipleDef(MI, MODef, Def))
916 continue;
917
918 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI)
919 << "\n with " << printReg(Def, TRI) << "\n in "
920 << MI << " from " << *Copy);
921
922 MODef.setReg(Def);
923 MODef.setIsRenamable(CopyOperands->Destination->isRenamable());
924
925 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
926 MaybeDeadCopies.insert(Copy);
927 Changed = true;
928 ++NumCopyBackwardPropagated;
929 }
930}
931
932void MachineCopyPropagation::BackwardCopyPropagateBlock(
934 LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName()
935 << "\n");
936
938 // Ignore non-trivial COPYs.
939 std::optional<DestSourcePair> CopyOperands =
940 isCopyInstr(MI, *TII, UseCopyInstr);
941 if (CopyOperands && MI.getNumOperands() == 2) {
942 Register DefReg = CopyOperands->Destination->getReg();
943 Register SrcReg = CopyOperands->Source->getReg();
944
945 if (!TRI->regsOverlap(DefReg, SrcReg)) {
946 MCRegister Def = DefReg.asMCReg();
947 MCRegister Src = SrcReg.asMCReg();
948
949 // Unlike forward cp, we don't invoke propagateDefs here,
950 // just let forward cp do COPY-to-COPY propagation.
951 if (isBackwardPropagatableCopy(MI, *MRI, *TII, UseCopyInstr)) {
952 Tracker.invalidateRegister(Src, *TRI, *TII, UseCopyInstr);
953 Tracker.invalidateRegister(Def, *TRI, *TII, UseCopyInstr);
954 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);
955 continue;
956 }
957 }
958 }
959
960 // Invalidate any earlyclobber regs first.
961 for (const MachineOperand &MO : MI.operands())
962 if (MO.isReg() && MO.isEarlyClobber()) {
963 MCRegister Reg = MO.getReg().asMCReg();
964 if (!Reg)
965 continue;
966 Tracker.invalidateRegister(Reg, *TRI, *TII, UseCopyInstr);
967 }
968
969 propagateDefs(MI);
970 for (const MachineOperand &MO : MI.operands()) {
971 if (!MO.isReg())
972 continue;
973
974 if (!MO.getReg())
975 continue;
976
977 if (MO.isDef())
978 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII,
979 UseCopyInstr);
980
981 if (MO.readsReg()) {
982 if (MO.isDebug()) {
983 // Check if the register in the debug instruction is utilized
984 // in a copy instruction, so we can update the debug info if the
985 // register is changed.
986 for (MCRegUnitIterator RUI(MO.getReg().asMCReg(), TRI); RUI.isValid();
987 ++RUI) {
988 if (auto *Copy = Tracker.findCopyDefViaUnit(*RUI, *TRI)) {
989 CopyDbgUsers[Copy].insert(&MI);
990 }
991 }
992 } else {
993 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII,
994 UseCopyInstr);
995 }
996 }
997 }
998 }
999
1000 for (auto *Copy : MaybeDeadCopies) {
1001 std::optional<DestSourcePair> CopyOperands =
1002 isCopyInstr(*Copy, *TII, UseCopyInstr);
1003 Register Src = CopyOperands->Source->getReg();
1004 Register Def = CopyOperands->Destination->getReg();
1005 SmallVector<MachineInstr *> MaybeDeadDbgUsers(CopyDbgUsers[Copy].begin(),
1006 CopyDbgUsers[Copy].end());
1007
1008 MRI->updateDbgUsersToReg(Src.asMCReg(), Def.asMCReg(), MaybeDeadDbgUsers);
1009 Copy->eraseFromParent();
1010 ++NumDeletes;
1011 }
1012
1013 MaybeDeadCopies.clear();
1014 CopyDbgUsers.clear();
1015 Tracker.clear();
1016}
1017
1018bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
1019 if (skipFunction(MF.getFunction()))
1020 return false;
1021
1022 Changed = false;
1023
1025 TII = MF.getSubtarget().getInstrInfo();
1026 MRI = &MF.getRegInfo();
1027
1028 for (MachineBasicBlock &MBB : MF) {
1029 BackwardCopyPropagateBlock(MBB);
1030 ForwardCopyPropagateBlock(MBB);
1031 }
1032
1033 return Changed;
1034}
1035
1037llvm::createMachineCopyPropagationPass(bool UseCopyInstr = false) {
1038 return new MachineCopyPropagation(UseCopyInstr);
1039}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
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 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 bool isBackwardPropagatableCopy(MachineInstr &MI, const MachineRegisterInfo &MRI, const TargetInstrInfo &TII, bool UseCopyInstr)
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:265
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
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
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:68
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
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
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:120
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
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:177
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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 const TargetInstrInfo * getInstrInfo() const
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:85
self_iterator getIterator()
Definition: ilist_node.h:82
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
DebugType
Definition: COFF.h:652
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:721
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
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.