1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This is an extremely simple MachineInstr-level copy propagation pass. 10 // 11 // This pass forwards the source of COPYs to the users of their destinations 12 // when doing so is legal. For example: 13 // 14 // %reg1 = COPY %reg0 15 // ... 16 // ... = OP %reg1 17 // 18 // If 19 // - %reg0 has not been clobbered by the time of the use of %reg1 20 // - the register class constraints are satisfied 21 // - the COPY def is the only value that reaches OP 22 // then this pass replaces the above with: 23 // 24 // %reg1 = COPY %reg0 25 // ... 26 // ... = OP %reg0 27 // 28 // This pass also removes some redundant COPYs. For example: 29 // 30 // %R1 = COPY %R0 31 // ... // No clobber of %R1 32 // %R0 = COPY %R1 <<< Removed 33 // 34 // or 35 // 36 // %R1 = COPY %R0 37 // ... // No clobber of %R0 38 // %R1 = COPY %R0 <<< Removed 39 // 40 // or 41 // 42 // $R0 = OP ... 43 // ... // No read/clobber of $R0 and $R1 44 // $R1 = COPY $R0 // $R0 is killed 45 // Replace $R0 with $R1 and remove the COPY 46 // $R1 = OP ... 47 // ... 48 // 49 //===----------------------------------------------------------------------===// 50 51 #include "llvm/ADT/DenseMap.h" 52 #include "llvm/ADT/STLExtras.h" 53 #include "llvm/ADT/SetVector.h" 54 #include "llvm/ADT/SmallSet.h" 55 #include "llvm/ADT/SmallVector.h" 56 #include "llvm/ADT/Statistic.h" 57 #include "llvm/ADT/iterator_range.h" 58 #include "llvm/CodeGen/MachineBasicBlock.h" 59 #include "llvm/CodeGen/MachineFunction.h" 60 #include "llvm/CodeGen/MachineFunctionPass.h" 61 #include "llvm/CodeGen/MachineInstr.h" 62 #include "llvm/CodeGen/MachineOperand.h" 63 #include "llvm/CodeGen/MachineRegisterInfo.h" 64 #include "llvm/CodeGen/TargetInstrInfo.h" 65 #include "llvm/CodeGen/TargetRegisterInfo.h" 66 #include "llvm/CodeGen/TargetSubtargetInfo.h" 67 #include "llvm/InitializePasses.h" 68 #include "llvm/MC/MCRegisterInfo.h" 69 #include "llvm/Pass.h" 70 #include "llvm/Support/Debug.h" 71 #include "llvm/Support/DebugCounter.h" 72 #include "llvm/Support/raw_ostream.h" 73 #include <cassert> 74 #include <iterator> 75 76 using namespace llvm; 77 78 #define DEBUG_TYPE "machine-cp" 79 80 STATISTIC(NumDeletes, "Number of dead copies deleted"); 81 STATISTIC(NumCopyForwards, "Number of copy uses forwarded"); 82 STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated"); 83 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd", 84 "Controls which register COPYs are forwarded"); 85 86 namespace { 87 88 class CopyTracker { 89 struct CopyInfo { 90 MachineInstr *MI; 91 SmallVector<unsigned, 4> DefRegs; 92 bool Avail; 93 }; 94 95 DenseMap<unsigned, CopyInfo> Copies; 96 97 public: 98 /// Mark all of the given registers and their subregisters as unavailable for 99 /// copying. 100 void markRegsUnavailable(ArrayRef<unsigned> Regs, 101 const TargetRegisterInfo &TRI) { 102 for (unsigned Reg : Regs) { 103 // Source of copy is no longer available for propagation. 104 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) { 105 auto CI = Copies.find(*RUI); 106 if (CI != Copies.end()) 107 CI->second.Avail = false; 108 } 109 } 110 } 111 112 /// Remove register from copy maps. 113 void invalidateRegister(unsigned Reg, const TargetRegisterInfo &TRI) { 114 // Since Reg might be a subreg of some registers, only invalidate Reg is not 115 // enough. We have to find the COPY defines Reg or registers defined by Reg 116 // and invalidate all of them. 117 SmallSet<unsigned, 8> RegsToInvalidate; 118 RegsToInvalidate.insert(Reg); 119 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) { 120 auto I = Copies.find(*RUI); 121 if (I != Copies.end()) { 122 if (MachineInstr *MI = I->second.MI) { 123 RegsToInvalidate.insert(MI->getOperand(0).getReg()); 124 RegsToInvalidate.insert(MI->getOperand(1).getReg()); 125 } 126 RegsToInvalidate.insert(I->second.DefRegs.begin(), 127 I->second.DefRegs.end()); 128 } 129 } 130 for (unsigned InvalidReg : RegsToInvalidate) 131 for (MCRegUnitIterator RUI(InvalidReg, &TRI); RUI.isValid(); ++RUI) 132 Copies.erase(*RUI); 133 } 134 135 /// Clobber a single register, removing it from the tracker's copy maps. 136 void clobberRegister(unsigned Reg, const TargetRegisterInfo &TRI) { 137 for (MCRegUnitIterator RUI(Reg, &TRI); RUI.isValid(); ++RUI) { 138 auto I = Copies.find(*RUI); 139 if (I != Copies.end()) { 140 // When we clobber the source of a copy, we need to clobber everything 141 // it defined. 142 markRegsUnavailable(I->second.DefRegs, TRI); 143 // When we clobber the destination of a copy, we need to clobber the 144 // whole register it defined. 145 if (MachineInstr *MI = I->second.MI) 146 markRegsUnavailable({MI->getOperand(0).getReg()}, TRI); 147 // Now we can erase the copy. 148 Copies.erase(I); 149 } 150 } 151 } 152 153 /// Add this copy's registers into the tracker's copy maps. 154 void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI) { 155 assert(MI->isCopy() && "Tracking non-copy?"); 156 157 Register Def = MI->getOperand(0).getReg(); 158 Register Src = MI->getOperand(1).getReg(); 159 160 // Remember Def is defined by the copy. 161 for (MCRegUnitIterator RUI(Def, &TRI); RUI.isValid(); ++RUI) 162 Copies[*RUI] = {MI, {}, true}; 163 164 // Remember source that's copied to Def. Once it's clobbered, then 165 // it's no longer available for copy propagation. 166 for (MCRegUnitIterator RUI(Src, &TRI); RUI.isValid(); ++RUI) { 167 auto I = Copies.insert({*RUI, {nullptr, {}, false}}); 168 auto &Copy = I.first->second; 169 if (!is_contained(Copy.DefRegs, Def)) 170 Copy.DefRegs.push_back(Def); 171 } 172 } 173 174 bool hasAnyCopies() { 175 return !Copies.empty(); 176 } 177 178 MachineInstr *findCopyForUnit(unsigned RegUnit, const TargetRegisterInfo &TRI, 179 bool MustBeAvailable = false) { 180 auto CI = Copies.find(RegUnit); 181 if (CI == Copies.end()) 182 return nullptr; 183 if (MustBeAvailable && !CI->second.Avail) 184 return nullptr; 185 return CI->second.MI; 186 } 187 188 MachineInstr *findCopyDefViaUnit(unsigned RegUnit, 189 const TargetRegisterInfo &TRI) { 190 auto CI = Copies.find(RegUnit); 191 if (CI == Copies.end()) 192 return nullptr; 193 if (CI->second.DefRegs.size() != 1) 194 return nullptr; 195 MCRegUnitIterator RUI(CI->second.DefRegs[0], &TRI); 196 return findCopyForUnit(*RUI, TRI, true); 197 } 198 199 MachineInstr *findAvailBackwardCopy(MachineInstr &I, unsigned Reg, 200 const TargetRegisterInfo &TRI) { 201 MCRegUnitIterator RUI(Reg, &TRI); 202 MachineInstr *AvailCopy = findCopyDefViaUnit(*RUI, TRI); 203 if (!AvailCopy || 204 !TRI.isSubRegisterEq(AvailCopy->getOperand(1).getReg(), Reg)) 205 return nullptr; 206 207 Register AvailSrc = AvailCopy->getOperand(1).getReg(); 208 Register AvailDef = AvailCopy->getOperand(0).getReg(); 209 for (const MachineInstr &MI : 210 make_range(AvailCopy->getReverseIterator(), I.getReverseIterator())) 211 for (const MachineOperand &MO : MI.operands()) 212 if (MO.isRegMask()) 213 // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef? 214 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef)) 215 return nullptr; 216 217 return AvailCopy; 218 } 219 220 MachineInstr *findAvailCopy(MachineInstr &DestCopy, unsigned Reg, 221 const TargetRegisterInfo &TRI) { 222 // We check the first RegUnit here, since we'll only be interested in the 223 // copy if it copies the entire register anyway. 224 MCRegUnitIterator RUI(Reg, &TRI); 225 MachineInstr *AvailCopy = 226 findCopyForUnit(*RUI, TRI, /*MustBeAvailable=*/true); 227 if (!AvailCopy || 228 !TRI.isSubRegisterEq(AvailCopy->getOperand(0).getReg(), Reg)) 229 return nullptr; 230 231 // Check that the available copy isn't clobbered by any regmasks between 232 // itself and the destination. 233 Register AvailSrc = AvailCopy->getOperand(1).getReg(); 234 Register AvailDef = AvailCopy->getOperand(0).getReg(); 235 for (const MachineInstr &MI : 236 make_range(AvailCopy->getIterator(), DestCopy.getIterator())) 237 for (const MachineOperand &MO : MI.operands()) 238 if (MO.isRegMask()) 239 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef)) 240 return nullptr; 241 242 return AvailCopy; 243 } 244 245 void clear() { 246 Copies.clear(); 247 } 248 }; 249 250 class MachineCopyPropagation : public MachineFunctionPass { 251 const TargetRegisterInfo *TRI; 252 const TargetInstrInfo *TII; 253 const MachineRegisterInfo *MRI; 254 255 public: 256 static char ID; // Pass identification, replacement for typeid 257 258 MachineCopyPropagation() : MachineFunctionPass(ID) { 259 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 260 } 261 262 void getAnalysisUsage(AnalysisUsage &AU) const override { 263 AU.setPreservesCFG(); 264 MachineFunctionPass::getAnalysisUsage(AU); 265 } 266 267 bool runOnMachineFunction(MachineFunction &MF) override; 268 269 MachineFunctionProperties getRequiredProperties() const override { 270 return MachineFunctionProperties().set( 271 MachineFunctionProperties::Property::NoVRegs); 272 } 273 274 private: 275 typedef enum { DebugUse = false, RegularUse = true } DebugType; 276 277 void ClobberRegister(unsigned Reg); 278 void ReadRegister(unsigned Reg, MachineInstr &Reader, 279 DebugType DT); 280 void ForwardCopyPropagateBlock(MachineBasicBlock &MBB); 281 void BackwardCopyPropagateBlock(MachineBasicBlock &MBB); 282 bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def); 283 void forwardUses(MachineInstr &MI); 284 void propagateDefs(MachineInstr &MI); 285 bool isForwardableRegClassCopy(const MachineInstr &Copy, 286 const MachineInstr &UseI, unsigned UseIdx); 287 bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy, 288 const MachineInstr &UseI, 289 unsigned UseIdx); 290 bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use); 291 292 /// Candidates for deletion. 293 SmallSetVector<MachineInstr *, 8> MaybeDeadCopies; 294 295 /// Multimap tracking debug users in current BB 296 DenseMap<MachineInstr*, SmallVector<MachineInstr*, 2>> CopyDbgUsers; 297 298 CopyTracker Tracker; 299 300 bool Changed; 301 }; 302 303 } // end anonymous namespace 304 305 char MachineCopyPropagation::ID = 0; 306 307 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 308 309 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE, 310 "Machine Copy Propagation Pass", false, false) 311 312 void MachineCopyPropagation::ReadRegister(unsigned Reg, MachineInstr &Reader, 313 DebugType DT) { 314 // If 'Reg' is defined by a copy, the copy is no longer a candidate 315 // for elimination. If a copy is "read" by a debug user, record the user 316 // for propagation. 317 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) { 318 if (MachineInstr *Copy = Tracker.findCopyForUnit(*RUI, *TRI)) { 319 if (DT == RegularUse) { 320 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump()); 321 MaybeDeadCopies.remove(Copy); 322 } else { 323 CopyDbgUsers[Copy].push_back(&Reader); 324 } 325 } 326 } 327 } 328 329 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def. 330 /// This fact may have been obscured by sub register usage or may not be true at 331 /// all even though Src and Def are subregisters of the registers used in 332 /// PreviousCopy. e.g. 333 /// isNopCopy("ecx = COPY eax", AX, CX) == true 334 /// isNopCopy("ecx = COPY eax", AH, CL) == false 335 static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src, 336 unsigned Def, const TargetRegisterInfo *TRI) { 337 Register PreviousSrc = PreviousCopy.getOperand(1).getReg(); 338 Register PreviousDef = PreviousCopy.getOperand(0).getReg(); 339 if (Src == PreviousSrc && Def == PreviousDef) 340 return true; 341 if (!TRI->isSubRegister(PreviousSrc, Src)) 342 return false; 343 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src); 344 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def); 345 } 346 347 /// Remove instruction \p Copy if there exists a previous copy that copies the 348 /// register \p Src to the register \p Def; This may happen indirectly by 349 /// copying the super registers. 350 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src, 351 unsigned Def) { 352 // Avoid eliminating a copy from/to a reserved registers as we cannot predict 353 // the value (Example: The sparc zero register is writable but stays zero). 354 if (MRI->isReserved(Src) || MRI->isReserved(Def)) 355 return false; 356 357 // Search for an existing copy. 358 MachineInstr *PrevCopy = Tracker.findAvailCopy(Copy, Def, *TRI); 359 if (!PrevCopy) 360 return false; 361 362 // Check that the existing copy uses the correct sub registers. 363 if (PrevCopy->getOperand(0).isDead()) 364 return false; 365 if (!isNopCopy(*PrevCopy, Src, Def, TRI)) 366 return false; 367 368 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump()); 369 370 // Copy was redundantly redefining either Src or Def. Remove earlier kill 371 // flags between Copy and PrevCopy because the value will be reused now. 372 assert(Copy.isCopy()); 373 Register CopyDef = Copy.getOperand(0).getReg(); 374 assert(CopyDef == Src || CopyDef == Def); 375 for (MachineInstr &MI : 376 make_range(PrevCopy->getIterator(), Copy.getIterator())) 377 MI.clearRegisterKills(CopyDef, TRI); 378 379 Copy.eraseFromParent(); 380 Changed = true; 381 ++NumDeletes; 382 return true; 383 } 384 385 bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy( 386 const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) { 387 Register Def = Copy.getOperand(0).getReg(); 388 389 if (const TargetRegisterClass *URC = 390 UseI.getRegClassConstraint(UseIdx, TII, TRI)) 391 return URC->contains(Def); 392 393 // We don't process further if UseI is a COPY, since forward copy propagation 394 // should handle that. 395 return false; 396 } 397 398 /// Decide whether we should forward the source of \param Copy to its use in 399 /// \param UseI based on the physical register class constraints of the opcode 400 /// and avoiding introducing more cross-class COPYs. 401 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy, 402 const MachineInstr &UseI, 403 unsigned UseIdx) { 404 405 Register CopySrcReg = Copy.getOperand(1).getReg(); 406 407 // If the new register meets the opcode register constraints, then allow 408 // forwarding. 409 if (const TargetRegisterClass *URC = 410 UseI.getRegClassConstraint(UseIdx, TII, TRI)) 411 return URC->contains(CopySrcReg); 412 413 if (!UseI.isCopy()) 414 return false; 415 416 /// COPYs don't have register class constraints, so if the user instruction 417 /// is a COPY, we just try to avoid introducing additional cross-class 418 /// COPYs. For example: 419 /// 420 /// RegClassA = COPY RegClassB // Copy parameter 421 /// ... 422 /// RegClassB = COPY RegClassA // UseI parameter 423 /// 424 /// which after forwarding becomes 425 /// 426 /// RegClassA = COPY RegClassB 427 /// ... 428 /// RegClassB = COPY RegClassB 429 /// 430 /// so we have reduced the number of cross-class COPYs and potentially 431 /// introduced a nop COPY that can be removed. 432 const TargetRegisterClass *UseDstRC = 433 TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg()); 434 435 const TargetRegisterClass *SuperRC = UseDstRC; 436 for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses(); 437 SuperRC; SuperRC = *SuperRCI++) 438 if (SuperRC->contains(CopySrcReg)) 439 return true; 440 441 return false; 442 } 443 444 /// Check that \p MI does not have implicit uses that overlap with it's \p Use 445 /// operand (the register being replaced), since these can sometimes be 446 /// implicitly tied to other operands. For example, on AMDGPU: 447 /// 448 /// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use> 449 /// 450 /// the %VGPR2 is implicitly tied to the larger reg operand, but we have no 451 /// way of knowing we need to update the latter when updating the former. 452 bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI, 453 const MachineOperand &Use) { 454 for (const MachineOperand &MIUse : MI.uses()) 455 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() && 456 MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg())) 457 return true; 458 459 return false; 460 } 461 462 /// Look for available copies whose destination register is used by \p MI and 463 /// replace the use in \p MI with the copy's source register. 464 void MachineCopyPropagation::forwardUses(MachineInstr &MI) { 465 if (!Tracker.hasAnyCopies()) 466 return; 467 468 // Look for non-tied explicit vreg uses that have an active COPY 469 // instruction that defines the physical register allocated to them. 470 // Replace the vreg with the source of the active COPY. 471 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd; 472 ++OpIdx) { 473 MachineOperand &MOUse = MI.getOperand(OpIdx); 474 // Don't forward into undef use operands since doing so can cause problems 475 // with the machine verifier, since it doesn't treat undef reads as reads, 476 // so we can end up with a live range that ends on an undef read, leading to 477 // an error that the live range doesn't end on a read of the live range 478 // register. 479 if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() || 480 MOUse.isImplicit()) 481 continue; 482 483 if (!MOUse.getReg()) 484 continue; 485 486 // Check that the register is marked 'renamable' so we know it is safe to 487 // rename it without violating any constraints that aren't expressed in the 488 // IR (e.g. ABI or opcode requirements). 489 if (!MOUse.isRenamable()) 490 continue; 491 492 MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg(), *TRI); 493 if (!Copy) 494 continue; 495 496 Register CopyDstReg = Copy->getOperand(0).getReg(); 497 const MachineOperand &CopySrc = Copy->getOperand(1); 498 Register CopySrcReg = CopySrc.getReg(); 499 500 // FIXME: Don't handle partial uses of wider COPYs yet. 501 if (MOUse.getReg() != CopyDstReg) { 502 LLVM_DEBUG( 503 dbgs() << "MCP: FIXME! Not forwarding COPY to sub-register use:\n " 504 << MI); 505 continue; 506 } 507 508 // Don't forward COPYs of reserved regs unless they are constant. 509 if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg)) 510 continue; 511 512 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx)) 513 continue; 514 515 if (hasImplicitOverlap(MI, MOUse)) 516 continue; 517 518 // Check that the instruction is not a copy that partially overwrites the 519 // original copy source that we are about to use. The tracker mechanism 520 // cannot cope with that. 521 if (MI.isCopy() && MI.modifiesRegister(CopySrcReg, TRI) && 522 !MI.definesRegister(CopySrcReg)) { 523 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI); 524 continue; 525 } 526 527 if (!DebugCounter::shouldExecute(FwdCounter)) { 528 LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n " 529 << MI); 530 continue; 531 } 532 533 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI) 534 << "\n with " << printReg(CopySrcReg, TRI) 535 << "\n in " << MI << " from " << *Copy); 536 537 MOUse.setReg(CopySrcReg); 538 if (!CopySrc.isRenamable()) 539 MOUse.setIsRenamable(false); 540 541 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n"); 542 543 // Clear kill markers that may have been invalidated. 544 for (MachineInstr &KMI : 545 make_range(Copy->getIterator(), std::next(MI.getIterator()))) 546 KMI.clearRegisterKills(CopySrcReg, TRI); 547 548 ++NumCopyForwards; 549 Changed = true; 550 } 551 } 552 553 void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) { 554 LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName() 555 << "\n"); 556 557 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 558 MachineInstr *MI = &*I; 559 ++I; 560 561 // Analyze copies (which don't overlap themselves). 562 if (MI->isCopy() && !TRI->regsOverlap(MI->getOperand(0).getReg(), 563 MI->getOperand(1).getReg())) { 564 Register Def = MI->getOperand(0).getReg(); 565 Register Src = MI->getOperand(1).getReg(); 566 567 assert(!Register::isVirtualRegister(Def) && 568 !Register::isVirtualRegister(Src) && 569 "MachineCopyPropagation should be run after register allocation!"); 570 571 // The two copies cancel out and the source of the first copy 572 // hasn't been overridden, eliminate the second one. e.g. 573 // %ecx = COPY %eax 574 // ... nothing clobbered eax. 575 // %eax = COPY %ecx 576 // => 577 // %ecx = COPY %eax 578 // 579 // or 580 // 581 // %ecx = COPY %eax 582 // ... nothing clobbered eax. 583 // %ecx = COPY %eax 584 // => 585 // %ecx = COPY %eax 586 if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def)) 587 continue; 588 589 forwardUses(*MI); 590 591 // Src may have been changed by forwardUses() 592 Src = MI->getOperand(1).getReg(); 593 594 // If Src is defined by a previous copy, the previous copy cannot be 595 // eliminated. 596 ReadRegister(Src, *MI, RegularUse); 597 for (const MachineOperand &MO : MI->implicit_operands()) { 598 if (!MO.isReg() || !MO.readsReg()) 599 continue; 600 Register Reg = MO.getReg(); 601 if (!Reg) 602 continue; 603 ReadRegister(Reg, *MI, RegularUse); 604 } 605 606 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); 607 608 // Copy is now a candidate for deletion. 609 if (!MRI->isReserved(Def)) 610 MaybeDeadCopies.insert(MI); 611 612 // If 'Def' is previously source of another copy, then this earlier copy's 613 // source is no longer available. e.g. 614 // %xmm9 = copy %xmm2 615 // ... 616 // %xmm2 = copy %xmm0 617 // ... 618 // %xmm2 = copy %xmm9 619 Tracker.clobberRegister(Def, *TRI); 620 for (const MachineOperand &MO : MI->implicit_operands()) { 621 if (!MO.isReg() || !MO.isDef()) 622 continue; 623 Register Reg = MO.getReg(); 624 if (!Reg) 625 continue; 626 Tracker.clobberRegister(Reg, *TRI); 627 } 628 629 Tracker.trackCopy(MI, *TRI); 630 631 continue; 632 } 633 634 // Clobber any earlyclobber regs first. 635 for (const MachineOperand &MO : MI->operands()) 636 if (MO.isReg() && MO.isEarlyClobber()) { 637 Register Reg = MO.getReg(); 638 // If we have a tied earlyclobber, that means it is also read by this 639 // instruction, so we need to make sure we don't remove it as dead 640 // later. 641 if (MO.isTied()) 642 ReadRegister(Reg, *MI, RegularUse); 643 Tracker.clobberRegister(Reg, *TRI); 644 } 645 646 forwardUses(*MI); 647 648 // Not a copy. 649 SmallVector<unsigned, 2> Defs; 650 const MachineOperand *RegMask = nullptr; 651 for (const MachineOperand &MO : MI->operands()) { 652 if (MO.isRegMask()) 653 RegMask = &MO; 654 if (!MO.isReg()) 655 continue; 656 Register Reg = MO.getReg(); 657 if (!Reg) 658 continue; 659 660 assert(!Register::isVirtualRegister(Reg) && 661 "MachineCopyPropagation should be run after register allocation!"); 662 663 if (MO.isDef() && !MO.isEarlyClobber()) { 664 Defs.push_back(Reg); 665 continue; 666 } else if (MO.readsReg()) 667 ReadRegister(Reg, *MI, MO.isDebug() ? DebugUse : RegularUse); 668 } 669 670 // The instruction has a register mask operand which means that it clobbers 671 // a large set of registers. Treat clobbered registers the same way as 672 // defined registers. 673 if (RegMask) { 674 // Erase any MaybeDeadCopies whose destination register is clobbered. 675 for (SmallSetVector<MachineInstr *, 8>::iterator DI = 676 MaybeDeadCopies.begin(); 677 DI != MaybeDeadCopies.end();) { 678 MachineInstr *MaybeDead = *DI; 679 Register Reg = MaybeDead->getOperand(0).getReg(); 680 assert(!MRI->isReserved(Reg)); 681 682 if (!RegMask->clobbersPhysReg(Reg)) { 683 ++DI; 684 continue; 685 } 686 687 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 688 MaybeDead->dump()); 689 690 // Make sure we invalidate any entries in the copy maps before erasing 691 // the instruction. 692 Tracker.clobberRegister(Reg, *TRI); 693 694 // erase() will return the next valid iterator pointing to the next 695 // element after the erased one. 696 DI = MaybeDeadCopies.erase(DI); 697 MaybeDead->eraseFromParent(); 698 Changed = true; 699 ++NumDeletes; 700 } 701 } 702 703 // Any previous copy definition or reading the Defs is no longer available. 704 for (unsigned Reg : Defs) 705 Tracker.clobberRegister(Reg, *TRI); 706 } 707 708 // If MBB doesn't have successors, delete the copies whose defs are not used. 709 // If MBB does have successors, then conservative assume the defs are live-out 710 // since we don't want to trust live-in lists. 711 if (MBB.succ_empty()) { 712 for (MachineInstr *MaybeDead : MaybeDeadCopies) { 713 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: "; 714 MaybeDead->dump()); 715 assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg())); 716 717 // Update matching debug values, if any. 718 assert(MaybeDead->isCopy()); 719 unsigned SrcReg = MaybeDead->getOperand(1).getReg(); 720 MRI->updateDbgUsersToReg(SrcReg, CopyDbgUsers[MaybeDead]); 721 722 MaybeDead->eraseFromParent(); 723 Changed = true; 724 ++NumDeletes; 725 } 726 } 727 728 MaybeDeadCopies.clear(); 729 CopyDbgUsers.clear(); 730 Tracker.clear(); 731 } 732 733 static bool isBackwardPropagatableCopy(MachineInstr &MI, 734 const MachineRegisterInfo &MRI) { 735 assert(MI.isCopy() && "MI is expected to be a COPY"); 736 Register Def = MI.getOperand(0).getReg(); 737 Register Src = MI.getOperand(1).getReg(); 738 739 if (!Def || !Src) 740 return false; 741 742 if (MRI.isReserved(Def) || MRI.isReserved(Src)) 743 return false; 744 745 return MI.getOperand(1).isRenamable() && MI.getOperand(1).isKill(); 746 } 747 748 void MachineCopyPropagation::propagateDefs(MachineInstr &MI) { 749 if (!Tracker.hasAnyCopies()) 750 return; 751 752 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd; 753 ++OpIdx) { 754 MachineOperand &MODef = MI.getOperand(OpIdx); 755 756 if (!MODef.isReg() || MODef.isUse()) 757 continue; 758 759 // Ignore non-trivial cases. 760 if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit()) 761 continue; 762 763 if (!MODef.getReg()) 764 continue; 765 766 // We only handle if the register comes from a vreg. 767 if (!MODef.isRenamable()) 768 continue; 769 770 MachineInstr *Copy = 771 Tracker.findAvailBackwardCopy(MI, MODef.getReg(), *TRI); 772 if (!Copy) 773 continue; 774 775 Register Def = Copy->getOperand(0).getReg(); 776 Register Src = Copy->getOperand(1).getReg(); 777 778 if (MODef.getReg() != Src) 779 continue; 780 781 if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx)) 782 continue; 783 784 if (hasImplicitOverlap(MI, MODef)) 785 continue; 786 787 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI) 788 << "\n with " << printReg(Def, TRI) << "\n in " 789 << MI << " from " << *Copy); 790 791 MODef.setReg(Def); 792 MODef.setIsRenamable(Copy->getOperand(0).isRenamable()); 793 794 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n"); 795 MaybeDeadCopies.insert(Copy); 796 Changed = true; 797 ++NumCopyBackwardPropagated; 798 } 799 } 800 801 void MachineCopyPropagation::BackwardCopyPropagateBlock( 802 MachineBasicBlock &MBB) { 803 LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName() 804 << "\n"); 805 806 for (MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend(); 807 I != E;) { 808 MachineInstr *MI = &*I; 809 ++I; 810 811 // Ignore non-trivial COPYs. 812 if (MI->isCopy() && MI->getNumOperands() == 2 && 813 !TRI->regsOverlap(MI->getOperand(0).getReg(), 814 MI->getOperand(1).getReg())) { 815 816 Register Def = MI->getOperand(0).getReg(); 817 Register Src = MI->getOperand(1).getReg(); 818 819 // Unlike forward cp, we don't invoke propagateDefs here, 820 // just let forward cp do COPY-to-COPY propagation. 821 if (isBackwardPropagatableCopy(*MI, *MRI)) { 822 Tracker.invalidateRegister(Src, *TRI); 823 Tracker.invalidateRegister(Def, *TRI); 824 Tracker.trackCopy(MI, *TRI); 825 continue; 826 } 827 } 828 829 // Invalidate any earlyclobber regs first. 830 for (const MachineOperand &MO : MI->operands()) 831 if (MO.isReg() && MO.isEarlyClobber()) { 832 Register Reg = MO.getReg(); 833 if (!Reg) 834 continue; 835 Tracker.invalidateRegister(Reg, *TRI); 836 } 837 838 propagateDefs(*MI); 839 for (const MachineOperand &MO : MI->operands()) { 840 if (!MO.isReg()) 841 continue; 842 843 if (!MO.getReg()) 844 continue; 845 846 if (MO.isDef()) 847 Tracker.invalidateRegister(MO.getReg(), *TRI); 848 849 if (MO.readsReg()) 850 Tracker.invalidateRegister(MO.getReg(), *TRI); 851 } 852 } 853 854 for (auto *Copy : MaybeDeadCopies) { 855 Copy->eraseFromParent(); 856 ++NumDeletes; 857 } 858 859 MaybeDeadCopies.clear(); 860 CopyDbgUsers.clear(); 861 Tracker.clear(); 862 } 863 864 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 865 if (skipFunction(MF.getFunction())) 866 return false; 867 868 Changed = false; 869 870 TRI = MF.getSubtarget().getRegisterInfo(); 871 TII = MF.getSubtarget().getInstrInfo(); 872 MRI = &MF.getRegInfo(); 873 874 for (MachineBasicBlock &MBB : MF) { 875 BackwardCopyPropagateBlock(MBB); 876 ForwardCopyPropagateBlock(MBB); 877 } 878 879 return Changed; 880 } 881