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 this->MBB = &MBB; 63 64 for (ScavengedInfo &SI : Scavenged) { 65 SI.Reg = 0; 66 SI.Restore = nullptr; 67 } 68 } 69 70 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) { 71 init(MBB); 72 LiveUnits.addLiveIns(MBB); 73 MBBI = MBB.begin(); 74 } 75 76 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) { 77 init(MBB); 78 LiveUnits.addLiveOuts(MBB); 79 MBBI = MBB.end(); 80 } 81 82 void RegScavenger::backward() { 83 const MachineInstr &MI = *--MBBI; 84 LiveUnits.stepBackward(MI); 85 86 // Expire scavenge spill frameindex uses. 87 for (ScavengedInfo &I : Scavenged) { 88 if (I.Restore == &MI) { 89 I.Reg = 0; 90 I.Restore = nullptr; 91 } 92 } 93 } 94 95 bool RegScavenger::isRegUsed(Register Reg, bool includeReserved) const { 96 if (isReserved(Reg)) 97 return includeReserved; 98 return !LiveUnits.available(Reg); 99 } 100 101 Register RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 102 for (Register Reg : *RC) { 103 if (!isRegUsed(Reg)) { 104 LLVM_DEBUG(dbgs() << "Scavenger found unused reg: " << printReg(Reg, TRI) 105 << "\n"); 106 return Reg; 107 } 108 } 109 return 0; 110 } 111 112 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 113 BitVector Mask(TRI->getNumRegs()); 114 for (Register Reg : *RC) 115 if (!isRegUsed(Reg)) 116 Mask.set(Reg); 117 return Mask; 118 } 119 120 /// Given the bitvector \p Available of free register units at position 121 /// \p From. Search backwards to find a register that is part of \p 122 /// Candidates and not used/clobbered until the point \p To. If there is 123 /// multiple candidates continue searching and pick the one that is not used/ 124 /// clobbered for the longest time. 125 /// Returns the register and the earliest position we know it to be free or 126 /// the position MBB.end() if no register is available. 127 static std::pair<MCPhysReg, MachineBasicBlock::iterator> 128 findSurvivorBackwards(const MachineRegisterInfo &MRI, 129 MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, 130 const LiveRegUnits &LiveOut, ArrayRef<MCPhysReg> AllocationOrder, 131 bool RestoreAfter) { 132 bool FoundTo = false; 133 MCPhysReg Survivor = 0; 134 MachineBasicBlock::iterator Pos; 135 MachineBasicBlock &MBB = *From->getParent(); 136 unsigned InstrLimit = 25; 137 unsigned InstrCountDown = InstrLimit; 138 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 139 LiveRegUnits Used(TRI); 140 141 assert(From->getParent() == To->getParent() && 142 "Target instruction is in other than current basic block, use " 143 "enterBasicBlockEnd first"); 144 145 for (MachineBasicBlock::iterator I = From;; --I) { 146 const MachineInstr &MI = *I; 147 148 Used.accumulate(MI); 149 150 if (I == To) { 151 // See if one of the registers in RC wasn't used so far. 152 for (MCPhysReg Reg : AllocationOrder) { 153 if (!MRI.isReserved(Reg) && Used.available(Reg) && 154 LiveOut.available(Reg)) 155 return std::make_pair(Reg, MBB.end()); 156 } 157 // Otherwise we will continue up to InstrLimit instructions to find 158 // the register which is not defined/used for the longest time. 159 FoundTo = true; 160 Pos = To; 161 // Note: It was fine so far to start our search at From, however now that 162 // we have to spill, and can only place the restore after From then 163 // add the regs used/defed by std::next(From) to the set. 164 if (RestoreAfter) 165 Used.accumulate(*std::next(From)); 166 } 167 if (FoundTo) { 168 // Don't search to FrameSetup instructions if we were searching from 169 // Non-FrameSetup instructions. Otherwise, the spill position may point 170 // before FrameSetup instructions. 171 if (!From->getFlag(MachineInstr::FrameSetup) && 172 MI.getFlag(MachineInstr::FrameSetup)) 173 break; 174 175 if (Survivor == 0 || !Used.available(Survivor)) { 176 MCPhysReg AvilableReg = 0; 177 for (MCPhysReg Reg : AllocationOrder) { 178 if (!MRI.isReserved(Reg) && Used.available(Reg)) { 179 AvilableReg = Reg; 180 break; 181 } 182 } 183 if (AvilableReg == 0) 184 break; 185 Survivor = AvilableReg; 186 } 187 if (--InstrCountDown == 0) 188 break; 189 190 // Keep searching when we find a vreg since the spilled register will 191 // be usefull for this other vreg as well later. 192 bool FoundVReg = false; 193 for (const MachineOperand &MO : MI.operands()) { 194 if (MO.isReg() && MO.getReg().isVirtual()) { 195 FoundVReg = true; 196 break; 197 } 198 } 199 if (FoundVReg) { 200 InstrCountDown = InstrLimit; 201 Pos = I; 202 } 203 if (I == MBB.begin()) 204 break; 205 } 206 assert(I != MBB.begin() && "Did not find target instruction while " 207 "iterating backwards"); 208 } 209 210 return std::make_pair(Survivor, Pos); 211 } 212 213 static unsigned getFrameIndexOperandNum(MachineInstr &MI) { 214 unsigned i = 0; 215 while (!MI.getOperand(i).isFI()) { 216 ++i; 217 assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!"); 218 } 219 return i; 220 } 221 222 RegScavenger::ScavengedInfo & 223 RegScavenger::spill(Register Reg, const TargetRegisterClass &RC, int SPAdj, 224 MachineBasicBlock::iterator Before, 225 MachineBasicBlock::iterator &UseMI) { 226 // Find an available scavenging slot with size and alignment matching 227 // the requirements of the class RC. 228 const MachineFunction &MF = *Before->getMF(); 229 const MachineFrameInfo &MFI = MF.getFrameInfo(); 230 unsigned NeedSize = TRI->getSpillSize(RC); 231 Align NeedAlign = TRI->getSpillAlign(RC); 232 233 unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max(); 234 int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd(); 235 for (unsigned I = 0; I < Scavenged.size(); ++I) { 236 if (Scavenged[I].Reg != 0) 237 continue; 238 // Verify that this slot is valid for this register. 239 int FI = Scavenged[I].FrameIndex; 240 if (FI < FIB || FI >= FIE) 241 continue; 242 unsigned S = MFI.getObjectSize(FI); 243 Align A = MFI.getObjectAlign(FI); 244 if (NeedSize > S || NeedAlign > A) 245 continue; 246 // Avoid wasting slots with large size and/or large alignment. Pick one 247 // that is the best fit for this register class (in street metric). 248 // Picking a larger slot than necessary could happen if a slot for a 249 // larger register is reserved before a slot for a smaller one. When 250 // trying to spill a smaller register, the large slot would be found 251 // first, thus making it impossible to spill the larger register later. 252 unsigned D = (S - NeedSize) + (A.value() - NeedAlign.value()); 253 if (D < Diff) { 254 SI = I; 255 Diff = D; 256 } 257 } 258 259 if (SI == Scavenged.size()) { 260 // We need to scavenge a register but have no spill slot, the target 261 // must know how to do it (if not, we'll assert below). 262 Scavenged.push_back(ScavengedInfo(FIE)); 263 } 264 265 // Avoid infinite regress 266 Scavenged[SI].Reg = Reg; 267 268 // If the target knows how to save/restore the register, let it do so; 269 // otherwise, use the emergency stack spill slot. 270 if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) { 271 // Spill the scavenged register before \p Before. 272 int FI = Scavenged[SI].FrameIndex; 273 if (FI < FIB || FI >= FIE) { 274 report_fatal_error(Twine("Error while trying to spill ") + 275 TRI->getName(Reg) + " from class " + 276 TRI->getRegClassName(&RC) + 277 ": Cannot scavenge register without an emergency " 278 "spill slot!"); 279 } 280 TII->storeRegToStackSlot(*MBB, Before, Reg, true, FI, &RC, TRI, Register()); 281 MachineBasicBlock::iterator II = std::prev(Before); 282 283 unsigned FIOperandNum = getFrameIndexOperandNum(*II); 284 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 285 286 // Restore the scavenged register before its use (or first terminator). 287 TII->loadRegFromStackSlot(*MBB, UseMI, Reg, FI, &RC, TRI, Register()); 288 II = std::prev(UseMI); 289 290 FIOperandNum = getFrameIndexOperandNum(*II); 291 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 292 } 293 return Scavenged[SI]; 294 } 295 296 Register RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC, 297 MachineBasicBlock::iterator To, 298 bool RestoreAfter, int SPAdj, 299 bool AllowSpill) { 300 const MachineBasicBlock &MBB = *To->getParent(); 301 const MachineFunction &MF = *MBB.getParent(); 302 303 // Find the register whose use is furthest away. 304 MachineBasicBlock::iterator UseMI; 305 ArrayRef<MCPhysReg> AllocationOrder = RC.getRawAllocationOrder(MF); 306 std::pair<MCPhysReg, MachineBasicBlock::iterator> P = findSurvivorBackwards( 307 *MRI, std::prev(MBBI), To, LiveUnits, AllocationOrder, RestoreAfter); 308 MCPhysReg Reg = P.first; 309 MachineBasicBlock::iterator SpillBefore = P.second; 310 // Found an available register? 311 if (Reg != 0 && SpillBefore == MBB.end()) { 312 LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI) 313 << '\n'); 314 return Reg; 315 } 316 317 if (!AllowSpill) 318 return 0; 319 320 assert(Reg != 0 && "No register left to scavenge!"); 321 322 MachineBasicBlock::iterator ReloadBefore = 323 RestoreAfter ? std::next(MBBI) : MBBI; 324 if (ReloadBefore != MBB.end()) 325 LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n'); 326 ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore); 327 Scavenged.Restore = &*std::prev(SpillBefore); 328 LiveUnits.removeReg(Reg); 329 LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI) 330 << " until " << *SpillBefore); 331 return Reg; 332 } 333 334 /// Allocate a register for the virtual register \p VReg. The last use of 335 /// \p VReg is around the current position of the register scavenger \p RS. 336 /// \p ReserveAfter controls whether the scavenged register needs to be reserved 337 /// after the current instruction, otherwise it will only be reserved before the 338 /// current instruction. 339 static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS, 340 Register VReg, bool ReserveAfter) { 341 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 342 #ifndef NDEBUG 343 // Verify that all definitions and uses are in the same basic block. 344 const MachineBasicBlock *CommonMBB = nullptr; 345 // Real definition for the reg, re-definitions are not considered. 346 const MachineInstr *RealDef = nullptr; 347 for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) { 348 MachineBasicBlock *MBB = MO.getParent()->getParent(); 349 if (CommonMBB == nullptr) 350 CommonMBB = MBB; 351 assert(MBB == CommonMBB && "All defs+uses must be in the same basic block"); 352 if (MO.isDef()) { 353 const MachineInstr &MI = *MO.getParent(); 354 if (!MI.readsRegister(VReg, &TRI)) { 355 assert((!RealDef || RealDef == &MI) && 356 "Can have at most one definition which is not a redefinition"); 357 RealDef = &MI; 358 } 359 } 360 } 361 assert(RealDef != nullptr && "Must have at least 1 Def"); 362 #endif 363 364 // We should only have one definition of the register. However to accommodate 365 // the requirements of two address code we also allow definitions in 366 // subsequent instructions provided they also read the register. That way 367 // we get a single contiguous lifetime. 368 // 369 // Definitions in MRI.def_begin() are unordered, search for the first. 370 MachineRegisterInfo::def_iterator FirstDef = llvm::find_if( 371 MRI.def_operands(VReg), [VReg, &TRI](const MachineOperand &MO) { 372 return !MO.getParent()->readsRegister(VReg, &TRI); 373 }); 374 assert(FirstDef != MRI.def_end() && 375 "Must have one definition that does not redefine vreg"); 376 MachineInstr &DefMI = *FirstDef->getParent(); 377 378 // The register scavenger will report a free register inserting an emergency 379 // spill/reload if necessary. 380 int SPAdj = 0; 381 const TargetRegisterClass &RC = *MRI.getRegClass(VReg); 382 Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(), 383 ReserveAfter, SPAdj); 384 MRI.replaceRegWith(VReg, SReg); 385 ++NumScavengedRegs; 386 return SReg; 387 } 388 389 /// Allocate (scavenge) vregs inside a single basic block. 390 /// Returns true if the target spill callback created new vregs and a 2nd pass 391 /// is necessary. 392 static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI, 393 RegScavenger &RS, 394 MachineBasicBlock &MBB) { 395 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 396 RS.enterBasicBlockEnd(MBB); 397 398 unsigned InitialNumVirtRegs = MRI.getNumVirtRegs(); 399 bool NextInstructionReadsVReg = false; 400 for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) { 401 // Move RegScavenger to the position between *std::prev(I) and *I. 402 RS.backward(I); 403 --I; 404 405 // Look for unassigned vregs in the uses of *std::next(I). 406 if (NextInstructionReadsVReg) { 407 MachineBasicBlock::iterator N = std::next(I); 408 const MachineInstr &NMI = *N; 409 for (const MachineOperand &MO : NMI.operands()) { 410 if (!MO.isReg()) 411 continue; 412 Register Reg = MO.getReg(); 413 // We only care about virtual registers and ignore virtual registers 414 // created by the target callbacks in the process (those will be handled 415 // in a scavenging round). 416 if (!Reg.isVirtual() || 417 Register::virtReg2Index(Reg) >= InitialNumVirtRegs) 418 continue; 419 if (!MO.readsReg()) 420 continue; 421 422 Register SReg = scavengeVReg(MRI, RS, Reg, true); 423 N->addRegisterKilled(SReg, &TRI, false); 424 RS.setRegUsed(SReg); 425 } 426 } 427 428 // Look for unassigned vregs in the defs of *I. 429 NextInstructionReadsVReg = false; 430 const MachineInstr &MI = *I; 431 for (const MachineOperand &MO : MI.operands()) { 432 if (!MO.isReg()) 433 continue; 434 Register Reg = MO.getReg(); 435 // Only vregs, no newly created vregs (see above). 436 if (!Reg.isVirtual() || 437 Register::virtReg2Index(Reg) >= InitialNumVirtRegs) 438 continue; 439 // We have to look at all operands anyway so we can precalculate here 440 // whether there is a reading operand. This allows use to skip the use 441 // step in the next iteration if there was none. 442 assert(!MO.isInternalRead() && "Cannot assign inside bundles"); 443 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses"); 444 if (MO.readsReg()) { 445 NextInstructionReadsVReg = true; 446 } 447 if (MO.isDef()) { 448 Register SReg = scavengeVReg(MRI, RS, Reg, false); 449 I->addRegisterDead(SReg, &TRI, false); 450 } 451 } 452 } 453 #ifndef NDEBUG 454 for (const MachineOperand &MO : MBB.front().operands()) { 455 if (!MO.isReg() || !MO.getReg().isVirtual()) 456 continue; 457 assert(!MO.isInternalRead() && "Cannot assign inside bundles"); 458 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses"); 459 assert(!MO.readsReg() && "Vreg use in first instruction not allowed"); 460 } 461 #endif 462 463 return MRI.getNumVirtRegs() != InitialNumVirtRegs; 464 } 465 466 void llvm::scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS) { 467 // FIXME: Iterating over the instruction stream is unnecessary. We can simply 468 // iterate over the vreg use list, which at this point only contains machine 469 // operands for which eliminateFrameIndex need a new scratch reg. 470 MachineRegisterInfo &MRI = MF.getRegInfo(); 471 // Shortcut. 472 if (MRI.getNumVirtRegs() == 0) { 473 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); 474 return; 475 } 476 477 // Run through the instructions and find any virtual registers. 478 for (MachineBasicBlock &MBB : MF) { 479 if (MBB.empty()) 480 continue; 481 482 bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB); 483 if (Again) { 484 LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block " 485 << MBB.getName() << '\n'); 486 Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB); 487 // The target required a 2nd run (because it created new vregs while 488 // spilling). Refuse to do another pass to keep compiletime in check. 489 if (Again) 490 report_fatal_error("Incomplete scavenging after 2nd pass"); 491 } 492 } 493 494 MRI.clearVirtRegs(); 495 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs); 496 } 497 498 namespace { 499 500 /// This class runs register scavenging independ of the PrologEpilogInserter. 501 /// This is used in for testing. 502 class ScavengerTest : public MachineFunctionPass { 503 public: 504 static char ID; 505 506 ScavengerTest() : MachineFunctionPass(ID) {} 507 508 bool runOnMachineFunction(MachineFunction &MF) override { 509 const TargetSubtargetInfo &STI = MF.getSubtarget(); 510 const TargetFrameLowering &TFL = *STI.getFrameLowering(); 511 512 RegScavenger RS; 513 // Let's hope that calling those outside of PrologEpilogueInserter works 514 // well enough to initialize the scavenger with some emergency spillslots 515 // for the target. 516 BitVector SavedRegs; 517 TFL.determineCalleeSaves(MF, SavedRegs, &RS); 518 TFL.processFunctionBeforeFrameFinalized(MF, &RS); 519 520 // Let's scavenge the current function 521 scavengeFrameVirtualRegs(MF, RS); 522 return true; 523 } 524 }; 525 526 } // end anonymous namespace 527 528 char ScavengerTest::ID; 529 530 INITIALIZE_PASS(ScavengerTest, "scavenger-test", 531 "Scavenge virtual registers inside basic blocks", false, false) 532