RegAllocGreedy.cpp revision 463a2977b1d9e6679f859db9f32e9e783b075c10
1//===-- RegAllocGreedy.cpp - greedy 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 RAGreedy function pass for register allocation in 11// optimized builds. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "AllocationOrder.h" 17#include "LiveIntervalUnion.h" 18#include "LiveRangeEdit.h" 19#include "RegAllocBase.h" 20#include "Spiller.h" 21#include "SpillPlacement.h" 22#include "SplitKit.h" 23#include "VirtRegMap.h" 24#include "VirtRegRewriter.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/EdgeBundles.h" 30#include "llvm/CodeGen/LiveIntervalAnalysis.h" 31#include "llvm/CodeGen/LiveStackAnalysis.h" 32#include "llvm/CodeGen/MachineDominators.h" 33#include "llvm/CodeGen/MachineFunctionPass.h" 34#include "llvm/CodeGen/MachineLoopInfo.h" 35#include "llvm/CodeGen/MachineLoopRanges.h" 36#include "llvm/CodeGen/MachineRegisterInfo.h" 37#include "llvm/CodeGen/Passes.h" 38#include "llvm/CodeGen/RegAllocRegistry.h" 39#include "llvm/CodeGen/RegisterCoalescer.h" 40#include "llvm/Target/TargetOptions.h" 41#include "llvm/Support/Debug.h" 42#include "llvm/Support/ErrorHandling.h" 43#include "llvm/Support/raw_ostream.h" 44#include "llvm/Support/Timer.h" 45 46using namespace llvm; 47 48static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 49 createGreedyRegisterAllocator); 50 51namespace { 52class RAGreedy : public MachineFunctionPass, public RegAllocBase { 53 // context 54 MachineFunction *MF; 55 BitVector ReservedRegs; 56 57 // analyses 58 SlotIndexes *Indexes; 59 LiveStacks *LS; 60 MachineDominatorTree *DomTree; 61 MachineLoopInfo *Loops; 62 MachineLoopRanges *LoopRanges; 63 EdgeBundles *Bundles; 64 SpillPlacement *SpillPlacer; 65 66 // state 67 std::auto_ptr<Spiller> SpillerInstance; 68 std::auto_ptr<SplitAnalysis> SA; 69 70 // splitting state. 71 72 /// All basic blocks where the current register is live. 73 SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints; 74 75 /// Additional information about basic blocks where the current variable is 76 /// live. Such a block will look like one of these templates: 77 /// 78 /// 1. | o---x | Internal to block. Variable is only live in this block. 79 /// 2. |---x | Live-in, kill. 80 /// 3. | o---| Def, live-out. 81 /// 4. |---x o---| Live-in, kill, def, live-out. 82 /// 5. |---o---o---| Live-through with uses or defs. 83 /// 6. |-----------| Live-through without uses. Transparent. 84 /// 85 struct BlockInfo { 86 MachineBasicBlock *MBB; 87 SlotIndex FirstUse; ///< First instr using current reg. 88 SlotIndex LastUse; ///< Last instr using current reg. 89 SlotIndex Kill; ///< Interval end point inside block. 90 SlotIndex Def; ///< Interval start point inside block. 91 bool Uses; ///< Current reg has uses or defs in block. 92 bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). 93 bool LiveIn; ///< Current reg is live in. 94 bool LiveOut; ///< Current reg is live out. 95 96 // Per-interference pattern scratch data. 97 bool OverlapEntry; ///< Interference overlaps entering interval. 98 bool OverlapExit; ///< Interference overlaps exiting interval. 99 }; 100 101 /// Basic blocks where var is live. This array is parallel to 102 /// SpillConstraints. 103 SmallVector<BlockInfo, 8> LiveBlocks; 104 105public: 106 RAGreedy(); 107 108 /// Return the pass name. 109 virtual const char* getPassName() const { 110 return "Greedy Register Allocator"; 111 } 112 113 /// RAGreedy analysis usage. 114 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 115 116 virtual void releaseMemory(); 117 118 virtual Spiller &spiller() { return *SpillerInstance; } 119 120 virtual float getPriority(LiveInterval *LI); 121 122 virtual unsigned selectOrSplit(LiveInterval&, 123 SmallVectorImpl<LiveInterval*>&); 124 125 /// Perform register allocation. 126 virtual bool runOnMachineFunction(MachineFunction &mf); 127 128 static char ID; 129 130private: 131 bool checkUncachedInterference(LiveInterval&, unsigned); 132 LiveInterval *getSingleInterference(LiveInterval&, unsigned); 133 bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg); 134 bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg); 135 float calcInterferenceWeight(LiveInterval&, unsigned); 136 void calcLiveBlockInfo(LiveInterval&); 137 float calcInterferenceInfo(LiveInterval&, unsigned); 138 float calcGlobalSplitCost(const BitVector&); 139 void splitAroundRegion(LiveInterval&, unsigned, const BitVector&, 140 SmallVectorImpl<LiveInterval*>&); 141 142 unsigned tryReassign(LiveInterval&, AllocationOrder&); 143 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 144 SmallVectorImpl<LiveInterval*>&); 145 unsigned trySplit(LiveInterval&, AllocationOrder&, 146 SmallVectorImpl<LiveInterval*>&); 147 unsigned trySpillInterferences(LiveInterval&, AllocationOrder&, 148 SmallVectorImpl<LiveInterval*>&); 149}; 150} // end anonymous namespace 151 152char RAGreedy::ID = 0; 153 154FunctionPass* llvm::createGreedyRegisterAllocator() { 155 return new RAGreedy(); 156} 157 158RAGreedy::RAGreedy(): MachineFunctionPass(ID) { 159 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 160 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 161 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 162 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 163 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 164 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 165 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 166 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 167 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 168 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 169 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 170 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 171 initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 172} 173 174void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 175 AU.setPreservesCFG(); 176 AU.addRequired<AliasAnalysis>(); 177 AU.addPreserved<AliasAnalysis>(); 178 AU.addRequired<LiveIntervals>(); 179 AU.addRequired<SlotIndexes>(); 180 AU.addPreserved<SlotIndexes>(); 181 if (StrongPHIElim) 182 AU.addRequiredID(StrongPHIEliminationID); 183 AU.addRequiredTransitive<RegisterCoalescer>(); 184 AU.addRequired<CalculateSpillWeights>(); 185 AU.addRequired<LiveStacks>(); 186 AU.addPreserved<LiveStacks>(); 187 AU.addRequired<MachineDominatorTree>(); 188 AU.addPreserved<MachineDominatorTree>(); 189 AU.addRequired<MachineLoopInfo>(); 190 AU.addPreserved<MachineLoopInfo>(); 191 AU.addRequired<MachineLoopRanges>(); 192 AU.addPreserved<MachineLoopRanges>(); 193 AU.addRequired<VirtRegMap>(); 194 AU.addPreserved<VirtRegMap>(); 195 AU.addRequired<EdgeBundles>(); 196 AU.addRequired<SpillPlacement>(); 197 MachineFunctionPass::getAnalysisUsage(AU); 198} 199 200void RAGreedy::releaseMemory() { 201 SpillerInstance.reset(0); 202 RegAllocBase::releaseMemory(); 203} 204 205float RAGreedy::getPriority(LiveInterval *LI) { 206 float Priority = LI->weight; 207 208 // Prioritize hinted registers so they are allocated first. 209 std::pair<unsigned, unsigned> Hint; 210 if (Hint.first || Hint.second) { 211 // The hint can be target specific, a virtual register, or a physreg. 212 Priority *= 2; 213 214 // Prefer physreg hints above anything else. 215 if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second)) 216 Priority *= 2; 217 } 218 return Priority; 219} 220 221 222//===----------------------------------------------------------------------===// 223// Register Reassignment 224//===----------------------------------------------------------------------===// 225 226// Check interference without using the cache. 227bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg, 228 unsigned PhysReg) { 229 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 230 LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]); 231 if (subQ.checkInterference()) 232 return true; 233 } 234 return false; 235} 236 237/// getSingleInterference - Return the single interfering virtual register 238/// assigned to PhysReg. Return 0 if more than one virtual register is 239/// interfering. 240LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg, 241 unsigned PhysReg) { 242 // Check physreg and aliases. 243 LiveInterval *Interference = 0; 244 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 245 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 246 if (Q.checkInterference()) { 247 if (Interference) 248 return 0; 249 Q.collectInterferingVRegs(1); 250 if (!Q.seenAllInterferences()) 251 return 0; 252 Interference = Q.interferingVRegs().front(); 253 } 254 } 255 return Interference; 256} 257 258// Attempt to reassign this virtual register to a different physical register. 259// 260// FIXME: we are not yet caching these "second-level" interferences discovered 261// in the sub-queries. These interferences can change with each call to 262// selectOrSplit. However, we could implement a "may-interfere" cache that 263// could be conservatively dirtied when we reassign or split. 264// 265// FIXME: This may result in a lot of alias queries. We could summarize alias 266// live intervals in their parent register's live union, but it's messy. 267bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg, 268 unsigned WantedPhysReg) { 269 assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) && 270 "Can only reassign virtual registers"); 271 assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) && 272 "inconsistent phys reg assigment"); 273 274 AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs); 275 while (unsigned PhysReg = Order.next()) { 276 // Don't reassign to a WantedPhysReg alias. 277 if (TRI->regsOverlap(PhysReg, WantedPhysReg)) 278 continue; 279 280 if (checkUncachedInterference(InterferingVReg, PhysReg)) 281 continue; 282 283 // Reassign the interfering virtual reg to this physical reg. 284 unsigned OldAssign = VRM->getPhys(InterferingVReg.reg); 285 DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " << 286 TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n'); 287 PhysReg2LiveUnion[OldAssign].extract(InterferingVReg); 288 VRM->clearVirt(InterferingVReg.reg); 289 VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg); 290 PhysReg2LiveUnion[PhysReg].unify(InterferingVReg); 291 292 return true; 293 } 294 return false; 295} 296 297/// reassignInterferences - Reassign all interferences to different physical 298/// registers such that Virtreg can be assigned to PhysReg. 299/// Currently this only works with a single interference. 300/// @param VirtReg Currently unassigned virtual register. 301/// @param PhysReg Physical register to be cleared. 302/// @return True on success, false if nothing was changed. 303bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) { 304 LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg); 305 if (!InterferingVReg) 306 return false; 307 if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg)) 308 return false; 309 return reassignVReg(*InterferingVReg, PhysReg); 310} 311 312/// tryReassign - Try to reassign interferences to different physregs. 313/// @param VirtReg Currently unassigned virtual register. 314/// @param Order Physregs to try. 315/// @return Physreg to assign VirtReg, or 0. 316unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) { 317 NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled); 318 Order.rewind(); 319 while (unsigned PhysReg = Order.next()) 320 if (reassignInterferences(VirtReg, PhysReg)) 321 return PhysReg; 322 return 0; 323} 324 325 326//===----------------------------------------------------------------------===// 327// Region Splitting 328//===----------------------------------------------------------------------===// 329 330/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks 331/// where VirtReg is live. 332/// The SpillConstraints array is minimally initialized with MBB->getNumber(). 333void RAGreedy::calcLiveBlockInfo(LiveInterval &VirtReg) { 334 LiveBlocks.clear(); 335 SpillConstraints.clear(); 336 337 assert(!VirtReg.empty() && "Cannot allocate an empty interval"); 338 LiveInterval::const_iterator LVI = VirtReg.begin(); 339 LiveInterval::const_iterator LVE = VirtReg.end(); 340 341 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; 342 UseI = SA->UseSlots.begin(); 343 UseE = SA->UseSlots.end(); 344 345 // Loop over basic blocks where VirtReg is live. 346 MachineFunction::iterator MFI = Indexes->getMBBFromIndex(LVI->start); 347 for (;;) { 348 // Block constraints depend on the interference pattern. 349 // Just allocate them here, don't compute anything. 350 SpillPlacement::BlockConstraint BC; 351 BC.Number = MFI->getNumber(); 352 SpillConstraints.push_back(BC); 353 354 BlockInfo BI; 355 BI.MBB = MFI; 356 SlotIndex Start, Stop; 357 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 358 359 // LVI is the first live segment overlapping MBB. 360 BI.LiveIn = LVI->start <= Start; 361 if (!BI.LiveIn) 362 BI.Def = LVI->start; 363 364 // Find the first and last uses in the block. 365 BI.Uses = SA->hasUses(MFI); 366 if (BI.Uses && UseI != UseE) { 367 BI.FirstUse = *UseI; 368 assert(BI.FirstUse >= Start); 369 do ++UseI; 370 while (UseI != UseE && *UseI < Stop); 371 BI.LastUse = UseI[-1]; 372 assert(BI.LastUse < Stop); 373 } 374 375 // Look for gaps in the live range. 376 bool hasGap = false; 377 BI.LiveOut = true; 378 while (LVI->end < Stop) { 379 SlotIndex LastStop = LVI->end; 380 if (++LVI == LVE || LVI->start >= Stop) { 381 BI.Kill = LastStop; 382 BI.LiveOut = false; 383 break; 384 } 385 if (LastStop < LVI->start) { 386 hasGap = true; 387 BI.Kill = LastStop; 388 BI.Def = LVI->start; 389 } 390 } 391 392 // Don't set LiveThrough when the block has a gap. 393 BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; 394 LiveBlocks.push_back(BI); 395 396 // LVI is now at LVE or LVI->end >= Stop. 397 if (LVI == LVE) 398 break; 399 400 // Live segment ends exactly at Stop. Move to the next segment. 401 if (LVI->end == Stop && ++LVI == LVE) 402 break; 403 404 // Pick the next basic block. 405 if (LVI->start < Stop) 406 ++MFI; 407 else 408 MFI = Indexes->getMBBFromIndex(LVI->start); 409 } 410} 411 412/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints 413/// when considering interference from PhysReg. Also compute an optimistic local 414/// cost of this interference pattern. 415/// 416/// The final cost of a split is the local cost + global cost of preferences 417/// broken by SpillPlacement. 418/// 419float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { 420 // Reset interference dependent info. 421 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 422 BlockInfo &BI = LiveBlocks[i]; 423 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 424 BC.Entry = (BI.Uses && BI.LiveIn) ? 425 SpillPlacement::PrefReg : SpillPlacement::DontCare; 426 BC.Exit = (BI.Uses && BI.LiveOut) ? 427 SpillPlacement::PrefReg : SpillPlacement::DontCare; 428 BI.OverlapEntry = BI.OverlapExit = false; 429 } 430 431 // Add interference info from each PhysReg alias. 432 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 433 if (!query(VirtReg, *AI).checkInterference()) 434 continue; 435 DEBUG(PhysReg2LiveUnion[*AI].print(dbgs(), TRI)); 436 LiveIntervalUnion::SegmentIter IntI = 437 PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 438 if (!IntI.valid()) 439 continue; 440 441 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 442 BlockInfo &BI = LiveBlocks[i]; 443 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 444 SlotIndex Start, Stop; 445 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 446 447 // Skip interference-free blocks. 448 if (IntI.start() >= Stop) 449 continue; 450 451 // Handle transparent blocks with interference separately. 452 // Transparent blocks never incur any fixed cost. 453 if (BI.LiveThrough && !BI.Uses) { 454 // Check if interference is live-in - force spill. 455 if (BC.Entry != SpillPlacement::MustSpill) { 456 BC.Entry = SpillPlacement::PrefSpill; 457 IntI.advanceTo(Start); 458 if (IntI.valid() && IntI.start() <= Start) 459 BC.Entry = SpillPlacement::MustSpill; 460 } 461 462 // Check if interference is live-out - force spill. 463 if (BC.Exit != SpillPlacement::MustSpill) { 464 BC.Exit = SpillPlacement::PrefSpill; 465 IntI.advanceTo(Stop); 466 if (IntI.valid() && IntI.start() < Stop) 467 BC.Exit = SpillPlacement::MustSpill; 468 } 469 470 // Nothing more to do for this transparent block. 471 if (!IntI.valid()) 472 break; 473 continue; 474 } 475 476 // Now we only have blocks with uses left. 477 // Check if the interference overlaps the uses. 478 assert(BI.Uses && "Non-transparent block without any uses"); 479 480 // Check interference on entry. 481 if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) { 482 IntI.advanceTo(Start); 483 if (!IntI.valid()) 484 break; 485 486 // Interference is live-in - force spill. 487 if (IntI.start() <= Start) 488 BC.Entry = SpillPlacement::MustSpill; 489 // Not live in, but before the first use. 490 else if (IntI.start() < BI.FirstUse) 491 BC.Entry = SpillPlacement::PrefSpill; 492 } 493 494 // Does interference overlap the uses in the entry segment 495 // [FirstUse;Kill)? 496 if (BI.LiveIn && !BI.OverlapEntry) { 497 IntI.advanceTo(BI.FirstUse); 498 if (!IntI.valid()) 499 break; 500 // A live-through interval has no kill. 501 // Check [FirstUse;LastUse) instead. 502 if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill)) 503 BI.OverlapEntry = true; 504 } 505 506 // Does interference overlap the uses in the exit segment [Def;LastUse)? 507 if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) { 508 IntI.advanceTo(BI.Def); 509 if (!IntI.valid()) 510 break; 511 if (IntI.start() < BI.LastUse) 512 BI.OverlapExit = true; 513 } 514 515 // Check interference on exit. 516 if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) { 517 // Check interference between LastUse and Stop. 518 if (BC.Exit != SpillPlacement::PrefSpill) { 519 IntI.advanceTo(BI.LastUse); 520 if (!IntI.valid()) 521 break; 522 if (IntI.start() < Stop) 523 BC.Exit = SpillPlacement::PrefSpill; 524 } 525 // Is the interference live-out? 526 IntI.advanceTo(Stop); 527 if (!IntI.valid()) 528 break; 529 if (IntI.start() < Stop) 530 BC.Exit = SpillPlacement::MustSpill; 531 } 532 } 533 } 534 535 // Accumulate a local cost of this interference pattern. 536 float LocalCost = 0; 537 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 538 BlockInfo &BI = LiveBlocks[i]; 539 if (!BI.Uses) 540 continue; 541 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 542 unsigned Inserts = 0; 543 544 // Do we need spill code for the entry segment? 545 if (BI.LiveIn) 546 Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg; 547 548 // For the exit segment? 549 if (BI.LiveOut) 550 Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg; 551 552 // The local cost of spill code in this block is the block frequency times 553 // the number of spill instructions inserted. 554 if (Inserts) 555 LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB); 556 } 557 DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = " 558 << LocalCost << '\n'); 559 return LocalCost; 560} 561 562/// calcGlobalSplitCost - Return the global split cost of following the split 563/// pattern in LiveBundles. This cost should be added to the local cost of the 564/// interference pattern in SpillConstraints. 565/// 566float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { 567 float GlobalCost = 0; 568 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 569 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 570 unsigned Inserts = 0; 571 // Broken entry preference? 572 Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] != 573 (BC.Entry == SpillPlacement::PrefReg); 574 // Broken exit preference? 575 Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] != 576 (BC.Exit == SpillPlacement::PrefReg); 577 if (Inserts) 578 GlobalCost += Inserts * SpillPlacer->getBlockFrequency(LiveBlocks[i].MBB); 579 } 580 DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n'); 581 return GlobalCost; 582} 583 584/// splitAroundRegion - Split VirtReg around the region determined by 585/// LiveBundles. Make an effort to avoid interference from PhysReg. 586/// 587/// The 'register' interval is going to contain as many uses as possible while 588/// avoiding interference. The 'stack' interval is the complement constructed by 589/// SplitEditor. It will contain the rest. 590/// 591void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, 592 const BitVector &LiveBundles, 593 SmallVectorImpl<LiveInterval*> &NewVRegs) { 594 DEBUG({ 595 dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI) 596 << " with bundles"; 597 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 598 dbgs() << " EB#" << i; 599 dbgs() << ".\n"; 600 }); 601 602 // First compute interference ranges in the live blocks. 603 typedef std::pair<SlotIndex, SlotIndex> IndexPair; 604 SmallVector<IndexPair, 8> InterferenceRanges; 605 InterferenceRanges.resize(LiveBlocks.size()); 606 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 607 if (!query(VirtReg, *AI).checkInterference()) 608 continue; 609 LiveIntervalUnion::SegmentIter IntI = 610 PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 611 if (!IntI.valid()) 612 continue; 613 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 614 BlockInfo &BI = LiveBlocks[i]; 615 if (!BI.Uses) 616 continue; 617 IndexPair &IP = InterferenceRanges[i]; 618 SlotIndex Start, Stop; 619 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 620 // Skip interference-free blocks. 621 if (IntI.start() >= Stop) 622 continue; 623 624 // First interference in block. 625 if (BI.LiveIn) { 626 IntI.advanceTo(Start); 627 if (!IntI.valid()) 628 break; 629 if (!IP.first.isValid() || IntI.start() < IP.first) 630 IP.first = IntI.start(); 631 } 632 633 // Last interference in block. 634 if (BI.LiveOut) { 635 IntI.advanceTo(Stop); 636 if (!IntI.valid() || IntI.start() >= Stop) 637 --IntI; 638 if (!IP.second.isValid() || IntI.stop() > IP.second) 639 IP.second = IntI.stop(); 640 } 641 } 642 } 643 644 SmallVector<LiveInterval*, 4> SpillRegs; 645 LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 646 SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit); 647 648 // Ranges to add to the register interval after all defs are in place. 649 SmallVector<IndexPair, 8> UseRanges; 650 651 // Create the main cross-block interval. 652 SE.openIntv(); 653 654 // First add all defs that are live out of a block. 655 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 656 BlockInfo &BI = LiveBlocks[i]; 657 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 658 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 659 660 // Should the register be live out? 661 if (!BI.LiveOut || !RegOut) 662 continue; 663 664 IndexPair &IP = InterferenceRanges[i]; 665 SlotIndex Start, Stop; 666 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 667 668 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 669 << Bundles->getBundle(BI.MBB->getNumber(), 1)); 670 671 // Check interference leaving the block. 672 if (!IP.second.isValid() || IP.second < Start) { 673 // Block is interference-free. 674 DEBUG(dbgs() << ", no interference"); 675 if (!BI.Uses) { 676 assert(BI.LiveThrough && "No uses, but not live through block?"); 677 // Block is live-through without interference. 678 DEBUG(dbgs() << ", no uses" 679 << (RegIn ? ", live-through.\n" : ", stack in.\n")); 680 if (!RegIn) 681 SE.enterIntvAtEnd(*BI.MBB); 682 continue; 683 } 684 if (!BI.LiveThrough) { 685 DEBUG(dbgs() << ", not live-through.\n"); 686 SE.enterIntvBefore(BI.Def); 687 UseRanges.push_back(IndexPair(BI.Def, Stop)); 688 continue; 689 } 690 if (!RegIn) { 691 // Block is live-through, but entry bundle is on the stack. 692 // Reload just before the first use. 693 DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 694 SE.enterIntvBefore(BI.FirstUse); 695 UseRanges.push_back(IndexPair(BI.FirstUse, Stop)); 696 continue; 697 } 698 DEBUG(dbgs() << ", live-through.\n"); 699 continue; 700 } 701 702 // Block has interference. 703 DEBUG(dbgs() << ", interference to " << IP.second); 704 if (!BI.Uses) { 705 // No uses in block, avoid interference by reloading as late as possible. 706 DEBUG(dbgs() << ", no uses.\n"); 707 SE.enterIntvAtEnd(*BI.MBB); 708 continue; 709 } 710 if (IP.second < BI.LastUse) { 711 // There are interference-free uses at the end of the block. 712 // Find the first use that can get the live-out register. 713 SmallVectorImpl<SlotIndex>::const_iterator UI = 714 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.second); 715 assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 716 SlotIndex Use = *UI; 717 DEBUG(dbgs() << ", free use at " << Use << ".\n"); 718 assert(Use <= BI.LastUse && "Couldn't find last use"); 719 SE.enterIntvBefore(Use); 720 UseRanges.push_back(IndexPair(Use, Stop)); 721 continue; 722 } 723 724 // Interference is after the last use. 725 DEBUG(dbgs() << " after last use.\n"); 726 SE.enterIntvAtEnd(*BI.MBB); 727 } 728 729 // Add the live-out ranges following the defs. 730 // We must wait until all defs have been inserted, otherwise SplitKit gets 731 // confused about the value mapping. 732 for (unsigned i = 0, e = UseRanges.size(); i != e; ++i) 733 SE.useIntv(UseRanges[i].first, UseRanges[i].second); 734 735 // Now all defs leading to live bundles are handled, do everything else. 736 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { 737 BlockInfo &BI = LiveBlocks[i]; 738 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 739 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 740 741 // Is the register live-in? 742 if (!BI.LiveIn || !RegIn) 743 continue; 744 745 // We have an incoming register. Check for interference. 746 IndexPair &IP = InterferenceRanges[i]; 747 SlotIndex Start, Stop; 748 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 749 750 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 751 << " -> BB#" << BI.MBB->getNumber()); 752 753 // Check interference entering the block. 754 if (!IP.first.isValid() || IP.first > Stop) { 755 // Block is interference-free. 756 DEBUG(dbgs() << ", no interference"); 757 if (!BI.Uses) { 758 assert(BI.LiveThrough && "No uses, but not live through block?"); 759 // Block is live-through without interference. 760 if (RegOut) { 761 DEBUG(dbgs() << ", no uses, live-through.\n"); 762 SE.useIntv(Start, Stop); 763 } else { 764 DEBUG(dbgs() << ", no uses, stack-out.\n"); 765 SE.leaveIntvAtTop(*BI.MBB); 766 } 767 continue; 768 } 769 if (!BI.LiveThrough) { 770 DEBUG(dbgs() << ", killed in block.\n"); 771 SE.useIntv(Start, BI.Kill.getBoundaryIndex()); 772 SE.leaveIntvAfter(BI.Kill); 773 continue; 774 } 775 if (!RegOut) { 776 // Block is live-through, but exit bundle is on the stack. 777 // Spill immediately after the last use. 778 DEBUG(dbgs() << ", uses, stack-out.\n"); 779 SE.useIntv(Start, BI.LastUse.getBoundaryIndex()); 780 SE.leaveIntvAfter(BI.LastUse); 781 continue; 782 } 783 // Register is live-through. 784 DEBUG(dbgs() << ", uses, live-through.\n"); 785 SE.useIntv(Start, Stop); 786 continue; 787 } 788 789 // Block has interference. 790 DEBUG(dbgs() << ", interference from " << IP.first); 791 if (!BI.Uses) { 792 // No uses in block, avoid interference by spilling as soon as possible. 793 DEBUG(dbgs() << ", no uses.\n"); 794 SE.leaveIntvAtTop(*BI.MBB); 795 continue; 796 } 797 if (IP.first > BI.FirstUse) { 798 // There are interference-free uses at the beginning of the block. 799 // Find the last use that can get the register. 800 SmallVectorImpl<SlotIndex>::const_iterator UI = 801 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.first); 802 assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 803 SlotIndex Use = (--UI)->getBoundaryIndex(); 804 DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 805 assert(Use >= BI.FirstUse && Use < IP.first); 806 SE.useIntv(Start, Use); 807 SE.leaveIntvAfter(Use); 808 continue; 809 } 810 811 // Interference is before the first use. 812 DEBUG(dbgs() << " before first use.\n"); 813 SE.leaveIntvAtTop(*BI.MBB); 814 } 815 816 SE.closeIntv(); 817 818 // FIXME: Should we be more aggressive about splitting the stack region into 819 // per-block segments? The current approach allows the stack region to 820 // separate into connected components. Some components may be allocatable. 821 SE.finish(); 822 823 if (VerifyEnabled) 824 MF->verify(this, "After splitting live range around region"); 825} 826 827unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 828 SmallVectorImpl<LiveInterval*> &NewVRegs) { 829 calcLiveBlockInfo(VirtReg); 830 BitVector LiveBundles, BestBundles; 831 float BestCost = 0; 832 unsigned BestReg = 0; 833 Order.rewind(); 834 while (unsigned PhysReg = Order.next()) { 835 float Cost = calcInterferenceInfo(VirtReg, PhysReg); 836 if (BestReg && Cost >= BestCost) 837 continue; 838 839 SpillPlacer->placeSpills(SpillConstraints, LiveBundles); 840 // No live bundles, defer to splitSingleBlocks(). 841 if (!LiveBundles.any()) 842 continue; 843 844 Cost += calcGlobalSplitCost(LiveBundles); 845 if (!BestReg || Cost < BestCost) { 846 BestReg = PhysReg; 847 BestCost = Cost; 848 BestBundles.swap(LiveBundles); 849 } 850 } 851 852 if (!BestReg) 853 return 0; 854 855 splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); 856 return 0; 857} 858 859 860//===----------------------------------------------------------------------===// 861// Live Range Splitting 862//===----------------------------------------------------------------------===// 863 864/// trySplit - Try to split VirtReg or one of its interferences, making it 865/// assignable. 866/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 867unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 868 SmallVectorImpl<LiveInterval*>&NewVRegs) { 869 NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled); 870 SA->analyze(&VirtReg); 871 872 // Don't attempt splitting on local intervals for now. TBD. 873 if (LIS->intervalIsInOneMBB(VirtReg)) 874 return 0; 875 876 // First try to split around a region spanning multiple blocks. 877 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 878 if (PhysReg || !NewVRegs.empty()) 879 return PhysReg; 880 881 // Then isolate blocks with multiple uses. 882 SplitAnalysis::BlockPtrSet Blocks; 883 if (SA->getMultiUseBlocks(Blocks)) { 884 SmallVector<LiveInterval*, 4> SpillRegs; 885 LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 886 SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks); 887 } 888 889 // Don't assign any physregs. 890 return 0; 891} 892 893 894//===----------------------------------------------------------------------===// 895// Spilling 896//===----------------------------------------------------------------------===// 897 898/// calcInterferenceWeight - Calculate the combined spill weight of 899/// interferences when assigning VirtReg to PhysReg. 900float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){ 901 float Sum = 0; 902 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 903 LiveIntervalUnion::Query &Q = query(VirtReg, *AI); 904 Q.collectInterferingVRegs(); 905 if (Q.seenUnspillableVReg()) 906 return HUGE_VALF; 907 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) 908 Sum += Q.interferingVRegs()[i]->weight; 909 } 910 return Sum; 911} 912 913/// trySpillInterferences - Try to spill interfering registers instead of the 914/// current one. Only do it if the accumulated spill weight is smaller than the 915/// current spill weight. 916unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg, 917 AllocationOrder &Order, 918 SmallVectorImpl<LiveInterval*> &NewVRegs) { 919 NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled); 920 unsigned BestPhys = 0; 921 float BestWeight = 0; 922 923 Order.rewind(); 924 while (unsigned PhysReg = Order.next()) { 925 float Weight = calcInterferenceWeight(VirtReg, PhysReg); 926 if (Weight == HUGE_VALF || Weight >= VirtReg.weight) 927 continue; 928 if (!BestPhys || Weight < BestWeight) 929 BestPhys = PhysReg, BestWeight = Weight; 930 } 931 932 // No candidates found. 933 if (!BestPhys) 934 return 0; 935 936 // Collect all interfering registers. 937 SmallVector<LiveInterval*, 8> Spills; 938 for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) { 939 LiveIntervalUnion::Query &Q = query(VirtReg, *AI); 940 Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end()); 941 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 942 LiveInterval *VReg = Q.interferingVRegs()[i]; 943 PhysReg2LiveUnion[*AI].extract(*VReg); 944 VRM->clearVirt(VReg->reg); 945 } 946 } 947 948 // Spill them all. 949 DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight " 950 << BestWeight << '\n'); 951 for (unsigned i = 0, e = Spills.size(); i != e; ++i) 952 spiller().spill(Spills[i], NewVRegs, Spills); 953 return BestPhys; 954} 955 956 957//===----------------------------------------------------------------------===// 958// Main Entry Point 959//===----------------------------------------------------------------------===// 960 961unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 962 SmallVectorImpl<LiveInterval*> &NewVRegs) { 963 // First try assigning a free register. 964 AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 965 while (unsigned PhysReg = Order.next()) { 966 if (!checkPhysRegInterference(VirtReg, PhysReg)) 967 return PhysReg; 968 } 969 970 // Try to reassign interferences. 971 if (unsigned PhysReg = tryReassign(VirtReg, Order)) 972 return PhysReg; 973 974 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 975 976 // Try splitting VirtReg or interferences. 977 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 978 if (PhysReg || !NewVRegs.empty()) 979 return PhysReg; 980 981 // Try to spill another interfering reg with less spill weight. 982 PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs); 983 if (PhysReg) 984 return PhysReg; 985 986 // Finally spill VirtReg itself. 987 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 988 SmallVector<LiveInterval*, 1> pendingSpills; 989 spiller().spill(&VirtReg, NewVRegs, pendingSpills); 990 991 // The live virtual register requesting allocation was spilled, so tell 992 // the caller not to allocate anything during this round. 993 return 0; 994} 995 996bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 997 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 998 << "********** Function: " 999 << ((Value*)mf.getFunction())->getName() << '\n'); 1000 1001 MF = &mf; 1002 if (VerifyEnabled) 1003 MF->verify(this, "Before greedy register allocator"); 1004 1005 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1006 Indexes = &getAnalysis<SlotIndexes>(); 1007 DomTree = &getAnalysis<MachineDominatorTree>(); 1008 ReservedRegs = TRI->getReservedRegs(*MF); 1009 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1010 Loops = &getAnalysis<MachineLoopInfo>(); 1011 LoopRanges = &getAnalysis<MachineLoopRanges>(); 1012 Bundles = &getAnalysis<EdgeBundles>(); 1013 SpillPlacer = &getAnalysis<SpillPlacement>(); 1014 1015 SA.reset(new SplitAnalysis(*MF, *LIS, *Loops)); 1016 1017 allocatePhysRegs(); 1018 addMBBLiveIns(MF); 1019 1020 // Run rewriter 1021 { 1022 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1023 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 1024 rewriter->runOnMachineFunction(*MF, *VRM, LIS); 1025 } 1026 1027 // The pass output is in VirtRegMap. Release all the transient data. 1028 releaseMemory(); 1029 1030 return true; 1031} 1032