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 Spiller &spiller() { return *spiller_; }
101 virtual unsigned selectOrSplit(LiveInterval &lvr,
102 SmallVectorImpl<LiveInterval*> &splitLVRs);
104 /// Perform register allocation.
105 virtual bool runOnMachineFunction(MachineFunction &mf);
110 char RABasic::ID = 0;
112 } // end anonymous namespace
114 // We should not need to publish the initializer as long as no other passes
116 #if 0 // disable INITIALIZE_PASS
117 INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
118 "Basic Register Allocator", false, false)
119 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
120 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
121 INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
122 INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
123 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
124 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
125 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
127 INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
129 INITIALIZE_PASS_END(RABasic, "basic-regalloc",
130 "Basic Register Allocator", false, false)
131 #endif // disable INITIALIZE_PASS
133 RABasic::RABasic(): MachineFunctionPass(ID) {
134 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
135 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
136 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
137 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
138 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
139 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
140 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
141 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
142 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
143 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
146 void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
147 au.setPreservesCFG();
148 au.addRequired<LiveIntervals>();
149 au.addPreserved<SlotIndexes>();
151 au.addRequiredID(StrongPHIEliminationID);
152 au.addRequiredTransitive<RegisterCoalescer>();
153 au.addRequired<CalculateSpillWeights>();
154 au.addRequired<LiveStacks>();
155 au.addPreserved<LiveStacks>();
156 au.addRequiredID(MachineDominatorsID);
157 au.addPreservedID(MachineDominatorsID);
158 au.addRequired<MachineLoopInfo>();
159 au.addPreserved<MachineLoopInfo>();
160 au.addRequired<VirtRegMap>();
161 au.addPreserved<VirtRegMap>();
162 DEBUG(au.addRequired<RenderMachineFunction>());
163 MachineFunctionPass::getAnalysisUsage(au);
166 void RABasic::releaseMemory() {
168 RegAllocBase::releaseMemory();
172 // Verify each LiveIntervalUnion.
173 void RegAllocBase::verify() {
174 LvrBitSet visitedVRegs;
175 OwningArrayPtr<LvrBitSet> unionVRegs(new LvrBitSet[physReg2liu_.numRegs()]);
176 // Verify disjoint unions.
177 for (unsigned preg = 0; preg < physReg2liu_.numRegs(); ++preg) {
178 DEBUG(PhysicalRegisterDescription prd(tri_); physReg2liu_[preg].dump(&prd));
179 LvrBitSet &vregs = unionVRegs[preg];
180 physReg2liu_[preg].verify(vregs);
181 // Union + intersection test could be done efficiently in one pass, but
182 // don't add a method to SparseBitVector unless we really need it.
183 assert(!visitedVRegs.intersects(vregs) && "vreg in multiple unions");
184 visitedVRegs |= vregs;
186 // Verify vreg coverage.
187 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
188 liItr != liEnd; ++liItr) {
189 unsigned reg = liItr->first;
190 LiveInterval &li = *liItr->second;
191 if (li.empty() ) continue;
192 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue;
193 if (!vrm_->hasPhys(reg)) continue; // spilled?
194 unsigned preg = vrm_->getPhys(reg);
195 if (!unionVRegs[preg].test(reg)) {
196 dbgs() << "LiveVirtReg " << reg << " not in union " <<
197 tri_->getName(preg) << "\n";
198 llvm_unreachable("unallocated live vreg");
201 // FIXME: I'm not sure how to verify spilled intervals.
205 //===----------------------------------------------------------------------===//
206 // RegAllocBase Implementation
207 //===----------------------------------------------------------------------===//
209 // Instantiate a LiveIntervalUnion for each physical register.
210 void RegAllocBase::LIUArray::init(unsigned nRegs) {
211 array_.reset(new LiveIntervalUnion[nRegs]);
213 for (unsigned pr = 0; pr < nRegs; ++pr) {
218 void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
219 LiveIntervals &lis) {
223 physReg2liu_.init(tri_->getNumRegs());
224 // Cache an interferece query for each physical reg
225 queries_.reset(new LiveIntervalUnion::Query[physReg2liu_.numRegs()]);
228 void RegAllocBase::LIUArray::clear() {
233 void RegAllocBase::releaseMemory() {
234 physReg2liu_.clear();
238 /// This class defines a queue of live virtual registers prioritized by spill
239 /// weight. The heaviest vreg is popped first.
241 /// Currently, this is trivial wrapper that gives us an opaque type in the
242 /// header, but we may later give it a virtual interface for register allocators
243 /// to override the priority queue comparator.
244 class LiveVirtRegQueue {
245 typedef std::priority_queue
246 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
250 // Is the queue empty?
251 bool empty() { return pq_.empty(); }
253 // Get the highest priority lvr (top + pop)
254 LiveInterval *get() {
255 LiveInterval *lvr = pq_.top();
259 // Add this lvr to the queue
260 void push(LiveInterval *lvr) {
264 } // end namespace llvm
266 // Visit all the live virtual registers. If they are already assigned to a
267 // physical register, unify them with the corresponding LiveIntervalUnion,
268 // otherwise push them on the priority queue for later assignment.
269 void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
270 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
271 liItr != liEnd; ++liItr) {
272 unsigned reg = liItr->first;
273 LiveInterval &li = *liItr->second;
274 if (li.empty()) continue;
275 if (TargetRegisterInfo::isPhysicalRegister(reg)) {
276 physReg2liu_[reg].unify(li);
284 // Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
285 // selectOrSplit implementation.
286 void RegAllocBase::allocatePhysRegs() {
287 LiveVirtRegQueue lvrQ;
288 seedLiveVirtRegs(lvrQ);
289 while (!lvrQ.empty()) {
290 LiveInterval *lvr = lvrQ.get();
291 typedef SmallVector<LiveInterval*, 4> LVRVec;
293 unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
294 if (availablePhysReg) {
295 DEBUG(dbgs() << "allocating: " << tri_->getName(availablePhysReg) <<
296 " " << *lvr << '\n');
297 assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
298 vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
299 physReg2liu_[availablePhysReg].unify(*lvr);
301 for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
302 lvrI != lvrEnd; ++lvrI) {
303 if ((*lvrI)->empty()) continue;
304 DEBUG(dbgs() << "queuing new interval: " << **lvrI << "\n");
305 assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
306 "expect split value in virtual register");
312 // Check if this live virtual reg interferes with a physical register. If not,
313 // then check for interference on each register that aliases with the physical
314 // register. Return the interfering register.
315 unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &lvr,
317 queries_[preg].init(&lvr, &physReg2liu_[preg]);
318 if (queries_[preg].checkInterference())
320 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
321 queries_[*asI].init(&lvr, &physReg2liu_[*asI]);
322 if (queries_[*asI].checkInterference())
328 // Sort live virtual registers by their register number.
329 struct LessLiveVirtualReg
330 : public std::binary_function<LiveInterval, LiveInterval, bool> {
331 bool operator()(const LiveInterval *left, const LiveInterval *right) const {
332 return left->reg < right->reg;
336 // Spill all interferences currently assigned to this physical register.
337 void RegAllocBase::spillReg(unsigned reg,
338 SmallVectorImpl<LiveInterval*> &splitLVRs) {
339 LiveIntervalUnion::Query &query = queries_[reg];
340 const SmallVectorImpl<LiveInterval*> &pendingSpills =
341 query.interferingVRegs();
342 for (SmallVectorImpl<LiveInterval*>::const_iterator I = pendingSpills.begin(),
343 E = pendingSpills.end(); I != E; ++I) {
344 LiveInterval &lvr = **I;
346 "extracting from " << tri_->getName(reg) << " " << lvr << '\n');
348 // Deallocate the interfering vreg by removing it from the union.
349 // A LiveInterval instance may not be in a union during modification!
350 physReg2liu_[reg].extract(lvr);
352 // After extracting segments, the query's results are invalid.
355 // Clear the vreg assignment.
356 vrm_->clearVirt(lvr.reg);
358 // Spill the extracted interval.
359 spiller().spill(&lvr, splitLVRs, pendingSpills);
363 // Spill or split all live virtual registers currently unified under preg that
364 // interfere with lvr. The newly spilled or split live intervals are returned by
365 // appending them to splitLVRs.
367 RegAllocBase::spillInterferences(unsigned preg,
368 SmallVectorImpl<LiveInterval*> &splitLVRs) {
369 // Record each interference and determine if all are spillable before mutating
370 // either the union or live intervals.
371 std::vector<LiveInterval*> spilledLVRs;
373 unsigned numInterferences = queries_[preg].collectInterferingVRegs();
374 if (queries_[preg].seenUnspillableVReg()) {
377 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
378 numInterferences += queries_[*asI].collectInterferingVRegs();
379 if (queries_[*asI].seenUnspillableVReg()) {
383 DEBUG(dbgs() << "spilling " << tri_->getName(preg) <<
384 " interferences with " << queries_[preg].lvr() << "\n");
385 assert(numInterferences > 0 && "expect interference");
387 // Spill each interfering vreg allocated to preg or an alias.
388 spillReg(preg, splitLVRs);
389 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI)
390 spillReg(*asI, splitLVRs);
394 //===----------------------------------------------------------------------===//
395 // RABasic Implementation
396 //===----------------------------------------------------------------------===//
398 // Driver for the register assignment and splitting heuristics.
399 // Manages iteration over the LiveIntervalUnions.
401 // Minimal implementation of register assignment and splitting--spills whenever
402 // we run out of registers.
404 // selectOrSplit can only be called once per live virtual register. We then do a
405 // single interference test for each register the correct class until we find an
406 // available register. So, the number of interference tests in the worst case is
407 // |vregs| * |machineregs|. And since the number of interference tests is
408 // minimal, there is no value in caching them.
409 unsigned RABasic::selectOrSplit(LiveInterval &lvr,
410 SmallVectorImpl<LiveInterval*> &splitLVRs) {
411 // Populate a list of physical register spill candidates.
412 std::vector<unsigned> pregSpillCands;
414 // Check for an available register in this class.
415 const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
416 for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
417 trcEnd = trc->allocation_order_end(*mf_);
418 trcI != trcEnd; ++trcI) {
419 unsigned preg = *trcI;
420 // Check interference and intialize queries for this lvr as a side effect.
421 unsigned interfReg = checkPhysRegInterference(lvr, preg);
422 if (interfReg == 0) {
423 // Found an available register.
426 LiveInterval *interferingVirtReg =
427 queries_[interfReg].firstInterference().liuSegPos()->liveVirtReg;
429 // The current lvr must either spillable, or one of its interferences must
430 // have less spill weight.
431 if (interferingVirtReg->weight < lvr.weight ) {
432 pregSpillCands.push_back(preg);
435 // Try to spill another interfering reg with less spill weight.
437 // FIXME: RAGreedy will sort this list by spill weight.
438 for (std::vector<unsigned>::iterator pregI = pregSpillCands.begin(),
439 pregE = pregSpillCands.end(); pregI != pregE; ++pregI) {
441 if (!spillInterferences(*pregI, splitLVRs)) continue;
443 unsigned interfReg = checkPhysRegInterference(lvr, *pregI);
444 if (interfReg != 0) {
445 const LiveSegment &seg =
446 *queries_[interfReg].firstInterference().liuSegPos();
447 dbgs() << "spilling cannot free " << tri_->getName(*pregI) <<
448 " for " << lvr.reg << " with interference " << seg.liveVirtReg << "\n";
449 llvm_unreachable("Interference after spill.");
451 // Tell the caller to allocate to this newly freed physical register.
454 // No other spill candidates were found, so spill the current lvr.
455 DEBUG(dbgs() << "spilling: " << lvr << '\n');
456 SmallVector<LiveInterval*, 1> pendingSpills;
457 spiller().spill(&lvr, splitLVRs, pendingSpills);
459 // The live virtual register requesting allocation was spilled, so tell
460 // the caller not to allocate anything during this round.
465 Spiller *createInlineSpiller(MachineFunctionPass &pass,
470 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
471 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
472 << "********** Function: "
473 << ((Value*)mf.getFunction())->getName() << '\n');
476 tm_ = &mf.getTarget();
477 mri_ = &mf.getRegInfo();
479 DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
481 RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis<VirtRegMap>(),
482 getAnalysis<LiveIntervals>());
484 // We may want to force InlineSpiller for this register allocator. For
485 // now we're also experimenting with the standard spiller.
487 //spiller_.reset(createInlineSpiller(*this, *mf_, *vrm_));
488 spiller_.reset(createSpiller(*this, *mf_, *vrm_));
492 // Diagnostic output before rewriting
493 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
495 // optional HTML output
496 DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
498 // FIXME: Verification currently must run before VirtRegRewriter. We should
499 // make the rewriter a separate pass and override verifyAnalysis instead. When
500 // that happens, verification naturally falls under VerifyMachineCode.
502 if (VerifyRegAlloc) {
503 // Verify accuracy of LiveIntervals. The standard machine code verifier
504 // ensures that each LiveIntervals covers all uses of the virtual reg.
506 // FIXME: MachineVerifier is currently broken when using the standard
507 // spiller. Enable it for InlineSpiller only.
508 // mf_->verify(this);
510 // Verify that LiveIntervals are partitioned into unions and disjoint within
517 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
518 rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
520 // The pass output is in VirtRegMap. Release all the transient data.
526 FunctionPass* llvm::createBasicRegisterAllocator()
528 return new RABasic();