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