1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This is an extremely simple MachineInstr-level copy propagation pass. 10 // 11 // This pass forwards the source of COPYs to the users of their destinations 12 // when doing so is legal. For example: 13 // 14 // %reg1 = COPY %reg0 15 // ... 16 // ... = OP %reg1 17 // 18 // If 19 // - %reg0 has not been clobbered by the time of the use of %reg1 20 // - the register class constraints are satisfied 21 // - the COPY def is the only value that reaches OP 22 // then this pass replaces the above with: 23 // 24 // %reg1 = COPY %reg0 25 // ... 26 // ... = OP %reg0 27 // 28 // This pass also removes some redundant COPYs. For example: 29 // 30 // %R1 = COPY %R0 31 // ... // No clobber of %R1 32 // %R0 = COPY %R1 <<< Removed 33 // 34 // or 35 // 36 // %R1 = COPY %R0 37 // ... // No clobber of %R0 38 // %R1 = COPY %R0 <<< Removed 39 // 40 // or 41 // 42 // $R0 = OP ... 43 // ... // No read/clobber of $R0 and $R1 44 // $R1 = COPY $R0 // $R0 is killed 45 // Replace $R0 with $R1 and remove the COPY 46 // $R1 = OP ... 47 // ... 48 // 49 //===----------------------------------------------------------------------===// 50 51 #include "llvm/ADT/DenseMap.h" 52 #include "llvm/ADT/STLExtras.h" 53 #include "llvm/ADT/SetVector.h" 54 #include "llvm/ADT/SmallSet.h" 55 #include "llvm/ADT/SmallVector.h" 56 #include "llvm/ADT/Statistic.h" 57 #include "llvm/ADT/iterator_range.h" 58 #include "llvm/CodeGen/MachineBasicBlock.h" 59 #include "llvm/CodeGen/MachineFunction.h" 60 #include "llvm/CodeGen/MachineFunctionPass.h" 61 #include "llvm/CodeGen/MachineInstr.h" 62 #include "llvm/CodeGen/MachineOperand.h" 63 #include "llvm/CodeGen/MachineRegisterInfo.h" 64 #include "llvm/CodeGen/TargetInstrInfo.h" 65 #include "llvm/CodeGen/TargetRegisterInfo.h" 66 #include "llvm/CodeGen/TargetSubtargetInfo.h" 67 #include "llvm/InitializePasses.h" 68 #include "llvm/MC/MCRegisterInfo.h" 69 #include "llvm/Pass.h" 70 #include "llvm/Support/Debug.h" 71 #include "llvm/Support/DebugCounter.h" 72 #include "llvm/Support/raw_ostream.h" 73 #include <cassert> 74 #include <iterator> 75 76 using namespace llvm; 77 78 #define DEBUG_TYPE "machine-cp" 79 80 STATISTIC(NumDeletes, "Number of dead copies deleted"); 81 STATISTIC(NumCopyForwards, "Number of copy uses forwarded"); 82 STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated"); 83 STATISTIC(SpillageChainsLength, "Length of spillage chains"); 84 STATISTIC(NumSpillageChains, "Number of spillage chains"); 85 DEBUG_COUNTER(FwdCounter, "machine-cp-fwd", 86 "Controls which register COPYs are forwarded"); 87 88 static cl::opt<bool> MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false), 89 cl::Hidden); 90 static cl::opt<cl::boolOrDefault> 91 EnableSpillageCopyElimination("enable-spill-copy-elim", cl::Hidden); 92 93 namespace { 94 95 static std::optional<DestSourcePair> isCopyInstr(const MachineInstr &MI, 96 const TargetInstrInfo &TII, 97 bool UseCopyInstr) { 98 if (UseCopyInstr) 99 return TII.isCopyInstr(MI); 100 101 if (MI.isCopy()) 102 return std::optional<DestSourcePair>( 103 DestSourcePair{MI.getOperand(0), MI.getOperand(1)}); 104 105 return std::nullopt; 106 } 107 108 class CopyTracker { 109 struct CopyInfo { 110 MachineInstr *MI, *LastSeenUseInCopy; 111 SmallVector<MCRegister, 4> DefRegs; 112 bool Avail; 113 }; 114 115 DenseMap<MCRegister, CopyInfo> Copies; 116 117 public: 118 /// Mark all of the given registers and their subregisters as unavailable for 119 /// copying. 120 void markRegsUnavailable(ArrayRef<MCRegister> Regs, 121 const TargetRegisterInfo &TRI) { 122 for (MCRegister Reg : Regs) { 123 // Source of copy is no longer available for propagation. 124 for (MCRegUnit Unit : TRI.regunits(Reg)) { 125 auto CI = Copies.find(Unit); 126 if (CI != Copies.end()) 127 CI->second.Avail = false; 128 } 129 } 130 } 131 132 /// Remove register from copy maps. 133 void invalidateRegister(MCRegister Reg, const TargetRegisterInfo &TRI, 134 const TargetInstrInfo &TII, bool UseCopyInstr) { 135 // Since Reg might be a subreg of some registers, only invalidate Reg is not 136 // enough. We have to find the COPY defines Reg or registers defined by Reg 137 // and invalidate all of them. Similarly, we must invalidate all of the 138 // the subregisters used in the source of the COPY. 139 SmallSet<MCRegUnit, 8> RegUnitsToInvalidate; 140 auto InvalidateCopy = [&](MachineInstr *MI) { 141 std::optional<DestSourcePair> CopyOperands = 142 isCopyInstr(*MI, TII, UseCopyInstr); 143 assert(CopyOperands && "Expect copy"); 144 145 auto Dest = TRI.regunits(CopyOperands->Destination->getReg().asMCReg()); 146 auto Src = TRI.regunits(CopyOperands->Source->getReg().asMCReg()); 147 RegUnitsToInvalidate.insert(Dest.begin(), Dest.end()); 148 RegUnitsToInvalidate.insert(Src.begin(), Src.end()); 149 }; 150 151 for (MCRegUnit Unit : TRI.regunits(Reg)) { 152 auto I = Copies.find(Unit); 153 if (I != Copies.end()) { 154 if (MachineInstr *MI = I->second.MI) 155 InvalidateCopy(MI); 156 if (MachineInstr *MI = I->second.LastSeenUseInCopy) 157 InvalidateCopy(MI); 158 } 159 } 160 for (MCRegUnit Unit : RegUnitsToInvalidate) 161 Copies.erase(Unit); 162 } 163 164 /// Clobber a single register, removing it from the tracker's copy maps. 165 void clobberRegister(MCRegister Reg, const TargetRegisterInfo &TRI, 166 const TargetInstrInfo &TII, bool UseCopyInstr) { 167 for (MCRegUnit Unit : TRI.regunits(Reg)) { 168 auto I = Copies.find(Unit); 169 if (I != Copies.end()) { 170 // When we clobber the source of a copy, we need to clobber everything 171 // it defined. 172 markRegsUnavailable(I->second.DefRegs, TRI); 173 // When we clobber the destination of a copy, we need to clobber the 174 // whole register it defined. 175 if (MachineInstr *MI = I->second.MI) { 176 std::optional<DestSourcePair> CopyOperands = 177 isCopyInstr(*MI, TII, UseCopyInstr); 178 179 MCRegister Def = CopyOperands->Destination->getReg().asMCReg(); 180 MCRegister Src = CopyOperands->Source->getReg().asMCReg(); 181 182 markRegsUnavailable(Def, TRI); 183 184 // Since we clobber the destination of a copy, the semantic of Src's 185 // "DefRegs" to contain Def is no longer effectual. We will also need 186 // to remove the record from the copy maps that indicates Src defined 187 // Def. Failing to do so might cause the target to miss some 188 // opportunities to further eliminate redundant copy instructions. 189 // Consider the following sequence during the 190 // ForwardCopyPropagateBlock procedure: 191 // L1: r0 = COPY r9 <- TrackMI 192 // L2: r0 = COPY r8 <- TrackMI (Remove r9 defined r0 from tracker) 193 // L3: use r0 <- Remove L2 from MaybeDeadCopies 194 // L4: early-clobber r9 <- Clobber r9 (L2 is still valid in tracker) 195 // L5: r0 = COPY r8 <- Remove NopCopy 196 for (MCRegUnit SrcUnit : TRI.regunits(Src)) { 197 auto SrcCopy = Copies.find(SrcUnit); 198 if (SrcCopy != Copies.end() && SrcCopy->second.LastSeenUseInCopy) { 199 // If SrcCopy defines multiple values, we only need 200 // to erase the record for Def in DefRegs. 201 for (auto itr = SrcCopy->second.DefRegs.begin(); 202 itr != SrcCopy->second.DefRegs.end(); itr++) { 203 if (*itr == Def) { 204 SrcCopy->second.DefRegs.erase(itr); 205 // If DefReg becomes empty after removal, we can remove the 206 // SrcCopy from the tracker's copy maps. We only remove those 207 // entries solely record the Def is defined by Src. If an 208 // entry also contains the definition record of other Def' 209 // registers, it cannot be cleared. 210 if (SrcCopy->second.DefRegs.empty() && !SrcCopy->second.MI) { 211 Copies.erase(SrcCopy); 212 } 213 break; 214 } 215 } 216 } 217 } 218 } 219 // Now we can erase the copy. 220 Copies.erase(I); 221 } 222 } 223 } 224 225 /// Add this copy's registers into the tracker's copy maps. 226 void trackCopy(MachineInstr *MI, const TargetRegisterInfo &TRI, 227 const TargetInstrInfo &TII, bool UseCopyInstr) { 228 std::optional<DestSourcePair> CopyOperands = 229 isCopyInstr(*MI, TII, UseCopyInstr); 230 assert(CopyOperands && "Tracking non-copy?"); 231 232 MCRegister Src = CopyOperands->Source->getReg().asMCReg(); 233 MCRegister Def = CopyOperands->Destination->getReg().asMCReg(); 234 235 // Remember Def is defined by the copy. 236 for (MCRegUnit Unit : TRI.regunits(Def)) 237 Copies[Unit] = {MI, nullptr, {}, true}; 238 239 // Remember source that's copied to Def. Once it's clobbered, then 240 // it's no longer available for copy propagation. 241 for (MCRegUnit Unit : TRI.regunits(Src)) { 242 auto I = Copies.insert({Unit, {nullptr, nullptr, {}, false}}); 243 auto &Copy = I.first->second; 244 if (!is_contained(Copy.DefRegs, Def)) 245 Copy.DefRegs.push_back(Def); 246 Copy.LastSeenUseInCopy = MI; 247 } 248 } 249 250 bool hasAnyCopies() { 251 return !Copies.empty(); 252 } 253 254 MachineInstr *findCopyForUnit(MCRegister RegUnit, 255 const TargetRegisterInfo &TRI, 256 bool MustBeAvailable = false) { 257 auto CI = Copies.find(RegUnit); 258 if (CI == Copies.end()) 259 return nullptr; 260 if (MustBeAvailable && !CI->second.Avail) 261 return nullptr; 262 return CI->second.MI; 263 } 264 265 MachineInstr *findCopyDefViaUnit(MCRegister RegUnit, 266 const TargetRegisterInfo &TRI) { 267 auto CI = Copies.find(RegUnit); 268 if (CI == Copies.end()) 269 return nullptr; 270 if (CI->second.DefRegs.size() != 1) 271 return nullptr; 272 MCRegUnit RU = *TRI.regunits(CI->second.DefRegs[0]).begin(); 273 return findCopyForUnit(RU, TRI, true); 274 } 275 276 MachineInstr *findAvailBackwardCopy(MachineInstr &I, MCRegister Reg, 277 const TargetRegisterInfo &TRI, 278 const TargetInstrInfo &TII, 279 bool UseCopyInstr) { 280 MCRegUnit RU = *TRI.regunits(Reg).begin(); 281 MachineInstr *AvailCopy = findCopyDefViaUnit(RU, TRI); 282 283 if (!AvailCopy) 284 return nullptr; 285 286 std::optional<DestSourcePair> CopyOperands = 287 isCopyInstr(*AvailCopy, TII, UseCopyInstr); 288 Register AvailSrc = CopyOperands->Source->getReg(); 289 Register AvailDef = CopyOperands->Destination->getReg(); 290 if (!TRI.isSubRegisterEq(AvailSrc, Reg)) 291 return nullptr; 292 293 for (const MachineInstr &MI : 294 make_range(AvailCopy->getReverseIterator(), I.getReverseIterator())) 295 for (const MachineOperand &MO : MI.operands()) 296 if (MO.isRegMask()) 297 // FIXME: Shall we simultaneously invalidate AvailSrc or AvailDef? 298 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef)) 299 return nullptr; 300 301 return AvailCopy; 302 } 303 304 MachineInstr *findAvailCopy(MachineInstr &DestCopy, MCRegister Reg, 305 const TargetRegisterInfo &TRI, 306 const TargetInstrInfo &TII, bool UseCopyInstr) { 307 // We check the first RegUnit here, since we'll only be interested in the 308 // copy if it copies the entire register anyway. 309 MCRegUnit RU = *TRI.regunits(Reg).begin(); 310 MachineInstr *AvailCopy = 311 findCopyForUnit(RU, TRI, /*MustBeAvailable=*/true); 312 313 if (!AvailCopy) 314 return nullptr; 315 316 std::optional<DestSourcePair> CopyOperands = 317 isCopyInstr(*AvailCopy, TII, UseCopyInstr); 318 Register AvailSrc = CopyOperands->Source->getReg(); 319 Register AvailDef = CopyOperands->Destination->getReg(); 320 if (!TRI.isSubRegisterEq(AvailDef, Reg)) 321 return nullptr; 322 323 // Check that the available copy isn't clobbered by any regmasks between 324 // itself and the destination. 325 for (const MachineInstr &MI : 326 make_range(AvailCopy->getIterator(), DestCopy.getIterator())) 327 for (const MachineOperand &MO : MI.operands()) 328 if (MO.isRegMask()) 329 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef)) 330 return nullptr; 331 332 return AvailCopy; 333 } 334 335 // Find last COPY that defines Reg before Current MachineInstr. 336 MachineInstr *findLastSeenDefInCopy(const MachineInstr &Current, 337 MCRegister Reg, 338 const TargetRegisterInfo &TRI, 339 const TargetInstrInfo &TII, 340 bool UseCopyInstr) { 341 MCRegUnit RU = *TRI.regunits(Reg).begin(); 342 auto CI = Copies.find(RU); 343 if (CI == Copies.end() || !CI->second.Avail) 344 return nullptr; 345 346 MachineInstr *DefCopy = CI->second.MI; 347 std::optional<DestSourcePair> CopyOperands = 348 isCopyInstr(*DefCopy, TII, UseCopyInstr); 349 Register Def = CopyOperands->Destination->getReg(); 350 if (!TRI.isSubRegisterEq(Def, Reg)) 351 return nullptr; 352 353 for (const MachineInstr &MI : 354 make_range(static_cast<const MachineInstr *>(DefCopy)->getIterator(), 355 Current.getIterator())) 356 for (const MachineOperand &MO : MI.operands()) 357 if (MO.isRegMask()) 358 if (MO.clobbersPhysReg(Def)) { 359 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " 360 << printReg(Def, &TRI) << "\n"); 361 return nullptr; 362 } 363 364 return DefCopy; 365 } 366 367 // Find last COPY that uses Reg. 368 MachineInstr *findLastSeenUseInCopy(MCRegister Reg, 369 const TargetRegisterInfo &TRI) { 370 MCRegUnit RU = *TRI.regunits(Reg).begin(); 371 auto CI = Copies.find(RU); 372 if (CI == Copies.end()) 373 return nullptr; 374 return CI->second.LastSeenUseInCopy; 375 } 376 377 void clear() { 378 Copies.clear(); 379 } 380 }; 381 382 class MachineCopyPropagation : public MachineFunctionPass { 383 const TargetRegisterInfo *TRI = nullptr; 384 const TargetInstrInfo *TII = nullptr; 385 const MachineRegisterInfo *MRI = nullptr; 386 387 // Return true if this is a copy instruction and false otherwise. 388 bool UseCopyInstr; 389 390 public: 391 static char ID; // Pass identification, replacement for typeid 392 393 MachineCopyPropagation(bool CopyInstr = false) 394 : MachineFunctionPass(ID), UseCopyInstr(CopyInstr || MCPUseCopyInstr) { 395 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 396 } 397 398 void getAnalysisUsage(AnalysisUsage &AU) const override { 399 AU.setPreservesCFG(); 400 MachineFunctionPass::getAnalysisUsage(AU); 401 } 402 403 bool runOnMachineFunction(MachineFunction &MF) override; 404 405 MachineFunctionProperties getRequiredProperties() const override { 406 return MachineFunctionProperties().set( 407 MachineFunctionProperties::Property::NoVRegs); 408 } 409 410 private: 411 typedef enum { DebugUse = false, RegularUse = true } DebugType; 412 413 void ReadRegister(MCRegister Reg, MachineInstr &Reader, DebugType DT); 414 void ForwardCopyPropagateBlock(MachineBasicBlock &MBB); 415 void BackwardCopyPropagateBlock(MachineBasicBlock &MBB); 416 void EliminateSpillageCopies(MachineBasicBlock &MBB); 417 bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def); 418 void forwardUses(MachineInstr &MI); 419 void propagateDefs(MachineInstr &MI); 420 bool isForwardableRegClassCopy(const MachineInstr &Copy, 421 const MachineInstr &UseI, unsigned UseIdx); 422 bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy, 423 const MachineInstr &UseI, 424 unsigned UseIdx); 425 bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use); 426 bool hasOverlappingMultipleDef(const MachineInstr &MI, 427 const MachineOperand &MODef, Register Def); 428 429 /// Candidates for deletion. 430 SmallSetVector<MachineInstr *, 8> MaybeDeadCopies; 431 432 /// Multimap tracking debug users in current BB 433 DenseMap<MachineInstr *, SmallSet<MachineInstr *, 2>> CopyDbgUsers; 434 435 CopyTracker Tracker; 436 437 bool Changed = false; 438 }; 439 440 } // end anonymous namespace 441 442 char MachineCopyPropagation::ID = 0; 443 444 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 445 446 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE, 447 "Machine Copy Propagation Pass", false, false) 448 449 void MachineCopyPropagation::ReadRegister(MCRegister Reg, MachineInstr &Reader, 450 DebugType DT) { 451 // If 'Reg' is defined by a copy, the copy is no longer a candidate 452 // for elimination. If a copy is "read" by a debug user, record the user 453 // for propagation. 454 for (MCRegUnit Unit : TRI->regunits(Reg)) { 455 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI)) { 456 if (DT == RegularUse) { 457 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump()); 458 MaybeDeadCopies.remove(Copy); 459 } else { 460 CopyDbgUsers[Copy].insert(&Reader); 461 } 462 } 463 } 464 } 465 466 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def. 467 /// This fact may have been obscured by sub register usage or may not be true at 468 /// all even though Src and Def are subregisters of the registers used in 469 /// PreviousCopy. e.g. 470 /// isNopCopy("ecx = COPY eax", AX, CX) == true 471 /// isNopCopy("ecx = COPY eax", AH, CL) == false 472 static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src, 473 MCRegister Def, const TargetRegisterInfo *TRI, 474 const TargetInstrInfo *TII, bool UseCopyInstr) { 475 476 std::optional<DestSourcePair> CopyOperands = 477 isCopyInstr(PreviousCopy, *TII, UseCopyInstr); 478 MCRegister PreviousSrc = CopyOperands->Source->getReg().asMCReg(); 479 MCRegister PreviousDef = CopyOperands->Destination->getReg().asMCReg(); 480 if (Src == PreviousSrc && Def == PreviousDef) 481 return true; 482 if (!TRI->isSubRegister(PreviousSrc, Src)) 483 return false; 484 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src); 485 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def); 486 } 487 488 /// Remove instruction \p Copy if there exists a previous copy that copies the 489 /// register \p Src to the register \p Def; This may happen indirectly by 490 /// copying the super registers. 491 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, 492 MCRegister Src, MCRegister Def) { 493 // Avoid eliminating a copy from/to a reserved registers as we cannot predict 494 // the value (Example: The sparc zero register is writable but stays zero). 495 if (MRI->isReserved(Src) || MRI->isReserved(Def)) 496 return false; 497 498 // Search for an existing copy. 499 MachineInstr *PrevCopy = 500 Tracker.findAvailCopy(Copy, Def, *TRI, *TII, UseCopyInstr); 501 if (!PrevCopy) 502 return false; 503 504 auto PrevCopyOperands = isCopyInstr(*PrevCopy, *TII, UseCopyInstr); 505 // Check that the existing copy uses the correct sub registers. 506 if (PrevCopyOperands->Destination->isDead()) 507 return false; 508 if (!isNopCopy(*PrevCopy, Src, Def, TRI, TII, UseCopyInstr)) 509 return false; 510 511 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump()); 512 513 // Copy was redundantly redefining either Src or Def. Remove earlier kill 514 // flags between Copy and PrevCopy because the value will be reused now. 515 std::optional<DestSourcePair> CopyOperands = 516 isCopyInstr(Copy, *TII, UseCopyInstr); 517 assert(CopyOperands); 518 519 Register CopyDef = CopyOperands->Destination->getReg(); 520 assert(CopyDef == Src || CopyDef == Def); 521 for (MachineInstr &MI : 522 make_range(PrevCopy->getIterator(), Copy.getIterator())) 523 MI.clearRegisterKills(CopyDef, TRI); 524 525 // Clear undef flag from remaining copy if needed. 526 if (!CopyOperands->Source->isUndef()) { 527 PrevCopy->getOperand(PrevCopyOperands->Source->getOperandNo()) 528 .setIsUndef(false); 529 } 530 531 Copy.eraseFromParent(); 532 Changed = true; 533 ++NumDeletes; 534 return true; 535 } 536 537 bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy( 538 const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) { 539 std::optional<DestSourcePair> CopyOperands = 540 isCopyInstr(Copy, *TII, UseCopyInstr); 541 Register Def = CopyOperands->Destination->getReg(); 542 543 if (const TargetRegisterClass *URC = 544 UseI.getRegClassConstraint(UseIdx, TII, TRI)) 545 return URC->contains(Def); 546 547 // We don't process further if UseI is a COPY, since forward copy propagation 548 // should handle that. 549 return false; 550 } 551 552 /// Decide whether we should forward the source of \param Copy to its use in 553 /// \param UseI based on the physical register class constraints of the opcode 554 /// and avoiding introducing more cross-class COPYs. 555 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy, 556 const MachineInstr &UseI, 557 unsigned UseIdx) { 558 std::optional<DestSourcePair> CopyOperands = 559 isCopyInstr(Copy, *TII, UseCopyInstr); 560 Register CopySrcReg = CopyOperands->Source->getReg(); 561 562 // If the new register meets the opcode register constraints, then allow 563 // forwarding. 564 if (const TargetRegisterClass *URC = 565 UseI.getRegClassConstraint(UseIdx, TII, TRI)) 566 return URC->contains(CopySrcReg); 567 568 auto UseICopyOperands = isCopyInstr(UseI, *TII, UseCopyInstr); 569 if (!UseICopyOperands) 570 return false; 571 572 /// COPYs don't have register class constraints, so if the user instruction 573 /// is a COPY, we just try to avoid introducing additional cross-class 574 /// COPYs. For example: 575 /// 576 /// RegClassA = COPY RegClassB // Copy parameter 577 /// ... 578 /// RegClassB = COPY RegClassA // UseI parameter 579 /// 580 /// which after forwarding becomes 581 /// 582 /// RegClassA = COPY RegClassB 583 /// ... 584 /// RegClassB = COPY RegClassB 585 /// 586 /// so we have reduced the number of cross-class COPYs and potentially 587 /// introduced a nop COPY that can be removed. 588 589 // Allow forwarding if src and dst belong to any common class, so long as they 590 // don't belong to any (possibly smaller) common class that requires copies to 591 // go via a different class. 592 Register UseDstReg = UseICopyOperands->Destination->getReg(); 593 bool Found = false; 594 bool IsCrossClass = false; 595 for (const TargetRegisterClass *RC : TRI->regclasses()) { 596 if (RC->contains(CopySrcReg) && RC->contains(UseDstReg)) { 597 Found = true; 598 if (TRI->getCrossCopyRegClass(RC) != RC) { 599 IsCrossClass = true; 600 break; 601 } 602 } 603 } 604 if (!Found) 605 return false; 606 if (!IsCrossClass) 607 return true; 608 // The forwarded copy would be cross-class. Only do this if the original copy 609 // was also cross-class. 610 Register CopyDstReg = CopyOperands->Destination->getReg(); 611 for (const TargetRegisterClass *RC : TRI->regclasses()) { 612 if (RC->contains(CopySrcReg) && RC->contains(CopyDstReg) && 613 TRI->getCrossCopyRegClass(RC) != RC) 614 return true; 615 } 616 return false; 617 } 618 619 /// Check that \p MI does not have implicit uses that overlap with it's \p Use 620 /// operand (the register being replaced), since these can sometimes be 621 /// implicitly tied to other operands. For example, on AMDGPU: 622 /// 623 /// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use> 624 /// 625 /// the %VGPR2 is implicitly tied to the larger reg operand, but we have no 626 /// way of knowing we need to update the latter when updating the former. 627 bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI, 628 const MachineOperand &Use) { 629 for (const MachineOperand &MIUse : MI.uses()) 630 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() && 631 MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg())) 632 return true; 633 634 return false; 635 } 636 637 /// For an MI that has multiple definitions, check whether \p MI has 638 /// a definition that overlaps with another of its definitions. 639 /// For example, on ARM: umull r9, r9, lr, r0 640 /// The umull instruction is unpredictable unless RdHi and RdLo are different. 641 bool MachineCopyPropagation::hasOverlappingMultipleDef( 642 const MachineInstr &MI, const MachineOperand &MODef, Register Def) { 643 for (const MachineOperand &MIDef : MI.defs()) { 644 if ((&MIDef != &MODef) && MIDef.isReg() && 645 TRI->regsOverlap(Def, MIDef.getReg())) 646 return true; 647 } 648 649 return false; 650 } 651 652 /// Look for available copies whose destination register is used by \p MI and 653 /// replace the use in \p MI with the copy's source register. 654 void MachineCopyPropagation::forwardUses(MachineInstr &MI) { 655 if (!Tracker.hasAnyCopies()) 656 return; 657 658 // Look for non-tied explicit vreg uses that have an active COPY 659 // instruction that defines the physical register allocated to them. 660 // Replace the vreg with the source of the active COPY. 661 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd; 662 ++OpIdx) { 663 MachineOperand &MOUse = MI.getOperand(OpIdx); 664 // Don't forward into undef use operands since doing so can cause problems 665 // with the machine verifier, since it doesn't treat undef reads as reads, 666 // so we can end up with a live range that ends on an undef read, leading to 667 // an error that the live range doesn't end on a read of the live range 668 // register. 669 if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() || 670 MOUse.isImplicit()) 671 continue; 672 673 if (!MOUse.getReg()) 674 continue; 675 676 // Check that the register is marked 'renamable' so we know it is safe to 677 // rename it without violating any constraints that aren't expressed in the 678 // IR (e.g. ABI or opcode requirements). 679 if (!MOUse.isRenamable()) 680 continue; 681 682 MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg().asMCReg(), 683 *TRI, *TII, UseCopyInstr); 684 if (!Copy) 685 continue; 686 687 std::optional<DestSourcePair> CopyOperands = 688 isCopyInstr(*Copy, *TII, UseCopyInstr); 689 Register CopyDstReg = CopyOperands->Destination->getReg(); 690 const MachineOperand &CopySrc = *CopyOperands->Source; 691 Register CopySrcReg = CopySrc.getReg(); 692 693 Register ForwardedReg = CopySrcReg; 694 // MI might use a sub-register of the Copy destination, in which case the 695 // forwarded register is the matching sub-register of the Copy source. 696 if (MOUse.getReg() != CopyDstReg) { 697 unsigned SubRegIdx = TRI->getSubRegIndex(CopyDstReg, MOUse.getReg()); 698 assert(SubRegIdx && 699 "MI source is not a sub-register of Copy destination"); 700 ForwardedReg = TRI->getSubReg(CopySrcReg, SubRegIdx); 701 if (!ForwardedReg) { 702 LLVM_DEBUG(dbgs() << "MCP: Copy source does not have sub-register " 703 << TRI->getSubRegIndexName(SubRegIdx) << '\n'); 704 continue; 705 } 706 } 707 708 // Don't forward COPYs of reserved regs unless they are constant. 709 if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg)) 710 continue; 711 712 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx)) 713 continue; 714 715 if (hasImplicitOverlap(MI, MOUse)) 716 continue; 717 718 // Check that the instruction is not a copy that partially overwrites the 719 // original copy source that we are about to use. The tracker mechanism 720 // cannot cope with that. 721 if (isCopyInstr(MI, *TII, UseCopyInstr) && 722 MI.modifiesRegister(CopySrcReg, TRI) && 723 !MI.definesRegister(CopySrcReg)) { 724 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI); 725 continue; 726 } 727 728 if (!DebugCounter::shouldExecute(FwdCounter)) { 729 LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n " 730 << MI); 731 continue; 732 } 733 734 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI) 735 << "\n with " << printReg(ForwardedReg, TRI) 736 << "\n in " << MI << " from " << *Copy); 737 738 MOUse.setReg(ForwardedReg); 739 740 if (!CopySrc.isRenamable()) 741 MOUse.setIsRenamable(false); 742 MOUse.setIsUndef(CopySrc.isUndef()); 743 744 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n"); 745 746 // Clear kill markers that may have been invalidated. 747 for (MachineInstr &KMI : 748 make_range(Copy->getIterator(), std::next(MI.getIterator()))) 749 KMI.clearRegisterKills(CopySrcReg, TRI); 750 751 ++NumCopyForwards; 752 Changed = true; 753 } 754 } 755 756 void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) { 757 LLVM_DEBUG(dbgs() << "MCP: ForwardCopyPropagateBlock " << MBB.getName() 758 << "\n"); 759 760 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) { 761 // Analyze copies (which don't overlap themselves). 762 std::optional<DestSourcePair> CopyOperands = 763 isCopyInstr(MI, *TII, UseCopyInstr); 764 if (CopyOperands) { 765 766 Register RegSrc = CopyOperands->Source->getReg(); 767 Register RegDef = CopyOperands->Destination->getReg(); 768 769 if (!TRI->regsOverlap(RegDef, RegSrc)) { 770 assert(RegDef.isPhysical() && RegSrc.isPhysical() && 771 "MachineCopyPropagation should be run after register allocation!"); 772 773 MCRegister Def = RegDef.asMCReg(); 774 MCRegister Src = RegSrc.asMCReg(); 775 776 // The two copies cancel out and the source of the first copy 777 // hasn't been overridden, eliminate the second one. e.g. 778 // %ecx = COPY %eax 779 // ... nothing clobbered eax. 780 // %eax = COPY %ecx 781 // => 782 // %ecx = COPY %eax 783 // 784 // or 785 // 786 // %ecx = COPY %eax 787 // ... nothing clobbered eax. 788 // %ecx = COPY %eax 789 // => 790 // %ecx = COPY %eax 791 if (eraseIfRedundant(MI, Def, Src) || eraseIfRedundant(MI, Src, Def)) 792 continue; 793 794 forwardUses(MI); 795 796 // Src may have been changed by forwardUses() 797 CopyOperands = isCopyInstr(MI, *TII, UseCopyInstr); 798 Src = CopyOperands->Source->getReg().asMCReg(); 799 800 // If Src is defined by a previous copy, the previous copy cannot be 801 // eliminated. 802 ReadRegister(Src, MI, RegularUse); 803 for (const MachineOperand &MO : MI.implicit_operands()) { 804 if (!MO.isReg() || !MO.readsReg()) 805 continue; 806 MCRegister Reg = MO.getReg().asMCReg(); 807 if (!Reg) 808 continue; 809 ReadRegister(Reg, MI, RegularUse); 810 } 811 812 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI.dump()); 813 814 // Copy is now a candidate for deletion. 815 if (!MRI->isReserved(Def)) 816 MaybeDeadCopies.insert(&MI); 817 818 // If 'Def' is previously source of another copy, then this earlier copy's 819 // source is no longer available. e.g. 820 // %xmm9 = copy %xmm2 821 // ... 822 // %xmm2 = copy %xmm0 823 // ... 824 // %xmm2 = copy %xmm9 825 Tracker.clobberRegister(Def, *TRI, *TII, UseCopyInstr); 826 for (const MachineOperand &MO : MI.implicit_operands()) { 827 if (!MO.isReg() || !MO.isDef()) 828 continue; 829 MCRegister Reg = MO.getReg().asMCReg(); 830 if (!Reg) 831 continue; 832 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr); 833 } 834 835 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr); 836 837 continue; 838 } 839 } 840 841 // Clobber any earlyclobber regs first. 842 for (const MachineOperand &MO : MI.operands()) 843 if (MO.isReg() && MO.isEarlyClobber()) { 844 MCRegister Reg = MO.getReg().asMCReg(); 845 // If we have a tied earlyclobber, that means it is also read by this 846 // instruction, so we need to make sure we don't remove it as dead 847 // later. 848 if (MO.isTied()) 849 ReadRegister(Reg, MI, RegularUse); 850 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr); 851 } 852 853 forwardUses(MI); 854 855 // Not a copy. 856 SmallVector<Register, 4> Defs; 857 const MachineOperand *RegMask = nullptr; 858 for (const MachineOperand &MO : MI.operands()) { 859 if (MO.isRegMask()) 860 RegMask = &MO; 861 if (!MO.isReg()) 862 continue; 863 Register Reg = MO.getReg(); 864 if (!Reg) 865 continue; 866 867 assert(!Reg.isVirtual() && 868 "MachineCopyPropagation should be run after register allocation!"); 869 870 if (MO.isDef() && !MO.isEarlyClobber()) { 871 Defs.push_back(Reg.asMCReg()); 872 continue; 873 } else if (MO.readsReg()) 874 ReadRegister(Reg.asMCReg(), MI, MO.isDebug() ? DebugUse : RegularUse); 875 } 876 877 // The instruction has a register mask operand which means that it clobbers 878 // a large set of registers. Treat clobbered registers the same way as 879 // defined registers. 880 if (RegMask) { 881 // Erase any MaybeDeadCopies whose destination register is clobbered. 882 for (SmallSetVector<MachineInstr *, 8>::iterator DI = 883 MaybeDeadCopies.begin(); 884 DI != MaybeDeadCopies.end();) { 885 MachineInstr *MaybeDead = *DI; 886 std::optional<DestSourcePair> CopyOperands = 887 isCopyInstr(*MaybeDead, *TII, UseCopyInstr); 888 MCRegister Reg = CopyOperands->Destination->getReg().asMCReg(); 889 assert(!MRI->isReserved(Reg)); 890 891 if (!RegMask->clobbersPhysReg(Reg)) { 892 ++DI; 893 continue; 894 } 895 896 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 897 MaybeDead->dump()); 898 899 // Make sure we invalidate any entries in the copy maps before erasing 900 // the instruction. 901 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr); 902 903 // erase() will return the next valid iterator pointing to the next 904 // element after the erased one. 905 DI = MaybeDeadCopies.erase(DI); 906 MaybeDead->eraseFromParent(); 907 Changed = true; 908 ++NumDeletes; 909 } 910 } 911 912 // Any previous copy definition or reading the Defs is no longer available. 913 for (MCRegister Reg : Defs) 914 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr); 915 } 916 917 // If MBB doesn't have successors, delete the copies whose defs are not used. 918 // If MBB does have successors, then conservative assume the defs are live-out 919 // since we don't want to trust live-in lists. 920 if (MBB.succ_empty()) { 921 for (MachineInstr *MaybeDead : MaybeDeadCopies) { 922 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: "; 923 MaybeDead->dump()); 924 925 std::optional<DestSourcePair> CopyOperands = 926 isCopyInstr(*MaybeDead, *TII, UseCopyInstr); 927 assert(CopyOperands); 928 929 Register SrcReg = CopyOperands->Source->getReg(); 930 Register DestReg = CopyOperands->Destination->getReg(); 931 assert(!MRI->isReserved(DestReg)); 932 933 // Update matching debug values, if any. 934 SmallVector<MachineInstr *> MaybeDeadDbgUsers( 935 CopyDbgUsers[MaybeDead].begin(), CopyDbgUsers[MaybeDead].end()); 936 MRI->updateDbgUsersToReg(DestReg.asMCReg(), SrcReg.asMCReg(), 937 MaybeDeadDbgUsers); 938 939 MaybeDead->eraseFromParent(); 940 Changed = true; 941 ++NumDeletes; 942 } 943 } 944 945 MaybeDeadCopies.clear(); 946 CopyDbgUsers.clear(); 947 Tracker.clear(); 948 } 949 950 static bool isBackwardPropagatableCopy(const DestSourcePair &CopyOperands, 951 const MachineRegisterInfo &MRI, 952 const TargetInstrInfo &TII) { 953 Register Def = CopyOperands.Destination->getReg(); 954 Register Src = CopyOperands.Source->getReg(); 955 956 if (!Def || !Src) 957 return false; 958 959 if (MRI.isReserved(Def) || MRI.isReserved(Src)) 960 return false; 961 962 return CopyOperands.Source->isRenamable() && CopyOperands.Source->isKill(); 963 } 964 965 void MachineCopyPropagation::propagateDefs(MachineInstr &MI) { 966 if (!Tracker.hasAnyCopies()) 967 return; 968 969 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd; 970 ++OpIdx) { 971 MachineOperand &MODef = MI.getOperand(OpIdx); 972 973 if (!MODef.isReg() || MODef.isUse()) 974 continue; 975 976 // Ignore non-trivial cases. 977 if (MODef.isTied() || MODef.isUndef() || MODef.isImplicit()) 978 continue; 979 980 if (!MODef.getReg()) 981 continue; 982 983 // We only handle if the register comes from a vreg. 984 if (!MODef.isRenamable()) 985 continue; 986 987 MachineInstr *Copy = Tracker.findAvailBackwardCopy( 988 MI, MODef.getReg().asMCReg(), *TRI, *TII, UseCopyInstr); 989 if (!Copy) 990 continue; 991 992 std::optional<DestSourcePair> CopyOperands = 993 isCopyInstr(*Copy, *TII, UseCopyInstr); 994 Register Def = CopyOperands->Destination->getReg(); 995 Register Src = CopyOperands->Source->getReg(); 996 997 if (MODef.getReg() != Src) 998 continue; 999 1000 if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx)) 1001 continue; 1002 1003 if (hasImplicitOverlap(MI, MODef)) 1004 continue; 1005 1006 if (hasOverlappingMultipleDef(MI, MODef, Def)) 1007 continue; 1008 1009 LLVM_DEBUG(dbgs() << "MCP: Replacing " << printReg(MODef.getReg(), TRI) 1010 << "\n with " << printReg(Def, TRI) << "\n in " 1011 << MI << " from " << *Copy); 1012 1013 MODef.setReg(Def); 1014 MODef.setIsRenamable(CopyOperands->Destination->isRenamable()); 1015 1016 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n"); 1017 MaybeDeadCopies.insert(Copy); 1018 Changed = true; 1019 ++NumCopyBackwardPropagated; 1020 } 1021 } 1022 1023 void MachineCopyPropagation::BackwardCopyPropagateBlock( 1024 MachineBasicBlock &MBB) { 1025 LLVM_DEBUG(dbgs() << "MCP: BackwardCopyPropagateBlock " << MBB.getName() 1026 << "\n"); 1027 1028 for (MachineInstr &MI : llvm::make_early_inc_range(llvm::reverse(MBB))) { 1029 // Ignore non-trivial COPYs. 1030 std::optional<DestSourcePair> CopyOperands = 1031 isCopyInstr(MI, *TII, UseCopyInstr); 1032 if (CopyOperands && MI.getNumOperands() == 2) { 1033 Register DefReg = CopyOperands->Destination->getReg(); 1034 Register SrcReg = CopyOperands->Source->getReg(); 1035 1036 if (!TRI->regsOverlap(DefReg, SrcReg)) { 1037 // Unlike forward cp, we don't invoke propagateDefs here, 1038 // just let forward cp do COPY-to-COPY propagation. 1039 if (isBackwardPropagatableCopy(*CopyOperands, *MRI, *TII)) { 1040 Tracker.invalidateRegister(SrcReg.asMCReg(), *TRI, *TII, 1041 UseCopyInstr); 1042 Tracker.invalidateRegister(DefReg.asMCReg(), *TRI, *TII, 1043 UseCopyInstr); 1044 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr); 1045 continue; 1046 } 1047 } 1048 } 1049 1050 // Invalidate any earlyclobber regs first. 1051 for (const MachineOperand &MO : MI.operands()) 1052 if (MO.isReg() && MO.isEarlyClobber()) { 1053 MCRegister Reg = MO.getReg().asMCReg(); 1054 if (!Reg) 1055 continue; 1056 Tracker.invalidateRegister(Reg, *TRI, *TII, UseCopyInstr); 1057 } 1058 1059 propagateDefs(MI); 1060 for (const MachineOperand &MO : MI.operands()) { 1061 if (!MO.isReg()) 1062 continue; 1063 1064 if (!MO.getReg()) 1065 continue; 1066 1067 if (MO.isDef()) 1068 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII, 1069 UseCopyInstr); 1070 1071 if (MO.readsReg()) { 1072 if (MO.isDebug()) { 1073 // Check if the register in the debug instruction is utilized 1074 // in a copy instruction, so we can update the debug info if the 1075 // register is changed. 1076 for (MCRegUnit Unit : TRI->regunits(MO.getReg().asMCReg())) { 1077 if (auto *Copy = Tracker.findCopyDefViaUnit(Unit, *TRI)) { 1078 CopyDbgUsers[Copy].insert(&MI); 1079 } 1080 } 1081 } else { 1082 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII, 1083 UseCopyInstr); 1084 } 1085 } 1086 } 1087 } 1088 1089 for (auto *Copy : MaybeDeadCopies) { 1090 std::optional<DestSourcePair> CopyOperands = 1091 isCopyInstr(*Copy, *TII, UseCopyInstr); 1092 Register Src = CopyOperands->Source->getReg(); 1093 Register Def = CopyOperands->Destination->getReg(); 1094 SmallVector<MachineInstr *> MaybeDeadDbgUsers(CopyDbgUsers[Copy].begin(), 1095 CopyDbgUsers[Copy].end()); 1096 1097 MRI->updateDbgUsersToReg(Src.asMCReg(), Def.asMCReg(), MaybeDeadDbgUsers); 1098 Copy->eraseFromParent(); 1099 ++NumDeletes; 1100 } 1101 1102 MaybeDeadCopies.clear(); 1103 CopyDbgUsers.clear(); 1104 Tracker.clear(); 1105 } 1106 1107 static void LLVM_ATTRIBUTE_UNUSED printSpillReloadChain( 1108 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &SpillChain, 1109 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> &ReloadChain, 1110 MachineInstr *Leader) { 1111 auto &SC = SpillChain[Leader]; 1112 auto &RC = ReloadChain[Leader]; 1113 for (auto I = SC.rbegin(), E = SC.rend(); I != E; ++I) 1114 (*I)->dump(); 1115 for (MachineInstr *MI : RC) 1116 MI->dump(); 1117 } 1118 1119 // Remove spill-reload like copy chains. For example 1120 // r0 = COPY r1 1121 // r1 = COPY r2 1122 // r2 = COPY r3 1123 // r3 = COPY r4 1124 // <def-use r4> 1125 // r4 = COPY r3 1126 // r3 = COPY r2 1127 // r2 = COPY r1 1128 // r1 = COPY r0 1129 // will be folded into 1130 // r0 = COPY r1 1131 // r1 = COPY r4 1132 // <def-use r4> 1133 // r4 = COPY r1 1134 // r1 = COPY r0 1135 // TODO: Currently we don't track usage of r0 outside the chain, so we 1136 // conservatively keep its value as it was before the rewrite. 1137 // 1138 // The algorithm is trying to keep 1139 // property#1: No Def of spill COPY in the chain is used or defined until the 1140 // paired reload COPY in the chain uses the Def. 1141 // 1142 // property#2: NO Source of COPY in the chain is used or defined until the next 1143 // COPY in the chain defines the Source, except the innermost spill-reload 1144 // pair. 1145 // 1146 // The algorithm is conducted by checking every COPY inside the MBB, assuming 1147 // the COPY is a reload COPY, then try to find paired spill COPY by searching 1148 // the COPY defines the Src of the reload COPY backward. If such pair is found, 1149 // it either belongs to an existing chain or a new chain depends on 1150 // last available COPY uses the Def of the reload COPY. 1151 // Implementation notes, we use CopyTracker::findLastDefCopy(Reg, ...) to find 1152 // out last COPY that defines Reg; we use CopyTracker::findLastUseCopy(Reg, ...) 1153 // to find out last COPY that uses Reg. When we are encountered with a Non-COPY 1154 // instruction, we check registers in the operands of this instruction. If this 1155 // Reg is defined by a COPY, we untrack this Reg via 1156 // CopyTracker::clobberRegister(Reg, ...). 1157 void MachineCopyPropagation::EliminateSpillageCopies(MachineBasicBlock &MBB) { 1158 // ChainLeader maps MI inside a spill-reload chain to its innermost reload COPY. 1159 // Thus we can track if a MI belongs to an existing spill-reload chain. 1160 DenseMap<MachineInstr *, MachineInstr *> ChainLeader; 1161 // SpillChain maps innermost reload COPY of a spill-reload chain to a sequence 1162 // of COPYs that forms spills of a spill-reload chain. 1163 // ReloadChain maps innermost reload COPY of a spill-reload chain to a 1164 // sequence of COPYs that forms reloads of a spill-reload chain. 1165 DenseMap<MachineInstr *, SmallVector<MachineInstr *>> SpillChain, ReloadChain; 1166 // If a COPY's Source has use or def until next COPY defines the Source, 1167 // we put the COPY in this set to keep property#2. 1168 DenseSet<const MachineInstr *> CopySourceInvalid; 1169 1170 auto TryFoldSpillageCopies = 1171 [&, this](const SmallVectorImpl<MachineInstr *> &SC, 1172 const SmallVectorImpl<MachineInstr *> &RC) { 1173 assert(SC.size() == RC.size() && "Spill-reload should be paired"); 1174 1175 // We need at least 3 pairs of copies for the transformation to apply, 1176 // because the first outermost pair cannot be removed since we don't 1177 // recolor outside of the chain and that we need at least one temporary 1178 // spill slot to shorten the chain. If we only have a chain of two 1179 // pairs, we already have the shortest sequence this code can handle: 1180 // the outermost pair for the temporary spill slot, and the pair that 1181 // use that temporary spill slot for the other end of the chain. 1182 // TODO: We might be able to simplify to one spill-reload pair if collecting 1183 // more infomation about the outermost COPY. 1184 if (SC.size() <= 2) 1185 return; 1186 1187 // If violate property#2, we don't fold the chain. 1188 for (const MachineInstr *Spill : drop_begin(SC)) 1189 if (CopySourceInvalid.count(Spill)) 1190 return; 1191 1192 for (const MachineInstr *Reload : drop_end(RC)) 1193 if (CopySourceInvalid.count(Reload)) 1194 return; 1195 1196 auto CheckCopyConstraint = [this](Register Def, Register Src) { 1197 for (const TargetRegisterClass *RC : TRI->regclasses()) { 1198 if (RC->contains(Def) && RC->contains(Src)) 1199 return true; 1200 } 1201 return false; 1202 }; 1203 1204 auto UpdateReg = [](MachineInstr *MI, const MachineOperand *Old, 1205 const MachineOperand *New) { 1206 for (MachineOperand &MO : MI->operands()) { 1207 if (&MO == Old) 1208 MO.setReg(New->getReg()); 1209 } 1210 }; 1211 1212 std::optional<DestSourcePair> InnerMostSpillCopy = 1213 isCopyInstr(*SC[0], *TII, UseCopyInstr); 1214 std::optional<DestSourcePair> OuterMostSpillCopy = 1215 isCopyInstr(*SC.back(), *TII, UseCopyInstr); 1216 std::optional<DestSourcePair> InnerMostReloadCopy = 1217 isCopyInstr(*RC[0], *TII, UseCopyInstr); 1218 std::optional<DestSourcePair> OuterMostReloadCopy = 1219 isCopyInstr(*RC.back(), *TII, UseCopyInstr); 1220 if (!CheckCopyConstraint(OuterMostSpillCopy->Source->getReg(), 1221 InnerMostSpillCopy->Source->getReg()) || 1222 !CheckCopyConstraint(InnerMostReloadCopy->Destination->getReg(), 1223 OuterMostReloadCopy->Destination->getReg())) 1224 return; 1225 1226 SpillageChainsLength += SC.size() + RC.size(); 1227 NumSpillageChains += 1; 1228 UpdateReg(SC[0], InnerMostSpillCopy->Destination, 1229 OuterMostSpillCopy->Source); 1230 UpdateReg(RC[0], InnerMostReloadCopy->Source, 1231 OuterMostReloadCopy->Destination); 1232 1233 for (size_t I = 1; I < SC.size() - 1; ++I) { 1234 SC[I]->eraseFromParent(); 1235 RC[I]->eraseFromParent(); 1236 NumDeletes += 2; 1237 } 1238 }; 1239 1240 auto IsFoldableCopy = [this](const MachineInstr &MaybeCopy) { 1241 if (MaybeCopy.getNumImplicitOperands() > 0) 1242 return false; 1243 std::optional<DestSourcePair> CopyOperands = 1244 isCopyInstr(MaybeCopy, *TII, UseCopyInstr); 1245 if (!CopyOperands) 1246 return false; 1247 Register Src = CopyOperands->Source->getReg(); 1248 Register Def = CopyOperands->Destination->getReg(); 1249 return Src && Def && !TRI->regsOverlap(Src, Def) && 1250 CopyOperands->Source->isRenamable() && 1251 CopyOperands->Destination->isRenamable(); 1252 }; 1253 1254 auto IsSpillReloadPair = [&, this](const MachineInstr &Spill, 1255 const MachineInstr &Reload) { 1256 if (!IsFoldableCopy(Spill) || !IsFoldableCopy(Reload)) 1257 return false; 1258 std::optional<DestSourcePair> SpillCopy = 1259 isCopyInstr(Spill, *TII, UseCopyInstr); 1260 std::optional<DestSourcePair> ReloadCopy = 1261 isCopyInstr(Reload, *TII, UseCopyInstr); 1262 if (!SpillCopy || !ReloadCopy) 1263 return false; 1264 return SpillCopy->Source->getReg() == ReloadCopy->Destination->getReg() && 1265 SpillCopy->Destination->getReg() == ReloadCopy->Source->getReg(); 1266 }; 1267 1268 auto IsChainedCopy = [&, this](const MachineInstr &Prev, 1269 const MachineInstr &Current) { 1270 if (!IsFoldableCopy(Prev) || !IsFoldableCopy(Current)) 1271 return false; 1272 std::optional<DestSourcePair> PrevCopy = 1273 isCopyInstr(Prev, *TII, UseCopyInstr); 1274 std::optional<DestSourcePair> CurrentCopy = 1275 isCopyInstr(Current, *TII, UseCopyInstr); 1276 if (!PrevCopy || !CurrentCopy) 1277 return false; 1278 return PrevCopy->Source->getReg() == CurrentCopy->Destination->getReg(); 1279 }; 1280 1281 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) { 1282 std::optional<DestSourcePair> CopyOperands = 1283 isCopyInstr(MI, *TII, UseCopyInstr); 1284 1285 // Update track information via non-copy instruction. 1286 SmallSet<Register, 8> RegsToClobber; 1287 if (!CopyOperands) { 1288 for (const MachineOperand &MO : MI.operands()) { 1289 if (!MO.isReg()) 1290 continue; 1291 Register Reg = MO.getReg(); 1292 if (!Reg) 1293 continue; 1294 MachineInstr *LastUseCopy = 1295 Tracker.findLastSeenUseInCopy(Reg.asMCReg(), *TRI); 1296 if (LastUseCopy) { 1297 LLVM_DEBUG(dbgs() << "MCP: Copy source of\n"); 1298 LLVM_DEBUG(LastUseCopy->dump()); 1299 LLVM_DEBUG(dbgs() << "might be invalidated by\n"); 1300 LLVM_DEBUG(MI.dump()); 1301 CopySourceInvalid.insert(LastUseCopy); 1302 } 1303 // Must be noted Tracker.clobberRegister(Reg, ...) removes tracking of 1304 // Reg, i.e, COPY that defines Reg is removed from the mapping as well 1305 // as marking COPYs that uses Reg unavailable. 1306 // We don't invoke CopyTracker::clobberRegister(Reg, ...) if Reg is not 1307 // defined by a previous COPY, since we don't want to make COPYs uses 1308 // Reg unavailable. 1309 if (Tracker.findLastSeenDefInCopy(MI, Reg.asMCReg(), *TRI, *TII, 1310 UseCopyInstr)) 1311 // Thus we can keep the property#1. 1312 RegsToClobber.insert(Reg); 1313 } 1314 for (Register Reg : RegsToClobber) { 1315 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr); 1316 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Reg, TRI) 1317 << "\n"); 1318 } 1319 continue; 1320 } 1321 1322 Register Src = CopyOperands->Source->getReg(); 1323 Register Def = CopyOperands->Destination->getReg(); 1324 // Check if we can find a pair spill-reload copy. 1325 LLVM_DEBUG(dbgs() << "MCP: Searching paired spill for reload: "); 1326 LLVM_DEBUG(MI.dump()); 1327 MachineInstr *MaybeSpill = 1328 Tracker.findLastSeenDefInCopy(MI, Src.asMCReg(), *TRI, *TII, UseCopyInstr); 1329 bool MaybeSpillIsChained = ChainLeader.count(MaybeSpill); 1330 if (!MaybeSpillIsChained && MaybeSpill && 1331 IsSpillReloadPair(*MaybeSpill, MI)) { 1332 // Check if we already have an existing chain. Now we have a 1333 // spill-reload pair. 1334 // L2: r2 = COPY r3 1335 // L5: r3 = COPY r2 1336 // Looking for a valid COPY before L5 which uses r3. 1337 // This can be serverial cases. 1338 // Case #1: 1339 // No COPY is found, which can be r3 is def-use between (L2, L5), we 1340 // create a new chain for L2 and L5. 1341 // Case #2: 1342 // L2: r2 = COPY r3 1343 // L5: r3 = COPY r2 1344 // Such COPY is found and is L2, we create a new chain for L2 and L5. 1345 // Case #3: 1346 // L2: r2 = COPY r3 1347 // L3: r1 = COPY r3 1348 // L5: r3 = COPY r2 1349 // we create a new chain for L2 and L5. 1350 // Case #4: 1351 // L2: r2 = COPY r3 1352 // L3: r1 = COPY r3 1353 // L4: r3 = COPY r1 1354 // L5: r3 = COPY r2 1355 // Such COPY won't be found since L4 defines r3. we create a new chain 1356 // for L2 and L5. 1357 // Case #5: 1358 // L2: r2 = COPY r3 1359 // L3: r3 = COPY r1 1360 // L4: r1 = COPY r3 1361 // L5: r3 = COPY r2 1362 // COPY is found and is L4 which belongs to an existing chain, we add 1363 // L2 and L5 to this chain. 1364 LLVM_DEBUG(dbgs() << "MCP: Found spill: "); 1365 LLVM_DEBUG(MaybeSpill->dump()); 1366 MachineInstr *MaybePrevReload = 1367 Tracker.findLastSeenUseInCopy(Def.asMCReg(), *TRI); 1368 auto Leader = ChainLeader.find(MaybePrevReload); 1369 MachineInstr *L = nullptr; 1370 if (Leader == ChainLeader.end() || 1371 (MaybePrevReload && !IsChainedCopy(*MaybePrevReload, MI))) { 1372 L = &MI; 1373 assert(!SpillChain.count(L) && 1374 "SpillChain should not have contained newly found chain"); 1375 } else { 1376 assert(MaybePrevReload && 1377 "Found a valid leader through nullptr should not happend"); 1378 L = Leader->second; 1379 assert(SpillChain[L].size() > 0 && 1380 "Existing chain's length should be larger than zero"); 1381 } 1382 assert(!ChainLeader.count(&MI) && !ChainLeader.count(MaybeSpill) && 1383 "Newly found paired spill-reload should not belong to any chain " 1384 "at this point"); 1385 ChainLeader.insert({MaybeSpill, L}); 1386 ChainLeader.insert({&MI, L}); 1387 SpillChain[L].push_back(MaybeSpill); 1388 ReloadChain[L].push_back(&MI); 1389 LLVM_DEBUG(dbgs() << "MCP: Chain " << L << " now is:\n"); 1390 LLVM_DEBUG(printSpillReloadChain(SpillChain, ReloadChain, L)); 1391 } else if (MaybeSpill && !MaybeSpillIsChained) { 1392 // MaybeSpill is unable to pair with MI. That's to say adding MI makes 1393 // the chain invalid. 1394 // The COPY defines Src is no longer considered as a candidate of a 1395 // valid chain. Since we expect the Def of a spill copy isn't used by 1396 // any COPY instruction until a reload copy. For example: 1397 // L1: r1 = COPY r2 1398 // L2: r3 = COPY r1 1399 // If we later have 1400 // L1: r1 = COPY r2 1401 // L2: r3 = COPY r1 1402 // L3: r2 = COPY r1 1403 // L1 and L3 can't be a valid spill-reload pair. 1404 // Thus we keep the property#1. 1405 LLVM_DEBUG(dbgs() << "MCP: Not paired spill-reload:\n"); 1406 LLVM_DEBUG(MaybeSpill->dump()); 1407 LLVM_DEBUG(MI.dump()); 1408 Tracker.clobberRegister(Src.asMCReg(), *TRI, *TII, UseCopyInstr); 1409 LLVM_DEBUG(dbgs() << "MCP: Removed tracking of " << printReg(Src, TRI) 1410 << "\n"); 1411 } 1412 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr); 1413 } 1414 1415 for (auto I = SpillChain.begin(), E = SpillChain.end(); I != E; ++I) { 1416 auto &SC = I->second; 1417 assert(ReloadChain.count(I->first) && 1418 "Reload chain of the same leader should exist"); 1419 auto &RC = ReloadChain[I->first]; 1420 TryFoldSpillageCopies(SC, RC); 1421 } 1422 1423 MaybeDeadCopies.clear(); 1424 CopyDbgUsers.clear(); 1425 Tracker.clear(); 1426 } 1427 1428 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 1429 if (skipFunction(MF.getFunction())) 1430 return false; 1431 1432 bool isSpillageCopyElimEnabled = false; 1433 switch (EnableSpillageCopyElimination) { 1434 case cl::BOU_UNSET: 1435 isSpillageCopyElimEnabled = 1436 MF.getSubtarget().enableSpillageCopyElimination(); 1437 break; 1438 case cl::BOU_TRUE: 1439 isSpillageCopyElimEnabled = true; 1440 break; 1441 case cl::BOU_FALSE: 1442 isSpillageCopyElimEnabled = false; 1443 break; 1444 } 1445 1446 Changed = false; 1447 1448 TRI = MF.getSubtarget().getRegisterInfo(); 1449 TII = MF.getSubtarget().getInstrInfo(); 1450 MRI = &MF.getRegInfo(); 1451 1452 for (MachineBasicBlock &MBB : MF) { 1453 if (isSpillageCopyElimEnabled) 1454 EliminateSpillageCopies(MBB); 1455 BackwardCopyPropagateBlock(MBB); 1456 ForwardCopyPropagateBlock(MBB); 1457 } 1458 1459 return Changed; 1460 } 1461 1462 MachineFunctionPass * 1463 llvm::createMachineCopyPropagationPass(bool UseCopyInstr = false) { 1464 return new MachineCopyPropagation(UseCopyInstr); 1465 } 1466