LLVM 19.0.0git
RegAllocBase.cpp
Go to the documentation of this file.
1//===- RegAllocBase.cpp - Register Allocator Base Class -------------------===//
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// This file defines the RegAllocBase class which provides common functionality
10// for LiveIntervalUnion-based register allocators.
11//
12//===----------------------------------------------------------------------===//
13
14#include "RegAllocBase.h"
16#include "llvm/ADT/Statistic.h"
26#include "llvm/IR/Module.h"
27#include "llvm/Pass.h"
29#include "llvm/Support/Debug.h"
31#include "llvm/Support/Timer.h"
33#include <cassert>
34
35using namespace llvm;
36
37#define DEBUG_TYPE "regalloc"
38
39STATISTIC(NumNewQueued, "Number of new live ranges queued");
40
41// Temporary verification option until we can put verification inside
42// MachineVerifier.
45 cl::Hidden, cl::desc("Verify during register allocation"));
46
47const char RegAllocBase::TimerGroupName[] = "regalloc";
48const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";
50
51//===----------------------------------------------------------------------===//
52// RegAllocBase Implementation
53//===----------------------------------------------------------------------===//
54
55// Pin the vtable to this file.
56void RegAllocBase::anchor() {}
57
59 LiveRegMatrix &mat) {
60 TRI = &vrm.getTargetRegInfo();
61 MRI = &vrm.getRegInfo();
62 VRM = &vrm;
63 LIS = &lis;
64 Matrix = &mat;
67}
68
69// Visit all the live registers. If they are already assigned to a physical
70// register, unify them with the corresponding LiveIntervalUnion, otherwise push
71// them on the priority queue for later assignment.
72void RegAllocBase::seedLiveRegs() {
73 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,
75 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
77 if (MRI->reg_nodbg_empty(Reg))
78 continue;
79 enqueue(&LIS->getInterval(Reg));
80 }
81}
82
83// Top-level driver to manage the queue of unassigned VirtRegs and call the
84// selectOrSplit implementation.
86 seedLiveRegs();
87
88 // Continue assigning vregs one at a time to available physical registers.
89 while (const LiveInterval *VirtReg = dequeue()) {
90 assert(!VRM->hasPhys(VirtReg->reg()) && "Register already assigned");
91
92 // Unused registers can appear when the spiller coalesces snippets.
93 if (MRI->reg_nodbg_empty(VirtReg->reg())) {
94 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
95 aboutToRemoveInterval(*VirtReg);
96 LIS->removeInterval(VirtReg->reg());
97 continue;
98 }
99
100 // Invalidate all interference queries, live ranges could have changed.
102
103 // selectOrSplit requests the allocator to return an available physical
104 // register if possible and populate a list of new live intervals that
105 // result from splitting.
106 LLVM_DEBUG(dbgs() << "\nselectOrSplit "
107 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg()))
108 << ':' << *VirtReg << " w=" << VirtReg->weight() << '\n');
109
110 using VirtRegVec = SmallVector<Register, 4>;
111
112 VirtRegVec SplitVRegs;
113 MCRegister AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
114
115 if (AvailablePhysReg == ~0u) {
116 // selectOrSplit failed to find a register!
117 // Probably caused by an inline asm.
118 MachineInstr *MI = nullptr;
119 for (MachineInstr &MIR : MRI->reg_instructions(VirtReg->reg())) {
120 MI = &MIR;
121 if (MI->isInlineAsm())
122 break;
123 }
124
125 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg());
127 if (AllocOrder.empty())
128 report_fatal_error("no registers from class available to allocate");
129 else if (MI && MI->isInlineAsm()) {
130 MI->emitError("inline assembly requires more registers than available");
131 } else if (MI) {
132 LLVMContext &Context =
133 MI->getParent()->getParent()->getMMI().getModule()->getContext();
134 Context.emitError("ran out of registers during register allocation");
135 } else {
136 report_fatal_error("ran out of registers during register allocation");
137 }
138
139 // Keep going after reporting the error.
140 VRM->assignVirt2Phys(VirtReg->reg(), AllocOrder.front());
141 } else if (AvailablePhysReg)
142 Matrix->assign(*VirtReg, AvailablePhysReg);
143
144 for (Register Reg : SplitVRegs) {
145 assert(LIS->hasInterval(Reg));
146
147 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
148 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned");
149 if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) {
150 assert(SplitVirtReg->empty() && "Non-empty but used interval");
151 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
152 aboutToRemoveInterval(*SplitVirtReg);
153 LIS->removeInterval(SplitVirtReg->reg());
154 continue;
155 }
156 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
157 assert(SplitVirtReg->reg().isVirtual() &&
158 "expect split value in virtual register");
159 enqueue(SplitVirtReg);
160 ++NumNewQueued;
161 }
162 }
163}
164
167 for (auto *DeadInst : DeadRemats) {
169 DeadInst->eraseFromParent();
170 }
171 DeadRemats.clear();
172}
173
175 const Register Reg = LI->reg();
176
177 assert(Reg.isVirtual() && "Can only enqueue virtual registers");
178
179 if (VRM->hasPhys(Reg))
180 return;
181
182 if (shouldAllocateRegister(Reg)) {
183 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n');
184 enqueueImpl(LI);
185 } else {
186 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI)
187 << " in skipped register class\n");
188 }
189}
#define LLVM_DEBUG(X)
Definition: Debug.h:101
IRTranslator LLVM IR MI
Module.h This file contains the declarations for the Module class.
static cl::opt< bool, true > VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), cl::Hidden, cl::desc("Verify during register allocation"))
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
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:168
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
void emitError(uint64_t LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
Register reg() const
Definition: LiveInterval.h:718
bool hasInterval(Register Reg) const
void RemoveMachineInstrFromMaps(MachineInstr &MI)
LiveInterval & getInterval(Register Reg)
void removeInterval(Register Reg)
Interval removal.
bool empty() const
Definition: LiveInterval.h:382
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
void assign(const LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
Representation of each machine instruction.
Definition: MachineInstr.h:69
void freezeReservedRegs()
freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
iterator_range< reg_instr_iterator > reg_instructions(Register Reg) const
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
virtual void aboutToRemoveInterval(const LiveInterval &LI)
Method called when the allocator is about to remove a LiveInterval.
Definition: RegAllocBase.h:130
virtual MCRegister selectOrSplit(const LiveInterval &VirtReg, SmallVectorImpl< Register > &splitLVRs)=0
void enqueue(const LiveInterval *LI)
enqueue - Add VirtReg to the priority queue of unassigned registers.
void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)
SmallPtrSet< MachineInstr *, 32 > DeadRemats
Inst which is a def of an original reg and whose defs are already all dead after remat is saved in De...
Definition: RegAllocBase.h:82
virtual Spiller & spiller()=0
const TargetRegisterInfo * TRI
Definition: RegAllocBase.h:66
LiveIntervals * LIS
Definition: RegAllocBase.h:69
static const char TimerGroupName[]
Definition: RegAllocBase.h:126
static const char TimerGroupDescription[]
Definition: RegAllocBase.h:127
LiveRegMatrix * Matrix
Definition: RegAllocBase.h:70
virtual const LiveInterval * dequeue()=0
dequeue - Return the next unassigned register, or NULL.
virtual void postOptimization()
VirtRegMap * VRM
Definition: RegAllocBase.h:68
RegisterClassInfo RegClassInfo
Definition: RegAllocBase.h:71
MachineRegisterInfo * MRI
Definition: RegAllocBase.h:67
virtual void enqueueImpl(const LiveInterval *LI)=0
enqueue - Add VirtReg to the priority queue of unassigned registers.
bool shouldAllocateRegister(Register Reg)
Get whether a given register should be allocated.
Definition: RegAllocBase.h:92
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
Definition: RegAllocBase.h:134
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
virtual void postOptimization()
Definition: Spiller.h:33
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
MachineRegisterInfo & getRegInfo() const
Definition: VirtRegMap.h:92
MachineFunction & getMachineFunction() const
Definition: VirtRegMap.h:87
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition: VirtRegMap.h:99
const TargetRegisterInfo & getTargetRegInfo() const
Definition: VirtRegMap.h:93
void assignVirt2Phys(Register virtReg, MCPhysReg physReg)
creates a mapping for the specified virtual register to the specified physical register
Definition: VirtRegMap.cpp:85
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:463
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:167
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.
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:163