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"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/CodeGen/LiveInterval.h"
18#include "llvm/CodeGen/LiveIntervals.h"
19#include "llvm/CodeGen/LiveRegMatrix.h"
20#include "llvm/CodeGen/MachineInstr.h"
21#include "llvm/CodeGen/MachineModuleInfo.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/CodeGen/Spiller.h"
24#include "llvm/CodeGen/TargetRegisterInfo.h"
25#include "llvm/CodeGen/VirtRegMap.h"
26#include "llvm/IR/DiagnosticInfo.h"
27#include "llvm/IR/Module.h"
28#include "llvm/IR/PassTimingInfo.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/Timer.h"
34#include "llvm/Support/raw_ostream.h"
35#include <cassert>
36
37using namespace llvm;
38
39#define DEBUG_TYPE "regalloc"
40
41STATISTIC(NumNewQueued, "Number of new live ranges queued");
42
43// Temporary verification option until we can put verification inside
44// MachineVerifier.
45static cl::opt<bool, true>
46 VerifyRegAlloc("verify-regalloc", cl::location(L&: RegAllocBase::VerifyEnabled),
47 cl::Hidden, cl::desc("Verify during register allocation"));
48
49const char RegAllocBase::TimerGroupName[] = "regalloc";
50const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";
51bool RegAllocBase::VerifyEnabled = false;
52
53//===----------------------------------------------------------------------===//
54// RegAllocBase Implementation
55//===----------------------------------------------------------------------===//
56
57// Pin the vtable to this file.
58void RegAllocBase::anchor() {}
59
60void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat,
61 RegisterClassInfo &rci) {
62 TRI = &vrm.getTargetRegInfo();
63 MRI = &vrm.getRegInfo();
64 VRM = &vrm;
65 LIS = &lis;
66 Matrix = &mat;
67 RegClassInfo = &rci;
68 MRI->freezeReservedRegs();
69 // Keep the shared analysis in step with the set just frozen.
70 RegClassInfo->updateReservedRegs(ReservedInput: MRI->getReservedRegs());
71 FailedVRegs.clear();
72}
73
74// Visit all the live registers. If they are already assigned to a physical
75// register, unify them with the corresponding LiveIntervalUnion, otherwise push
76// them on the priority queue for later assignment.
77void RegAllocBase::seedLiveRegs() {
78 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,
79 TimerGroupDescription, TimePassesIsEnabled);
80 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
81 Register Reg = Register::index2VirtReg(Index: i);
82 if (MRI->reg_nodbg_empty(RegNo: Reg))
83 continue;
84 enqueue(LI: &LIS->getInterval(Reg));
85 }
86}
87
88// Top-level driver to manage the queue of unassigned VirtRegs and call the
89// selectOrSplit implementation.
90void RegAllocBase::allocatePhysRegs() {
91 seedLiveRegs();
92
93 // Continue assigning vregs one at a time to available physical registers.
94 while (const LiveInterval *VirtReg = dequeue()) {
95 assert(!VRM->hasPhys(VirtReg->reg()) && "Register already assigned");
96
97 // Unused registers can appear when the spiller coalesces snippets.
98 if (MRI->reg_nodbg_empty(RegNo: VirtReg->reg())) {
99 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
100 aboutToRemoveInterval(LI: *VirtReg);
101 LIS->removeInterval(Reg: VirtReg->reg());
102 continue;
103 }
104
105 // Invalidate all interference queries, live ranges could have changed.
106 Matrix->invalidateVirtRegs();
107
108 // selectOrSplit requests the allocator to return an available physical
109 // register if possible and populate a list of new live intervals that
110 // result from splitting.
111 LLVM_DEBUG(dbgs() << "\nselectOrSplit "
112 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg()))
113 << ':' << *VirtReg << '\n');
114
115 using VirtRegVec = SmallVector<Register, 4>;
116
117 VirtRegVec SplitVRegs;
118 MCRegister AvailablePhysReg = selectOrSplit(VirtReg: *VirtReg, splitLVRs&: SplitVRegs);
119
120 if (AvailablePhysReg == ~0u) {
121 // selectOrSplit failed to find a register!
122 // Probably caused by an inline asm.
123 MachineInstr *MI = nullptr;
124 for (MachineInstr &MIR : MRI->reg_instructions(Reg: VirtReg->reg())) {
125 MI = &MIR;
126 if (MI->isInlineAsm())
127 break;
128 }
129
130 const TargetRegisterClass *RC = MRI->getRegClass(Reg: VirtReg->reg());
131 AvailablePhysReg = getErrorAssignment(RC: *RC, CtxMI: MI);
132
133 // Keep going after reporting the error.
134 cleanupFailedVReg(FailedVReg: VirtReg->reg(), PhysReg: AvailablePhysReg, SplitRegs&: SplitVRegs);
135 } else if (AvailablePhysReg)
136 Matrix->assign(VirtReg: *VirtReg, PhysReg: AvailablePhysReg);
137
138 for (Register Reg : SplitVRegs) {
139 assert(LIS->hasInterval(Reg));
140
141 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
142 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned");
143 if (MRI->reg_nodbg_empty(RegNo: SplitVirtReg->reg())) {
144 assert(SplitVirtReg->empty() && "Non-empty but used interval");
145 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');
146 aboutToRemoveInterval(LI: *SplitVirtReg);
147 LIS->removeInterval(Reg: SplitVirtReg->reg());
148 continue;
149 }
150 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
151 assert(SplitVirtReg->reg().isVirtual() &&
152 "expect split value in virtual register");
153 enqueue(LI: SplitVirtReg);
154 ++NumNewQueued;
155 }
156 }
157}
158
159void RegAllocBase::postOptimization() {
160 spiller().postOptimization();
161
162 // Verify LiveRegMatrix after spilling (no dangling pointers).
163 assert(Matrix->isValid() && "LiveRegMatrix validation failed");
164
165 for (auto *DeadInst : DeadRemats) {
166 LIS->RemoveMachineInstrFromMaps(MI&: *DeadInst);
167 DeadInst->eraseFromParent();
168 }
169 DeadRemats.clear();
170}
171
172void RegAllocBase::cleanupFailedVReg(Register FailedReg, MCRegister PhysReg,
173 SmallVectorImpl<Register> &SplitRegs) {
174 // We still should produce valid IR. Kill all the uses and reduce the live
175 // ranges so that we don't think it's possible to introduce kill flags later
176 // which will fail the verifier.
177 for (MachineOperand &MO : MRI->reg_operands(Reg: FailedReg)) {
178 if (MO.readsReg())
179 MO.setIsUndef(true);
180 if (MO.isDef())
181 cleanupFailedDefs(MI&: *MO.getParent(), FailedReg, PhysReg);
182 }
183
184 if (!MRI->isReserved(PhysReg)) {
185 // Physical liveness for any aliasing registers is now unreliable, so delete
186 // the uses.
187 for (MCRegAliasIterator Aliases(PhysReg, TRI, true); Aliases.isValid();
188 ++Aliases) {
189 for (MachineOperand &MO : MRI->reg_operands(Reg: *Aliases)) {
190 if (MO.readsReg())
191 MO.setIsUndef(true);
192 }
193 }
194 }
195
196 // Directly perform the rewrite, and do not leave it to VirtRegRewriter as
197 // usual. This avoids trying to manage illegal overlapping assignments in
198 // LiveRegMatrix.
199 MRI->replaceRegWith(FromReg: FailedReg, ToReg: PhysReg);
200 LIS->removeInterval(Reg: FailedReg);
201}
202
203void RegAllocBase::cleanupFailedDefs(MachineInstr &MI, Register FailedReg,
204 MCRegister PhysReg) {
205 auto IsErrorDef = [=](const MachineOperand &MO) {
206 return MO.getReg() == FailedReg || MO.getReg() == PhysReg;
207 };
208
209 SlotIndex Idx = LIS->getInstructionIndex(Instr: MI);
210 std::optional<bool> AssignedIsDead;
211 bool AnyLive = false;
212 for (const MachineOperand &MO : MI.all_defs()) {
213 Register Reg = MO.getReg();
214 if (IsErrorDef(MO)) {
215 AnyLive |= !MO.isDead();
216 if (MRI->isReserved(PhysReg))
217 continue;
218
219 // Add the def to the PhysReg regunit ranges so it interferes with later
220 // assignments. Ranges computed later will include the rewritten def.
221 MCRegister DefReg = PhysReg;
222 if (MO.getSubReg())
223 DefReg = TRI->getSubReg(Reg: PhysReg, Idx: MO.getSubReg());
224
225 SlotIndex DefIdx = Idx.getRegSlot(EC: MO.isEarlyClobber());
226 for (MCRegUnit Unit : TRI->regunits(Reg: DefReg)) {
227 LiveRange *LR = LIS->getCachedRegUnit(Unit);
228 if (LR && !LR->liveAt(index: DefIdx))
229 LR->createDeadDef(Def: DefIdx, VNIAlloc&: LIS->getVNInfoAllocator());
230 }
231 } else if (Reg.isVirtual() && VRM->hasPhys(virtReg: Reg)) {
232 MCRegister AssignedReg = VRM->getPhys(virtReg: Reg);
233 if (MO.getSubReg())
234 AssignedReg = TRI->getSubReg(Reg: AssignedReg, Idx: MO.getSubReg());
235 if (AssignedReg == PhysReg)
236 AssignedIsDead = MO.isDead();
237 }
238 }
239
240 // Match a virtual register def assigned PhysReg, since its dead flag must
241 // agree with its live interval. Otherwise, keep PhysReg live if any def is.
242 bool IsDead = AssignedIsDead.value_or(u: !AnyLive);
243 for (MachineOperand &MO : MI.all_defs()) {
244 if (IsErrorDef(MO))
245 MO.setIsDead(IsDead);
246 }
247}
248
249void RegAllocBase::enqueue(const LiveInterval *LI) {
250 const Register Reg = LI->reg();
251
252 assert(Reg.isVirtual() && "Can only enqueue virtual registers");
253
254 if (VRM->hasPhys(virtReg: Reg))
255 return;
256
257 if (shouldAllocateRegister(Reg)) {
258 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n');
259 enqueueImpl(LI);
260 } else {
261 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI)
262 << " in skipped register class\n");
263 }
264}
265
266MCPhysReg RegAllocBase::getErrorAssignment(const TargetRegisterClass &RC,
267 const MachineInstr *CtxMI) {
268 MachineFunction &MF = VRM->getMachineFunction();
269
270 // Avoid printing the error for every single instance of the register. It
271 // would be better if this were per register class.
272 bool EmitError = !MF.getProperties().hasFailedRegAlloc();
273 if (EmitError)
274 MF.getProperties().setFailedRegAlloc();
275
276 const Function &Fn = MF.getFunction();
277 LLVMContext &Context = Fn.getContext();
278
279 ArrayRef<MCPhysReg> AllocOrder = RegClassInfo->getOrder(RC: &RC);
280 if (AllocOrder.empty()) {
281 // If the allocation order is empty, it likely means all registers in the
282 // class are reserved. We still to need to pick something, so look at the
283 // underlying class.
284 ArrayRef<MCPhysReg> RawRegs = RC.getRegisters();
285
286 if (EmitError) {
287 Context.diagnose(DI: DiagnosticInfoRegAllocFailure(
288 "no registers from class available to allocate", Fn,
289 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation()));
290 }
291
292 assert(!RawRegs.empty() && "register classes cannot have no registers");
293 return RawRegs.front();
294 }
295
296 if (EmitError) {
297 if (CtxMI && CtxMI->isInlineAsm()) {
298 CtxMI->emitInlineAsmError(
299 ErrMsg: "inline assembly requires more registers than available");
300 } else {
301 Context.diagnose(DI: DiagnosticInfoRegAllocFailure(
302 "ran out of registers during register allocation", Fn,
303 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation()));
304 }
305 }
306
307 return AllocOrder.front();
308}
309