RegAllocGreedy.cpp revision cfafc54040cc9722995558124f253d05a038176b
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 "InterferenceCache.h" 18#include "LiveDebugVariables.h" 19#include "LiveRangeEdit.h" 20#include "RegAllocBase.h" 21#include "Spiller.h" 22#include "SpillPlacement.h" 23#include "SplitKit.h" 24#include "VirtRegMap.h" 25#include "llvm/ADT/Statistic.h" 26#include "llvm/Analysis/AliasAnalysis.h" 27#include "llvm/Function.h" 28#include "llvm/PassAnalysisSupport.h" 29#include "llvm/CodeGen/CalcSpillWeights.h" 30#include "llvm/CodeGen/EdgeBundles.h" 31#include "llvm/CodeGen/LiveIntervalAnalysis.h" 32#include "llvm/CodeGen/LiveStackAnalysis.h" 33#include "llvm/CodeGen/MachineDominators.h" 34#include "llvm/CodeGen/MachineFunctionPass.h" 35#include "llvm/CodeGen/MachineLoopInfo.h" 36#include "llvm/CodeGen/MachineLoopRanges.h" 37#include "llvm/CodeGen/MachineRegisterInfo.h" 38#include "llvm/CodeGen/Passes.h" 39#include "llvm/CodeGen/RegAllocRegistry.h" 40#include "llvm/CodeGen/RegisterCoalescer.h" 41#include "llvm/Target/TargetOptions.h" 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 <queue> 48 49using namespace llvm; 50 51STATISTIC(NumGlobalSplits, "Number of split global live ranges"); 52STATISTIC(NumLocalSplits, "Number of split local live ranges"); 53STATISTIC(NumEvicted, "Number of interferences evicted"); 54 55static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 56 createGreedyRegisterAllocator); 57 58namespace { 59class RAGreedy : public MachineFunctionPass, 60 public RegAllocBase, 61 private LiveRangeEdit::Delegate { 62 63 // context 64 MachineFunction *MF; 65 BitVector ReservedRegs; 66 67 // analyses 68 SlotIndexes *Indexes; 69 LiveStacks *LS; 70 MachineDominatorTree *DomTree; 71 MachineLoopInfo *Loops; 72 MachineLoopRanges *LoopRanges; 73 EdgeBundles *Bundles; 74 SpillPlacement *SpillPlacer; 75 76 // state 77 std::auto_ptr<Spiller> SpillerInstance; 78 std::priority_queue<std::pair<unsigned, unsigned> > Queue; 79 80 // Live ranges pass through a number of stages as we try to allocate them. 81 // Some of the stages may also create new live ranges: 82 // 83 // - Region splitting. 84 // - Per-block splitting. 85 // - Local splitting. 86 // - Spilling. 87 // 88 // Ranges produced by one of the stages skip the previous stages when they are 89 // dequeued. This improves performance because we can skip interference checks 90 // that are unlikely to give any results. It also guarantees that the live 91 // range splitting algorithm terminates, something that is otherwise hard to 92 // ensure. 93 enum LiveRangeStage { 94 RS_New, ///< Never seen before. 95 RS_First, ///< First time in the queue. 96 RS_Second, ///< Second time in the queue. 97 RS_Region, ///< Produced by region splitting. 98 RS_Block, ///< Produced by per-block splitting. 99 RS_Local, ///< Produced by local splitting. 100 RS_Spill ///< Produced by spilling. 101 }; 102 103 IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage; 104 105 LiveRangeStage getStage(const LiveInterval &VirtReg) const { 106 return LiveRangeStage(LRStage[VirtReg.reg]); 107 } 108 109 template<typename Iterator> 110 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 111 LRStage.resize(MRI->getNumVirtRegs()); 112 for (;Begin != End; ++Begin) { 113 unsigned Reg = (*Begin)->reg; 114 if (LRStage[Reg] == RS_New) 115 LRStage[Reg] = NewStage; 116 } 117 } 118 119 // splitting state. 120 std::auto_ptr<SplitAnalysis> SA; 121 std::auto_ptr<SplitEditor> SE; 122 123 /// Cached per-block interference maps 124 InterferenceCache IntfCache; 125 126 /// All basic blocks where the current register is live. 127 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 128 129 /// Global live range splitting candidate info. 130 struct GlobalSplitCandidate { 131 unsigned PhysReg; 132 BitVector LiveBundles; 133 }; 134 135 /// Candidate info for for each PhysReg in AllocationOrder. 136 /// This vector never shrinks, but grows to the size of the largest register 137 /// class. 138 SmallVector<GlobalSplitCandidate, 32> GlobalCand; 139 140 /// For every instruction in SA->UseSlots, store the previous non-copy 141 /// instruction. 142 SmallVector<SlotIndex, 8> PrevSlot; 143 144public: 145 RAGreedy(); 146 147 /// Return the pass name. 148 virtual const char* getPassName() const { 149 return "Greedy Register Allocator"; 150 } 151 152 /// RAGreedy analysis usage. 153 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 154 virtual void releaseMemory(); 155 virtual Spiller &spiller() { return *SpillerInstance; } 156 virtual void enqueue(LiveInterval *LI); 157 virtual LiveInterval *dequeue(); 158 virtual unsigned selectOrSplit(LiveInterval&, 159 SmallVectorImpl<LiveInterval*>&); 160 161 /// Perform register allocation. 162 virtual bool runOnMachineFunction(MachineFunction &mf); 163 164 static char ID; 165 166private: 167 void LRE_WillEraseInstruction(MachineInstr*); 168 bool LRE_CanEraseVirtReg(unsigned); 169 void LRE_WillShrinkVirtReg(unsigned); 170 void LRE_DidCloneVirtReg(unsigned, unsigned); 171 172 float calcSplitConstraints(unsigned); 173 float calcGlobalSplitCost(const BitVector&); 174 void splitAroundRegion(LiveInterval&, unsigned, const BitVector&, 175 SmallVectorImpl<LiveInterval*>&); 176 void calcGapWeights(unsigned, SmallVectorImpl<float>&); 177 SlotIndex getPrevMappedIndex(const MachineInstr*); 178 void calcPrevSlots(); 179 unsigned nextSplitPoint(unsigned); 180 bool canEvictInterference(LiveInterval&, unsigned, float&); 181 182 unsigned tryEvict(LiveInterval&, AllocationOrder&, 183 SmallVectorImpl<LiveInterval*>&); 184 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 185 SmallVectorImpl<LiveInterval*>&); 186 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 187 SmallVectorImpl<LiveInterval*>&); 188 unsigned trySplit(LiveInterval&, AllocationOrder&, 189 SmallVectorImpl<LiveInterval*>&); 190}; 191} // end anonymous namespace 192 193char RAGreedy::ID = 0; 194 195FunctionPass* llvm::createGreedyRegisterAllocator() { 196 return new RAGreedy(); 197} 198 199RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) { 200 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 201 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 202 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 203 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 204 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 205 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 206 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 207 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 208 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 209 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 210 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 211 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 212 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 213 initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 214} 215 216void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 217 AU.setPreservesCFG(); 218 AU.addRequired<AliasAnalysis>(); 219 AU.addPreserved<AliasAnalysis>(); 220 AU.addRequired<LiveIntervals>(); 221 AU.addRequired<SlotIndexes>(); 222 AU.addPreserved<SlotIndexes>(); 223 AU.addRequired<LiveDebugVariables>(); 224 AU.addPreserved<LiveDebugVariables>(); 225 if (StrongPHIElim) 226 AU.addRequiredID(StrongPHIEliminationID); 227 AU.addRequiredTransitive<RegisterCoalescer>(); 228 AU.addRequired<CalculateSpillWeights>(); 229 AU.addRequired<LiveStacks>(); 230 AU.addPreserved<LiveStacks>(); 231 AU.addRequired<MachineDominatorTree>(); 232 AU.addPreserved<MachineDominatorTree>(); 233 AU.addRequired<MachineLoopInfo>(); 234 AU.addPreserved<MachineLoopInfo>(); 235 AU.addRequired<MachineLoopRanges>(); 236 AU.addPreserved<MachineLoopRanges>(); 237 AU.addRequired<VirtRegMap>(); 238 AU.addPreserved<VirtRegMap>(); 239 AU.addRequired<EdgeBundles>(); 240 AU.addRequired<SpillPlacement>(); 241 MachineFunctionPass::getAnalysisUsage(AU); 242} 243 244 245//===----------------------------------------------------------------------===// 246// LiveRangeEdit delegate methods 247//===----------------------------------------------------------------------===// 248 249void RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) { 250 // LRE itself will remove from SlotIndexes and parent basic block. 251 VRM->RemoveMachineInstrFromMaps(MI); 252} 253 254bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 255 if (unsigned PhysReg = VRM->getPhys(VirtReg)) { 256 unassign(LIS->getInterval(VirtReg), PhysReg); 257 return true; 258 } 259 // Unassigned virtreg is probably in the priority queue. 260 // RegAllocBase will erase it after dequeueing. 261 return false; 262} 263 264void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 265 unsigned PhysReg = VRM->getPhys(VirtReg); 266 if (!PhysReg) 267 return; 268 269 // Register is assigned, put it back on the queue for reassignment. 270 LiveInterval &LI = LIS->getInterval(VirtReg); 271 unassign(LI, PhysReg); 272 enqueue(&LI); 273} 274 275void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 276 // LRE may clone a virtual register because dead code elimination causes it to 277 // be split into connected components. Ensure that the new register gets the 278 // same stage as the parent. 279 LRStage.grow(New); 280 LRStage[New] = LRStage[Old]; 281} 282 283void RAGreedy::releaseMemory() { 284 SpillerInstance.reset(0); 285 LRStage.clear(); 286 RegAllocBase::releaseMemory(); 287} 288 289void RAGreedy::enqueue(LiveInterval *LI) { 290 // Prioritize live ranges by size, assigning larger ranges first. 291 // The queue holds (size, reg) pairs. 292 const unsigned Size = LI->getSize(); 293 const unsigned Reg = LI->reg; 294 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 295 "Can only enqueue virtual registers"); 296 unsigned Prio; 297 298 LRStage.grow(Reg); 299 if (LRStage[Reg] == RS_New) 300 LRStage[Reg] = RS_First; 301 302 if (LRStage[Reg] == RS_Second) 303 // Unsplit ranges that couldn't be allocated immediately are deferred until 304 // everything else has been allocated. Long ranges are allocated last so 305 // they are split against realistic interference. 306 Prio = (1u << 31) - Size; 307 else { 308 // Everything else is allocated in long->short order. Long ranges that don't 309 // fit should be spilled ASAP so they don't create interference. 310 Prio = (1u << 31) + Size; 311 312 // Boost ranges that have a physical register hint. 313 if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 314 Prio |= (1u << 30); 315 } 316 317 Queue.push(std::make_pair(Prio, Reg)); 318} 319 320LiveInterval *RAGreedy::dequeue() { 321 if (Queue.empty()) 322 return 0; 323 LiveInterval *LI = &LIS->getInterval(Queue.top().second); 324 Queue.pop(); 325 return LI; 326} 327 328//===----------------------------------------------------------------------===// 329// Interference eviction 330//===----------------------------------------------------------------------===// 331 332/// canEvict - Return true if all interferences between VirtReg and PhysReg can 333/// be evicted. Set maxWeight to the maximal spill weight of an interference. 334bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 335 float &MaxWeight) { 336 float Weight = 0; 337 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 338 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 339 // If there is 10 or more interferences, chances are one is smaller. 340 if (Q.collectInterferingVRegs(10) >= 10) 341 return false; 342 343 // Check if any interfering live range is heavier than VirtReg. 344 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 345 LiveInterval *Intf = Q.interferingVRegs()[i]; 346 if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 347 return false; 348 if (Intf->weight >= VirtReg.weight) 349 return false; 350 Weight = std::max(Weight, Intf->weight); 351 } 352 } 353 MaxWeight = Weight; 354 return true; 355} 356 357/// tryEvict - Try to evict all interferences for a physreg. 358/// @param VirtReg Currently unassigned virtual register. 359/// @param Order Physregs to try. 360/// @return Physreg to assign VirtReg, or 0. 361unsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 362 AllocationOrder &Order, 363 SmallVectorImpl<LiveInterval*> &NewVRegs){ 364 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 365 366 // Keep track of the lightest single interference seen so far. 367 float BestWeight = 0; 368 unsigned BestPhys = 0; 369 370 Order.rewind(); 371 while (unsigned PhysReg = Order.next()) { 372 float Weight = 0; 373 if (!canEvictInterference(VirtReg, PhysReg, Weight)) 374 continue; 375 376 // This is an eviction candidate. 377 DEBUG(dbgs() << "max " << PrintReg(PhysReg, TRI) << " interference = " 378 << Weight << '\n'); 379 if (BestPhys && Weight >= BestWeight) 380 continue; 381 382 // Best so far. 383 BestPhys = PhysReg; 384 BestWeight = Weight; 385 // Stop if the hint can be used. 386 if (Order.isHint(PhysReg)) 387 break; 388 } 389 390 if (!BestPhys) 391 return 0; 392 393 DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n"); 394 for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) { 395 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 396 assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 397 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 398 LiveInterval *Intf = Q.interferingVRegs()[i]; 399 unassign(*Intf, VRM->getPhys(Intf->reg)); 400 ++NumEvicted; 401 NewVRegs.push_back(Intf); 402 } 403 } 404 return BestPhys; 405} 406 407 408//===----------------------------------------------------------------------===// 409// Region Splitting 410//===----------------------------------------------------------------------===// 411 412/// calcSplitConstraints - Fill out the SplitConstraints vector based on the 413/// interference pattern in Physreg and its aliases. Return the static cost of 414/// this split, assuming that all preferences in SplitConstraints are met. 415float RAGreedy::calcSplitConstraints(unsigned PhysReg) { 416 InterferenceCache::Cursor Intf(IntfCache, PhysReg); 417 418 // Reset interference dependent info. 419 SplitConstraints.resize(SA->LiveBlocks.size()); 420 float StaticCost = 0; 421 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 422 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 423 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 424 425 BC.Number = BI.MBB->getNumber(); 426 Intf.moveToBlock(BC.Number); 427 BC.Entry = (BI.Uses && BI.LiveIn) ? 428 SpillPlacement::PrefReg : SpillPlacement::DontCare; 429 BC.Exit = (BI.Uses && BI.LiveOut) ? 430 SpillPlacement::PrefReg : SpillPlacement::DontCare; 431 432 if (!Intf.hasInterference()) 433 continue; 434 435 // Number of spill code instructions to insert. 436 unsigned Ins = 0; 437 438 // Interference for the live-in value. 439 if (BI.LiveIn) { 440 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 441 BC.Entry = SpillPlacement::MustSpill, Ins += BI.Uses; 442 else if (!BI.Uses) 443 BC.Entry = SpillPlacement::PrefSpill; 444 else if (Intf.first() < BI.FirstUse) 445 BC.Entry = SpillPlacement::PrefSpill, ++Ins; 446 else if (Intf.first() < (BI.LiveThrough ? BI.LastUse : BI.Kill)) 447 ++Ins; 448 } 449 450 // Interference for the live-out value. 451 if (BI.LiveOut) { 452 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 453 BC.Exit = SpillPlacement::MustSpill, Ins += BI.Uses; 454 else if (!BI.Uses) 455 BC.Exit = SpillPlacement::PrefSpill; 456 else if (Intf.last() > BI.LastUse) 457 BC.Exit = SpillPlacement::PrefSpill, ++Ins; 458 else if (Intf.last() > (BI.LiveThrough ? BI.FirstUse : BI.Def)) 459 ++Ins; 460 } 461 462 // Accumulate the total frequency of inserted spill code. 463 if (Ins) 464 StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 465 } 466 return StaticCost; 467} 468 469 470/// calcGlobalSplitCost - Return the global split cost of following the split 471/// pattern in LiveBundles. This cost should be added to the local cost of the 472/// interference pattern in SplitConstraints. 473/// 474float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { 475 float GlobalCost = 0; 476 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 477 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 478 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 479 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 480 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 481 unsigned Ins = 0; 482 483 if (!BI.Uses) 484 Ins += RegIn != RegOut; 485 else { 486 if (BI.LiveIn) 487 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 488 if (BI.LiveOut) 489 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 490 } 491 if (Ins) 492 GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 493 } 494 return GlobalCost; 495} 496 497/// splitAroundRegion - Split VirtReg around the region determined by 498/// LiveBundles. Make an effort to avoid interference from PhysReg. 499/// 500/// The 'register' interval is going to contain as many uses as possible while 501/// avoiding interference. The 'stack' interval is the complement constructed by 502/// SplitEditor. It will contain the rest. 503/// 504void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, 505 const BitVector &LiveBundles, 506 SmallVectorImpl<LiveInterval*> &NewVRegs) { 507 DEBUG({ 508 dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI) 509 << " with bundles"; 510 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 511 dbgs() << " EB#" << i; 512 dbgs() << ".\n"; 513 }); 514 515 InterferenceCache::Cursor Intf(IntfCache, PhysReg); 516 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 517 SE->reset(LREdit); 518 519 // Create the main cross-block interval. 520 SE->openIntv(); 521 522 // First add all defs that are live out of a block. 523 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 524 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 525 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 526 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 527 528 // Should the register be live out? 529 if (!BI.LiveOut || !RegOut) 530 continue; 531 532 SlotIndex Start, Stop; 533 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 534 Intf.moveToBlock(BI.MBB->getNumber()); 535 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 536 << Bundles->getBundle(BI.MBB->getNumber(), 1) 537 << " [" << Start << ';' 538 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 539 << ") intf [" << Intf.first() << ';' << Intf.last() << ')'); 540 541 // The interference interval should either be invalid or overlap MBB. 542 assert((!Intf.hasInterference() || Intf.first() < Stop) 543 && "Bad interference"); 544 assert((!Intf.hasInterference() || Intf.last() > Start) 545 && "Bad interference"); 546 547 // Check interference leaving the block. 548 if (!Intf.hasInterference()) { 549 // Block is interference-free. 550 DEBUG(dbgs() << ", no interference"); 551 if (!BI.Uses) { 552 assert(BI.LiveThrough && "No uses, but not live through block?"); 553 // Block is live-through without interference. 554 DEBUG(dbgs() << ", no uses" 555 << (RegIn ? ", live-through.\n" : ", stack in.\n")); 556 if (!RegIn) 557 SE->enterIntvAtEnd(*BI.MBB); 558 continue; 559 } 560 if (!BI.LiveThrough) { 561 DEBUG(dbgs() << ", not live-through.\n"); 562 SE->useIntv(SE->enterIntvBefore(BI.Def), Stop); 563 continue; 564 } 565 if (!RegIn) { 566 // Block is live-through, but entry bundle is on the stack. 567 // Reload just before the first use. 568 DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 569 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 570 continue; 571 } 572 DEBUG(dbgs() << ", live-through.\n"); 573 continue; 574 } 575 576 // Block has interference. 577 DEBUG(dbgs() << ", interference to " << Intf.last()); 578 579 if (!BI.LiveThrough && Intf.last() <= BI.Def) { 580 // The interference doesn't reach the outgoing segment. 581 DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n'); 582 SE->useIntv(BI.Def, Stop); 583 continue; 584 } 585 586 587 if (!BI.Uses) { 588 // No uses in block, avoid interference by reloading as late as possible. 589 DEBUG(dbgs() << ", no uses.\n"); 590 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 591 assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 592 continue; 593 } 594 595 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 596 if (Intf.last().getBoundaryIndex() < BI.LastUse) { 597 // There are interference-free uses at the end of the block. 598 // Find the first use that can get the live-out register. 599 SmallVectorImpl<SlotIndex>::const_iterator UI = 600 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 601 Intf.last().getBoundaryIndex()); 602 assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 603 SlotIndex Use = *UI; 604 assert(Use <= BI.LastUse && "Couldn't find last use"); 605 // Only attempt a split befroe the last split point. 606 if (Use.getBaseIndex() <= LastSplitPoint) { 607 DEBUG(dbgs() << ", free use at " << Use << ".\n"); 608 SlotIndex SegStart = SE->enterIntvBefore(Use); 609 assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 610 assert(SegStart < LastSplitPoint && "Impossible split point"); 611 SE->useIntv(SegStart, Stop); 612 continue; 613 } 614 } 615 616 // Interference is after the last use. 617 DEBUG(dbgs() << " after last use.\n"); 618 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 619 assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 620 } 621 622 // Now all defs leading to live bundles are handled, do everything else. 623 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 624 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 625 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 626 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 627 628 // Is the register live-in? 629 if (!BI.LiveIn || !RegIn) 630 continue; 631 632 // We have an incoming register. Check for interference. 633 SlotIndex Start, Stop; 634 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 635 Intf.moveToBlock(BI.MBB->getNumber()); 636 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 637 << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';' 638 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 639 << ')'); 640 641 // Check interference entering the block. 642 if (!Intf.hasInterference()) { 643 // Block is interference-free. 644 DEBUG(dbgs() << ", no interference"); 645 if (!BI.Uses) { 646 assert(BI.LiveThrough && "No uses, but not live through block?"); 647 // Block is live-through without interference. 648 if (RegOut) { 649 DEBUG(dbgs() << ", no uses, live-through.\n"); 650 SE->useIntv(Start, Stop); 651 } else { 652 DEBUG(dbgs() << ", no uses, stack-out.\n"); 653 SE->leaveIntvAtTop(*BI.MBB); 654 } 655 continue; 656 } 657 if (!BI.LiveThrough) { 658 DEBUG(dbgs() << ", killed in block.\n"); 659 SE->useIntv(Start, SE->leaveIntvAfter(BI.Kill)); 660 continue; 661 } 662 if (!RegOut) { 663 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 664 // Block is live-through, but exit bundle is on the stack. 665 // Spill immediately after the last use. 666 if (BI.LastUse < LastSplitPoint) { 667 DEBUG(dbgs() << ", uses, stack-out.\n"); 668 SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 669 continue; 670 } 671 // The last use is after the last split point, it is probably an 672 // indirect jump. 673 DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 674 << LastSplitPoint << ", stack-out.\n"); 675 SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint); 676 SE->useIntv(Start, SegEnd); 677 // Run a double interval from the split to the last use. 678 // This makes it possible to spill the complement without affecting the 679 // indirect branch. 680 SE->overlapIntv(SegEnd, BI.LastUse); 681 continue; 682 } 683 // Register is live-through. 684 DEBUG(dbgs() << ", uses, live-through.\n"); 685 SE->useIntv(Start, Stop); 686 continue; 687 } 688 689 // Block has interference. 690 DEBUG(dbgs() << ", interference from " << Intf.first()); 691 692 if (!BI.LiveThrough && Intf.first() >= BI.Kill) { 693 // The interference doesn't reach the outgoing segment. 694 DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n'); 695 SE->useIntv(Start, BI.Kill); 696 continue; 697 } 698 699 if (!BI.Uses) { 700 // No uses in block, avoid interference by spilling as soon as possible. 701 DEBUG(dbgs() << ", no uses.\n"); 702 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 703 assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 704 continue; 705 } 706 if (Intf.first().getBaseIndex() > BI.FirstUse) { 707 // There are interference-free uses at the beginning of the block. 708 // Find the last use that can get the register. 709 SmallVectorImpl<SlotIndex>::const_iterator UI = 710 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 711 Intf.first().getBaseIndex()); 712 assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 713 SlotIndex Use = (--UI)->getBoundaryIndex(); 714 DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 715 SlotIndex SegEnd = SE->leaveIntvAfter(Use); 716 assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 717 SE->useIntv(Start, SegEnd); 718 continue; 719 } 720 721 // Interference is before the first use. 722 DEBUG(dbgs() << " before first use.\n"); 723 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 724 assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 725 } 726 727 SE->closeIntv(); 728 729 // FIXME: Should we be more aggressive about splitting the stack region into 730 // per-block segments? The current approach allows the stack region to 731 // separate into connected components. Some components may be allocatable. 732 SE->finish(); 733 ++NumGlobalSplits; 734 735 if (VerifyEnabled) 736 MF->verify(this, "After splitting live range around region"); 737} 738 739unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 740 SmallVectorImpl<LiveInterval*> &NewVRegs) { 741 BitVector LiveBundles, BestBundles; 742 float BestCost = 0; 743 unsigned BestReg = 0; 744 745 Order.rewind(); 746 for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) { 747 if (GlobalCand.size() <= Cand) 748 GlobalCand.resize(Cand+1); 749 GlobalCand[Cand].PhysReg = PhysReg; 750 751 float Cost = calcSplitConstraints(PhysReg); 752 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 753 if (BestReg && Cost >= BestCost) { 754 DEBUG(dbgs() << " higher.\n"); 755 continue; 756 } 757 758 SpillPlacer->placeSpills(SplitConstraints, LiveBundles); 759 // No live bundles, defer to splitSingleBlocks(). 760 if (!LiveBundles.any()) { 761 DEBUG(dbgs() << " no bundles.\n"); 762 continue; 763 } 764 765 Cost += calcGlobalSplitCost(LiveBundles); 766 DEBUG({ 767 dbgs() << ", total = " << Cost << " with bundles"; 768 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 769 dbgs() << " EB#" << i; 770 dbgs() << ".\n"; 771 }); 772 if (!BestReg || Cost < BestCost) { 773 BestReg = PhysReg; 774 BestCost = 0.98f * Cost; // Prevent rounding effects. 775 BestBundles.swap(LiveBundles); 776 } 777 } 778 779 if (!BestReg) 780 return 0; 781 782 splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); 783 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region); 784 return 0; 785} 786 787 788//===----------------------------------------------------------------------===// 789// Local Splitting 790//===----------------------------------------------------------------------===// 791 792 793/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 794/// in order to use PhysReg between two entries in SA->UseSlots. 795/// 796/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 797/// 798void RAGreedy::calcGapWeights(unsigned PhysReg, 799 SmallVectorImpl<float> &GapWeight) { 800 assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 801 const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 802 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 803 const unsigned NumGaps = Uses.size()-1; 804 805 // Start and end points for the interference check. 806 SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 807 SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 808 809 GapWeight.assign(NumGaps, 0.0f); 810 811 // Add interference from each overlapping register. 812 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 813 if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 814 .checkInterference()) 815 continue; 816 817 // We know that VirtReg is a continuous interval from FirstUse to LastUse, 818 // so we don't need InterferenceQuery. 819 // 820 // Interference that overlaps an instruction is counted in both gaps 821 // surrounding the instruction. The exception is interference before 822 // StartIdx and after StopIdx. 823 // 824 LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 825 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 826 // Skip the gaps before IntI. 827 while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 828 if (++Gap == NumGaps) 829 break; 830 if (Gap == NumGaps) 831 break; 832 833 // Update the gaps covered by IntI. 834 const float weight = IntI.value()->weight; 835 for (; Gap != NumGaps; ++Gap) { 836 GapWeight[Gap] = std::max(GapWeight[Gap], weight); 837 if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 838 break; 839 } 840 if (Gap == NumGaps) 841 break; 842 } 843 } 844} 845 846/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 847/// before MI that has a slot index. If MI is the first mapped instruction in 848/// its block, return the block start index instead. 849/// 850SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 851 assert(MI && "Missing MachineInstr"); 852 const MachineBasicBlock *MBB = MI->getParent(); 853 MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 854 while (I != B) 855 if (!(--I)->isDebugValue() && !I->isCopy()) 856 return Indexes->getInstructionIndex(I); 857 return Indexes->getMBBStartIdx(MBB); 858} 859 860/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 861/// real non-copy instruction for each instruction in SA->UseSlots. 862/// 863void RAGreedy::calcPrevSlots() { 864 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 865 PrevSlot.clear(); 866 PrevSlot.reserve(Uses.size()); 867 for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 868 const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 869 PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 870 } 871} 872 873/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 874/// be beneficial to split before UseSlots[i]. 875/// 876/// 0 is always a valid split point 877unsigned RAGreedy::nextSplitPoint(unsigned i) { 878 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 879 const unsigned Size = Uses.size(); 880 assert(i != Size && "No split points after the end"); 881 // Allow split before i when Uses[i] is not adjacent to the previous use. 882 while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 883 ; 884 return i; 885} 886 887/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 888/// basic block. 889/// 890unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 891 SmallVectorImpl<LiveInterval*> &NewVRegs) { 892 assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 893 const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 894 895 // Note that it is possible to have an interval that is live-in or live-out 896 // while only covering a single block - A phi-def can use undef values from 897 // predecessors, and the block could be a single-block loop. 898 // We don't bother doing anything clever about such a case, we simply assume 899 // that the interval is continuous from FirstUse to LastUse. We should make 900 // sure that we don't do anything illegal to such an interval, though. 901 902 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 903 if (Uses.size() <= 2) 904 return 0; 905 const unsigned NumGaps = Uses.size()-1; 906 907 DEBUG({ 908 dbgs() << "tryLocalSplit: "; 909 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 910 dbgs() << ' ' << SA->UseSlots[i]; 911 dbgs() << '\n'; 912 }); 913 914 // For every use, find the previous mapped non-copy instruction. 915 // We use this to detect valid split points, and to estimate new interval 916 // sizes. 917 calcPrevSlots(); 918 919 unsigned BestBefore = NumGaps; 920 unsigned BestAfter = 0; 921 float BestDiff = 0; 922 923 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 924 SmallVector<float, 8> GapWeight; 925 926 Order.rewind(); 927 while (unsigned PhysReg = Order.next()) { 928 // Keep track of the largest spill weight that would need to be evicted in 929 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 930 calcGapWeights(PhysReg, GapWeight); 931 932 // Try to find the best sequence of gaps to close. 933 // The new spill weight must be larger than any gap interference. 934 935 // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 936 unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 937 938 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 939 // It is the spill weight that needs to be evicted. 940 float MaxGap = GapWeight[0]; 941 for (unsigned i = 1; i != SplitAfter; ++i) 942 MaxGap = std::max(MaxGap, GapWeight[i]); 943 944 for (;;) { 945 // Live before/after split? 946 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 947 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 948 949 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 950 << Uses[SplitBefore] << '-' << Uses[SplitAfter] 951 << " i=" << MaxGap); 952 953 // Stop before the interval gets so big we wouldn't be making progress. 954 if (!LiveBefore && !LiveAfter) { 955 DEBUG(dbgs() << " all\n"); 956 break; 957 } 958 // Should the interval be extended or shrunk? 959 bool Shrink = true; 960 if (MaxGap < HUGE_VALF) { 961 // Estimate the new spill weight. 962 // 963 // Each instruction reads and writes the register, except the first 964 // instr doesn't read when !FirstLive, and the last instr doesn't write 965 // when !LastLive. 966 // 967 // We will be inserting copies before and after, so the total number of 968 // reads and writes is 2 * EstUses. 969 // 970 const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 971 2*(LiveBefore + LiveAfter); 972 973 // Try to guess the size of the new interval. This should be trivial, 974 // but the slot index of an inserted copy can be a lot smaller than the 975 // instruction it is inserted before if there are many dead indexes 976 // between them. 977 // 978 // We measure the distance from the instruction before SplitBefore to 979 // get a conservative estimate. 980 // 981 // The final distance can still be different if inserting copies 982 // triggers a slot index renumbering. 983 // 984 const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 985 PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 986 // Would this split be possible to allocate? 987 // Never allocate all gaps, we wouldn't be making progress. 988 float Diff = EstWeight - MaxGap; 989 DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff); 990 if (Diff > 0) { 991 Shrink = false; 992 if (Diff > BestDiff) { 993 DEBUG(dbgs() << " (best)"); 994 BestDiff = Diff; 995 BestBefore = SplitBefore; 996 BestAfter = SplitAfter; 997 } 998 } 999 } 1000 1001 // Try to shrink. 1002 if (Shrink) { 1003 SplitBefore = nextSplitPoint(SplitBefore); 1004 if (SplitBefore < SplitAfter) { 1005 DEBUG(dbgs() << " shrink\n"); 1006 // Recompute the max when necessary. 1007 if (GapWeight[SplitBefore - 1] >= MaxGap) { 1008 MaxGap = GapWeight[SplitBefore]; 1009 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1010 MaxGap = std::max(MaxGap, GapWeight[i]); 1011 } 1012 continue; 1013 } 1014 MaxGap = 0; 1015 } 1016 1017 // Try to extend the interval. 1018 if (SplitAfter >= NumGaps) { 1019 DEBUG(dbgs() << " end\n"); 1020 break; 1021 } 1022 1023 DEBUG(dbgs() << " extend\n"); 1024 for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1025 SplitAfter != e; ++SplitAfter) 1026 MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1027 continue; 1028 } 1029 } 1030 1031 // Didn't find any candidates? 1032 if (BestBefore == NumGaps) 1033 return 0; 1034 1035 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1036 << '-' << Uses[BestAfter] << ", " << BestDiff 1037 << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1038 1039 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1040 SE->reset(LREdit); 1041 1042 SE->openIntv(); 1043 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1044 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1045 SE->useIntv(SegStart, SegStop); 1046 SE->closeIntv(); 1047 SE->finish(); 1048 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local); 1049 ++NumLocalSplits; 1050 1051 return 0; 1052} 1053 1054//===----------------------------------------------------------------------===// 1055// Live Range Splitting 1056//===----------------------------------------------------------------------===// 1057 1058/// trySplit - Try to split VirtReg or one of its interferences, making it 1059/// assignable. 1060/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1061unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1062 SmallVectorImpl<LiveInterval*>&NewVRegs) { 1063 // Local intervals are handled separately. 1064 if (LIS->intervalIsInOneMBB(VirtReg)) { 1065 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1066 SA->analyze(&VirtReg); 1067 return tryLocalSplit(VirtReg, Order, NewVRegs); 1068 } 1069 1070 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1071 1072 // Don't iterate global splitting. 1073 // Move straight to spilling if this range was produced by a global split. 1074 LiveRangeStage Stage = getStage(VirtReg); 1075 if (Stage >= RS_Block) 1076 return 0; 1077 1078 SA->analyze(&VirtReg); 1079 1080 // First try to split around a region spanning multiple blocks. 1081 if (Stage < RS_Region) { 1082 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1083 if (PhysReg || !NewVRegs.empty()) 1084 return PhysReg; 1085 } 1086 1087 // Then isolate blocks with multiple uses. 1088 if (Stage < RS_Block) { 1089 SplitAnalysis::BlockPtrSet Blocks; 1090 if (SA->getMultiUseBlocks(Blocks)) { 1091 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1092 SE->reset(LREdit); 1093 SE->splitSingleBlocks(Blocks); 1094 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block); 1095 if (VerifyEnabled) 1096 MF->verify(this, "After splitting live range around basic blocks"); 1097 } 1098 } 1099 1100 // Don't assign any physregs. 1101 return 0; 1102} 1103 1104 1105//===----------------------------------------------------------------------===// 1106// Main Entry Point 1107//===----------------------------------------------------------------------===// 1108 1109unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1110 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1111 // First try assigning a free register. 1112 AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 1113 while (unsigned PhysReg = Order.next()) { 1114 if (!checkPhysRegInterference(VirtReg, PhysReg)) 1115 return PhysReg; 1116 } 1117 1118 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1119 return PhysReg; 1120 1121 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1122 1123 // The first time we see a live range, don't try to split or spill. 1124 // Wait until the second time, when all smaller ranges have been allocated. 1125 // This gives a better picture of the interference to split around. 1126 LiveRangeStage Stage = getStage(VirtReg); 1127 if (Stage == RS_First) { 1128 LRStage[VirtReg.reg] = RS_Second; 1129 DEBUG(dbgs() << "wait for second round\n"); 1130 NewVRegs.push_back(&VirtReg); 1131 return 0; 1132 } 1133 1134 assert(Stage < RS_Spill && "Cannot allocate after spilling"); 1135 1136 // Try splitting VirtReg or interferences. 1137 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1138 if (PhysReg || !NewVRegs.empty()) 1139 return PhysReg; 1140 1141 // Finally spill VirtReg itself. 1142 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1143 LiveRangeEdit LRE(VirtReg, NewVRegs, this); 1144 spiller().spill(LRE); 1145 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill); 1146 1147 if (VerifyEnabled) 1148 MF->verify(this, "After spilling"); 1149 1150 // The live virtual register requesting allocation was spilled, so tell 1151 // the caller not to allocate anything during this round. 1152 return 0; 1153} 1154 1155bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1156 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1157 << "********** Function: " 1158 << ((Value*)mf.getFunction())->getName() << '\n'); 1159 1160 MF = &mf; 1161 if (VerifyEnabled) 1162 MF->verify(this, "Before greedy register allocator"); 1163 1164 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1165 Indexes = &getAnalysis<SlotIndexes>(); 1166 DomTree = &getAnalysis<MachineDominatorTree>(); 1167 ReservedRegs = TRI->getReservedRegs(*MF); 1168 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1169 Loops = &getAnalysis<MachineLoopInfo>(); 1170 LoopRanges = &getAnalysis<MachineLoopRanges>(); 1171 Bundles = &getAnalysis<EdgeBundles>(); 1172 SpillPlacer = &getAnalysis<SpillPlacement>(); 1173 1174 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1175 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 1176 LRStage.clear(); 1177 LRStage.resize(MRI->getNumVirtRegs()); 1178 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 1179 1180 allocatePhysRegs(); 1181 addMBBLiveIns(MF); 1182 LIS->addKillFlags(); 1183 1184 // Run rewriter 1185 { 1186 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1187 VRM->rewrite(Indexes); 1188 } 1189 1190 // Write out new DBG_VALUE instructions. 1191 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 1192 1193 // The pass output is in VirtRegMap. Release all the transient data. 1194 releaseMemory(); 1195 1196 return true; 1197} 1198