RegAllocGreedy.cpp revision 2c0cbce763a258ac58590a8ca3c28ff722093fef
1//===-- RegAllocGreedy.cpp - greedy register allocator --------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the RAGreedy function pass for register allocation in 11// optimized builds. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "AllocationOrder.h" 17#include "InterferenceCache.h" 18#include "LiveDebugVariables.h" 19#include "LiveRangeEdit.h" 20#include "RegAllocBase.h" 21#include "Spiller.h" 22#include "SpillPlacement.h" 23#include "SplitKit.h" 24#include "VirtRegMap.h" 25#include "RegisterCoalescer.h" 26#include "llvm/ADT/Statistic.h" 27#include "llvm/Analysis/AliasAnalysis.h" 28#include "llvm/Function.h" 29#include "llvm/PassAnalysisSupport.h" 30#include "llvm/CodeGen/CalcSpillWeights.h" 31#include "llvm/CodeGen/EdgeBundles.h" 32#include "llvm/CodeGen/LiveIntervalAnalysis.h" 33#include "llvm/CodeGen/LiveStackAnalysis.h" 34#include "llvm/CodeGen/MachineDominators.h" 35#include "llvm/CodeGen/MachineFunctionPass.h" 36#include "llvm/CodeGen/MachineLoopInfo.h" 37#include "llvm/CodeGen/MachineLoopRanges.h" 38#include "llvm/CodeGen/MachineRegisterInfo.h" 39#include "llvm/CodeGen/Passes.h" 40#include "llvm/CodeGen/RegAllocRegistry.h" 41#include "llvm/Target/TargetOptions.h" 42#include "llvm/Support/Debug.h" 43#include "llvm/Support/ErrorHandling.h" 44#include "llvm/Support/raw_ostream.h" 45#include "llvm/Support/Timer.h" 46 47#include <queue> 48 49using namespace llvm; 50 51STATISTIC(NumGlobalSplits, "Number of split global live ranges"); 52STATISTIC(NumLocalSplits, "Number of split local live ranges"); 53STATISTIC(NumEvicted, "Number of interferences evicted"); 54 55static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 56 createGreedyRegisterAllocator); 57 58namespace { 59class RAGreedy : public MachineFunctionPass, 60 public RegAllocBase, 61 private LiveRangeEdit::Delegate { 62 63 // context 64 MachineFunction *MF; 65 66 // analyses 67 SlotIndexes *Indexes; 68 LiveStacks *LS; 69 MachineDominatorTree *DomTree; 70 MachineLoopInfo *Loops; 71 MachineLoopRanges *LoopRanges; 72 EdgeBundles *Bundles; 73 SpillPlacement *SpillPlacer; 74 LiveDebugVariables *DebugVars; 75 76 // state 77 std::auto_ptr<Spiller> SpillerInstance; 78 std::priority_queue<std::pair<unsigned, unsigned> > Queue; 79 80 // Live ranges pass through a number of stages as we try to allocate them. 81 // Some of the stages may also create new live ranges: 82 // 83 // - Region splitting. 84 // - Per-block splitting. 85 // - Local splitting. 86 // - Spilling. 87 // 88 // Ranges produced by one of the stages skip the previous stages when they are 89 // dequeued. This improves performance because we can skip interference checks 90 // that are unlikely to give any results. It also guarantees that the live 91 // range splitting algorithm terminates, something that is otherwise hard to 92 // ensure. 93 enum LiveRangeStage { 94 RS_New, ///< Never seen before. 95 RS_First, ///< First time in the queue. 96 RS_Second, ///< Second time in the queue. 97 RS_Global, ///< Produced by global splitting. 98 RS_Local, ///< Produced by local splitting. 99 RS_Spill ///< Produced by spilling. 100 }; 101 102 static const char *const StageName[]; 103 104 IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage; 105 106 LiveRangeStage getStage(const LiveInterval &VirtReg) const { 107 return LiveRangeStage(LRStage[VirtReg.reg]); 108 } 109 110 template<typename Iterator> 111 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 112 LRStage.resize(MRI->getNumVirtRegs()); 113 for (;Begin != End; ++Begin) { 114 unsigned Reg = (*Begin)->reg; 115 if (LRStage[Reg] == RS_New) 116 LRStage[Reg] = NewStage; 117 } 118 } 119 120 // Eviction. Sometimes an assigned live range can be evicted without 121 // conditions, but other times it must be split after being evicted to avoid 122 // infinite loops. 123 enum CanEvict { 124 CE_Never, ///< Can never evict. 125 CE_Always, ///< Can always evict. 126 CE_WithSplit ///< Can evict only if range is also split or spilled. 127 }; 128 129 // splitting state. 130 std::auto_ptr<SplitAnalysis> SA; 131 std::auto_ptr<SplitEditor> SE; 132 133 /// Cached per-block interference maps 134 InterferenceCache IntfCache; 135 136 /// All basic blocks where the current register has uses. 137 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 138 139 /// Global live range splitting candidate info. 140 struct GlobalSplitCandidate { 141 unsigned PhysReg; 142 BitVector LiveBundles; 143 SmallVector<unsigned, 8> ActiveBlocks; 144 145 void reset(unsigned Reg) { 146 PhysReg = Reg; 147 LiveBundles.clear(); 148 ActiveBlocks.clear(); 149 } 150 }; 151 152 /// Candidate info for for each PhysReg in AllocationOrder. 153 /// This vector never shrinks, but grows to the size of the largest register 154 /// class. 155 SmallVector<GlobalSplitCandidate, 32> GlobalCand; 156 157public: 158 RAGreedy(); 159 160 /// Return the pass name. 161 virtual const char* getPassName() const { 162 return "Greedy Register Allocator"; 163 } 164 165 /// RAGreedy analysis usage. 166 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 167 virtual void releaseMemory(); 168 virtual Spiller &spiller() { return *SpillerInstance; } 169 virtual void enqueue(LiveInterval *LI); 170 virtual LiveInterval *dequeue(); 171 virtual unsigned selectOrSplit(LiveInterval&, 172 SmallVectorImpl<LiveInterval*>&); 173 174 /// Perform register allocation. 175 virtual bool runOnMachineFunction(MachineFunction &mf); 176 177 static char ID; 178 179private: 180 void LRE_WillEraseInstruction(MachineInstr*); 181 bool LRE_CanEraseVirtReg(unsigned); 182 void LRE_WillShrinkVirtReg(unsigned); 183 void LRE_DidCloneVirtReg(unsigned, unsigned); 184 185 float calcSpillCost(); 186 bool addSplitConstraints(InterferenceCache::Cursor, float&); 187 void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 188 void growRegion(GlobalSplitCandidate &Cand, InterferenceCache::Cursor); 189 float calcGlobalSplitCost(GlobalSplitCandidate&, InterferenceCache::Cursor); 190 void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&, 191 SmallVectorImpl<LiveInterval*>&); 192 void calcGapWeights(unsigned, SmallVectorImpl<float>&); 193 CanEvict canEvict(LiveInterval &A, LiveInterval &B); 194 bool canEvictInterference(LiveInterval&, unsigned, float&); 195 196 unsigned tryAssign(LiveInterval&, AllocationOrder&, 197 SmallVectorImpl<LiveInterval*>&); 198 unsigned tryEvict(LiveInterval&, AllocationOrder&, 199 SmallVectorImpl<LiveInterval*>&, unsigned = ~0u); 200 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 201 SmallVectorImpl<LiveInterval*>&); 202 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 203 SmallVectorImpl<LiveInterval*>&); 204 unsigned trySplit(LiveInterval&, AllocationOrder&, 205 SmallVectorImpl<LiveInterval*>&); 206}; 207} // end anonymous namespace 208 209char RAGreedy::ID = 0; 210 211#ifndef NDEBUG 212const char *const RAGreedy::StageName[] = { 213 "RS_New", 214 "RS_First", 215 "RS_Second", 216 "RS_Global", 217 "RS_Local", 218 "RS_Spill" 219}; 220#endif 221 222// Hysteresis to use when comparing floats. 223// This helps stabilize decisions based on float comparisons. 224const float Hysteresis = 0.98f; 225 226 227FunctionPass* llvm::createGreedyRegisterAllocator() { 228 return new RAGreedy(); 229} 230 231RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) { 232 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 233 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 234 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 235 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 236 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 237 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 238 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 239 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 240 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 241 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 242 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 243 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 244 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 245 initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 246} 247 248void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 249 AU.setPreservesCFG(); 250 AU.addRequired<AliasAnalysis>(); 251 AU.addPreserved<AliasAnalysis>(); 252 AU.addRequired<LiveIntervals>(); 253 AU.addRequired<SlotIndexes>(); 254 AU.addPreserved<SlotIndexes>(); 255 AU.addRequired<LiveDebugVariables>(); 256 AU.addPreserved<LiveDebugVariables>(); 257 if (StrongPHIElim) 258 AU.addRequiredID(StrongPHIEliminationID); 259 AU.addRequiredTransitive<RegisterCoalescer>(); 260 AU.addRequired<CalculateSpillWeights>(); 261 AU.addRequired<LiveStacks>(); 262 AU.addPreserved<LiveStacks>(); 263 AU.addRequired<MachineDominatorTree>(); 264 AU.addPreserved<MachineDominatorTree>(); 265 AU.addRequired<MachineLoopInfo>(); 266 AU.addPreserved<MachineLoopInfo>(); 267 AU.addRequired<MachineLoopRanges>(); 268 AU.addPreserved<MachineLoopRanges>(); 269 AU.addRequired<VirtRegMap>(); 270 AU.addPreserved<VirtRegMap>(); 271 AU.addRequired<EdgeBundles>(); 272 AU.addRequired<SpillPlacement>(); 273 MachineFunctionPass::getAnalysisUsage(AU); 274} 275 276 277//===----------------------------------------------------------------------===// 278// LiveRangeEdit delegate methods 279//===----------------------------------------------------------------------===// 280 281void RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) { 282 // LRE itself will remove from SlotIndexes and parent basic block. 283 VRM->RemoveMachineInstrFromMaps(MI); 284} 285 286bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 287 if (unsigned PhysReg = VRM->getPhys(VirtReg)) { 288 unassign(LIS->getInterval(VirtReg), PhysReg); 289 return true; 290 } 291 // Unassigned virtreg is probably in the priority queue. 292 // RegAllocBase will erase it after dequeueing. 293 return false; 294} 295 296void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 297 unsigned PhysReg = VRM->getPhys(VirtReg); 298 if (!PhysReg) 299 return; 300 301 // Register is assigned, put it back on the queue for reassignment. 302 LiveInterval &LI = LIS->getInterval(VirtReg); 303 unassign(LI, PhysReg); 304 enqueue(&LI); 305} 306 307void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 308 // LRE may clone a virtual register because dead code elimination causes it to 309 // be split into connected components. Ensure that the new register gets the 310 // same stage as the parent. 311 LRStage.grow(New); 312 LRStage[New] = LRStage[Old]; 313} 314 315void RAGreedy::releaseMemory() { 316 SpillerInstance.reset(0); 317 LRStage.clear(); 318 GlobalCand.clear(); 319 RegAllocBase::releaseMemory(); 320} 321 322void RAGreedy::enqueue(LiveInterval *LI) { 323 // Prioritize live ranges by size, assigning larger ranges first. 324 // The queue holds (size, reg) pairs. 325 const unsigned Size = LI->getSize(); 326 const unsigned Reg = LI->reg; 327 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 328 "Can only enqueue virtual registers"); 329 unsigned Prio; 330 331 LRStage.grow(Reg); 332 if (LRStage[Reg] == RS_New) 333 LRStage[Reg] = RS_First; 334 335 if (LRStage[Reg] == RS_Second) 336 // Unsplit ranges that couldn't be allocated immediately are deferred until 337 // everything else has been allocated. Long ranges are allocated last so 338 // they are split against realistic interference. 339 Prio = (1u << 31) - Size; 340 else { 341 // Everything else is allocated in long->short order. Long ranges that don't 342 // fit should be spilled ASAP so they don't create interference. 343 Prio = (1u << 31) + Size; 344 345 // Boost ranges that have a physical register hint. 346 if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 347 Prio |= (1u << 30); 348 } 349 350 Queue.push(std::make_pair(Prio, Reg)); 351} 352 353LiveInterval *RAGreedy::dequeue() { 354 if (Queue.empty()) 355 return 0; 356 LiveInterval *LI = &LIS->getInterval(Queue.top().second); 357 Queue.pop(); 358 return LI; 359} 360 361 362//===----------------------------------------------------------------------===// 363// Direct Assignment 364//===----------------------------------------------------------------------===// 365 366/// tryAssign - Try to assign VirtReg to an available register. 367unsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 368 AllocationOrder &Order, 369 SmallVectorImpl<LiveInterval*> &NewVRegs) { 370 Order.rewind(); 371 unsigned PhysReg; 372 while ((PhysReg = Order.next())) 373 if (!checkPhysRegInterference(VirtReg, PhysReg)) 374 break; 375 if (!PhysReg || Order.isHint(PhysReg)) 376 return PhysReg; 377 378 // PhysReg is available. Try to evict interference from a cheaper alternative. 379 unsigned Cost = TRI->getCostPerUse(PhysReg); 380 381 // Most registers have 0 additional cost. 382 if (!Cost) 383 return PhysReg; 384 385 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 386 << '\n'); 387 unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 388 return CheapReg ? CheapReg : PhysReg; 389} 390 391 392//===----------------------------------------------------------------------===// 393// Interference eviction 394//===----------------------------------------------------------------------===// 395 396/// canEvict - determine if A can evict the assigned live range B. The eviction 397/// policy defined by this function together with the allocation order defined 398/// by enqueue() decides which registers ultimately end up being split and 399/// spilled. 400/// 401/// This function must define a non-circular relation when it returns CE_Always, 402/// otherwise infinite eviction loops are possible. When evicting a <= RS_Second 403/// range, it is possible to return CE_WithSplit which forces the evicted 404/// register to be split or spilled before it can evict anything again. That 405/// guarantees progress. 406RAGreedy::CanEvict RAGreedy::canEvict(LiveInterval &A, LiveInterval &B) { 407 return A.weight > B.weight ? CE_Always : CE_Never; 408} 409 410/// canEvict - Return true if all interferences between VirtReg and PhysReg can 411/// be evicted. 412/// Return false if any interference is heavier than MaxWeight. 413/// On return, set MaxWeight to the maximal spill weight of an interference. 414bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 415 float &MaxWeight) { 416 float Weight = 0; 417 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 418 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 419 // If there is 10 or more interferences, chances are one is heavier. 420 if (Q.collectInterferingVRegs(10, MaxWeight) >= 10) 421 return false; 422 423 // Check if any interfering live range is heavier than MaxWeight. 424 for (unsigned i = Q.interferingVRegs().size(); i; --i) { 425 LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 426 if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 427 return false; 428 if (Intf->weight >= MaxWeight) 429 return false; 430 switch (canEvict(VirtReg, *Intf)) { 431 case CE_Always: 432 break; 433 case CE_Never: 434 return false; 435 case CE_WithSplit: 436 if (getStage(*Intf) > RS_Second) 437 return false; 438 break; 439 } 440 Weight = std::max(Weight, Intf->weight); 441 } 442 } 443 MaxWeight = Weight; 444 return true; 445} 446 447/// tryEvict - Try to evict all interferences for a physreg. 448/// @param VirtReg Currently unassigned virtual register. 449/// @param Order Physregs to try. 450/// @return Physreg to assign VirtReg, or 0. 451unsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 452 AllocationOrder &Order, 453 SmallVectorImpl<LiveInterval*> &NewVRegs, 454 unsigned CostPerUseLimit) { 455 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 456 457 // Keep track of the lightest single interference seen so far. 458 float BestWeight = HUGE_VALF; 459 unsigned BestPhys = 0; 460 461 Order.rewind(); 462 while (unsigned PhysReg = Order.next()) { 463 if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 464 continue; 465 // The first use of a register in a function has cost 1. 466 if (CostPerUseLimit == 1 && !MRI->isPhysRegUsed(PhysReg)) 467 continue; 468 469 float Weight = BestWeight; 470 if (!canEvictInterference(VirtReg, PhysReg, Weight)) 471 continue; 472 473 // This is an eviction candidate. 474 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = " 475 << Weight << '\n'); 476 if (BestPhys && Weight >= BestWeight) 477 continue; 478 479 // Best so far. 480 BestPhys = PhysReg; 481 BestWeight = Weight; 482 // Stop if the hint can be used. 483 if (Order.isHint(PhysReg)) 484 break; 485 } 486 487 if (!BestPhys) 488 return 0; 489 490 DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n"); 491 for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) { 492 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 493 assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 494 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 495 LiveInterval *Intf = Q.interferingVRegs()[i]; 496 unassign(*Intf, VRM->getPhys(Intf->reg)); 497 ++NumEvicted; 498 NewVRegs.push_back(Intf); 499 // Prevent looping by forcing the evicted ranges to be split before they 500 // can evict anything else. 501 if (getStage(*Intf) < RS_Second && 502 canEvict(VirtReg, *Intf) == CE_WithSplit) 503 LRStage[Intf->reg] = RS_Second; 504 } 505 } 506 return BestPhys; 507} 508 509 510//===----------------------------------------------------------------------===// 511// Region Splitting 512//===----------------------------------------------------------------------===// 513 514/// addSplitConstraints - Fill out the SplitConstraints vector based on the 515/// interference pattern in Physreg and its aliases. Add the constraints to 516/// SpillPlacement and return the static cost of this split in Cost, assuming 517/// that all preferences in SplitConstraints are met. 518/// Return false if there are no bundles with positive bias. 519bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 520 float &Cost) { 521 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 522 523 // Reset interference dependent info. 524 SplitConstraints.resize(UseBlocks.size()); 525 float StaticCost = 0; 526 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 527 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 528 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 529 530 BC.Number = BI.MBB->getNumber(); 531 Intf.moveToBlock(BC.Number); 532 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 533 BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 534 535 if (!Intf.hasInterference()) 536 continue; 537 538 // Number of spill code instructions to insert. 539 unsigned Ins = 0; 540 541 // Interference for the live-in value. 542 if (BI.LiveIn) { 543 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 544 BC.Entry = SpillPlacement::MustSpill, ++Ins; 545 else if (Intf.first() < BI.FirstUse) 546 BC.Entry = SpillPlacement::PrefSpill, ++Ins; 547 else if (Intf.first() < BI.LastUse) 548 ++Ins; 549 } 550 551 // Interference for the live-out value. 552 if (BI.LiveOut) { 553 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 554 BC.Exit = SpillPlacement::MustSpill, ++Ins; 555 else if (Intf.last() > BI.LastUse) 556 BC.Exit = SpillPlacement::PrefSpill, ++Ins; 557 else if (Intf.last() > BI.FirstUse) 558 ++Ins; 559 } 560 561 // Accumulate the total frequency of inserted spill code. 562 if (Ins) 563 StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 564 } 565 Cost = StaticCost; 566 567 // Add constraints for use-blocks. Note that these are the only constraints 568 // that may add a positive bias, it is downhill from here. 569 SpillPlacer->addConstraints(SplitConstraints); 570 return SpillPlacer->scanActiveBundles(); 571} 572 573 574/// addThroughConstraints - Add constraints and links to SpillPlacer from the 575/// live-through blocks in Blocks. 576void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 577 ArrayRef<unsigned> Blocks) { 578 const unsigned GroupSize = 8; 579 SpillPlacement::BlockConstraint BCS[GroupSize]; 580 unsigned TBS[GroupSize]; 581 unsigned B = 0, T = 0; 582 583 for (unsigned i = 0; i != Blocks.size(); ++i) { 584 unsigned Number = Blocks[i]; 585 Intf.moveToBlock(Number); 586 587 if (!Intf.hasInterference()) { 588 assert(T < GroupSize && "Array overflow"); 589 TBS[T] = Number; 590 if (++T == GroupSize) { 591 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 592 T = 0; 593 } 594 continue; 595 } 596 597 assert(B < GroupSize && "Array overflow"); 598 BCS[B].Number = Number; 599 600 // Interference for the live-in value. 601 if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 602 BCS[B].Entry = SpillPlacement::MustSpill; 603 else 604 BCS[B].Entry = SpillPlacement::PrefSpill; 605 606 // Interference for the live-out value. 607 if (Intf.last() >= SA->getLastSplitPoint(Number)) 608 BCS[B].Exit = SpillPlacement::MustSpill; 609 else 610 BCS[B].Exit = SpillPlacement::PrefSpill; 611 612 if (++B == GroupSize) { 613 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 614 SpillPlacer->addConstraints(Array); 615 B = 0; 616 } 617 } 618 619 ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 620 SpillPlacer->addConstraints(Array); 621 SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 622} 623 624void RAGreedy::growRegion(GlobalSplitCandidate &Cand, 625 InterferenceCache::Cursor Intf) { 626 // Keep track of through blocks that have not been added to SpillPlacer. 627 BitVector Todo = SA->getThroughBlocks(); 628 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 629 unsigned AddedTo = 0; 630#ifndef NDEBUG 631 unsigned Visited = 0; 632#endif 633 634 for (;;) { 635 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 636 if (NewBundles.empty()) 637 break; 638 // Find new through blocks in the periphery of PrefRegBundles. 639 for (int i = 0, e = NewBundles.size(); i != e; ++i) { 640 unsigned Bundle = NewBundles[i]; 641 // Look at all blocks connected to Bundle in the full graph. 642 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 643 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 644 I != E; ++I) { 645 unsigned Block = *I; 646 if (!Todo.test(Block)) 647 continue; 648 Todo.reset(Block); 649 // This is a new through block. Add it to SpillPlacer later. 650 ActiveBlocks.push_back(Block); 651#ifndef NDEBUG 652 ++Visited; 653#endif 654 } 655 } 656 // Any new blocks to add? 657 if (ActiveBlocks.size() > AddedTo) { 658 ArrayRef<unsigned> Add(&ActiveBlocks[AddedTo], 659 ActiveBlocks.size() - AddedTo); 660 addThroughConstraints(Intf, Add); 661 AddedTo = ActiveBlocks.size(); 662 } 663 // Perhaps iterating can enable more bundles? 664 SpillPlacer->iterate(); 665 } 666 DEBUG(dbgs() << ", v=" << Visited); 667} 668 669/// calcSpillCost - Compute how expensive it would be to split the live range in 670/// SA around all use blocks instead of forming bundle regions. 671float RAGreedy::calcSpillCost() { 672 float Cost = 0; 673 const LiveInterval &LI = SA->getParent(); 674 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 675 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 676 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 677 unsigned Number = BI.MBB->getNumber(); 678 // We normally only need one spill instruction - a load or a store. 679 Cost += SpillPlacer->getBlockFrequency(Number); 680 681 // Unless the value is redefined in the block. 682 if (BI.LiveIn && BI.LiveOut) { 683 SlotIndex Start, Stop; 684 tie(Start, Stop) = Indexes->getMBBRange(Number); 685 LiveInterval::const_iterator I = LI.find(Start); 686 assert(I != LI.end() && "Expected live-in value"); 687 // Is there a different live-out value? If so, we need an extra spill 688 // instruction. 689 if (I->end < Stop) 690 Cost += SpillPlacer->getBlockFrequency(Number); 691 } 692 } 693 return Cost; 694} 695 696/// calcGlobalSplitCost - Return the global split cost of following the split 697/// pattern in LiveBundles. This cost should be added to the local cost of the 698/// interference pattern in SplitConstraints. 699/// 700float RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand, 701 InterferenceCache::Cursor Intf) { 702 float GlobalCost = 0; 703 const BitVector &LiveBundles = Cand.LiveBundles; 704 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 705 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 706 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 707 SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 708 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 709 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 710 unsigned Ins = 0; 711 712 if (BI.LiveIn) 713 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 714 if (BI.LiveOut) 715 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 716 if (Ins) 717 GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 718 } 719 720 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 721 unsigned Number = Cand.ActiveBlocks[i]; 722 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 723 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 724 if (!RegIn && !RegOut) 725 continue; 726 if (RegIn && RegOut) { 727 // We need double spill code if this block has interference. 728 Intf.moveToBlock(Number); 729 if (Intf.hasInterference()) 730 GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 731 continue; 732 } 733 // live-in / stack-out or stack-in live-out. 734 GlobalCost += SpillPlacer->getBlockFrequency(Number); 735 } 736 return GlobalCost; 737} 738 739/// splitAroundRegion - Split VirtReg around the region determined by 740/// LiveBundles. Make an effort to avoid interference from PhysReg. 741/// 742/// The 'register' interval is going to contain as many uses as possible while 743/// avoiding interference. The 'stack' interval is the complement constructed by 744/// SplitEditor. It will contain the rest. 745/// 746void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, 747 GlobalSplitCandidate &Cand, 748 SmallVectorImpl<LiveInterval*> &NewVRegs) { 749 const BitVector &LiveBundles = Cand.LiveBundles; 750 751 DEBUG({ 752 dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI) 753 << " with bundles"; 754 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 755 dbgs() << " EB#" << i; 756 dbgs() << ".\n"; 757 }); 758 759 InterferenceCache::Cursor Intf(IntfCache, Cand.PhysReg); 760 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 761 SE->reset(LREdit); 762 763 // Create the main cross-block interval. 764 const unsigned MainIntv = SE->openIntv(); 765 766 // First add all defs that are live out of a block. 767 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 768 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 769 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 770 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 771 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 772 773 // Create separate intervals for isolated blocks with multiple uses. 774 if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) { 775 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 776 SE->splitSingleBlock(BI); 777 SE->selectIntv(MainIntv); 778 continue; 779 } 780 781 // Should the register be live out? 782 if (!BI.LiveOut || !RegOut) 783 continue; 784 785 SlotIndex Start, Stop; 786 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 787 Intf.moveToBlock(BI.MBB->getNumber()); 788 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 789 << Bundles->getBundle(BI.MBB->getNumber(), 1) 790 << " [" << Start << ';' 791 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 792 << ") intf [" << Intf.first() << ';' << Intf.last() << ')'); 793 794 // The interference interval should either be invalid or overlap MBB. 795 assert((!Intf.hasInterference() || Intf.first() < Stop) 796 && "Bad interference"); 797 assert((!Intf.hasInterference() || Intf.last() > Start) 798 && "Bad interference"); 799 800 // Check interference leaving the block. 801 if (!Intf.hasInterference()) { 802 // Block is interference-free. 803 DEBUG(dbgs() << ", no interference"); 804 if (!BI.LiveThrough) { 805 DEBUG(dbgs() << ", not live-through.\n"); 806 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 807 continue; 808 } 809 if (!RegIn) { 810 // Block is live-through, but entry bundle is on the stack. 811 // Reload just before the first use. 812 DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 813 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 814 continue; 815 } 816 DEBUG(dbgs() << ", live-through.\n"); 817 continue; 818 } 819 820 // Block has interference. 821 DEBUG(dbgs() << ", interference to " << Intf.last()); 822 823 if (!BI.LiveThrough && Intf.last() <= BI.FirstUse) { 824 // The interference doesn't reach the outgoing segment. 825 DEBUG(dbgs() << " doesn't affect def from " << BI.FirstUse << '\n'); 826 SE->useIntv(BI.FirstUse, Stop); 827 continue; 828 } 829 830 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 831 if (Intf.last().getBoundaryIndex() < BI.LastUse) { 832 // There are interference-free uses at the end of the block. 833 // Find the first use that can get the live-out register. 834 SmallVectorImpl<SlotIndex>::const_iterator UI = 835 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 836 Intf.last().getBoundaryIndex()); 837 assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 838 SlotIndex Use = *UI; 839 assert(Use <= BI.LastUse && "Couldn't find last use"); 840 // Only attempt a split befroe the last split point. 841 if (Use.getBaseIndex() <= LastSplitPoint) { 842 DEBUG(dbgs() << ", free use at " << Use << ".\n"); 843 SlotIndex SegStart = SE->enterIntvBefore(Use); 844 assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 845 assert(SegStart < LastSplitPoint && "Impossible split point"); 846 SE->useIntv(SegStart, Stop); 847 continue; 848 } 849 } 850 851 // Interference is after the last use. 852 DEBUG(dbgs() << " after last use.\n"); 853 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 854 assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 855 } 856 857 // Now all defs leading to live bundles are handled, do everything else. 858 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 859 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 860 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 861 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 862 863 // Is the register live-in? 864 if (!BI.LiveIn || !RegIn) 865 continue; 866 867 // We have an incoming register. Check for interference. 868 SlotIndex Start, Stop; 869 tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 870 Intf.moveToBlock(BI.MBB->getNumber()); 871 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 872 << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';' 873 << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 874 << ')'); 875 876 // Check interference entering the block. 877 if (!Intf.hasInterference()) { 878 // Block is interference-free. 879 DEBUG(dbgs() << ", no interference"); 880 if (!BI.LiveThrough) { 881 DEBUG(dbgs() << ", killed in block.\n"); 882 SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 883 continue; 884 } 885 if (!RegOut) { 886 SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 887 // Block is live-through, but exit bundle is on the stack. 888 // Spill immediately after the last use. 889 if (BI.LastUse < LastSplitPoint) { 890 DEBUG(dbgs() << ", uses, stack-out.\n"); 891 SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 892 continue; 893 } 894 // The last use is after the last split point, it is probably an 895 // indirect jump. 896 DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 897 << LastSplitPoint << ", stack-out.\n"); 898 SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint); 899 SE->useIntv(Start, SegEnd); 900 // Run a double interval from the split to the last use. 901 // This makes it possible to spill the complement without affecting the 902 // indirect branch. 903 SE->overlapIntv(SegEnd, BI.LastUse); 904 continue; 905 } 906 // Register is live-through. 907 DEBUG(dbgs() << ", uses, live-through.\n"); 908 SE->useIntv(Start, Stop); 909 continue; 910 } 911 912 // Block has interference. 913 DEBUG(dbgs() << ", interference from " << Intf.first()); 914 915 if (!BI.LiveThrough && Intf.first() >= BI.LastUse) { 916 // The interference doesn't reach the outgoing segment. 917 DEBUG(dbgs() << " doesn't affect kill at " << BI.LastUse << '\n'); 918 SE->useIntv(Start, BI.LastUse); 919 continue; 920 } 921 922 if (Intf.first().getBaseIndex() > BI.FirstUse) { 923 // There are interference-free uses at the beginning of the block. 924 // Find the last use that can get the register. 925 SmallVectorImpl<SlotIndex>::const_iterator UI = 926 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 927 Intf.first().getBaseIndex()); 928 assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 929 SlotIndex Use = (--UI)->getBoundaryIndex(); 930 DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 931 SlotIndex SegEnd = SE->leaveIntvAfter(Use); 932 assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 933 SE->useIntv(Start, SegEnd); 934 continue; 935 } 936 937 // Interference is before the first use. 938 DEBUG(dbgs() << " before first use.\n"); 939 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 940 assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 941 } 942 943 // Handle live-through blocks. 944 for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 945 unsigned Number = Cand.ActiveBlocks[i]; 946 bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 947 bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 948 DEBUG(dbgs() << "Live through BB#" << Number << '\n'); 949 if (RegIn && RegOut) { 950 Intf.moveToBlock(Number); 951 if (!Intf.hasInterference()) { 952 SE->useIntv(Indexes->getMBBStartIdx(Number), 953 Indexes->getMBBEndIdx(Number)); 954 continue; 955 } 956 } 957 MachineBasicBlock *MBB = MF->getBlockNumbered(Number); 958 if (RegIn) 959 SE->leaveIntvAtTop(*MBB); 960 if (RegOut) 961 SE->enterIntvAtEnd(*MBB); 962 } 963 964 ++NumGlobalSplits; 965 966 SmallVector<unsigned, 8> IntvMap; 967 SE->finish(&IntvMap); 968 DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 969 970 LRStage.resize(MRI->getNumVirtRegs()); 971 unsigned OrigBlocks = SA->getNumLiveBlocks(); 972 973 // Sort out the new intervals created by splitting. We get four kinds: 974 // - Remainder intervals should not be split again. 975 // - Candidate intervals can be assigned to Cand.PhysReg. 976 // - Block-local splits are candidates for local splitting. 977 // - DCE leftovers should go back on the queue. 978 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 979 unsigned Reg = LREdit.get(i)->reg; 980 981 // Ignore old intervals from DCE. 982 if (LRStage[Reg] != RS_New) 983 continue; 984 985 // Remainder interval. Don't try splitting again, spill if it doesn't 986 // allocate. 987 if (IntvMap[i] == 0) { 988 LRStage[Reg] = RS_Global; 989 continue; 990 } 991 992 // Main interval. Allow repeated splitting as long as the number of live 993 // blocks is strictly decreasing. 994 if (IntvMap[i] == MainIntv) { 995 if (SA->countLiveBlocks(LREdit.get(i)) >= OrigBlocks) { 996 DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 997 << " blocks as original.\n"); 998 // Don't allow repeated splitting as a safe guard against looping. 999 LRStage[Reg] = RS_Global; 1000 } 1001 continue; 1002 } 1003 1004 // Other intervals are treated as new. This includes local intervals created 1005 // for blocks with multiple uses, and anything created by DCE. 1006 } 1007 1008 if (VerifyEnabled) 1009 MF->verify(this, "After splitting live range around region"); 1010} 1011 1012unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1013 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1014 float BestCost = Hysteresis * calcSpillCost(); 1015 DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 1016 const unsigned NoCand = ~0u; 1017 unsigned BestCand = NoCand; 1018 1019 Order.rewind(); 1020 for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) { 1021 if (GlobalCand.size() <= Cand) 1022 GlobalCand.resize(Cand+1); 1023 GlobalCand[Cand].reset(PhysReg); 1024 1025 SpillPlacer->prepare(GlobalCand[Cand].LiveBundles); 1026 float Cost; 1027 InterferenceCache::Cursor Intf(IntfCache, PhysReg); 1028 if (!addSplitConstraints(Intf, Cost)) { 1029 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 1030 continue; 1031 } 1032 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1033 if (Cost >= BestCost) { 1034 DEBUG({ 1035 if (BestCand == NoCand) 1036 dbgs() << " worse than no bundles\n"; 1037 else 1038 dbgs() << " worse than " 1039 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1040 }); 1041 continue; 1042 } 1043 growRegion(GlobalCand[Cand], Intf); 1044 1045 SpillPlacer->finish(); 1046 1047 // No live bundles, defer to splitSingleBlocks(). 1048 if (!GlobalCand[Cand].LiveBundles.any()) { 1049 DEBUG(dbgs() << " no bundles.\n"); 1050 continue; 1051 } 1052 1053 Cost += calcGlobalSplitCost(GlobalCand[Cand], Intf); 1054 DEBUG({ 1055 dbgs() << ", total = " << Cost << " with bundles"; 1056 for (int i = GlobalCand[Cand].LiveBundles.find_first(); i>=0; 1057 i = GlobalCand[Cand].LiveBundles.find_next(i)) 1058 dbgs() << " EB#" << i; 1059 dbgs() << ".\n"; 1060 }); 1061 if (Cost < BestCost) { 1062 BestCand = Cand; 1063 BestCost = Hysteresis * Cost; // Prevent rounding effects. 1064 } 1065 } 1066 1067 if (BestCand == NoCand) 1068 return 0; 1069 1070 splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs); 1071 return 0; 1072} 1073 1074 1075//===----------------------------------------------------------------------===// 1076// Local Splitting 1077//===----------------------------------------------------------------------===// 1078 1079 1080/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1081/// in order to use PhysReg between two entries in SA->UseSlots. 1082/// 1083/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1084/// 1085void RAGreedy::calcGapWeights(unsigned PhysReg, 1086 SmallVectorImpl<float> &GapWeight) { 1087 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1088 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1089 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1090 const unsigned NumGaps = Uses.size()-1; 1091 1092 // Start and end points for the interference check. 1093 SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 1094 SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 1095 1096 GapWeight.assign(NumGaps, 0.0f); 1097 1098 // Add interference from each overlapping register. 1099 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1100 if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 1101 .checkInterference()) 1102 continue; 1103 1104 // We know that VirtReg is a continuous interval from FirstUse to LastUse, 1105 // so we don't need InterferenceQuery. 1106 // 1107 // Interference that overlaps an instruction is counted in both gaps 1108 // surrounding the instruction. The exception is interference before 1109 // StartIdx and after StopIdx. 1110 // 1111 LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 1112 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1113 // Skip the gaps before IntI. 1114 while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1115 if (++Gap == NumGaps) 1116 break; 1117 if (Gap == NumGaps) 1118 break; 1119 1120 // Update the gaps covered by IntI. 1121 const float weight = IntI.value()->weight; 1122 for (; Gap != NumGaps; ++Gap) { 1123 GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1124 if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1125 break; 1126 } 1127 if (Gap == NumGaps) 1128 break; 1129 } 1130 } 1131} 1132 1133/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1134/// basic block. 1135/// 1136unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1137 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1138 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1139 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1140 1141 // Note that it is possible to have an interval that is live-in or live-out 1142 // while only covering a single block - A phi-def can use undef values from 1143 // predecessors, and the block could be a single-block loop. 1144 // We don't bother doing anything clever about such a case, we simply assume 1145 // that the interval is continuous from FirstUse to LastUse. We should make 1146 // sure that we don't do anything illegal to such an interval, though. 1147 1148 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1149 if (Uses.size() <= 2) 1150 return 0; 1151 const unsigned NumGaps = Uses.size()-1; 1152 1153 DEBUG({ 1154 dbgs() << "tryLocalSplit: "; 1155 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1156 dbgs() << ' ' << SA->UseSlots[i]; 1157 dbgs() << '\n'; 1158 }); 1159 1160 // Since we allow local split results to be split again, there is a risk of 1161 // creating infinite loops. It is tempting to require that the new live 1162 // ranges have less instructions than the original. That would guarantee 1163 // convergence, but it is too strict. A live range with 3 instructions can be 1164 // split 2+3 (including the COPY), and we want to allow that. 1165 // 1166 // Instead we use these rules: 1167 // 1168 // 1. Allow any split for ranges with getStage() < RS_Local. (Except for the 1169 // noop split, of course). 1170 // 2. Require progress be made for ranges with getStage() >= RS_Local. All 1171 // the new ranges must have fewer instructions than before the split. 1172 // 3. New ranges with the same number of instructions are marked RS_Local, 1173 // smaller ranges are marked RS_New. 1174 // 1175 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1176 // excessive splitting and infinite loops. 1177 // 1178 bool ProgressRequired = getStage(VirtReg) >= RS_Local; 1179 1180 // Best split candidate. 1181 unsigned BestBefore = NumGaps; 1182 unsigned BestAfter = 0; 1183 float BestDiff = 0; 1184 1185 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1186 SmallVector<float, 8> GapWeight; 1187 1188 Order.rewind(); 1189 while (unsigned PhysReg = Order.next()) { 1190 // Keep track of the largest spill weight that would need to be evicted in 1191 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1192 calcGapWeights(PhysReg, GapWeight); 1193 1194 // Try to find the best sequence of gaps to close. 1195 // The new spill weight must be larger than any gap interference. 1196 1197 // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1198 unsigned SplitBefore = 0, SplitAfter = 1; 1199 1200 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1201 // It is the spill weight that needs to be evicted. 1202 float MaxGap = GapWeight[0]; 1203 1204 for (;;) { 1205 // Live before/after split? 1206 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1207 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1208 1209 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1210 << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1211 << " i=" << MaxGap); 1212 1213 // Stop before the interval gets so big we wouldn't be making progress. 1214 if (!LiveBefore && !LiveAfter) { 1215 DEBUG(dbgs() << " all\n"); 1216 break; 1217 } 1218 // Should the interval be extended or shrunk? 1219 bool Shrink = true; 1220 1221 // How many gaps would the new range have? 1222 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1223 1224 // Legally, without causing looping? 1225 bool Legal = !ProgressRequired || NewGaps < NumGaps; 1226 1227 if (Legal && MaxGap < HUGE_VALF) { 1228 // Estimate the new spill weight. Each instruction reads or writes the 1229 // register. Conservatively assume there are no read-modify-write 1230 // instructions. 1231 // 1232 // Try to guess the size of the new interval. 1233 const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1234 Uses[SplitBefore].distance(Uses[SplitAfter]) + 1235 (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1236 // Would this split be possible to allocate? 1237 // Never allocate all gaps, we wouldn't be making progress. 1238 DEBUG(dbgs() << " w=" << EstWeight); 1239 if (EstWeight * Hysteresis >= MaxGap) { 1240 Shrink = false; 1241 float Diff = EstWeight - MaxGap; 1242 if (Diff > BestDiff) { 1243 DEBUG(dbgs() << " (best)"); 1244 BestDiff = Hysteresis * Diff; 1245 BestBefore = SplitBefore; 1246 BestAfter = SplitAfter; 1247 } 1248 } 1249 } 1250 1251 // Try to shrink. 1252 if (Shrink) { 1253 if (++SplitBefore < SplitAfter) { 1254 DEBUG(dbgs() << " shrink\n"); 1255 // Recompute the max when necessary. 1256 if (GapWeight[SplitBefore - 1] >= MaxGap) { 1257 MaxGap = GapWeight[SplitBefore]; 1258 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1259 MaxGap = std::max(MaxGap, GapWeight[i]); 1260 } 1261 continue; 1262 } 1263 MaxGap = 0; 1264 } 1265 1266 // Try to extend the interval. 1267 if (SplitAfter >= NumGaps) { 1268 DEBUG(dbgs() << " end\n"); 1269 break; 1270 } 1271 1272 DEBUG(dbgs() << " extend\n"); 1273 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1274 } 1275 } 1276 1277 // Didn't find any candidates? 1278 if (BestBefore == NumGaps) 1279 return 0; 1280 1281 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1282 << '-' << Uses[BestAfter] << ", " << BestDiff 1283 << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1284 1285 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1286 SE->reset(LREdit); 1287 1288 SE->openIntv(); 1289 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1290 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1291 SE->useIntv(SegStart, SegStop); 1292 SmallVector<unsigned, 8> IntvMap; 1293 SE->finish(&IntvMap); 1294 DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1295 1296 // If the new range has the same number of instructions as before, mark it as 1297 // RS_Local so the next split will be forced to make progress. Otherwise, 1298 // leave the new intervals as RS_New so they can compete. 1299 bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1300 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1301 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1302 if (NewGaps >= NumGaps) { 1303 DEBUG(dbgs() << "Tagging non-progress ranges: "); 1304 assert(!ProgressRequired && "Didn't make progress when it was required."); 1305 LRStage.resize(MRI->getNumVirtRegs()); 1306 for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1307 if (IntvMap[i] == 1) { 1308 LRStage[LREdit.get(i)->reg] = RS_Local; 1309 DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg)); 1310 } 1311 DEBUG(dbgs() << '\n'); 1312 } 1313 ++NumLocalSplits; 1314 1315 return 0; 1316} 1317 1318//===----------------------------------------------------------------------===// 1319// Live Range Splitting 1320//===----------------------------------------------------------------------===// 1321 1322/// trySplit - Try to split VirtReg or one of its interferences, making it 1323/// assignable. 1324/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1325unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1326 SmallVectorImpl<LiveInterval*>&NewVRegs) { 1327 // Local intervals are handled separately. 1328 if (LIS->intervalIsInOneMBB(VirtReg)) { 1329 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1330 SA->analyze(&VirtReg); 1331 return tryLocalSplit(VirtReg, Order, NewVRegs); 1332 } 1333 1334 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1335 1336 // Don't iterate global splitting. 1337 // Move straight to spilling if this range was produced by a global split. 1338 if (getStage(VirtReg) >= RS_Global) 1339 return 0; 1340 1341 SA->analyze(&VirtReg); 1342 1343 // FIXME: SplitAnalysis may repair broken live ranges coming from the 1344 // coalescer. That may cause the range to become allocatable which means that 1345 // tryRegionSplit won't be making progress. This check should be replaced with 1346 // an assertion when the coalescer is fixed. 1347 if (SA->didRepairRange()) { 1348 // VirtReg has changed, so all cached queries are invalid. 1349 invalidateVirtRegs(); 1350 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1351 return PhysReg; 1352 } 1353 1354 // First try to split around a region spanning multiple blocks. 1355 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1356 if (PhysReg || !NewVRegs.empty()) 1357 return PhysReg; 1358 1359 // Then isolate blocks with multiple uses. 1360 SplitAnalysis::BlockPtrSet Blocks; 1361 if (SA->getMultiUseBlocks(Blocks)) { 1362 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1363 SE->reset(LREdit); 1364 SE->splitSingleBlocks(Blocks); 1365 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global); 1366 if (VerifyEnabled) 1367 MF->verify(this, "After splitting live range around basic blocks"); 1368 } 1369 1370 // Don't assign any physregs. 1371 return 0; 1372} 1373 1374 1375//===----------------------------------------------------------------------===// 1376// Main Entry Point 1377//===----------------------------------------------------------------------===// 1378 1379unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1380 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1381 // First try assigning a free register. 1382 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 1383 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1384 return PhysReg; 1385 1386 LiveRangeStage Stage = getStage(VirtReg); 1387 DEBUG(dbgs() << StageName[Stage] << '\n'); 1388 1389 // Try to evict a less worthy live range, but only for ranges from the primary 1390 // queue. The RS_Second ranges already failed to do this, and they should not 1391 // get a second chance until they have been split. 1392 if (Stage != RS_Second) 1393 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1394 return PhysReg; 1395 1396 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1397 1398 // The first time we see a live range, don't try to split or spill. 1399 // Wait until the second time, when all smaller ranges have been allocated. 1400 // This gives a better picture of the interference to split around. 1401 if (Stage == RS_First) { 1402 LRStage[VirtReg.reg] = RS_Second; 1403 DEBUG(dbgs() << "wait for second round\n"); 1404 NewVRegs.push_back(&VirtReg); 1405 return 0; 1406 } 1407 1408 // If we couldn't allocate a register from spilling, there is probably some 1409 // invalid inline assembly. The base class wil report it. 1410 if (Stage >= RS_Spill) 1411 return ~0u; 1412 1413 // Try splitting VirtReg or interferences. 1414 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1415 if (PhysReg || !NewVRegs.empty()) 1416 return PhysReg; 1417 1418 // Finally spill VirtReg itself. 1419 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1420 LiveRangeEdit LRE(VirtReg, NewVRegs, this); 1421 spiller().spill(LRE); 1422 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill); 1423 1424 if (VerifyEnabled) 1425 MF->verify(this, "After spilling"); 1426 1427 // The live virtual register requesting allocation was spilled, so tell 1428 // the caller not to allocate anything during this round. 1429 return 0; 1430} 1431 1432bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1433 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1434 << "********** Function: " 1435 << ((Value*)mf.getFunction())->getName() << '\n'); 1436 1437 MF = &mf; 1438 if (VerifyEnabled) 1439 MF->verify(this, "Before greedy register allocator"); 1440 1441 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1442 Indexes = &getAnalysis<SlotIndexes>(); 1443 DomTree = &getAnalysis<MachineDominatorTree>(); 1444 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1445 Loops = &getAnalysis<MachineLoopInfo>(); 1446 LoopRanges = &getAnalysis<MachineLoopRanges>(); 1447 Bundles = &getAnalysis<EdgeBundles>(); 1448 SpillPlacer = &getAnalysis<SpillPlacement>(); 1449 DebugVars = &getAnalysis<LiveDebugVariables>(); 1450 1451 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1452 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 1453 LRStage.clear(); 1454 LRStage.resize(MRI->getNumVirtRegs()); 1455 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 1456 1457 allocatePhysRegs(); 1458 addMBBLiveIns(MF); 1459 LIS->addKillFlags(); 1460 1461 // Run rewriter 1462 { 1463 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1464 VRM->rewrite(Indexes); 1465 } 1466 1467 // Write out new DBG_VALUE instructions. 1468 DebugVars->emitDebugValues(VRM); 1469 1470 // The pass output is in VirtRegMap. Release all the transient data. 1471 releaseMemory(); 1472 1473 return true; 1474} 1475