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