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