RegAllocGreedy.cpp revision 9efa2a263ea470caacef1c85f6ca45e32bf516d3
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 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 418 419 // Reset interference dependent info. 420 SplitConstraints.resize(UseBlocks.size()); 421 float StaticCost = 0; 422 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 423 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 424 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 425 426 BC.Number = BI.MBB->getNumber(); 427 Intf.moveToBlock(BC.Number); 428 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 429 BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 430 431 if (!Intf.hasInterference()) 432 continue; 433 434 // Number of spill code instructions to insert. 435 unsigned Ins = 0; 436 437 // Interference for the live-in value. 438 if (BI.LiveIn) { 439 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 440 BC.Entry = SpillPlacement::MustSpill, ++Ins; 441 else if (Intf.first() < BI.FirstUse) 442 BC.Entry = SpillPlacement::PrefSpill, ++Ins; 443 else if (Intf.first() < (BI.LiveThrough ? BI.LastUse : BI.Kill)) 444 ++Ins; 445 } 446 447 // Interference for the live-out value. 448 if (BI.LiveOut) { 449 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 450 BC.Exit = SpillPlacement::MustSpill, ++Ins; 451 else if (Intf.last() > BI.LastUse) 452 BC.Exit = SpillPlacement::PrefSpill, ++Ins; 453 else if (Intf.last() > (BI.LiveThrough ? BI.FirstUse : BI.Def)) 454 ++Ins; 455 } 456 457 // Accumulate the total frequency of inserted spill code. 458 if (Ins) 459 StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 460 } 461 462 // Now handle the live-through blocks without uses. 463 ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks(); 464 SplitConstraints.resize(UseBlocks.size() + ThroughBlocks.size()); 465 for (unsigned i = 0; i != ThroughBlocks.size(); ++i) { 466 SpillPlacement::BlockConstraint &BC = SplitConstraints[UseBlocks.size()+i]; 467 BC.Number = ThroughBlocks[i]; 468 BC.Entry = SpillPlacement::DontCare; 469 BC.Exit = SpillPlacement::DontCare; 470 471 Intf.moveToBlock(BC.Number); 472 if (!Intf.hasInterference()) 473 continue; 474 475 // Interference for the live-in value. 476 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 477 BC.Entry = SpillPlacement::MustSpill; 478 else 479 BC.Entry = SpillPlacement::PrefSpill; 480 481 // Interference for the live-out value. 482 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 483 BC.Exit = SpillPlacement::MustSpill; 484 else 485 BC.Exit = SpillPlacement::PrefSpill; 486 } 487 488 return StaticCost; 489} 490 491 492/// calcGlobalSplitCost - Return the global split cost of following the split 493/// pattern in LiveBundles. This cost should be added to the local cost of the 494/// interference pattern in SplitConstraints. 495/// 496float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { 497 float GlobalCost = 0; 498 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 499 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 500 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 501 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 502 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 503 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 504 unsigned Ins = 0; 505 506 if (BI.LiveIn) 507 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 508 if (BI.LiveOut) 509 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 510 if (Ins) 511 GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 512 } 513 514 ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks(); 515 SplitConstraints.resize(UseBlocks.size() + ThroughBlocks.size()); 516 for (unsigned i = 0; i != ThroughBlocks.size(); ++i) { 517 unsigned Number = ThroughBlocks[i]; 518 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 519 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 520 if (RegIn != RegOut) 521 GlobalCost += SpillPlacer->getBlockFrequency(Number); 522 } 523 return GlobalCost; 524} 525 526/// splitAroundRegion - Split VirtReg around the region determined by 527/// LiveBundles. Make an effort to avoid interference from PhysReg. 528/// 529/// The 'register' interval is going to contain as many uses as possible while 530/// avoiding interference. The 'stack' interval is the complement constructed by 531/// SplitEditor. It will contain the rest. 532/// 533void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, 534 const BitVector &LiveBundles, 535 SmallVectorImpl<LiveInterval*> &NewVRegs) { 536 DEBUG({ 537 dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI) 538 << " with bundles"; 539 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 540 dbgs() << " EB#" << i; 541 dbgs() << ".\n"; 542 }); 543 544 InterferenceCache::Cursor Intf(IntfCache, PhysReg); 545 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 546 SE->reset(LREdit); 547 548 // Create the main cross-block interval. 549 SE->openIntv(); 550 551 // First add all defs that are live out of a block. 552 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 553 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 554 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 555 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 556 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 557 558 // Should the register be live out? 559 if (!BI.LiveOut || !RegOut) 560 continue; 561 562 SlotIndex Start, Stop; 563 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 564 Intf.moveToBlock(BI.MBB->getNumber()); 565 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 566 << Bundles->getBundle(BI.MBB->getNumber(), 1) 567 << " [" << Start << ';' 568 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 569 << ") intf [" << Intf.first() << ';' << Intf.last() << ')'); 570 571 // The interference interval should either be invalid or overlap MBB. 572 assert((!Intf.hasInterference() || Intf.first() < Stop) 573 && "Bad interference"); 574 assert((!Intf.hasInterference() || Intf.last() > Start) 575 && "Bad interference"); 576 577 // Check interference leaving the block. 578 if (!Intf.hasInterference()) { 579 // Block is interference-free. 580 DEBUG(dbgs() << ", no interference"); 581 if (!BI.LiveThrough) { 582 DEBUG(dbgs() << ", not live-through.\n"); 583 SE->useIntv(SE->enterIntvBefore(BI.Def), Stop); 584 continue; 585 } 586 if (!RegIn) { 587 // Block is live-through, but entry bundle is on the stack. 588 // Reload just before the first use. 589 DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 590 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 591 continue; 592 } 593 DEBUG(dbgs() << ", live-through.\n"); 594 continue; 595 } 596 597 // Block has interference. 598 DEBUG(dbgs() << ", interference to " << Intf.last()); 599 600 if (!BI.LiveThrough && Intf.last() <= BI.Def) { 601 // The interference doesn't reach the outgoing segment. 602 DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n'); 603 SE->useIntv(BI.Def, Stop); 604 continue; 605 } 606 607 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 608 if (Intf.last().getBoundaryIndex() < BI.LastUse) { 609 // There are interference-free uses at the end of the block. 610 // Find the first use that can get the live-out register. 611 SmallVectorImpl<SlotIndex>::const_iterator UI = 612 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 613 Intf.last().getBoundaryIndex()); 614 assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 615 SlotIndex Use = *UI; 616 assert(Use <= BI.LastUse && "Couldn't find last use"); 617 // Only attempt a split befroe the last split point. 618 if (Use.getBaseIndex() <= LastSplitPoint) { 619 DEBUG(dbgs() << ", free use at " << Use << ".\n"); 620 SlotIndex SegStart = SE->enterIntvBefore(Use); 621 assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 622 assert(SegStart < LastSplitPoint && "Impossible split point"); 623 SE->useIntv(SegStart, Stop); 624 continue; 625 } 626 } 627 628 // Interference is after the last use. 629 DEBUG(dbgs() << " after last use.\n"); 630 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 631 assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 632 } 633 634 // Now all defs leading to live bundles are handled, do everything else. 635 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 636 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 637 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 638 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 639 640 // Is the register live-in? 641 if (!BI.LiveIn || !RegIn) 642 continue; 643 644 // We have an incoming register. Check for interference. 645 SlotIndex Start, Stop; 646 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 647 Intf.moveToBlock(BI.MBB->getNumber()); 648 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 649 << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';' 650 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 651 << ')'); 652 653 // Check interference entering the block. 654 if (!Intf.hasInterference()) { 655 // Block is interference-free. 656 DEBUG(dbgs() << ", no interference"); 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 (Intf.first().getBaseIndex() > BI.FirstUse) { 700 // There are interference-free uses at the beginning of the block. 701 // Find the last use that can get the register. 702 SmallVectorImpl<SlotIndex>::const_iterator UI = 703 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 704 Intf.first().getBaseIndex()); 705 assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 706 SlotIndex Use = (--UI)->getBoundaryIndex(); 707 DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 708 SlotIndex SegEnd = SE->leaveIntvAfter(Use); 709 assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 710 SE->useIntv(Start, SegEnd); 711 continue; 712 } 713 714 // Interference is before the first use. 715 DEBUG(dbgs() << " before first use.\n"); 716 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 717 assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 718 } 719 720 // Handle live-through blocks. 721 ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks(); 722 for (unsigned i = 0; i != ThroughBlocks.size(); ++i) { 723 unsigned Number = ThroughBlocks[i]; 724 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 725 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 726 DEBUG(dbgs() << "Live through BB#" << Number << '\n'); 727 if (RegIn && RegOut) { 728 Intf.moveToBlock(Number); 729 if (!Intf.hasInterference()) { 730 SE->useIntv(Indexes->getMBBStartIdx(Number), 731 Indexes->getMBBEndIdx(Number)); 732 continue; 733 } 734 } 735 MachineBasicBlock *MBB = MF->getBlockNumbered(Number); 736 if (RegIn) 737 SE->leaveIntvAtTop(*MBB); 738 if (RegOut) 739 SE->enterIntvAtEnd(*MBB); 740 } 741 742 SE->closeIntv(); 743 744 // FIXME: Should we be more aggressive about splitting the stack region into 745 // per-block segments? The current approach allows the stack region to 746 // separate into connected components. Some components may be allocatable. 747 SE->finish(); 748 ++NumGlobalSplits; 749 750 if (VerifyEnabled) 751 MF->verify(this, "After splitting live range around region"); 752} 753 754unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 755 SmallVectorImpl<LiveInterval*> &NewVRegs) { 756 BitVector LiveBundles, BestBundles; 757 float BestCost = 0; 758 unsigned BestReg = 0; 759 760 Order.rewind(); 761 for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) { 762 if (GlobalCand.size() <= Cand) 763 GlobalCand.resize(Cand+1); 764 GlobalCand[Cand].PhysReg = PhysReg; 765 766 float Cost = calcSplitConstraints(PhysReg); 767 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 768 if (BestReg && Cost >= BestCost) { 769 DEBUG(dbgs() << " higher.\n"); 770 continue; 771 } 772 773 SpillPlacer->prepare(LiveBundles); 774 SpillPlacer->addConstraints(SplitConstraints); 775 SpillPlacer->finish(); 776 777 // No live bundles, defer to splitSingleBlocks(). 778 if (!LiveBundles.any()) { 779 DEBUG(dbgs() << " no bundles.\n"); 780 continue; 781 } 782 783 Cost += calcGlobalSplitCost(LiveBundles); 784 DEBUG({ 785 dbgs() << ", total = " << Cost << " with bundles"; 786 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 787 dbgs() << " EB#" << i; 788 dbgs() << ".\n"; 789 }); 790 if (!BestReg || Cost < BestCost) { 791 BestReg = PhysReg; 792 BestCost = 0.98f * Cost; // Prevent rounding effects. 793 BestBundles.swap(LiveBundles); 794 } 795 } 796 797 if (!BestReg) 798 return 0; 799 800 splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); 801 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region); 802 return 0; 803} 804 805 806//===----------------------------------------------------------------------===// 807// Local Splitting 808//===----------------------------------------------------------------------===// 809 810 811/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 812/// in order to use PhysReg between two entries in SA->UseSlots. 813/// 814/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 815/// 816void RAGreedy::calcGapWeights(unsigned PhysReg, 817 SmallVectorImpl<float> &GapWeight) { 818 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 819 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 820 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 821 const unsigned NumGaps = Uses.size()-1; 822 823 // Start and end points for the interference check. 824 SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 825 SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 826 827 GapWeight.assign(NumGaps, 0.0f); 828 829 // Add interference from each overlapping register. 830 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 831 if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 832 .checkInterference()) 833 continue; 834 835 // We know that VirtReg is a continuous interval from FirstUse to LastUse, 836 // so we don't need InterferenceQuery. 837 // 838 // Interference that overlaps an instruction is counted in both gaps 839 // surrounding the instruction. The exception is interference before 840 // StartIdx and after StopIdx. 841 // 842 LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 843 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 844 // Skip the gaps before IntI. 845 while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 846 if (++Gap == NumGaps) 847 break; 848 if (Gap == NumGaps) 849 break; 850 851 // Update the gaps covered by IntI. 852 const float weight = IntI.value()->weight; 853 for (; Gap != NumGaps; ++Gap) { 854 GapWeight[Gap] = std::max(GapWeight[Gap], weight); 855 if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 856 break; 857 } 858 if (Gap == NumGaps) 859 break; 860 } 861 } 862} 863 864/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 865/// before MI that has a slot index. If MI is the first mapped instruction in 866/// its block, return the block start index instead. 867/// 868SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 869 assert(MI && "Missing MachineInstr"); 870 const MachineBasicBlock *MBB = MI->getParent(); 871 MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 872 while (I != B) 873 if (!(--I)->isDebugValue() && !I->isCopy()) 874 return Indexes->getInstructionIndex(I); 875 return Indexes->getMBBStartIdx(MBB); 876} 877 878/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 879/// real non-copy instruction for each instruction in SA->UseSlots. 880/// 881void RAGreedy::calcPrevSlots() { 882 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 883 PrevSlot.clear(); 884 PrevSlot.reserve(Uses.size()); 885 for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 886 const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 887 PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 888 } 889} 890 891/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 892/// be beneficial to split before UseSlots[i]. 893/// 894/// 0 is always a valid split point 895unsigned RAGreedy::nextSplitPoint(unsigned i) { 896 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 897 const unsigned Size = Uses.size(); 898 assert(i != Size && "No split points after the end"); 899 // Allow split before i when Uses[i] is not adjacent to the previous use. 900 while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 901 ; 902 return i; 903} 904 905/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 906/// basic block. 907/// 908unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 909 SmallVectorImpl<LiveInterval*> &NewVRegs) { 910 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 911 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 912 913 // Note that it is possible to have an interval that is live-in or live-out 914 // while only covering a single block - A phi-def can use undef values from 915 // predecessors, and the block could be a single-block loop. 916 // We don't bother doing anything clever about such a case, we simply assume 917 // that the interval is continuous from FirstUse to LastUse. We should make 918 // sure that we don't do anything illegal to such an interval, though. 919 920 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 921 if (Uses.size() <= 2) 922 return 0; 923 const unsigned NumGaps = Uses.size()-1; 924 925 DEBUG({ 926 dbgs() << "tryLocalSplit: "; 927 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 928 dbgs() << ' ' << SA->UseSlots[i]; 929 dbgs() << '\n'; 930 }); 931 932 // For every use, find the previous mapped non-copy instruction. 933 // We use this to detect valid split points, and to estimate new interval 934 // sizes. 935 calcPrevSlots(); 936 937 unsigned BestBefore = NumGaps; 938 unsigned BestAfter = 0; 939 float BestDiff = 0; 940 941 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 942 SmallVector<float, 8> GapWeight; 943 944 Order.rewind(); 945 while (unsigned PhysReg = Order.next()) { 946 // Keep track of the largest spill weight that would need to be evicted in 947 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 948 calcGapWeights(PhysReg, GapWeight); 949 950 // Try to find the best sequence of gaps to close. 951 // The new spill weight must be larger than any gap interference. 952 953 // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 954 unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 955 956 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 957 // It is the spill weight that needs to be evicted. 958 float MaxGap = GapWeight[0]; 959 for (unsigned i = 1; i != SplitAfter; ++i) 960 MaxGap = std::max(MaxGap, GapWeight[i]); 961 962 for (;;) { 963 // Live before/after split? 964 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 965 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 966 967 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 968 << Uses[SplitBefore] << '-' << Uses[SplitAfter] 969 << " i=" << MaxGap); 970 971 // Stop before the interval gets so big we wouldn't be making progress. 972 if (!LiveBefore && !LiveAfter) { 973 DEBUG(dbgs() << " all\n"); 974 break; 975 } 976 // Should the interval be extended or shrunk? 977 bool Shrink = true; 978 if (MaxGap < HUGE_VALF) { 979 // Estimate the new spill weight. 980 // 981 // Each instruction reads and writes the register, except the first 982 // instr doesn't read when !FirstLive, and the last instr doesn't write 983 // when !LastLive. 984 // 985 // We will be inserting copies before and after, so the total number of 986 // reads and writes is 2 * EstUses. 987 // 988 const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 989 2*(LiveBefore + LiveAfter); 990 991 // Try to guess the size of the new interval. This should be trivial, 992 // but the slot index of an inserted copy can be a lot smaller than the 993 // instruction it is inserted before if there are many dead indexes 994 // between them. 995 // 996 // We measure the distance from the instruction before SplitBefore to 997 // get a conservative estimate. 998 // 999 // The final distance can still be different if inserting copies 1000 // triggers a slot index renumbering. 1001 // 1002 const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 1003 PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 1004 // Would this split be possible to allocate? 1005 // Never allocate all gaps, we wouldn't be making progress. 1006 float Diff = EstWeight - MaxGap; 1007 DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff); 1008 if (Diff > 0) { 1009 Shrink = false; 1010 if (Diff > BestDiff) { 1011 DEBUG(dbgs() << " (best)"); 1012 BestDiff = Diff; 1013 BestBefore = SplitBefore; 1014 BestAfter = SplitAfter; 1015 } 1016 } 1017 } 1018 1019 // Try to shrink. 1020 if (Shrink) { 1021 SplitBefore = nextSplitPoint(SplitBefore); 1022 if (SplitBefore < SplitAfter) { 1023 DEBUG(dbgs() << " shrink\n"); 1024 // Recompute the max when necessary. 1025 if (GapWeight[SplitBefore - 1] >= MaxGap) { 1026 MaxGap = GapWeight[SplitBefore]; 1027 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1028 MaxGap = std::max(MaxGap, GapWeight[i]); 1029 } 1030 continue; 1031 } 1032 MaxGap = 0; 1033 } 1034 1035 // Try to extend the interval. 1036 if (SplitAfter >= NumGaps) { 1037 DEBUG(dbgs() << " end\n"); 1038 break; 1039 } 1040 1041 DEBUG(dbgs() << " extend\n"); 1042 for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1043 SplitAfter != e; ++SplitAfter) 1044 MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1045 continue; 1046 } 1047 } 1048 1049 // Didn't find any candidates? 1050 if (BestBefore == NumGaps) 1051 return 0; 1052 1053 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1054 << '-' << Uses[BestAfter] << ", " << BestDiff 1055 << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1056 1057 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1058 SE->reset(LREdit); 1059 1060 SE->openIntv(); 1061 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1062 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1063 SE->useIntv(SegStart, SegStop); 1064 SE->closeIntv(); 1065 SE->finish(); 1066 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local); 1067 ++NumLocalSplits; 1068 1069 return 0; 1070} 1071 1072//===----------------------------------------------------------------------===// 1073// Live Range Splitting 1074//===----------------------------------------------------------------------===// 1075 1076/// trySplit - Try to split VirtReg or one of its interferences, making it 1077/// assignable. 1078/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1079unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1080 SmallVectorImpl<LiveInterval*>&NewVRegs) { 1081 // Local intervals are handled separately. 1082 if (LIS->intervalIsInOneMBB(VirtReg)) { 1083 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1084 SA->analyze(&VirtReg); 1085 return tryLocalSplit(VirtReg, Order, NewVRegs); 1086 } 1087 1088 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1089 1090 // Don't iterate global splitting. 1091 // Move straight to spilling if this range was produced by a global split. 1092 LiveRangeStage Stage = getStage(VirtReg); 1093 if (Stage >= RS_Block) 1094 return 0; 1095 1096 SA->analyze(&VirtReg); 1097 1098 // First try to split around a region spanning multiple blocks. 1099 if (Stage < RS_Region) { 1100 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1101 if (PhysReg || !NewVRegs.empty()) 1102 return PhysReg; 1103 } 1104 1105 // Then isolate blocks with multiple uses. 1106 if (Stage < RS_Block) { 1107 SplitAnalysis::BlockPtrSet Blocks; 1108 if (SA->getMultiUseBlocks(Blocks)) { 1109 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1110 SE->reset(LREdit); 1111 SE->splitSingleBlocks(Blocks); 1112 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block); 1113 if (VerifyEnabled) 1114 MF->verify(this, "After splitting live range around basic blocks"); 1115 } 1116 } 1117 1118 // Don't assign any physregs. 1119 return 0; 1120} 1121 1122 1123//===----------------------------------------------------------------------===// 1124// Main Entry Point 1125//===----------------------------------------------------------------------===// 1126 1127unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1128 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1129 // First try assigning a free register. 1130 AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 1131 while (unsigned PhysReg = Order.next()) { 1132 if (!checkPhysRegInterference(VirtReg, PhysReg)) 1133 return PhysReg; 1134 } 1135 1136 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1137 return PhysReg; 1138 1139 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1140 1141 // The first time we see a live range, don't try to split or spill. 1142 // Wait until the second time, when all smaller ranges have been allocated. 1143 // This gives a better picture of the interference to split around. 1144 LiveRangeStage Stage = getStage(VirtReg); 1145 if (Stage == RS_First) { 1146 LRStage[VirtReg.reg] = RS_Second; 1147 DEBUG(dbgs() << "wait for second round\n"); 1148 NewVRegs.push_back(&VirtReg); 1149 return 0; 1150 } 1151 1152 assert(Stage < RS_Spill && "Cannot allocate after spilling"); 1153 1154 // Try splitting VirtReg or interferences. 1155 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1156 if (PhysReg || !NewVRegs.empty()) 1157 return PhysReg; 1158 1159 // Finally spill VirtReg itself. 1160 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1161 LiveRangeEdit LRE(VirtReg, NewVRegs, this); 1162 spiller().spill(LRE); 1163 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill); 1164 1165 if (VerifyEnabled) 1166 MF->verify(this, "After spilling"); 1167 1168 // The live virtual register requesting allocation was spilled, so tell 1169 // the caller not to allocate anything during this round. 1170 return 0; 1171} 1172 1173bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1174 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1175 << "********** Function: " 1176 << ((Value*)mf.getFunction())->getName() << '\n'); 1177 1178 MF = &mf; 1179 if (VerifyEnabled) 1180 MF->verify(this, "Before greedy register allocator"); 1181 1182 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1183 Indexes = &getAnalysis<SlotIndexes>(); 1184 DomTree = &getAnalysis<MachineDominatorTree>(); 1185 ReservedRegs = TRI->getReservedRegs(*MF); 1186 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1187 Loops = &getAnalysis<MachineLoopInfo>(); 1188 LoopRanges = &getAnalysis<MachineLoopRanges>(); 1189 Bundles = &getAnalysis<EdgeBundles>(); 1190 SpillPlacer = &getAnalysis<SpillPlacement>(); 1191 1192 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1193 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 1194 LRStage.clear(); 1195 LRStage.resize(MRI->getNumVirtRegs()); 1196 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 1197 1198 allocatePhysRegs(); 1199 addMBBLiveIns(MF); 1200 LIS->addKillFlags(); 1201 1202 // Run rewriter 1203 { 1204 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1205 VRM->rewrite(Indexes); 1206 } 1207 1208 // Write out new DBG_VALUE instructions. 1209 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 1210 1211 // The pass output is in VirtRegMap. Release all the transient data. 1212 releaseMemory(); 1213 1214 return true; 1215} 1216