/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/RegAllocBasic.cpp
Line | Count | Source (jump to first uncovered line) |
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/LiveIntervalAnalysis.h" |
22 | | #include "llvm/CodeGen/LiveRangeEdit.h" |
23 | | #include "llvm/CodeGen/LiveRegMatrix.h" |
24 | | #include "llvm/CodeGen/LiveStackAnalysis.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/VirtRegMap.h" |
33 | | #include "llvm/PassAnalysisSupport.h" |
34 | | #include "llvm/Support/Debug.h" |
35 | | #include "llvm/Support/raw_ostream.h" |
36 | | #include "llvm/Target/TargetRegisterInfo.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 | 50.0k | bool operator()(LiveInterval *A, LiveInterval *B) const { |
50 | 50.0k | return A->weight < B->weight; |
51 | 50.0k | } |
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 | 808 | Spiller &spiller() override { return *SpillerInstance; } |
91 | | |
92 | 3.74k | void enqueue(LiveInterval *LI) override { |
93 | 3.74k | Queue.push(LI); |
94 | 3.74k | } |
95 | | |
96 | 3.96k | LiveInterval *dequeue() override { |
97 | 3.96k | if (Queue.empty()) |
98 | 217 | return nullptr; |
99 | 3.74k | LiveInterval *LI = Queue.top(); |
100 | 3.74k | Queue.pop(); |
101 | 3.74k | return LI; |
102 | 3.74k | } |
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 | 44 | } |
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 | 36.7k | INITIALIZE_PASS_BEGIN36.7k (RABasic, "regallocbasic", "Basic Register Allocator",
|
131 | 36.7k | false, false) |
132 | 36.7k | INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) |
133 | 36.7k | INITIALIZE_PASS_DEPENDENCY(SlotIndexes) |
134 | 36.7k | INITIALIZE_PASS_DEPENDENCY(LiveIntervals) |
135 | 36.7k | INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) |
136 | 36.7k | INITIALIZE_PASS_DEPENDENCY(MachineScheduler) |
137 | 36.7k | INITIALIZE_PASS_DEPENDENCY(LiveStacks) |
138 | 36.7k | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
139 | 36.7k | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
140 | 36.7k | INITIALIZE_PASS_DEPENDENCY(VirtRegMap) |
141 | 36.7k | INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix) |
142 | 36.7k | INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false, |
143 | | false) |
144 | | |
145 | 836 | bool RABasic::LRE_CanEraseVirtReg(unsigned VirtReg) { |
146 | 836 | LiveInterval &LI = LIS->getInterval(VirtReg); |
147 | 836 | if (VRM->hasPhys(VirtReg)836 ) { |
148 | 0 | Matrix->unassign(LI); |
149 | 0 | aboutToRemoveInterval(LI); |
150 | 0 | return true; |
151 | 0 | } |
152 | 836 | // Unassigned virtreg is probably in the priority queue. |
153 | 836 | // RegAllocBase will erase it after dequeueing. |
154 | 836 | // Nonetheless, clear the live-range so that the debug |
155 | 836 | // dump will show the right state for that VirtReg. |
156 | 836 | LI.clear(); |
157 | 836 | return false; |
158 | 836 | } |
159 | | |
160 | 252 | void RABasic::LRE_WillShrinkVirtReg(unsigned VirtReg) { |
161 | 252 | if (!VRM->hasPhys(VirtReg)) |
162 | 251 | return; |
163 | 1 | |
164 | 1 | // 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 | 1 | } |
169 | | |
170 | 44 | RABasic::RABasic(): MachineFunctionPass(ID) { |
171 | 44 | } |
172 | | |
173 | 44 | void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { |
174 | 44 | AU.setPreservesCFG(); |
175 | 44 | AU.addRequired<AAResultsWrapperPass>(); |
176 | 44 | AU.addPreserved<AAResultsWrapperPass>(); |
177 | 44 | AU.addRequired<LiveIntervals>(); |
178 | 44 | AU.addPreserved<LiveIntervals>(); |
179 | 44 | AU.addPreserved<SlotIndexes>(); |
180 | 44 | AU.addRequired<LiveDebugVariables>(); |
181 | 44 | AU.addPreserved<LiveDebugVariables>(); |
182 | 44 | AU.addRequired<LiveStacks>(); |
183 | 44 | AU.addPreserved<LiveStacks>(); |
184 | 44 | AU.addRequired<MachineBlockFrequencyInfo>(); |
185 | 44 | AU.addPreserved<MachineBlockFrequencyInfo>(); |
186 | 44 | AU.addRequiredID(MachineDominatorsID); |
187 | 44 | AU.addPreservedID(MachineDominatorsID); |
188 | 44 | AU.addRequired<MachineLoopInfo>(); |
189 | 44 | AU.addPreserved<MachineLoopInfo>(); |
190 | 44 | AU.addRequired<VirtRegMap>(); |
191 | 44 | AU.addPreserved<VirtRegMap>(); |
192 | 44 | AU.addRequired<LiveRegMatrix>(); |
193 | 44 | AU.addPreserved<LiveRegMatrix>(); |
194 | 44 | MachineFunctionPass::getAnalysisUsage(AU); |
195 | 44 | } |
196 | | |
197 | 434 | void RABasic::releaseMemory() { |
198 | 434 | SpillerInstance.reset(); |
199 | 434 | } |
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 | | bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, |
206 | 29.4k | SmallVectorImpl<unsigned> &SplitVRegs) { |
207 | 29.4k | // Record each interference and determine if all are spillable before mutating |
208 | 29.4k | // either the union or live intervals. |
209 | 29.4k | SmallVector<LiveInterval*, 8> Intfs; |
210 | 29.4k | |
211 | 29.4k | // Collect interferences assigned to any alias of the physical register. |
212 | 29.4k | for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid()29.4k ; ++Units12 ) { |
213 | 29.4k | LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); |
214 | 29.4k | Q.collectInterferingVRegs(); |
215 | 29.4k | for (unsigned i = Q.interferingVRegs().size(); i29.4k ; --i10 ) { |
216 | 29.4k | LiveInterval *Intf = Q.interferingVRegs()[i - 1]; |
217 | 29.4k | if (!Intf->isSpillable() || 29.4k Intf->weight > VirtReg.weight28.8k ) |
218 | 29.4k | return false; |
219 | 10 | Intfs.push_back(Intf); |
220 | 10 | } |
221 | 29.4k | } |
222 | 7 | DEBUG7 (dbgs() << "spilling " << TRI->getName(PhysReg) << |
223 | 7 | " interferences with " << VirtReg << "\n"); |
224 | 7 | assert(!Intfs.empty() && "expected interference"); |
225 | 7 | |
226 | 7 | // Spill each interfering vreg allocated to PhysReg or an alias. |
227 | 17 | for (unsigned i = 0, e = Intfs.size(); i != e17 ; ++i10 ) { |
228 | 10 | LiveInterval &Spill = *Intfs[i]; |
229 | 10 | |
230 | 10 | // Skip duplicates. |
231 | 10 | if (!VRM->hasPhys(Spill.reg)) |
232 | 3 | continue; |
233 | 7 | |
234 | 7 | // Deallocate the interfering vreg by removing it from the union. |
235 | 7 | // A LiveInterval instance may not be in a union during modification! |
236 | 7 | Matrix->unassign(Spill); |
237 | 7 | |
238 | 7 | // Spill the extracted interval. |
239 | 7 | LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); |
240 | 7 | spiller().spill(LRE); |
241 | 7 | } |
242 | 7 | return true; |
243 | 29.4k | } |
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 | | unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, |
258 | 3.74k | SmallVectorImpl<unsigned> &SplitVRegs) { |
259 | 3.74k | // Populate a list of physical register spill candidates. |
260 | 3.74k | SmallVector<unsigned, 8> PhysRegSpillCands; |
261 | 3.74k | |
262 | 3.74k | // Check for an available register in this class. |
263 | 3.74k | AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix); |
264 | 114k | while (unsigned PhysReg114k = Order.next()) { |
265 | 113k | // Check for interference in PhysReg |
266 | 113k | switch (Matrix->checkInterference(VirtReg, PhysReg)) { |
267 | 3.15k | case LiveRegMatrix::IK_Free: |
268 | 3.15k | // PhysReg is available, allocate it. |
269 | 3.15k | return PhysReg; |
270 | 113k | |
271 | 37.7k | case LiveRegMatrix::IK_VirtReg: |
272 | 37.7k | // Only virtual registers in the way, we may be able to spill them. |
273 | 37.7k | PhysRegSpillCands.push_back(PhysReg); |
274 | 37.7k | continue; |
275 | 113k | |
276 | 72.9k | default: |
277 | 72.9k | // RegMask or RegUnit interference. |
278 | 72.9k | continue; |
279 | 113k | } |
280 | 113k | } |
281 | 3.74k | |
282 | 3.74k | // Try to spill another interfering reg with less spill weight. |
283 | 594 | for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), |
284 | 30.0k | PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE30.0k ; ++PhysRegI29.4k ) { |
285 | 29.4k | if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) |
286 | 29.4k | continue; |
287 | 7 | |
288 | 29.4k | assert(!Matrix->checkInterference(VirtReg, *PhysRegI) && |
289 | 7 | "Interference after spill."); |
290 | 7 | // Tell the caller to allocate to this newly freed physical register. |
291 | 7 | return *PhysRegI; |
292 | 7 | } |
293 | 594 | |
294 | 594 | // No other spill candidates were found, so spill the current VirtReg. |
295 | 587 | DEBUG587 (dbgs() << "spilling: " << VirtReg << '\n'); |
296 | 587 | if (!VirtReg.isSpillable()) |
297 | 3 | return ~0u; |
298 | 584 | LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); |
299 | 584 | spiller().spill(LRE); |
300 | 584 | |
301 | 584 | // The live virtual register requesting allocation was spilled, so tell |
302 | 584 | // the caller not to allocate anything during this round. |
303 | 584 | return 0; |
304 | 584 | } |
305 | | |
306 | 217 | bool RABasic::runOnMachineFunction(MachineFunction &mf) { |
307 | 217 | DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" |
308 | 217 | << "********** Function: " |
309 | 217 | << mf.getName() << '\n'); |
310 | 217 | |
311 | 217 | MF = &mf; |
312 | 217 | RegAllocBase::init(getAnalysis<VirtRegMap>(), |
313 | 217 | getAnalysis<LiveIntervals>(), |
314 | 217 | getAnalysis<LiveRegMatrix>()); |
315 | 217 | |
316 | 217 | calculateSpillWeightsAndHints(*LIS, *MF, VRM, |
317 | 217 | getAnalysis<MachineLoopInfo>(), |
318 | 217 | getAnalysis<MachineBlockFrequencyInfo>()); |
319 | 217 | |
320 | 217 | SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); |
321 | 217 | |
322 | 217 | allocatePhysRegs(); |
323 | 217 | postOptimization(); |
324 | 217 | |
325 | 217 | // Diagnostic output before rewriting |
326 | 217 | DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); |
327 | 217 | |
328 | 217 | releaseMemory(); |
329 | 217 | return true; |
330 | 217 | } |
331 | | |
332 | | FunctionPass* llvm::createBasicRegisterAllocator() |
333 | 42 | { |
334 | 42 | return new RABasic(); |
335 | 42 | } |