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/Analysis/AliasAnalysis.h"
23 #include "llvm/Function.h"
24 #include "llvm/PassAnalysisSupport.h"
25 #include "llvm/CodeGen/CalcSpillWeights.h"
26 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
27 #include "llvm/CodeGen/LiveStackAnalysis.h"
28 #include "llvm/CodeGen/MachineFunctionPass.h"
29 #include "llvm/CodeGen/MachineInstr.h"
30 #include "llvm/CodeGen/MachineLoopInfo.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/CodeGen/Passes.h"
33 #include "llvm/CodeGen/RegAllocRegistry.h"
34 #include "llvm/CodeGen/RegisterCoalescer.h"
35 #include "llvm/Target/TargetMachine.h"
36 #include "llvm/Target/TargetOptions.h"
37 #include "llvm/Target/TargetRegisterInfo.h"
39 #include "llvm/ADT/SparseBitVector.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/ErrorHandling.h"
43 #include "llvm/Support/raw_ostream.h"
50 static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
51 createBasicRegisterAllocator);
53 // Temporary verification option until we can put verification inside
56 VerifyRegAlloc("verify-regalloc",
57 cl::desc("Verify live intervals before renaming"));
59 class PhysicalRegisterDescription : public AbstractRegisterDescription {
60 const TargetRegisterInfo *tri_;
62 PhysicalRegisterDescription(const TargetRegisterInfo *tri): tri_(tri) {}
63 virtual const char *getName(unsigned reg) const { return tri_->getName(reg); }
68 /// RABasic provides a minimal implementation of the basic register allocation
69 /// algorithm. It prioritizes live virtual registers by spill weight and spills
70 /// whenever a register is unavailable. This is not practical in production but
71 /// provides a useful baseline both for measuring other allocators and comparing
72 /// the speed of the basic algorithm against other styles of allocators.
73 class RABasic : public MachineFunctionPass, public RegAllocBase
77 const TargetMachine *tm_;
78 MachineRegisterInfo *mri_;
79 BitVector reservedRegs_;
83 RenderMachineFunction *rmf_;
86 std::auto_ptr<Spiller> spiller_;
91 /// Return the pass name.
92 virtual const char* getPassName() const {
93 return "Basic Register Allocator";
96 /// RABasic analysis usage.
97 virtual void getAnalysisUsage(AnalysisUsage &au) const;
99 virtual void releaseMemory();
101 virtual Spiller &spiller() { return *spiller_; }
103 virtual unsigned selectOrSplit(LiveInterval &lvr,
104 SmallVectorImpl<LiveInterval*> &splitLVRs);
106 /// Perform register allocation.
107 virtual bool runOnMachineFunction(MachineFunction &mf);
112 char RABasic::ID = 0;
114 } // end anonymous namespace
116 // We should not need to publish the initializer as long as no other passes
118 #if 0 // disable INITIALIZE_PASS
119 INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
120 "Basic Register Allocator", false, false)
121 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
122 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
123 INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
124 INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
125 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
126 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
127 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
129 INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
131 INITIALIZE_PASS_END(RABasic, "basic-regalloc",
132 "Basic Register Allocator", false, false)
133 #endif // disable INITIALIZE_PASS
135 RABasic::RABasic(): MachineFunctionPass(ID) {
136 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
137 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
138 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
139 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
140 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
141 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
142 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
143 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
144 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
145 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
148 void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
149 au.setPreservesCFG();
150 au.addRequired<AliasAnalysis>();
151 au.addPreserved<AliasAnalysis>();
152 au.addRequired<LiveIntervals>();
153 au.addPreserved<SlotIndexes>();
155 au.addRequiredID(StrongPHIEliminationID);
156 au.addRequiredTransitive<RegisterCoalescer>();
157 au.addRequired<CalculateSpillWeights>();
158 au.addRequired<LiveStacks>();
159 au.addPreserved<LiveStacks>();
160 au.addRequiredID(MachineDominatorsID);
161 au.addPreservedID(MachineDominatorsID);
162 au.addRequired<MachineLoopInfo>();
163 au.addPreserved<MachineLoopInfo>();
164 au.addRequired<VirtRegMap>();
165 au.addPreserved<VirtRegMap>();
166 DEBUG(au.addRequired<RenderMachineFunction>());
167 MachineFunctionPass::getAnalysisUsage(au);
170 void RABasic::releaseMemory() {
172 RegAllocBase::releaseMemory();
176 // Verify each LiveIntervalUnion.
177 void RegAllocBase::verify() {
178 LvrBitSet visitedVRegs;
179 OwningArrayPtr<LvrBitSet> unionVRegs(new LvrBitSet[physReg2liu_.numRegs()]);
180 // Verify disjoint unions.
181 for (unsigned preg = 0; preg < physReg2liu_.numRegs(); ++preg) {
182 DEBUG(PhysicalRegisterDescription prd(tri_); physReg2liu_[preg].dump(&prd));
183 LvrBitSet &vregs = unionVRegs[preg];
184 physReg2liu_[preg].verify(vregs);
185 // Union + intersection test could be done efficiently in one pass, but
186 // don't add a method to SparseBitVector unless we really need it.
187 assert(!visitedVRegs.intersects(vregs) && "vreg in multiple unions");
188 visitedVRegs |= vregs;
190 // Verify vreg coverage.
191 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
192 liItr != liEnd; ++liItr) {
193 unsigned reg = liItr->first;
194 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue;
195 if (!vrm_->hasPhys(reg)) continue; // spilled?
196 unsigned preg = vrm_->getPhys(reg);
197 if (!unionVRegs[preg].test(reg)) {
198 dbgs() << "LiveVirtReg " << reg << " not in union " <<
199 tri_->getName(preg) << "\n";
200 llvm_unreachable("unallocated live vreg");
203 // FIXME: I'm not sure how to verify spilled intervals.
207 //===----------------------------------------------------------------------===//
208 // RegAllocBase Implementation
209 //===----------------------------------------------------------------------===//
211 // Instantiate a LiveIntervalUnion for each physical register.
212 void RegAllocBase::LIUArray::init(unsigned nRegs) {
213 array_.reset(new LiveIntervalUnion[nRegs]);
215 for (unsigned pr = 0; pr < nRegs; ++pr) {
220 void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
221 LiveIntervals &lis) {
225 physReg2liu_.init(tri_->getNumRegs());
226 // Cache an interferece query for each physical reg
227 queries_.reset(new LiveIntervalUnion::Query[physReg2liu_.numRegs()]);
230 void RegAllocBase::LIUArray::clear() {
235 void RegAllocBase::releaseMemory() {
236 physReg2liu_.clear();
240 /// This class defines a queue of live virtual registers prioritized by spill
241 /// weight. The heaviest vreg is popped first.
243 /// Currently, this is trivial wrapper that gives us an opaque type in the
244 /// header, but we may later give it a virtual interface for register allocators
245 /// to override the priority queue comparator.
246 class LiveVirtRegQueue {
247 typedef std::priority_queue
248 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
252 // Is the queue empty?
253 bool empty() { return pq_.empty(); }
255 // Get the highest priority lvr (top + pop)
256 LiveInterval *get() {
257 LiveInterval *lvr = pq_.top();
261 // Add this lvr to the queue
262 void push(LiveInterval *lvr) {
266 } // end namespace llvm
268 // Visit all the live virtual registers. If they are already assigned to a
269 // physical register, unify them with the corresponding LiveIntervalUnion,
270 // otherwise push them on the priority queue for later assignment.
271 void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
272 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
273 liItr != liEnd; ++liItr) {
274 unsigned reg = liItr->first;
275 LiveInterval &li = *liItr->second;
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 if (query(lvr, preg).checkInterference())
320 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
321 if (query(lvr, *asI).checkInterference())
327 // Sort live virtual registers by their register number.
328 struct LessLiveVirtualReg
329 : public std::binary_function<LiveInterval, LiveInterval, bool> {
330 bool operator()(const LiveInterval *left, const LiveInterval *right) const {
331 return left->reg < right->reg;
335 // Spill all interferences currently assigned to this physical register.
336 void RegAllocBase::spillReg(LiveInterval& lvr, unsigned reg,
337 SmallVectorImpl<LiveInterval*> &splitLVRs) {
338 LiveIntervalUnion::Query &Q = query(lvr, reg);
339 const SmallVectorImpl<LiveInterval*> &pendingSpills = Q.interferingVRegs();
341 for (SmallVectorImpl<LiveInterval*>::const_iterator I = pendingSpills.begin(),
342 E = pendingSpills.end(); I != E; ++I) {
343 LiveInterval &spilledLVR = **I;
344 DEBUG(dbgs() << "extracting from " <<
345 tri_->getName(reg) << " " << spilledLVR << '\n');
347 // Deallocate the interfering vreg by removing it from the union.
348 // A LiveInterval instance may not be in a union during modification!
349 physReg2liu_[reg].extract(spilledLVR);
351 // Clear the vreg assignment.
352 vrm_->clearVirt(spilledLVR.reg);
354 // Spill the extracted interval.
355 spiller().spill(&spilledLVR, splitLVRs, pendingSpills);
357 // After extracting segments, the query's results are invalid. But keep the
358 // contents valid until we're done accessing pendingSpills.
362 // Spill or split all live virtual registers currently unified under preg that
363 // interfere with lvr. The newly spilled or split live intervals are returned by
364 // appending them to splitLVRs.
366 RegAllocBase::spillInterferences(LiveInterval &lvr, unsigned preg,
367 SmallVectorImpl<LiveInterval*> &splitLVRs) {
368 // Record each interference and determine if all are spillable before mutating
369 // either the union or live intervals.
371 // Collect interferences assigned to the requested physical register.
372 LiveIntervalUnion::Query &QPreg = query(lvr, preg);
373 unsigned numInterferences = QPreg.collectInterferingVRegs();
374 if (QPreg.seenUnspillableVReg()) {
377 // Collect interferences assigned to any alias of the physical register.
378 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
379 LiveIntervalUnion::Query &QAlias = query(lvr, *asI);
380 numInterferences += QAlias.collectInterferingVRegs();
381 if (QAlias.seenUnspillableVReg()) {
385 DEBUG(dbgs() << "spilling " << tri_->getName(preg) <<
386 " interferences with " << lvr << "\n");
387 assert(numInterferences > 0 && "expect interference");
389 // Spill each interfering vreg allocated to preg or an alias.
390 spillReg(lvr, preg, splitLVRs);
391 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI)
392 spillReg(lvr, *asI, splitLVRs);
396 //===----------------------------------------------------------------------===//
397 // RABasic Implementation
398 //===----------------------------------------------------------------------===//
400 // Driver for the register assignment and splitting heuristics.
401 // Manages iteration over the LiveIntervalUnions.
403 // Minimal implementation of register assignment and splitting--spills whenever
404 // we run out of registers.
406 // selectOrSplit can only be called once per live virtual register. We then do a
407 // single interference test for each register the correct class until we find an
408 // available register. So, the number of interference tests in the worst case is
409 // |vregs| * |machineregs|. And since the number of interference tests is
410 // minimal, there is no value in caching them.
411 unsigned RABasic::selectOrSplit(LiveInterval &lvr,
412 SmallVectorImpl<LiveInterval*> &splitLVRs) {
413 // Populate a list of physical register spill candidates.
414 SmallVector<unsigned, 8> pregSpillCands;
416 // Check for an available register in this class.
417 const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
418 for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
419 trcEnd = trc->allocation_order_end(*mf_);
420 trcI != trcEnd; ++trcI) {
421 unsigned preg = *trcI;
422 if (reservedRegs_.test(preg)) continue;
424 // Check interference and intialize queries for this lvr as a side effect.
425 unsigned interfReg = checkPhysRegInterference(lvr, preg);
426 if (interfReg == 0) {
427 // Found an available register.
430 LiveInterval *interferingVirtReg =
431 queries_[interfReg].firstInterference().liuSegPos()->liveVirtReg;
433 // The current lvr must either spillable, or one of its interferences must
434 // have less spill weight.
435 if (interferingVirtReg->weight < lvr.weight ) {
436 pregSpillCands.push_back(preg);
439 // Try to spill another interfering reg with less spill weight.
441 // FIXME: RAGreedy will sort this list by spill weight.
442 for (SmallVectorImpl<unsigned>::iterator pregI = pregSpillCands.begin(),
443 pregE = pregSpillCands.end(); pregI != pregE; ++pregI) {
445 if (!spillInterferences(lvr, *pregI, splitLVRs)) continue;
447 unsigned interfReg = checkPhysRegInterference(lvr, *pregI);
448 if (interfReg != 0) {
449 const LiveSegment &seg =
450 *queries_[interfReg].firstInterference().liuSegPos();
451 dbgs() << "spilling cannot free " << tri_->getName(*pregI) <<
452 " for " << lvr.reg << " with interference " << *seg.liveVirtReg << "\n";
453 llvm_unreachable("Interference after spill.");
455 // Tell the caller to allocate to this newly freed physical register.
458 // No other spill candidates were found, so spill the current lvr.
459 DEBUG(dbgs() << "spilling: " << lvr << '\n');
460 SmallVector<LiveInterval*, 1> pendingSpills;
461 spiller().spill(&lvr, splitLVRs, pendingSpills);
463 // The live virtual register requesting allocation was spilled, so tell
464 // the caller not to allocate anything during this round.
469 Spiller *createInlineSpiller(MachineFunctionPass &pass,
474 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
475 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
476 << "********** Function: "
477 << ((Value*)mf.getFunction())->getName() << '\n');
480 tm_ = &mf.getTarget();
481 mri_ = &mf.getRegInfo();
483 DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
485 const TargetRegisterInfo *TRI = tm_->getRegisterInfo();
486 RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(),
487 getAnalysis<LiveIntervals>());
489 reservedRegs_ = TRI->getReservedRegs(*mf_);
491 // We may want to force InlineSpiller for this register allocator. For
492 // now we're also experimenting with the standard spiller.
494 //spiller_.reset(createInlineSpiller(*this, *mf_, *vrm_));
495 spiller_.reset(createSpiller(*this, *mf_, *vrm_));
499 // Diagnostic output before rewriting
500 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
502 // optional HTML output
503 DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
505 // FIXME: Verification currently must run before VirtRegRewriter. We should
506 // make the rewriter a separate pass and override verifyAnalysis instead. When
507 // that happens, verification naturally falls under VerifyMachineCode.
509 if (VerifyRegAlloc) {
510 // Verify accuracy of LiveIntervals. The standard machine code verifier
511 // ensures that each LiveIntervals covers all uses of the virtual reg.
513 // FIXME: MachineVerifier is currently broken when using the standard
514 // spiller. Enable it for InlineSpiller only.
515 // mf_->verify(this);
517 // Verify that LiveIntervals are partitioned into unions and disjoint within
524 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
525 rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
527 // The pass output is in VirtRegMap. Release all the transient data.
533 FunctionPass* llvm::createBasicRegisterAllocator()
535 return new RABasic();