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