RegAllocGreedy.cpp revision 8b6a933498299773243a6b4e05513d6dc11e4d32
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 "LiveIntervalUnion.h" 18#include "LiveRangeEdit.h" 19#include "RegAllocBase.h" 20#include "Spiller.h" 21#include "SpillPlacement.h" 22#include "SplitKit.h" 23#include "VirtRegMap.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/Analysis/AliasAnalysis.h" 26#include "llvm/Function.h" 27#include "llvm/PassAnalysisSupport.h" 28#include "llvm/CodeGen/CalcSpillWeights.h" 29#include "llvm/CodeGen/EdgeBundles.h" 30#include "llvm/CodeGen/LiveIntervalAnalysis.h" 31#include "llvm/CodeGen/LiveStackAnalysis.h" 32#include "llvm/CodeGen/MachineDominators.h" 33#include "llvm/CodeGen/MachineFunctionPass.h" 34#include "llvm/CodeGen/MachineLoopInfo.h" 35#include "llvm/CodeGen/MachineLoopRanges.h" 36#include "llvm/CodeGen/MachineRegisterInfo.h" 37#include "llvm/CodeGen/Passes.h" 38#include "llvm/CodeGen/RegAllocRegistry.h" 39#include "llvm/CodeGen/RegisterCoalescer.h" 40#include "llvm/Target/TargetOptions.h" 41#include "llvm/Support/Debug.h" 42#include "llvm/Support/ErrorHandling.h" 43#include "llvm/Support/raw_ostream.h" 44#include "llvm/Support/Timer.h" 45 46#include <queue> 47 48using namespace llvm; 49 50STATISTIC(NumGlobalSplits, "Number of split global live ranges"); 51STATISTIC(NumLocalSplits, "Number of split local live ranges"); 52STATISTIC(NumReassigned, "Number of interferences reassigned"); 53STATISTIC(NumEvicted, "Number of interferences evicted"); 54 55static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 56 createGreedyRegisterAllocator); 57 58namespace { 59class RAGreedy : public MachineFunctionPass, public RegAllocBase { 60 // context 61 MachineFunction *MF; 62 BitVector ReservedRegs; 63 64 // analyses 65 SlotIndexes *Indexes; 66 LiveStacks *LS; 67 MachineDominatorTree *DomTree; 68 MachineLoopInfo *Loops; 69 MachineLoopRanges *LoopRanges; 70 EdgeBundles *Bundles; 71 SpillPlacement *SpillPlacer; 72 73 // state 74 std::auto_ptr<Spiller> SpillerInstance; 75 std::priority_queue<std::pair<unsigned, unsigned> > Queue; 76 77 // Live ranges pass through a number of stages as we try to allocate them. 78 // Some of the stages may also create new live ranges: 79 // 80 // - Region splitting. 81 // - Per-block splitting. 82 // - Local splitting. 83 // - Spilling. 84 // 85 // Ranges produced by one of the stages skip the previous stages when they are 86 // dequeued. This improves performance because we can skip interference checks 87 // that are unlikely to give any results. It also guarantees that the live 88 // range splitting algorithm terminates, something that is otherwise hard to 89 // ensure. 90 enum LiveRangeStage { 91 RS_Original, ///< Never seen before, never split. 92 RS_Second, ///< Second time in the queue. 93 RS_Region, ///< Produced by region splitting. 94 RS_Block, ///< Produced by per-block splitting. 95 RS_Local, ///< Produced by local splitting. 96 RS_Spill ///< Produced by spilling. 97 }; 98 99 IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage; 100 101 LiveRangeStage getStage(const LiveInterval &VirtReg) const { 102 return LiveRangeStage(LRStage[VirtReg.reg]); 103 } 104 105 template<typename Iterator> 106 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 107 LRStage.resize(MRI->getNumVirtRegs()); 108 for (;Begin != End; ++Begin) 109 LRStage[(*Begin)->reg] = NewStage; 110 } 111 112 // splitting state. 113 std::auto_ptr<SplitAnalysis> SA; 114 std::auto_ptr<SplitEditor> SE; 115 116 /// All basic blocks where the current register is live. 117 SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints; 118 119 typedef std::pair<SlotIndex, SlotIndex> IndexPair; 120 121 /// For every instruction in SA->UseSlots, store the previous non-copy 122 /// instruction. 123 SmallVector<SlotIndex, 8> PrevSlot; 124 125public: 126 RAGreedy(); 127 128 /// Return the pass name. 129 virtual const char* getPassName() const { 130 return "Greedy Register Allocator"; 131 } 132 133 /// RAGreedy analysis usage. 134 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 135 virtual void releaseMemory(); 136 virtual Spiller &spiller() { return *SpillerInstance; } 137 virtual void enqueue(LiveInterval *LI); 138 virtual LiveInterval *dequeue(); 139 virtual unsigned selectOrSplit(LiveInterval&, 140 SmallVectorImpl<LiveInterval*>&); 141 142 /// Perform register allocation. 143 virtual bool runOnMachineFunction(MachineFunction &mf); 144 145 static char ID; 146 147private: 148 bool checkUncachedInterference(LiveInterval&, unsigned); 149 LiveInterval *getSingleInterference(LiveInterval&, unsigned); 150 bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg); 151 void mapGlobalInterference(unsigned, SmallVectorImpl<IndexPair>&); 152 float calcInterferenceInfo(LiveInterval&, unsigned); 153 float calcGlobalSplitCost(const BitVector&); 154 void splitAroundRegion(LiveInterval&, unsigned, const BitVector&, 155 SmallVectorImpl<LiveInterval*>&); 156 void calcGapWeights(unsigned, SmallVectorImpl<float>&); 157 SlotIndex getPrevMappedIndex(const MachineInstr*); 158 void calcPrevSlots(); 159 unsigned nextSplitPoint(unsigned); 160 bool canEvictInterference(LiveInterval&, unsigned, float&); 161 162 unsigned tryReassign(LiveInterval&, AllocationOrder&, 163 SmallVectorImpl<LiveInterval*>&); 164 unsigned tryEvict(LiveInterval&, AllocationOrder&, 165 SmallVectorImpl<LiveInterval*>&); 166 unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 167 SmallVectorImpl<LiveInterval*>&); 168 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 169 SmallVectorImpl<LiveInterval*>&); 170 unsigned trySplit(LiveInterval&, AllocationOrder&, 171 SmallVectorImpl<LiveInterval*>&); 172}; 173} // end anonymous namespace 174 175char RAGreedy::ID = 0; 176 177FunctionPass* llvm::createGreedyRegisterAllocator() { 178 return new RAGreedy(); 179} 180 181RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_Original) { 182 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 183 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 184 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 185 initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 186 initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 187 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 188 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 189 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 190 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 191 initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 192 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 193 initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 194 initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 195} 196 197void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 198 AU.setPreservesCFG(); 199 AU.addRequired<AliasAnalysis>(); 200 AU.addPreserved<AliasAnalysis>(); 201 AU.addRequired<LiveIntervals>(); 202 AU.addRequired<SlotIndexes>(); 203 AU.addPreserved<SlotIndexes>(); 204 if (StrongPHIElim) 205 AU.addRequiredID(StrongPHIEliminationID); 206 AU.addRequiredTransitive<RegisterCoalescer>(); 207 AU.addRequired<CalculateSpillWeights>(); 208 AU.addRequired<LiveStacks>(); 209 AU.addPreserved<LiveStacks>(); 210 AU.addRequired<MachineDominatorTree>(); 211 AU.addPreserved<MachineDominatorTree>(); 212 AU.addRequired<MachineLoopInfo>(); 213 AU.addPreserved<MachineLoopInfo>(); 214 AU.addRequired<MachineLoopRanges>(); 215 AU.addPreserved<MachineLoopRanges>(); 216 AU.addRequired<VirtRegMap>(); 217 AU.addPreserved<VirtRegMap>(); 218 AU.addRequired<EdgeBundles>(); 219 AU.addRequired<SpillPlacement>(); 220 MachineFunctionPass::getAnalysisUsage(AU); 221} 222 223void RAGreedy::releaseMemory() { 224 SpillerInstance.reset(0); 225 LRStage.clear(); 226 RegAllocBase::releaseMemory(); 227} 228 229void RAGreedy::enqueue(LiveInterval *LI) { 230 // Prioritize live ranges by size, assigning larger ranges first. 231 // The queue holds (size, reg) pairs. 232 const unsigned Size = LI->getSize(); 233 const unsigned Reg = LI->reg; 234 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 235 "Can only enqueue virtual registers"); 236 unsigned Prio; 237 238 LRStage.grow(Reg); 239 if (LRStage[Reg] == RS_Original) 240 // 1st generation ranges are handled first, long -> short. 241 Prio = (1u << 31) + Size; 242 else 243 // Repeat offenders are handled second, short -> long 244 Prio = (1u << 30) - Size; 245 246 // Boost ranges that have a physical register hint. 247 const unsigned Hint = VRM->getRegAllocPref(Reg); 248 if (TargetRegisterInfo::isPhysicalRegister(Hint)) 249 Prio |= (1u << 30); 250 251 Queue.push(std::make_pair(Prio, Reg)); 252} 253 254LiveInterval *RAGreedy::dequeue() { 255 if (Queue.empty()) 256 return 0; 257 LiveInterval *LI = &LIS->getInterval(Queue.top().second); 258 Queue.pop(); 259 return LI; 260} 261 262//===----------------------------------------------------------------------===// 263// Register Reassignment 264//===----------------------------------------------------------------------===// 265 266// Check interference without using the cache. 267bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg, 268 unsigned PhysReg) { 269 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 270 LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]); 271 if (subQ.checkInterference()) 272 return true; 273 } 274 return false; 275} 276 277/// getSingleInterference - Return the single interfering virtual register 278/// assigned to PhysReg. Return 0 if more than one virtual register is 279/// interfering. 280LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg, 281 unsigned PhysReg) { 282 // Check physreg and aliases. 283 LiveInterval *Interference = 0; 284 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 285 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 286 if (Q.checkInterference()) { 287 if (Interference) 288 return 0; 289 if (Q.collectInterferingVRegs(2) > 1) 290 return 0; 291 Interference = Q.interferingVRegs().front(); 292 } 293 } 294 return Interference; 295} 296 297// Attempt to reassign this virtual register to a different physical register. 298// 299// FIXME: we are not yet caching these "second-level" interferences discovered 300// in the sub-queries. These interferences can change with each call to 301// selectOrSplit. However, we could implement a "may-interfere" cache that 302// could be conservatively dirtied when we reassign or split. 303// 304// FIXME: This may result in a lot of alias queries. We could summarize alias 305// live intervals in their parent register's live union, but it's messy. 306bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg, 307 unsigned WantedPhysReg) { 308 assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) && 309 "Can only reassign virtual registers"); 310 assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) && 311 "inconsistent phys reg assigment"); 312 313 AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs); 314 while (unsigned PhysReg = Order.next()) { 315 // Don't reassign to a WantedPhysReg alias. 316 if (TRI->regsOverlap(PhysReg, WantedPhysReg)) 317 continue; 318 319 if (checkUncachedInterference(InterferingVReg, PhysReg)) 320 continue; 321 322 // Reassign the interfering virtual reg to this physical reg. 323 unsigned OldAssign = VRM->getPhys(InterferingVReg.reg); 324 DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " << 325 TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n'); 326 unassign(InterferingVReg, OldAssign); 327 assign(InterferingVReg, PhysReg); 328 ++NumReassigned; 329 return true; 330 } 331 return false; 332} 333 334/// tryReassign - Try to reassign a single interference to a different physreg. 335/// @param VirtReg Currently unassigned virtual register. 336/// @param Order Physregs to try. 337/// @return Physreg to assign VirtReg, or 0. 338unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order, 339 SmallVectorImpl<LiveInterval*> &NewVRegs){ 340 NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled); 341 342 Order.rewind(); 343 while (unsigned PhysReg = Order.next()) { 344 LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg); 345 if (!InterferingVReg) 346 continue; 347 if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg)) 348 continue; 349 if (reassignVReg(*InterferingVReg, PhysReg)) 350 return PhysReg; 351 } 352 return 0; 353} 354 355 356//===----------------------------------------------------------------------===// 357// Interference eviction 358//===----------------------------------------------------------------------===// 359 360/// canEvict - Return true if all interferences between VirtReg and PhysReg can 361/// be evicted. Set maxWeight to the maximal spill weight of an interference. 362bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 363 float &MaxWeight) { 364 float Weight = 0; 365 for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 366 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 367 // If there is 10 or more interferences, chances are one is smaller. 368 if (Q.collectInterferingVRegs(10) >= 10) 369 return false; 370 371 // Check if any interfering live range is heavier than VirtReg. 372 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 373 LiveInterval *Intf = Q.interferingVRegs()[i]; 374 if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 375 return false; 376 if (Intf->weight >= VirtReg.weight) 377 return false; 378 Weight = std::max(Weight, Intf->weight); 379 } 380 } 381 MaxWeight = Weight; 382 return true; 383} 384 385/// tryEvict - Try to evict all interferences for a physreg. 386/// @param VirtReg Currently unassigned virtual register. 387/// @param Order Physregs to try. 388/// @return Physreg to assign VirtReg, or 0. 389unsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 390 AllocationOrder &Order, 391 SmallVectorImpl<LiveInterval*> &NewVRegs){ 392 NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 393 394 // Keep track of the lightest single interference seen so far. 395 float BestWeight = 0; 396 unsigned BestPhys = 0; 397 398 Order.rewind(); 399 while (unsigned PhysReg = Order.next()) { 400 float Weight = 0; 401 if (!canEvictInterference(VirtReg, PhysReg, Weight)) 402 continue; 403 404 // This is an eviction candidate. 405 DEBUG(dbgs() << "max " << PrintReg(PhysReg, TRI) << " interference = " 406 << Weight << '\n'); 407 if (BestPhys && Weight >= BestWeight) 408 continue; 409 410 // Best so far. 411 BestPhys = PhysReg; 412 BestWeight = Weight; 413 // Stop if the hint can be used. 414 if (Order.isHint(PhysReg)) 415 break; 416 } 417 418 if (!BestPhys) 419 return 0; 420 421 DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n"); 422 for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) { 423 LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 424 assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 425 for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 426 LiveInterval *Intf = Q.interferingVRegs()[i]; 427 unassign(*Intf, VRM->getPhys(Intf->reg)); 428 ++NumEvicted; 429 NewVRegs.push_back(Intf); 430 } 431 } 432 return BestPhys; 433} 434 435 436//===----------------------------------------------------------------------===// 437// Region Splitting 438//===----------------------------------------------------------------------===// 439 440/// mapGlobalInterference - Compute a map of the interference from PhysReg and 441/// its aliases in each block in SA->LiveBlocks. 442/// If LiveBlocks[i] is live-in, Ranges[i].first is the first interference. 443/// If LiveBlocks[i] is live-out, Ranges[i].second is the last interference. 444void RAGreedy::mapGlobalInterference(unsigned PhysReg, 445 SmallVectorImpl<IndexPair> &Ranges) { 446 Ranges.assign(SA->LiveBlocks.size(), IndexPair()); 447 LiveInterval &VirtReg = const_cast<LiveInterval&>(SA->getParent()); 448 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 449 if (!query(VirtReg, *AI).checkInterference()) 450 continue; 451 LiveIntervalUnion::SegmentIter IntI = 452 PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 453 if (!IntI.valid()) 454 continue; 455 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 456 const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 457 IndexPair &IP = Ranges[i]; 458 459 // Skip interference-free blocks. 460 if (IntI.start() >= BI.Stop) 461 continue; 462 463 // First interference in block. 464 if (BI.LiveIn) { 465 IntI.advanceTo(BI.Start); 466 if (!IntI.valid()) 467 break; 468 if (IntI.start() >= BI.Stop) 469 continue; 470 if (!IP.first.isValid() || IntI.start() < IP.first) 471 IP.first = IntI.start(); 472 } 473 474 // Last interference in block. 475 if (BI.LiveOut) { 476 IntI.advanceTo(BI.Stop); 477 if (!IntI.valid() || IntI.start() >= BI.Stop) 478 --IntI; 479 if (IntI.stop() <= BI.Start) 480 continue; 481 if (!IP.second.isValid() || IntI.stop() > IP.second) 482 IP.second = IntI.stop(); 483 } 484 } 485 } 486} 487 488/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints 489/// when considering interference from PhysReg. Also compute an optimistic local 490/// cost of this interference pattern. 491/// 492/// The final cost of a split is the local cost + global cost of preferences 493/// broken by SpillPlacement. 494/// 495float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { 496 // Reset interference dependent info. 497 SpillConstraints.resize(SA->LiveBlocks.size()); 498 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 499 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 500 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 501 BC.Number = BI.MBB->getNumber(); 502 BC.Entry = (BI.Uses && BI.LiveIn) ? 503 SpillPlacement::PrefReg : SpillPlacement::DontCare; 504 BC.Exit = (BI.Uses && BI.LiveOut) ? 505 SpillPlacement::PrefReg : SpillPlacement::DontCare; 506 BI.OverlapEntry = BI.OverlapExit = false; 507 } 508 509 // Add interference info from each PhysReg alias. 510 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 511 if (!query(VirtReg, *AI).checkInterference()) 512 continue; 513 LiveIntervalUnion::SegmentIter IntI = 514 PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 515 if (!IntI.valid()) 516 continue; 517 518 // Determine which blocks have interference live in or after the last split 519 // point. 520 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 521 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 522 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 523 524 // Skip interference-free blocks. 525 if (IntI.start() >= BI.Stop) 526 continue; 527 528 // Is the interference live-in? 529 if (BI.LiveIn) { 530 IntI.advanceTo(BI.Start); 531 if (!IntI.valid()) 532 break; 533 if (IntI.start() <= BI.Start) 534 BC.Entry = SpillPlacement::MustSpill; 535 } 536 537 // Is the interference overlapping the last split point? 538 if (BI.LiveOut) { 539 if (IntI.stop() < BI.LastSplitPoint) 540 IntI.advanceTo(BI.LastSplitPoint.getPrevSlot()); 541 if (!IntI.valid()) 542 break; 543 if (IntI.start() < BI.Stop) 544 BC.Exit = SpillPlacement::MustSpill; 545 } 546 } 547 548 // Rewind iterator and check other interferences. 549 IntI.find(VirtReg.beginIndex()); 550 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 551 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 552 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 553 554 // Skip interference-free blocks. 555 if (IntI.start() >= BI.Stop) 556 continue; 557 558 // Handle transparent blocks with interference separately. 559 // Transparent blocks never incur any fixed cost. 560 if (BI.LiveThrough && !BI.Uses) { 561 IntI.advanceTo(BI.Start); 562 if (!IntI.valid()) 563 break; 564 if (IntI.start() >= BI.Stop) 565 continue; 566 567 if (BC.Entry != SpillPlacement::MustSpill) 568 BC.Entry = SpillPlacement::PrefSpill; 569 if (BC.Exit != SpillPlacement::MustSpill) 570 BC.Exit = SpillPlacement::PrefSpill; 571 continue; 572 } 573 574 // Now we only have blocks with uses left. 575 // Check if the interference overlaps the uses. 576 assert(BI.Uses && "Non-transparent block without any uses"); 577 578 // Check interference on entry. 579 if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) { 580 IntI.advanceTo(BI.Start); 581 if (!IntI.valid()) 582 break; 583 // Not live in, but before the first use. 584 if (IntI.start() < BI.FirstUse) { 585 BC.Entry = SpillPlacement::PrefSpill; 586 // If the block contains a kill from an earlier split, never split 587 // again in the same block. 588 if (!BI.LiveThrough && !SA->isOriginalEndpoint(BI.Kill)) 589 BC.Entry = SpillPlacement::MustSpill; 590 } 591 } 592 593 // Does interference overlap the uses in the entry segment 594 // [FirstUse;Kill)? 595 if (BI.LiveIn && !BI.OverlapEntry) { 596 IntI.advanceTo(BI.FirstUse); 597 if (!IntI.valid()) 598 break; 599 // A live-through interval has no kill. 600 // Check [FirstUse;LastUse) instead. 601 if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill)) 602 BI.OverlapEntry = true; 603 } 604 605 // Does interference overlap the uses in the exit segment [Def;LastUse)? 606 if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) { 607 IntI.advanceTo(BI.Def); 608 if (!IntI.valid()) 609 break; 610 if (IntI.start() < BI.LastUse) 611 BI.OverlapExit = true; 612 } 613 614 // Check interference on exit. 615 if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) { 616 // Check interference between LastUse and Stop. 617 if (BC.Exit != SpillPlacement::PrefSpill) { 618 IntI.advanceTo(BI.LastUse); 619 if (!IntI.valid()) 620 break; 621 if (IntI.start() < BI.Stop) { 622 BC.Exit = SpillPlacement::PrefSpill; 623 // Avoid splitting twice in the same block. 624 if (!BI.LiveThrough && !SA->isOriginalEndpoint(BI.Def)) 625 BC.Exit = SpillPlacement::MustSpill; 626 } 627 } 628 } 629 } 630 } 631 632 // Accumulate a local cost of this interference pattern. 633 float LocalCost = 0; 634 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 635 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 636 if (!BI.Uses) 637 continue; 638 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 639 unsigned Inserts = 0; 640 641 // Do we need spill code for the entry segment? 642 if (BI.LiveIn) 643 Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg; 644 645 // For the exit segment? 646 if (BI.LiveOut) 647 Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg; 648 649 // The local cost of spill code in this block is the block frequency times 650 // the number of spill instructions inserted. 651 if (Inserts) 652 LocalCost += Inserts * SpillPlacer->getBlockFrequency(BC.Number); 653 } 654 DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = " 655 << LocalCost << '\n'); 656 return LocalCost; 657} 658 659/// calcGlobalSplitCost - Return the global split cost of following the split 660/// pattern in LiveBundles. This cost should be added to the local cost of the 661/// interference pattern in SpillConstraints. 662/// 663float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { 664 float GlobalCost = 0; 665 for (unsigned i = 0, e = SpillConstraints.size(); i != e; ++i) { 666 SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 667 unsigned Inserts = 0; 668 // Broken entry preference? 669 Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] != 670 (BC.Entry == SpillPlacement::PrefReg); 671 // Broken exit preference? 672 Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] != 673 (BC.Exit == SpillPlacement::PrefReg); 674 if (Inserts) 675 GlobalCost += Inserts * SpillPlacer->getBlockFrequency(BC.Number); 676 } 677 DEBUG({ 678 dbgs() << "Global cost = " << GlobalCost << " with bundles"; 679 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 680 dbgs() << " EB#" << i; 681 dbgs() << ".\n"; 682 }); 683 return GlobalCost; 684} 685 686/// splitAroundRegion - Split VirtReg around the region determined by 687/// LiveBundles. Make an effort to avoid interference from PhysReg. 688/// 689/// The 'register' interval is going to contain as many uses as possible while 690/// avoiding interference. The 'stack' interval is the complement constructed by 691/// SplitEditor. It will contain the rest. 692/// 693void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, 694 const BitVector &LiveBundles, 695 SmallVectorImpl<LiveInterval*> &NewVRegs) { 696 DEBUG({ 697 dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI) 698 << " with bundles"; 699 for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 700 dbgs() << " EB#" << i; 701 dbgs() << ".\n"; 702 }); 703 704 // First compute interference ranges in the live blocks. 705 SmallVector<IndexPair, 8> InterferenceRanges; 706 mapGlobalInterference(PhysReg, InterferenceRanges); 707 708 SmallVector<LiveInterval*, 4> SpillRegs; 709 LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 710 SE->reset(LREdit); 711 712 // Create the main cross-block interval. 713 SE->openIntv(); 714 715 // First add all defs that are live out of a block. 716 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 717 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 718 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 719 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 720 721 // Should the register be live out? 722 if (!BI.LiveOut || !RegOut) 723 continue; 724 725 IndexPair &IP = InterferenceRanges[i]; 726 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 727 << Bundles->getBundle(BI.MBB->getNumber(), 1) 728 << " intf [" << IP.first << ';' << IP.second << ')'); 729 730 // The interference interval should either be invalid or overlap MBB. 731 assert((!IP.first.isValid() || IP.first < BI.Stop) && "Bad interference"); 732 assert((!IP.second.isValid() || IP.second > BI.Start) 733 && "Bad interference"); 734 735 // Check interference leaving the block. 736 if (!IP.second.isValid()) { 737 // Block is interference-free. 738 DEBUG(dbgs() << ", no interference"); 739 if (!BI.Uses) { 740 assert(BI.LiveThrough && "No uses, but not live through block?"); 741 // Block is live-through without interference. 742 DEBUG(dbgs() << ", no uses" 743 << (RegIn ? ", live-through.\n" : ", stack in.\n")); 744 if (!RegIn) 745 SE->enterIntvAtEnd(*BI.MBB); 746 continue; 747 } 748 if (!BI.LiveThrough) { 749 DEBUG(dbgs() << ", not live-through.\n"); 750 SE->useIntv(SE->enterIntvBefore(BI.Def), BI.Stop); 751 continue; 752 } 753 if (!RegIn) { 754 // Block is live-through, but entry bundle is on the stack. 755 // Reload just before the first use. 756 DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 757 SE->useIntv(SE->enterIntvBefore(BI.FirstUse), BI.Stop); 758 continue; 759 } 760 DEBUG(dbgs() << ", live-through.\n"); 761 continue; 762 } 763 764 // Block has interference. 765 DEBUG(dbgs() << ", interference to " << IP.second); 766 767 if (!BI.LiveThrough && IP.second <= BI.Def) { 768 // The interference doesn't reach the outgoing segment. 769 DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n'); 770 SE->useIntv(BI.Def, BI.Stop); 771 continue; 772 } 773 774 775 if (!BI.Uses) { 776 // No uses in block, avoid interference by reloading as late as possible. 777 DEBUG(dbgs() << ", no uses.\n"); 778 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 779 assert(SegStart >= IP.second && "Couldn't avoid interference"); 780 continue; 781 } 782 783 if (IP.second.getBoundaryIndex() < BI.LastUse) { 784 // There are interference-free uses at the end of the block. 785 // Find the first use that can get the live-out register. 786 SmallVectorImpl<SlotIndex>::const_iterator UI = 787 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 788 IP.second.getBoundaryIndex()); 789 assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 790 SlotIndex Use = *UI; 791 assert(Use <= BI.LastUse && "Couldn't find last use"); 792 // Only attempt a split befroe the last split point. 793 if (Use.getBaseIndex() <= BI.LastSplitPoint) { 794 DEBUG(dbgs() << ", free use at " << Use << ".\n"); 795 SlotIndex SegStart = SE->enterIntvBefore(Use); 796 assert(SegStart >= IP.second && "Couldn't avoid interference"); 797 assert(SegStart < BI.LastSplitPoint && "Impossible split point"); 798 SE->useIntv(SegStart, BI.Stop); 799 continue; 800 } 801 } 802 803 // Interference is after the last use. 804 DEBUG(dbgs() << " after last use.\n"); 805 SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 806 assert(SegStart >= IP.second && "Couldn't avoid interference"); 807 } 808 809 // Now all defs leading to live bundles are handled, do everything else. 810 for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 811 SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 812 bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 813 bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 814 815 // Is the register live-in? 816 if (!BI.LiveIn || !RegIn) 817 continue; 818 819 // We have an incoming register. Check for interference. 820 IndexPair &IP = InterferenceRanges[i]; 821 822 DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 823 << " -> BB#" << BI.MBB->getNumber()); 824 825 // Check interference entering the block. 826 if (!IP.first.isValid()) { 827 // Block is interference-free. 828 DEBUG(dbgs() << ", no interference"); 829 if (!BI.Uses) { 830 assert(BI.LiveThrough && "No uses, but not live through block?"); 831 // Block is live-through without interference. 832 if (RegOut) { 833 DEBUG(dbgs() << ", no uses, live-through.\n"); 834 SE->useIntv(BI.Start, BI.Stop); 835 } else { 836 DEBUG(dbgs() << ", no uses, stack-out.\n"); 837 SE->leaveIntvAtTop(*BI.MBB); 838 } 839 continue; 840 } 841 if (!BI.LiveThrough) { 842 DEBUG(dbgs() << ", killed in block.\n"); 843 SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.Kill)); 844 continue; 845 } 846 if (!RegOut) { 847 // Block is live-through, but exit bundle is on the stack. 848 // Spill immediately after the last use. 849 if (BI.LastUse < BI.LastSplitPoint) { 850 DEBUG(dbgs() << ", uses, stack-out.\n"); 851 SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.LastUse)); 852 continue; 853 } 854 // The last use is after the last split point, it is probably an 855 // indirect jump. 856 DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 857 << BI.LastSplitPoint << ", stack-out.\n"); 858 SlotIndex SegEnd = SE->leaveIntvBefore(BI.LastSplitPoint); 859 SE->useIntv(BI.Start, SegEnd); 860 // Run a double interval from the split to the last use. 861 // This makes it possible to spill the complement without affecting the 862 // indirect branch. 863 SE->overlapIntv(SegEnd, BI.LastUse); 864 continue; 865 } 866 // Register is live-through. 867 DEBUG(dbgs() << ", uses, live-through.\n"); 868 SE->useIntv(BI.Start, BI.Stop); 869 continue; 870 } 871 872 // Block has interference. 873 DEBUG(dbgs() << ", interference from " << IP.first); 874 875 if (!BI.LiveThrough && IP.first >= BI.Kill) { 876 // The interference doesn't reach the outgoing segment. 877 DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n'); 878 SE->useIntv(BI.Start, BI.Kill); 879 continue; 880 } 881 882 if (!BI.Uses) { 883 // No uses in block, avoid interference by spilling as soon as possible. 884 DEBUG(dbgs() << ", no uses.\n"); 885 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 886 assert(SegEnd <= IP.first && "Couldn't avoid interference"); 887 continue; 888 } 889 if (IP.first.getBaseIndex() > BI.FirstUse) { 890 // There are interference-free uses at the beginning of the block. 891 // Find the last use that can get the register. 892 SmallVectorImpl<SlotIndex>::const_iterator UI = 893 std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 894 IP.first.getBaseIndex()); 895 assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 896 SlotIndex Use = (--UI)->getBoundaryIndex(); 897 DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 898 SlotIndex SegEnd = SE->leaveIntvAfter(Use); 899 assert(SegEnd <= IP.first && "Couldn't avoid interference"); 900 SE->useIntv(BI.Start, SegEnd); 901 continue; 902 } 903 904 // Interference is before the first use. 905 DEBUG(dbgs() << " before first use.\n"); 906 SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 907 assert(SegEnd <= IP.first && "Couldn't avoid interference"); 908 } 909 910 SE->closeIntv(); 911 912 // FIXME: Should we be more aggressive about splitting the stack region into 913 // per-block segments? The current approach allows the stack region to 914 // separate into connected components. Some components may be allocatable. 915 SE->finish(); 916 ++NumGlobalSplits; 917 918 if (VerifyEnabled) { 919 MF->verify(this, "After splitting live range around region"); 920 921#ifndef NDEBUG 922 // Make sure that at least one of the new intervals can allocate to PhysReg. 923 // That was the whole point of splitting the live range. 924 bool found = false; 925 for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E; 926 ++I) 927 if (!checkUncachedInterference(**I, PhysReg)) { 928 found = true; 929 break; 930 } 931 assert(found && "No allocatable intervals after pointless splitting"); 932#endif 933 } 934} 935 936unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 937 SmallVectorImpl<LiveInterval*> &NewVRegs) { 938 BitVector LiveBundles, BestBundles; 939 float BestCost = 0; 940 unsigned BestReg = 0; 941 Order.rewind(); 942 while (unsigned PhysReg = Order.next()) { 943 float Cost = calcInterferenceInfo(VirtReg, PhysReg); 944 if (BestReg && Cost >= BestCost) 945 continue; 946 947 SpillPlacer->placeSpills(SpillConstraints, LiveBundles); 948 // No live bundles, defer to splitSingleBlocks(). 949 if (!LiveBundles.any()) 950 continue; 951 952 Cost += calcGlobalSplitCost(LiveBundles); 953 if (!BestReg || Cost < BestCost) { 954 BestReg = PhysReg; 955 BestCost = Cost; 956 BestBundles.swap(LiveBundles); 957 } 958 } 959 960 if (!BestReg) 961 return 0; 962 963 splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); 964 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region); 965 return 0; 966} 967 968 969//===----------------------------------------------------------------------===// 970// Local Splitting 971//===----------------------------------------------------------------------===// 972 973 974/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 975/// in order to use PhysReg between two entries in SA->UseSlots. 976/// 977/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 978/// 979void RAGreedy::calcGapWeights(unsigned PhysReg, 980 SmallVectorImpl<float> &GapWeight) { 981 assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 982 const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 983 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 984 const unsigned NumGaps = Uses.size()-1; 985 986 // Start and end points for the interference check. 987 SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 988 SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 989 990 GapWeight.assign(NumGaps, 0.0f); 991 992 // Add interference from each overlapping register. 993 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 994 if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 995 .checkInterference()) 996 continue; 997 998 // We know that VirtReg is a continuous interval from FirstUse to LastUse, 999 // so we don't need InterferenceQuery. 1000 // 1001 // Interference that overlaps an instruction is counted in both gaps 1002 // surrounding the instruction. The exception is interference before 1003 // StartIdx and after StopIdx. 1004 // 1005 LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 1006 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1007 // Skip the gaps before IntI. 1008 while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1009 if (++Gap == NumGaps) 1010 break; 1011 if (Gap == NumGaps) 1012 break; 1013 1014 // Update the gaps covered by IntI. 1015 const float weight = IntI.value()->weight; 1016 for (; Gap != NumGaps; ++Gap) { 1017 GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1018 if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1019 break; 1020 } 1021 if (Gap == NumGaps) 1022 break; 1023 } 1024 } 1025} 1026 1027/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 1028/// before MI that has a slot index. If MI is the first mapped instruction in 1029/// its block, return the block start index instead. 1030/// 1031SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 1032 assert(MI && "Missing MachineInstr"); 1033 const MachineBasicBlock *MBB = MI->getParent(); 1034 MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 1035 while (I != B) 1036 if (!(--I)->isDebugValue() && !I->isCopy()) 1037 return Indexes->getInstructionIndex(I); 1038 return Indexes->getMBBStartIdx(MBB); 1039} 1040 1041/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 1042/// real non-copy instruction for each instruction in SA->UseSlots. 1043/// 1044void RAGreedy::calcPrevSlots() { 1045 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1046 PrevSlot.clear(); 1047 PrevSlot.reserve(Uses.size()); 1048 for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 1049 const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 1050 PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 1051 } 1052} 1053 1054/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 1055/// be beneficial to split before UseSlots[i]. 1056/// 1057/// 0 is always a valid split point 1058unsigned RAGreedy::nextSplitPoint(unsigned i) { 1059 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1060 const unsigned Size = Uses.size(); 1061 assert(i != Size && "No split points after the end"); 1062 // Allow split before i when Uses[i] is not adjacent to the previous use. 1063 while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 1064 ; 1065 return i; 1066} 1067 1068/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1069/// basic block. 1070/// 1071unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1072 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1073 assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 1074 const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 1075 1076 // Note that it is possible to have an interval that is live-in or live-out 1077 // while only covering a single block - A phi-def can use undef values from 1078 // predecessors, and the block could be a single-block loop. 1079 // We don't bother doing anything clever about such a case, we simply assume 1080 // that the interval is continuous from FirstUse to LastUse. We should make 1081 // sure that we don't do anything illegal to such an interval, though. 1082 1083 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1084 if (Uses.size() <= 2) 1085 return 0; 1086 const unsigned NumGaps = Uses.size()-1; 1087 1088 DEBUG({ 1089 dbgs() << "tryLocalSplit: "; 1090 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1091 dbgs() << ' ' << SA->UseSlots[i]; 1092 dbgs() << '\n'; 1093 }); 1094 1095 // For every use, find the previous mapped non-copy instruction. 1096 // We use this to detect valid split points, and to estimate new interval 1097 // sizes. 1098 calcPrevSlots(); 1099 1100 unsigned BestBefore = NumGaps; 1101 unsigned BestAfter = 0; 1102 float BestDiff = 0; 1103 1104 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1105 SmallVector<float, 8> GapWeight; 1106 1107 Order.rewind(); 1108 while (unsigned PhysReg = Order.next()) { 1109 // Keep track of the largest spill weight that would need to be evicted in 1110 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1111 calcGapWeights(PhysReg, GapWeight); 1112 1113 // Try to find the best sequence of gaps to close. 1114 // The new spill weight must be larger than any gap interference. 1115 1116 // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1117 unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 1118 1119 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1120 // It is the spill weight that needs to be evicted. 1121 float MaxGap = GapWeight[0]; 1122 for (unsigned i = 1; i != SplitAfter; ++i) 1123 MaxGap = std::max(MaxGap, GapWeight[i]); 1124 1125 for (;;) { 1126 // Live before/after split? 1127 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1128 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1129 1130 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1131 << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1132 << " i=" << MaxGap); 1133 1134 // Stop before the interval gets so big we wouldn't be making progress. 1135 if (!LiveBefore && !LiveAfter) { 1136 DEBUG(dbgs() << " all\n"); 1137 break; 1138 } 1139 // Should the interval be extended or shrunk? 1140 bool Shrink = true; 1141 if (MaxGap < HUGE_VALF) { 1142 // Estimate the new spill weight. 1143 // 1144 // Each instruction reads and writes the register, except the first 1145 // instr doesn't read when !FirstLive, and the last instr doesn't write 1146 // when !LastLive. 1147 // 1148 // We will be inserting copies before and after, so the total number of 1149 // reads and writes is 2 * EstUses. 1150 // 1151 const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 1152 2*(LiveBefore + LiveAfter); 1153 1154 // Try to guess the size of the new interval. This should be trivial, 1155 // but the slot index of an inserted copy can be a lot smaller than the 1156 // instruction it is inserted before if there are many dead indexes 1157 // between them. 1158 // 1159 // We measure the distance from the instruction before SplitBefore to 1160 // get a conservative estimate. 1161 // 1162 // The final distance can still be different if inserting copies 1163 // triggers a slot index renumbering. 1164 // 1165 const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 1166 PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 1167 // Would this split be possible to allocate? 1168 // Never allocate all gaps, we wouldn't be making progress. 1169 float Diff = EstWeight - MaxGap; 1170 DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff); 1171 if (Diff > 0) { 1172 Shrink = false; 1173 if (Diff > BestDiff) { 1174 DEBUG(dbgs() << " (best)"); 1175 BestDiff = Diff; 1176 BestBefore = SplitBefore; 1177 BestAfter = SplitAfter; 1178 } 1179 } 1180 } 1181 1182 // Try to shrink. 1183 if (Shrink) { 1184 SplitBefore = nextSplitPoint(SplitBefore); 1185 if (SplitBefore < SplitAfter) { 1186 DEBUG(dbgs() << " shrink\n"); 1187 // Recompute the max when necessary. 1188 if (GapWeight[SplitBefore - 1] >= MaxGap) { 1189 MaxGap = GapWeight[SplitBefore]; 1190 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1191 MaxGap = std::max(MaxGap, GapWeight[i]); 1192 } 1193 continue; 1194 } 1195 MaxGap = 0; 1196 } 1197 1198 // Try to extend the interval. 1199 if (SplitAfter >= NumGaps) { 1200 DEBUG(dbgs() << " end\n"); 1201 break; 1202 } 1203 1204 DEBUG(dbgs() << " extend\n"); 1205 for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1206 SplitAfter != e; ++SplitAfter) 1207 MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1208 continue; 1209 } 1210 } 1211 1212 // Didn't find any candidates? 1213 if (BestBefore == NumGaps) 1214 return 0; 1215 1216 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1217 << '-' << Uses[BestAfter] << ", " << BestDiff 1218 << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1219 1220 SmallVector<LiveInterval*, 4> SpillRegs; 1221 LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 1222 SE->reset(LREdit); 1223 1224 SE->openIntv(); 1225 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1226 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1227 SE->useIntv(SegStart, SegStop); 1228 SE->closeIntv(); 1229 SE->finish(); 1230 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local); 1231 ++NumLocalSplits; 1232 1233 return 0; 1234} 1235 1236//===----------------------------------------------------------------------===// 1237// Live Range Splitting 1238//===----------------------------------------------------------------------===// 1239 1240/// trySplit - Try to split VirtReg or one of its interferences, making it 1241/// assignable. 1242/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1243unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1244 SmallVectorImpl<LiveInterval*>&NewVRegs) { 1245 // Local intervals are handled separately. 1246 if (LIS->intervalIsInOneMBB(VirtReg)) { 1247 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1248 SA->analyze(&VirtReg); 1249 return tryLocalSplit(VirtReg, Order, NewVRegs); 1250 } 1251 1252 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1253 1254 // Don't iterate global splitting. 1255 // Move straight to spilling if this range was produced by a global split. 1256 LiveRangeStage Stage = getStage(VirtReg); 1257 if (Stage >= RS_Block) 1258 return 0; 1259 1260 SA->analyze(&VirtReg); 1261 1262 // First try to split around a region spanning multiple blocks. 1263 if (Stage < RS_Region) { 1264 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1265 if (PhysReg || !NewVRegs.empty()) 1266 return PhysReg; 1267 } 1268 1269 // Then isolate blocks with multiple uses. 1270 if (Stage < RS_Block) { 1271 SplitAnalysis::BlockPtrSet Blocks; 1272 if (SA->getMultiUseBlocks(Blocks)) { 1273 SmallVector<LiveInterval*, 4> SpillRegs; 1274 LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 1275 SE->reset(LREdit); 1276 SE->splitSingleBlocks(Blocks); 1277 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block); 1278 if (VerifyEnabled) 1279 MF->verify(this, "After splitting live range around basic blocks"); 1280 } 1281 } 1282 1283 // Don't assign any physregs. 1284 return 0; 1285} 1286 1287 1288//===----------------------------------------------------------------------===// 1289// Main Entry Point 1290//===----------------------------------------------------------------------===// 1291 1292unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1293 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1294 LiveRangeStage Stage = getStage(VirtReg); 1295 if (Stage == RS_Original) 1296 LRStage[VirtReg.reg] = RS_Second; 1297 1298 // First try assigning a free register. 1299 AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 1300 while (unsigned PhysReg = Order.next()) { 1301 if (!checkPhysRegInterference(VirtReg, PhysReg)) 1302 return PhysReg; 1303 } 1304 1305 if (unsigned PhysReg = tryReassign(VirtReg, Order, NewVRegs)) 1306 return PhysReg; 1307 1308 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1309 return PhysReg; 1310 1311 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1312 1313 // The first time we see a live range, don't try to split or spill. 1314 // Wait until the second time, when all smaller ranges have been allocated. 1315 // This gives a better picture of the interference to split around. 1316 if (Stage == RS_Original) { 1317 NewVRegs.push_back(&VirtReg); 1318 return 0; 1319 } 1320 1321 assert(Stage < RS_Spill && "Cannot allocate after spilling"); 1322 1323 // Try splitting VirtReg or interferences. 1324 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1325 if (PhysReg || !NewVRegs.empty()) 1326 return PhysReg; 1327 1328 // Finally spill VirtReg itself. 1329 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1330 SmallVector<LiveInterval*, 1> pendingSpills; 1331 spiller().spill(&VirtReg, NewVRegs, pendingSpills); 1332 1333 // The live virtual register requesting allocation was spilled, so tell 1334 // the caller not to allocate anything during this round. 1335 return 0; 1336} 1337 1338bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1339 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1340 << "********** Function: " 1341 << ((Value*)mf.getFunction())->getName() << '\n'); 1342 1343 MF = &mf; 1344 if (VerifyEnabled) 1345 MF->verify(this, "Before greedy register allocator"); 1346 1347 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1348 Indexes = &getAnalysis<SlotIndexes>(); 1349 DomTree = &getAnalysis<MachineDominatorTree>(); 1350 ReservedRegs = TRI->getReservedRegs(*MF); 1351 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1352 Loops = &getAnalysis<MachineLoopInfo>(); 1353 LoopRanges = &getAnalysis<MachineLoopRanges>(); 1354 Bundles = &getAnalysis<EdgeBundles>(); 1355 SpillPlacer = &getAnalysis<SpillPlacement>(); 1356 1357 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1358 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 1359 LRStage.clear(); 1360 LRStage.resize(MRI->getNumVirtRegs()); 1361 1362 allocatePhysRegs(); 1363 addMBBLiveIns(MF); 1364 LIS->addKillFlags(); 1365 1366 // Run rewriter 1367 { 1368 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1369 VRM->rewrite(Indexes); 1370 } 1371 1372 // The pass output is in VirtRegMap. Release all the transient data. 1373 releaseMemory(); 1374 1375 return true; 1376} 1377