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