LLVM 17.0.0git
RegisterScavenging.cpp
Go to the documentation of this file.
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
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/Statistic.h"
36#include "llvm/Pass.h"
37#include "llvm/Support/Debug.h"
40#include <cassert>
41#include <iterator>
42#include <limits>
43#include <utility>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "reg-scavenging"
48
49STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
50
52 LiveUnits.addRegMasked(Reg, LaneMask);
53}
54
55void RegScavenger::init(MachineBasicBlock &MBB) {
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
83 init(MBB);
84 LiveUnits.addLiveIns(MBB);
85}
86
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
98void RegScavenger::addRegUnits(BitVector &BV, MCRegister Reg) {
99 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
100 BV.set(*RUI);
101}
102
103void RegScavenger::removeRegUnits(BitVector &BV, MCRegister Reg) {
104 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
105 BV.reset(*RUI);
106}
107
108void 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
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 (!Reg.isPhysical() || 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 if (none_of(TRI->subregs(Reg),
202 [&](MCPhysReg SR) { return isRegUsed(SR); }) &&
203 none_of(TRI->superregs(Reg),
204 [&](MCPhysReg SR) { return isRegUsed(SR); })) {
205 MBB->getParent()->verify(nullptr, "In Register Scavenger");
206 llvm_unreachable("Using an undefined register!");
207 }
208 }
209 } else {
210 assert(MO.isDef());
211#if 0
212 // FIXME: Enable this once we've figured out how to correctly transfer
213 // implicit kills during codegen passes like the coalescer.
214 assert((KillRegs.test(Reg) || isUnused(Reg) ||
215 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
216 "Re-defining a live register!");
217#endif
218 }
219 }
220#endif // NDEBUG
221
222 // Commit the changes.
223 setUnused(KillRegUnits);
224 setUsed(DefRegUnits);
225}
226
228 assert(Tracking && "Must be tracking to determine kills and defs");
229
230 const MachineInstr &MI = *MBBI;
231 LiveUnits.stepBackward(MI);
232
233 // Expire scavenge spill frameindex uses.
234 for (ScavengedInfo &I : Scavenged) {
235 if (I.Restore == &MI) {
236 I.Reg = 0;
237 I.Restore = nullptr;
238 }
239 }
240
241 if (MBBI == MBB->begin()) {
242 MBBI = MachineBasicBlock::iterator(nullptr);
243 Tracking = false;
244 } else
245 --MBBI;
246}
247
248bool RegScavenger::isRegUsed(Register Reg, bool includeReserved) const {
249 if (isReserved(Reg))
250 return includeReserved;
251 return !LiveUnits.available(Reg);
252}
253
255 for (Register Reg : *RC) {
256 if (!isRegUsed(Reg)) {
257 LLVM_DEBUG(dbgs() << "Scavenger found unused reg: " << printReg(Reg, TRI)
258 << "\n");
259 return Reg;
260 }
261 }
262 return 0;
263}
264
266 BitVector Mask(TRI->getNumRegs());
267 for (Register Reg : *RC)
268 if (!isRegUsed(Reg))
269 Mask.set(Reg);
270 return Mask;
271}
272
273Register RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
274 BitVector &Candidates,
276 unsigned InstrLimit,
278 auto FindFirstCandidate = [&]() -> int {
279 for (MCPhysReg Reg : AllocationOrder) {
280 if (Candidates.test(Reg))
281 return Reg;
282 }
283 return -1;
284 };
285
286 int Survivor = FindFirstCandidate();
287 assert(Survivor > 0 && "No candidates for scavenging");
288
290 assert(StartMI != ME && "MI already at terminator");
291 MachineBasicBlock::iterator RestorePointMI = StartMI;
293
294 bool inVirtLiveRange = false;
295 for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
296 if (MI->isDebugOrPseudoInstr()) {
297 ++InstrLimit; // Don't count debug instructions
298 continue;
299 }
300 bool isVirtKillInsn = false;
301 bool isVirtDefInsn = false;
302 // Remove any candidates touched by instruction.
303 for (const MachineOperand &MO : MI->operands()) {
304 if (MO.isRegMask())
305 Candidates.clearBitsNotInMask(MO.getRegMask());
306 if (!MO.isReg() || MO.isUndef() || !MO.getReg())
307 continue;
308 if (MO.getReg().isVirtual()) {
309 if (MO.isDef())
310 isVirtDefInsn = true;
311 else if (MO.isKill())
312 isVirtKillInsn = true;
313 continue;
314 }
315 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
316 Candidates.reset(*AI);
317 }
318 // If we're not in a virtual reg's live range, this is a valid
319 // restore point.
320 if (!inVirtLiveRange) RestorePointMI = MI;
321
322 // Update whether we're in the live range of a virtual register
323 if (isVirtKillInsn) inVirtLiveRange = false;
324 if (isVirtDefInsn) inVirtLiveRange = true;
325
326 // Was our survivor untouched by this instruction?
327 if (Candidates.test(Survivor))
328 continue;
329
330 // All candidates gone?
331 if (Candidates.none())
332 break;
333
334 Survivor = FindFirstCandidate();
335 }
336 // If we ran off the end, that's where we want to restore.
337 if (MI == ME) RestorePointMI = ME;
338 assert(RestorePointMI != StartMI &&
339 "No available scavenger restore location!");
340
341 // We ran out of candidates, so stop the search.
342 UseMI = RestorePointMI;
343 return Survivor;
344}
345
346/// Given the bitvector \p Available of free register units at position
347/// \p From. Search backwards to find a register that is part of \p
348/// Candidates and not used/clobbered until the point \p To. If there is
349/// multiple candidates continue searching and pick the one that is not used/
350/// clobbered for the longest time.
351/// Returns the register and the earliest position we know it to be free or
352/// the position MBB.end() if no register is available.
353static std::pair<MCPhysReg, MachineBasicBlock::iterator>
357 bool RestoreAfter) {
358 bool FoundTo = false;
359 MCPhysReg Survivor = 0;
361 MachineBasicBlock &MBB = *From->getParent();
362 unsigned InstrLimit = 25;
363 unsigned InstrCountDown = InstrLimit;
364 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
365 LiveRegUnits Used(TRI);
366
367 assert(From->getParent() == To->getParent() &&
368 "Target instruction is in other than current basic block, use "
369 "enterBasicBlockEnd first");
370
371 for (MachineBasicBlock::iterator I = From;; --I) {
372 const MachineInstr &MI = *I;
373
374 Used.accumulate(MI);
375
376 if (I == To) {
377 // See if one of the registers in RC wasn't used so far.
378 for (MCPhysReg Reg : AllocationOrder) {
379 if (!MRI.isReserved(Reg) && Used.available(Reg) &&
380 LiveOut.available(Reg))
381 return std::make_pair(Reg, MBB.end());
382 }
383 // Otherwise we will continue up to InstrLimit instructions to find
384 // the register which is not defined/used for the longest time.
385 FoundTo = true;
386 Pos = To;
387 // Note: It was fine so far to start our search at From, however now that
388 // we have to spill, and can only place the restore after From then
389 // add the regs used/defed by std::next(From) to the set.
390 if (RestoreAfter)
391 Used.accumulate(*std::next(From));
392 }
393 if (FoundTo) {
394 // Don't search to FrameSetup instructions if we were searching from
395 // Non-FrameSetup instructions. Otherwise, the spill position may point
396 // before FrameSetup instructions.
397 if (!From->getFlag(MachineInstr::FrameSetup) &&
399 break;
400
401 if (Survivor == 0 || !Used.available(Survivor)) {
402 MCPhysReg AvilableReg = 0;
403 for (MCPhysReg Reg : AllocationOrder) {
404 if (!MRI.isReserved(Reg) && Used.available(Reg)) {
405 AvilableReg = Reg;
406 break;
407 }
408 }
409 if (AvilableReg == 0)
410 break;
411 Survivor = AvilableReg;
412 }
413 if (--InstrCountDown == 0)
414 break;
415
416 // Keep searching when we find a vreg since the spilled register will
417 // be usefull for this other vreg as well later.
418 bool FoundVReg = false;
419 for (const MachineOperand &MO : MI.operands()) {
420 if (MO.isReg() && MO.getReg().isVirtual()) {
421 FoundVReg = true;
422 break;
423 }
424 }
425 if (FoundVReg) {
426 InstrCountDown = InstrLimit;
427 Pos = I;
428 }
429 if (I == MBB.begin())
430 break;
431 }
432 assert(I != MBB.begin() && "Did not find target instruction while "
433 "iterating backwards");
434 }
435
436 return std::make_pair(Survivor, Pos);
437}
438
440 unsigned i = 0;
441 while (!MI.getOperand(i).isFI()) {
442 ++i;
443 assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
444 }
445 return i;
446}
447
448RegScavenger::ScavengedInfo &
449RegScavenger::spill(Register Reg, const TargetRegisterClass &RC, int SPAdj,
452 // Find an available scavenging slot with size and alignment matching
453 // the requirements of the class RC.
454 const MachineFunction &MF = *Before->getMF();
455 const MachineFrameInfo &MFI = MF.getFrameInfo();
456 unsigned NeedSize = TRI->getSpillSize(RC);
457 Align NeedAlign = TRI->getSpillAlign(RC);
458
459 unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max();
460 int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
461 for (unsigned I = 0; I < Scavenged.size(); ++I) {
462 if (Scavenged[I].Reg != 0)
463 continue;
464 // Verify that this slot is valid for this register.
465 int FI = Scavenged[I].FrameIndex;
466 if (FI < FIB || FI >= FIE)
467 continue;
468 unsigned S = MFI.getObjectSize(FI);
469 Align A = MFI.getObjectAlign(FI);
470 if (NeedSize > S || NeedAlign > A)
471 continue;
472 // Avoid wasting slots with large size and/or large alignment. Pick one
473 // that is the best fit for this register class (in street metric).
474 // Picking a larger slot than necessary could happen if a slot for a
475 // larger register is reserved before a slot for a smaller one. When
476 // trying to spill a smaller register, the large slot would be found
477 // first, thus making it impossible to spill the larger register later.
478 unsigned D = (S - NeedSize) + (A.value() - NeedAlign.value());
479 if (D < Diff) {
480 SI = I;
481 Diff = D;
482 }
483 }
484
485 if (SI == Scavenged.size()) {
486 // We need to scavenge a register but have no spill slot, the target
487 // must know how to do it (if not, we'll assert below).
488 Scavenged.push_back(ScavengedInfo(FIE));
489 }
490
491 // Avoid infinite regress
492 Scavenged[SI].Reg = Reg;
493
494 // If the target knows how to save/restore the register, let it do so;
495 // otherwise, use the emergency stack spill slot.
496 if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {
497 // Spill the scavenged register before \p Before.
498 int FI = Scavenged[SI].FrameIndex;
499 if (FI < FIB || FI >= FIE) {
500 report_fatal_error(Twine("Error while trying to spill ") +
501 TRI->getName(Reg) + " from class " +
502 TRI->getRegClassName(&RC) +
503 ": Cannot scavenge register without an emergency "
504 "spill slot!");
505 }
506 TII->storeRegToStackSlot(*MBB, Before, Reg, true, FI, &RC, TRI, Register());
507 MachineBasicBlock::iterator II = std::prev(Before);
508
509 unsigned FIOperandNum = getFrameIndexOperandNum(*II);
510 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
511
512 // Restore the scavenged register before its use (or first terminator).
513 TII->loadRegFromStackSlot(*MBB, UseMI, Reg, FI, &RC, TRI, Register());
514 II = std::prev(UseMI);
515
516 FIOperandNum = getFrameIndexOperandNum(*II);
517 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
518 }
519 return Scavenged[SI];
520}
521
524 int SPAdj, bool AllowSpill) {
525 MachineInstr &MI = *I;
526 const MachineFunction &MF = *MI.getMF();
527 // Consider all allocatable registers in the register class initially
528 BitVector Candidates = TRI->getAllocatableSet(MF, RC);
529
530 // Exclude all the registers being used by the instruction.
531 for (const MachineOperand &MO : MI.operands()) {
532 if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
533 !MO.getReg().isVirtual())
534 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
535 Candidates.reset(*AI);
536 }
537
538 // If we have already scavenged some registers, remove them from the
539 // candidates. If we end up recursively calling eliminateFrameIndex, we don't
540 // want to be clobbering previously scavenged registers or their associated
541 // stack slots.
542 for (ScavengedInfo &SI : Scavenged) {
543 if (SI.Reg) {
544 if (isRegUsed(SI.Reg)) {
546 dbgs() << "Removing " << printReg(SI.Reg, TRI) <<
547 " from scavenging candidates since it was already scavenged\n");
548 for (MCRegAliasIterator AI(SI.Reg, TRI, true); AI.isValid(); ++AI)
549 Candidates.reset(*AI);
550 }
551 }
552 }
553
554 // Try to find a register that's unused if there is one, as then we won't
555 // have to spill.
557 Available &= Candidates;
558 if (Available.any())
559 Candidates = Available;
560
561 // Find the register whose use is furthest away.
563 Register SReg =
564 findSurvivorReg(I, Candidates, RC->getRawAllocationOrder(MF), 25, UseMI);
565
566 // If we found an unused register there is no reason to spill it.
567 if (!isRegUsed(SReg)) {
568 LLVM_DEBUG(dbgs() << "Scavenged register: " << printReg(SReg, TRI) << "\n");
569 return SReg;
570 }
571
572 if (!AllowSpill)
573 return 0;
574
575#ifndef NDEBUG
576 for (ScavengedInfo &SI : Scavenged) {
577 assert(SI.Reg != SReg && "scavenged a previously scavenged register");
578 }
579#endif
580
581 ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI);
582 Scavenged.Restore = &*std::prev(UseMI);
583
584 LLVM_DEBUG(dbgs() << "Scavenged register (with spill): "
585 << printReg(SReg, TRI) << "\n");
586
587 return SReg;
588}
589
592 bool RestoreAfter, int SPAdj,
593 bool AllowSpill) {
594 const MachineBasicBlock &MBB = *To->getParent();
595 const MachineFunction &MF = *MBB.getParent();
596
597 // Find the register whose use is furthest away.
600 std::pair<MCPhysReg, MachineBasicBlock::iterator> P =
601 findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, AllocationOrder,
602 RestoreAfter);
603 MCPhysReg Reg = P.first;
604 MachineBasicBlock::iterator SpillBefore = P.second;
605 // Found an available register?
606 if (Reg != 0 && SpillBefore == MBB.end()) {
607 LLVM_DEBUG(dbgs() << "Scavenged free register: " << printReg(Reg, TRI)
608 << '\n');
609 return Reg;
610 }
611
612 if (!AllowSpill)
613 return 0;
614
615 assert(Reg != 0 && "No register left to scavenge!");
616
617 MachineBasicBlock::iterator ReloadAfter =
618 RestoreAfter ? std::next(MBBI) : MBBI;
619 MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter);
620 if (ReloadBefore != MBB.end())
621 LLVM_DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
622 ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
623 Scavenged.Restore = &*std::prev(SpillBefore);
624 LiveUnits.removeReg(Reg);
625 LLVM_DEBUG(dbgs() << "Scavenged register with spill: " << printReg(Reg, TRI)
626 << " until " << *SpillBefore);
627 return Reg;
628}
629
630/// Allocate a register for the virtual register \p VReg. The last use of
631/// \p VReg is around the current position of the register scavenger \p RS.
632/// \p ReserveAfter controls whether the scavenged register needs to be reserved
633/// after the current instruction, otherwise it will only be reserved before the
634/// current instruction.
636 Register VReg, bool ReserveAfter) {
637 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
638#ifndef NDEBUG
639 // Verify that all definitions and uses are in the same basic block.
640 const MachineBasicBlock *CommonMBB = nullptr;
641 // Real definition for the reg, re-definitions are not considered.
642 const MachineInstr *RealDef = nullptr;
643 for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
644 MachineBasicBlock *MBB = MO.getParent()->getParent();
645 if (CommonMBB == nullptr)
646 CommonMBB = MBB;
647 assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
648 if (MO.isDef()) {
649 const MachineInstr &MI = *MO.getParent();
650 if (!MI.readsRegister(VReg, &TRI)) {
651 assert((!RealDef || RealDef == &MI) &&
652 "Can have at most one definition which is not a redefinition");
653 RealDef = &MI;
654 }
655 }
656 }
657 assert(RealDef != nullptr && "Must have at least 1 Def");
658#endif
659
660 // We should only have one definition of the register. However to accommodate
661 // the requirements of two address code we also allow definitions in
662 // subsequent instructions provided they also read the register. That way
663 // we get a single contiguous lifetime.
664 //
665 // Definitions in MRI.def_begin() are unordered, search for the first.
667 MRI.def_operands(VReg), [VReg, &TRI](const MachineOperand &MO) {
668 return !MO.getParent()->readsRegister(VReg, &TRI);
669 });
670 assert(FirstDef != MRI.def_end() &&
671 "Must have one definition that does not redefine vreg");
672 MachineInstr &DefMI = *FirstDef->getParent();
673
674 // The register scavenger will report a free register inserting an emergency
675 // spill/reload if necessary.
676 int SPAdj = 0;
677 const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
678 Register SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
679 ReserveAfter, SPAdj);
680 MRI.replaceRegWith(VReg, SReg);
681 ++NumScavengedRegs;
682 return SReg;
683}
684
685/// Allocate (scavenge) vregs inside a single basic block.
686/// Returns true if the target spill callback created new vregs and a 2nd pass
687/// is necessary.
689 RegScavenger &RS,
691 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
693
694 unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
695 bool NextInstructionReadsVReg = false;
696 for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
697 --I;
698 // Move RegScavenger to the position between *I and *std::next(I).
699 RS.backward(I);
700
701 // Look for unassigned vregs in the uses of *std::next(I).
702 if (NextInstructionReadsVReg) {
703 MachineBasicBlock::iterator N = std::next(I);
704 const MachineInstr &NMI = *N;
705 for (const MachineOperand &MO : NMI.operands()) {
706 if (!MO.isReg())
707 continue;
708 Register Reg = MO.getReg();
709 // We only care about virtual registers and ignore virtual registers
710 // created by the target callbacks in the process (those will be handled
711 // in a scavenging round).
712 if (!Reg.isVirtual() ||
713 Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
714 continue;
715 if (!MO.readsReg())
716 continue;
717
718 Register SReg = scavengeVReg(MRI, RS, Reg, true);
719 N->addRegisterKilled(SReg, &TRI, false);
720 RS.setRegUsed(SReg);
721 }
722 }
723
724 // Look for unassigned vregs in the defs of *I.
725 NextInstructionReadsVReg = false;
726 const MachineInstr &MI = *I;
727 for (const MachineOperand &MO : MI.operands()) {
728 if (!MO.isReg())
729 continue;
730 Register Reg = MO.getReg();
731 // Only vregs, no newly created vregs (see above).
732 if (!Reg.isVirtual() ||
733 Register::virtReg2Index(Reg) >= InitialNumVirtRegs)
734 continue;
735 // We have to look at all operands anyway so we can precalculate here
736 // whether there is a reading operand. This allows use to skip the use
737 // step in the next iteration if there was none.
738 assert(!MO.isInternalRead() && "Cannot assign inside bundles");
739 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
740 if (MO.readsReg()) {
741 NextInstructionReadsVReg = true;
742 }
743 if (MO.isDef()) {
744 Register SReg = scavengeVReg(MRI, RS, Reg, false);
745 I->addRegisterDead(SReg, &TRI, false);
746 }
747 }
748 }
749#ifndef NDEBUG
750 for (const MachineOperand &MO : MBB.front().operands()) {
751 if (!MO.isReg() || !MO.getReg().isVirtual())
752 continue;
753 assert(!MO.isInternalRead() && "Cannot assign inside bundles");
754 assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
755 assert(!MO.readsReg() && "Vreg use in first instruction not allowed");
756 }
757#endif
758
759 return MRI.getNumVirtRegs() != InitialNumVirtRegs;
760}
761
763 // FIXME: Iterating over the instruction stream is unnecessary. We can simply
764 // iterate over the vreg use list, which at this point only contains machine
765 // operands for which eliminateFrameIndex need a new scratch reg.
767 // Shortcut.
768 if (MRI.getNumVirtRegs() == 0) {
770 return;
771 }
772
773 // Run through the instructions and find any virtual registers.
774 for (MachineBasicBlock &MBB : MF) {
775 if (MBB.empty())
776 continue;
777
778 bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
779 if (Again) {
780 LLVM_DEBUG(dbgs() << "Warning: Required two scavenging passes for block "
781 << MBB.getName() << '\n');
783 // The target required a 2nd run (because it created new vregs while
784 // spilling). Refuse to do another pass to keep compiletime in check.
785 if (Again)
786 report_fatal_error("Incomplete scavenging after 2nd pass");
787 }
788 }
789
790 MRI.clearVirtRegs();
792}
793
794namespace {
795
796/// This class runs register scavenging independ of the PrologEpilogInserter.
797/// This is used in for testing.
798class ScavengerTest : public MachineFunctionPass {
799public:
800 static char ID;
801
802 ScavengerTest() : MachineFunctionPass(ID) {}
803
804 bool runOnMachineFunction(MachineFunction &MF) override {
805 const TargetSubtargetInfo &STI = MF.getSubtarget();
806 const TargetFrameLowering &TFL = *STI.getFrameLowering();
807
808 RegScavenger RS;
809 // Let's hope that calling those outside of PrologEpilogueInserter works
810 // well enough to initialize the scavenger with some emergency spillslots
811 // for the target.
812 BitVector SavedRegs;
813 TFL.determineCalleeSaves(MF, SavedRegs, &RS);
815
816 // Let's scavenge the current function
818 return true;
819 }
820};
821
822} // end anonymous namespace
823
824char ScavengerTest::ID;
825
826INITIALIZE_PASS(ScavengerTest, "scavenger-test",
827 "Scavenge virtual registers inside basic blocks", false, false)
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock & MBB
This file implements the BitVector class.
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))
#define LLVM_DEBUG(X)
Definition: Debug.h:101
@ Available
We know the block is fully available. This is a fixpoint.
IRTranslator LLVM IR MI
A set of register units.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define P(N)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static Register scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS, Register VReg, bool ReserveAfter)
Allocate a register for the virtual register VReg.
static unsigned getFrameIndexOperandNum(MachineInstr &MI)
static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI, RegScavenger &RS, MachineBasicBlock &MBB)
Allocate (scavenge) vregs inside a single basic block.
static std::pair< MCPhysReg, MachineBasicBlock::iterator > findSurvivorBackwards(const MachineRegisterInfo &MRI, MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, const LiveRegUnits &LiveOut, ArrayRef< MCPhysReg > AllocationOrder, bool RestoreAfter)
Given the bitvector Available of free register units at position From.
This file declares the machine register scavenger class.
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & reset()
Definition: BitVector.h:392
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:341
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
Definition: BitVector.h:725
BitVector & set()
Definition: BitVector.h:351
bool none() const
none - Returns true if none of the bits are set.
Definition: BitVector.h:188
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
void addRegMasked(MCPhysReg Reg, LaneBitmask Mask)
Adds register units covered by physical register Reg that are part of the lanemask Mask.
Definition: LiveRegUnits.h:93
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:116
void init(const TargetRegisterInfo &TRI)
Initialize and clear the set.
Definition: LiveRegUnits.h:73
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of block MBB.
void addLiveIns(const MachineBasicBlock &MBB)
Adds registers living into block MBB.
void removeReg(MCPhysReg Reg)
Removes all register units covered by physical register Reg.
Definition: LiveRegUnits.h:102
MCRegAliasIterator enumerates all registers aliasing Reg.
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
const char * getName(MCRegister RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register.
iterator_range< mc_superreg_iterator > superregs(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, excluding Reg.
iterator_range< mc_subreg_iterator > subregs(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, excluding Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineInstrBundleIterator< MachineInstr > iterator
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
int getObjectIndexEnd() const
Return one past the maximum frame object index.
int getObjectIndexBegin() const
Return the minimum frame object index.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const MachineFunctionProperties & getProperties() const
Get the function properties.
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use.
Representation of each machine instruction.
Definition: MachineInstr.h:68
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:641
MachineOperand class - Representation of each machine instruction operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
void enterBasicBlockEnd(MachineBasicBlock &MBB)
Start tracking liveness from the end of basic block MBB.
bool isRegUsed(Register Reg, bool includeReserved=true) const
Return if a specific register is currently used.
Register FindUnusedReg(const TargetRegisterClass *RC) const
Find an unused register of the specified register class.
Register scavengeRegister(const TargetRegisterClass *RC, MachineBasicBlock::iterator I, int SPAdj, bool AllowSpill=true)
Make a register of the specific register class available and do the appropriate bookkeeping.
void setRegUsed(Register Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Tell the scavenger a register is used.
void backward()
Update internal register state and move MBB iterator backwards.
void enterBasicBlock(MachineBasicBlock &MBB)
Start tracking liveness from the begin of basic block MBB.
Register scavengeRegisterBackwards(const TargetRegisterClass &RC, MachineBasicBlock::iterator To, bool RestoreAfter, int SPAdj, bool AllowSpill=true)
Make a register of the specific register class available from the current position backwards to the p...
BitVector getRegsAvailable(const TargetRegisterClass *RC)
Return all available registers in the register class in Mask.
void forward()
Move the internal MBB iterator and update register states.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
Information about stack frame layout on the target.
virtual void determineCalleeSaves(MachineFunction &MF, BitVector &SavedRegs, RegScavenger *RS=nullptr) const
This method determines which of the registers reported by TargetRegisterInfo::getCalleeSavedRegs() sh...
virtual void processFunctionBeforeFrameFinalized(MachineFunction &MF, RegScavenger *RS=nullptr) const
processFunctionBeforeFrameFinalized - This method is called immediately before the specified function...
virtual void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const
Load the specified register of the given register class from the specified stack frame index.
virtual void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const
Store the specified register of the given register class to the specified stack frame index.
ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF) const
Returns the preferred order for allocating registers from this register class in MF.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Align getSpillAlign(const TargetRegisterClass &RC) const
Return the minimum required alignment in bytes for a spill slot for a register of this class.
virtual bool eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj, unsigned FIOperandNum, RegScavenger *RS=nullptr) const =0
This method must be overriden to eliminate abstract frame indices from instructions which may use the...
virtual bool saveScavengerRegister(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, MachineBasicBlock::iterator &UseMI, const TargetRegisterClass *RC, Register Reg) const
Spill the register so it can be used by the register scavenger.
unsigned getSpillSize(const TargetRegisterClass &RC) const
Return the size in bytes of the stack slot allocated to hold a spilled copy of a register from class ...
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
BitVector getAllocatableSet(const MachineFunction &MF, const TargetRegisterClass *RC=nullptr) const
Returns a bitset indexed by register number indicating if a register is allocatable or not.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetFrameLowering * getFrameLowering() const
virtual const TargetInstrInfo * getInstrInfo() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS)
Replaces all frame index virtual registers with physical registers.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1833
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1846
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
#define N
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85