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