1 //===- RegisterScavenging.cpp - Machine register scavenging ---------------===// 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 /// \file 10 /// This file implements the machine register scavenger. It can provide 11 /// information, such as unused registers, at any point in a machine basic 12 /// block. It also provides a mechanism to make registers available by evicting 13 /// them to spill slots. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/CodeGen/RegisterScavenging.h" 18 #include "llvm/ADT/ArrayRef.h" 19 #include "llvm/ADT/BitVector.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/CodeGen/LiveRegUnits.h" 23 #include "llvm/CodeGen/MachineBasicBlock.h" 24 #include "llvm/CodeGen/MachineFrameInfo.h" 25 #include "llvm/CodeGen/MachineFunction.h" 26 #include "llvm/CodeGen/MachineFunctionPass.h" 27 #include "llvm/CodeGen/MachineInstr.h" 28 #include "llvm/CodeGen/MachineOperand.h" 29 #include "llvm/CodeGen/MachineRegisterInfo.h" 30 #include "llvm/CodeGen/TargetFrameLowering.h" 31 #include "llvm/CodeGen/TargetInstrInfo.h" 32 #include "llvm/CodeGen/TargetRegisterInfo.h" 33 #include "llvm/CodeGen/TargetSubtargetInfo.h" 34 #include "llvm/InitializePasses.h" 35 #include "llvm/MC/MCRegisterInfo.h" 36 #include "llvm/Pass.h" 37 #include "llvm/Support/Debug.h" 38 #include "llvm/Support/ErrorHandling.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include <algorithm> 41 #include <cassert> 42 #include <iterator> 43 #include <limits> 44 #include <string> 45 #include <utility> 46 47 using namespace llvm; 48 49 #define DEBUG_TYPE "reg-scavenging" 50 51 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged"); 52 53 void RegScavenger::setRegUsed(Register Reg, LaneBitmask LaneMask) { 54 LiveUnits.addRegMasked(Reg, LaneMask); 55 } 56 57 void RegScavenger::init(MachineBasicBlock &MBB) { 58 MachineFunction &MF = *MBB.getParent(); 59 TII = MF.getSubtarget().getInstrInfo(); 60 TRI = MF.getSubtarget().getRegisterInfo(); 61 MRI = &MF.getRegInfo(); 62 LiveUnits.init(*TRI); 63 64 assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) && 65 "Target changed?"); 66 67 // Self-initialize. 68 if (!this->MBB) { 69 NumRegUnits = TRI->getNumRegUnits(); 70 KillRegUnits.resize(NumRegUnits); 71 DefRegUnits.resize(NumRegUnits); 72 TmpRegUnits.resize(NumRegUnits); 73 } 74 this->MBB = &MBB; 75 76 for (ScavengedInfo &SI : Scavenged) { 77 SI.Reg = 0; 78 SI.Restore = nullptr; 79 } 80 81 Tracking = false; 82 } 83 84 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) { 85 init(MBB); 86 LiveUnits.addLiveIns(MBB); 87 } 88 89 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) { 90 init(MBB); 91 LiveUnits.addLiveOuts(MBB); 92 93 // Move internal iterator at the last instruction of the block. 94 if (!MBB.empty()) { 95 MBBI = std::prev(MBB.end()); 96 Tracking = true; 97 } 98 } 99 100 void RegScavenger::addRegUnits(BitVector &BV, MCRegister Reg) { 101 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) 102 BV.set(*RUI); 103 } 104 105 void RegScavenger::removeRegUnits(BitVector &BV, MCRegister Reg) { 106 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) 107 BV.reset(*RUI); 108 } 109 110 void RegScavenger::determineKillsAndDefs() { 111 assert(Tracking && "Must be tracking to determine kills and defs"); 112 113 MachineInstr &MI = *MBBI; 114 assert(!MI.isDebugInstr() && "Debug values have no kills or defs"); 115 116 // Find out which registers are early clobbered, killed, defined, and marked 117 // def-dead in this instruction. 118 KillRegUnits.reset(); 119 DefRegUnits.reset(); 120 for (const MachineOperand &MO : MI.operands()) { 121 if (MO.isRegMask()) { 122 TmpRegUnits.reset(); 123 for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) { 124 for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) { 125 if (MO.clobbersPhysReg(*RURI)) { 126 TmpRegUnits.set(RU); 127 break; 128 } 129 } 130 } 131 132 // Apply the mask. 133 KillRegUnits |= TmpRegUnits; 134 } 135 if (!MO.isReg()) 136 continue; 137 if (!MO.getReg().isPhysical() || isReserved(MO.getReg())) 138 continue; 139 MCRegister Reg = MO.getReg().asMCReg(); 140 141 if (MO.isUse()) { 142 // Ignore undef uses. 143 if (MO.isUndef()) 144 continue; 145 if (MO.isKill()) 146 addRegUnits(KillRegUnits, Reg); 147 } else { 148 assert(MO.isDef()); 149 if (MO.isDead()) 150 addRegUnits(KillRegUnits, Reg); 151 else 152 addRegUnits(DefRegUnits, Reg); 153 } 154 } 155 } 156 157 void RegScavenger::forward() { 158 // Move ptr forward. 159 if (!Tracking) { 160 MBBI = MBB->begin(); 161 Tracking = true; 162 } else { 163 assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 164 MBBI = std::next(MBBI); 165 } 166 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 167 168 MachineInstr &MI = *MBBI; 169 170 for (ScavengedInfo &I : Scavenged) { 171 if (I.Restore != &MI) 172 continue; 173 174 I.Reg = 0; 175 I.Restore = nullptr; 176 } 177 178 if (MI.isDebugOrPseudoInstr()) 179 return; 180 181 determineKillsAndDefs(); 182 183 // Verify uses and defs. 184 #ifndef NDEBUG 185 for (const MachineOperand &MO : MI.operands()) { 186 if (!MO.isReg()) 187 continue; 188 Register Reg = MO.getReg(); 189 if (!Register::isPhysicalRegister(Reg) || isReserved(Reg)) 190 continue; 191 if (MO.isUse()) { 192 if (MO.isUndef()) 193 continue; 194 if (!isRegUsed(Reg)) { 195 // Check if it's partial live: e.g. 196 // D0 = insert_subreg undef D0, S0 197 // ... D0 198 // The problem is the insert_subreg could be eliminated. The use of 199 // D0 is using a partially undef value. This is not *incorrect* since 200 // S1 is can be freely clobbered. 201 // Ideally we would like a way to model this, but leaving the 202 // insert_subreg around causes both correctness and performance issues. 203 bool SubUsed = false; 204 for (const MCPhysReg &SubReg : TRI->subregs(Reg)) 205 if (isRegUsed(SubReg)) { 206 SubUsed = true; 207 break; 208 } 209 bool SuperUsed = false; 210 for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) { 211 if (isRegUsed(*SR)) { 212 SuperUsed = true; 213 break; 214 } 215 } 216 if (!SubUsed && !SuperUsed) { 217 MBB->getParent()->verify(nullptr, "In Register Scavenger"); 218 llvm_unreachable("Using an undefined register!"); 219 } 220 (void)SubUsed; 221 (void)SuperUsed; 222 } 223 } else { 224 assert(MO.isDef()); 225 #if 0 226 // FIXME: Enable this once we've figured out how to correctly transfer 227 // implicit kills during codegen passes like the coalescer. 228 assert((KillRegs.test(Reg) || isUnused(Reg) || 229 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 230 "Re-defining a live register!"); 231 #endif 232 } 233 } 234 #endif // NDEBUG 235 236 // Commit the changes. 237 setUnused(KillRegUnits); 238 setUsed(DefRegUnits); 239 } 240 241 void RegScavenger::backward() { 242 assert(Tracking && "Must be tracking to determine kills and defs"); 243 244 const MachineInstr &MI = *MBBI; 245 LiveUnits.stepBackward(MI); 246 247 // Expire scavenge spill frameindex uses. 248 for (ScavengedInfo &I : Scavenged) { 249 if (I.Restore == &MI) { 250 I.Reg = 0; 251 I.Restore = nullptr; 252 } 253 } 254 255 if (MBBI == MBB->begin()) { 256 MBBI = MachineBasicBlock::iterator(nullptr); 257 Tracking = false; 258 } else 259 --MBBI; 260 } 261 262 bool RegScavenger::isRegUsed(Register Reg, bool includeReserved) const { 263 if (isReserved(Reg)) 264 return includeReserved; 265 return !LiveUnits.available(Reg); 266 } 267 268 Register RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 269 for (Register Reg : *RC) { 270 if (!isRegUsed(Reg)) { 271 LLVM_DEBUG(dbgs() << "Scavenger found unused reg: " << printReg(Reg, TRI) 272 << "\n"); 273 return Reg; 274 } 275 } 276 return 0; 277 } 278 279 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 280 BitVector Mask(TRI->getNumRegs()); 281 for (Register Reg : *RC) 282 if (!isRegUsed(Reg)) 283 Mask.set(Reg); 284 return Mask; 285 } 286 287 Register RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 288 BitVector &Candidates, 289 unsigned InstrLimit, 290 MachineBasicBlock::iterator &UseMI) { 291 int Survivor = Candidates.find_first(); 292 assert(Survivor > 0 && "No candidates for scavenging"); 293 294 MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 295 assert(StartMI != ME && "MI already at terminator"); 296 MachineBasicBlock::iterator RestorePointMI = StartMI; 297 MachineBasicBlock::iterator MI = StartMI; 298 299 bool inVirtLiveRange = false; 300 for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 301 if (MI->isDebugOrPseudoInstr()) { 302 ++InstrLimit; // Don't count debug instructions 303 continue; 304 } 305 bool isVirtKillInsn = false; 306 bool isVirtDefInsn = false; 307 // Remove any candidates touched by instruction. 308 for (const MachineOperand &MO : MI->operands()) { 309 if (MO.isRegMask()) 310 Candidates.clearBitsNotInMask(MO.getRegMask()); 311 if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 312 continue; 313 if (Register::isVirtualRegister(MO.getReg())) { 314 if (MO.isDef()) 315 isVirtDefInsn = true; 316 else if (MO.isKill()) 317 isVirtKillInsn = true; 318 continue; 319 } 320 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 321 Candidates.reset(*AI); 322 } 323 // If we're not in a virtual reg's live range, this is a valid 324 // restore point. 325 if (!inVirtLiveRange) RestorePointMI = MI; 326 327 // Update whether we're in the live range of a virtual register 328 if (isVirtKillInsn) inVirtLiveRange = false; 329 if (isVirtDefInsn) inVirtLiveRange = true; 330 331 // Was our survivor untouched by this instruction? 332 if (Candidates.test(Survivor)) 333 continue; 334 335 // All candidates gone? 336 if (Candidates.none()) 337 break; 338 339 Survivor = Candidates.find_first(); 340 } 341 // If we ran off the end, that's where we want to restore. 342 if (MI == ME) RestorePointMI = ME; 343 assert(RestorePointMI != StartMI && 344 "No available scavenger restore location!"); 345 346 // We ran out of candidates, so stop the search. 347 UseMI = RestorePointMI; 348 return Survivor; 349 } 350 351 /// Given the bitvector \p Available of free register units at position 352 /// \p From. Search backwards to find a register that is part of \p 353 /// Candidates and not used/clobbered until the point \p To. If there is 354 /// multiple candidates continue searching and pick the one that is not used/ 355 /// clobbered for the longest time. 356 /// Returns the register and the earliest position we know it to be free or 357 /// the position MBB.end() if no register is available. 358 static std::pair<MCPhysReg, MachineBasicBlock::iterator> 359 findSurvivorBackwards(const MachineRegisterInfo &MRI, 360 MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, 361 const LiveRegUnits &LiveOut, ArrayRef<MCPhysReg> AllocationOrder, 362 bool RestoreAfter) { 363 bool FoundTo = false; 364 MCPhysReg Survivor = 0; 365 MachineBasicBlock::iterator Pos; 366 MachineBasicBlock &MBB = *From->getParent(); 367 unsigned InstrLimit = 25; 368 unsigned InstrCountDown = InstrLimit; 369 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 370 LiveRegUnits Used(TRI); 371 372 assert(From->getParent() == To->getParent() && 373 "Target instruction is in other than current basic block, use " 374 "enterBasicBlockEnd first"); 375 376 for (MachineBasicBlock::iterator I = From;; --I) { 377 const MachineInstr &MI = *I; 378 379 Used.accumulate(MI); 380 381 if (I == To) { 382 // See if one of the registers in RC wasn't used so far. 383 for (MCPhysReg Reg : AllocationOrder) { 384 if (!MRI.isReserved(Reg) && Used.available(Reg) && 385 LiveOut.available(Reg)) 386 return std::make_pair(Reg, MBB.end()); 387 } 388 // Otherwise we will continue up to InstrLimit instructions to find 389 // the register which is not defined/used for the longest time. 390 FoundTo = true; 391 Pos = To; 392 // Note: It was fine so far to start our search at From, however now that 393 // we have to spill, and can only place the restore after From then 394 // add the regs used/defed by std::next(From) to the set. 395 if (RestoreAfter) 396 Used.accumulate(*std::next(From)); 397 } 398 if (FoundTo) { 399 if (Survivor == 0 || !Used.available(Survivor)) { 400 MCPhysReg AvilableReg = 0; 401 for (MCPhysReg Reg : AllocationOrder) { 402 if (!MRI.isReserved(Reg) && Used.available(Reg)) { 403 AvilableReg = Reg; 404 break; 405 } 406 } 407 if (AvilableReg == 0) 408 break; 409 Survivor = AvilableReg; 410 } 411 if (--InstrCountDown == 0) 412 break; 413 414 // Keep searching when we find a vreg since the spilled register will 415 // be usefull for this other vreg as well later. 416 bool FoundVReg = false; 417 for (const MachineOperand &MO : MI.operands()) { 418 if (MO.isReg() && Register::isVirtualRegister(MO.getReg())) { 419 FoundVReg = true; 420 break; 421 } 422 } 423 if (FoundVReg) { 424 InstrCountDown = InstrLimit; 425 Pos = I; 426 } 427 if (I == MBB.begin()) 428 break; 429 } 430 assert(I != MBB.begin() && "Did not find target instruction while " 431 "iterating backwards"); 432 } 433 434 return std::make_pair(Survivor, Pos); 435 } 436 437 static unsigned getFrameIndexOperandNum(MachineInstr &MI) { 438 unsigned i = 0; 439 while (!MI.getOperand(i).isFI()) { 440 ++i; 441 assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!"); 442 } 443 return i; 444 } 445 446 RegScavenger::ScavengedInfo & 447 RegScavenger::spill(Register Reg, const TargetRegisterClass &RC, int SPAdj, 448 MachineBasicBlock::iterator Before, 449 MachineBasicBlock::iterator &UseMI) { 450 // Find an available scavenging slot with size and alignment matching 451 // the requirements of the class RC. 452 const MachineFunction &MF = *Before->getMF(); 453 const MachineFrameInfo &MFI = MF.getFrameInfo(); 454 unsigned NeedSize = TRI->getSpillSize(RC); 455 Align NeedAlign = TRI->getSpillAlign(RC); 456 457 unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max(); 458 int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd(); 459 for (unsigned I = 0; I < Scavenged.size(); ++I) { 460 if (Scavenged[I].Reg != 0) 461 continue; 462 // Verify that this slot is valid for this register. 463 int FI = Scavenged[I].FrameIndex; 464 if (FI < FIB || FI >= FIE) 465 continue; 466 unsigned S = MFI.getObjectSize(FI); 467 Align A = MFI.getObjectAlign(FI); 468 if (NeedSize > S || NeedAlign > A) 469 continue; 470 // Avoid wasting slots with large size and/or large alignment. Pick one 471 // that is the best fit for this register class (in street metric). 472 // Picking a larger slot than necessary could happen if a slot for a 473 // larger register is reserved before a slot for a smaller one. When 474 // trying to spill a smaller register, the large slot would be found 475 // first, thus making it impossible to spill the larger register later. 476 unsigned D = (S - NeedSize) + (A.value() - NeedAlign.value()); 477 if (D < Diff) { 478 SI = I; 479 Diff = D; 480 } 481 } 482 483 if (SI == Scavenged.size()) { 484 // We need to scavenge a register but have no spill slot, the target 485 // must know how to do it (if not, we'll assert below). 486 Scavenged.push_back(ScavengedInfo(FIE)); 487 } 488 489 // Avoid infinite regress 490 Scavenged[SI].Reg = Reg; 491 492 // If the target knows how to save/restore the register, let it do so; 493 // otherwise, use the emergency stack spill slot. 494 if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) { 495 // Spill the scavenged register before \p Before. 496 int FI = Scavenged[SI].FrameIndex; 497 if (FI < FIB || FI >= FIE) { 498 report_fatal_error(Twine("Error while trying to spill ") + 499 TRI->getName(Reg) + " from class " + 500 TRI->getRegClassName(&RC) + 501 ": Cannot scavenge register without an emergency " 502 "spill slot!"); 503 } 504 TII->storeRegToStackSlot(*MBB, Before, Reg, true, FI, &RC, TRI); 505 MachineBasicBlock::iterator II = std::prev(Before); 506 507 unsigned FIOperandNum = getFrameIndexOperandNum(*II); 508 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 509 510 // Restore the scavenged register before its use (or first terminator). 511 TII->loadRegFromStackSlot(*MBB, UseMI, Reg, FI, &RC, TRI); 512 II = std::prev(UseMI); 513 514 FIOperandNum = getFrameIndexOperandNum(*II); 515 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 516 } 517 return Scavenged[SI]; 518 } 519 520 Register RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 521 MachineBasicBlock::iterator I, 522 int SPAdj, bool AllowSpill) { 523 MachineInstr &MI = *I; 524 const MachineFunction &MF = *MI.getMF(); 525 // Consider all allocatable registers in the register class initially 526 BitVector Candidates = TRI->getAllocatableSet(MF, RC); 527 528 // Exclude all the registers being used by the instruction. 529 for (const MachineOperand &MO : MI.operands()) { 530 if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) && 531 !Register::isVirtualRegister(MO.getReg())) 532 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 533 Candidates.reset(*AI); 534 } 535 536 // If we have already scavenged some registers, remove them from the 537 // candidates. If we end up recursively calling eliminateFrameIndex, we don't 538 // want to be clobbering previously scavenged registers or their associated 539 // stack slots. 540 for (ScavengedInfo &SI : Scavenged) { 541 if (SI.Reg) { 542 if (isRegUsed(SI.Reg)) { 543 LLVM_DEBUG( 544 dbgs() << "Removing " << printReg(SI.Reg, TRI) << 545 " from scavenging candidates since it was already scavenged\n"); 546 for (MCRegAliasIterator AI(SI.Reg, TRI, true); AI.isValid(); ++AI) 547 Candidates.reset(*AI); 548 } 549 } 550 } 551 552 // Try to find a register that's unused if there is one, as then we won't 553 // have to spill. 554 BitVector Available = getRegsAvailable(RC); 555 Available &= Candidates; 556 if (Available.any()) 557 Candidates = Available; 558 559 // Find the register whose use is furthest away. 560 MachineBasicBlock::iterator UseMI; 561 Register SReg = findSurvivorReg(I, Candidates, 25, UseMI); 562 563 // If we found an unused register there is no reason to spill it. 564 if (!isRegUsed(SReg)) { 565 LLVM_DEBUG(dbgs() << "Scavenged register: " << printReg(SReg, TRI) << "\n"); 566 return SReg; 567 } 568 569 if (!AllowSpill) 570 return 0; 571 572 #ifndef NDEBUG 573 for (ScavengedInfo &SI : Scavenged) { 574 assert(SI.Reg != SReg && "scavenged a previously scavenged register"); 575 } 576 #endif 577 578 ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI); 579 Scavenged.Restore = &*std::prev(UseMI); 580 581 LLVM_DEBUG(dbgs() << "Scavenged register (with spill): " 582 << printReg(SReg, TRI) << "\n"); 583 584 return SReg; 585 } 586 587 Register RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC, 588 MachineBasicBlock::iterator To, 589 bool RestoreAfter, int SPAdj, 590 bool AllowSpill) { 591 const MachineBasicBlock &MBB = *To->getParent(); 592 const MachineFunction &MF = *MBB.getParent(); 593 594 // Find the register whose use is furthest away. 595 MachineBasicBlock::iterator UseMI; 596 ArrayRef<MCPhysReg> AllocationOrder = RC.getRawAllocationOrder(MF); 597 std::pair<MCPhysReg, MachineBasicBlock::iterator> P = 598 findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, AllocationOrder, 599 RestoreAfter); 600 MCPhysReg Reg = P.first; 601 MachineBasicBlock::iterator SpillBefore = P.second; 602 // Found an available register? 603 if (Reg != 0 && SpillBefore == MBB.end()) { 604 LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI) 605 << '\n'); 606 return Reg; 607 } 608 609 if (!AllowSpill) 610 return 0; 611 612 assert(Reg != 0 && "No register left to scavenge!"); 613 614 MachineBasicBlock::iterator ReloadAfter = 615 RestoreAfter ? std::next(MBBI) : MBBI; 616 MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter); 617 if (ReloadBefore != MBB.end()) 618 LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n'); 619 ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore); 620 Scavenged.Restore = &*std::prev(SpillBefore); 621 LiveUnits.removeReg(Reg); 622 LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI) 623 << " until " << *SpillBefore); 624 return Reg; 625 } 626 627 /// Allocate a register for the virtual register \p VReg. The last use of 628 /// \p VReg is around the current position of the register scavenger \p RS. 629 /// \p ReserveAfter controls whether the scavenged register needs to be reserved 630 /// after the current instruction, otherwise it will only be reserved before the 631 /// current instruction. 632 static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS, 633 Register VReg, bool ReserveAfter) { 634 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 635 #ifndef NDEBUG 636 // Verify that all definitions and uses are in the same basic block. 637 const MachineBasicBlock *CommonMBB = nullptr; 638 // Real definition for the reg, re-definitions are not considered. 639 const MachineInstr *RealDef = nullptr; 640 for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) { 641 MachineBasicBlock *MBB = MO.getParent()->getParent(); 642 if (CommonMBB == nullptr) 643 CommonMBB = MBB; 644 assert(MBB == CommonMBB && "All defs+uses must be in the same basic block"); 645 if (MO.isDef()) { 646 const MachineInstr &MI = *MO.getParent(); 647 if (!MI.readsRegister(VReg, &TRI)) { 648 assert((!RealDef || RealDef == &MI) && 649 "Can have at most one definition which is not a redefinition"); 650 RealDef = &MI; 651 } 652 } 653 } 654 assert(RealDef != nullptr && "Must have at least 1 Def"); 655 #endif 656 657 // We should only have one definition of the register. However to accommodate 658 // the requirements of two address code we also allow definitions in 659 // subsequent instructions provided they also read the register. That way 660 // we get a single contiguous lifetime. 661 // 662 // Definitions in MRI.def_begin() are unordered, search for the first. 663 MachineRegisterInfo::def_iterator FirstDef = llvm::find_if( 664 MRI.def_operands(VReg), [VReg, &TRI](const MachineOperand &MO) { 665 return !MO.getParent()->readsRegister(VReg, &TRI); 666 }); 667 assert(FirstDef != MRI.def_end() && 668 "Must have one definition that does not redefine vreg"); 669 MachineInstr &DefMI = *FirstDef->getParent(); 670 671 // The register scavenger will report a free register inserting an emergency 672 // spill/reload if necessary. 673 int SPAdj = 0; 674 const TargetRegisterClass &RC = *MRI.getRegClass(VReg); 675 Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(), 676 ReserveAfter, SPAdj); 677 MRI.replaceRegWith(VReg, SReg); 678 ++NumScavengedRegs; 679 return SReg; 680 } 681 682 /// Allocate (scavenge) vregs inside a single basic block. 683 /// Returns true if the target spill callback created new vregs and a 2nd pass 684 /// is necessary. 685 static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI, 686 RegScavenger &RS, 687 MachineBasicBlock &MBB) { 688 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 689 RS.enterBasicBlockEnd(MBB); 690 691 unsigned InitialNumVirtRegs = MRI.getNumVirtRegs(); 692 bool NextInstructionReadsVReg = false; 693 for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) { 694 --I; 695 // Move RegScavenger to the position between *I and *std::next(I). 696 RS.backward(I); 697 698 // Look for unassigned vregs in the uses of *std::next(I). 699 if (NextInstructionReadsVReg) { 700 MachineBasicBlock::iterator N = std::next(I); 701 const MachineInstr &NMI = *N; 702 for (const MachineOperand &MO : NMI.operands()) { 703 if (!MO.isReg()) 704 continue; 705 Register Reg = MO.getReg(); 706 // We only care about virtual registers and ignore virtual registers 707 // created by the target callbacks in the process (those will be handled 708 // in a scavenging round). 709 if (!Register::isVirtualRegister(Reg) || 710 Register::virtReg2Index(Reg) >= InitialNumVirtRegs) 711 continue; 712 if (!MO.readsReg()) 713 continue; 714 715 Register SReg = scavengeVReg(MRI, RS, Reg, true); 716 N->addRegisterKilled(SReg, &TRI, false); 717 RS.setRegUsed(SReg); 718 } 719 } 720 721 // Look for unassigned vregs in the defs of *I. 722 NextInstructionReadsVReg = false; 723 const MachineInstr &MI = *I; 724 for (const MachineOperand &MO : MI.operands()) { 725 if (!MO.isReg()) 726 continue; 727 Register Reg = MO.getReg(); 728 // Only vregs, no newly created vregs (see above). 729 if (!Register::isVirtualRegister(Reg) || 730 Register::virtReg2Index(Reg) >= InitialNumVirtRegs) 731 continue; 732 // We have to look at all operands anyway so we can precalculate here 733 // whether there is a reading operand. This allows use to skip the use 734 // step in the next iteration if there was none. 735 assert(!MO.isInternalRead() && "Cannot assign inside bundles"); 736 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses"); 737 if (MO.readsReg()) { 738 NextInstructionReadsVReg = true; 739 } 740 if (MO.isDef()) { 741 Register SReg = scavengeVReg(MRI, RS, Reg, false); 742 I->addRegisterDead(SReg, &TRI, false); 743 } 744 } 745 } 746 #ifndef NDEBUG 747 for (const MachineOperand &MO : MBB.front().operands()) { 748 if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg())) 749 continue; 750 assert(!MO.isInternalRead() && "Cannot assign inside bundles"); 751 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses"); 752 assert(!MO.readsReg() && "Vreg use in first instruction not allowed"); 753 } 754 #endif 755 756 return MRI.getNumVirtRegs() != InitialNumVirtRegs; 757 } 758 759 void llvm::scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS) { 760 // FIXME: Iterating over the instruction stream is unnecessary. We can simply 761 // iterate over the vreg use list, which at this point only contains machine 762 // operands for which eliminateFrameIndex need a new scratch reg. 763 MachineRegisterInfo &MRI = MF.getRegInfo(); 764 // Shortcut. 765 if (MRI.getNumVirtRegs() == 0) { 766 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); 767 return; 768 } 769 770 // Run through the instructions and find any virtual registers. 771 for (MachineBasicBlock &MBB : MF) { 772 if (MBB.empty()) 773 continue; 774 775 bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB); 776 if (Again) { 777 LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block " 778 << MBB.getName() << '\n'); 779 Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB); 780 // The target required a 2nd run (because it created new vregs while 781 // spilling). Refuse to do another pass to keep compiletime in check. 782 if (Again) 783 report_fatal_error("Incomplete scavenging after 2nd pass"); 784 } 785 } 786 787 MRI.clearVirtRegs(); 788 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); 789 } 790 791 namespace { 792 793 /// This class runs register scavenging independ of the PrologEpilogInserter. 794 /// This is used in for testing. 795 class ScavengerTest : public MachineFunctionPass { 796 public: 797 static char ID; 798 799 ScavengerTest() : MachineFunctionPass(ID) {} 800 801 bool runOnMachineFunction(MachineFunction &MF) override { 802 const TargetSubtargetInfo &STI = MF.getSubtarget(); 803 const TargetFrameLowering &TFL = *STI.getFrameLowering(); 804 805 RegScavenger RS; 806 // Let's hope that calling those outside of PrologEpilogueInserter works 807 // well enough to initialize the scavenger with some emergency spillslots 808 // for the target. 809 BitVector SavedRegs; 810 TFL.determineCalleeSaves(MF, SavedRegs, &RS); 811 TFL.processFunctionBeforeFrameFinalized(MF, &RS); 812 813 // Let's scavenge the current function 814 scavengeFrameVirtualRegs(MF, RS); 815 return true; 816 } 817 }; 818 819 } // end anonymous namespace 820 821 char ScavengerTest::ID; 822 823 INITIALIZE_PASS(ScavengerTest, "scavenger-test", 824 "Scavenge virtual registers inside basic blocks", false, false) 825