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