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"));
61 class PhysicalRegisterDescription : public AbstractRegisterDescription {
62 const TargetRegisterInfo *tri_;
64 PhysicalRegisterDescription(const TargetRegisterInfo *tri): tri_(tri) {}
65 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 void addMBBLiveIns();
115 char RABasic::ID = 0;
117 } // end anonymous namespace
119 // We should not need to publish the initializer as long as no other passes
121 #if 0 // disable INITIALIZE_PASS
122 INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
123 "Basic Register Allocator", false, false)
124 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
125 INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
126 INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
127 INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
128 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
129 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
130 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
132 INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
134 INITIALIZE_PASS_END(RABasic, "basic-regalloc",
135 "Basic Register Allocator", false, false)
136 #endif // disable INITIALIZE_PASS
138 RABasic::RABasic(): MachineFunctionPass(ID) {
139 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
140 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
141 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
142 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
143 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
144 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
145 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
146 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
147 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
148 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
151 void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
152 au.setPreservesCFG();
153 au.addRequired<AliasAnalysis>();
154 au.addPreserved<AliasAnalysis>();
155 au.addRequired<LiveIntervals>();
156 au.addPreserved<SlotIndexes>();
158 au.addRequiredID(StrongPHIEliminationID);
159 au.addRequiredTransitive<RegisterCoalescer>();
160 au.addRequired<CalculateSpillWeights>();
161 au.addRequired<LiveStacks>();
162 au.addPreserved<LiveStacks>();
163 au.addRequiredID(MachineDominatorsID);
164 au.addPreservedID(MachineDominatorsID);
165 au.addRequired<MachineLoopInfo>();
166 au.addPreserved<MachineLoopInfo>();
167 au.addRequired<VirtRegMap>();
168 au.addPreserved<VirtRegMap>();
169 DEBUG(au.addRequired<RenderMachineFunction>());
170 MachineFunctionPass::getAnalysisUsage(au);
173 void RABasic::releaseMemory() {
175 RegAllocBase::releaseMemory();
179 // Verify each LiveIntervalUnion.
180 void RegAllocBase::verify() {
181 LvrBitSet visitedVRegs;
182 OwningArrayPtr<LvrBitSet> unionVRegs(new LvrBitSet[physReg2liu_.numRegs()]);
183 // Verify disjoint unions.
184 for (unsigned preg = 0; preg < physReg2liu_.numRegs(); ++preg) {
185 DEBUG(PhysicalRegisterDescription prd(tri_); physReg2liu_[preg].dump(&prd));
186 LvrBitSet &vregs = unionVRegs[preg];
187 physReg2liu_[preg].verify(vregs);
188 // Union + intersection test could be done efficiently in one pass, but
189 // don't add a method to SparseBitVector unless we really need it.
190 assert(!visitedVRegs.intersects(vregs) && "vreg in multiple unions");
191 visitedVRegs |= vregs;
193 // Verify vreg coverage.
194 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
195 liItr != liEnd; ++liItr) {
196 unsigned reg = liItr->first;
197 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue;
198 if (!vrm_->hasPhys(reg)) continue; // spilled?
199 unsigned preg = vrm_->getPhys(reg);
200 if (!unionVRegs[preg].test(reg)) {
201 dbgs() << "LiveVirtReg " << reg << " not in union " <<
202 tri_->getName(preg) << "\n";
203 llvm_unreachable("unallocated live vreg");
206 // FIXME: I'm not sure how to verify spilled intervals.
210 //===----------------------------------------------------------------------===//
211 // RegAllocBase Implementation
212 //===----------------------------------------------------------------------===//
214 // Instantiate a LiveIntervalUnion for each physical register.
215 void RegAllocBase::LIUArray::init(unsigned nRegs) {
216 array_.reset(new LiveIntervalUnion[nRegs]);
218 for (unsigned pr = 0; pr < nRegs; ++pr) {
223 void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
224 LiveIntervals &lis) {
228 physReg2liu_.init(tri_->getNumRegs());
229 // Cache an interferece query for each physical reg
230 queries_.reset(new LiveIntervalUnion::Query[physReg2liu_.numRegs()]);
233 void RegAllocBase::LIUArray::clear() {
238 void RegAllocBase::releaseMemory() {
239 physReg2liu_.clear();
243 /// This class defines a queue of live virtual registers prioritized by spill
244 /// weight. The heaviest vreg is popped first.
246 /// Currently, this is trivial wrapper that gives us an opaque type in the
247 /// header, but we may later give it a virtual interface for register allocators
248 /// to override the priority queue comparator.
249 class LiveVirtRegQueue {
250 typedef std::priority_queue
251 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
255 // Is the queue empty?
256 bool empty() { return pq_.empty(); }
258 // Get the highest priority lvr (top + pop)
259 LiveInterval *get() {
260 LiveInterval *lvr = pq_.top();
264 // Add this lvr to the queue
265 void push(LiveInterval *lvr) {
269 } // end namespace llvm
271 // Visit all the live virtual registers. If they are already assigned to a
272 // physical register, unify them with the corresponding LiveIntervalUnion,
273 // otherwise push them on the priority queue for later assignment.
274 void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
275 for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
276 liItr != liEnd; ++liItr) {
277 unsigned reg = liItr->first;
278 LiveInterval &li = *liItr->second;
279 if (TargetRegisterInfo::isPhysicalRegister(reg)) {
280 physReg2liu_[reg].unify(li);
288 // Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
289 // selectOrSplit implementation.
290 void RegAllocBase::allocatePhysRegs() {
291 LiveVirtRegQueue lvrQ;
292 seedLiveVirtRegs(lvrQ);
293 while (!lvrQ.empty()) {
294 LiveInterval *lvr = lvrQ.get();
295 typedef SmallVector<LiveInterval*, 4> LVRVec;
297 unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
298 if (availablePhysReg) {
299 DEBUG(dbgs() << "allocating: " << tri_->getName(availablePhysReg) <<
300 " " << *lvr << '\n');
301 assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
302 vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
303 physReg2liu_[availablePhysReg].unify(*lvr);
305 for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
306 lvrI != lvrEnd; ++lvrI) {
307 if ((*lvrI)->empty()) continue;
308 DEBUG(dbgs() << "queuing new interval: " << **lvrI << "\n");
309 assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
310 "expect split value in virtual register");
316 // Check if this live virtual reg interferes with a physical register. If not,
317 // then check for interference on each register that aliases with the physical
318 // register. Return the interfering register.
319 unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &lvr,
321 if (query(lvr, preg).checkInterference())
323 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
324 if (query(lvr, *asI).checkInterference())
330 // Sort live virtual registers by their register number.
331 struct LessLiveVirtualReg
332 : public std::binary_function<LiveInterval, LiveInterval, bool> {
333 bool operator()(const LiveInterval *left, const LiveInterval *right) const {
334 return left->reg < right->reg;
338 // Spill all interferences currently assigned to this physical register.
339 void RegAllocBase::spillReg(LiveInterval& lvr, unsigned reg,
340 SmallVectorImpl<LiveInterval*> &splitLVRs) {
341 LiveIntervalUnion::Query &Q = query(lvr, reg);
342 const SmallVectorImpl<LiveInterval*> &pendingSpills = Q.interferingVRegs();
344 for (SmallVectorImpl<LiveInterval*>::const_iterator I = pendingSpills.begin(),
345 E = pendingSpills.end(); I != E; ++I) {
346 LiveInterval &spilledLVR = **I;
347 DEBUG(dbgs() << "extracting from " <<
348 tri_->getName(reg) << " " << spilledLVR << '\n');
350 // Deallocate the interfering vreg by removing it from the union.
351 // A LiveInterval instance may not be in a union during modification!
352 physReg2liu_[reg].extract(spilledLVR);
354 // Clear the vreg assignment.
355 vrm_->clearVirt(spilledLVR.reg);
357 // Spill the extracted interval.
358 spiller().spill(&spilledLVR, splitLVRs, pendingSpills);
360 // After extracting segments, the query's results are invalid. But keep the
361 // contents valid until we're done accessing pendingSpills.
365 // Spill or split all live virtual registers currently unified under preg that
366 // interfere with lvr. The newly spilled or split live intervals are returned by
367 // appending them to splitLVRs.
369 RegAllocBase::spillInterferences(LiveInterval &lvr, unsigned preg,
370 SmallVectorImpl<LiveInterval*> &splitLVRs) {
371 // Record each interference and determine if all are spillable before mutating
372 // either the union or live intervals.
374 // Collect interferences assigned to the requested physical register.
375 LiveIntervalUnion::Query &QPreg = query(lvr, preg);
376 unsigned numInterferences = QPreg.collectInterferingVRegs();
377 if (QPreg.seenUnspillableVReg()) {
380 // Collect interferences assigned to any alias of the physical register.
381 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
382 LiveIntervalUnion::Query &QAlias = query(lvr, *asI);
383 numInterferences += QAlias.collectInterferingVRegs();
384 if (QAlias.seenUnspillableVReg()) {
388 DEBUG(dbgs() << "spilling " << tri_->getName(preg) <<
389 " interferences with " << lvr << "\n");
390 assert(numInterferences > 0 && "expect interference");
392 // Spill each interfering vreg allocated to preg or an alias.
393 spillReg(lvr, preg, splitLVRs);
394 for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI)
395 spillReg(lvr, *asI, splitLVRs);
399 //===----------------------------------------------------------------------===//
400 // RABasic Implementation
401 //===----------------------------------------------------------------------===//
403 // Driver for the register assignment and splitting heuristics.
404 // Manages iteration over the LiveIntervalUnions.
406 // Minimal implementation of register assignment and splitting--spills whenever
407 // we run out of registers.
409 // selectOrSplit can only be called once per live virtual register. We then do a
410 // single interference test for each register the correct class until we find an
411 // available register. So, the number of interference tests in the worst case is
412 // |vregs| * |machineregs|. And since the number of interference tests is
413 // minimal, there is no value in caching them.
414 unsigned RABasic::selectOrSplit(LiveInterval &lvr,
415 SmallVectorImpl<LiveInterval*> &splitLVRs) {
416 // Populate a list of physical register spill candidates.
417 SmallVector<unsigned, 8> pregSpillCands;
419 // Check for an available register in this class.
420 const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
421 for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
422 trcEnd = trc->allocation_order_end(*mf_);
423 trcI != trcEnd; ++trcI) {
424 unsigned preg = *trcI;
425 if (reservedRegs_.test(preg)) continue;
427 // Check interference and intialize queries for this lvr as a side effect.
428 unsigned interfReg = checkPhysRegInterference(lvr, preg);
429 if (interfReg == 0) {
430 // Found an available register.
433 LiveInterval *interferingVirtReg =
434 queries_[interfReg].firstInterference().liuSegPos()->liveVirtReg;
436 // The current lvr must either spillable, or one of its interferences must
437 // have less spill weight.
438 if (interferingVirtReg->weight < lvr.weight ) {
439 pregSpillCands.push_back(preg);
442 // Try to spill another interfering reg with less spill weight.
444 // FIXME: RAGreedy will sort this list by spill weight.
445 for (SmallVectorImpl<unsigned>::iterator pregI = pregSpillCands.begin(),
446 pregE = pregSpillCands.end(); pregI != pregE; ++pregI) {
448 if (!spillInterferences(lvr, *pregI, splitLVRs)) continue;
450 unsigned interfReg = checkPhysRegInterference(lvr, *pregI);
451 if (interfReg != 0) {
452 const LiveSegment &seg =
453 *queries_[interfReg].firstInterference().liuSegPos();
454 dbgs() << "spilling cannot free " << tri_->getName(*pregI) <<
455 " for " << lvr.reg << " with interference " << *seg.liveVirtReg << "\n";
456 llvm_unreachable("Interference after spill.");
458 // Tell the caller to allocate to this newly freed physical register.
461 // No other spill candidates were found, so spill the current lvr.
462 DEBUG(dbgs() << "spilling: " << lvr << '\n');
463 SmallVector<LiveInterval*, 1> pendingSpills;
464 spiller().spill(&lvr, splitLVRs, pendingSpills);
466 // The live virtual register requesting allocation was spilled, so tell
467 // the caller not to allocate anything during this round.
471 // Add newly allocated physical register to the MBB live in sets.
472 void RABasic::addMBBLiveIns() {
473 SmallVector<MachineBasicBlock*, 8> liveInMBBs;
474 MachineBasicBlock &entryMBB = *mf_->begin();
476 for (unsigned preg = 0; preg < physReg2liu_.numRegs(); ++preg) {
477 LiveIntervalUnion &liu = physReg2liu_[preg];
478 for (LiveIntervalUnion::SegmentIter segI = liu.begin(), segE = liu.end();
479 segI != segE; ++segI) {
480 // Find the set of basic blocks which this range is live into...
481 if (lis_->findLiveInMBBs(segI->start, segI->end, liveInMBBs)) {
482 // And add the physreg for this interval to their live-in sets.
483 for (unsigned i = 0; i != liveInMBBs.size(); ++i) {
484 if (liveInMBBs[i] != &entryMBB) {
485 if (!liveInMBBs[i]->isLiveIn(preg)) {
486 liveInMBBs[i]->addLiveIn(preg);
497 Spiller *createInlineSpiller(MachineFunctionPass &pass,
502 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
503 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
504 << "********** Function: "
505 << ((Value*)mf.getFunction())->getName() << '\n');
508 tm_ = &mf.getTarget();
509 mri_ = &mf.getRegInfo();
511 DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
513 const TargetRegisterInfo *TRI = tm_->getRegisterInfo();
514 RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(),
515 getAnalysis<LiveIntervals>());
517 reservedRegs_ = TRI->getReservedRegs(*mf_);
519 // We may want to force InlineSpiller for this register allocator. For
520 // now we're also experimenting with the standard spiller.
522 //spiller_.reset(createInlineSpiller(*this, *mf_, *vrm_));
523 spiller_.reset(createSpiller(*this, *mf_, *vrm_));
529 // Diagnostic output before rewriting
530 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
532 // optional HTML output
533 DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
535 // FIXME: Verification currently must run before VirtRegRewriter. We should
536 // make the rewriter a separate pass and override verifyAnalysis instead. When
537 // that happens, verification naturally falls under VerifyMachineCode.
539 if (VerifyRegAlloc) {
540 // Verify accuracy of LiveIntervals. The standard machine code verifier
541 // ensures that each LiveIntervals covers all uses of the virtual reg.
543 // FIXME: MachineVerifier is currently broken when using the standard
544 // spiller. Enable it for InlineSpiller only.
545 // mf_->verify(this);
547 // Verify that LiveIntervals are partitioned into unions and disjoint within
554 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
555 rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
557 // The pass output is in VirtRegMap. Release all the transient data.
563 FunctionPass* llvm::createBasicRegisterAllocator()
565 return new RABasic();