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 std::string Msg = std::string("Error while trying to spill ") + 499 TRI->getName(Reg) + " from class " + TRI->getRegClassName(&RC) + 500 ": Cannot scavenge register without an emergency spill slot!"; 501 report_fatal_error(Msg.c_str()); 502 } 503 TII->storeRegToStackSlot(*MBB, Before, Reg, true, Scavenged[SI].FrameIndex, 504 &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, Scavenged[SI].FrameIndex, 512 &RC, TRI); 513 II = std::prev(UseMI); 514 515 FIOperandNum = getFrameIndexOperandNum(*II); 516 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 517 } 518 return Scavenged[SI]; 519 } 520 521 Register RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 522 MachineBasicBlock::iterator I, 523 int SPAdj, bool AllowSpill) { 524 MachineInstr &MI = *I; 525 const MachineFunction &MF = *MI.getMF(); 526 // Consider all allocatable registers in the register class initially 527 BitVector Candidates = TRI->getAllocatableSet(MF, RC); 528 529 // Exclude all the registers being used by the instruction. 530 for (const MachineOperand &MO : MI.operands()) { 531 if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) && 532 !Register::isVirtualRegister(MO.getReg())) 533 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 534 Candidates.reset(*AI); 535 } 536 537 // Try to find a register that's unused if there is one, as then we won't 538 // have to spill. 539 BitVector Available = getRegsAvailable(RC); 540 Available &= Candidates; 541 if (Available.any()) 542 Candidates = Available; 543 544 // Find the register whose use is furthest away. 545 MachineBasicBlock::iterator UseMI; 546 Register SReg = findSurvivorReg(I, Candidates, 25, UseMI); 547 548 // If we found an unused register there is no reason to spill it. 549 if (!isRegUsed(SReg)) { 550 LLVM_DEBUG(dbgs() << "Scavenged register: " << printReg(SReg, TRI) << "\n"); 551 return SReg; 552 } 553 554 if (!AllowSpill) 555 return 0; 556 557 ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI); 558 Scavenged.Restore = &*std::prev(UseMI); 559 560 LLVM_DEBUG(dbgs() << "Scavenged register (with spill): " 561 << printReg(SReg, TRI) << "\n"); 562 563 return SReg; 564 } 565 566 Register RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC, 567 MachineBasicBlock::iterator To, 568 bool RestoreAfter, int SPAdj, 569 bool AllowSpill) { 570 const MachineBasicBlock &MBB = *To->getParent(); 571 const MachineFunction &MF = *MBB.getParent(); 572 573 // Find the register whose use is furthest away. 574 MachineBasicBlock::iterator UseMI; 575 ArrayRef<MCPhysReg> AllocationOrder = RC.getRawAllocationOrder(MF); 576 std::pair<MCPhysReg, MachineBasicBlock::iterator> P = 577 findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, AllocationOrder, 578 RestoreAfter); 579 MCPhysReg Reg = P.first; 580 MachineBasicBlock::iterator SpillBefore = P.second; 581 // Found an available register? 582 if (Reg != 0 && SpillBefore == MBB.end()) { 583 LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI) 584 << '\n'); 585 return Reg; 586 } 587 588 if (!AllowSpill) 589 return 0; 590 591 assert(Reg != 0 && "No register left to scavenge!"); 592 593 MachineBasicBlock::iterator ReloadAfter = 594 RestoreAfter ? std::next(MBBI) : MBBI; 595 MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter); 596 if (ReloadBefore != MBB.end()) 597 LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n'); 598 ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore); 599 Scavenged.Restore = &*std::prev(SpillBefore); 600 LiveUnits.removeReg(Reg); 601 LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI) 602 << " until " << *SpillBefore); 603 return Reg; 604 } 605 606 /// Allocate a register for the virtual register \p VReg. The last use of 607 /// \p VReg is around the current position of the register scavenger \p RS. 608 /// \p ReserveAfter controls whether the scavenged register needs to be reserved 609 /// after the current instruction, otherwise it will only be reserved before the 610 /// current instruction. 611 static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS, 612 Register VReg, bool ReserveAfter) { 613 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 614 #ifndef NDEBUG 615 // Verify that all definitions and uses are in the same basic block. 616 const MachineBasicBlock *CommonMBB = nullptr; 617 // Real definition for the reg, re-definitions are not considered. 618 const MachineInstr *RealDef = nullptr; 619 for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) { 620 MachineBasicBlock *MBB = MO.getParent()->getParent(); 621 if (CommonMBB == nullptr) 622 CommonMBB = MBB; 623 assert(MBB == CommonMBB && "All defs+uses must be in the same basic block"); 624 if (MO.isDef()) { 625 const MachineInstr &MI = *MO.getParent(); 626 if (!MI.readsRegister(VReg, &TRI)) { 627 assert((!RealDef || RealDef == &MI) && 628 "Can have at most one definition which is not a redefinition"); 629 RealDef = &MI; 630 } 631 } 632 } 633 assert(RealDef != nullptr && "Must have at least 1 Def"); 634 #endif 635 636 // We should only have one definition of the register. However to accommodate 637 // the requirements of two address code we also allow definitions in 638 // subsequent instructions provided they also read the register. That way 639 // we get a single contiguous lifetime. 640 // 641 // Definitions in MRI.def_begin() are unordered, search for the first. 642 MachineRegisterInfo::def_iterator FirstDef = llvm::find_if( 643 MRI.def_operands(VReg), [VReg, &TRI](const MachineOperand &MO) { 644 return !MO.getParent()->readsRegister(VReg, &TRI); 645 }); 646 assert(FirstDef != MRI.def_end() && 647 "Must have one definition that does not redefine vreg"); 648 MachineInstr &DefMI = *FirstDef->getParent(); 649 650 // The register scavenger will report a free register inserting an emergency 651 // spill/reload if necessary. 652 int SPAdj = 0; 653 const TargetRegisterClass &RC = *MRI.getRegClass(VReg); 654 Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(), 655 ReserveAfter, SPAdj); 656 MRI.replaceRegWith(VReg, SReg); 657 ++NumScavengedRegs; 658 return SReg; 659 } 660 661 /// Allocate (scavenge) vregs inside a single basic block. 662 /// Returns true if the target spill callback created new vregs and a 2nd pass 663 /// is necessary. 664 static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI, 665 RegScavenger &RS, 666 MachineBasicBlock &MBB) { 667 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 668 RS.enterBasicBlockEnd(MBB); 669 670 unsigned InitialNumVirtRegs = MRI.getNumVirtRegs(); 671 bool NextInstructionReadsVReg = false; 672 for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) { 673 --I; 674 // Move RegScavenger to the position between *I and *std::next(I). 675 RS.backward(I); 676 677 // Look for unassigned vregs in the uses of *std::next(I). 678 if (NextInstructionReadsVReg) { 679 MachineBasicBlock::iterator N = std::next(I); 680 const MachineInstr &NMI = *N; 681 for (const MachineOperand &MO : NMI.operands()) { 682 if (!MO.isReg()) 683 continue; 684 Register Reg = MO.getReg(); 685 // We only care about virtual registers and ignore virtual registers 686 // created by the target callbacks in the process (those will be handled 687 // in a scavenging round). 688 if (!Register::isVirtualRegister(Reg) || 689 Register::virtReg2Index(Reg) >= InitialNumVirtRegs) 690 continue; 691 if (!MO.readsReg()) 692 continue; 693 694 Register SReg = scavengeVReg(MRI, RS, Reg, true); 695 N->addRegisterKilled(SReg, &TRI, false); 696 RS.setRegUsed(SReg); 697 } 698 } 699 700 // Look for unassigned vregs in the defs of *I. 701 NextInstructionReadsVReg = false; 702 const MachineInstr &MI = *I; 703 for (const MachineOperand &MO : MI.operands()) { 704 if (!MO.isReg()) 705 continue; 706 Register Reg = MO.getReg(); 707 // Only vregs, no newly created vregs (see above). 708 if (!Register::isVirtualRegister(Reg) || 709 Register::virtReg2Index(Reg) >= InitialNumVirtRegs) 710 continue; 711 // We have to look at all operands anyway so we can precalculate here 712 // whether there is a reading operand. This allows use to skip the use 713 // step in the next iteration if there was none. 714 assert(!MO.isInternalRead() && "Cannot assign inside bundles"); 715 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses"); 716 if (MO.readsReg()) { 717 NextInstructionReadsVReg = true; 718 } 719 if (MO.isDef()) { 720 Register SReg = scavengeVReg(MRI, RS, Reg, false); 721 I->addRegisterDead(SReg, &TRI, false); 722 } 723 } 724 } 725 #ifndef NDEBUG 726 for (const MachineOperand &MO : MBB.front().operands()) { 727 if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg())) 728 continue; 729 assert(!MO.isInternalRead() && "Cannot assign inside bundles"); 730 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses"); 731 assert(!MO.readsReg() && "Vreg use in first instruction not allowed"); 732 } 733 #endif 734 735 return MRI.getNumVirtRegs() != InitialNumVirtRegs; 736 } 737 738 void llvm::scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS) { 739 // FIXME: Iterating over the instruction stream is unnecessary. We can simply 740 // iterate over the vreg use list, which at this point only contains machine 741 // operands for which eliminateFrameIndex need a new scratch reg. 742 MachineRegisterInfo &MRI = MF.getRegInfo(); 743 // Shortcut. 744 if (MRI.getNumVirtRegs() == 0) { 745 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); 746 return; 747 } 748 749 // Run through the instructions and find any virtual registers. 750 for (MachineBasicBlock &MBB : MF) { 751 if (MBB.empty()) 752 continue; 753 754 bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB); 755 if (Again) { 756 LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block " 757 << MBB.getName() << '\n'); 758 Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB); 759 // The target required a 2nd run (because it created new vregs while 760 // spilling). Refuse to do another pass to keep compiletime in check. 761 if (Again) 762 report_fatal_error("Incomplete scavenging after 2nd pass"); 763 } 764 } 765 766 MRI.clearVirtRegs(); 767 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); 768 } 769 770 namespace { 771 772 /// This class runs register scavenging independ of the PrologEpilogInserter. 773 /// This is used in for testing. 774 class ScavengerTest : public MachineFunctionPass { 775 public: 776 static char ID; 777 778 ScavengerTest() : MachineFunctionPass(ID) {} 779 780 bool runOnMachineFunction(MachineFunction &MF) override { 781 const TargetSubtargetInfo &STI = MF.getSubtarget(); 782 const TargetFrameLowering &TFL = *STI.getFrameLowering(); 783 784 RegScavenger RS; 785 // Let's hope that calling those outside of PrologEpilogueInserter works 786 // well enough to initialize the scavenger with some emergency spillslots 787 // for the target. 788 BitVector SavedRegs; 789 TFL.determineCalleeSaves(MF, SavedRegs, &RS); 790 TFL.processFunctionBeforeFrameFinalized(MF, &RS); 791 792 // Let's scavenge the current function 793 scavengeFrameVirtualRegs(MF, RS); 794 return true; 795 } 796 }; 797 798 } // end anonymous namespace 799 800 char ScavengerTest::ID; 801 802 INITIALIZE_PASS(ScavengerTest, "scavenger-test", 803 "Scavenge virtual registers inside basic blocks", false, false) 804