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/Pass.h"
28#include "llvm/Support/Debug.h"
30#include "llvm/Support/Timer.h"
32#include <cassert>
33
34using namespace llvm;
35
36#define DEBUG_TYPE "regalloc"
37
38STATISTIC(NumNewQueued, "Number of new live ranges queued");
39
40// Temporary verification option until we can put verification inside
41// MachineVerifier.
44 cl::Hidden, cl::desc("Verify during register allocation"));
45
46const char RegAllocBase::TimerGroupName[] = "regalloc";
47const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";
49
50//===----------------------------------------------------------------------===//
51// RegAllocBase Implementation
52//===----------------------------------------------------------------------===//
53
54// Pin the vtable to this file.
55void RegAllocBase::anchor() {}
56
58 LiveRegMatrix &mat) {
59 TRI = &vrm.getTargetRegInfo();
60 MRI = &vrm.getRegInfo();
61 VRM = &vrm;
62 LIS = &lis;
63 Matrix = &mat;
66}
67
68// Visit all the live registers. If they are already assigned to a physical
69// register, unify them with the corresponding LiveIntervalUnion, otherwise push
70// them on the priority queue for later assignment.
71void RegAllocBase::seedLiveRegs() {
72 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,
74 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
76 if (MRI->reg_nodbg_empty(Reg))
77 continue;
78 enqueue(&LIS->getInterval(Reg));
79 }
80}
81
82// Top-level driver to manage the queue of unassigned VirtRegs and call the
83// selectOrSplit implementation.
85 seedLiveRegs();
86
87 // Continue assigning vregs one at a time to available physical registers.
88 while (const LiveInterval *VirtReg = dequeue()) {
89 assert(!VRM->hasPhys(VirtReg->reg()) && "Register already assigned");
90
91 // Unused registers can appear when the spiller coalesces snippets.
92 if (MRI->reg_nodbg_empty(VirtReg->reg())) {
93 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
94 aboutToRemoveInterval(*VirtReg);
95 LIS->removeInterval(VirtReg->reg());
96 continue;
97 }
98
99 // Invalidate all interference queries, live ranges could have changed.
101
102 // selectOrSplit requests the allocator to return an available physical
103 // register if possible and populate a list of new live intervals that
104 // result from splitting.
105 LLVM_DEBUG(dbgs() << "\nselectOrSplit "
106 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg()))
107 << ':' << *VirtReg << " w=" << VirtReg->weight() << '\n');
108
109 using VirtRegVec = SmallVector<Register, 4>;
110
111 VirtRegVec SplitVRegs;
112 MCRegister AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
113
114 if (AvailablePhysReg == ~0u) {
115 // selectOrSplit failed to find a register!
116 // Probably caused by an inline asm.
117 MachineInstr *MI = nullptr;
119 I = MRI->reg_instr_begin(VirtReg->reg()),
120 E = MRI->reg_instr_end();
121 I != E;) {
122 MI = &*(I++);
123 if (MI->isInlineAsm())
124 break;
125 }
126
127 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg());
129 if (AllocOrder.empty())
130 report_fatal_error("no registers from class available to allocate");
131 else if (MI && MI->isInlineAsm()) {
132 MI->emitError("inline assembly requires more registers than available");
133 } else if (MI) {
135 MI->getParent()->getParent()->getMMI().getModule()->getContext();
136 Context.emitError("ran out of registers during register allocation");
137 } else {
138 report_fatal_error("ran out of registers during register allocation");
139 }
140
141 // Keep going after reporting the error.
142 VRM->assignVirt2Phys(VirtReg->reg(), AllocOrder.front());
143 } else if (AvailablePhysReg)
144 Matrix->assign(*VirtReg, AvailablePhysReg);
145
146 for (Register Reg : SplitVRegs) {
147 assert(LIS->hasInterval(Reg));
148
149 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
150 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned");
151 if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) {
152 assert(SplitVirtReg->empty() && "Non-empty but used interval");
153 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
154 aboutToRemoveInterval(*SplitVirtReg);
155 LIS->removeInterval(SplitVirtReg->reg());
156 continue;
157 }
158 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
159 assert(SplitVirtReg->reg().isVirtual() &&
160 "expect split value in virtual register");
161 enqueue(SplitVirtReg);
162 ++NumNewQueued;
163 }
164 }
165}
166
169 for (auto *DeadInst : DeadRemats) {
171 DeadInst->eraseFromParent();
172 }
173 DeadRemats.clear();
174}
175
177 const Register Reg = LI->reg();
178
179 assert(Reg.isVirtual() && "Can only enqueue virtual registers");
180
181 if (VRM->hasPhys(Reg))
182 return;
183
184 const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
185 if (ShouldAllocateClass(*TRI, RC)) {
186 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n');
187 enqueueImpl(LI);
188 } else {
189 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI)
190 << " in skipped register class\n");
191 }
192}
#define LLVM_DEBUG(X)
Definition: Debug.h:101
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
LLVMContext & Context
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
defusechain_iterator - This class provides iterator support for machine operands in the function that...
reg_instr_iterator reg_instr_begin(Register RegNo) const
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.
static reg_instr_iterator reg_instr_end()
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
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:119
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:77
virtual Spiller & spiller()=0
const TargetRegisterInfo * TRI
Definition: RegAllocBase.h:65
LiveIntervals * LIS
Definition: RegAllocBase.h:68
static const char TimerGroupName[]
Definition: RegAllocBase.h:115
static const char TimerGroupDescription[]
Definition: RegAllocBase.h:116
LiveRegMatrix * Matrix
Definition: RegAllocBase.h:69
virtual const LiveInterval * dequeue()=0
dequeue - Return the next unassigned register, or NULL.
virtual void postOptimization()
VirtRegMap * VRM
Definition: RegAllocBase.h:67
RegisterClassInfo RegClassInfo
Definition: RegAllocBase.h:70
MachineRegisterInfo * MRI
Definition: RegAllocBase.h:66
virtual void enqueueImpl(const LiveInterval *LI)=0
enqueue - Add VirtReg to the priority queue of unassigned registers.
static bool VerifyEnabled
VerifyEnabled - True when -verify-regalloc is given.
Definition: RegAllocBase.h:123
const RegClassFilterFunc ShouldAllocateClass
Definition: RegAllocBase.h:71
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:470
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:156
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