RegAllocGreedy.cpp revision 3bae1bf62eba1a2715ec22d9800799184cc495e6
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 if (GlobalCand.size() <= NumCands) 1251 GlobalCand.resize(NumCands+1); 1252 GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1253 Cand.reset(IntfCache, PhysReg); 1254 1255 SpillPlacer->prepare(Cand.LiveBundles); 1256 float Cost; 1257 if (!addSplitConstraints(Cand.Intf, Cost)) { 1258 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 1259 continue; 1260 } 1261 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1262 if (Cost >= BestCost) { 1263 DEBUG({ 1264 if (BestCand == NoCand) 1265 dbgs() << " worse than no bundles\n"; 1266 else 1267 dbgs() << " worse than " 1268 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1269 }); 1270 continue; 1271 } 1272 growRegion(Cand); 1273 1274 SpillPlacer->finish(); 1275 1276 // No live bundles, defer to splitSingleBlocks(). 1277 if (!Cand.LiveBundles.any()) { 1278 DEBUG(dbgs() << " no bundles.\n"); 1279 continue; 1280 } 1281 1282 Cost += calcGlobalSplitCost(Cand); 1283 DEBUG({ 1284 dbgs() << ", total = " << Cost << " with bundles"; 1285 for (int i = Cand.LiveBundles.find_first(); i>=0; 1286 i = Cand.LiveBundles.find_next(i)) 1287 dbgs() << " EB#" << i; 1288 dbgs() << ".\n"; 1289 }); 1290 if (Cost < BestCost) { 1291 BestCand = NumCands; 1292 BestCost = Hysteresis * Cost; // Prevent rounding effects. 1293 } 1294 ++NumCands; 1295 } 1296 1297 if (BestCand == NoCand) 1298 return 0; 1299 1300 splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs); 1301 return 0; 1302} 1303 1304 1305//===----------------------------------------------------------------------===// 1306// Local Splitting 1307//===----------------------------------------------------------------------===// 1308 1309 1310/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1311/// in order to use PhysReg between two entries in SA->UseSlots. 1312/// 1313/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1314/// 1315void RAGreedy::calcGapWeights(unsigned PhysReg, 1316 SmallVectorImpl<float> &GapWeight) { 1317 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1318 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1319 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1320 const unsigned NumGaps = Uses.size()-1; 1321 1322 // Start and end points for the interference check. 1323 SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 1324 SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 1325 1326 GapWeight.assign(NumGaps, 0.0f); 1327 1328 // Add interference from each overlapping register. 1329 for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1330 if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 1331 .checkInterference()) 1332 continue; 1333 1334 // We know that VirtReg is a continuous interval from FirstUse to LastUse, 1335 // so we don't need InterferenceQuery. 1336 // 1337 // Interference that overlaps an instruction is counted in both gaps 1338 // surrounding the instruction. The exception is interference before 1339 // StartIdx and after StopIdx. 1340 // 1341 LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 1342 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1343 // Skip the gaps before IntI. 1344 while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1345 if (++Gap == NumGaps) 1346 break; 1347 if (Gap == NumGaps) 1348 break; 1349 1350 // Update the gaps covered by IntI. 1351 const float weight = IntI.value()->weight; 1352 for (; Gap != NumGaps; ++Gap) { 1353 GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1354 if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1355 break; 1356 } 1357 if (Gap == NumGaps) 1358 break; 1359 } 1360 } 1361} 1362 1363/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1364/// basic block. 1365/// 1366unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1367 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1368 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1369 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1370 1371 // Note that it is possible to have an interval that is live-in or live-out 1372 // while only covering a single block - A phi-def can use undef values from 1373 // predecessors, and the block could be a single-block loop. 1374 // We don't bother doing anything clever about such a case, we simply assume 1375 // that the interval is continuous from FirstUse to LastUse. We should make 1376 // sure that we don't do anything illegal to such an interval, though. 1377 1378 const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1379 if (Uses.size() <= 2) 1380 return 0; 1381 const unsigned NumGaps = Uses.size()-1; 1382 1383 DEBUG({ 1384 dbgs() << "tryLocalSplit: "; 1385 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1386 dbgs() << ' ' << SA->UseSlots[i]; 1387 dbgs() << '\n'; 1388 }); 1389 1390 // Since we allow local split results to be split again, there is a risk of 1391 // creating infinite loops. It is tempting to require that the new live 1392 // ranges have less instructions than the original. That would guarantee 1393 // convergence, but it is too strict. A live range with 3 instructions can be 1394 // split 2+3 (including the COPY), and we want to allow that. 1395 // 1396 // Instead we use these rules: 1397 // 1398 // 1. Allow any split for ranges with getStage() < RS_Local. (Except for the 1399 // noop split, of course). 1400 // 2. Require progress be made for ranges with getStage() >= RS_Local. All 1401 // the new ranges must have fewer instructions than before the split. 1402 // 3. New ranges with the same number of instructions are marked RS_Local, 1403 // smaller ranges are marked RS_New. 1404 // 1405 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1406 // excessive splitting and infinite loops. 1407 // 1408 bool ProgressRequired = getStage(VirtReg) >= RS_Local; 1409 1410 // Best split candidate. 1411 unsigned BestBefore = NumGaps; 1412 unsigned BestAfter = 0; 1413 float BestDiff = 0; 1414 1415 const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1416 SmallVector<float, 8> GapWeight; 1417 1418 Order.rewind(); 1419 while (unsigned PhysReg = Order.next()) { 1420 // Keep track of the largest spill weight that would need to be evicted in 1421 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1422 calcGapWeights(PhysReg, GapWeight); 1423 1424 // Try to find the best sequence of gaps to close. 1425 // The new spill weight must be larger than any gap interference. 1426 1427 // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1428 unsigned SplitBefore = 0, SplitAfter = 1; 1429 1430 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1431 // It is the spill weight that needs to be evicted. 1432 float MaxGap = GapWeight[0]; 1433 1434 for (;;) { 1435 // Live before/after split? 1436 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1437 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1438 1439 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1440 << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1441 << " i=" << MaxGap); 1442 1443 // Stop before the interval gets so big we wouldn't be making progress. 1444 if (!LiveBefore && !LiveAfter) { 1445 DEBUG(dbgs() << " all\n"); 1446 break; 1447 } 1448 // Should the interval be extended or shrunk? 1449 bool Shrink = true; 1450 1451 // How many gaps would the new range have? 1452 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1453 1454 // Legally, without causing looping? 1455 bool Legal = !ProgressRequired || NewGaps < NumGaps; 1456 1457 if (Legal && MaxGap < HUGE_VALF) { 1458 // Estimate the new spill weight. Each instruction reads or writes the 1459 // register. Conservatively assume there are no read-modify-write 1460 // instructions. 1461 // 1462 // Try to guess the size of the new interval. 1463 const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1464 Uses[SplitBefore].distance(Uses[SplitAfter]) + 1465 (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1466 // Would this split be possible to allocate? 1467 // Never allocate all gaps, we wouldn't be making progress. 1468 DEBUG(dbgs() << " w=" << EstWeight); 1469 if (EstWeight * Hysteresis >= MaxGap) { 1470 Shrink = false; 1471 float Diff = EstWeight - MaxGap; 1472 if (Diff > BestDiff) { 1473 DEBUG(dbgs() << " (best)"); 1474 BestDiff = Hysteresis * Diff; 1475 BestBefore = SplitBefore; 1476 BestAfter = SplitAfter; 1477 } 1478 } 1479 } 1480 1481 // Try to shrink. 1482 if (Shrink) { 1483 if (++SplitBefore < SplitAfter) { 1484 DEBUG(dbgs() << " shrink\n"); 1485 // Recompute the max when necessary. 1486 if (GapWeight[SplitBefore - 1] >= MaxGap) { 1487 MaxGap = GapWeight[SplitBefore]; 1488 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1489 MaxGap = std::max(MaxGap, GapWeight[i]); 1490 } 1491 continue; 1492 } 1493 MaxGap = 0; 1494 } 1495 1496 // Try to extend the interval. 1497 if (SplitAfter >= NumGaps) { 1498 DEBUG(dbgs() << " end\n"); 1499 break; 1500 } 1501 1502 DEBUG(dbgs() << " extend\n"); 1503 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1504 } 1505 } 1506 1507 // Didn't find any candidates? 1508 if (BestBefore == NumGaps) 1509 return 0; 1510 1511 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1512 << '-' << Uses[BestAfter] << ", " << BestDiff 1513 << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1514 1515 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1516 SE->reset(LREdit); 1517 1518 SE->openIntv(); 1519 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1520 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1521 SE->useIntv(SegStart, SegStop); 1522 SmallVector<unsigned, 8> IntvMap; 1523 SE->finish(&IntvMap); 1524 DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1525 1526 // If the new range has the same number of instructions as before, mark it as 1527 // RS_Local so the next split will be forced to make progress. Otherwise, 1528 // leave the new intervals as RS_New so they can compete. 1529 bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1530 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1531 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1532 if (NewGaps >= NumGaps) { 1533 DEBUG(dbgs() << "Tagging non-progress ranges: "); 1534 assert(!ProgressRequired && "Didn't make progress when it was required."); 1535 for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1536 if (IntvMap[i] == 1) { 1537 setStage(*LREdit.get(i), RS_Local); 1538 DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg)); 1539 } 1540 DEBUG(dbgs() << '\n'); 1541 } 1542 ++NumLocalSplits; 1543 1544 return 0; 1545} 1546 1547//===----------------------------------------------------------------------===// 1548// Live Range Splitting 1549//===----------------------------------------------------------------------===// 1550 1551/// trySplit - Try to split VirtReg or one of its interferences, making it 1552/// assignable. 1553/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1554unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1555 SmallVectorImpl<LiveInterval*>&NewVRegs) { 1556 // Local intervals are handled separately. 1557 if (LIS->intervalIsInOneMBB(VirtReg)) { 1558 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1559 SA->analyze(&VirtReg); 1560 return tryLocalSplit(VirtReg, Order, NewVRegs); 1561 } 1562 1563 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1564 1565 // Don't iterate global splitting. 1566 // Move straight to spilling if this range was produced by a global split. 1567 if (getStage(VirtReg) >= RS_Global) 1568 return 0; 1569 1570 SA->analyze(&VirtReg); 1571 1572 // FIXME: SplitAnalysis may repair broken live ranges coming from the 1573 // coalescer. That may cause the range to become allocatable which means that 1574 // tryRegionSplit won't be making progress. This check should be replaced with 1575 // an assertion when the coalescer is fixed. 1576 if (SA->didRepairRange()) { 1577 // VirtReg has changed, so all cached queries are invalid. 1578 invalidateVirtRegs(); 1579 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1580 return PhysReg; 1581 } 1582 1583 // First try to split around a region spanning multiple blocks. 1584 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1585 if (PhysReg || !NewVRegs.empty()) 1586 return PhysReg; 1587 1588 // Then isolate blocks with multiple uses. 1589 SplitAnalysis::BlockPtrSet Blocks; 1590 if (SA->getMultiUseBlocks(Blocks)) { 1591 LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1592 SE->reset(LREdit); 1593 SE->splitSingleBlocks(Blocks); 1594 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global); 1595 if (VerifyEnabled) 1596 MF->verify(this, "After splitting live range around basic blocks"); 1597 } 1598 1599 // Don't assign any physregs. 1600 return 0; 1601} 1602 1603 1604//===----------------------------------------------------------------------===// 1605// Main Entry Point 1606//===----------------------------------------------------------------------===// 1607 1608unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1609 SmallVectorImpl<LiveInterval*> &NewVRegs) { 1610 // First try assigning a free register. 1611 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 1612 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1613 return PhysReg; 1614 1615 LiveRangeStage Stage = getStage(VirtReg); 1616 DEBUG(dbgs() << StageName[Stage] 1617 << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 1618 1619 // Try to evict a less worthy live range, but only for ranges from the primary 1620 // queue. The RS_Second ranges already failed to do this, and they should not 1621 // get a second chance until they have been split. 1622 if (Stage != RS_Second) 1623 if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1624 return PhysReg; 1625 1626 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1627 1628 // The first time we see a live range, don't try to split or spill. 1629 // Wait until the second time, when all smaller ranges have been allocated. 1630 // This gives a better picture of the interference to split around. 1631 if (Stage == RS_First) { 1632 setStage(VirtReg, RS_Second); 1633 DEBUG(dbgs() << "wait for second round\n"); 1634 NewVRegs.push_back(&VirtReg); 1635 return 0; 1636 } 1637 1638 // If we couldn't allocate a register from spilling, there is probably some 1639 // invalid inline assembly. The base class wil report it. 1640 if (Stage >= RS_Spill || !VirtReg.isSpillable()) 1641 return ~0u; 1642 1643 // Try splitting VirtReg or interferences. 1644 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1645 if (PhysReg || !NewVRegs.empty()) 1646 return PhysReg; 1647 1648 // Finally spill VirtReg itself. 1649 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1650 LiveRangeEdit LRE(VirtReg, NewVRegs, this); 1651 spiller().spill(LRE); 1652 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill); 1653 1654 if (VerifyEnabled) 1655 MF->verify(this, "After spilling"); 1656 1657 // The live virtual register requesting allocation was spilled, so tell 1658 // the caller not to allocate anything during this round. 1659 return 0; 1660} 1661 1662bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1663 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1664 << "********** Function: " 1665 << ((Value*)mf.getFunction())->getName() << '\n'); 1666 1667 MF = &mf; 1668 if (VerifyEnabled) 1669 MF->verify(this, "Before greedy register allocator"); 1670 1671 RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1672 Indexes = &getAnalysis<SlotIndexes>(); 1673 DomTree = &getAnalysis<MachineDominatorTree>(); 1674 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1675 Loops = &getAnalysis<MachineLoopInfo>(); 1676 LoopRanges = &getAnalysis<MachineLoopRanges>(); 1677 Bundles = &getAnalysis<EdgeBundles>(); 1678 SpillPlacer = &getAnalysis<SpillPlacement>(); 1679 DebugVars = &getAnalysis<LiveDebugVariables>(); 1680 1681 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1682 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 1683 ExtraRegInfo.clear(); 1684 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1685 NextCascade = 1; 1686 IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 1687 1688 allocatePhysRegs(); 1689 addMBBLiveIns(MF); 1690 LIS->addKillFlags(); 1691 1692 // Run rewriter 1693 { 1694 NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1695 VRM->rewrite(Indexes); 1696 } 1697 1698 // Write out new DBG_VALUE instructions. 1699 DebugVars->emitDebugValues(VRM); 1700 1701 // The pass output is in VirtRegMap. Release all the transient data. 1702 releaseMemory(); 1703 1704 return true; 1705} 1706