1234285Sdim//===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// 2234285Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6234285Sdim// 7234285Sdim//===----------------------------------------------------------------------===// 8234285Sdim// 9234285Sdim// This is an extremely simple MachineInstr-level copy propagation pass. 10234285Sdim// 11341825Sdim// This pass forwards the source of COPYs to the users of their destinations 12341825Sdim// when doing so is legal. For example: 13341825Sdim// 14341825Sdim// %reg1 = COPY %reg0 15341825Sdim// ... 16341825Sdim// ... = OP %reg1 17341825Sdim// 18341825Sdim// If 19341825Sdim// - %reg0 has not been clobbered by the time of the use of %reg1 20341825Sdim// - the register class constraints are satisfied 21341825Sdim// - the COPY def is the only value that reaches OP 22341825Sdim// then this pass replaces the above with: 23341825Sdim// 24341825Sdim// %reg1 = COPY %reg0 25341825Sdim// ... 26341825Sdim// ... = OP %reg0 27341825Sdim// 28341825Sdim// This pass also removes some redundant COPYs. For example: 29341825Sdim// 30341825Sdim// %R1 = COPY %R0 31341825Sdim// ... // No clobber of %R1 32341825Sdim// %R0 = COPY %R1 <<< Removed 33341825Sdim// 34341825Sdim// or 35341825Sdim// 36341825Sdim// %R1 = COPY %R0 37341825Sdim// ... // No clobber of %R0 38341825Sdim// %R1 = COPY %R0 <<< Removed 39341825Sdim// 40360784Sdim// or 41360784Sdim// 42360784Sdim// $R0 = OP ... 43360784Sdim// ... // No read/clobber of $R0 and $R1 44360784Sdim// $R1 = COPY $R0 // $R0 is killed 45360784Sdim// Replace $R0 with $R1 and remove the COPY 46360784Sdim// $R1 = OP ... 47360784Sdim// ... 48360784Sdim// 49234285Sdim//===----------------------------------------------------------------------===// 50234285Sdim 51249423Sdim#include "llvm/ADT/DenseMap.h" 52327952Sdim#include "llvm/ADT/STLExtras.h" 53249423Sdim#include "llvm/ADT/SetVector.h" 54249423Sdim#include "llvm/ADT/SmallVector.h" 55249423Sdim#include "llvm/ADT/Statistic.h" 56327952Sdim#include "llvm/ADT/iterator_range.h" 57327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 58234285Sdim#include "llvm/CodeGen/MachineFunction.h" 59234285Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 60327952Sdim#include "llvm/CodeGen/MachineInstr.h" 61327952Sdim#include "llvm/CodeGen/MachineOperand.h" 62243830Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 63341825Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 64327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 65327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 66360784Sdim#include "llvm/InitializePasses.h" 67327952Sdim#include "llvm/MC/MCRegisterInfo.h" 68249423Sdim#include "llvm/Pass.h" 69234285Sdim#include "llvm/Support/Debug.h" 70341825Sdim#include "llvm/Support/DebugCounter.h" 71234285Sdim#include "llvm/Support/raw_ostream.h" 72327952Sdim#include <cassert> 73327952Sdim#include <iterator> 74327952Sdim 75234285Sdimusing namespace llvm; 76234285Sdim 77321369Sdim#define DEBUG_TYPE "machine-cp" 78276479Sdim 79234285SdimSTATISTIC(NumDeletes, "Number of dead copies deleted"); 80341825SdimSTATISTIC(NumCopyForwards, "Number of copy uses forwarded"); 81360784SdimSTATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated"); 82341825SdimDEBUG_COUNTER(FwdCounter, "machine-cp-fwd", 83341825Sdim "Controls which register COPYs are forwarded"); 84234285Sdim 85234285Sdimnamespace { 86309124Sdim 87344779Sdimclass CopyTracker { 88344779Sdim struct CopyInfo { 89344779Sdim MachineInstr *MI; 90344779Sdim SmallVector<unsigned, 4> DefRegs; 91344779Sdim bool Avail; 92344779Sdim }; 93327952Sdim 94344779Sdim DenseMap<unsigned, CopyInfo> Copies; 95234285Sdim 96344779Sdimpublic: 97344779Sdim /// Mark all of the given registers and their subregisters as unavailable for 98344779Sdim /// copying. 99344779Sdim void markRegsUnavailable(ArrayRef<unsigned> Regs, 100344779Sdim const TargetRegisterInfo &TRI) { 101344779Sdim for (unsigned Reg : Regs) { 102344779Sdim // Source of copy is no longer available for propagation. 103344779Sdim for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) { 104344779Sdim auto CI = Copies.find(*RUI); 105344779Sdim if (CI != Copies.end()) 106344779Sdim CI->second.Avail = false; 107344779Sdim } 108234285Sdim } 109344779Sdim } 110234285Sdim 111360784Sdim /// Remove register from copy maps. 112360784Sdim void invalidateRegister(unsigned Reg, const TargetRegisterInfo &TRI) { 113360784Sdim // Since Reg might be a subreg of some registers, only invalidate Reg is not 114360784Sdim // enough. We have to find the COPY defines Reg or registers defined by Reg 115360784Sdim // and invalidate all of them. 116360784Sdim DenseSet<unsigned> RegsToInvalidate{Reg}; 117360784Sdim for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) { 118360784Sdim auto I = Copies.find(*RUI); 119360784Sdim if (I != Copies.end()) { 120360784Sdim if (MachineInstr *MI = I->second.MI) { 121360784Sdim RegsToInvalidate.insert(MI->getOperand(0).getReg()); 122360784Sdim RegsToInvalidate.insert(MI->getOperand(1).getReg()); 123360784Sdim } 124360784Sdim RegsToInvalidate.insert(I->second.DefRegs.begin(), 125360784Sdim I->second.DefRegs.end()); 126360784Sdim } 127360784Sdim } 128360784Sdim for (unsigned InvalidReg : RegsToInvalidate) 129360784Sdim for (MCRegUnitIterator RUI(InvalidReg, &TRI); RUI.isValid(); ++RUI) 130360784Sdim Copies.erase(*RUI); 131360784Sdim } 132360784Sdim 133344779Sdim /// Clobber a single register, removing it from the tracker's copy maps. 134344779Sdim void clobberRegister(unsigned Reg, const TargetRegisterInfo &TRI) { 135344779Sdim for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) { 136344779Sdim auto I = Copies.find(*RUI); 137344779Sdim if (I != Copies.end()) { 138344779Sdim // When we clobber the source of a copy, we need to clobber everything 139344779Sdim // it defined. 140344779Sdim markRegsUnavailable(I->second.DefRegs, TRI); 141344779Sdim // When we clobber the destination of a copy, we need to clobber the 142344779Sdim // whole register it defined. 143344779Sdim if (MachineInstr *MI = I->second.MI) 144344779Sdim markRegsUnavailable({MI->getOperand(0).getReg()}, TRI); 145344779Sdim // Now we can erase the copy. 146344779Sdim Copies.erase(I); 147344779Sdim } 148309124Sdim } 149344779Sdim } 150309124Sdim 151344779Sdim /// Add this copy's registers into the tracker's copy maps. 152344779Sdim void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI) { 153344779Sdim assert(MI->isCopy() && "Tracking non-copy?"); 154234285Sdim 155360784Sdim Register Def = MI->getOperand(0).getReg(); 156360784Sdim Register Src = MI->getOperand(1).getReg(); 157309124Sdim 158344779Sdim // Remember Def is defined by the copy. 159344779Sdim for (MCRegUnitIterator RUI(Def, &TRI); RUI.isValid(); ++RUI) 160344779Sdim Copies[*RUI] = {MI, {}, true}; 161234285Sdim 162344779Sdim // Remember source that's copied to Def. Once it's clobbered, then 163344779Sdim // it's no longer available for copy propagation. 164344779Sdim for (MCRegUnitIterator RUI(Src, &TRI); RUI.isValid(); ++RUI) { 165344779Sdim auto I = Copies.insert({*RUI, {nullptr, {}, false}}); 166344779Sdim auto &Copy = I.first->second; 167344779Sdim if (!is_contained(Copy.DefRegs, Def)) 168344779Sdim Copy.DefRegs.push_back(Def); 169344779Sdim } 170344779Sdim } 171327952Sdim 172344779Sdim bool hasAnyCopies() { 173344779Sdim return !Copies.empty(); 174344779Sdim } 175327952Sdim 176344779Sdim MachineInstr *findCopyForUnit(unsigned RegUnit, const TargetRegisterInfo &TRI, 177344779Sdim bool MustBeAvailable = false) { 178344779Sdim auto CI = Copies.find(RegUnit); 179344779Sdim if (CI == Copies.end()) 180344779Sdim return nullptr; 181344779Sdim if (MustBeAvailable && !CI->second.Avail) 182344779Sdim return nullptr; 183344779Sdim return CI->second.MI; 184344779Sdim } 185327952Sdim 186360784Sdim MachineInstr *findCopyDefViaUnit(unsigned RegUnit, 187360784Sdim const TargetRegisterInfo &TRI) { 188360784Sdim auto CI = Copies.find(RegUnit); 189360784Sdim if (CI == Copies.end()) 190360784Sdim return nullptr; 191360784Sdim if (CI->second.DefRegs.size() != 1) 192360784Sdim return nullptr; 193360784Sdim MCRegUnitIterator RUI(CI->second.DefRegs[0], &TRI); 194360784Sdim return findCopyForUnit(*RUI, TRI, true); 195360784Sdim } 196360784Sdim 197360784Sdim MachineInstr *findAvailBackwardCopy(MachineInstr &I, unsigned Reg, 198360784Sdim const TargetRegisterInfo &TRI) { 199360784Sdim MCRegUnitIterator RUI(Reg, &TRI); 200360784Sdim MachineInstr *AvailCopy = findCopyDefViaUnit(*RUI, TRI); 201360784Sdim if (!AvailCopy || 202360784Sdim !TRI.isSubRegisterEq(AvailCopy->getOperand(1).getReg(), Reg)) 203360784Sdim return nullptr; 204360784Sdim 205360784Sdim Register AvailSrc = AvailCopy->getOperand(1).getReg(); 206360784Sdim Register AvailDef = AvailCopy->getOperand(0).getReg(); 207360784Sdim for (const MachineInstr &MI : 208360784Sdim make_range(AvailCopy->getReverseIterator(), I.getReverseIterator())) 209360784Sdim for (const MachineOperand &MO : MI.operands()) 210360784Sdim if (MO.isRegMask()) 211360784Sdim // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef? 212360784Sdim if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef)) 213360784Sdim return nullptr; 214360784Sdim 215360784Sdim return AvailCopy; 216360784Sdim } 217360784Sdim 218344779Sdim MachineInstr *findAvailCopy(MachineInstr &DestCopy, unsigned Reg, 219344779Sdim const TargetRegisterInfo &TRI) { 220344779Sdim // We check the first RegUnit here, since we'll only be interested in the 221344779Sdim // copy if it copies the entire register anyway. 222344779Sdim MCRegUnitIterator RUI(Reg, &TRI); 223344779Sdim MachineInstr *AvailCopy = 224344779Sdim findCopyForUnit(*RUI, TRI, /*MustBeAvailable=*/true); 225344779Sdim if (!AvailCopy || 226344779Sdim !TRI.isSubRegisterEq(AvailCopy->getOperand(0).getReg(), Reg)) 227344779Sdim return nullptr; 228327952Sdim 229344779Sdim // Check that the available copy isn't clobbered by any regmasks between 230344779Sdim // itself and the destination. 231360784Sdim Register AvailSrc = AvailCopy->getOperand(1).getReg(); 232360784Sdim Register AvailDef = AvailCopy->getOperand(0).getReg(); 233344779Sdim for (const MachineInstr &MI : 234344779Sdim make_range(AvailCopy->getIterator(), DestCopy.getIterator())) 235344779Sdim for (const MachineOperand &MO : MI.operands()) 236344779Sdim if (MO.isRegMask()) 237344779Sdim if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef)) 238344779Sdim return nullptr; 239327952Sdim 240344779Sdim return AvailCopy; 241344779Sdim } 242327952Sdim 243344779Sdim void clear() { 244344779Sdim Copies.clear(); 245344779Sdim } 246344779Sdim}; 247327952Sdim 248344779Sdimclass MachineCopyPropagation : public MachineFunctionPass { 249344779Sdim const TargetRegisterInfo *TRI; 250344779Sdim const TargetInstrInfo *TII; 251344779Sdim const MachineRegisterInfo *MRI; 252234285Sdim 253344779Sdimpublic: 254344779Sdim static char ID; // Pass identification, replacement for typeid 255234285Sdim 256344779Sdim MachineCopyPropagation() : MachineFunctionPass(ID) { 257344779Sdim initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 258309124Sdim } 259309124Sdim 260344779Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 261344779Sdim AU.setPreservesCFG(); 262344779Sdim MachineFunctionPass::getAnalysisUsage(AU); 263309124Sdim } 264309124Sdim 265344779Sdim bool runOnMachineFunction(MachineFunction &MF) override; 266309124Sdim 267344779Sdim MachineFunctionProperties getRequiredProperties() const override { 268344779Sdim return MachineFunctionProperties().set( 269344779Sdim MachineFunctionProperties::Property::NoVRegs); 270234285Sdim } 271234285Sdim 272344779Sdimprivate: 273360784Sdim typedef enum { DebugUse = false, RegularUse = true } DebugType; 274360784Sdim 275344779Sdim void ClobberRegister(unsigned Reg); 276360784Sdim void ReadRegister(unsigned Reg, MachineInstr &Reader, 277360784Sdim DebugType DT); 278360784Sdim void ForwardCopyPropagateBlock(MachineBasicBlock &MBB); 279360784Sdim void BackwardCopyPropagateBlock(MachineBasicBlock &MBB); 280344779Sdim bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def); 281344779Sdim void forwardUses(MachineInstr &MI); 282360784Sdim void propagateDefs(MachineInstr &MI); 283344779Sdim bool isForwardableRegClassCopy(const MachineInstr &Copy, 284344779Sdim const MachineInstr &UseI, unsigned UseIdx); 285360784Sdim bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy, 286360784Sdim const MachineInstr &UseI, 287360784Sdim unsigned UseIdx); 288344779Sdim bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use); 289344779Sdim 290344779Sdim /// Candidates for deletion. 291344779Sdim SmallSetVector<MachineInstr *, 8> MaybeDeadCopies; 292344779Sdim 293360784Sdim /// Multimap tracking debug users in current BB 294360784Sdim DenseMap<MachineInstr*, SmallVector<MachineInstr*, 2>> CopyDbgUsers; 295360784Sdim 296344779Sdim CopyTracker Tracker; 297344779Sdim 298344779Sdim bool Changed; 299344779Sdim}; 300344779Sdim 301344779Sdim} // end anonymous namespace 302344779Sdim 303344779Sdimchar MachineCopyPropagation::ID = 0; 304344779Sdim 305344779Sdimchar &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 306344779Sdim 307344779SdimINITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE, 308344779Sdim "Machine Copy Propagation Pass", false, false) 309344779Sdim 310360784Sdimvoid MachineCopyPropagation::ReadRegister(unsigned Reg, MachineInstr &Reader, 311360784Sdim DebugType DT) { 312314564Sdim // If 'Reg' is defined by a copy, the copy is no longer a candidate 313360784Sdim // for elimination. If a copy is "read" by a debug user, record the user 314360784Sdim // for propagation. 315344779Sdim for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) { 316344779Sdim if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) { 317360784Sdim if (DT == RegularUse) { 318360784Sdim LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump()); 319360784Sdim MaybeDeadCopies.remove(Copy); 320360784Sdim } else { 321360784Sdim CopyDbgUsers[Copy].push_back(&Reader); 322360784Sdim } 323314564Sdim } 324314564Sdim } 325314564Sdim} 326314564Sdim 327309124Sdim/// Return true if \p PreviousCopy did copy register \p Src to register \p Def. 328309124Sdim/// This fact may have been obscured by sub register usage or may not be true at 329309124Sdim/// all even though Src and Def are subregisters of the registers used in 330309124Sdim/// PreviousCopy. e.g. 331309124Sdim/// isNopCopy("ecx = COPY eax", AX, CX) == true 332309124Sdim/// isNopCopy("ecx = COPY eax", AH, CL) == false 333309124Sdimstatic bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src, 334309124Sdim unsigned Def, const TargetRegisterInfo *TRI) { 335360784Sdim Register PreviousSrc = PreviousCopy.getOperand(1).getReg(); 336360784Sdim Register PreviousDef = PreviousCopy.getOperand(0).getReg(); 337309124Sdim if (Src == PreviousSrc) { 338309124Sdim assert(Def == PreviousDef); 339309124Sdim return true; 340309124Sdim } 341309124Sdim if (!TRI->isSubRegister(PreviousSrc, Src)) 342234285Sdim return false; 343309124Sdim unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src); 344309124Sdim return SubIdx == TRI->getSubRegIndex(PreviousDef, Def); 345234285Sdim} 346234285Sdim 347309124Sdim/// Remove instruction \p Copy if there exists a previous copy that copies the 348309124Sdim/// register \p Src to the register \p Def; This may happen indirectly by 349309124Sdim/// copying the super registers. 350309124Sdimbool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src, 351309124Sdim unsigned Def) { 352309124Sdim // Avoid eliminating a copy from/to a reserved registers as we cannot predict 353309124Sdim // the value (Example: The sparc zero register is writable but stays zero). 354309124Sdim if (MRI->isReserved(Src) || MRI->isReserved(Def)) 355309124Sdim return false; 356234285Sdim 357309124Sdim // Search for an existing copy. 358344779Sdim MachineInstr *PrevCopy = Tracker.findAvailCopy(Copy, Def, *TRI); 359344779Sdim if (!PrevCopy) 360309124Sdim return false; 361309124Sdim 362309124Sdim // Check that the existing copy uses the correct sub registers. 363344779Sdim if (PrevCopy->getOperand(0).isDead()) 364327952Sdim return false; 365344779Sdim if (!isNopCopy(*PrevCopy, Src, Def, TRI)) 366309124Sdim return false; 367309124Sdim 368341825Sdim LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump()); 369309124Sdim 370309124Sdim // Copy was redundantly redefining either Src or Def. Remove earlier kill 371309124Sdim // flags between Copy and PrevCopy because the value will be reused now. 372309124Sdim assert(Copy.isCopy()); 373360784Sdim Register CopyDef = Copy.getOperand(0).getReg(); 374309124Sdim assert(CopyDef == Src || CopyDef == Def); 375309124Sdim for (MachineInstr &MI : 376344779Sdim make_range(PrevCopy->getIterator(), Copy.getIterator())) 377309124Sdim MI.clearRegisterKills(CopyDef, TRI); 378309124Sdim 379309124Sdim Copy.eraseFromParent(); 380309124Sdim Changed = true; 381309124Sdim ++NumDeletes; 382309124Sdim return true; 383234285Sdim} 384234285Sdim 385360784Sdimbool MachineCopyPropagation::isBackwardPropagatableRegClassCopy( 386360784Sdim const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) { 387360784Sdim Register Def = Copy.getOperand(0).getReg(); 388360784Sdim 389360784Sdim if (const TargetRegisterClass *URC = 390360784Sdim UseI.getRegClassConstraint(UseIdx, TII, TRI)) 391360784Sdim return URC->contains(Def); 392360784Sdim 393360784Sdim // We don't process further if UseI is a COPY, since forward copy propagation 394360784Sdim // should handle that. 395360784Sdim return false; 396360784Sdim} 397360784Sdim 398341825Sdim/// Decide whether we should forward the source of \param Copy to its use in 399341825Sdim/// \param UseI based on the physical register class constraints of the opcode 400341825Sdim/// and avoiding introducing more cross-class COPYs. 401341825Sdimbool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy, 402341825Sdim const MachineInstr &UseI, 403341825Sdim unsigned UseIdx) { 404341825Sdim 405360784Sdim Register CopySrcReg = Copy.getOperand(1).getReg(); 406341825Sdim 407341825Sdim // If the new register meets the opcode register constraints, then allow 408341825Sdim // forwarding. 409341825Sdim if (const TargetRegisterClass *URC = 410341825Sdim UseI.getRegClassConstraint(UseIdx, TII, TRI)) 411341825Sdim return URC->contains(CopySrcReg); 412341825Sdim 413341825Sdim if (!UseI.isCopy()) 414341825Sdim return false; 415341825Sdim 416341825Sdim /// COPYs don't have register class constraints, so if the user instruction 417341825Sdim /// is a COPY, we just try to avoid introducing additional cross-class 418341825Sdim /// COPYs. For example: 419341825Sdim /// 420341825Sdim /// RegClassA = COPY RegClassB // Copy parameter 421341825Sdim /// ... 422341825Sdim /// RegClassB = COPY RegClassA // UseI parameter 423341825Sdim /// 424341825Sdim /// which after forwarding becomes 425341825Sdim /// 426341825Sdim /// RegClassA = COPY RegClassB 427341825Sdim /// ... 428341825Sdim /// RegClassB = COPY RegClassB 429341825Sdim /// 430341825Sdim /// so we have reduced the number of cross-class COPYs and potentially 431341825Sdim /// introduced a nop COPY that can be removed. 432341825Sdim const TargetRegisterClass *UseDstRC = 433341825Sdim TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg()); 434341825Sdim 435341825Sdim const TargetRegisterClass *SuperRC = UseDstRC; 436341825Sdim for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses(); 437341825Sdim SuperRC; SuperRC = *SuperRCI++) 438341825Sdim if (SuperRC->contains(CopySrcReg)) 439341825Sdim return true; 440341825Sdim 441341825Sdim return false; 442341825Sdim} 443341825Sdim 444341825Sdim/// Check that \p MI does not have implicit uses that overlap with it's \p Use 445341825Sdim/// operand (the register being replaced), since these can sometimes be 446341825Sdim/// implicitly tied to other operands. For example, on AMDGPU: 447341825Sdim/// 448341825Sdim/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use> 449341825Sdim/// 450341825Sdim/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no 451341825Sdim/// way of knowing we need to update the latter when updating the former. 452341825Sdimbool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI, 453341825Sdim const MachineOperand &Use) { 454341825Sdim for (const MachineOperand &MIUse : MI.uses()) 455341825Sdim if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() && 456341825Sdim MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg())) 457341825Sdim return true; 458341825Sdim 459341825Sdim return false; 460341825Sdim} 461341825Sdim 462341825Sdim/// Look for available copies whose destination register is used by \p MI and 463341825Sdim/// replace the use in \p MI with the copy's source register. 464341825Sdimvoid MachineCopyPropagation::forwardUses(MachineInstr &MI) { 465344779Sdim if (!Tracker.hasAnyCopies()) 466341825Sdim return; 467341825Sdim 468341825Sdim // Look for non-tied explicit vreg uses that have an active COPY 469341825Sdim // instruction that defines the physical register allocated to them. 470341825Sdim // Replace the vreg with the source of the active COPY. 471341825Sdim for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd; 472341825Sdim ++OpIdx) { 473341825Sdim MachineOperand &MOUse = MI.getOperand(OpIdx); 474341825Sdim // Don't forward into undef use operands since doing so can cause problems 475341825Sdim // with the machine verifier, since it doesn't treat undef reads as reads, 476341825Sdim // so we can end up with a live range that ends on an undef read, leading to 477341825Sdim // an error that the live range doesn't end on a read of the live range 478341825Sdim // register. 479341825Sdim if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() || 480341825Sdim MOUse.isImplicit()) 481341825Sdim continue; 482341825Sdim 483341825Sdim if (!MOUse.getReg()) 484341825Sdim continue; 485341825Sdim 486341825Sdim // Check that the register is marked 'renamable' so we know it is safe to 487341825Sdim // rename it without violating any constraints that aren't expressed in the 488341825Sdim // IR (e.g. ABI or opcode requirements). 489341825Sdim if (!MOUse.isRenamable()) 490341825Sdim continue; 491341825Sdim 492344779Sdim MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg(), *TRI); 493344779Sdim if (!Copy) 494341825Sdim continue; 495341825Sdim 496360784Sdim Register CopyDstReg = Copy->getOperand(0).getReg(); 497344779Sdim const MachineOperand &CopySrc = Copy->getOperand(1); 498360784Sdim Register CopySrcReg = CopySrc.getReg(); 499341825Sdim 500341825Sdim // FIXME: Don't handle partial uses of wider COPYs yet. 501341825Sdim if (MOUse.getReg() != CopyDstReg) { 502341825Sdim LLVM_DEBUG( 503341825Sdim dbgs() << "MCP: FIXME! Not forwarding COPY to sub-register use:\n " 504341825Sdim << MI); 505341825Sdim continue; 506341825Sdim } 507341825Sdim 508341825Sdim // Don't forward COPYs of reserved regs unless they are constant. 509341825Sdim if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg)) 510341825Sdim continue; 511341825Sdim 512344779Sdim if (!isForwardableRegClassCopy(*Copy, MI, OpIdx)) 513341825Sdim continue; 514341825Sdim 515341825Sdim if (hasImplicitOverlap(MI, MOUse)) 516341825Sdim continue; 517341825Sdim 518360784Sdim // Check that the instruction is not a copy that partially overwrites the 519360784Sdim // original copy source that we are about to use. The tracker mechanism 520360784Sdim // cannot cope with that. 521360784Sdim if (MI.isCopy() && MI.modifiesRegister(CopySrcReg, TRI) && 522360784Sdim !MI.definesRegister(CopySrcReg)) { 523360784Sdim LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI); 524360784Sdim continue; 525360784Sdim } 526360784Sdim 527341825Sdim if (!DebugCounter::shouldExecute(FwdCounter)) { 528341825Sdim LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n " 529341825Sdim << MI); 530341825Sdim continue; 531341825Sdim } 532341825Sdim 533341825Sdim LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI) 534341825Sdim << "\n with " << printReg(CopySrcReg, TRI) 535344779Sdim << "\n in " << MI << " from " << *Copy); 536341825Sdim 537341825Sdim MOUse.setReg(CopySrcReg); 538341825Sdim if (!CopySrc.isRenamable()) 539341825Sdim MOUse.setIsRenamable(false); 540341825Sdim 541341825Sdim LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n"); 542341825Sdim 543341825Sdim // Clear kill markers that may have been invalidated. 544341825Sdim for (MachineInstr &KMI : 545344779Sdim make_range(Copy->getIterator(), std::next(MI.getIterator()))) 546341825Sdim KMI.clearRegisterKills(CopySrcReg, TRI); 547341825Sdim 548341825Sdim ++NumCopyForwards; 549341825Sdim Changed = true; 550341825Sdim } 551341825Sdim} 552341825Sdim 553360784Sdimvoid MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) { 554360784Sdim LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName() 555360784Sdim << "\n"); 556276479Sdim 557234285Sdim for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 558234285Sdim MachineInstr *MI = &*I; 559234285Sdim ++I; 560234285Sdim 561341825Sdim // Analyze copies (which don't overlap themselves). 562341825Sdim if (MI->isCopy() && !TRI->regsOverlap(MI->getOperand(0).getReg(), 563341825Sdim MI->getOperand(1).getReg())) { 564360784Sdim Register Def = MI->getOperand(0).getReg(); 565360784Sdim Register Src = MI->getOperand(1).getReg(); 566234285Sdim 567360784Sdim assert(!Register::isVirtualRegister(Def) && 568360784Sdim !Register::isVirtualRegister(Src) && 569309124Sdim "MachineCopyPropagation should be run after register allocation!"); 570234285Sdim 571309124Sdim // The two copies cancel out and the source of the first copy 572309124Sdim // hasn't been overridden, eliminate the second one. e.g. 573327952Sdim // %ecx = COPY %eax 574327952Sdim // ... nothing clobbered eax. 575327952Sdim // %eax = COPY %ecx 576309124Sdim // => 577327952Sdim // %ecx = COPY %eax 578309124Sdim // 579309124Sdim // or 580309124Sdim // 581327952Sdim // %ecx = COPY %eax 582327952Sdim // ... nothing clobbered eax. 583327952Sdim // %ecx = COPY %eax 584309124Sdim // => 585327952Sdim // %ecx = COPY %eax 586309124Sdim if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def)) 587309124Sdim continue; 588234285Sdim 589341825Sdim forwardUses(*MI); 590341825Sdim 591341825Sdim // Src may have been changed by forwardUses() 592341825Sdim Src = MI->getOperand(1).getReg(); 593341825Sdim 594309124Sdim // If Src is defined by a previous copy, the previous copy cannot be 595309124Sdim // eliminated. 596360784Sdim ReadRegister(Src, *MI, RegularUse); 597314564Sdim for (const MachineOperand &MO : MI->implicit_operands()) { 598314564Sdim if (!MO.isReg() || !MO.readsReg()) 599314564Sdim continue; 600360784Sdim Register Reg = MO.getReg(); 601314564Sdim if (!Reg) 602314564Sdim continue; 603360784Sdim ReadRegister(Reg, *MI, RegularUse); 604234285Sdim } 605234285Sdim 606341825Sdim LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); 607276479Sdim 608234285Sdim // Copy is now a candidate for deletion. 609309124Sdim if (!MRI->isReserved(Def)) 610309124Sdim MaybeDeadCopies.insert(MI); 611234285Sdim 612309124Sdim // If 'Def' is previously source of another copy, then this earlier copy's 613234285Sdim // source is no longer available. e.g. 614327952Sdim // %xmm9 = copy %xmm2 615234285Sdim // ... 616327952Sdim // %xmm2 = copy %xmm0 617234285Sdim // ... 618327952Sdim // %xmm2 = copy %xmm9 619344779Sdim Tracker.clobberRegister(Def, *TRI); 620314564Sdim for (const MachineOperand &MO : MI->implicit_operands()) { 621314564Sdim if (!MO.isReg() || !MO.isDef()) 622314564Sdim continue; 623360784Sdim Register Reg = MO.getReg(); 624314564Sdim if (!Reg) 625314564Sdim continue; 626344779Sdim Tracker.clobberRegister(Reg, *TRI); 627314564Sdim } 628234285Sdim 629344779Sdim Tracker.trackCopy(MI, *TRI); 630234285Sdim 631234285Sdim continue; 632234285Sdim } 633234285Sdim 634341825Sdim // Clobber any earlyclobber regs first. 635341825Sdim for (const MachineOperand &MO : MI->operands()) 636341825Sdim if (MO.isReg() && MO.isEarlyClobber()) { 637360784Sdim Register Reg = MO.getReg(); 638341825Sdim // If we have a tied earlyclobber, that means it is also read by this 639341825Sdim // instruction, so we need to make sure we don't remove it as dead 640341825Sdim // later. 641341825Sdim if (MO.isTied()) 642360784Sdim ReadRegister(Reg, *MI, RegularUse); 643344779Sdim Tracker.clobberRegister(Reg, *TRI); 644341825Sdim } 645341825Sdim 646341825Sdim forwardUses(*MI); 647341825Sdim 648234285Sdim // Not a copy. 649234285Sdim SmallVector<unsigned, 2> Defs; 650309124Sdim const MachineOperand *RegMask = nullptr; 651309124Sdim for (const MachineOperand &MO : MI->operands()) { 652234285Sdim if (MO.isRegMask()) 653309124Sdim RegMask = &MO; 654234285Sdim if (!MO.isReg()) 655234285Sdim continue; 656360784Sdim Register Reg = MO.getReg(); 657234285Sdim if (!Reg) 658234285Sdim continue; 659234285Sdim 660360784Sdim assert(!Register::isVirtualRegister(Reg) && 661309124Sdim "MachineCopyPropagation should be run after register allocation!"); 662234285Sdim 663341825Sdim if (MO.isDef() && !MO.isEarlyClobber()) { 664234285Sdim Defs.push_back(Reg); 665321369Sdim continue; 666360784Sdim } else if (MO.readsReg()) 667360784Sdim ReadRegister(Reg, *MI, MO.isDebug() ? DebugUse : RegularUse); 668234285Sdim } 669234285Sdim 670234285Sdim // The instruction has a register mask operand which means that it clobbers 671309124Sdim // a large set of registers. Treat clobbered registers the same way as 672309124Sdim // defined registers. 673309124Sdim if (RegMask) { 674234285Sdim // Erase any MaybeDeadCopies whose destination register is clobbered. 675309124Sdim for (SmallSetVector<MachineInstr *, 8>::iterator DI = 676309124Sdim MaybeDeadCopies.begin(); 677309124Sdim DI != MaybeDeadCopies.end();) { 678309124Sdim MachineInstr *MaybeDead = *DI; 679360784Sdim Register Reg = MaybeDead->getOperand(0).getReg(); 680309124Sdim assert(!MRI->isReserved(Reg)); 681309124Sdim 682309124Sdim if (!RegMask->clobbersPhysReg(Reg)) { 683309124Sdim ++DI; 684234285Sdim continue; 685309124Sdim } 686309124Sdim 687341825Sdim LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 688341825Sdim MaybeDead->dump()); 689309124Sdim 690344779Sdim // Make sure we invalidate any entries in the copy maps before erasing 691344779Sdim // the instruction. 692344779Sdim Tracker.clobberRegister(Reg, *TRI); 693344779Sdim 694309124Sdim // erase() will return the next valid iterator pointing to the next 695309124Sdim // element after the erased one. 696309124Sdim DI = MaybeDeadCopies.erase(DI); 697309124Sdim MaybeDead->eraseFromParent(); 698234285Sdim Changed = true; 699234285Sdim ++NumDeletes; 700234285Sdim } 701234285Sdim } 702234285Sdim 703309124Sdim // Any previous copy definition or reading the Defs is no longer available. 704309124Sdim for (unsigned Reg : Defs) 705344779Sdim Tracker.clobberRegister(Reg, *TRI); 706234285Sdim } 707234285Sdim 708234285Sdim // If MBB doesn't have successors, delete the copies whose defs are not used. 709234285Sdim // If MBB does have successors, then conservative assume the defs are live-out 710234285Sdim // since we don't want to trust live-in lists. 711234285Sdim if (MBB.succ_empty()) { 712309124Sdim for (MachineInstr *MaybeDead : MaybeDeadCopies) { 713341825Sdim LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: "; 714341825Sdim MaybeDead->dump()); 715309124Sdim assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg())); 716344779Sdim 717360784Sdim // Update matching debug values, if any. 718344779Sdim assert(MaybeDead->isCopy()); 719360784Sdim unsigned SrcReg = MaybeDead->getOperand(1).getReg(); 720360784Sdim MRI->updateDbgUsersToReg(SrcReg, CopyDbgUsers[MaybeDead]); 721344779Sdim 722309124Sdim MaybeDead->eraseFromParent(); 723309124Sdim Changed = true; 724309124Sdim ++NumDeletes; 725234285Sdim } 726234285Sdim } 727234285Sdim 728309124Sdim MaybeDeadCopies.clear(); 729360784Sdim CopyDbgUsers.clear(); 730344779Sdim Tracker.clear(); 731234285Sdim} 732234285Sdim 733360784Sdimstatic bool isBackwardPropagatableCopy(MachineInstr &MI, 734360784Sdim const MachineRegisterInfo &MRI) { 735360784Sdim assert(MI.isCopy() && "MI is expected to be a COPY"); 736360784Sdim Register Def = MI.getOperand(0).getReg(); 737360784Sdim Register Src = MI.getOperand(1).getReg(); 738360784Sdim 739360784Sdim if (!Def || !Src) 740360784Sdim return false; 741360784Sdim 742360784Sdim if (MRI.isReserved(Def) || MRI.isReserved(Src)) 743360784Sdim return false; 744360784Sdim 745360784Sdim return MI.getOperand(1).isRenamable() && MI.getOperand(1).isKill(); 746360784Sdim} 747360784Sdim 748360784Sdimvoid MachineCopyPropagation::propagateDefs(MachineInstr &MI) { 749360784Sdim if (!Tracker.hasAnyCopies()) 750360784Sdim return; 751360784Sdim 752360784Sdim for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd; 753360784Sdim ++OpIdx) { 754360784Sdim MachineOperand &MODef = MI.getOperand(OpIdx); 755360784Sdim 756360784Sdim if (!MODef.isReg() || MODef.isUse()) 757360784Sdim continue; 758360784Sdim 759360784Sdim // Ignore non-trivial cases. 760360784Sdim if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit()) 761360784Sdim continue; 762360784Sdim 763360784Sdim if (!MODef.getReg()) 764360784Sdim continue; 765360784Sdim 766360784Sdim // We only handle if the register comes from a vreg. 767360784Sdim if (!MODef.isRenamable()) 768360784Sdim continue; 769360784Sdim 770360784Sdim MachineInstr *Copy = 771360784Sdim Tracker.findAvailBackwardCopy(MI, MODef.getReg(), *TRI); 772360784Sdim if (!Copy) 773360784Sdim continue; 774360784Sdim 775360784Sdim Register Def = Copy->getOperand(0).getReg(); 776360784Sdim Register Src = Copy->getOperand(1).getReg(); 777360784Sdim 778360784Sdim if (MODef.getReg() != Src) 779360784Sdim continue; 780360784Sdim 781360784Sdim if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx)) 782360784Sdim continue; 783360784Sdim 784360784Sdim if (hasImplicitOverlap(MI, MODef)) 785360784Sdim continue; 786360784Sdim 787360784Sdim LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI) 788360784Sdim << "\n with " << printReg(Def, TRI) << "\n in " 789360784Sdim << MI << " from " << *Copy); 790360784Sdim 791360784Sdim MODef.setReg(Def); 792360784Sdim MODef.setIsRenamable(Copy->getOperand(0).isRenamable()); 793360784Sdim 794360784Sdim LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n"); 795360784Sdim MaybeDeadCopies.insert(Copy); 796360784Sdim Changed = true; 797360784Sdim ++NumCopyBackwardPropagated; 798360784Sdim } 799360784Sdim} 800360784Sdim 801360784Sdimvoid MachineCopyPropagation::BackwardCopyPropagateBlock( 802360784Sdim MachineBasicBlock &MBB) { 803360784Sdim LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName() 804360784Sdim << "\n"); 805360784Sdim 806360784Sdim for (MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend(); 807360784Sdim I != E;) { 808360784Sdim MachineInstr *MI = &*I; 809360784Sdim ++I; 810360784Sdim 811360784Sdim // Ignore non-trivial COPYs. 812360784Sdim if (MI->isCopy() && MI->getNumOperands() == 2 && 813360784Sdim !TRI->regsOverlap(MI->getOperand(0).getReg(), 814360784Sdim MI->getOperand(1).getReg())) { 815360784Sdim 816360784Sdim Register Def = MI->getOperand(0).getReg(); 817360784Sdim Register Src = MI->getOperand(1).getReg(); 818360784Sdim 819360784Sdim // Unlike forward cp, we don't invoke propagateDefs here, 820360784Sdim // just let forward cp do COPY-to-COPY propagation. 821360784Sdim if (isBackwardPropagatableCopy(*MI, *MRI)) { 822360784Sdim Tracker.invalidateRegister(Src, *TRI); 823360784Sdim Tracker.invalidateRegister(Def, *TRI); 824360784Sdim Tracker.trackCopy(MI, *TRI); 825360784Sdim continue; 826360784Sdim } 827360784Sdim } 828360784Sdim 829360784Sdim // Invalidate any earlyclobber regs first. 830360784Sdim for (const MachineOperand &MO : MI->operands()) 831360784Sdim if (MO.isReg() && MO.isEarlyClobber()) { 832360784Sdim Register Reg = MO.getReg(); 833360784Sdim if (!Reg) 834360784Sdim continue; 835360784Sdim Tracker.invalidateRegister(Reg, *TRI); 836360784Sdim } 837360784Sdim 838360784Sdim propagateDefs(*MI); 839360784Sdim for (const MachineOperand &MO : MI->operands()) { 840360784Sdim if (!MO.isReg()) 841360784Sdim continue; 842360784Sdim 843360784Sdim if (!MO.getReg()) 844360784Sdim continue; 845360784Sdim 846360784Sdim if (MO.isDef()) 847360784Sdim Tracker.invalidateRegister(MO.getReg(), *TRI); 848360784Sdim 849360784Sdim if (MO.readsReg()) 850360784Sdim Tracker.invalidateRegister(MO.getReg(), *TRI); 851360784Sdim } 852360784Sdim } 853360784Sdim 854360784Sdim for (auto *Copy : MaybeDeadCopies) { 855360784Sdim Copy->eraseFromParent(); 856360784Sdim ++NumDeletes; 857360784Sdim } 858360784Sdim 859360784Sdim MaybeDeadCopies.clear(); 860360784Sdim CopyDbgUsers.clear(); 861360784Sdim Tracker.clear(); 862360784Sdim} 863360784Sdim 864234285Sdimbool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 865327952Sdim if (skipFunction(MF.getFunction())) 866276479Sdim return false; 867276479Sdim 868309124Sdim Changed = false; 869234285Sdim 870280031Sdim TRI = MF.getSubtarget().getRegisterInfo(); 871280031Sdim TII = MF.getSubtarget().getInstrInfo(); 872243830Sdim MRI = &MF.getRegInfo(); 873234285Sdim 874360784Sdim for (MachineBasicBlock &MBB : MF) { 875360784Sdim BackwardCopyPropagateBlock(MBB); 876360784Sdim ForwardCopyPropagateBlock(MBB); 877360784Sdim } 878234285Sdim 879234285Sdim return Changed; 880234285Sdim} 881