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.addRequired<MachineDominatorTreeWrapperPass>();
104 AU.addRequiredID(ID&: MachineDominatorsID);
105 AU.addRequired<MachineLoopInfoWrapperPass>();
106 AU.addRequired<VirtRegMapWrapperLegacy>();
107 AU.addPreserved<VirtRegMapWrapperLegacy>();
108 AU.addRequired<LiveRegMatrixWrapperLegacy>();
109 AU.addPreserved<LiveRegMatrixWrapperLegacy>();
110 MachineFunctionPass::getAnalysisUsage(AU);
111}
112
113void RABasic::releaseMemory() {
114 SpillerInstance.reset();
115}
116
117
118// Spill or split all live virtual registers currently unified under PhysReg
119// that interfere with VirtReg. The newly spilled or split live intervals are
120// returned by appending them to SplitVRegs.
121bool RABasic::spillInterferences(const LiveInterval &VirtReg,
122 MCRegister PhysReg,
123 SmallVectorImpl<Register> &SplitVRegs) {
124 // Record each interference and determine if all are spillable before mutating
125 // either the union or live intervals.
126 SmallVector<const LiveInterval *, 8> Intfs;
127
128 // Collect interferences assigned to any alias of the physical register.
129 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
130 LiveIntervalUnion::Query &Q = Matrix->query(LR: VirtReg, RegUnit: Unit);
131 for (const auto *Intf : reverse(C: Q.interferingVRegs())) {
132 if (!Intf->isSpillable() || Intf->weight() > VirtReg.weight())
133 return false;
134 Intfs.push_back(Elt: Intf);
135 }
136 }
137 LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI)
138 << " interferences with " << VirtReg << "\n");
139 assert(!Intfs.empty() && "expected interference");
140
141 // Spill each interfering vreg allocated to PhysReg or an alias.
142 for (const LiveInterval *Spill : Intfs) {
143 // Skip duplicates.
144 if (!VRM->hasPhys(virtReg: Spill->reg()))
145 continue;
146
147 // Deallocate the interfering vreg by removing it from the union.
148 // A LiveInterval instance may not be in a union during modification!
149 Matrix->unassign(VirtReg: *Spill);
150
151 // Spill the extracted interval.
152 LiveRangeEdit LRE(Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
153 spiller().spill(LRE);
154 }
155 return true;
156}
157
158// Driver for the register assignment and splitting heuristics.
159// Manages iteration over the LiveIntervalUnions.
160//
161// This is a minimal implementation of register assignment and splitting that
162// spills whenever we run out of registers.
163//
164// selectOrSplit can only be called once per live virtual register. We then do a
165// single interference test for each register the correct class until we find an
166// available register. So, the number of interference tests in the worst case is
167// |vregs| * |machineregs|. And since the number of interference tests is
168// minimal, there is no value in caching them outside the scope of
169// selectOrSplit().
170MCRegister RABasic::selectOrSplit(const LiveInterval &VirtReg,
171 SmallVectorImpl<Register> &SplitVRegs) {
172 // Populate a list of physical register spill candidates.
173 SmallVector<MCRegister, 8> PhysRegSpillCands;
174
175 // Check for an available register in this class.
176 auto Order =
177 AllocationOrder::create(VirtReg: VirtReg.reg(), VRM: *VRM, RegClassInfo, Matrix);
178 for (MCRegister PhysReg : Order) {
179 assert(PhysReg.isValid());
180 // Check for interference in PhysReg
181 switch (Matrix->checkInterference(VirtReg, PhysReg)) {
182 case LiveRegMatrix::IK_Free:
183 // PhysReg is available, allocate it.
184 return PhysReg;
185
186 case LiveRegMatrix::IK_VirtReg:
187 // Only virtual registers in the way, we may be able to spill them.
188 PhysRegSpillCands.push_back(Elt: PhysReg);
189 continue;
190
191 default:
192 // RegMask or RegUnit interference.
193 continue;
194 }
195 }
196
197 // Try to spill another interfering reg with less spill weight.
198 for (MCRegister &PhysReg : PhysRegSpillCands) {
199 if (!spillInterferences(VirtReg, PhysReg, SplitVRegs))
200 continue;
201
202 assert(!Matrix->checkInterference(VirtReg, PhysReg) &&
203 "Interference after spill.");
204 // Tell the caller to allocate to this newly freed physical register.
205 return PhysReg;
206 }
207
208 // No other spill candidates were found, so spill the current VirtReg.
209 LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
210 if (!VirtReg.isSpillable())
211 return ~0u;
212 LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
213 spiller().spill(LRE);
214
215 // The live virtual register requesting allocation was spilled, so tell
216 // the caller not to allocate anything during this round.
217 return 0;
218}
219
220bool RABasic::runOnMachineFunction(MachineFunction &mf) {
221 LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
222 << "********** Function: " << mf.getName() << '\n');
223
224 MF = &mf;
225 auto &MBFI = getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
226 auto &LiveStks = getAnalysis<LiveStacksWrapperLegacy>().getLS();
227 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
228
229 RegAllocBase::init(vrm&: getAnalysis<VirtRegMapWrapperLegacy>().getVRM(),
230 lis&: getAnalysis<LiveIntervalsWrapperPass>().getLIS(),
231 mat&: getAnalysis<LiveRegMatrixWrapperLegacy>().getLRM());
232 VirtRegAuxInfo VRAI(*MF, *LIS, *VRM,
233 getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI,
234 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
235 VRAI.calculateSpillWeightsAndHints();
236
237 SpillerInstance.reset(
238 p: createInlineSpiller(Analyses: {.LIS: *LIS, .LSS: LiveStks, .MDT: MDT, .MBFI: MBFI}, MF&: *MF, VRM&: *VRM, VRAI));
239
240 allocatePhysRegs();
241 postOptimization();
242
243 // Diagnostic output before rewriting
244 LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
245
246 releaseMemory();
247 return true;
248}
249
250FunctionPass* llvm::createBasicRegisterAllocator() {
251 return new RABasic();
252}
253
254FunctionPass *llvm::createBasicRegisterAllocator(RegAllocFilterFunc F) {
255 return new RABasic(F);
256}
257