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 "RegAllocBase.h" 17 #include "LiveDebugVariables.h" 18 #include "LiveIntervalUnion.h" 19 #include "LiveRangeEdit.h" 20 #include "RenderMachineFunction.h" 21 #include "Spiller.h" 22 #include "VirtRegMap.h" 23 #include "llvm/ADT/OwningPtr.h" 24 #include "llvm/ADT/Statistic.h" 25 #include "llvm/Analysis/AliasAnalysis.h" 26 #include "llvm/Function.h" 27 #include "llvm/PassAnalysisSupport.h" 28 #include "llvm/CodeGen/CalcSpillWeights.h" 29 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 30 #include "llvm/CodeGen/LiveStackAnalysis.h" 31 #include "llvm/CodeGen/MachineFunctionPass.h" 32 #include "llvm/CodeGen/MachineInstr.h" 33 #include "llvm/CodeGen/MachineLoopInfo.h" 34 #include "llvm/CodeGen/MachineRegisterInfo.h" 35 #include "llvm/CodeGen/Passes.h" 36 #include "llvm/CodeGen/RegAllocRegistry.h" 37 #include "llvm/Target/TargetMachine.h" 38 #include "llvm/Target/TargetOptions.h" 39 #include "llvm/Target/TargetRegisterInfo.h" 40 #ifndef NDEBUG 41 #include "llvm/ADT/SparseBitVector.h" 42 #endif 43 #include "llvm/Support/Debug.h" 44 #include "llvm/Support/ErrorHandling.h" 45 #include "llvm/Support/raw_ostream.h" 46 #include "llvm/Support/Timer.h" 47 48 #include <cstdlib> 49 #include <queue> 50 51 using namespace llvm; 52 53 STATISTIC(NumAssigned , "Number of registers assigned"); 54 STATISTIC(NumUnassigned , "Number of registers unassigned"); 55 STATISTIC(NumNewQueued , "Number of new live ranges queued"); 56 57 static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", 58 createBasicRegisterAllocator); 59 60 // Temporary verification option until we can put verification inside 61 // MachineVerifier. 62 static cl::opt<bool, true> 63 VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 64 cl::desc("Verify during register allocation")); 65 66 const char *RegAllocBase::TimerGroupName = "Register Allocation"; 67 bool RegAllocBase::VerifyEnabled = false; 68 69 namespace { 70 struct CompSpillWeight { 71 bool operator()(LiveInterval *A, LiveInterval *B) const { 72 return A->weight < B->weight; 73 } 74 }; 75 } 76 77 namespace { 78 /// RABasic provides a minimal implementation of the basic register allocation 79 /// algorithm. It prioritizes live virtual registers by spill weight and spills 80 /// whenever a register is unavailable. This is not practical in production but 81 /// provides a useful baseline both for measuring other allocators and comparing 82 /// the speed of the basic algorithm against other styles of allocators. 83 class RABasic : public MachineFunctionPass, public RegAllocBase 84 { 85 // context 86 MachineFunction *MF; 87 88 // analyses 89 LiveStacks *LS; 90 RenderMachineFunction *RMF; 91 92 // state 93 std::auto_ptr<Spiller> SpillerInstance; 94 std::priority_queue<LiveInterval*, std::vector<LiveInterval*>, 95 CompSpillWeight> Queue; 96 public: 97 RABasic(); 98 99 /// Return the pass name. 100 virtual const char* getPassName() const { 101 return "Basic Register Allocator"; 102 } 103 104 /// RABasic analysis usage. 105 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 106 107 virtual void releaseMemory(); 108 109 virtual Spiller &spiller() { return *SpillerInstance; } 110 111 virtual float getPriority(LiveInterval *LI) { return LI->weight; } 112 113 virtual void enqueue(LiveInterval *LI) { 114 Queue.push(LI); 115 } 116 117 virtual LiveInterval *dequeue() { 118 if (Queue.empty()) 119 return 0; 120 LiveInterval *LI = Queue.top(); 121 Queue.pop(); 122 return LI; 123 } 124 125 virtual unsigned selectOrSplit(LiveInterval &VirtReg, 126 SmallVectorImpl<LiveInterval*> &SplitVRegs); 127 128 /// Perform register allocation. 129 virtual bool runOnMachineFunction(MachineFunction &mf); 130 131 static char ID; 132 }; 133 134 char RABasic::ID = 0; 135 136 } // end anonymous namespace 137 138 RABasic::RABasic(): MachineFunctionPass(ID) { 139 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 140 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 141 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 142 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 143 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 144 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 145 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 146 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 147 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 148 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 149 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); 150 } 151 152 void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { 153 AU.setPreservesCFG(); 154 AU.addRequired<AliasAnalysis>(); 155 AU.addPreserved<AliasAnalysis>(); 156 AU.addRequired<LiveIntervals>(); 157 AU.addPreserved<SlotIndexes>(); 158 AU.addRequired<LiveDebugVariables>(); 159 AU.addPreserved<LiveDebugVariables>(); 160 if (StrongPHIElim) 161 AU.addRequiredID(StrongPHIEliminationID); 162 AU.addRequiredTransitiveID(RegisterCoalescerPassID); 163 AU.addRequired<CalculateSpillWeights>(); 164 AU.addRequired<LiveStacks>(); 165 AU.addPreserved<LiveStacks>(); 166 AU.addRequiredID(MachineDominatorsID); 167 AU.addPreservedID(MachineDominatorsID); 168 AU.addRequired<MachineLoopInfo>(); 169 AU.addPreserved<MachineLoopInfo>(); 170 AU.addRequired<VirtRegMap>(); 171 AU.addPreserved<VirtRegMap>(); 172 DEBUG(AU.addRequired<RenderMachineFunction>()); 173 MachineFunctionPass::getAnalysisUsage(AU); 174 } 175 176 void RABasic::releaseMemory() { 177 SpillerInstance.reset(0); 178 RegAllocBase::releaseMemory(); 179 } 180 181 #ifndef NDEBUG 182 // Verify each LiveIntervalUnion. 183 void RegAllocBase::verify() { 184 LiveVirtRegBitSet VisitedVRegs; 185 OwningArrayPtr<LiveVirtRegBitSet> 186 unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]); 187 188 // Verify disjoint unions. 189 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 190 DEBUG(PhysReg2LiveUnion[PhysReg].print(dbgs(), TRI)); 191 LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg]; 192 PhysReg2LiveUnion[PhysReg].verify(VRegs); 193 // Union + intersection test could be done efficiently in one pass, but 194 // don't add a method to SparseBitVector unless we really need it. 195 assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions"); 196 VisitedVRegs |= VRegs; 197 } 198 199 // Verify vreg coverage. 200 for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end(); 201 liItr != liEnd; ++liItr) { 202 unsigned reg = liItr->first; 203 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue; 204 if (!VRM->hasPhys(reg)) continue; // spilled? 205 unsigned PhysReg = VRM->getPhys(reg); 206 if (!unionVRegs[PhysReg].test(reg)) { 207 dbgs() << "LiveVirtReg " << reg << " not in union " << 208 TRI->getName(PhysReg) << "\n"; 209 llvm_unreachable("unallocated live vreg"); 210 } 211 } 212 // FIXME: I'm not sure how to verify spilled intervals. 213 } 214 #endif //!NDEBUG 215 216 //===----------------------------------------------------------------------===// 217 // RegAllocBase Implementation 218 //===----------------------------------------------------------------------===// 219 220 // Instantiate a LiveIntervalUnion for each physical register. 221 void RegAllocBase::LiveUnionArray::init(LiveIntervalUnion::Allocator &allocator, 222 unsigned NRegs) { 223 NumRegs = NRegs; 224 Array = 225 static_cast<LiveIntervalUnion*>(malloc(sizeof(LiveIntervalUnion)*NRegs)); 226 for (unsigned r = 0; r != NRegs; ++r) 227 new(Array + r) LiveIntervalUnion(r, allocator); 228 } 229 230 void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) { 231 NamedRegionTimer T("Initialize", TimerGroupName, TimePassesIsEnabled); 232 TRI = &vrm.getTargetRegInfo(); 233 MRI = &vrm.getRegInfo(); 234 VRM = &vrm; 235 LIS = &lis; 236 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 237 238 const unsigned NumRegs = TRI->getNumRegs(); 239 if (NumRegs != PhysReg2LiveUnion.numRegs()) { 240 PhysReg2LiveUnion.init(UnionAllocator, NumRegs); 241 // Cache an interferece query for each physical reg 242 Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); 243 } 244 } 245 246 void RegAllocBase::LiveUnionArray::clear() { 247 if (!Array) 248 return; 249 for (unsigned r = 0; r != NumRegs; ++r) 250 Array[r].~LiveIntervalUnion(); 251 free(Array); 252 NumRegs = 0; 253 Array = 0; 254 } 255 256 void RegAllocBase::releaseMemory() { 257 for (unsigned r = 0, e = PhysReg2LiveUnion.numRegs(); r != e; ++r) 258 PhysReg2LiveUnion[r].clear(); 259 } 260 261 // Visit all the live registers. If they are already assigned to a physical 262 // register, unify them with the corresponding LiveIntervalUnion, otherwise push 263 // them on the priority queue for later assignment. 264 void RegAllocBase::seedLiveRegs() { 265 NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 266 for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) { 267 unsigned RegNum = I->first; 268 LiveInterval &VirtReg = *I->second; 269 if (TargetRegisterInfo::isPhysicalRegister(RegNum)) 270 PhysReg2LiveUnion[RegNum].unify(VirtReg); 271 else 272 enqueue(&VirtReg); 273 } 274 } 275 276 void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) { 277 DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 278 << " to " << PrintReg(PhysReg, TRI) << '\n'); 279 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 280 VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 281 MRI->setPhysRegUsed(PhysReg); 282 PhysReg2LiveUnion[PhysReg].unify(VirtReg); 283 ++NumAssigned; 284 } 285 286 void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { 287 DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 288 << " from " << PrintReg(PhysReg, TRI) << '\n'); 289 assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign"); 290 PhysReg2LiveUnion[PhysReg].extract(VirtReg); 291 VRM->clearVirt(VirtReg.reg); 292 ++NumUnassigned; 293 } 294 295 // Top-level driver to manage the queue of unassigned VirtRegs and call the 296 // selectOrSplit implementation. 297 void RegAllocBase::allocatePhysRegs() { 298 seedLiveRegs(); 299 300 // Continue assigning vregs one at a time to available physical registers. 301 while (LiveInterval *VirtReg = dequeue()) { 302 assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 303 304 // Unused registers can appear when the spiller coalesces snippets. 305 if (MRI->reg_nodbg_empty(VirtReg->reg)) { 306 DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 307 LIS->removeInterval(VirtReg->reg); 308 continue; 309 } 310 311 // Invalidate all interference queries, live ranges could have changed. 312 invalidateVirtRegs(); 313 314 // selectOrSplit requests the allocator to return an available physical 315 // register if possible and populate a list of new live intervals that 316 // result from splitting. 317 DEBUG(dbgs() << "\nselectOrSplit " 318 << MRI->getRegClass(VirtReg->reg)->getName() 319 << ':' << *VirtReg << '\n'); 320 typedef SmallVector<LiveInterval*, 4> VirtRegVec; 321 VirtRegVec SplitVRegs; 322 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 323 324 if (AvailablePhysReg == ~0u) { 325 // selectOrSplit failed to find a register! 326 const char *Msg = "ran out of registers during register allocation"; 327 // Probably caused by an inline asm. 328 MachineInstr *MI; 329 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); 330 (MI = I.skipInstruction());) 331 if (MI->isInlineAsm()) 332 break; 333 if (MI) 334 MI->emitError(Msg); 335 else 336 report_fatal_error(Msg); 337 // Keep going after reporting the error. 338 VRM->assignVirt2Phys(VirtReg->reg, 339 RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 340 continue; 341 } 342 343 if (AvailablePhysReg) 344 assign(*VirtReg, AvailablePhysReg); 345 346 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 347 I != E; ++I) { 348 LiveInterval *SplitVirtReg = *I; 349 assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 350 if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 351 DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 352 LIS->removeInterval(SplitVirtReg->reg); 353 continue; 354 } 355 DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 356 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 357 "expect split value in virtual register"); 358 enqueue(SplitVirtReg); 359 ++NumNewQueued; 360 } 361 } 362 } 363 364 // Check if this live virtual register interferes with a physical register. If 365 // not, then check for interference on each register that aliases with the 366 // physical register. Return the interfering register. 367 unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, 368 unsigned PhysReg) { 369 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) 370 if (query(VirtReg, *AliasI).checkInterference()) 371 return *AliasI; 372 return 0; 373 } 374 375 // Helper for spillInteferences() that spills all interfering vregs currently 376 // assigned to this physical register. 377 void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, 378 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 379 LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg); 380 assert(Q.seenAllInterferences() && "need collectInterferences()"); 381 const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs(); 382 383 for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(), 384 E = PendingSpills.end(); I != E; ++I) { 385 LiveInterval &SpilledVReg = **I; 386 DEBUG(dbgs() << "extracting from " << 387 TRI->getName(PhysReg) << " " << SpilledVReg << '\n'); 388 389 // Deallocate the interfering vreg by removing it from the union. 390 // A LiveInterval instance may not be in a union during modification! 391 unassign(SpilledVReg, PhysReg); 392 393 // Spill the extracted interval. 394 LiveRangeEdit LRE(SpilledVReg, SplitVRegs, 0, &PendingSpills); 395 spiller().spill(LRE); 396 } 397 // After extracting segments, the query's results are invalid. But keep the 398 // contents valid until we're done accessing pendingSpills. 399 Q.clear(); 400 } 401 402 // Spill or split all live virtual registers currently unified under PhysReg 403 // that interfere with VirtReg. The newly spilled or split live intervals are 404 // returned by appending them to SplitVRegs. 405 bool 406 RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, 407 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 408 // Record each interference and determine if all are spillable before mutating 409 // either the union or live intervals. 410 unsigned NumInterferences = 0; 411 // Collect interferences assigned to any alias of the physical register. 412 for (const unsigned *asI = TRI->getOverlaps(PhysReg); *asI; ++asI) { 413 LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI); 414 NumInterferences += QAlias.collectInterferingVRegs(); 415 if (QAlias.seenUnspillableVReg()) { 416 return false; 417 } 418 } 419 DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) << 420 " interferences with " << VirtReg << "\n"); 421 assert(NumInterferences > 0 && "expect interference"); 422 423 // Spill each interfering vreg allocated to PhysReg or an alias. 424 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) 425 spillReg(VirtReg, *AliasI, SplitVRegs); 426 return true; 427 } 428 429 // Add newly allocated physical registers to the MBB live in sets. 430 void RegAllocBase::addMBBLiveIns(MachineFunction *MF) { 431 NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled); 432 SlotIndexes *Indexes = LIS->getSlotIndexes(); 433 if (MF->size() <= 1) 434 return; 435 436 LiveIntervalUnion::SegmentIter SI; 437 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 438 LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg]; 439 if (LiveUnion.empty()) 440 continue; 441 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " live-in:"); 442 MachineFunction::iterator MBB = llvm::next(MF->begin()); 443 MachineFunction::iterator MFE = MF->end(); 444 SlotIndex Start, Stop; 445 tie(Start, Stop) = Indexes->getMBBRange(MBB); 446 SI.setMap(LiveUnion.getMap()); 447 SI.find(Start); 448 while (SI.valid()) { 449 if (SI.start() <= Start) { 450 if (!MBB->isLiveIn(PhysReg)) 451 MBB->addLiveIn(PhysReg); 452 DEBUG(dbgs() << "\tBB#" << MBB->getNumber() << ':' 453 << PrintReg(SI.value()->reg, TRI)); 454 } else if (SI.start() > Stop) 455 MBB = Indexes->getMBBFromIndex(SI.start().getPrevIndex()); 456 if (++MBB == MFE) 457 break; 458 tie(Start, Stop) = Indexes->getMBBRange(MBB); 459 SI.advanceTo(Start); 460 } 461 DEBUG(dbgs() << '\n'); 462 } 463 } 464 465 466 //===----------------------------------------------------------------------===// 467 // RABasic Implementation 468 //===----------------------------------------------------------------------===// 469 470 // Driver for the register assignment and splitting heuristics. 471 // Manages iteration over the LiveIntervalUnions. 472 // 473 // This is a minimal implementation of register assignment and splitting that 474 // spills whenever we run out of registers. 475 // 476 // selectOrSplit can only be called once per live virtual register. We then do a 477 // single interference test for each register the correct class until we find an 478 // available register. So, the number of interference tests in the worst case is 479 // |vregs| * |machineregs|. And since the number of interference tests is 480 // minimal, there is no value in caching them outside the scope of 481 // selectOrSplit(). 482 unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, 483 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 484 // Populate a list of physical register spill candidates. 485 SmallVector<unsigned, 8> PhysRegSpillCands; 486 487 // Check for an available register in this class. 488 ArrayRef<unsigned> Order = 489 RegClassInfo.getOrder(MRI->getRegClass(VirtReg.reg)); 490 for (ArrayRef<unsigned>::iterator I = Order.begin(), E = Order.end(); I != E; 491 ++I) { 492 unsigned PhysReg = *I; 493 494 // Check interference and as a side effect, intialize queries for this 495 // VirtReg and its aliases. 496 unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg); 497 if (interfReg == 0) { 498 // Found an available register. 499 return PhysReg; 500 } 501 Queries[interfReg].collectInterferingVRegs(1); 502 LiveInterval *interferingVirtReg = 503 Queries[interfReg].interferingVRegs().front(); 504 505 // The current VirtReg must either be spillable, or one of its interferences 506 // must have less spill weight. 507 if (interferingVirtReg->weight < VirtReg.weight ) { 508 PhysRegSpillCands.push_back(PhysReg); 509 } 510 } 511 // Try to spill another interfering reg with less spill weight. 512 for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), 513 PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { 514 515 if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; 516 517 assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && 518 "Interference after spill."); 519 // Tell the caller to allocate to this newly freed physical register. 520 return *PhysRegI; 521 } 522 523 // No other spill candidates were found, so spill the current VirtReg. 524 DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); 525 if (!VirtReg.isSpillable()) 526 return ~0u; 527 LiveRangeEdit LRE(VirtReg, SplitVRegs); 528 spiller().spill(LRE); 529 530 // The live virtual register requesting allocation was spilled, so tell 531 // the caller not to allocate anything during this round. 532 return 0; 533 } 534 535 bool RABasic::runOnMachineFunction(MachineFunction &mf) { 536 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" 537 << "********** Function: " 538 << ((Value*)mf.getFunction())->getName() << '\n'); 539 540 MF = &mf; 541 DEBUG(RMF = &getAnalysis<RenderMachineFunction>()); 542 543 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 544 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 545 546 allocatePhysRegs(); 547 548 addMBBLiveIns(MF); 549 550 // Diagnostic output before rewriting 551 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); 552 553 // optional HTML output 554 DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM)); 555 556 // FIXME: Verification currently must run before VirtRegRewriter. We should 557 // make the rewriter a separate pass and override verifyAnalysis instead. When 558 // that happens, verification naturally falls under VerifyMachineCode. 559 #ifndef NDEBUG 560 if (VerifyEnabled) { 561 // Verify accuracy of LiveIntervals. The standard machine code verifier 562 // ensures that each LiveIntervals covers all uses of the virtual reg. 563 564 // FIXME: MachineVerifier is badly broken when using the standard 565 // spiller. Always use -spiller=inline with -verify-regalloc. Even with the 566 // inline spiller, some tests fail to verify because the coalescer does not 567 // always generate verifiable code. 568 MF->verify(this, "In RABasic::verify"); 569 570 // Verify that LiveIntervals are partitioned into unions and disjoint within 571 // the unions. 572 verify(); 573 } 574 #endif // !NDEBUG 575 576 // Run rewriter 577 VRM->rewrite(LIS->getSlotIndexes()); 578 579 // Write out new DBG_VALUE instructions. 580 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 581 582 // The pass output is in VirtRegMap. Release all the transient data. 583 releaseMemory(); 584 585 return true; 586 } 587 588 FunctionPass* llvm::createBasicRegisterAllocator() 589 { 590 return new RABasic(); 591 } 592