1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This is an extremely simple MachineInstr-level copy propagation pass.
12 // This pass forwards the source of COPYs to the users of their destinations
13 // when doing so is legal. For example:
20 // - %reg0 has not been clobbered by the time of the use of %reg1
21 // - the register class constraints are satisfied
22 // - the COPY def is the only value that reaches OP
23 // then this pass replaces the above with:
29 // This pass also removes some redundant COPYs. For example:
32 // ... // No clobber of %R1
33 // %R0 = COPY %R1 <<< Removed
38 // ... // No clobber of %R0
39 // %R1 = COPY %R0 <<< Removed
41 //===----------------------------------------------------------------------===//
43 #include "llvm/ADT/DenseMap.h"
44 #include "llvm/ADT/STLExtras.h"
45 #include "llvm/ADT/SetVector.h"
46 #include "llvm/ADT/SmallVector.h"
47 #include "llvm/ADT/Statistic.h"
48 #include "llvm/ADT/iterator_range.h"
49 #include "llvm/CodeGen/MachineBasicBlock.h"
50 #include "llvm/CodeGen/MachineFunction.h"
51 #include "llvm/CodeGen/MachineFunctionPass.h"
52 #include "llvm/CodeGen/MachineInstr.h"
53 #include "llvm/CodeGen/MachineOperand.h"
54 #include "llvm/CodeGen/MachineRegisterInfo.h"
55 #include "llvm/CodeGen/TargetInstrInfo.h"
56 #include "llvm/CodeGen/TargetRegisterInfo.h"
57 #include "llvm/CodeGen/TargetSubtargetInfo.h"
58 #include "llvm/MC/MCRegisterInfo.h"
59 #include "llvm/Pass.h"
60 #include "llvm/Support/Debug.h"
61 #include "llvm/Support/DebugCounter.h"
62 #include "llvm/Support/raw_ostream.h"
68 #define DEBUG_TYPE "machine-cp"
70 STATISTIC(NumDeletes, "Number of dead copies deleted");
71 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
72 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
73 "Controls which register COPYs are forwarded");
80 SmallVector<unsigned, 4> DefRegs;
84 DenseMap<unsigned, CopyInfo> Copies;
87 /// Mark all of the given registers and their subregisters as unavailable for
89 void markRegsUnavailable(ArrayRef<unsigned> Regs,
90 const TargetRegisterInfo &TRI) {
91 for (unsigned Reg : Regs) {
92 // Source of copy is no longer available for propagation.
93 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
94 auto CI = Copies.find(*RUI);
95 if (CI != Copies.end())
96 CI->second.Avail = false;
101 /// Clobber a single register, removing it from the tracker's copy maps.
102 void clobberRegister(unsigned Reg, const TargetRegisterInfo &TRI) {
103 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) {
104 auto I = Copies.find(*RUI);
105 if (I != Copies.end()) {
106 // When we clobber the source of a copy, we need to clobber everything
108 markRegsUnavailable(I->second.DefRegs, TRI);
109 // When we clobber the destination of a copy, we need to clobber the
110 // whole register it defined.
111 if (MachineInstr *MI = I->second.MI)
112 markRegsUnavailable({MI->getOperand(0).getReg()}, TRI);
113 // Now we can erase the copy.
119 /// Add this copy's registers into the tracker's copy maps.
120 void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI) {
121 assert(MI->isCopy() && "Tracking non-copy?");
123 unsigned Def = MI->getOperand(0).getReg();
124 unsigned Src = MI->getOperand(1).getReg();
126 // Remember Def is defined by the copy.
127 for (MCRegUnitIterator RUI(Def, &TRI); RUI.isValid(); ++RUI)
128 Copies[*RUI] = {MI, {}, true};
130 // Remember source that's copied to Def. Once it's clobbered, then
131 // it's no longer available for copy propagation.
132 for (MCRegUnitIterator RUI(Src, &TRI); RUI.isValid(); ++RUI) {
133 auto I = Copies.insert({*RUI, {nullptr, {}, false}});
134 auto &Copy = I.first->second;
135 if (!is_contained(Copy.DefRegs, Def))
136 Copy.DefRegs.push_back(Def);
140 bool hasAnyCopies() {
141 return !Copies.empty();
144 MachineInstr *findCopyForUnit(unsigned RegUnit, const TargetRegisterInfo &TRI,
145 bool MustBeAvailable = false) {
146 auto CI = Copies.find(RegUnit);
147 if (CI == Copies.end())
149 if (MustBeAvailable && !CI->second.Avail)
151 return CI->second.MI;
154 MachineInstr *findAvailCopy(MachineInstr &DestCopy, unsigned Reg,
155 const TargetRegisterInfo &TRI) {
156 // We check the first RegUnit here, since we'll only be interested in the
157 // copy if it copies the entire register anyway.
158 MCRegUnitIterator RUI(Reg, &TRI);
159 MachineInstr *AvailCopy =
160 findCopyForUnit(*RUI, TRI, /*MustBeAvailable=*/true);
162 !TRI.isSubRegisterEq(AvailCopy->getOperand(0).getReg(), Reg))
165 // Check that the available copy isn't clobbered by any regmasks between
166 // itself and the destination.
167 unsigned AvailSrc = AvailCopy->getOperand(1).getReg();
168 unsigned AvailDef = AvailCopy->getOperand(0).getReg();
169 for (const MachineInstr &MI :
170 make_range(AvailCopy->getIterator(), DestCopy.getIterator()))
171 for (const MachineOperand &MO : MI.operands())
173 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
184 class MachineCopyPropagation : public MachineFunctionPass {
185 const TargetRegisterInfo *TRI;
186 const TargetInstrInfo *TII;
187 const MachineRegisterInfo *MRI;
190 static char ID; // Pass identification, replacement for typeid
192 MachineCopyPropagation() : MachineFunctionPass(ID) {
193 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
196 void getAnalysisUsage(AnalysisUsage &AU) const override {
197 AU.setPreservesCFG();
198 MachineFunctionPass::getAnalysisUsage(AU);
201 bool runOnMachineFunction(MachineFunction &MF) override;
203 MachineFunctionProperties getRequiredProperties() const override {
204 return MachineFunctionProperties().set(
205 MachineFunctionProperties::Property::NoVRegs);
209 void ClobberRegister(unsigned Reg);
210 void ReadRegister(unsigned Reg);
211 void CopyPropagateBlock(MachineBasicBlock &MBB);
212 bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
213 void forwardUses(MachineInstr &MI);
214 bool isForwardableRegClassCopy(const MachineInstr &Copy,
215 const MachineInstr &UseI, unsigned UseIdx);
216 bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
218 /// Candidates for deletion.
219 SmallSetVector<MachineInstr *, 8> MaybeDeadCopies;
226 } // end anonymous namespace
228 char MachineCopyPropagation::ID = 0;
230 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
232 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
233 "Machine Copy Propagation Pass", false, false)
235 void MachineCopyPropagation::ReadRegister(unsigned Reg) {
236 // If 'Reg' is defined by a copy, the copy is no longer a candidate
238 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
239 if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) {
240 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
241 MaybeDeadCopies.remove(Copy);
246 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
247 /// This fact may have been obscured by sub register usage or may not be true at
248 /// all even though Src and Def are subregisters of the registers used in
249 /// PreviousCopy. e.g.
250 /// isNopCopy("ecx = COPY eax", AX, CX) == true
251 /// isNopCopy("ecx = COPY eax", AH, CL) == false
252 static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src,
253 unsigned Def, const TargetRegisterInfo *TRI) {
254 unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg();
255 unsigned PreviousDef = PreviousCopy.getOperand(0).getReg();
256 if (Src == PreviousSrc) {
257 assert(Def == PreviousDef);
260 if (!TRI->isSubRegister(PreviousSrc, Src))
262 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
263 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
266 /// Remove instruction \p Copy if there exists a previous copy that copies the
267 /// register \p Src to the register \p Def; This may happen indirectly by
268 /// copying the super registers.
269 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
271 // Avoid eliminating a copy from/to a reserved registers as we cannot predict
272 // the value (Example: The sparc zero register is writable but stays zero).
273 if (MRI->isReserved(Src) || MRI->isReserved(Def))
276 // Search for an existing copy.
277 MachineInstr *PrevCopy = Tracker.findAvailCopy(Copy, Def, *TRI);
281 // Check that the existing copy uses the correct sub registers.
282 if (PrevCopy->getOperand(0).isDead())
284 if (!isNopCopy(*PrevCopy, Src, Def, TRI))
287 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
289 // Copy was redundantly redefining either Src or Def. Remove earlier kill
290 // flags between Copy and PrevCopy because the value will be reused now.
291 assert(Copy.isCopy());
292 unsigned CopyDef = Copy.getOperand(0).getReg();
293 assert(CopyDef == Src || CopyDef == Def);
294 for (MachineInstr &MI :
295 make_range(PrevCopy->getIterator(), Copy.getIterator()))
296 MI.clearRegisterKills(CopyDef, TRI);
298 Copy.eraseFromParent();
304 /// Decide whether we should forward the source of \param Copy to its use in
305 /// \param UseI based on the physical register class constraints of the opcode
306 /// and avoiding introducing more cross-class COPYs.
307 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
308 const MachineInstr &UseI,
311 unsigned CopySrcReg = Copy.getOperand(1).getReg();
313 // If the new register meets the opcode register constraints, then allow
315 if (const TargetRegisterClass *URC =
316 UseI.getRegClassConstraint(UseIdx, TII, TRI))
317 return URC->contains(CopySrcReg);
322 /// COPYs don't have register class constraints, so if the user instruction
323 /// is a COPY, we just try to avoid introducing additional cross-class
324 /// COPYs. For example:
326 /// RegClassA = COPY RegClassB // Copy parameter
328 /// RegClassB = COPY RegClassA // UseI parameter
330 /// which after forwarding becomes
332 /// RegClassA = COPY RegClassB
334 /// RegClassB = COPY RegClassB
336 /// so we have reduced the number of cross-class COPYs and potentially
337 /// introduced a nop COPY that can be removed.
338 const TargetRegisterClass *UseDstRC =
339 TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg());
341 const TargetRegisterClass *SuperRC = UseDstRC;
342 for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses();
343 SuperRC; SuperRC = *SuperRCI++)
344 if (SuperRC->contains(CopySrcReg))
350 /// Check that \p MI does not have implicit uses that overlap with it's \p Use
351 /// operand (the register being replaced), since these can sometimes be
352 /// implicitly tied to other operands. For example, on AMDGPU:
354 /// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
356 /// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
357 /// way of knowing we need to update the latter when updating the former.
358 bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
359 const MachineOperand &Use) {
360 for (const MachineOperand &MIUse : MI.uses())
361 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
362 MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
368 /// Look for available copies whose destination register is used by \p MI and
369 /// replace the use in \p MI with the copy's source register.
370 void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
371 if (!Tracker.hasAnyCopies())
374 // Look for non-tied explicit vreg uses that have an active COPY
375 // instruction that defines the physical register allocated to them.
376 // Replace the vreg with the source of the active COPY.
377 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
379 MachineOperand &MOUse = MI.getOperand(OpIdx);
380 // Don't forward into undef use operands since doing so can cause problems
381 // with the machine verifier, since it doesn't treat undef reads as reads,
382 // so we can end up with a live range that ends on an undef read, leading to
383 // an error that the live range doesn't end on a read of the live range
385 if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
392 // Check that the register is marked 'renamable' so we know it is safe to
393 // rename it without violating any constraints that aren't expressed in the
394 // IR (e.g. ABI or opcode requirements).
395 if (!MOUse.isRenamable())
398 MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg(), *TRI);
402 unsigned CopyDstReg = Copy->getOperand(0).getReg();
403 const MachineOperand &CopySrc = Copy->getOperand(1);
404 unsigned CopySrcReg = CopySrc.getReg();
406 // FIXME: Don't handle partial uses of wider COPYs yet.
407 if (MOUse.getReg() != CopyDstReg) {
409 dbgs() << "MCP: FIXME! Not forwarding COPY to sub-register use:\n "
414 // Don't forward COPYs of reserved regs unless they are constant.
415 if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
418 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
421 if (hasImplicitOverlap(MI, MOUse))
424 if (!DebugCounter::shouldExecute(FwdCounter)) {
425 LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "
430 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
431 << "\n with " << printReg(CopySrcReg, TRI)
432 << "\n in " << MI << " from " << *Copy);
434 MOUse.setReg(CopySrcReg);
435 if (!CopySrc.isRenamable())
436 MOUse.setIsRenamable(false);
438 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
440 // Clear kill markers that may have been invalidated.
441 for (MachineInstr &KMI :
442 make_range(Copy->getIterator(), std::next(MI.getIterator())))
443 KMI.clearRegisterKills(CopySrcReg, TRI);
450 void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
451 LLVM_DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
453 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
454 MachineInstr *MI = &*I;
457 // Analyze copies (which don't overlap themselves).
458 if (MI->isCopy() && !TRI->regsOverlap(MI->getOperand(0).getReg(),
459 MI->getOperand(1).getReg())) {
460 unsigned Def = MI->getOperand(0).getReg();
461 unsigned Src = MI->getOperand(1).getReg();
463 assert(!TargetRegisterInfo::isVirtualRegister(Def) &&
464 !TargetRegisterInfo::isVirtualRegister(Src) &&
465 "MachineCopyPropagation should be run after register allocation!");
467 // The two copies cancel out and the source of the first copy
468 // hasn't been overridden, eliminate the second one. e.g.
470 // ... nothing clobbered eax.
478 // ... nothing clobbered eax.
482 if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def))
487 // Src may have been changed by forwardUses()
488 Src = MI->getOperand(1).getReg();
490 // If Src is defined by a previous copy, the previous copy cannot be
493 for (const MachineOperand &MO : MI->implicit_operands()) {
494 if (!MO.isReg() || !MO.readsReg())
496 unsigned Reg = MO.getReg();
502 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
504 // Copy is now a candidate for deletion.
505 if (!MRI->isReserved(Def))
506 MaybeDeadCopies.insert(MI);
508 // If 'Def' is previously source of another copy, then this earlier copy's
509 // source is no longer available. e.g.
510 // %xmm9 = copy %xmm2
512 // %xmm2 = copy %xmm0
514 // %xmm2 = copy %xmm9
515 Tracker.clobberRegister(Def, *TRI);
516 for (const MachineOperand &MO : MI->implicit_operands()) {
517 if (!MO.isReg() || !MO.isDef())
519 unsigned Reg = MO.getReg();
522 Tracker.clobberRegister(Reg, *TRI);
525 Tracker.trackCopy(MI, *TRI);
530 // Clobber any earlyclobber regs first.
531 for (const MachineOperand &MO : MI->operands())
532 if (MO.isReg() && MO.isEarlyClobber()) {
533 unsigned Reg = MO.getReg();
534 // If we have a tied earlyclobber, that means it is also read by this
535 // instruction, so we need to make sure we don't remove it as dead
539 Tracker.clobberRegister(Reg, *TRI);
545 SmallVector<unsigned, 2> Defs;
546 const MachineOperand *RegMask = nullptr;
547 for (const MachineOperand &MO : MI->operands()) {
552 unsigned Reg = MO.getReg();
556 assert(!TargetRegisterInfo::isVirtualRegister(Reg) &&
557 "MachineCopyPropagation should be run after register allocation!");
559 if (MO.isDef() && !MO.isEarlyClobber()) {
562 } else if (!MO.isDebug() && MO.readsReg())
566 // The instruction has a register mask operand which means that it clobbers
567 // a large set of registers. Treat clobbered registers the same way as
568 // defined registers.
570 // Erase any MaybeDeadCopies whose destination register is clobbered.
571 for (SmallSetVector<MachineInstr *, 8>::iterator DI =
572 MaybeDeadCopies.begin();
573 DI != MaybeDeadCopies.end();) {
574 MachineInstr *MaybeDead = *DI;
575 unsigned Reg = MaybeDead->getOperand(0).getReg();
576 assert(!MRI->isReserved(Reg));
578 if (!RegMask->clobbersPhysReg(Reg)) {
583 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
586 // Make sure we invalidate any entries in the copy maps before erasing
588 Tracker.clobberRegister(Reg, *TRI);
590 // erase() will return the next valid iterator pointing to the next
591 // element after the erased one.
592 DI = MaybeDeadCopies.erase(DI);
593 MaybeDead->eraseFromParent();
599 // Any previous copy definition or reading the Defs is no longer available.
600 for (unsigned Reg : Defs)
601 Tracker.clobberRegister(Reg, *TRI);
604 // If MBB doesn't have successors, delete the copies whose defs are not used.
605 // If MBB does have successors, then conservative assume the defs are live-out
606 // since we don't want to trust live-in lists.
607 if (MBB.succ_empty()) {
608 for (MachineInstr *MaybeDead : MaybeDeadCopies) {
609 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
611 assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
613 // Update matching debug values.
614 assert(MaybeDead->isCopy());
615 MaybeDead->changeDebugValuesDefReg(MaybeDead->getOperand(1).getReg());
617 MaybeDead->eraseFromParent();
623 MaybeDeadCopies.clear();
627 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
628 if (skipFunction(MF.getFunction()))
633 TRI = MF.getSubtarget().getRegisterInfo();
634 TII = MF.getSubtarget().getInstrInfo();
635 MRI = &MF.getRegInfo();
637 for (MachineBasicBlock &MBB : MF)
638 CopyPropagateBlock(MBB);