1 //===-- RegAllocBasic.cpp - basic register allocator ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the RABasic function pass, which provides a minimal
11 // implementation of the basic register allocator.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "regalloc"
16 #include "LiveIntervalUnion.h"
17 #include "RegAllocBase.h"
18 #include "RenderMachineFunction.h"
20 #include "VirtRegMap.h"
21 #include "VirtRegRewriter.h"
22 #include "llvm/Function.h"
23 #include "llvm/PassAnalysisSupport.h"
24 #include "llvm/CodeGen/CalcSpillWeights.h"
25 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
26 #include "llvm/CodeGen/LiveStackAnalysis.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineInstr.h"
29 #include "llvm/CodeGen/MachineLoopInfo.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/CodeGen/RegAllocRegistry.h"
33 #include "llvm/CodeGen/RegisterCoalescer.h"
34 #include "llvm/Target/TargetMachine.h"
35 #include "llvm/Target/TargetOptions.h"
36 #include "llvm/Target/TargetRegisterInfo.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/raw_ostream.h"
46 static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
47 createBasicRegisterAllocator);
51 /// RABasic provides a minimal implementation of the basic register allocation
52 /// algorithm. It prioritizes live virtual registers by spill weight and spills
53 /// whenever a register is unavailable. This is not practical in production but
54 /// provides a useful baseline both for measuring other allocators and comparing
55 /// the speed of the basic algorithm against other styles of allocators.
56 class RABasic : public MachineFunctionPass, public RegAllocBase
60 const TargetMachine *tm_;
61 MachineRegisterInfo *mri_;
65 RenderMachineFunction *rmf_;
68 std::auto_ptr<Spiller> spiller_;
73 /// Return the pass name.
74 virtual const char* getPassName() const {
75 return "Basic Register Allocator";
78 /// RABasic analysis usage.
79 virtual void getAnalysisUsage(AnalysisUsage &au) const;
81 virtual void releaseMemory();
83 virtual unsigned selectOrSplit(LiveInterval &lvr,
84 SmallVectorImpl<LiveInterval*> &splitLVRs);
86 void spillInterferences(unsigned preg,
87 SmallVectorImpl<LiveInterval*> &splitLVRs);
89 /// Perform register allocation.
90 virtual bool runOnMachineFunction(MachineFunction &mf);
97 } // end anonymous namespace
99 // We should not need to publish the initializer as long as no other passes
101 #if 0 // disable INITIALIZE_PASS
102 INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
103 "Basic Register Allocator", false, false)
104 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
105 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
106 INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
107 INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
108 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
109 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
110 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
112 INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
114 INITIALIZE_PASS_END(RABasic, "basic-regalloc",
115 "Basic Register Allocator", false, false)
116 #endif // disable INITIALIZE_PASS
118 RABasic::RABasic(): MachineFunctionPass(ID) {
119 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
120 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
121 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
122 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
123 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
124 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
125 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
126 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
127 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
128 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
131 void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
132 au.setPreservesCFG();
133 au.addRequired<LiveIntervals>();
134 au.addPreserved<SlotIndexes>();
136 au.addRequiredID(StrongPHIEliminationID);
137 au.addRequiredTransitive<RegisterCoalescer>();
138 au.addRequired<CalculateSpillWeights>();
139 au.addRequired<LiveStacks>();
140 au.addPreserved<LiveStacks>();
141 au.addRequiredID(MachineDominatorsID);
142 au.addPreservedID(MachineDominatorsID);
143 au.addRequired<MachineLoopInfo>();
144 au.addPreserved<MachineLoopInfo>();
145 au.addRequired<VirtRegMap>();
146 au.addPreserved<VirtRegMap>();
147 DEBUG(au.addRequired<RenderMachineFunction>());
148 MachineFunctionPass::getAnalysisUsage(au);
151 void RABasic::releaseMemory() {
153 RegAllocBase::releaseMemory();
156 //===----------------------------------------------------------------------===//
157 // RegAllocBase Implementation
158 //===----------------------------------------------------------------------===//
160 // Instantiate a LiveIntervalUnion for each physical register.
161 void RegAllocBase::LIUArray::init(unsigned nRegs) {
162 array_.reset(new LiveIntervalUnion[nRegs]);
164 for (unsigned pr = 0; pr < nRegs; ++pr) {
169 void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
170 LiveIntervals &lis) {
174 physReg2liu_.init(tri_->getNumRegs());
175 // Cache an interferece query for each physical reg
176 queries_.reset(new LiveIntervalUnion::Query[physReg2liu_.numRegs()]);
179 void RegAllocBase::LIUArray::clear() {
184 void RegAllocBase::releaseMemory() {
185 physReg2liu_.clear();
189 /// This class defines a queue of live virtual registers prioritized by spill
190 /// weight. The heaviest vreg is popped first.
192 /// Currently, this is trivial wrapper that gives us an opaque type in the
193 /// header, but we may later give it a virtual interface for register allocators
194 /// to override the priority queue comparator.
195 class LiveVirtRegQueue {
196 typedef std::priority_queue
197 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
201 // Is the queue empty?
202 bool empty() { return pq_.empty(); }
204 // Get the highest priority lvr (top + pop)
205 LiveInterval *get() {
206 LiveInterval *lvr = pq_.top();
210 // Add this lvr to the queue
211 void push(LiveInterval *lvr) {
215 } // end namespace llvm
217 // Visit all the live virtual registers. If they are already assigned to a
218 // physical register, unify them with the corresponding LiveIntervalUnion,
219 // otherwise push them on the priority queue for later assignment.
220 void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
221 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
222 liItr != liEnd; ++liItr) {
223 unsigned reg = liItr->first;
224 LiveInterval &li = *liItr->second;
225 if (TargetRegisterInfo::isPhysicalRegister(reg)) {
226 physReg2liu_[reg].unify(li);
234 // Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
235 // selectOrSplit implementation.
236 void RegAllocBase::allocatePhysRegs() {
237 LiveVirtRegQueue lvrQ;
238 seedLiveVirtRegs(lvrQ);
239 while (!lvrQ.empty()) {
240 LiveInterval *lvr = lvrQ.get();
241 typedef SmallVector<LiveInterval*, 4> LVRVec;
243 unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
244 if (availablePhysReg) {
245 DEBUG(dbgs() << "allocating: " << tri_->getName(availablePhysReg) <<
247 assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
248 vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
249 physReg2liu_[availablePhysReg].unify(*lvr);
251 for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
252 lvrI != lvrEnd; ++lvrI) {
253 DEBUG(dbgs() << "queuing new interval: " << **lvrI << "\n");
254 assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
255 "expect split value in virtual register");
261 // Check if this live virtual reg interferes with a physical register. If not,
262 // then check for interference on each register that aliases with the physical
263 // register. Return the interfering register.
264 unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &lvr,
266 queries_[preg].init(&lvr, &physReg2liu_[preg]);
267 if (queries_[preg].checkInterference())
269 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
270 queries_[*asI].init(&lvr, &physReg2liu_[*asI]);
271 if (queries_[*asI].checkInterference())
277 // Spill all live virtual registers currently unified under preg that interfere
279 void RABasic::spillInterferences(unsigned preg,
280 SmallVectorImpl<LiveInterval*> &splitLVRs) {
281 SmallPtrSet<LiveInterval*, 8> spilledLVRs;
282 LiveIntervalUnion::Query &query = queries_[preg];
283 LiveIntervalUnion::InterferenceResult ir = query.firstInterference();
284 assert(query.isInterference(ir) && "expect interference");
286 LiveInterval *lvr = ir.liuSegPos()->liveVirtReg;
287 if (!spilledLVRs.insert(lvr)) continue;
288 // Spill the previously allocated lvr.
289 SmallVector<LiveInterval*, 1> spillIs; // ignored
290 spiller_->spill(lvr, splitLVRs, spillIs);
291 } while (query.nextInterference(ir));
292 for (SmallPtrSetIterator<LiveInterval*> lvrI = spilledLVRs.begin(),
293 lvrEnd = spilledLVRs.end();
294 lvrI != lvrEnd; ++lvrI ) {
295 // Deallocate the interfering lvr by removing it from the preg union.
296 physReg2liu_[preg].extract(**lvrI);
298 // After extracting segments, the query's results are invalid.
302 //===----------------------------------------------------------------------===//
303 // RABasic Implementation
304 //===----------------------------------------------------------------------===//
306 // Driver for the register assignment and splitting heuristics.
307 // Manages iteration over the LiveIntervalUnions.
309 // Minimal implementation of register assignment and splitting--spills whenever
310 // we run out of registers.
312 // selectOrSplit can only be called once per live virtual register. We then do a
313 // single interference test for each register the correct class until we find an
314 // available register. So, the number of interference tests in the worst case is
315 // |vregs| * |machineregs|. And since the number of interference tests is
316 // minimal, there is no value in caching them.
317 unsigned RABasic::selectOrSplit(LiveInterval &lvr,
318 SmallVectorImpl<LiveInterval*> &splitLVRs) {
319 // Accumulate the min spill cost among the interferences, in case we spill.
320 unsigned minSpillReg = 0;
321 unsigned minSpillAlias = 0;
322 float minSpillWeight = lvr.weight;
324 // Check for an available reg in this class.
325 const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
326 for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
327 trcEnd = trc->allocation_order_end(*mf_);
328 trcI != trcEnd; ++trcI) {
329 unsigned preg = *trcI;
330 unsigned interfReg = checkPhysRegInterference(lvr, preg);
331 if (interfReg == 0) {
334 LiveIntervalUnion::InterferenceResult interf =
335 queries_[interfReg].firstInterference();
336 float interfWeight = interf.liuSegPos()->liveVirtReg->weight;
337 if (interfWeight < minSpillWeight ) {
338 minSpillReg = interfReg;
339 minSpillAlias = preg;
340 minSpillWeight = interfWeight;
343 if (minSpillReg == 0) {
344 DEBUG(dbgs() << "spilling: " << lvr << '\n');
345 SmallVector<LiveInterval*, 1> spillIs; // ignored
346 spiller_->spill(&lvr, splitLVRs, spillIs);
347 // The live virtual register requesting to be allocated was spilled. So tell
348 // the caller not to allocate anything for this round.
351 // Free the cheapest physical register.
352 spillInterferences(minSpillReg, splitLVRs);
353 // Tell the caller to allocate to this newly freed physical register.
354 assert(minSpillAlias != 0 && "need a free register after spilling");
355 // We just spilled the first register that interferes with minSpillAlias. We
356 // now assume minSpillAlias is free because only one register alias may
357 // interfere at a time. e.g. we ignore predication.
358 unsigned interfReg = checkPhysRegInterference(lvr, minSpillAlias);
359 if (interfReg != 0) {
360 dbgs() << "spilling cannot free " << tri_->getName(minSpillAlias) <<
361 " for " << lvr.reg << " with interference " <<
362 *queries_[interfReg].firstInterference().liuSegPos()->liveVirtReg << "\n";
363 llvm_unreachable("Interference after spill.");
365 return minSpillAlias;
369 Spiller *createInlineSpiller(MachineFunctionPass &pass,
374 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
375 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
376 << "********** Function: "
377 << ((Value*)mf.getFunction())->getName() << '\n');
380 tm_ = &mf.getTarget();
381 mri_ = &mf.getRegInfo();
383 DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
385 RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis<VirtRegMap>(),
386 getAnalysis<LiveIntervals>());
388 // We may want to force InlineSpiller for this register allocator. For
389 // now we're also experimenting with the standard spiller.
391 //spiller_.reset(createInlineSpiller(*this, *mf_, *vrm_));
392 spiller_.reset(createSpiller(*this, *mf_, *vrm_));
396 // Diagnostic output before rewriting
397 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
399 // optional HTML output
400 DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
403 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
404 rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
406 // The pass output is in VirtRegMap. Release all the transient data.
412 FunctionPass* llvm::createBasicRegisterAllocator()
414 return new RABasic();