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