RegAllocBasic.cpp revision 2b38c51f0ece16ef00068da56bee4623fb9ae485
1//===-- RegAllocBasic.cpp - basic register allocator ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the RABasic function pass, which provides a minimal 11// implementation of the basic register allocator. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "LiveIntervalUnion.h" 17#include "RegAllocBase.h" 18#include "RenderMachineFunction.h" 19#include "Spiller.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" 38#ifndef NDEBUG 39#include "llvm/ADT/SparseBitVector.h" 40#endif 41#include "llvm/Support/Debug.h" 42#include "llvm/Support/ErrorHandling.h" 43#include "llvm/Support/raw_ostream.h" 44 45#include <vector> 46#include <queue> 47 48using namespace llvm; 49 50static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", 51 createBasicRegisterAllocator); 52 53// Temporary verification option until we can put verification inside 54// MachineVerifier. 55static cl::opt<bool> 56VerifyRegAlloc("verify-regalloc", 57 cl::desc("Verify live intervals before renaming")); 58 59namespace { 60 61class PhysicalRegisterDescription : public AbstractRegisterDescription { 62 const TargetRegisterInfo *TRI; 63public: 64 PhysicalRegisterDescription(const TargetRegisterInfo *T): TRI(T) {} 65 virtual const char *getName(unsigned Reg) const { return TRI->getName(Reg); } 66}; 67 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. 73class RABasic : public MachineFunctionPass, public RegAllocBase 74{ 75 // context 76 MachineFunction *MF; 77 const TargetMachine *TM; 78 MachineRegisterInfo *MRI; 79 80 BitVector ReservedRegs; 81 82 // analyses 83 LiveStacks *LS; 84 RenderMachineFunction *RMF; 85 86 // state 87 std::auto_ptr<Spiller> SpillerInstance; 88 89public: 90 RABasic(); 91 92 /// Return the pass name. 93 virtual const char* getPassName() const { 94 return "Basic Register Allocator"; 95 } 96 97 /// RABasic analysis usage. 98 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 99 100 virtual void releaseMemory(); 101 102 virtual Spiller &spiller() { return *SpillerInstance; } 103 104 virtual unsigned selectOrSplit(LiveInterval &VirtReg, 105 SmallVectorImpl<LiveInterval*> &SplitVRegs); 106 107 /// Perform register allocation. 108 virtual bool runOnMachineFunction(MachineFunction &mf); 109 110 static char ID; 111 112private: 113 void addMBBLiveIns(); 114}; 115 116char RABasic::ID = 0; 117 118} // end anonymous namespace 119 120RABasic::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()); 131} 132 133void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { 134 AU.setPreservesCFG(); 135 AU.addRequired<AliasAnalysis>(); 136 AU.addPreserved<AliasAnalysis>(); 137 AU.addRequired<LiveIntervals>(); 138 AU.addPreserved<SlotIndexes>(); 139 if (StrongPHIElim) 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); 153} 154 155void RABasic::releaseMemory() { 156 SpillerInstance.reset(0); 157 RegAllocBase::releaseMemory(); 158} 159 160#ifndef NDEBUG 161// Verify each LiveIntervalUnion. 162void RegAllocBase::verify() { 163 LiveVirtRegBitSet VisitedVRegs; 164 OwningArrayPtr<LiveVirtRegBitSet> 165 unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]); 166 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; 177 } 178 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"); 190 } 191 } 192 // FIXME: I'm not sure how to verify spilled intervals. 193} 194#endif //!NDEBUG 195 196//===----------------------------------------------------------------------===// 197// RegAllocBase Implementation 198//===----------------------------------------------------------------------===// 199 200// Instantiate a LiveIntervalUnion for each physical register. 201void RegAllocBase::LiveUnionArray::init(unsigned NRegs) { 202 Array.reset(new LiveIntervalUnion[NRegs]); 203 NumRegs = NRegs; 204 for (unsigned RegNum = 0; RegNum < NRegs; ++RegNum) { 205 Array[RegNum].init(RegNum); 206 } 207} 208 209void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm, 210 LiveIntervals &lis) { 211 TRI = &tri; 212 VRM = &vrm; 213 LIS = &lis; 214 PhysReg2LiveUnion.init(TRI->getNumRegs()); 215 // Cache an interferece query for each physical reg 216 Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); 217} 218 219void RegAllocBase::LiveUnionArray::clear() { 220 NumRegs = 0; 221 Array.reset(0); 222} 223 224void RegAllocBase::releaseMemory() { 225 PhysReg2LiveUnion.clear(); 226} 227 228namespace llvm { 229/// This class defines a queue of live virtual registers prioritized by spill 230/// weight. The heaviest vreg is popped first. 231/// 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. 235class LiveVirtRegQueue { 236 typedef std::priority_queue 237 <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> 238 PriorityQ; 239 PriorityQ PQ; 240 241public: 242 // Is the queue empty? 243 bool empty() { return PQ.empty(); } 244 245 // Get the highest priority lvr (top + pop) 246 LiveInterval *get() { 247 LiveInterval *VirtReg = PQ.top(); 248 PQ.pop(); 249 return VirtReg; 250 } 251 // Add this lvr to the queue 252 void push(LiveInterval *VirtReg) { 253 PQ.push(VirtReg); 254 } 255}; 256} // end namespace llvm 257 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. 261void 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); 267 } 268 else { 269 VirtRegQ.push(&VirtReg); 270 } 271 } 272} 273 274// Top-level driver to manage the queue of unassigned VirtRegs and call the 275// selectOrSplit implementation. 276void RegAllocBase::allocatePhysRegs() { 277 278 // Push each vreg onto a queue or "precolor" by adding it to a physreg union. 279 LiveVirtRegQueue VirtRegQ; 280 seedLiveVirtRegs(VirtRegQ); 281 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(); 286 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); 293 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); 300 } 301 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 302 I != E; ++I) { 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); 309 } 310 } 311} 312 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. 316unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, 317 unsigned PhysReg) { 318 if (query(VirtReg, PhysReg).checkInterference()) 319 return PhysReg; 320 for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) { 321 if (query(VirtReg, *AliasI).checkInterference()) 322 return *AliasI; 323 } 324 return 0; 325} 326 327// Helper for spillInteferences() that spills all interfering vregs currently 328// assigned to this physical register. 329void 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(); 334 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'); 340 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); 344 345 // Clear the vreg assignment. 346 VRM->clearVirt(SpilledVReg.reg); 347 348 // Spill the extracted interval. 349 spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills); 350 } 351 // After extracting segments, the query's results are invalid. But keep the 352 // contents valid until we're done accessing pendingSpills. 353 Q.clear(); 354} 355 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. 359bool 360RegAllocBase::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. 364 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()) { 369 return false; 370 } 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()) { 376 return false; 377 } 378 } 379 DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) << 380 " interferences with " << VirtReg << "\n"); 381 assert(NumInterferences > 0 && "expect interference"); 382 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); 387 return true; 388} 389 390//===----------------------------------------------------------------------===// 391// RABasic Implementation 392//===----------------------------------------------------------------------===// 393 394// Driver for the register assignment and splitting heuristics. 395// Manages iteration over the LiveIntervalUnions. 396// 397// This is a minimal implementation of register assignment and splitting that 398// spills whenever we run out of registers. 399// 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 405// selectOrSplit(). 406unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, 407 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 408 // Populate a list of physical register spill candidates. 409 SmallVector<unsigned, 8> PhysRegSpillCands; 410 411 // Check for an available register in this class. 412 const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg); 413 DEBUG(dbgs() << "RegClass: " << TRC->getName() << ' '); 414 415 for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF), 416 E = TRC->allocation_order_end(*MF); 417 I != E; ++I) { 418 419 unsigned PhysReg = *I; 420 if (ReservedRegs.test(PhysReg)) continue; 421 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. 427 return PhysReg; 428 } 429 LiveInterval *interferingVirtReg = 430 Queries[interfReg].firstInterference().liveUnionPos()->VirtReg; 431 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); 436 } 437 } 438 // Try to spill another interfering reg with less spill weight. 439 // 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) { 443 444 if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; 445 446 assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && 447 "Interference after spill."); 448 // Tell the caller to allocate to this newly freed physical register. 449 return *PhysRegI; 450 } 451 // No other spill candidates were found, so spill the current VirtReg. 452 DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); 453 SmallVector<LiveInterval*, 1> pendingSpills; 454 455 spiller().spill(&VirtReg, SplitVRegs, pendingSpills); 456 457 // The live virtual register requesting allocation was spilled, so tell 458 // the caller not to allocate anything during this round. 459 return 0; 460} 461 462// Add newly allocated physical registers to the MBB live in sets. 463void RABasic::addMBBLiveIns() { 464 typedef SmallVector<MachineBasicBlock*, 8> MBBVec; 465 MBBVec liveInMBBs; 466 MachineBasicBlock &entryMBB = *MF->begin(); 467 468 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 469 LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg]; 470 471 for (LiveIntervalUnion::SegmentIter SI = LiveUnion.begin(), 472 SegEnd = LiveUnion.end(); 473 SI != SegEnd; ++SI) { 474 475 // Find the set of basic blocks which this range is live into... 476 liveInMBBs.clear(); 477 if (!LIS->findLiveInMBBs(SI->Start, SI->End, liveInMBBs)) continue; 478 479 // And add the physreg for this interval to their live-in sets. 480 for (MBBVec::iterator I = liveInMBBs.begin(), E = liveInMBBs.end(); 481 I != E; ++I) { 482 MachineBasicBlock *MBB = *I; 483 if (MBB == &entryMBB) continue; 484 if (MBB->isLiveIn(PhysReg)) continue; 485 MBB->addLiveIn(PhysReg); 486 } 487 } 488 } 489} 490 491bool RABasic::runOnMachineFunction(MachineFunction &mf) { 492 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" 493 << "********** Function: " 494 << ((Value*)mf.getFunction())->getName() << '\n'); 495 496 MF = &mf; 497 TM = &mf.getTarget(); 498 MRI = &mf.getRegInfo(); 499 500 DEBUG(RMF = &getAnalysis<RenderMachineFunction>()); 501 502 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 503 RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(), 504 getAnalysis<LiveIntervals>()); 505 506 ReservedRegs = TRI->getReservedRegs(*MF); 507 508 SpillerInstance.reset(createSpiller(*this, *MF, *VRM)); 509 510 allocatePhysRegs(); 511 512 addMBBLiveIns(); 513 514 // Diagnostic output before rewriting 515 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); 516 517 // optional HTML output 518 DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM)); 519 520 // FIXME: Verification currently must run before VirtRegRewriter. We should 521 // make the rewriter a separate pass and override verifyAnalysis instead. When 522 // that happens, verification naturally falls under VerifyMachineCode. 523#ifndef NDEBUG 524 if (VerifyRegAlloc) { 525 // Verify accuracy of LiveIntervals. The standard machine code verifier 526 // ensures that each LiveIntervals covers all uses of the virtual reg. 527 528 // FIXME: MachineVerifier is badly broken when using the standard 529 // spiller. Always use -spiller=inline with -verify-regalloc. Even with the 530 // inline spiller, some tests fail to verify because the coalescer does not 531 // always generate verifiable code. 532 MF->verify(this); 533 534 // Verify that LiveIntervals are partitioned into unions and disjoint within 535 // the unions. 536 verify(); 537 } 538#endif // !NDEBUG 539 540 // Run rewriter 541 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 542 rewriter->runOnMachineFunction(*MF, *VRM, LIS); 543 544 // The pass output is in VirtRegMap. Release all the transient data. 545 releaseMemory(); 546 547 return true; 548} 549 550FunctionPass* llvm::createBasicRegisterAllocator() 551{ 552 return new RABasic(); 553} 554