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 *T): TRI(T) {}
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;
80 BitVector ReservedRegs;
84 RenderMachineFunction *RMF;
87 std::auto_ptr<Spiller> SpillerInstance;
92 /// Return the pass name.
93 virtual const char* getPassName() const {
94 return "Basic Register Allocator";
97 /// RABasic analysis usage.
98 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
100 virtual void releaseMemory();
102 virtual Spiller &spiller() { return *SpillerInstance; }
104 virtual unsigned selectOrSplit(LiveInterval &VirtReg,
105 SmallVectorImpl<LiveInterval*> &SplitVRegs);
107 /// Perform register allocation.
108 virtual bool runOnMachineFunction(MachineFunction &mf);
113 void addMBBLiveIns();
116 char RABasic::ID = 0;
118 } // end anonymous namespace
120 RABasic::RABasic(): MachineFunctionPass(ID) {
121 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
122 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
123 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
124 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
125 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
126 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
127 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
128 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
129 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
130 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
133 void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
134 AU.setPreservesCFG();
135 AU.addRequired<AliasAnalysis>();
136 AU.addPreserved<AliasAnalysis>();
137 AU.addRequired<LiveIntervals>();
138 AU.addPreserved<SlotIndexes>();
140 AU.addRequiredID(StrongPHIEliminationID);
141 AU.addRequiredTransitive<RegisterCoalescer>();
142 AU.addRequired<CalculateSpillWeights>();
143 AU.addRequired<LiveStacks>();
144 AU.addPreserved<LiveStacks>();
145 AU.addRequiredID(MachineDominatorsID);
146 AU.addPreservedID(MachineDominatorsID);
147 AU.addRequired<MachineLoopInfo>();
148 AU.addPreserved<MachineLoopInfo>();
149 AU.addRequired<VirtRegMap>();
150 AU.addPreserved<VirtRegMap>();
151 DEBUG(AU.addRequired<RenderMachineFunction>());
152 MachineFunctionPass::getAnalysisUsage(AU);
155 void RABasic::releaseMemory() {
156 SpillerInstance.reset(0);
157 RegAllocBase::releaseMemory();
161 // Verify each LiveIntervalUnion.
162 void RegAllocBase::verify() {
163 LiveVirtRegBitSet VisitedVRegs;
164 OwningArrayPtr<LiveVirtRegBitSet>
165 unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]);
167 // Verify disjoint unions.
168 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) {
169 DEBUG(PhysicalRegisterDescription PRD(TRI);
170 PhysReg2LiveUnion[PhysReg].dump(&PRD));
171 LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg];
172 PhysReg2LiveUnion[PhysReg].verify(VRegs);
173 // Union + intersection test could be done efficiently in one pass, but
174 // don't add a method to SparseBitVector unless we really need it.
175 assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions");
176 VisitedVRegs |= VRegs;
179 // Verify vreg coverage.
180 for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end();
181 liItr != liEnd; ++liItr) {
182 unsigned reg = liItr->first;
183 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue;
184 if (!VRM->hasPhys(reg)) continue; // spilled?
185 unsigned PhysReg = VRM->getPhys(reg);
186 if (!unionVRegs[PhysReg].test(reg)) {
187 dbgs() << "LiveVirtReg " << reg << " not in union " <<
188 TRI->getName(PhysReg) << "\n";
189 llvm_unreachable("unallocated live vreg");
192 // FIXME: I'm not sure how to verify spilled intervals.
196 //===----------------------------------------------------------------------===//
197 // RegAllocBase Implementation
198 //===----------------------------------------------------------------------===//
200 // Instantiate a LiveIntervalUnion for each physical register.
201 void RegAllocBase::LiveUnionArray::init(unsigned NRegs) {
202 Array.reset(new LiveIntervalUnion[NRegs]);
204 for (unsigned RegNum = 0; RegNum < NRegs; ++RegNum) {
205 Array[RegNum].init(RegNum);
209 void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
210 LiveIntervals &lis) {
214 PhysReg2LiveUnion.init(TRI->getNumRegs());
215 // Cache an interferece query for each physical reg
216 Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]);
219 void RegAllocBase::LiveUnionArray::clear() {
224 void RegAllocBase::releaseMemory() {
225 PhysReg2LiveUnion.clear();
229 /// This class defines a queue of live virtual registers prioritized by spill
230 /// weight. The heaviest vreg is popped first.
232 /// Currently, this is trivial wrapper that gives us an opaque type in the
233 /// header, but we may later give it a virtual interface for register allocators
234 /// to override the priority queue comparator.
235 class LiveVirtRegQueue {
236 typedef std::priority_queue
237 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority>
242 // Is the queue empty?
243 bool empty() { return PQ.empty(); }
245 // Get the highest priority lvr (top + pop)
246 LiveInterval *get() {
247 LiveInterval *VirtReg = PQ.top();
251 // Add this lvr to the queue
252 void push(LiveInterval *VirtReg) {
256 } // end namespace llvm
258 // Visit all the live virtual registers. If they are already assigned to a
259 // physical register, unify them with the corresponding LiveIntervalUnion,
260 // otherwise push them on the priority queue for later assignment.
261 void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ) {
262 for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) {
263 unsigned RegNum = I->first;
264 LiveInterval &VirtReg = *I->second;
265 if (TargetRegisterInfo::isPhysicalRegister(RegNum)) {
266 PhysReg2LiveUnion[RegNum].unify(VirtReg);
269 VirtRegQ.push(&VirtReg);
274 // Top-level driver to manage the queue of unassigned VirtRegs and call the
275 // selectOrSplit implementation.
276 void RegAllocBase::allocatePhysRegs() {
278 // Push each vreg onto a queue or "precolor" by adding it to a physreg union.
279 LiveVirtRegQueue VirtRegQ;
280 seedLiveVirtRegs(VirtRegQ);
282 // Continue assigning vregs one at a time to available physical registers.
283 while (!VirtRegQ.empty()) {
284 // Pop the highest priority vreg.
285 LiveInterval *VirtReg = VirtRegQ.get();
287 // selectOrSplit requests the allocator to return an available physical
288 // register if possible and populate a list of new live intervals that
289 // result from splitting.
290 typedef SmallVector<LiveInterval*, 4> VirtRegVec;
291 VirtRegVec SplitVRegs;
292 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
294 if (AvailablePhysReg) {
295 DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg) <<
296 " " << *VirtReg << '\n');
297 assert(!VRM->hasPhys(VirtReg->reg) && "duplicate vreg in union");
298 VRM->assignVirt2Phys(VirtReg->reg, AvailablePhysReg);
299 PhysReg2LiveUnion[AvailablePhysReg].unify(*VirtReg);
301 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end();
303 LiveInterval* SplitVirtReg = *I;
304 if (SplitVirtReg->empty()) continue;
305 DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
306 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
307 "expect split value in virtual register");
308 VirtRegQ.push(SplitVirtReg);
313 // Check if this live virtual register interferes with a physical register. If
314 // not, then check for interference on each register that aliases with the
315 // physical register. Return the interfering register.
316 unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg,
318 if (query(VirtReg, PhysReg).checkInterference())
320 for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) {
321 if (query(VirtReg, *AliasI).checkInterference())
327 // Helper for spillInteferences() that spills all interfering vregs currently
328 // assigned to this physical register.
329 void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg,
330 SmallVectorImpl<LiveInterval*> &SplitVRegs) {
331 LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg);
332 assert(Q.seenAllInterferences() && "need collectInterferences()");
333 const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs();
335 for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(),
336 E = PendingSpills.end(); I != E; ++I) {
337 LiveInterval &SpilledVReg = **I;
338 DEBUG(dbgs() << "extracting from " <<
339 TRI->getName(PhysReg) << " " << SpilledVReg << '\n');
341 // Deallocate the interfering vreg by removing it from the union.
342 // A LiveInterval instance may not be in a union during modification!
343 PhysReg2LiveUnion[PhysReg].extract(SpilledVReg);
345 // Clear the vreg assignment.
346 VRM->clearVirt(SpilledVReg.reg);
348 // Spill the extracted interval.
349 spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills);
351 // After extracting segments, the query's results are invalid. But keep the
352 // contents valid until we're done accessing pendingSpills.
356 // Spill or split all live virtual registers currently unified under PhysReg
357 // that interfere with VirtReg. The newly spilled or split live intervals are
358 // returned by appending them to SplitVRegs.
360 RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
361 SmallVectorImpl<LiveInterval*> &SplitVRegs) {
362 // Record each interference and determine if all are spillable before mutating
363 // either the union or live intervals.
365 // Collect interferences assigned to the requested physical register.
366 LiveIntervalUnion::Query &QPreg = query(VirtReg, PhysReg);
367 unsigned NumInterferences = QPreg.collectInterferingVRegs();
368 if (QPreg.seenUnspillableVReg()) {
371 // Collect interferences assigned to any alias of the physical register.
372 for (const unsigned *asI = TRI->getAliasSet(PhysReg); *asI; ++asI) {
373 LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI);
374 NumInterferences += QAlias.collectInterferingVRegs();
375 if (QAlias.seenUnspillableVReg()) {
379 DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) <<
380 " interferences with " << VirtReg << "\n");
381 assert(NumInterferences > 0 && "expect interference");
383 // Spill each interfering vreg allocated to PhysReg or an alias.
384 spillReg(VirtReg, PhysReg, SplitVRegs);
385 for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI)
386 spillReg(VirtReg, *AliasI, SplitVRegs);
390 //===----------------------------------------------------------------------===//
391 // RABasic Implementation
392 //===----------------------------------------------------------------------===//
394 // Driver for the register assignment and splitting heuristics.
395 // Manages iteration over the LiveIntervalUnions.
397 // This is a minimal implementation of register assignment and splitting that
398 // spills whenever we run out of registers.
400 // selectOrSplit can only be called once per live virtual register. We then do a
401 // single interference test for each register the correct class until we find an
402 // available register. So, the number of interference tests in the worst case is
403 // |vregs| * |machineregs|. And since the number of interference tests is
404 // minimal, there is no value in caching them outside the scope of
406 unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
407 SmallVectorImpl<LiveInterval*> &SplitVRegs) {
408 // Populate a list of physical register spill candidates.
409 SmallVector<unsigned, 8> PhysRegSpillCands;
411 // Check for an available register in this class.
412 const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg);
413 DEBUG(dbgs() << "RegClass: " << TRC->getName() << ' ');
415 for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF),
416 E = TRC->allocation_order_end(*MF);
419 unsigned PhysReg = *I;
420 if (ReservedRegs.test(PhysReg)) continue;
422 // Check interference and as a side effect, intialize queries for this
423 // VirtReg and its aliases.
424 unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg);
425 if (interfReg == 0) {
426 // Found an available register.
429 LiveInterval *interferingVirtReg =
430 Queries[interfReg].firstInterference().liveUnionPos()->VirtReg;
432 // The current VirtReg must either spillable, or one of its interferences
433 // must have less spill weight.
434 if (interferingVirtReg->weight < VirtReg.weight ) {
435 PhysRegSpillCands.push_back(PhysReg);
438 // Try to spill another interfering reg with less spill weight.
440 // FIXME: RAGreedy will sort this list by spill weight.
441 for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
442 PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
444 if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
446 unsigned InterferingReg = checkPhysRegInterference(VirtReg, *PhysRegI);
447 if (InterferingReg != 0) {
448 const LiveSegment &seg =
449 *Queries[InterferingReg].firstInterference().liveUnionPos();
451 dbgs() << "spilling cannot free " << TRI->getName(*PhysRegI) <<
452 " for " << VirtReg.reg << " with interference " << *seg.VirtReg << "\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 VirtReg.
459 DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
460 SmallVector<LiveInterval*, 1> pendingSpills;
462 spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
464 // The live virtual register requesting allocation was spilled, so tell
465 // the caller not to allocate anything during this round.
469 // Add newly allocated physical registers to the MBB live in sets.
470 void RABasic::addMBBLiveIns() {
471 typedef SmallVector<MachineBasicBlock*, 8> MBBVec;
473 MachineBasicBlock &entryMBB = *MF->begin();
475 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) {
476 LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg];
478 for (LiveIntervalUnion::SegmentIter SI = LiveUnion.begin(),
479 SegEnd = LiveUnion.end();
480 SI != SegEnd; ++SI) {
482 // Find the set of basic blocks which this range is live into...
484 if (!LIS->findLiveInMBBs(SI->Start, SI->End, liveInMBBs)) continue;
486 // And add the physreg for this interval to their live-in sets.
487 for (MBBVec::iterator I = liveInMBBs.begin(), E = liveInMBBs.end();
489 MachineBasicBlock *MBB = *I;
490 if (MBB == &entryMBB) continue;
491 if (MBB->isLiveIn(PhysReg)) continue;
492 MBB->addLiveIn(PhysReg);
498 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
499 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
500 << "********** Function: "
501 << ((Value*)mf.getFunction())->getName() << '\n');
504 TM = &mf.getTarget();
505 MRI = &mf.getRegInfo();
507 DEBUG(RMF = &getAnalysis<RenderMachineFunction>());
509 const TargetRegisterInfo *TRI = TM->getRegisterInfo();
510 RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(),
511 getAnalysis<LiveIntervals>());
513 ReservedRegs = TRI->getReservedRegs(*MF);
515 SpillerInstance.reset(createSpiller(*this, *MF, *VRM));
521 // Diagnostic output before rewriting
522 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
524 // optional HTML output
525 DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM));
527 // FIXME: Verification currently must run before VirtRegRewriter. We should
528 // make the rewriter a separate pass and override verifyAnalysis instead. When
529 // that happens, verification naturally falls under VerifyMachineCode.
531 if (VerifyRegAlloc) {
532 // Verify accuracy of LiveIntervals. The standard machine code verifier
533 // ensures that each LiveIntervals covers all uses of the virtual reg.
535 // FIXME: MachineVerifier is badly broken when using the standard
536 // spiller. Always use -spiller=inline with -verify-regalloc. Even with the
537 // inline spiller, some tests fail to verify because the coalescer does not
538 // always generate verifiable code.
541 // Verify that LiveIntervals are partitioned into unions and disjoint within
548 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
549 rewriter->runOnMachineFunction(*MF, *VRM, LIS);
551 // The pass output is in VirtRegMap. Release all the transient data.
557 FunctionPass* llvm::createBasicRegisterAllocator()
559 return new RABasic();