RegAllocGreedy.cpp revision 6d6132986d2ef14bbf9d76f5acbf2a0bace32d69
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 "llvm/CodeGen/Passes.h" 17#include "AllocationOrder.h" 18#include "InterferenceCache.h" 19#include "LiveDebugVariables.h" 20#include "RegAllocBase.h" 21#include "SpillPlacement.h" 22#include "Spiller.h" 23#include "SplitKit.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/Analysis/AliasAnalysis.h" 26#include "llvm/CodeGen/CalcSpillWeights.h" 27#include "llvm/CodeGen/EdgeBundles.h" 28#include "llvm/CodeGen/LiveIntervalAnalysis.h" 29#include "llvm/CodeGen/LiveRangeEdit.h" 30#include "llvm/CodeGen/LiveRegMatrix.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/MachineRegisterInfo.h" 36#include "llvm/CodeGen/RegAllocRegistry.h" 37#include "llvm/CodeGen/VirtRegMap.h" 38#include "llvm/PassAnalysisSupport.h" 39#include "llvm/Support/CommandLine.h" 40#include "llvm/Support/Debug.h" 41#include "llvm/Support/ErrorHandling.h" 42#include "llvm/Support/Timer.h" 43#include "llvm/Support/raw_ostream.h" 44#include "llvm/Target/TargetOptions.h" 45#include <queue> 46 47using namespace llvm; 48 49STATISTIC(NumGlobalSplits, "Number of split global live ranges"); 50STATISTIC(NumLocalSplits, "Number of split local live ranges"); 51STATISTIC(NumEvicted, "Number of interferences evicted"); 52 53static cl::opt<SplitEditor::ComplementSpillMode> 54SplitSpillMode("split-spill-mode", cl::Hidden, 55 cl::desc("Spill mode for splitting live ranges"), 56 cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), 57 clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), 58 clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"), 59 clEnumValEnd), 60 cl::init(SplitEditor::SM_Partition)); 61 62static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 63 createGreedyRegisterAllocator); 64 65namespace { 66class RAGreedy : public MachineFunctionPass, 67 public RegAllocBase, 68 private LiveRangeEdit::Delegate { 69 70 // context 71 MachineFunction *MF; 72 73 // analyses 74 SlotIndexes *Indexes; 75 MachineDominatorTree *DomTree; 76 MachineLoopInfo *Loops; 77 EdgeBundles *Bundles; 78 SpillPlacement *SpillPlacer; 79 LiveDebugVariables *DebugVars; 80 81 // state 82 std::auto_ptr<Spiller> SpillerInstance; 83 std::priority_queue<std::pair<unsigned, unsigned> > Queue; 84 unsigned NextCascade; 85 86 // Live ranges pass through a number of stages as we try to allocate them. 87 // Some of the stages may also create new live ranges: 88 // 89 // - Region splitting. 90 // - Per-block splitting. 91 // - Local splitting. 92 // - Spilling. 93 // 94 // Ranges produced by one of the stages skip the previous stages when they are 95 // dequeued. This improves performance because we can skip interference checks 96 // that are unlikely to give any results. It also guarantees that the live 97 // range splitting algorithm terminates, something that is otherwise hard to 98 // ensure. 99 enum LiveRangeStage { 100 /// Newly created live range that has never been queued. 101 RS_New, 102 103 /// Only attempt assignment and eviction. Then requeue as RS_Split. 104 RS_Assign, 105 106 /// Attempt live range splitting if assignment is impossible. 107 RS_Split, 108 109 /// Attempt more aggressive live range splitting that is guaranteed to make 110 /// progress. This is used for split products that may not be making 111 /// progress. 112 RS_Split2, 113 114 /// Live range will be spilled. No more splitting will be attempted. 115 RS_Spill, 116 117 /// There is nothing more we can do to this live range. Abort compilation 118 /// if it can't be assigned. 119 RS_Done 120 }; 121 122 static const char *const StageName[]; 123 124 // RegInfo - Keep additional information about each live range. 125 struct RegInfo { 126 LiveRangeStage Stage; 127 128 // Cascade - Eviction loop prevention. See canEvictInterference(). 129 unsigned Cascade; 130 131 RegInfo() : Stage(RS_New), Cascade(0) {} 132 }; 133 134 IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo; 135 136 LiveRangeStage getStage(const LiveInterval &VirtReg) const { 137 return ExtraRegInfo[VirtReg.reg].Stage; 138 } 139 140 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) { 141 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 142 ExtraRegInfo[VirtReg.reg].Stage = Stage; 143 } 144 145 template<typename Iterator> 146 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 147 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 148 for (;Begin != End; ++Begin) { 149 unsigned Reg = (*Begin)->reg; 150 if (ExtraRegInfo[Reg].Stage == RS_New) 151 ExtraRegInfo[Reg].Stage = NewStage; 152 } 153 } 154 155 /// Cost of evicting interference. 156 struct EvictionCost { 157 unsigned BrokenHints; ///< Total number of broken hints. 158 float MaxWeight; ///< Maximum spill weight evicted. 159 160 EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {} 161 162 bool operator<(const EvictionCost &O) const { 163 if (BrokenHints != O.BrokenHints) 164 return BrokenHints < O.BrokenHints; 165 return MaxWeight < O.MaxWeight; 166 } 167 }; 168 169 // splitting state. 170 std::auto_ptr<SplitAnalysis> SA; 171 std::auto_ptr<SplitEditor> SE; 172 173 /// Cached per-block interference maps 174 InterferenceCache IntfCache; 175 176 /// All basic blocks where the current register has uses. 177 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 178 179 /// Global live range splitting candidate info. 180 struct GlobalSplitCandidate { 181 // Register intended for assignment, or 0. 182 unsigned PhysReg; 183 184 // SplitKit interval index for this candidate. 185 unsigned IntvIdx; 186 187 // Interference for PhysReg. 188 InterferenceCache::Cursor Intf; 189 190 // Bundles where this candidate should be live. 191 BitVector LiveBundles; 192 SmallVector<unsigned, 8> ActiveBlocks; 193 194 void reset(InterferenceCache &Cache, unsigned Reg) { 195 PhysReg = Reg; 196 IntvIdx = 0; 197 Intf.setPhysReg(Cache, Reg); 198 LiveBundles.clear(); 199 ActiveBlocks.clear(); 200 } 201 202 // Set B[i] = C for every live bundle where B[i] was NoCand. 203 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 204 unsigned Count = 0; 205 for (int i = LiveBundles.find_first(); i >= 0; 206 i = LiveBundles.find_next(i)) 207 if (B[i] == NoCand) { 208 B[i] = C; 209 Count++; 210 } 211 return Count; 212 } 213 }; 214 215 /// Candidate info for for each PhysReg in AllocationOrder. 216 /// This vector never shrinks, but grows to the size of the largest register 217 /// class. 218 SmallVector<GlobalSplitCandidate, 32> GlobalCand; 219 220 enum { NoCand = ~0u }; 221 222 /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 223 /// NoCand which indicates the stack interval. 224 SmallVector<unsigned, 32> BundleCand; 225 226public: 227 RAGreedy(); 228 229 /// Return the pass name. 230 virtual const char* getPassName() const { 231 return "Greedy Register Allocator"; 232 } 233 234 /// RAGreedy analysis usage. 235 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 236 virtual void releaseMemory(); 237 virtual Spiller &spiller() { return *SpillerInstance; } 238 virtual void enqueue(LiveInterval *LI); 239 virtual LiveInterval *dequeue(); 240 virtual unsigned selectOrSplit(LiveInterval&, 241 SmallVectorImpl<LiveInterval*>&); 242 243 /// Perform register allocation. 244 virtual bool runOnMachineFunction(MachineFunction &mf); 245 246 static char ID; 247 248private: 249 bool LRE_CanEraseVirtReg(unsigned); 250 void LRE_WillShrinkVirtReg(unsigned); 251 void LRE_DidCloneVirtReg(unsigned, unsigned); 252 253 float calcSpillCost(); 254 bool addSplitConstraints(InterferenceCache::Cursor, float&); 255 void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 256 void growRegion(GlobalSplitCandidate &Cand); 257 float calcGlobalSplitCost(GlobalSplitCandidate&); 258 bool calcCompactRegion(GlobalSplitCandidate&); 259 void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>); 260 void calcGapWeights(unsigned, SmallVectorImpl<float>&); 261 bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); 262 bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); 263 void evictInterference(LiveInterval&, unsigned, 264 SmallVectorImpl<LiveInterval*>&); 265 266 unsigned tryAssign(LiveInterval&, AllocationOrder&, 267 SmallVectorImpl<LiveInterval*>&); 268 unsigned tryEvict(LiveInterval&, AllocationOrder&, 269 SmallVectorImpl<LiveInterval*>&, unsigned = ~0u); 270 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 271 SmallVectorImpl<LiveInterval*>&); 272 unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, 273 SmallVectorImpl<LiveInterval*>&); 274 unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&, 275 SmallVectorImpl<LiveInterval*>&); 276 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 277 SmallVectorImpl<LiveInterval*>&); 278 unsigned trySplit(LiveInterval&, AllocationOrder&, 279 SmallVectorImpl<LiveInterval*>&); 280}; 281} // end anonymous namespace 282 283char RAGreedy::ID = 0; 284 285#ifndef NDEBUG 286const char *const RAGreedy::StageName[] = { 287 "RS_New", 288 "RS_Assign", 289 "RS_Split", 290 "RS_Split2", 291 "RS_Spill", 292 "RS_Done" 293}; 294#endif 295 296// Hysteresis to use when comparing floats. 297// This helps stabilize decisions based on float comparisons. 298const float Hysteresis = 0.98f; 299 300 301FunctionPass* llvm::createGreedyRegisterAllocator() { 302 return new RAGreedy(); 303} 304 305RAGreedy::RAGreedy(): MachineFunctionPass(ID) { 306 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 307 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 308 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 309 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 310 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 311 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 312 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 313 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 314 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 315 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 316 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 317 initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry()); 318 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 319 initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 320} 321 322void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 323 AU.setPreservesCFG(); 324 AU.addRequired<AliasAnalysis>(); 325 AU.addPreserved<AliasAnalysis>(); 326 AU.addRequired<LiveIntervals>(); 327 AU.addPreserved<LiveIntervals>(); 328 AU.addRequired<SlotIndexes>(); 329 AU.addPreserved<SlotIndexes>(); 330 AU.addRequired<LiveDebugVariables>(); 331 AU.addPreserved<LiveDebugVariables>(); 332 AU.addRequired<LiveStacks>(); 333 AU.addPreserved<LiveStacks>(); 334 AU.addRequired<CalculateSpillWeights>(); 335 AU.addRequired<MachineDominatorTree>(); 336 AU.addPreserved<MachineDominatorTree>(); 337 AU.addRequired<MachineLoopInfo>(); 338 AU.addPreserved<MachineLoopInfo>(); 339 AU.addRequired<VirtRegMap>(); 340 AU.addPreserved<VirtRegMap>(); 341 AU.addRequired<LiveRegMatrix>(); 342 AU.addPreserved<LiveRegMatrix>(); 343 AU.addRequired<EdgeBundles>(); 344 AU.addRequired<SpillPlacement>(); 345 MachineFunctionPass::getAnalysisUsage(AU); 346} 347 348 349//===----------------------------------------------------------------------===// 350// LiveRangeEdit delegate methods 351//===----------------------------------------------------------------------===// 352 353bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 354 if (VRM->hasPhys(VirtReg)) { 355 Matrix->unassign(LIS->getInterval(VirtReg)); 356 return true; 357 } 358 // Unassigned virtreg is probably in the priority queue. 359 // RegAllocBase will erase it after dequeueing. 360 return false; 361} 362 363void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 364 if (!VRM->hasPhys(VirtReg)) 365 return; 366 367 // Register is assigned, put it back on the queue for reassignment. 368 LiveInterval &LI = LIS->getInterval(VirtReg); 369 Matrix->unassign(LI); 370 enqueue(&LI); 371} 372 373void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 374 // Cloning a register we haven't even heard about yet? Just ignore it. 375 if (!ExtraRegInfo.inBounds(Old)) 376 return; 377 378 // LRE may clone a virtual register because dead code elimination causes it to 379 // be split into connected components. The new components are much smaller 380 // than the original, so they should get a new chance at being assigned. 381 // same stage as the parent. 382 ExtraRegInfo[Old].Stage = RS_Assign; 383 ExtraRegInfo.grow(New); 384 ExtraRegInfo[New] = ExtraRegInfo[Old]; 385} 386 387void RAGreedy::releaseMemory() { 388 SpillerInstance.reset(0); 389 ExtraRegInfo.clear(); 390 GlobalCand.clear(); 391} 392 393void RAGreedy::enqueue(LiveInterval *LI) { 394 // Prioritize live ranges by size, assigning larger ranges first. 395 // The queue holds (size, reg) pairs. 396 const unsigned Size = LI->getSize(); 397 const unsigned Reg = LI->reg; 398 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 399 "Can only enqueue virtual registers"); 400 unsigned Prio; 401 402 ExtraRegInfo.grow(Reg); 403 if (ExtraRegInfo[Reg].Stage == RS_New) 404 ExtraRegInfo[Reg].Stage = RS_Assign; 405 406 if (ExtraRegInfo[Reg].Stage == RS_Split) { 407 // Unsplit ranges that couldn't be allocated immediately are deferred until 408 // everything else has been allocated. 409 Prio = Size; 410 } else { 411 // Everything is allocated in long->short order. Long ranges that don't fit 412 // should be spilled (or split) ASAP so they don't create interference. 413 Prio = (1u << 31) + Size; 414 415 // Boost ranges that have a physical register hint. 416 if (VRM->hasKnownPreference(Reg)) 417 Prio |= (1u << 30); 418 } 419 420 Queue.push(std::make_pair(Prio, ~Reg)); 421} 422 423LiveInterval *RAGreedy::dequeue() { 424 if (Queue.empty()) 425 return 0; 426 LiveInterval *LI = &LIS->getInterval(~Queue.top().second); 427 Queue.pop(); 428 return LI; 429} 430 431 432//===----------------------------------------------------------------------===// 433// Direct Assignment 434//===----------------------------------------------------------------------===// 435 436/// tryAssign - Try to assign VirtReg to an available register. 437unsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 438 AllocationOrder &Order, 439 SmallVectorImpl<LiveInterval*> &NewVRegs) { 440 Order.rewind(); 441 unsigned PhysReg; 442 while ((PhysReg = Order.next())) 443 if (!Matrix->checkInterference(VirtReg, PhysReg)) 444 break; 445 if (!PhysReg || Order.isHint()) 446 return PhysReg; 447 448 // PhysReg is available, but there may be a better choice. 449 450 // If we missed a simple hint, try to cheaply evict interference from the 451 // preferred register. 452 if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg)) 453 if (Order.isHint(Hint)) { 454 DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n'); 455 EvictionCost MaxCost(1); 456 if (canEvictInterference(VirtReg, Hint, true, MaxCost)) { 457 evictInterference(VirtReg, Hint, NewVRegs); 458 return Hint; 459 } 460 } 461 462 // Try to evict interference from a cheaper alternative. 463 unsigned Cost = TRI->getCostPerUse(PhysReg); 464 465 // Most registers have 0 additional cost. 466 if (!Cost) 467 return PhysReg; 468 469 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 470 << '\n'); 471 unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 472 return CheapReg ? CheapReg : PhysReg; 473} 474 475 476//===----------------------------------------------------------------------===// 477// Interference eviction 478//===----------------------------------------------------------------------===// 479 480/// shouldEvict - determine if A should evict the assigned live range B. The 481/// eviction policy defined by this function together with the allocation order 482/// defined by enqueue() decides which registers ultimately end up being split 483/// and spilled. 484/// 485/// Cascade numbers are used to prevent infinite loops if this function is a 486/// cyclic relation. 487/// 488/// @param A The live range to be assigned. 489/// @param IsHint True when A is about to be assigned to its preferred 490/// register. 491/// @param B The live range to be evicted. 492/// @param BreaksHint True when B is already assigned to its preferred register. 493bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint, 494 LiveInterval &B, bool BreaksHint) { 495 bool CanSplit = getStage(B) < RS_Spill; 496 497 // Be fairly aggressive about following hints as long as the evictee can be 498 // split. 499 if (CanSplit && IsHint && !BreaksHint) 500 return true; 501 502 return A.weight > B.weight; 503} 504 505/// canEvictInterference - Return true if all interferences between VirtReg and 506/// PhysReg can be evicted. When OnlyCheap is set, don't do anything 507/// 508/// @param VirtReg Live range that is about to be assigned. 509/// @param PhysReg Desired register for assignment. 510/// @param IsHint True when PhysReg is VirtReg's preferred register. 511/// @param MaxCost Only look for cheaper candidates and update with new cost 512/// when returning true. 513/// @returns True when interference can be evicted cheaper than MaxCost. 514bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 515 bool IsHint, EvictionCost &MaxCost) { 516 // It is only possible to evict virtual register interference. 517 if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) 518 return false; 519 520 // Find VirtReg's cascade number. This will be unassigned if VirtReg was never 521 // involved in an eviction before. If a cascade number was assigned, deny 522 // evicting anything with the same or a newer cascade number. This prevents 523 // infinite eviction loops. 524 // 525 // This works out so a register without a cascade number is allowed to evict 526 // anything, and it can be evicted by anything. 527 unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 528 if (!Cascade) 529 Cascade = NextCascade; 530 531 EvictionCost Cost; 532 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 533 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 534 // If there is 10 or more interferences, chances are one is heavier. 535 if (Q.collectInterferingVRegs(10) >= 10) 536 return false; 537 538 // Check if any interfering live range is heavier than MaxWeight. 539 for (unsigned i = Q.interferingVRegs().size(); i; --i) { 540 LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 541 assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) && 542 "Only expecting virtual register interference from query"); 543 // Never evict spill products. They cannot split or spill. 544 if (getStage(*Intf) == RS_Done) 545 return false; 546 // Once a live range becomes small enough, it is urgent that we find a 547 // register for it. This is indicated by an infinite spill weight. These 548 // urgent live ranges get to evict almost anything. 549 // 550 // Also allow urgent evictions of unspillable ranges from a strictly 551 // larger allocation order. 552 bool Urgent = !VirtReg.isSpillable() && 553 (Intf->isSpillable() || 554 RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) < 555 RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg))); 556 // Only evict older cascades or live ranges without a cascade. 557 unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade; 558 if (Cascade <= IntfCascade) { 559 if (!Urgent) 560 return false; 561 // We permit breaking cascades for urgent evictions. It should be the 562 // last resort, though, so make it really expensive. 563 Cost.BrokenHints += 10; 564 } 565 // Would this break a satisfied hint? 566 bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); 567 // Update eviction cost. 568 Cost.BrokenHints += BreaksHint; 569 Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); 570 // Abort if this would be too expensive. 571 if (!(Cost < MaxCost)) 572 return false; 573 // Finally, apply the eviction policy for non-urgent evictions. 574 if (!Urgent && !shouldEvict(VirtReg, IsHint, *Intf, BreaksHint)) 575 return false; 576 } 577 } 578 MaxCost = Cost; 579 return true; 580} 581 582/// evictInterference - Evict any interferring registers that prevent VirtReg 583/// from being assigned to Physreg. This assumes that canEvictInterference 584/// returned true. 585void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg, 586 SmallVectorImpl<LiveInterval*> &NewVRegs) { 587 // Make sure that VirtReg has a cascade number, and assign that cascade 588 // number to every evicted register. These live ranges than then only be 589 // evicted by a newer cascade, preventing infinite loops. 590 unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 591 if (!Cascade) 592 Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++; 593 594 DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI) 595 << " interference: Cascade " << Cascade << '\n'); 596 597 // Collect all interfering virtregs first. 598 SmallVector<LiveInterval*, 8> Intfs; 599 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 600 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 601 assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 602 ArrayRef<LiveInterval*> IVR = Q.interferingVRegs(); 603 Intfs.append(IVR.begin(), IVR.end()); 604 } 605 606 // Evict them second. This will invalidate the queries. 607 for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { 608 LiveInterval *Intf = Intfs[i]; 609 // The same VirtReg may be present in multiple RegUnits. Skip duplicates. 610 if (!VRM->hasPhys(Intf->reg)) 611 continue; 612 Matrix->unassign(*Intf); 613 assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || 614 VirtReg.isSpillable() < Intf->isSpillable()) && 615 "Cannot decrease cascade number, illegal eviction"); 616 ExtraRegInfo[Intf->reg].Cascade = Cascade; 617 ++NumEvicted; 618 NewVRegs.push_back(Intf); 619 } 620} 621 622/// tryEvict - Try to evict all interferences for a physreg. 623/// @param VirtReg Currently unassigned virtual register. 624/// @param Order Physregs to try. 625/// @return Physreg to assign VirtReg, or 0. 626unsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 627 AllocationOrder &Order, 628 SmallVectorImpl<LiveInterval*> &NewVRegs, 629 unsigned CostPerUseLimit) { 630 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 631 632 // Keep track of the cheapest interference seen so far. 633 EvictionCost BestCost(~0u); 634 unsigned BestPhys = 0; 635 unsigned OrderLimit = Order.getOrder().size(); 636 637 // When we are just looking for a reduced cost per use, don't break any 638 // hints, and only evict smaller spill weights. 639 if (CostPerUseLimit < ~0u) { 640 BestCost.BrokenHints = 0; 641 BestCost.MaxWeight = VirtReg.weight; 642 643 // Check of any registers in RC are below CostPerUseLimit. 644 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg); 645 unsigned MinCost = RegClassInfo.getMinCost(RC); 646 if (MinCost >= CostPerUseLimit) { 647 DEBUG(dbgs() << RC->getName() << " minimum cost = " << MinCost 648 << ", no cheaper registers to be found.\n"); 649 return 0; 650 } 651 652 // It is normal for register classes to have a long tail of registers with 653 // the same cost. We don't need to look at them if they're too expensive. 654 if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) { 655 OrderLimit = RegClassInfo.getLastCostChange(RC); 656 DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n"); 657 } 658 } 659 660 Order.rewind(); 661 while (unsigned PhysReg = Order.nextWithDups(OrderLimit)) { 662 if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 663 continue; 664 // The first use of a callee-saved register in a function has cost 1. 665 // Don't start using a CSR when the CostPerUseLimit is low. 666 if (CostPerUseLimit == 1) 667 if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg)) 668 if (!MRI->isPhysRegUsed(CSR)) { 669 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR " 670 << PrintReg(CSR, TRI) << '\n'); 671 continue; 672 } 673 674 if (!canEvictInterference(VirtReg, PhysReg, false, BestCost)) 675 continue; 676 677 // Best so far. 678 BestPhys = PhysReg; 679 680 // Stop if the hint can be used. 681 if (Order.isHint()) 682 break; 683 } 684 685 if (!BestPhys) 686 return 0; 687 688 evictInterference(VirtReg, BestPhys, NewVRegs); 689 return BestPhys; 690} 691 692 693//===----------------------------------------------------------------------===// 694// Region Splitting 695//===----------------------------------------------------------------------===// 696 697/// addSplitConstraints - Fill out the SplitConstraints vector based on the 698/// interference pattern in Physreg and its aliases. Add the constraints to 699/// SpillPlacement and return the static cost of this split in Cost, assuming 700/// that all preferences in SplitConstraints are met. 701/// Return false if there are no bundles with positive bias. 702bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 703 float &Cost) { 704 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 705 706 // Reset interference dependent info. 707 SplitConstraints.resize(UseBlocks.size()); 708 float StaticCost = 0; 709 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 710 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 711 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 712 713 BC.Number = BI.MBB->getNumber(); 714 Intf.moveToBlock(BC.Number); 715 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 716 BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 717 BC.ChangesValue = BI.FirstDef; 718 719 if (!Intf.hasInterference()) 720 continue; 721 722 // Number of spill code instructions to insert. 723 unsigned Ins = 0; 724 725 // Interference for the live-in value. 726 if (BI.LiveIn) { 727 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 728 BC.Entry = SpillPlacement::MustSpill, ++Ins; 729 else if (Intf.first() < BI.FirstInstr) 730 BC.Entry = SpillPlacement::PrefSpill, ++Ins; 731 else if (Intf.first() < BI.LastInstr) 732 ++Ins; 733 } 734 735 // Interference for the live-out value. 736 if (BI.LiveOut) { 737 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 738 BC.Exit = SpillPlacement::MustSpill, ++Ins; 739 else if (Intf.last() > BI.LastInstr) 740 BC.Exit = SpillPlacement::PrefSpill, ++Ins; 741 else if (Intf.last() > BI.FirstInstr) 742 ++Ins; 743 } 744 745 // Accumulate the total frequency of inserted spill code. 746 if (Ins) 747 StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 748 } 749 Cost = StaticCost; 750 751 // Add constraints for use-blocks. Note that these are the only constraints 752 // that may add a positive bias, it is downhill from here. 753 SpillPlacer->addConstraints(SplitConstraints); 754 return SpillPlacer->scanActiveBundles(); 755} 756 757 758/// addThroughConstraints - Add constraints and links to SpillPlacer from the 759/// live-through blocks in Blocks. 760void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 761 ArrayRef<unsigned> Blocks) { 762 const unsigned GroupSize = 8; 763 SpillPlacement::BlockConstraint BCS[GroupSize]; 764 unsigned TBS[GroupSize]; 765 unsigned B = 0, T = 0; 766 767 for (unsigned i = 0; i != Blocks.size(); ++i) { 768 unsigned Number = Blocks[i]; 769 Intf.moveToBlock(Number); 770 771 if (!Intf.hasInterference()) { 772 assert(T < GroupSize && "Array overflow"); 773 TBS[T] = Number; 774 if (++T == GroupSize) { 775 SpillPlacer->addLinks(makeArrayRef(TBS, T)); 776 T = 0; 777 } 778 continue; 779 } 780 781 assert(B < GroupSize && "Array overflow"); 782 BCS[B].Number = Number; 783 784 // Interference for the live-in value. 785 if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 786 BCS[B].Entry = SpillPlacement::MustSpill; 787 else 788 BCS[B].Entry = SpillPlacement::PrefSpill; 789 790 // Interference for the live-out value. 791 if (Intf.last() >= SA->getLastSplitPoint(Number)) 792 BCS[B].Exit = SpillPlacement::MustSpill; 793 else 794 BCS[B].Exit = SpillPlacement::PrefSpill; 795 796 if (++B == GroupSize) { 797 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 798 SpillPlacer->addConstraints(Array); 799 B = 0; 800 } 801 } 802 803 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 804 SpillPlacer->addConstraints(Array); 805 SpillPlacer->addLinks(makeArrayRef(TBS, T)); 806} 807 808void RAGreedy::growRegion(GlobalSplitCandidate &Cand) { 809 // Keep track of through blocks that have not been added to SpillPlacer. 810 BitVector Todo = SA->getThroughBlocks(); 811 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 812 unsigned AddedTo = 0; 813#ifndef NDEBUG 814 unsigned Visited = 0; 815#endif 816 817 for (;;) { 818 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 819 // Find new through blocks in the periphery of PrefRegBundles. 820 for (int i = 0, e = NewBundles.size(); i != e; ++i) { 821 unsigned Bundle = NewBundles[i]; 822 // Look at all blocks connected to Bundle in the full graph. 823 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 824 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 825 I != E; ++I) { 826 unsigned Block = *I; 827 if (!Todo.test(Block)) 828 continue; 829 Todo.reset(Block); 830 // This is a new through block. Add it to SpillPlacer later. 831 ActiveBlocks.push_back(Block); 832#ifndef NDEBUG 833 ++Visited; 834#endif 835 } 836 } 837 // Any new blocks to add? 838 if (ActiveBlocks.size() == AddedTo) 839 break; 840 841 // Compute through constraints from the interference, or assume that all 842 // through blocks prefer spilling when forming compact regions. 843 ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo); 844 if (Cand.PhysReg) 845 addThroughConstraints(Cand.Intf, NewBlocks); 846 else 847 // Provide a strong negative bias on through blocks to prevent unwanted 848 // liveness on loop backedges. 849 SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); 850 AddedTo = ActiveBlocks.size(); 851 852 // Perhaps iterating can enable more bundles? 853 SpillPlacer->iterate(); 854 } 855 DEBUG(dbgs() << ", v=" << Visited); 856} 857 858/// calcCompactRegion - Compute the set of edge bundles that should be live 859/// when splitting the current live range into compact regions. Compact 860/// regions can be computed without looking at interference. They are the 861/// regions formed by removing all the live-through blocks from the live range. 862/// 863/// Returns false if the current live range is already compact, or if the 864/// compact regions would form single block regions anyway. 865bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { 866 // Without any through blocks, the live range is already compact. 867 if (!SA->getNumThroughBlocks()) 868 return false; 869 870 // Compact regions don't correspond to any physreg. 871 Cand.reset(IntfCache, 0); 872 873 DEBUG(dbgs() << "Compact region bundles"); 874 875 // Use the spill placer to determine the live bundles. GrowRegion pretends 876 // that all the through blocks have interference when PhysReg is unset. 877 SpillPlacer->prepare(Cand.LiveBundles); 878 879 // The static split cost will be zero since Cand.Intf reports no interference. 880 float Cost; 881 if (!addSplitConstraints(Cand.Intf, Cost)) { 882 DEBUG(dbgs() << ", none.\n"); 883 return false; 884 } 885 886 growRegion(Cand); 887 SpillPlacer->finish(); 888 889 if (!Cand.LiveBundles.any()) { 890 DEBUG(dbgs() << ", none.\n"); 891 return false; 892 } 893 894 DEBUG({ 895 for (int i = Cand.LiveBundles.find_first(); i>=0; 896 i = Cand.LiveBundles.find_next(i)) 897 dbgs() << " EB#" << i; 898 dbgs() << ".\n"; 899 }); 900 return true; 901} 902 903/// calcSpillCost - Compute how expensive it would be to split the live range in 904/// SA around all use blocks instead of forming bundle regions. 905float RAGreedy::calcSpillCost() { 906 float Cost = 0; 907 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 908 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 909 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 910 unsigned Number = BI.MBB->getNumber(); 911 // We normally only need one spill instruction - a load or a store. 912 Cost += SpillPlacer->getBlockFrequency(Number); 913 914 // Unless the value is redefined in the block. 915 if (BI.LiveIn && BI.LiveOut && BI.FirstDef) 916 Cost += SpillPlacer->getBlockFrequency(Number); 917 } 918 return Cost; 919} 920 921/// calcGlobalSplitCost - Return the global split cost of following the split 922/// pattern in LiveBundles. This cost should be added to the local cost of the 923/// interference pattern in SplitConstraints. 924/// 925float RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { 926 float GlobalCost = 0; 927 const BitVector &LiveBundles = Cand.LiveBundles; 928 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 929 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 930 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 931 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 932 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 933 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 934 unsigned Ins = 0; 935 936 if (BI.LiveIn) 937 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 938 if (BI.LiveOut) 939 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 940 if (Ins) 941 GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 942 } 943 944 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 945 unsigned Number = Cand.ActiveBlocks[i]; 946 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 947 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 948 if (!RegIn && !RegOut) 949 continue; 950 if (RegIn && RegOut) { 951 // We need double spill code if this block has interference. 952 Cand.Intf.moveToBlock(Number); 953 if (Cand.Intf.hasInterference()) 954 GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 955 continue; 956 } 957 // live-in / stack-out or stack-in live-out. 958 GlobalCost += SpillPlacer->getBlockFrequency(Number); 959 } 960 return GlobalCost; 961} 962 963/// splitAroundRegion - Split the current live range around the regions 964/// determined by BundleCand and GlobalCand. 965/// 966/// Before calling this function, GlobalCand and BundleCand must be initialized 967/// so each bundle is assigned to a valid candidate, or NoCand for the 968/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor 969/// objects must be initialized for the current live range, and intervals 970/// created for the used candidates. 971/// 972/// @param LREdit The LiveRangeEdit object handling the current split. 973/// @param UsedCands List of used GlobalCand entries. Every BundleCand value 974/// must appear in this list. 975void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, 976 ArrayRef<unsigned> UsedCands) { 977 // These are the intervals created for new global ranges. We may create more 978 // intervals for local ranges. 979 const unsigned NumGlobalIntvs = LREdit.size(); 980 DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n"); 981 assert(NumGlobalIntvs && "No global intervals configured"); 982 983 // Isolate even single instructions when dealing with a proper sub-class. 984 // That guarantees register class inflation for the stack interval because it 985 // is all copies. 986 unsigned Reg = SA->getParent().reg; 987 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 988 989 // First handle all the blocks with uses. 990 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 991 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 992 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 993 unsigned Number = BI.MBB->getNumber(); 994 unsigned IntvIn = 0, IntvOut = 0; 995 SlotIndex IntfIn, IntfOut; 996 if (BI.LiveIn) { 997 unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 998 if (CandIn != NoCand) { 999 GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 1000 IntvIn = Cand.IntvIdx; 1001 Cand.Intf.moveToBlock(Number); 1002 IntfIn = Cand.Intf.first(); 1003 } 1004 } 1005 if (BI.LiveOut) { 1006 unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 1007 if (CandOut != NoCand) { 1008 GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 1009 IntvOut = Cand.IntvIdx; 1010 Cand.Intf.moveToBlock(Number); 1011 IntfOut = Cand.Intf.last(); 1012 } 1013 } 1014 1015 // Create separate intervals for isolated blocks with multiple uses. 1016 if (!IntvIn && !IntvOut) { 1017 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 1018 if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1019 SE->splitSingleBlock(BI); 1020 continue; 1021 } 1022 1023 if (IntvIn && IntvOut) 1024 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 1025 else if (IntvIn) 1026 SE->splitRegInBlock(BI, IntvIn, IntfIn); 1027 else 1028 SE->splitRegOutBlock(BI, IntvOut, IntfOut); 1029 } 1030 1031 // Handle live-through blocks. The relevant live-through blocks are stored in 1032 // the ActiveBlocks list with each candidate. We need to filter out 1033 // duplicates. 1034 BitVector Todo = SA->getThroughBlocks(); 1035 for (unsigned c = 0; c != UsedCands.size(); ++c) { 1036 ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks; 1037 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 1038 unsigned Number = Blocks[i]; 1039 if (!Todo.test(Number)) 1040 continue; 1041 Todo.reset(Number); 1042 1043 unsigned IntvIn = 0, IntvOut = 0; 1044 SlotIndex IntfIn, IntfOut; 1045 1046 unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 1047 if (CandIn != NoCand) { 1048 GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 1049 IntvIn = Cand.IntvIdx; 1050 Cand.Intf.moveToBlock(Number); 1051 IntfIn = Cand.Intf.first(); 1052 } 1053 1054 unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 1055 if (CandOut != NoCand) { 1056 GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 1057 IntvOut = Cand.IntvIdx; 1058 Cand.Intf.moveToBlock(Number); 1059 IntfOut = Cand.Intf.last(); 1060 } 1061 if (!IntvIn && !IntvOut) 1062 continue; 1063 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 1064 } 1065 } 1066 1067 ++NumGlobalSplits; 1068 1069 SmallVector<unsigned, 8> IntvMap; 1070 SE->finish(&IntvMap); 1071 DebugVars->splitRegister(Reg, LREdit.regs()); 1072 1073 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1074 unsigned OrigBlocks = SA->getNumLiveBlocks(); 1075 1076 // Sort out the new intervals created by splitting. We get four kinds: 1077 // - Remainder intervals should not be split again. 1078 // - Candidate intervals can be assigned to Cand.PhysReg. 1079 // - Block-local splits are candidates for local splitting. 1080 // - DCE leftovers should go back on the queue. 1081 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1082 LiveInterval &Reg = *LREdit.get(i); 1083 1084 // Ignore old intervals from DCE. 1085 if (getStage(Reg) != RS_New) 1086 continue; 1087 1088 // Remainder interval. Don't try splitting again, spill if it doesn't 1089 // allocate. 1090 if (IntvMap[i] == 0) { 1091 setStage(Reg, RS_Spill); 1092 continue; 1093 } 1094 1095 // Global intervals. Allow repeated splitting as long as the number of live 1096 // blocks is strictly decreasing. 1097 if (IntvMap[i] < NumGlobalIntvs) { 1098 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { 1099 DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 1100 << " blocks as original.\n"); 1101 // Don't allow repeated splitting as a safe guard against looping. 1102 setStage(Reg, RS_Split2); 1103 } 1104 continue; 1105 } 1106 1107 // Other intervals are treated as new. This includes local intervals created 1108 // for blocks with multiple uses, and anything created by DCE. 1109 } 1110 1111 if (VerifyEnabled) 1112 MF->verify(this, "After splitting live range around region"); 1113} 1114 1115unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1116 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1117 unsigned NumCands = 0; 1118 unsigned BestCand = NoCand; 1119 float BestCost; 1120 SmallVector<unsigned, 8> UsedCands; 1121 1122 // Check if we can split this live range around a compact region. 1123 bool HasCompact = calcCompactRegion(GlobalCand.front()); 1124 if (HasCompact) { 1125 // Yes, keep GlobalCand[0] as the compact region candidate. 1126 NumCands = 1; 1127 BestCost = HUGE_VALF; 1128 } else { 1129 // No benefit from the compact region, our fallback will be per-block 1130 // splitting. Make sure we find a solution that is cheaper than spilling. 1131 BestCost = Hysteresis * calcSpillCost(); 1132 DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 1133 } 1134 1135 Order.rewind(); 1136 while (unsigned PhysReg = Order.next()) { 1137 // Discard bad candidates before we run out of interference cache cursors. 1138 // This will only affect register classes with a lot of registers (>32). 1139 if (NumCands == IntfCache.getMaxCursors()) { 1140 unsigned WorstCount = ~0u; 1141 unsigned Worst = 0; 1142 for (unsigned i = 0; i != NumCands; ++i) { 1143 if (i == BestCand || !GlobalCand[i].PhysReg) 1144 continue; 1145 unsigned Count = GlobalCand[i].LiveBundles.count(); 1146 if (Count < WorstCount) 1147 Worst = i, WorstCount = Count; 1148 } 1149 --NumCands; 1150 GlobalCand[Worst] = GlobalCand[NumCands]; 1151 if (BestCand == NumCands) 1152 BestCand = Worst; 1153 } 1154 1155 if (GlobalCand.size() <= NumCands) 1156 GlobalCand.resize(NumCands+1); 1157 GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1158 Cand.reset(IntfCache, PhysReg); 1159 1160 SpillPlacer->prepare(Cand.LiveBundles); 1161 float Cost; 1162 if (!addSplitConstraints(Cand.Intf, Cost)) { 1163 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 1164 continue; 1165 } 1166 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1167 if (Cost >= BestCost) { 1168 DEBUG({ 1169 if (BestCand == NoCand) 1170 dbgs() << " worse than no bundles\n"; 1171 else 1172 dbgs() << " worse than " 1173 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1174 }); 1175 continue; 1176 } 1177 growRegion(Cand); 1178 1179 SpillPlacer->finish(); 1180 1181 // No live bundles, defer to splitSingleBlocks(). 1182 if (!Cand.LiveBundles.any()) { 1183 DEBUG(dbgs() << " no bundles.\n"); 1184 continue; 1185 } 1186 1187 Cost += calcGlobalSplitCost(Cand); 1188 DEBUG({ 1189 dbgs() << ", total = " << Cost << " with bundles"; 1190 for (int i = Cand.LiveBundles.find_first(); i>=0; 1191 i = Cand.LiveBundles.find_next(i)) 1192 dbgs() << " EB#" << i; 1193 dbgs() << ".\n"; 1194 }); 1195 if (Cost < BestCost) { 1196 BestCand = NumCands; 1197 BestCost = Hysteresis * Cost; // Prevent rounding effects. 1198 } 1199 ++NumCands; 1200 } 1201 1202 // No solutions found, fall back to single block splitting. 1203 if (!HasCompact && BestCand == NoCand) 1204 return 0; 1205 1206 // Prepare split editor. 1207 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1208 SE->reset(LREdit, SplitSpillMode); 1209 1210 // Assign all edge bundles to the preferred candidate, or NoCand. 1211 BundleCand.assign(Bundles->getNumBundles(), NoCand); 1212 1213 // Assign bundles for the best candidate region. 1214 if (BestCand != NoCand) { 1215 GlobalSplitCandidate &Cand = GlobalCand[BestCand]; 1216 if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { 1217 UsedCands.push_back(BestCand); 1218 Cand.IntvIdx = SE->openIntv(); 1219 DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in " 1220 << B << " bundles, intv " << Cand.IntvIdx << ".\n"); 1221 (void)B; 1222 } 1223 } 1224 1225 // Assign bundles for the compact region. 1226 if (HasCompact) { 1227 GlobalSplitCandidate &Cand = GlobalCand.front(); 1228 assert(!Cand.PhysReg && "Compact region has no physreg"); 1229 if (unsigned B = Cand.getBundles(BundleCand, 0)) { 1230 UsedCands.push_back(0); 1231 Cand.IntvIdx = SE->openIntv(); 1232 DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv " 1233 << Cand.IntvIdx << ".\n"); 1234 (void)B; 1235 } 1236 } 1237 1238 splitAroundRegion(LREdit, UsedCands); 1239 return 0; 1240} 1241 1242 1243//===----------------------------------------------------------------------===// 1244// Per-Block Splitting 1245//===----------------------------------------------------------------------===// 1246 1247/// tryBlockSplit - Split a global live range around every block with uses. This 1248/// creates a lot of local live ranges, that will be split by tryLocalSplit if 1249/// they don't allocate. 1250unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1251 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1252 assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); 1253 unsigned Reg = VirtReg.reg; 1254 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 1255 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1256 SE->reset(LREdit, SplitSpillMode); 1257 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1258 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1259 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1260 if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1261 SE->splitSingleBlock(BI); 1262 } 1263 // No blocks were split. 1264 if (LREdit.empty()) 1265 return 0; 1266 1267 // We did split for some blocks. 1268 SmallVector<unsigned, 8> IntvMap; 1269 SE->finish(&IntvMap); 1270 1271 // Tell LiveDebugVariables about the new ranges. 1272 DebugVars->splitRegister(Reg, LREdit.regs()); 1273 1274 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1275 1276 // Sort out the new intervals created by splitting. The remainder interval 1277 // goes straight to spilling, the new local ranges get to stay RS_New. 1278 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1279 LiveInterval &LI = *LREdit.get(i); 1280 if (getStage(LI) == RS_New && IntvMap[i] == 0) 1281 setStage(LI, RS_Spill); 1282 } 1283 1284 if (VerifyEnabled) 1285 MF->verify(this, "After splitting live range around basic blocks"); 1286 return 0; 1287} 1288 1289 1290//===----------------------------------------------------------------------===// 1291// Per-Instruction Splitting 1292//===----------------------------------------------------------------------===// 1293 1294/// tryInstructionSplit - Split a live range around individual instructions. 1295/// This is normally not worthwhile since the spiller is doing essentially the 1296/// same thing. However, when the live range is in a constrained register 1297/// class, it may help to insert copies such that parts of the live range can 1298/// be moved to a larger register class. 1299/// 1300/// This is similar to spilling to a larger register class. 1301unsigned 1302RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1303 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1304 // There is no point to this if there are no larger sub-classes. 1305 if (!RegClassInfo.isProperSubClass(MRI->getRegClass(VirtReg.reg))) 1306 return 0; 1307 1308 // Always enable split spill mode, since we're effectively spilling to a 1309 // register. 1310 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1311 SE->reset(LREdit, SplitEditor::SM_Size); 1312 1313 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1314 if (Uses.size() <= 1) 1315 return 0; 1316 1317 DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n"); 1318 1319 // Split around every non-copy instruction. 1320 for (unsigned i = 0; i != Uses.size(); ++i) { 1321 if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i])) 1322 if (MI->isFullCopy()) { 1323 DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI); 1324 continue; 1325 } 1326 SE->openIntv(); 1327 SlotIndex SegStart = SE->enterIntvBefore(Uses[i]); 1328 SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]); 1329 SE->useIntv(SegStart, SegStop); 1330 } 1331 1332 if (LREdit.empty()) { 1333 DEBUG(dbgs() << "All uses were copies.\n"); 1334 return 0; 1335 } 1336 1337 SmallVector<unsigned, 8> IntvMap; 1338 SE->finish(&IntvMap); 1339 DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1340 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1341 1342 // Assign all new registers to RS_Spill. This was the last chance. 1343 setStage(LREdit.begin(), LREdit.end(), RS_Spill); 1344 return 0; 1345} 1346 1347 1348//===----------------------------------------------------------------------===// 1349// Local Splitting 1350//===----------------------------------------------------------------------===// 1351 1352 1353/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1354/// in order to use PhysReg between two entries in SA->UseSlots. 1355/// 1356/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1357/// 1358void RAGreedy::calcGapWeights(unsigned PhysReg, 1359 SmallVectorImpl<float> &GapWeight) { 1360 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1361 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1362 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1363 const unsigned NumGaps = Uses.size()-1; 1364 1365 // Start and end points for the interference check. 1366 SlotIndex StartIdx = 1367 BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr; 1368 SlotIndex StopIdx = 1369 BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr; 1370 1371 GapWeight.assign(NumGaps, 0.0f); 1372 1373 // Add interference from each overlapping register. 1374 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1375 if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units) 1376 .checkInterference()) 1377 continue; 1378 1379 // We know that VirtReg is a continuous interval from FirstInstr to 1380 // LastInstr, so we don't need InterferenceQuery. 1381 // 1382 // Interference that overlaps an instruction is counted in both gaps 1383 // surrounding the instruction. The exception is interference before 1384 // StartIdx and after StopIdx. 1385 // 1386 LiveIntervalUnion::SegmentIter IntI = 1387 Matrix->getLiveUnions()[*Units] .find(StartIdx); 1388 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1389 // Skip the gaps before IntI. 1390 while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1391 if (++Gap == NumGaps) 1392 break; 1393 if (Gap == NumGaps) 1394 break; 1395 1396 // Update the gaps covered by IntI. 1397 const float weight = IntI.value()->weight; 1398 for (; Gap != NumGaps; ++Gap) { 1399 GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1400 if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1401 break; 1402 } 1403 if (Gap == NumGaps) 1404 break; 1405 } 1406 } 1407 1408 // Add fixed interference. 1409 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1410 const LiveInterval &LI = LIS->getRegUnit(*Units); 1411 LiveInterval::const_iterator I = LI.find(StartIdx); 1412 LiveInterval::const_iterator E = LI.end(); 1413 1414 // Same loop as above. Mark any overlapped gaps as HUGE_VALF. 1415 for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) { 1416 while (Uses[Gap+1].getBoundaryIndex() < I->start) 1417 if (++Gap == NumGaps) 1418 break; 1419 if (Gap == NumGaps) 1420 break; 1421 1422 for (; Gap != NumGaps; ++Gap) { 1423 GapWeight[Gap] = HUGE_VALF; 1424 if (Uses[Gap+1].getBaseIndex() >= I->end) 1425 break; 1426 } 1427 if (Gap == NumGaps) 1428 break; 1429 } 1430 } 1431} 1432 1433/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1434/// basic block. 1435/// 1436unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1437 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1438 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1439 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1440 1441 // Note that it is possible to have an interval that is live-in or live-out 1442 // while only covering a single block - A phi-def can use undef values from 1443 // predecessors, and the block could be a single-block loop. 1444 // We don't bother doing anything clever about such a case, we simply assume 1445 // that the interval is continuous from FirstInstr to LastInstr. We should 1446 // make sure that we don't do anything illegal to such an interval, though. 1447 1448 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1449 if (Uses.size() <= 2) 1450 return 0; 1451 const unsigned NumGaps = Uses.size()-1; 1452 1453 DEBUG({ 1454 dbgs() << "tryLocalSplit: "; 1455 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1456 dbgs() << ' ' << Uses[i]; 1457 dbgs() << '\n'; 1458 }); 1459 1460 // If VirtReg is live across any register mask operands, compute a list of 1461 // gaps with register masks. 1462 SmallVector<unsigned, 8> RegMaskGaps; 1463 if (Matrix->checkRegMaskInterference(VirtReg)) { 1464 // Get regmask slots for the whole block. 1465 ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber()); 1466 DEBUG(dbgs() << RMS.size() << " regmasks in block:"); 1467 // Constrain to VirtReg's live range. 1468 unsigned ri = std::lower_bound(RMS.begin(), RMS.end(), 1469 Uses.front().getRegSlot()) - RMS.begin(); 1470 unsigned re = RMS.size(); 1471 for (unsigned i = 0; i != NumGaps && ri != re; ++i) { 1472 // Look for Uses[i] <= RMS <= Uses[i+1]. 1473 assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i])); 1474 if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri])) 1475 continue; 1476 // Skip a regmask on the same instruction as the last use. It doesn't 1477 // overlap the live range. 1478 if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps) 1479 break; 1480 DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]); 1481 RegMaskGaps.push_back(i); 1482 // Advance ri to the next gap. A regmask on one of the uses counts in 1483 // both gaps. 1484 while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1])) 1485 ++ri; 1486 } 1487 DEBUG(dbgs() << '\n'); 1488 } 1489 1490 // Since we allow local split results to be split again, there is a risk of 1491 // creating infinite loops. It is tempting to require that the new live 1492 // ranges have less instructions than the original. That would guarantee 1493 // convergence, but it is too strict. A live range with 3 instructions can be 1494 // split 2+3 (including the COPY), and we want to allow that. 1495 // 1496 // Instead we use these rules: 1497 // 1498 // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the 1499 // noop split, of course). 1500 // 2. Require progress be made for ranges with getStage() == RS_Split2. All 1501 // the new ranges must have fewer instructions than before the split. 1502 // 3. New ranges with the same number of instructions are marked RS_Split2, 1503 // smaller ranges are marked RS_New. 1504 // 1505 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1506 // excessive splitting and infinite loops. 1507 // 1508 bool ProgressRequired = getStage(VirtReg) >= RS_Split2; 1509 1510 // Best split candidate. 1511 unsigned BestBefore = NumGaps; 1512 unsigned BestAfter = 0; 1513 float BestDiff = 0; 1514 1515 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1516 SmallVector<float, 8> GapWeight; 1517 1518 Order.rewind(); 1519 while (unsigned PhysReg = Order.next()) { 1520 // Keep track of the largest spill weight that would need to be evicted in 1521 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1522 calcGapWeights(PhysReg, GapWeight); 1523 1524 // Remove any gaps with regmask clobbers. 1525 if (Matrix->checkRegMaskInterference(VirtReg, PhysReg)) 1526 for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i) 1527 GapWeight[RegMaskGaps[i]] = HUGE_VALF; 1528 1529 // Try to find the best sequence of gaps to close. 1530 // The new spill weight must be larger than any gap interference. 1531 1532 // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1533 unsigned SplitBefore = 0, SplitAfter = 1; 1534 1535 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1536 // It is the spill weight that needs to be evicted. 1537 float MaxGap = GapWeight[0]; 1538 1539 for (;;) { 1540 // Live before/after split? 1541 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1542 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1543 1544 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1545 << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1546 << " i=" << MaxGap); 1547 1548 // Stop before the interval gets so big we wouldn't be making progress. 1549 if (!LiveBefore && !LiveAfter) { 1550 DEBUG(dbgs() << " all\n"); 1551 break; 1552 } 1553 // Should the interval be extended or shrunk? 1554 bool Shrink = true; 1555 1556 // How many gaps would the new range have? 1557 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1558 1559 // Legally, without causing looping? 1560 bool Legal = !ProgressRequired || NewGaps < NumGaps; 1561 1562 if (Legal && MaxGap < HUGE_VALF) { 1563 // Estimate the new spill weight. Each instruction reads or writes the 1564 // register. Conservatively assume there are no read-modify-write 1565 // instructions. 1566 // 1567 // Try to guess the size of the new interval. 1568 const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1569 Uses[SplitBefore].distance(Uses[SplitAfter]) + 1570 (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1571 // Would this split be possible to allocate? 1572 // Never allocate all gaps, we wouldn't be making progress. 1573 DEBUG(dbgs() << " w=" << EstWeight); 1574 if (EstWeight * Hysteresis >= MaxGap) { 1575 Shrink = false; 1576 float Diff = EstWeight - MaxGap; 1577 if (Diff > BestDiff) { 1578 DEBUG(dbgs() << " (best)"); 1579 BestDiff = Hysteresis * Diff; 1580 BestBefore = SplitBefore; 1581 BestAfter = SplitAfter; 1582 } 1583 } 1584 } 1585 1586 // Try to shrink. 1587 if (Shrink) { 1588 if (++SplitBefore < SplitAfter) { 1589 DEBUG(dbgs() << " shrink\n"); 1590 // Recompute the max when necessary. 1591 if (GapWeight[SplitBefore - 1] >= MaxGap) { 1592 MaxGap = GapWeight[SplitBefore]; 1593 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1594 MaxGap = std::max(MaxGap, GapWeight[i]); 1595 } 1596 continue; 1597 } 1598 MaxGap = 0; 1599 } 1600 1601 // Try to extend the interval. 1602 if (SplitAfter >= NumGaps) { 1603 DEBUG(dbgs() << " end\n"); 1604 break; 1605 } 1606 1607 DEBUG(dbgs() << " extend\n"); 1608 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1609 } 1610 } 1611 1612 // Didn't find any candidates? 1613 if (BestBefore == NumGaps) 1614 return 0; 1615 1616 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1617 << '-' << Uses[BestAfter] << ", " << BestDiff 1618 << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1619 1620 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1621 SE->reset(LREdit); 1622 1623 SE->openIntv(); 1624 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1625 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1626 SE->useIntv(SegStart, SegStop); 1627 SmallVector<unsigned, 8> IntvMap; 1628 SE->finish(&IntvMap); 1629 DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1630 1631 // If the new range has the same number of instructions as before, mark it as 1632 // RS_Split2 so the next split will be forced to make progress. Otherwise, 1633 // leave the new intervals as RS_New so they can compete. 1634 bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1635 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1636 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1637 if (NewGaps >= NumGaps) { 1638 DEBUG(dbgs() << "Tagging non-progress ranges: "); 1639 assert(!ProgressRequired && "Didn't make progress when it was required."); 1640 for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1641 if (IntvMap[i] == 1) { 1642 setStage(*LREdit.get(i), RS_Split2); 1643 DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg)); 1644 } 1645 DEBUG(dbgs() << '\n'); 1646 } 1647 ++NumLocalSplits; 1648 1649 return 0; 1650} 1651 1652//===----------------------------------------------------------------------===// 1653// Live Range Splitting 1654//===----------------------------------------------------------------------===// 1655 1656/// trySplit - Try to split VirtReg or one of its interferences, making it 1657/// assignable. 1658/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1659unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1660 SmallVectorImpl<LiveInterval*>&NewVRegs) { 1661 // Ranges must be Split2 or less. 1662 if (getStage(VirtReg) >= RS_Spill) 1663 return 0; 1664 1665 // Local intervals are handled separately. 1666 if (LIS->intervalIsInOneMBB(VirtReg)) { 1667 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1668 SA->analyze(&VirtReg); 1669 unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs); 1670 if (PhysReg || !NewVRegs.empty()) 1671 return PhysReg; 1672 return tryInstructionSplit(VirtReg, Order, NewVRegs); 1673 } 1674 1675 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1676 1677 SA->analyze(&VirtReg); 1678 1679 // FIXME: SplitAnalysis may repair broken live ranges coming from the 1680 // coalescer. That may cause the range to become allocatable which means that 1681 // tryRegionSplit won't be making progress. This check should be replaced with 1682 // an assertion when the coalescer is fixed. 1683 if (SA->didRepairRange()) { 1684 // VirtReg has changed, so all cached queries are invalid. 1685 Matrix->invalidateVirtRegs(); 1686 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1687 return PhysReg; 1688 } 1689 1690 // First try to split around a region spanning multiple blocks. RS_Split2 1691 // ranges already made dubious progress with region splitting, so they go 1692 // straight to single block splitting. 1693 if (getStage(VirtReg) < RS_Split2) { 1694 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1695 if (PhysReg || !NewVRegs.empty()) 1696 return PhysReg; 1697 } 1698 1699 // Then isolate blocks. 1700 return tryBlockSplit(VirtReg, Order, NewVRegs); 1701} 1702 1703 1704//===----------------------------------------------------------------------===// 1705// Main Entry Point 1706//===----------------------------------------------------------------------===// 1707 1708unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1709 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1710 // First try assigning a free register. 1711 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 1712 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1713 return PhysReg; 1714 1715 LiveRangeStage Stage = getStage(VirtReg); 1716 DEBUG(dbgs() << StageName[Stage] 1717 << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 1718 1719 // Try to evict a less worthy live range, but only for ranges from the primary 1720 // queue. The RS_Split ranges already failed to do this, and they should not 1721 // get a second chance until they have been split. 1722 if (Stage != RS_Split) 1723 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1724 return PhysReg; 1725 1726 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1727 1728 // The first time we see a live range, don't try to split or spill. 1729 // Wait until the second time, when all smaller ranges have been allocated. 1730 // This gives a better picture of the interference to split around. 1731 if (Stage < RS_Split) { 1732 setStage(VirtReg, RS_Split); 1733 DEBUG(dbgs() << "wait for second round\n"); 1734 NewVRegs.push_back(&VirtReg); 1735 return 0; 1736 } 1737 1738 // If we couldn't allocate a register from spilling, there is probably some 1739 // invalid inline assembly. The base class wil report it. 1740 if (Stage >= RS_Done || !VirtReg.isSpillable()) 1741 return ~0u; 1742 1743 // Try splitting VirtReg or interferences. 1744 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1745 if (PhysReg || !NewVRegs.empty()) 1746 return PhysReg; 1747 1748 // Finally spill VirtReg itself. 1749 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1750 LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1751 spiller().spill(LRE); 1752 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); 1753 1754 if (VerifyEnabled) 1755 MF->verify(this, "After spilling"); 1756 1757 // The live virtual register requesting allocation was spilled, so tell 1758 // the caller not to allocate anything during this round. 1759 return 0; 1760} 1761 1762bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1763 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1764 << "********** Function: " << mf.getName() << '\n'); 1765 1766 MF = &mf; 1767 if (VerifyEnabled) 1768 MF->verify(this, "Before greedy register allocator"); 1769 1770 RegAllocBase::init(getAnalysis<VirtRegMap>(), 1771 getAnalysis<LiveIntervals>(), 1772 getAnalysis<LiveRegMatrix>()); 1773 Indexes = &getAnalysis<SlotIndexes>(); 1774 DomTree = &getAnalysis<MachineDominatorTree>(); 1775 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1776 Loops = &getAnalysis<MachineLoopInfo>(); 1777 Bundles = &getAnalysis<EdgeBundles>(); 1778 SpillPlacer = &getAnalysis<SpillPlacement>(); 1779 DebugVars = &getAnalysis<LiveDebugVariables>(); 1780 1781 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1782 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 1783 ExtraRegInfo.clear(); 1784 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1785 NextCascade = 1; 1786 IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); 1787 GlobalCand.resize(32); // This will grow as needed. 1788 1789 allocatePhysRegs(); 1790 releaseMemory(); 1791 return true; 1792} 1793