RegAllocBasic.cpp revision 38f6bd0fc8095ef79a89b3db15ff6dc734ac90e7
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 "llvm/ADT/OwningPtr.h" 22#include "llvm/ADT/Statistic.h" 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/Function.h" 25#include "llvm/PassAnalysisSupport.h" 26#include "llvm/CodeGen/CalcSpillWeights.h" 27#include "llvm/CodeGen/LiveIntervalAnalysis.h" 28#include "llvm/CodeGen/LiveStackAnalysis.h" 29#include "llvm/CodeGen/MachineFunctionPass.h" 30#include "llvm/CodeGen/MachineInstr.h" 31#include "llvm/CodeGen/MachineLoopInfo.h" 32#include "llvm/CodeGen/MachineRegisterInfo.h" 33#include "llvm/CodeGen/Passes.h" 34#include "llvm/CodeGen/RegAllocRegistry.h" 35#include "llvm/CodeGen/RegisterCoalescer.h" 36#include "llvm/Target/TargetMachine.h" 37#include "llvm/Target/TargetOptions.h" 38#include "llvm/Target/TargetRegisterInfo.h" 39#ifndef NDEBUG 40#include "llvm/ADT/SparseBitVector.h" 41#endif 42#include "llvm/Support/Debug.h" 43#include "llvm/Support/ErrorHandling.h" 44#include "llvm/Support/raw_ostream.h" 45#include "llvm/Support/Timer.h" 46 47#include <cstdlib> 48#include <queue> 49 50using namespace llvm; 51 52STATISTIC(NumAssigned , "Number of registers assigned"); 53STATISTIC(NumUnassigned , "Number of registers unassigned"); 54STATISTIC(NumNewQueued , "Number of new live ranges queued"); 55 56static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", 57 createBasicRegisterAllocator); 58 59// Temporary verification option until we can put verification inside 60// MachineVerifier. 61static cl::opt<bool, true> 62VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 63 cl::desc("Verify during register allocation")); 64 65const char *RegAllocBase::TimerGroupName = "Register Allocation"; 66bool RegAllocBase::VerifyEnabled = false; 67 68namespace { 69 struct CompSpillWeight { 70 bool operator()(LiveInterval *A, LiveInterval *B) const { 71 return A->weight < B->weight; 72 } 73 }; 74} 75 76namespace { 77/// RABasic provides a minimal implementation of the basic register allocation 78/// algorithm. It prioritizes live virtual registers by spill weight and spills 79/// whenever a register is unavailable. This is not practical in production but 80/// provides a useful baseline both for measuring other allocators and comparing 81/// the speed of the basic algorithm against other styles of allocators. 82class RABasic : public MachineFunctionPass, public RegAllocBase 83{ 84 // context 85 MachineFunction *MF; 86 BitVector ReservedRegs; 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; 96public: 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 134char RABasic::ID = 0; 135 136} // end anonymous namespace 137 138RABasic::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()); 149} 150 151void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { 152 AU.setPreservesCFG(); 153 AU.addRequired<AliasAnalysis>(); 154 AU.addPreserved<AliasAnalysis>(); 155 AU.addRequired<LiveIntervals>(); 156 AU.addPreserved<SlotIndexes>(); 157 if (StrongPHIElim) 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); 171} 172 173void RABasic::releaseMemory() { 174 SpillerInstance.reset(0); 175 RegAllocBase::releaseMemory(); 176} 177 178#ifndef NDEBUG 179// Verify each LiveIntervalUnion. 180void RegAllocBase::verify() { 181 LiveVirtRegBitSet VisitedVRegs; 182 OwningArrayPtr<LiveVirtRegBitSet> 183 unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]); 184 185 // Verify disjoint unions. 186 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 187 DEBUG(PhysReg2LiveUnion[PhysReg].print(dbgs(), TRI)); 188 LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg]; 189 PhysReg2LiveUnion[PhysReg].verify(VRegs); 190 // Union + intersection test could be done efficiently in one pass, but 191 // don't add a method to SparseBitVector unless we really need it. 192 assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions"); 193 VisitedVRegs |= VRegs; 194 } 195 196 // Verify vreg coverage. 197 for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end(); 198 liItr != liEnd; ++liItr) { 199 unsigned reg = liItr->first; 200 if (TargetRegisterInfo::isPhysicalRegister(reg)) continue; 201 if (!VRM->hasPhys(reg)) continue; // spilled? 202 unsigned PhysReg = VRM->getPhys(reg); 203 if (!unionVRegs[PhysReg].test(reg)) { 204 dbgs() << "LiveVirtReg " << reg << " not in union " << 205 TRI->getName(PhysReg) << "\n"; 206 llvm_unreachable("unallocated live vreg"); 207 } 208 } 209 // FIXME: I'm not sure how to verify spilled intervals. 210} 211#endif //!NDEBUG 212 213//===----------------------------------------------------------------------===// 214// RegAllocBase Implementation 215//===----------------------------------------------------------------------===// 216 217// Instantiate a LiveIntervalUnion for each physical register. 218void RegAllocBase::LiveUnionArray::init(LiveIntervalUnion::Allocator &allocator, 219 unsigned NRegs) { 220 NumRegs = NRegs; 221 Array = 222 static_cast<LiveIntervalUnion*>(malloc(sizeof(LiveIntervalUnion)*NRegs)); 223 for (unsigned r = 0; r != NRegs; ++r) 224 new(Array + r) LiveIntervalUnion(r, allocator); 225} 226 227void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) { 228 NamedRegionTimer T("Initialize", TimerGroupName, TimePassesIsEnabled); 229 TRI = &vrm.getTargetRegInfo(); 230 MRI = &vrm.getRegInfo(); 231 VRM = &vrm; 232 LIS = &lis; 233 PhysReg2LiveUnion.init(UnionAllocator, TRI->getNumRegs()); 234 // Cache an interferece query for each physical reg 235 Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]); 236} 237 238void RegAllocBase::LiveUnionArray::clear() { 239 if (!Array) 240 return; 241 for (unsigned r = 0; r != NumRegs; ++r) 242 Array[r].~LiveIntervalUnion(); 243 free(Array); 244 NumRegs = 0; 245 Array = 0; 246} 247 248void RegAllocBase::releaseMemory() { 249 PhysReg2LiveUnion.clear(); 250} 251 252// Visit all the live registers. If they are already assigned to a physical 253// register, unify them with the corresponding LiveIntervalUnion, otherwise push 254// them on the priority queue for later assignment. 255void RegAllocBase::seedLiveRegs() { 256 for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) { 257 unsigned RegNum = I->first; 258 LiveInterval &VirtReg = *I->second; 259 if (TargetRegisterInfo::isPhysicalRegister(RegNum)) 260 PhysReg2LiveUnion[RegNum].unify(VirtReg); 261 else 262 enqueue(&VirtReg); 263 } 264} 265 266void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) { 267 DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 268 << " to " << PrintReg(PhysReg, TRI) << '\n'); 269 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 270 VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 271 PhysReg2LiveUnion[PhysReg].unify(VirtReg); 272 ++NumAssigned; 273} 274 275void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { 276 DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 277 << " from " << PrintReg(PhysReg, TRI) << '\n'); 278 assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign"); 279 PhysReg2LiveUnion[PhysReg].extract(VirtReg); 280 VRM->clearVirt(VirtReg.reg); 281 ++NumUnassigned; 282} 283 284// Top-level driver to manage the queue of unassigned VirtRegs and call the 285// selectOrSplit implementation. 286void RegAllocBase::allocatePhysRegs() { 287 seedLiveRegs(); 288 289 // Continue assigning vregs one at a time to available physical registers. 290 while (LiveInterval *VirtReg = dequeue()) { 291 // selectOrSplit requests the allocator to return an available physical 292 // register if possible and populate a list of new live intervals that 293 // result from splitting. 294 DEBUG(dbgs() << "\nselectOrSplit " 295 << MRI->getRegClass(VirtReg->reg)->getName() 296 << ':' << *VirtReg << '\n'); 297 typedef SmallVector<LiveInterval*, 4> VirtRegVec; 298 VirtRegVec SplitVRegs; 299 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 300 301 if (AvailablePhysReg) 302 assign(*VirtReg, AvailablePhysReg); 303 304 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 305 I != E; ++I) { 306 LiveInterval *SplitVirtReg = *I; 307 if (SplitVirtReg->empty()) continue; 308 DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 309 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 310 "expect split value in virtual register"); 311 enqueue(SplitVirtReg); 312 ++NumNewQueued; 313 } 314 } 315} 316 317// Check if this live virtual register interferes with a physical register. If 318// not, then check for interference on each register that aliases with the 319// physical register. Return the interfering register. 320unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, 321 unsigned PhysReg) { 322 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) 323 if (query(VirtReg, *AliasI).checkInterference()) 324 return *AliasI; 325 return 0; 326} 327 328// Helper for spillInteferences() that spills all interfering vregs currently 329// assigned to this physical register. 330void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, 331 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 332 LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg); 333 assert(Q.seenAllInterferences() && "need collectInterferences()"); 334 const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs(); 335 336 for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(), 337 E = PendingSpills.end(); I != E; ++I) { 338 LiveInterval &SpilledVReg = **I; 339 DEBUG(dbgs() << "extracting from " << 340 TRI->getName(PhysReg) << " " << SpilledVReg << '\n'); 341 342 // Deallocate the interfering vreg by removing it from the union. 343 // A LiveInterval instance may not be in a union during modification! 344 unassign(SpilledVReg, PhysReg); 345 346 // Spill the extracted interval. 347 spiller().spill(&SpilledVReg, SplitVRegs, &PendingSpills); 348 } 349 // After extracting segments, the query's results are invalid. But keep the 350 // contents valid until we're done accessing pendingSpills. 351 Q.clear(); 352} 353 354// Spill or split all live virtual registers currently unified under PhysReg 355// that interfere with VirtReg. The newly spilled or split live intervals are 356// returned by appending them to SplitVRegs. 357bool 358RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, 359 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 360 // Record each interference and determine if all are spillable before mutating 361 // either the union or live intervals. 362 unsigned NumInterferences = 0; 363 // Collect interferences assigned to any alias of the physical register. 364 for (const unsigned *asI = TRI->getOverlaps(PhysReg); *asI; ++asI) { 365 LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI); 366 NumInterferences += QAlias.collectInterferingVRegs(); 367 if (QAlias.seenUnspillableVReg()) { 368 return false; 369 } 370 } 371 DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) << 372 " interferences with " << VirtReg << "\n"); 373 assert(NumInterferences > 0 && "expect interference"); 374 375 // Spill each interfering vreg allocated to PhysReg or an alias. 376 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) 377 spillReg(VirtReg, *AliasI, SplitVRegs); 378 return true; 379} 380 381// Add newly allocated physical registers to the MBB live in sets. 382void RegAllocBase::addMBBLiveIns(MachineFunction *MF) { 383 NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled); 384 typedef SmallVector<MachineBasicBlock*, 8> MBBVec; 385 MBBVec liveInMBBs; 386 MachineBasicBlock &entryMBB = *MF->begin(); 387 388 for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) { 389 LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg]; 390 if (LiveUnion.empty()) 391 continue; 392 for (LiveIntervalUnion::SegmentIter SI = LiveUnion.begin(); SI.valid(); 393 ++SI) { 394 395 // Find the set of basic blocks which this range is live into... 396 liveInMBBs.clear(); 397 if (!LIS->findLiveInMBBs(SI.start(), SI.stop(), liveInMBBs)) continue; 398 399 // And add the physreg for this interval to their live-in sets. 400 for (MBBVec::iterator I = liveInMBBs.begin(), E = liveInMBBs.end(); 401 I != E; ++I) { 402 MachineBasicBlock *MBB = *I; 403 if (MBB == &entryMBB) continue; 404 if (MBB->isLiveIn(PhysReg)) continue; 405 MBB->addLiveIn(PhysReg); 406 } 407 } 408 } 409} 410 411 412//===----------------------------------------------------------------------===// 413// RABasic Implementation 414//===----------------------------------------------------------------------===// 415 416// Driver for the register assignment and splitting heuristics. 417// Manages iteration over the LiveIntervalUnions. 418// 419// This is a minimal implementation of register assignment and splitting that 420// spills whenever we run out of registers. 421// 422// selectOrSplit can only be called once per live virtual register. We then do a 423// single interference test for each register the correct class until we find an 424// available register. So, the number of interference tests in the worst case is 425// |vregs| * |machineregs|. And since the number of interference tests is 426// minimal, there is no value in caching them outside the scope of 427// selectOrSplit(). 428unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, 429 SmallVectorImpl<LiveInterval*> &SplitVRegs) { 430 // Populate a list of physical register spill candidates. 431 SmallVector<unsigned, 8> PhysRegSpillCands; 432 433 // Check for an available register in this class. 434 const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg); 435 436 for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF), 437 E = TRC->allocation_order_end(*MF); 438 I != E; ++I) { 439 440 unsigned PhysReg = *I; 441 if (ReservedRegs.test(PhysReg)) continue; 442 443 // Check interference and as a side effect, intialize queries for this 444 // VirtReg and its aliases. 445 unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg); 446 if (interfReg == 0) { 447 // Found an available register. 448 return PhysReg; 449 } 450 LiveInterval *interferingVirtReg = 451 Queries[interfReg].firstInterference().liveUnionPos().value(); 452 453 // The current VirtReg must either be spillable, or one of its interferences 454 // must have less spill weight. 455 if (interferingVirtReg->weight < VirtReg.weight ) { 456 PhysRegSpillCands.push_back(PhysReg); 457 } 458 } 459 // Try to spill another interfering reg with less spill weight. 460 for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), 461 PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { 462 463 if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue; 464 465 assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 && 466 "Interference after spill."); 467 // Tell the caller to allocate to this newly freed physical register. 468 return *PhysRegI; 469 } 470 // No other spill candidates were found, so spill the current VirtReg. 471 DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); 472 spiller().spill(&VirtReg, SplitVRegs, 0); 473 474 // The live virtual register requesting allocation was spilled, so tell 475 // the caller not to allocate anything during this round. 476 return 0; 477} 478 479bool RABasic::runOnMachineFunction(MachineFunction &mf) { 480 DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" 481 << "********** Function: " 482 << ((Value*)mf.getFunction())->getName() << '\n'); 483 484 MF = &mf; 485 DEBUG(RMF = &getAnalysis<RenderMachineFunction>()); 486 487 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 488 489 ReservedRegs = TRI->getReservedRegs(*MF); 490 491 SpillerInstance.reset(createSpiller(*this, *MF, *VRM)); 492 493 allocatePhysRegs(); 494 495 addMBBLiveIns(MF); 496 497 // Diagnostic output before rewriting 498 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); 499 500 // optional HTML output 501 DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM)); 502 503 // FIXME: Verification currently must run before VirtRegRewriter. We should 504 // make the rewriter a separate pass and override verifyAnalysis instead. When 505 // that happens, verification naturally falls under VerifyMachineCode. 506#ifndef NDEBUG 507 if (VerifyEnabled) { 508 // Verify accuracy of LiveIntervals. The standard machine code verifier 509 // ensures that each LiveIntervals covers all uses of the virtual reg. 510 511 // FIXME: MachineVerifier is badly broken when using the standard 512 // spiller. Always use -spiller=inline with -verify-regalloc. Even with the 513 // inline spiller, some tests fail to verify because the coalescer does not 514 // always generate verifiable code. 515 MF->verify(this, "In RABasic::verify"); 516 517 // Verify that LiveIntervals are partitioned into unions and disjoint within 518 // the unions. 519 verify(); 520 } 521#endif // !NDEBUG 522 523 // Run rewriter 524 VRM->rewrite(LIS->getSlotIndexes()); 525 526 // The pass output is in VirtRegMap. Release all the transient data. 527 releaseMemory(); 528 529 return true; 530} 531 532FunctionPass* llvm::createBasicRegisterAllocator() 533{ 534 return new RABasic(); 535} 536