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