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"
38 #include "llvm/ADT/SparseBitVector.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/ErrorHandling.h"
42 #include "llvm/Support/raw_ostream.h"
49 static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
50 createBasicRegisterAllocator);
52 // Temporary verification option until we can put verification inside
55 VerifyRegAlloc("verify-regalloc",
56 cl::desc("Verify live intervals before renaming"));
58 class PhysicalRegisterDescription : public AbstractRegisterDescription {
59 const TargetRegisterInfo *tri_;
61 PhysicalRegisterDescription(const TargetRegisterInfo *tri): tri_(tri) {}
62 virtual const char *getName(unsigned reg) const { return tri_->getName(reg); }
67 /// RABasic provides a minimal implementation of the basic register allocation
68 /// algorithm. It prioritizes live virtual registers by spill weight and spills
69 /// whenever a register is unavailable. This is not practical in production but
70 /// provides a useful baseline both for measuring other allocators and comparing
71 /// the speed of the basic algorithm against other styles of allocators.
72 class RABasic : public MachineFunctionPass, public RegAllocBase
76 const TargetMachine *tm_;
77 MachineRegisterInfo *mri_;
81 RenderMachineFunction *rmf_;
84 std::auto_ptr<Spiller> spiller_;
89 /// Return the pass name.
90 virtual const char* getPassName() const {
91 return "Basic Register Allocator";
94 /// RABasic analysis usage.
95 virtual void getAnalysisUsage(AnalysisUsage &au) const;
97 virtual void releaseMemory();
99 virtual unsigned selectOrSplit(LiveInterval &lvr,
100 SmallVectorImpl<LiveInterval*> &splitLVRs);
102 void spillInterferences(unsigned preg,
103 SmallVectorImpl<LiveInterval*> &splitLVRs);
105 /// Perform register allocation.
106 virtual bool runOnMachineFunction(MachineFunction &mf);
111 char RABasic::ID = 0;
113 } // end anonymous namespace
115 // We should not need to publish the initializer as long as no other passes
117 #if 0 // disable INITIALIZE_PASS
118 INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
119 "Basic Register Allocator", false, false)
120 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
121 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
122 INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
123 INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
124 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
125 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
126 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
128 INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
130 INITIALIZE_PASS_END(RABasic, "basic-regalloc",
131 "Basic Register Allocator", false, false)
132 #endif // disable INITIALIZE_PASS
134 RABasic::RABasic(): MachineFunctionPass(ID) {
135 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
136 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
137 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
138 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
139 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
140 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
141 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
142 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
143 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
144 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
147 void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
148 au.setPreservesCFG();
149 au.addRequired<LiveIntervals>();
150 au.addPreserved<SlotIndexes>();
152 au.addRequiredID(StrongPHIEliminationID);
153 au.addRequiredTransitive<RegisterCoalescer>();
154 au.addRequired<CalculateSpillWeights>();
155 au.addRequired<LiveStacks>();
156 au.addPreserved<LiveStacks>();
157 au.addRequiredID(MachineDominatorsID);
158 au.addPreservedID(MachineDominatorsID);
159 au.addRequired<MachineLoopInfo>();
160 au.addPreserved<MachineLoopInfo>();
161 au.addRequired<VirtRegMap>();
162 au.addPreserved<VirtRegMap>();
163 DEBUG(au.addRequired<RenderMachineFunction>());
164 MachineFunctionPass::getAnalysisUsage(au);
167 void RABasic::releaseMemory() {
169 RegAllocBase::releaseMemory();
173 // Verify each LiveIntervalUnion.
174 void RegAllocBase::verify() {
175 LvrBitSet visitedVRegs;
176 OwningArrayPtr<LvrBitSet> unionVRegs(new LvrBitSet[physReg2liu_.numRegs()]);
177 // Verify disjoint unions.
178 for (unsigned preg = 0; preg < physReg2liu_.numRegs(); ++preg) {
179 DEBUG(PhysicalRegisterDescription prd(tri_); physReg2liu_[preg].dump(&prd));
180 LvrBitSet &vregs = unionVRegs[preg];
181 physReg2liu_[preg].verify(vregs);
182 // Union + intersection test could be done efficiently in one pass, but
183 // don't add a method to SparseBitVector unless we really need it.
184 assert(!visitedVRegs.intersects(vregs) && "vreg in multiple unions");
185 visitedVRegs |= vregs;
187 // Verify vreg coverage.
188 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
189 liItr != liEnd; ++liItr) {
190 unsigned reg = liItr->first;
191 LiveInterval &li = *liItr->second;
192 if (li.empty() ) continue;
193 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue;
194 if (!vrm_->hasPhys(reg)) continue; // spilled?
195 unsigned preg = vrm_->getPhys(reg);
196 if (!unionVRegs[preg].test(reg)) {
197 dbgs() << "LiveVirtReg " << reg << " not in union " <<
198 tri_->getName(preg) << "\n";
199 llvm_unreachable("unallocated live vreg");
202 // FIXME: I'm not sure how to verify spilled intervals.
206 //===----------------------------------------------------------------------===//
207 // RegAllocBase Implementation
208 //===----------------------------------------------------------------------===//
210 // Instantiate a LiveIntervalUnion for each physical register.
211 void RegAllocBase::LIUArray::init(unsigned nRegs) {
212 array_.reset(new LiveIntervalUnion[nRegs]);
214 for (unsigned pr = 0; pr < nRegs; ++pr) {
219 void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
220 LiveIntervals &lis) {
224 physReg2liu_.init(tri_->getNumRegs());
225 // Cache an interferece query for each physical reg
226 queries_.reset(new LiveIntervalUnion::Query[physReg2liu_.numRegs()]);
229 void RegAllocBase::LIUArray::clear() {
234 void RegAllocBase::releaseMemory() {
235 physReg2liu_.clear();
239 /// This class defines a queue of live virtual registers prioritized by spill
240 /// weight. The heaviest vreg is popped first.
242 /// Currently, this is trivial wrapper that gives us an opaque type in the
243 /// header, but we may later give it a virtual interface for register allocators
244 /// to override the priority queue comparator.
245 class LiveVirtRegQueue {
246 typedef std::priority_queue
247 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
251 // Is the queue empty?
252 bool empty() { return pq_.empty(); }
254 // Get the highest priority lvr (top + pop)
255 LiveInterval *get() {
256 LiveInterval *lvr = pq_.top();
260 // Add this lvr to the queue
261 void push(LiveInterval *lvr) {
265 } // end namespace llvm
267 // Visit all the live virtual registers. If they are already assigned to a
268 // physical register, unify them with the corresponding LiveIntervalUnion,
269 // otherwise push them on the priority queue for later assignment.
270 void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
271 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
272 liItr != liEnd; ++liItr) {
273 unsigned reg = liItr->first;
274 LiveInterval &li = *liItr->second;
275 if (li.empty()) continue;
276 if (TargetRegisterInfo::isPhysicalRegister(reg)) {
277 physReg2liu_[reg].unify(li);
285 // Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
286 // selectOrSplit implementation.
287 void RegAllocBase::allocatePhysRegs() {
288 LiveVirtRegQueue lvrQ;
289 seedLiveVirtRegs(lvrQ);
290 while (!lvrQ.empty()) {
291 LiveInterval *lvr = lvrQ.get();
292 typedef SmallVector<LiveInterval*, 4> LVRVec;
294 unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
295 if (availablePhysReg) {
296 DEBUG(dbgs() << "allocating: " << tri_->getName(availablePhysReg) <<
297 " " << *lvr << '\n');
298 assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
299 vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
300 physReg2liu_[availablePhysReg].unify(*lvr);
302 for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
303 lvrI != lvrEnd; ++lvrI) {
304 if ((*lvrI)->empty()) continue;
305 DEBUG(dbgs() << "queuing new interval: " << **lvrI << "\n");
306 assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
307 "expect split value in virtual register");
313 // Check if this live virtual reg interferes with a physical register. If not,
314 // then check for interference on each register that aliases with the physical
315 // register. Return the interfering register.
316 unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &lvr,
318 queries_[preg].init(&lvr, &physReg2liu_[preg]);
319 if (queries_[preg].checkInterference())
321 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
322 queries_[*asI].init(&lvr, &physReg2liu_[*asI]);
323 if (queries_[*asI].checkInterference())
329 // Spill or split all live virtual registers currently unified under preg that
330 // interfere with lvr. The newly spilled or split live intervals are returned by
331 // appending them to splitLVRs.
332 void RABasic::spillInterferences(unsigned preg,
333 SmallVectorImpl<LiveInterval*> &splitLVRs) {
334 SmallPtrSet<LiveInterval*, 8> spilledLVRs;
335 LiveIntervalUnion::Query &query = queries_[preg];
336 // Record each interference before mutating either the union or live
338 LiveIntervalUnion::InterferenceResult ir = query.firstInterference();
339 assert(query.isInterference(ir) && "expect interference");
341 spilledLVRs.insert(ir.liuSegPos()->liveVirtReg);
342 } while (query.nextInterference(ir));
343 for (SmallPtrSetIterator<LiveInterval*> lvrI = spilledLVRs.begin(),
344 lvrEnd = spilledLVRs.end();
345 lvrI != lvrEnd; ++lvrI ) {
346 LiveInterval& lvr = **lvrI;
347 // Spill the previously allocated lvr.
348 DEBUG(dbgs() << "extracting from " << preg << " " << lvr << '\n');
349 // Deallocate the interfering lvr by removing it from the preg union.
350 // Live intervals may not be in a union during modification.
351 physReg2liu_[preg].extract(lvr);
352 // Spill the extracted interval.
353 SmallVector<LiveInterval*, 8> spillIs;
354 spiller_->spill(&lvr, splitLVRs, spillIs);
356 // After extracting segments, the query's results are invalid.
360 //===----------------------------------------------------------------------===//
361 // RABasic Implementation
362 //===----------------------------------------------------------------------===//
364 // Driver for the register assignment and splitting heuristics.
365 // Manages iteration over the LiveIntervalUnions.
367 // Minimal implementation of register assignment and splitting--spills whenever
368 // we run out of registers.
370 // selectOrSplit can only be called once per live virtual register. We then do a
371 // single interference test for each register the correct class until we find an
372 // available register. So, the number of interference tests in the worst case is
373 // |vregs| * |machineregs|. And since the number of interference tests is
374 // minimal, there is no value in caching them.
375 unsigned RABasic::selectOrSplit(LiveInterval &lvr,
376 SmallVectorImpl<LiveInterval*> &splitLVRs) {
377 // Accumulate the min spill cost among the interferences, in case we spill.
378 unsigned minSpillReg = 0;
379 unsigned minSpillAlias = 0;
380 float minSpillWeight = lvr.weight;
382 // Check for an available reg in this class.
383 const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
384 for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
385 trcEnd = trc->allocation_order_end(*mf_);
386 trcI != trcEnd; ++trcI) {
387 unsigned preg = *trcI;
388 unsigned interfReg = checkPhysRegInterference(lvr, preg);
389 if (interfReg == 0) {
392 LiveIntervalUnion::InterferenceResult interf =
393 queries_[interfReg].firstInterference();
394 float interfWeight = interf.liuSegPos()->liveVirtReg->weight;
395 if (interfWeight < minSpillWeight ) {
396 minSpillReg = interfReg;
397 minSpillAlias = preg;
398 minSpillWeight = interfWeight;
401 if (minSpillReg == 0) {
402 DEBUG(dbgs() << "spilling: " << lvr << '\n');
403 SmallVector<LiveInterval*, 1> spillIs; // ignored
404 spiller_->spill(&lvr, splitLVRs, spillIs);
405 // The live virtual register requesting to be allocated was spilled. So tell
406 // the caller not to allocate anything for this round.
409 // Free the cheapest physical register.
410 spillInterferences(minSpillReg, splitLVRs);
411 // Tell the caller to allocate to this newly freed physical register.
412 assert(minSpillAlias != 0 && "need a free register after spilling");
413 // We just spilled the first register that interferes with minSpillAlias. We
414 // now assume minSpillAlias is free because only one register alias may
415 // interfere at a time. e.g. we ignore predication.
416 unsigned interfReg = checkPhysRegInterference(lvr, minSpillAlias);
417 if (interfReg != 0) {
418 dbgs() << "spilling cannot free " << tri_->getName(minSpillAlias) <<
419 " for " << lvr.reg << " with interference " <<
420 *queries_[interfReg].firstInterference().liuSegPos()->liveVirtReg << "\n";
421 llvm_unreachable("Interference after spill.");
423 return minSpillAlias;
427 Spiller *createInlineSpiller(MachineFunctionPass &pass,
432 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
433 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
434 << "********** Function: "
435 << ((Value*)mf.getFunction())->getName() << '\n');
438 tm_ = &mf.getTarget();
439 mri_ = &mf.getRegInfo();
441 DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
443 RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis<VirtRegMap>(),
444 getAnalysis<LiveIntervals>());
446 // We may want to force InlineSpiller for this register allocator. For
447 // now we're also experimenting with the standard spiller.
449 //spiller_.reset(createInlineSpiller(*this, *mf_, *vrm_));
450 spiller_.reset(createSpiller(*this, *mf_, *vrm_));
454 // Diagnostic output before rewriting
455 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
457 // optional HTML output
458 DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
460 // FIXME: Verification currently must run before VirtRegRewriter. We should
461 // make the rewriter a separate pass and override verifyAnalysis instead. When
462 // that happens, verification naturally falls under VerifyMachineCode.
464 if (VerifyRegAlloc) {
465 // Verify accuracy of LiveIntervals. The standard machine code verifier
466 // ensures that each LiveIntervals covers all uses of the virtual reg.
468 // FIXME: MachineVerifier is currently broken when using the standard
469 // spiller. Enable it for InlineSpiller only.
470 // mf_->verify(this);
472 // Verify that LiveIntervals are partitioned into unions and disjoint within
479 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
480 rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
482 // The pass output is in VirtRegMap. Release all the transient data.
488 FunctionPass* llvm::createBasicRegisterAllocator()
490 return new RABasic();