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/// \file
10/// This file defines the RABasic function pass, which provides a minimal
11/// implementation of the basic register allocator.
12///
13//===----------------------------------------------------------------------===//
14
15#include "RegAllocBasic.h"
16#include "AllocationOrder.h"
17#include "llvm/Analysis/AliasAnalysis.h"
18#include "llvm/Analysis/ProfileSummaryInfo.h"
19#include "llvm/CodeGen/CalcSpillWeights.h"
20#include "llvm/CodeGen/LiveDebugVariables.h"
21#include "llvm/CodeGen/LiveIntervals.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/MachineLoopInfo.h"
27#include "llvm/CodeGen/Passes.h"
28#include "llvm/CodeGen/RegAllocRegistry.h"
29#include "llvm/CodeGen/VirtRegMap.h"
30#include "llvm/Pass.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/raw_ostream.h"
33
34using namespace llvm;
35
36#define DEBUG_TYPE "regalloc"
37
38static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
39 createBasicRegisterAllocator);
40
41char RABasic::ID = 0;
42
43char &llvm::RABasicID = RABasic::ID;
44
45INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator",
46 false, false)
47INITIALIZE_PASS_DEPENDENCY(LiveDebugVariablesWrapperLegacy)
48INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
49INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
50INITIALIZE_PASS_DEPENDENCY(RegisterCoalescerLegacy)
51INITIALIZE_PASS_DEPENDENCY(MachineSchedulerLegacy)
52INITIALIZE_PASS_DEPENDENCY(LiveStacksWrapperLegacy)
53INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
54INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
55INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
56INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)
57INITIALIZE_PASS_DEPENDENCY(LiveRegMatrixWrapperLegacy)
58INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
59INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false,
60 false)
61
62bool RABasic::LRE_CanEraseVirtReg(Register VirtReg) {
63 LiveInterval &LI = LIS->getInterval(Reg: VirtReg);
64 if (VRM->hasPhys(virtReg: VirtReg)) {
65 Matrix->unassign(VirtReg: LI);
66 aboutToRemoveInterval(LI);
67 return true;
68 }
69 // Unassigned virtreg is probably in the priority queue.
70 // RegAllocBase will erase it after dequeueing.
71 // Nonetheless, clear the live-range so that the debug
72 // dump will show the right state for that VirtReg.
73 LI.clear();
74 return false;
75}
76
77void RABasic::LRE_WillShrinkVirtReg(Register VirtReg) {
78 if (!VRM->hasPhys(virtReg: VirtReg))
79 return;
80
81 // Register is assigned, put it back on the queue for reassignment.
82 LiveInterval &LI = LIS->getInterval(Reg: VirtReg);
83 Matrix->unassign(VirtReg: LI);
84 enqueue(LI: &LI);
85}
86
87RABasic::RABasic(RegAllocFilterFunc F)
88 : MachineFunctionPass(ID), RegAllocBase(F) {}
89
90void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
91 AU.setPreservesCFG();
92 AU.addRequired<AAResultsWrapperPass>();
93 AU.addPreserved<AAResultsWrapperPass>();
94 AU.addRequired<LiveIntervalsWrapperPass>();
95 AU.addPreserved<LiveIntervalsWrapperPass>();
96 AU.addPreserved<SlotIndexesWrapperPass>();
97 AU.addRequired<LiveDebugVariablesWrapperLegacy>();
98 AU.addPreserved<LiveDebugVariablesWrapperLegacy>();
99 AU.addRequired<LiveStacksWrapperLegacy>();
100 AU.addPreserved<LiveStacksWrapperLegacy>();
101 AU.addRequired<ProfileSummaryInfoWrapperPass>();
102 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
103 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
104 AU.addRequired<MachineDominatorTreeWrapperPass>();
105 AU.addRequiredID(ID&: MachineDominatorsID);
106 AU.addPreservedID(ID&: MachineDominatorsID);
107 AU.addRequired<MachineLoopInfoWrapperPass>();
108 AU.addPreserved<MachineLoopInfoWrapperPass>();
109 AU.addRequired<VirtRegMapWrapperLegacy>();
110 AU.addPreserved<VirtRegMapWrapperLegacy>();
111 AU.addRequired<LiveRegMatrixWrapperLegacy>();
112 AU.addPreserved<LiveRegMatrixWrapperLegacy>();
113 MachineFunctionPass::getAnalysisUsage(AU);
114}
115
116void RABasic::releaseMemory() {
117 SpillerInstance.reset();
118}
119
120
121// Spill or split all live virtual registers currently unified under PhysReg
122// that interfere with VirtReg. The newly spilled or split live intervals are
123// returned by appending them to SplitVRegs.
124bool RABasic::spillInterferences(const LiveInterval &VirtReg,
125 MCRegister PhysReg,
126 SmallVectorImpl<Register> &SplitVRegs) {
127 // Record each interference and determine if all are spillable before mutating
128 // either the union or live intervals.
129 SmallVector<const LiveInterval *, 8> Intfs;
130
131 // Collect interferences assigned to any alias of the physical register.
132 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
133 LiveIntervalUnion::Query &Q = Matrix->query(LR: VirtReg, RegUnit: Unit);
134 for (const auto *Intf : reverse(C: Q.interferingVRegs())) {
135 if (!Intf->isSpillable() || Intf->weight() > VirtReg.weight())
136 return false;
137 Intfs.push_back(Elt: Intf);
138 }
139 }
140 LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI)
141 << " interferences with " << VirtReg << "\n");
142 assert(!Intfs.empty() && "expected interference");
143
144 // Spill each interfering vreg allocated to PhysReg or an alias.
145 for (const LiveInterval *Spill : Intfs) {
146 // Skip duplicates.
147 if (!VRM->hasPhys(virtReg: Spill->reg()))
148 continue;
149
150 // Deallocate the interfering vreg by removing it from the union.
151 // A LiveInterval instance may not be in a union during modification!
152 Matrix->unassign(VirtReg: *Spill);
153
154 // Spill the extracted interval.
155 LiveRangeEdit LRE(Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
156 spiller().spill(LRE);
157 }
158 return true;
159}
160
161// Driver for the register assignment and splitting heuristics.
162// Manages iteration over the LiveIntervalUnions.
163//
164// This is a minimal implementation of register assignment and splitting that
165// spills whenever we run out of registers.
166//
167// selectOrSplit can only be called once per live virtual register. We then do a
168// single interference test for each register the correct class until we find an
169// available register. So, the number of interference tests in the worst case is
170// |vregs| * |machineregs|. And since the number of interference tests is
171// minimal, there is no value in caching them outside the scope of
172// selectOrSplit().
173MCRegister RABasic::selectOrSplit(const LiveInterval &VirtReg,
174 SmallVectorImpl<Register> &SplitVRegs) {
175 // Populate a list of physical register spill candidates.
176 SmallVector<MCRegister, 8> PhysRegSpillCands;
177
178 // Check for an available register in this class.
179 auto Order =
180 AllocationOrder::create(VirtReg: VirtReg.reg(), VRM: *VRM, RegClassInfo, Matrix);
181 for (MCRegister PhysReg : Order) {
182 assert(PhysReg.isValid());
183 // Check for interference in PhysReg
184 switch (Matrix->checkInterference(VirtReg, PhysReg)) {
185 case LiveRegMatrix::IK_Free:
186 // PhysReg is available, allocate it.
187 return PhysReg;
188
189 case LiveRegMatrix::IK_VirtReg:
190 // Only virtual registers in the way, we may be able to spill them.
191 PhysRegSpillCands.push_back(Elt: PhysReg);
192 continue;
193
194 default:
195 // RegMask or RegUnit interference.
196 continue;
197 }
198 }
199
200 // Try to spill another interfering reg with less spill weight.
201 for (MCRegister &PhysReg : PhysRegSpillCands) {
202 if (!spillInterferences(VirtReg, PhysReg, SplitVRegs))
203 continue;
204
205 assert(!Matrix->checkInterference(VirtReg, PhysReg) &&
206 "Interference after spill.");
207 // Tell the caller to allocate to this newly freed physical register.
208 return PhysReg;
209 }
210
211 // No other spill candidates were found, so spill the current VirtReg.
212 LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
213 if (!VirtReg.isSpillable())
214 return ~0u;
215 LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
216 spiller().spill(LRE);
217
218 // The live virtual register requesting allocation was spilled, so tell
219 // the caller not to allocate anything during this round.
220 return 0;
221}
222
223bool RABasic::runOnMachineFunction(MachineFunction &mf) {
224 LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
225 << "********** Function: " << mf.getName() << '\n');
226
227 MF = &mf;
228 auto &MBFI = getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
229 auto &LiveStks = getAnalysis<LiveStacksWrapperLegacy>().getLS();
230 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
231
232 RegAllocBase::init(vrm&: getAnalysis<VirtRegMapWrapperLegacy>().getVRM(),
233 lis&: getAnalysis<LiveIntervalsWrapperPass>().getLIS(),
234 mat&: getAnalysis<LiveRegMatrixWrapperLegacy>().getLRM());
235 VirtRegAuxInfo VRAI(*MF, *LIS, *VRM,
236 getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI,
237 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
238 VRAI.calculateSpillWeightsAndHints();
239
240 SpillerInstance.reset(
241 p: createInlineSpiller(Analyses: {.LIS: *LIS, .LSS: LiveStks, .MDT: MDT, .MBFI: MBFI}, MF&: *MF, VRM&: *VRM, VRAI));
242
243 allocatePhysRegs();
244 postOptimization();
245
246 // Diagnostic output before rewriting
247 LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
248
249 releaseMemory();
250 return true;
251}
252
253FunctionPass* llvm::createBasicRegisterAllocator() {
254 return new RABasic();
255}
256
257FunctionPass *llvm::createBasicRegisterAllocator(RegAllocFilterFunc F) {
258 return new RABasic(F);
259}
260