1 | //===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===// |
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 RABasic function pass, which provides a minimal |
10 | // implementation of the basic register allocator. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #include "AllocationOrder.h" |
15 | #include "LiveDebugVariables.h" |
16 | #include "RegAllocBase.h" |
17 | #include "llvm/Analysis/AliasAnalysis.h" |
18 | #include "llvm/CodeGen/CalcSpillWeights.h" |
19 | #include "llvm/CodeGen/LiveIntervals.h" |
20 | #include "llvm/CodeGen/LiveRangeEdit.h" |
21 | #include "llvm/CodeGen/LiveRegMatrix.h" |
22 | #include "llvm/CodeGen/LiveStacks.h" |
23 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
24 | #include "llvm/CodeGen/MachineFunctionPass.h" |
25 | #include "llvm/CodeGen/MachineLoopInfo.h" |
26 | #include "llvm/CodeGen/Passes.h" |
27 | #include "llvm/CodeGen/RegAllocRegistry.h" |
28 | #include "llvm/CodeGen/Spiller.h" |
29 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
30 | #include "llvm/CodeGen/VirtRegMap.h" |
31 | #include "llvm/Pass.h" |
32 | #include "llvm/Support/Debug.h" |
33 | #include "llvm/Support/raw_ostream.h" |
34 | #include <queue> |
35 | |
36 | using namespace llvm; |
37 | |
38 | #define DEBUG_TYPE "regalloc" |
39 | |
40 | static RegisterRegAlloc basicRegAlloc("basic" , "basic register allocator" , |
41 | createBasicRegisterAllocator); |
42 | |
43 | namespace { |
44 | struct CompSpillWeight { |
45 | bool operator()(const LiveInterval *A, const LiveInterval *B) const { |
46 | return A->weight() < B->weight(); |
47 | } |
48 | }; |
49 | } |
50 | |
51 | namespace { |
52 | /// RABasic provides a minimal implementation of the basic register allocation |
53 | /// algorithm. It prioritizes live virtual registers by spill weight and spills |
54 | /// whenever a register is unavailable. This is not practical in production but |
55 | /// provides a useful baseline both for measuring other allocators and comparing |
56 | /// the speed of the basic algorithm against other styles of allocators. |
57 | class RABasic : public MachineFunctionPass, |
58 | public RegAllocBase, |
59 | private LiveRangeEdit::Delegate { |
60 | // context |
61 | MachineFunction *MF = nullptr; |
62 | |
63 | // state |
64 | std::unique_ptr<Spiller> SpillerInstance; |
65 | std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>, |
66 | CompSpillWeight> |
67 | Queue; |
68 | |
69 | // Scratch space. Allocated here to avoid repeated malloc calls in |
70 | // selectOrSplit(). |
71 | BitVector UsableRegs; |
72 | |
73 | bool LRE_CanEraseVirtReg(Register) override; |
74 | void LRE_WillShrinkVirtReg(Register) override; |
75 | |
76 | public: |
77 | RABasic(const RegClassFilterFunc F = allocateAllRegClasses); |
78 | |
79 | /// Return the pass name. |
80 | StringRef getPassName() const override { return "Basic Register Allocator" ; } |
81 | |
82 | /// RABasic analysis usage. |
83 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
84 | |
85 | void releaseMemory() override; |
86 | |
87 | Spiller &spiller() override { return *SpillerInstance; } |
88 | |
89 | void enqueueImpl(const LiveInterval *LI) override { Queue.push(x: LI); } |
90 | |
91 | const LiveInterval *dequeue() override { |
92 | if (Queue.empty()) |
93 | return nullptr; |
94 | const LiveInterval *LI = Queue.top(); |
95 | Queue.pop(); |
96 | return LI; |
97 | } |
98 | |
99 | MCRegister selectOrSplit(const LiveInterval &VirtReg, |
100 | SmallVectorImpl<Register> &SplitVRegs) override; |
101 | |
102 | /// Perform register allocation. |
103 | bool runOnMachineFunction(MachineFunction &mf) override; |
104 | |
105 | MachineFunctionProperties getRequiredProperties() const override { |
106 | return MachineFunctionProperties().set( |
107 | MachineFunctionProperties::Property::NoPHIs); |
108 | } |
109 | |
110 | MachineFunctionProperties getClearedProperties() const override { |
111 | return MachineFunctionProperties().set( |
112 | MachineFunctionProperties::Property::IsSSA); |
113 | } |
114 | |
115 | // Helper for spilling all live virtual registers currently unified under preg |
116 | // that interfere with the most recently queried lvr. Return true if spilling |
117 | // was successful, and append any new spilled/split intervals to splitLVRs. |
118 | bool spillInterferences(const LiveInterval &VirtReg, MCRegister PhysReg, |
119 | SmallVectorImpl<Register> &SplitVRegs); |
120 | |
121 | static char ID; |
122 | }; |
123 | |
124 | char RABasic::ID = 0; |
125 | |
126 | } // end anonymous namespace |
127 | |
128 | char &llvm::RABasicID = RABasic::ID; |
129 | |
130 | INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic" , "Basic Register Allocator" , |
131 | false, false) |
132 | INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) |
133 | INITIALIZE_PASS_DEPENDENCY(SlotIndexes) |
134 | INITIALIZE_PASS_DEPENDENCY(LiveIntervals) |
135 | INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) |
136 | INITIALIZE_PASS_DEPENDENCY(MachineScheduler) |
137 | INITIALIZE_PASS_DEPENDENCY(LiveStacks) |
138 | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) |
139 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
140 | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
141 | INITIALIZE_PASS_DEPENDENCY(VirtRegMap) |
142 | INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix) |
143 | INITIALIZE_PASS_END(RABasic, "regallocbasic" , "Basic Register Allocator" , false, |
144 | false) |
145 | |
146 | bool RABasic::LRE_CanEraseVirtReg(Register VirtReg) { |
147 | LiveInterval &LI = LIS->getInterval(Reg: VirtReg); |
148 | if (VRM->hasPhys(virtReg: VirtReg)) { |
149 | Matrix->unassign(VirtReg: LI); |
150 | aboutToRemoveInterval(LI); |
151 | return true; |
152 | } |
153 | // Unassigned virtreg is probably in the priority queue. |
154 | // RegAllocBase will erase it after dequeueing. |
155 | // Nonetheless, clear the live-range so that the debug |
156 | // dump will show the right state for that VirtReg. |
157 | LI.clear(); |
158 | return false; |
159 | } |
160 | |
161 | void RABasic::LRE_WillShrinkVirtReg(Register VirtReg) { |
162 | if (!VRM->hasPhys(virtReg: VirtReg)) |
163 | return; |
164 | |
165 | // Register is assigned, put it back on the queue for reassignment. |
166 | LiveInterval &LI = LIS->getInterval(Reg: VirtReg); |
167 | Matrix->unassign(VirtReg: LI); |
168 | enqueue(LI: &LI); |
169 | } |
170 | |
171 | RABasic::RABasic(RegClassFilterFunc F): |
172 | MachineFunctionPass(ID), |
173 | RegAllocBase(F) { |
174 | } |
175 | |
176 | void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { |
177 | AU.setPreservesCFG(); |
178 | AU.addRequired<AAResultsWrapperPass>(); |
179 | AU.addPreserved<AAResultsWrapperPass>(); |
180 | AU.addRequired<LiveIntervals>(); |
181 | AU.addPreserved<LiveIntervals>(); |
182 | AU.addPreserved<SlotIndexes>(); |
183 | AU.addRequired<LiveDebugVariables>(); |
184 | AU.addPreserved<LiveDebugVariables>(); |
185 | AU.addRequired<LiveStacks>(); |
186 | AU.addPreserved<LiveStacks>(); |
187 | AU.addRequired<MachineBlockFrequencyInfo>(); |
188 | AU.addPreserved<MachineBlockFrequencyInfo>(); |
189 | AU.addRequiredID(ID&: MachineDominatorsID); |
190 | AU.addPreservedID(ID&: MachineDominatorsID); |
191 | AU.addRequired<MachineLoopInfo>(); |
192 | AU.addPreserved<MachineLoopInfo>(); |
193 | AU.addRequired<VirtRegMap>(); |
194 | AU.addPreserved<VirtRegMap>(); |
195 | AU.addRequired<LiveRegMatrix>(); |
196 | AU.addPreserved<LiveRegMatrix>(); |
197 | MachineFunctionPass::getAnalysisUsage(AU); |
198 | } |
199 | |
200 | void RABasic::releaseMemory() { |
201 | SpillerInstance.reset(); |
202 | } |
203 | |
204 | |
205 | // Spill or split all live virtual registers currently unified under PhysReg |
206 | // that interfere with VirtReg. The newly spilled or split live intervals are |
207 | // returned by appending them to SplitVRegs. |
208 | bool RABasic::spillInterferences(const LiveInterval &VirtReg, |
209 | MCRegister PhysReg, |
210 | SmallVectorImpl<Register> &SplitVRegs) { |
211 | // Record each interference and determine if all are spillable before mutating |
212 | // either the union or live intervals. |
213 | SmallVector<const LiveInterval *, 8> Intfs; |
214 | |
215 | // Collect interferences assigned to any alias of the physical register. |
216 | for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) { |
217 | LiveIntervalUnion::Query &Q = Matrix->query(LR: VirtReg, RegUnit: Unit); |
218 | for (const auto *Intf : reverse(C: Q.interferingVRegs())) { |
219 | if (!Intf->isSpillable() || Intf->weight() > VirtReg.weight()) |
220 | return false; |
221 | Intfs.push_back(Elt: Intf); |
222 | } |
223 | } |
224 | LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI) |
225 | << " interferences with " << VirtReg << "\n" ); |
226 | assert(!Intfs.empty() && "expected interference" ); |
227 | |
228 | // Spill each interfering vreg allocated to PhysReg or an alias. |
229 | for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { |
230 | const LiveInterval &Spill = *Intfs[i]; |
231 | |
232 | // Skip duplicates. |
233 | if (!VRM->hasPhys(virtReg: Spill.reg())) |
234 | continue; |
235 | |
236 | // Deallocate the interfering vreg by removing it from the union. |
237 | // A LiveInterval instance may not be in a union during modification! |
238 | Matrix->unassign(VirtReg: Spill); |
239 | |
240 | // Spill the extracted interval. |
241 | LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); |
242 | spiller().spill(LRE); |
243 | } |
244 | return true; |
245 | } |
246 | |
247 | // Driver for the register assignment and splitting heuristics. |
248 | // Manages iteration over the LiveIntervalUnions. |
249 | // |
250 | // This is a minimal implementation of register assignment and splitting that |
251 | // spills whenever we run out of registers. |
252 | // |
253 | // selectOrSplit can only be called once per live virtual register. We then do a |
254 | // single interference test for each register the correct class until we find an |
255 | // available register. So, the number of interference tests in the worst case is |
256 | // |vregs| * |machineregs|. And since the number of interference tests is |
257 | // minimal, there is no value in caching them outside the scope of |
258 | // selectOrSplit(). |
259 | MCRegister RABasic::selectOrSplit(const LiveInterval &VirtReg, |
260 | SmallVectorImpl<Register> &SplitVRegs) { |
261 | // Populate a list of physical register spill candidates. |
262 | SmallVector<MCRegister, 8> PhysRegSpillCands; |
263 | |
264 | // Check for an available register in this class. |
265 | auto Order = |
266 | AllocationOrder::create(VirtReg: VirtReg.reg(), VRM: *VRM, RegClassInfo, Matrix); |
267 | for (MCRegister PhysReg : Order) { |
268 | assert(PhysReg.isValid()); |
269 | // Check for interference in PhysReg |
270 | switch (Matrix->checkInterference(VirtReg, PhysReg)) { |
271 | case LiveRegMatrix::IK_Free: |
272 | // PhysReg is available, allocate it. |
273 | return PhysReg; |
274 | |
275 | case LiveRegMatrix::IK_VirtReg: |
276 | // Only virtual registers in the way, we may be able to spill them. |
277 | PhysRegSpillCands.push_back(Elt: PhysReg); |
278 | continue; |
279 | |
280 | default: |
281 | // RegMask or RegUnit interference. |
282 | continue; |
283 | } |
284 | } |
285 | |
286 | // Try to spill another interfering reg with less spill weight. |
287 | for (MCRegister &PhysReg : PhysRegSpillCands) { |
288 | if (!spillInterferences(VirtReg, PhysReg, SplitVRegs)) |
289 | continue; |
290 | |
291 | assert(!Matrix->checkInterference(VirtReg, PhysReg) && |
292 | "Interference after spill." ); |
293 | // Tell the caller to allocate to this newly freed physical register. |
294 | return PhysReg; |
295 | } |
296 | |
297 | // No other spill candidates were found, so spill the current VirtReg. |
298 | LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); |
299 | if (!VirtReg.isSpillable()) |
300 | return ~0u; |
301 | LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); |
302 | spiller().spill(LRE); |
303 | |
304 | // The live virtual register requesting allocation was spilled, so tell |
305 | // the caller not to allocate anything during this round. |
306 | return 0; |
307 | } |
308 | |
309 | bool RABasic::runOnMachineFunction(MachineFunction &mf) { |
310 | LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" |
311 | << "********** Function: " << mf.getName() << '\n'); |
312 | |
313 | MF = &mf; |
314 | RegAllocBase::init(vrm&: getAnalysis<VirtRegMap>(), |
315 | lis&: getAnalysis<LiveIntervals>(), |
316 | mat&: getAnalysis<LiveRegMatrix>()); |
317 | VirtRegAuxInfo VRAI(*MF, *LIS, *VRM, getAnalysis<MachineLoopInfo>(), |
318 | getAnalysis<MachineBlockFrequencyInfo>()); |
319 | VRAI.calculateSpillWeightsAndHints(); |
320 | |
321 | SpillerInstance.reset(p: createInlineSpiller(Pass&: *this, MF&: *MF, VRM&: *VRM, VRAI)); |
322 | |
323 | allocatePhysRegs(); |
324 | postOptimization(); |
325 | |
326 | // Diagnostic output before rewriting |
327 | LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n" ); |
328 | |
329 | releaseMemory(); |
330 | return true; |
331 | } |
332 | |
333 | FunctionPass* llvm::createBasicRegisterAllocator() { |
334 | return new RABasic(); |
335 | } |
336 | |
337 | FunctionPass* llvm::createBasicRegisterAllocator(RegClassFilterFunc F) { |
338 | return new RABasic(F); |
339 | } |
340 | |