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