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/Pass.h" |
27 | #include "llvm/Support/CommandLine.h" |
28 | #include "llvm/Support/Debug.h" |
29 | #include "llvm/Support/ErrorHandling.h" |
30 | #include "llvm/Support/Timer.h" |
31 | #include "llvm/Support/raw_ostream.h" |
32 | #include <cassert> |
33 | |
34 | using namespace llvm; |
35 | |
36 | #define DEBUG_TYPE "regalloc" |
37 | |
38 | STATISTIC(NumNewQueued, "Number of new live ranges queued" ); |
39 | |
40 | // Temporary verification option until we can put verification inside |
41 | // MachineVerifier. |
42 | static cl::opt<bool, true> |
43 | VerifyRegAlloc("verify-regalloc" , cl::location(L&: RegAllocBase::VerifyEnabled), |
44 | cl::Hidden, cl::desc("Verify during register allocation" )); |
45 | |
46 | const char RegAllocBase::TimerGroupName[] = "regalloc" ; |
47 | const char RegAllocBase::TimerGroupDescription[] = "Register Allocation" ; |
48 | bool RegAllocBase::VerifyEnabled = false; |
49 | |
50 | //===----------------------------------------------------------------------===// |
51 | // RegAllocBase Implementation |
52 | //===----------------------------------------------------------------------===// |
53 | |
54 | // Pin the vtable to this file. |
55 | void RegAllocBase::anchor() {} |
56 | |
57 | void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis, |
58 | LiveRegMatrix &mat) { |
59 | TRI = &vrm.getTargetRegInfo(); |
60 | MRI = &vrm.getRegInfo(); |
61 | VRM = &vrm; |
62 | LIS = &lis; |
63 | Matrix = &mat; |
64 | MRI->freezeReservedRegs(vrm.getMachineFunction()); |
65 | RegClassInfo.runOnMachineFunction(MF: vrm.getMachineFunction()); |
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. |
71 | void RegAllocBase::seedLiveRegs() { |
72 | NamedRegionTimer T("seed" , "Seed Live Regs" , TimerGroupName, |
73 | TimerGroupDescription, TimePassesIsEnabled); |
74 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { |
75 | Register Reg = Register::index2VirtReg(Index: i); |
76 | if (MRI->reg_nodbg_empty(RegNo: Reg)) |
77 | continue; |
78 | enqueue(LI: &LIS->getInterval(Reg)); |
79 | } |
80 | } |
81 | |
82 | // Top-level driver to manage the queue of unassigned VirtRegs and call the |
83 | // selectOrSplit implementation. |
84 | void RegAllocBase::allocatePhysRegs() { |
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(RegNo: VirtReg->reg())) { |
93 | LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); |
94 | aboutToRemoveInterval(LI: *VirtReg); |
95 | LIS->removeInterval(Reg: VirtReg->reg()); |
96 | continue; |
97 | } |
98 | |
99 | // Invalidate all interference queries, live ranges could have changed. |
100 | Matrix->invalidateVirtRegs(); |
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: *VirtReg, splitLVRs&: SplitVRegs); |
113 | |
114 | if (AvailablePhysReg == ~0u) { |
115 | // selectOrSplit failed to find a register! |
116 | // Probably caused by an inline asm. |
117 | MachineInstr *MI = nullptr; |
118 | for (MachineRegisterInfo::reg_instr_iterator |
119 | I = MRI->reg_instr_begin(RegNo: 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(Reg: VirtReg->reg()); |
128 | ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(RC); |
129 | if (AllocOrder.empty()) |
130 | report_fatal_error(reason: "no registers from class available to allocate" ); |
131 | else if (MI && MI->isInlineAsm()) { |
132 | MI->emitError(Msg: "inline assembly requires more registers than available" ); |
133 | } else if (MI) { |
134 | LLVMContext &Context = |
135 | MI->getParent()->getParent()->getMMI().getModule()->getContext(); |
136 | Context.emitError(ErrorStr: "ran out of registers during register allocation" ); |
137 | } else { |
138 | report_fatal_error(reason: "ran out of registers during register allocation" ); |
139 | } |
140 | |
141 | // Keep going after reporting the error. |
142 | VRM->assignVirt2Phys(virtReg: VirtReg->reg(), physReg: AllocOrder.front()); |
143 | } else if (AvailablePhysReg) |
144 | Matrix->assign(VirtReg: *VirtReg, PhysReg: 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(RegNo: SplitVirtReg->reg())) { |
152 | assert(SplitVirtReg->empty() && "Non-empty but used interval" ); |
153 | LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); |
154 | aboutToRemoveInterval(LI: *SplitVirtReg); |
155 | LIS->removeInterval(Reg: 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(LI: SplitVirtReg); |
162 | ++NumNewQueued; |
163 | } |
164 | } |
165 | } |
166 | |
167 | void RegAllocBase::postOptimization() { |
168 | spiller().postOptimization(); |
169 | for (auto *DeadInst : DeadRemats) { |
170 | LIS->RemoveMachineInstrFromMaps(MI&: *DeadInst); |
171 | DeadInst->eraseFromParent(); |
172 | } |
173 | DeadRemats.clear(); |
174 | } |
175 | |
176 | void RegAllocBase::enqueue(const LiveInterval *LI) { |
177 | const Register Reg = LI->reg(); |
178 | |
179 | assert(Reg.isVirtual() && "Can only enqueue virtual registers" ); |
180 | |
181 | if (VRM->hasPhys(virtReg: 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 | } |
193 | |