RegAllocGreedy.cpp revision 223017
1218885Sdim//===-- RegAllocGreedy.cpp - greedy register allocator --------------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This file defines the RAGreedy function pass for register allocation in 11218885Sdim// optimized builds. 12218885Sdim// 13218885Sdim//===----------------------------------------------------------------------===// 14218885Sdim 15218885Sdim#define DEBUG_TYPE "regalloc" 16218885Sdim#include "AllocationOrder.h" 17221345Sdim#include "InterferenceCache.h" 18221345Sdim#include "LiveDebugVariables.h" 19218885Sdim#include "LiveRangeEdit.h" 20218885Sdim#include "RegAllocBase.h" 21218885Sdim#include "Spiller.h" 22218885Sdim#include "SpillPlacement.h" 23218885Sdim#include "SplitKit.h" 24218885Sdim#include "VirtRegMap.h" 25218885Sdim#include "llvm/ADT/Statistic.h" 26218885Sdim#include "llvm/Analysis/AliasAnalysis.h" 27218885Sdim#include "llvm/Function.h" 28218885Sdim#include "llvm/PassAnalysisSupport.h" 29218885Sdim#include "llvm/CodeGen/CalcSpillWeights.h" 30218885Sdim#include "llvm/CodeGen/EdgeBundles.h" 31218885Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 32218885Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 33218885Sdim#include "llvm/CodeGen/MachineDominators.h" 34218885Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 35218885Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 36218885Sdim#include "llvm/CodeGen/MachineLoopRanges.h" 37218885Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 38218885Sdim#include "llvm/CodeGen/Passes.h" 39218885Sdim#include "llvm/CodeGen/RegAllocRegistry.h" 40218885Sdim#include "llvm/CodeGen/RegisterCoalescer.h" 41218885Sdim#include "llvm/Target/TargetOptions.h" 42218885Sdim#include "llvm/Support/Debug.h" 43218885Sdim#include "llvm/Support/ErrorHandling.h" 44218885Sdim#include "llvm/Support/raw_ostream.h" 45218885Sdim#include "llvm/Support/Timer.h" 46218885Sdim 47219077Sdim#include <queue> 48219077Sdim 49218885Sdimusing namespace llvm; 50218885Sdim 51218885SdimSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 52218885SdimSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 53218885SdimSTATISTIC(NumEvicted, "Number of interferences evicted"); 54218885Sdim 55218885Sdimstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 56218885Sdim createGreedyRegisterAllocator); 57218885Sdim 58218885Sdimnamespace { 59221345Sdimclass RAGreedy : public MachineFunctionPass, 60221345Sdim public RegAllocBase, 61221345Sdim private LiveRangeEdit::Delegate { 62221345Sdim 63218885Sdim // context 64218885Sdim MachineFunction *MF; 65218885Sdim 66218885Sdim // analyses 67218885Sdim SlotIndexes *Indexes; 68218885Sdim LiveStacks *LS; 69218885Sdim MachineDominatorTree *DomTree; 70218885Sdim MachineLoopInfo *Loops; 71218885Sdim MachineLoopRanges *LoopRanges; 72218885Sdim EdgeBundles *Bundles; 73218885Sdim SpillPlacement *SpillPlacer; 74223017Sdim LiveDebugVariables *DebugVars; 75218885Sdim 76218885Sdim // state 77218885Sdim std::auto_ptr<Spiller> SpillerInstance; 78219077Sdim std::priority_queue<std::pair<unsigned, unsigned> > Queue; 79218885Sdim 80221345Sdim // Live ranges pass through a number of stages as we try to allocate them. 81221345Sdim // Some of the stages may also create new live ranges: 82221345Sdim // 83221345Sdim // - Region splitting. 84221345Sdim // - Per-block splitting. 85221345Sdim // - Local splitting. 86221345Sdim // - Spilling. 87221345Sdim // 88221345Sdim // Ranges produced by one of the stages skip the previous stages when they are 89221345Sdim // dequeued. This improves performance because we can skip interference checks 90221345Sdim // that are unlikely to give any results. It also guarantees that the live 91221345Sdim // range splitting algorithm terminates, something that is otherwise hard to 92221345Sdim // ensure. 93221345Sdim enum LiveRangeStage { 94221345Sdim RS_New, ///< Never seen before. 95221345Sdim RS_First, ///< First time in the queue. 96221345Sdim RS_Second, ///< Second time in the queue. 97221345Sdim RS_Global, ///< Produced by global splitting. 98221345Sdim RS_Local, ///< Produced by local splitting. 99221345Sdim RS_Spill ///< Produced by spilling. 100221345Sdim }; 101221345Sdim 102223017Sdim static const char *const StageName[]; 103223017Sdim 104221345Sdim IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage; 105221345Sdim 106221345Sdim LiveRangeStage getStage(const LiveInterval &VirtReg) const { 107221345Sdim return LiveRangeStage(LRStage[VirtReg.reg]); 108221345Sdim } 109221345Sdim 110221345Sdim template<typename Iterator> 111221345Sdim void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 112221345Sdim LRStage.resize(MRI->getNumVirtRegs()); 113221345Sdim for (;Begin != End; ++Begin) { 114221345Sdim unsigned Reg = (*Begin)->reg; 115221345Sdim if (LRStage[Reg] == RS_New) 116221345Sdim LRStage[Reg] = NewStage; 117221345Sdim } 118221345Sdim } 119221345Sdim 120223017Sdim // Eviction. Sometimes an assigned live range can be evicted without 121223017Sdim // conditions, but other times it must be split after being evicted to avoid 122223017Sdim // infinite loops. 123223017Sdim enum CanEvict { 124223017Sdim CE_Never, ///< Can never evict. 125223017Sdim CE_Always, ///< Can always evict. 126223017Sdim CE_WithSplit ///< Can evict only if range is also split or spilled. 127223017Sdim }; 128223017Sdim 129218885Sdim // splitting state. 130221345Sdim std::auto_ptr<SplitAnalysis> SA; 131221345Sdim std::auto_ptr<SplitEditor> SE; 132218885Sdim 133221345Sdim /// Cached per-block interference maps 134221345Sdim InterferenceCache IntfCache; 135218885Sdim 136221345Sdim /// All basic blocks where the current register has uses. 137221345Sdim SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 138221345Sdim 139221345Sdim /// Global live range splitting candidate info. 140221345Sdim struct GlobalSplitCandidate { 141221345Sdim unsigned PhysReg; 142221345Sdim BitVector LiveBundles; 143221345Sdim SmallVector<unsigned, 8> ActiveBlocks; 144221345Sdim 145221345Sdim void reset(unsigned Reg) { 146221345Sdim PhysReg = Reg; 147221345Sdim LiveBundles.clear(); 148221345Sdim ActiveBlocks.clear(); 149221345Sdim } 150221345Sdim }; 151221345Sdim 152221345Sdim /// Candidate info for for each PhysReg in AllocationOrder. 153221345Sdim /// This vector never shrinks, but grows to the size of the largest register 154221345Sdim /// class. 155221345Sdim SmallVector<GlobalSplitCandidate, 32> GlobalCand; 156221345Sdim 157218885Sdimpublic: 158218885Sdim RAGreedy(); 159218885Sdim 160218885Sdim /// Return the pass name. 161218885Sdim virtual const char* getPassName() const { 162218885Sdim return "Greedy Register Allocator"; 163218885Sdim } 164218885Sdim 165218885Sdim /// RAGreedy analysis usage. 166218885Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 167218885Sdim virtual void releaseMemory(); 168218885Sdim virtual Spiller &spiller() { return *SpillerInstance; } 169219077Sdim virtual void enqueue(LiveInterval *LI); 170219077Sdim virtual LiveInterval *dequeue(); 171218885Sdim virtual unsigned selectOrSplit(LiveInterval&, 172218885Sdim SmallVectorImpl<LiveInterval*>&); 173218885Sdim 174218885Sdim /// Perform register allocation. 175218885Sdim virtual bool runOnMachineFunction(MachineFunction &mf); 176218885Sdim 177218885Sdim static char ID; 178218885Sdim 179218885Sdimprivate: 180221345Sdim void LRE_WillEraseInstruction(MachineInstr*); 181221345Sdim bool LRE_CanEraseVirtReg(unsigned); 182221345Sdim void LRE_WillShrinkVirtReg(unsigned); 183221345Sdim void LRE_DidCloneVirtReg(unsigned, unsigned); 184221345Sdim 185221345Sdim float calcSpillCost(); 186221345Sdim bool addSplitConstraints(InterferenceCache::Cursor, float&); 187221345Sdim void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 188221345Sdim void growRegion(GlobalSplitCandidate &Cand, InterferenceCache::Cursor); 189221345Sdim float calcGlobalSplitCost(GlobalSplitCandidate&, InterferenceCache::Cursor); 190221345Sdim void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&, 191218885Sdim SmallVectorImpl<LiveInterval*>&); 192218885Sdim void calcGapWeights(unsigned, SmallVectorImpl<float>&); 193223017Sdim CanEvict canEvict(LiveInterval &A, LiveInterval &B); 194221345Sdim bool canEvictInterference(LiveInterval&, unsigned, float&); 195218885Sdim 196221345Sdim unsigned tryAssign(LiveInterval&, AllocationOrder&, 197221345Sdim SmallVectorImpl<LiveInterval*>&); 198219077Sdim unsigned tryEvict(LiveInterval&, AllocationOrder&, 199221345Sdim SmallVectorImpl<LiveInterval*>&, unsigned = ~0u); 200218885Sdim unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 201218885Sdim SmallVectorImpl<LiveInterval*>&); 202218885Sdim unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 203218885Sdim SmallVectorImpl<LiveInterval*>&); 204218885Sdim unsigned trySplit(LiveInterval&, AllocationOrder&, 205218885Sdim SmallVectorImpl<LiveInterval*>&); 206218885Sdim}; 207218885Sdim} // end anonymous namespace 208218885Sdim 209218885Sdimchar RAGreedy::ID = 0; 210218885Sdim 211223017Sdim#ifndef NDEBUG 212223017Sdimconst char *const RAGreedy::StageName[] = { 213223017Sdim "RS_New", 214223017Sdim "RS_First", 215223017Sdim "RS_Second", 216223017Sdim "RS_Global", 217223017Sdim "RS_Local", 218223017Sdim "RS_Spill" 219223017Sdim}; 220223017Sdim#endif 221223017Sdim 222221345Sdim// Hysteresis to use when comparing floats. 223221345Sdim// This helps stabilize decisions based on float comparisons. 224221345Sdimconst float Hysteresis = 0.98f; 225221345Sdim 226221345Sdim 227218885SdimFunctionPass* llvm::createGreedyRegisterAllocator() { 228218885Sdim return new RAGreedy(); 229218885Sdim} 230218885Sdim 231221345SdimRAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_New) { 232221345Sdim initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 233218885Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 234218885Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 235218885Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 236218885Sdim initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 237218885Sdim initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 238218885Sdim initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 239218885Sdim initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 240218885Sdim initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 241218885Sdim initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 242218885Sdim initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 243218885Sdim initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 244218885Sdim initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 245218885Sdim initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 246218885Sdim} 247218885Sdim 248218885Sdimvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 249218885Sdim AU.setPreservesCFG(); 250218885Sdim AU.addRequired<AliasAnalysis>(); 251218885Sdim AU.addPreserved<AliasAnalysis>(); 252218885Sdim AU.addRequired<LiveIntervals>(); 253218885Sdim AU.addRequired<SlotIndexes>(); 254218885Sdim AU.addPreserved<SlotIndexes>(); 255221345Sdim AU.addRequired<LiveDebugVariables>(); 256221345Sdim AU.addPreserved<LiveDebugVariables>(); 257218885Sdim if (StrongPHIElim) 258218885Sdim AU.addRequiredID(StrongPHIEliminationID); 259218885Sdim AU.addRequiredTransitive<RegisterCoalescer>(); 260218885Sdim AU.addRequired<CalculateSpillWeights>(); 261218885Sdim AU.addRequired<LiveStacks>(); 262218885Sdim AU.addPreserved<LiveStacks>(); 263218885Sdim AU.addRequired<MachineDominatorTree>(); 264218885Sdim AU.addPreserved<MachineDominatorTree>(); 265218885Sdim AU.addRequired<MachineLoopInfo>(); 266218885Sdim AU.addPreserved<MachineLoopInfo>(); 267218885Sdim AU.addRequired<MachineLoopRanges>(); 268218885Sdim AU.addPreserved<MachineLoopRanges>(); 269218885Sdim AU.addRequired<VirtRegMap>(); 270218885Sdim AU.addPreserved<VirtRegMap>(); 271218885Sdim AU.addRequired<EdgeBundles>(); 272218885Sdim AU.addRequired<SpillPlacement>(); 273218885Sdim MachineFunctionPass::getAnalysisUsage(AU); 274218885Sdim} 275218885Sdim 276221345Sdim 277221345Sdim//===----------------------------------------------------------------------===// 278221345Sdim// LiveRangeEdit delegate methods 279221345Sdim//===----------------------------------------------------------------------===// 280221345Sdim 281221345Sdimvoid RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) { 282221345Sdim // LRE itself will remove from SlotIndexes and parent basic block. 283221345Sdim VRM->RemoveMachineInstrFromMaps(MI); 284221345Sdim} 285221345Sdim 286221345Sdimbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 287221345Sdim if (unsigned PhysReg = VRM->getPhys(VirtReg)) { 288221345Sdim unassign(LIS->getInterval(VirtReg), PhysReg); 289221345Sdim return true; 290221345Sdim } 291221345Sdim // Unassigned virtreg is probably in the priority queue. 292221345Sdim // RegAllocBase will erase it after dequeueing. 293221345Sdim return false; 294221345Sdim} 295221345Sdim 296221345Sdimvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 297221345Sdim unsigned PhysReg = VRM->getPhys(VirtReg); 298221345Sdim if (!PhysReg) 299221345Sdim return; 300221345Sdim 301221345Sdim // Register is assigned, put it back on the queue for reassignment. 302221345Sdim LiveInterval &LI = LIS->getInterval(VirtReg); 303221345Sdim unassign(LI, PhysReg); 304221345Sdim enqueue(&LI); 305221345Sdim} 306221345Sdim 307221345Sdimvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 308221345Sdim // LRE may clone a virtual register because dead code elimination causes it to 309221345Sdim // be split into connected components. Ensure that the new register gets the 310221345Sdim // same stage as the parent. 311221345Sdim LRStage.grow(New); 312221345Sdim LRStage[New] = LRStage[Old]; 313221345Sdim} 314221345Sdim 315218885Sdimvoid RAGreedy::releaseMemory() { 316218885Sdim SpillerInstance.reset(0); 317221345Sdim LRStage.clear(); 318221345Sdim GlobalCand.clear(); 319218885Sdim RegAllocBase::releaseMemory(); 320218885Sdim} 321218885Sdim 322219077Sdimvoid RAGreedy::enqueue(LiveInterval *LI) { 323219077Sdim // Prioritize live ranges by size, assigning larger ranges first. 324219077Sdim // The queue holds (size, reg) pairs. 325219077Sdim const unsigned Size = LI->getSize(); 326219077Sdim const unsigned Reg = LI->reg; 327219077Sdim assert(TargetRegisterInfo::isVirtualRegister(Reg) && 328219077Sdim "Can only enqueue virtual registers"); 329219077Sdim unsigned Prio; 330218885Sdim 331221345Sdim LRStage.grow(Reg); 332221345Sdim if (LRStage[Reg] == RS_New) 333221345Sdim LRStage[Reg] = RS_First; 334221345Sdim 335221345Sdim if (LRStage[Reg] == RS_Second) 336221345Sdim // Unsplit ranges that couldn't be allocated immediately are deferred until 337221345Sdim // everything else has been allocated. Long ranges are allocated last so 338221345Sdim // they are split against realistic interference. 339221345Sdim Prio = (1u << 31) - Size; 340221345Sdim else { 341221345Sdim // Everything else is allocated in long->short order. Long ranges that don't 342221345Sdim // fit should be spilled ASAP so they don't create interference. 343219077Sdim Prio = (1u << 31) + Size; 344218885Sdim 345221345Sdim // Boost ranges that have a physical register hint. 346221345Sdim if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg))) 347221345Sdim Prio |= (1u << 30); 348221345Sdim } 349219077Sdim 350219077Sdim Queue.push(std::make_pair(Prio, Reg)); 351218885Sdim} 352218885Sdim 353219077SdimLiveInterval *RAGreedy::dequeue() { 354219077Sdim if (Queue.empty()) 355219077Sdim return 0; 356219077Sdim LiveInterval *LI = &LIS->getInterval(Queue.top().second); 357219077Sdim Queue.pop(); 358219077Sdim return LI; 359219077Sdim} 360218885Sdim 361221345Sdim 362218885Sdim//===----------------------------------------------------------------------===// 363221345Sdim// Direct Assignment 364218885Sdim//===----------------------------------------------------------------------===// 365218885Sdim 366221345Sdim/// tryAssign - Try to assign VirtReg to an available register. 367221345Sdimunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 368221345Sdim AllocationOrder &Order, 369221345Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 370221345Sdim Order.rewind(); 371221345Sdim unsigned PhysReg; 372221345Sdim while ((PhysReg = Order.next())) 373221345Sdim if (!checkPhysRegInterference(VirtReg, PhysReg)) 374221345Sdim break; 375221345Sdim if (!PhysReg || Order.isHint(PhysReg)) 376221345Sdim return PhysReg; 377218885Sdim 378221345Sdim // PhysReg is available. Try to evict interference from a cheaper alternative. 379221345Sdim unsigned Cost = TRI->getCostPerUse(PhysReg); 380218885Sdim 381221345Sdim // Most registers have 0 additional cost. 382221345Sdim if (!Cost) 383221345Sdim return PhysReg; 384218885Sdim 385221345Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 386221345Sdim << '\n'); 387221345Sdim unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 388221345Sdim return CheapReg ? CheapReg : PhysReg; 389218885Sdim} 390218885Sdim 391218885Sdim 392219077Sdim//===----------------------------------------------------------------------===// 393219077Sdim// Interference eviction 394219077Sdim//===----------------------------------------------------------------------===// 395219077Sdim 396223017Sdim/// canEvict - determine if A can evict the assigned live range B. The eviction 397223017Sdim/// policy defined by this function together with the allocation order defined 398223017Sdim/// by enqueue() decides which registers ultimately end up being split and 399223017Sdim/// spilled. 400223017Sdim/// 401223017Sdim/// This function must define a non-circular relation when it returns CE_Always, 402223017Sdim/// otherwise infinite eviction loops are possible. When evicting a <= RS_Second 403223017Sdim/// range, it is possible to return CE_WithSplit which forces the evicted 404223017Sdim/// register to be split or spilled before it can evict anything again. That 405223017Sdim/// guarantees progress. 406223017SdimRAGreedy::CanEvict RAGreedy::canEvict(LiveInterval &A, LiveInterval &B) { 407223017Sdim return A.weight > B.weight ? CE_Always : CE_Never; 408223017Sdim} 409223017Sdim 410219077Sdim/// canEvict - Return true if all interferences between VirtReg and PhysReg can 411221345Sdim/// be evicted. 412221345Sdim/// Return false if any interference is heavier than MaxWeight. 413221345Sdim/// On return, set MaxWeight to the maximal spill weight of an interference. 414219077Sdimbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 415221345Sdim float &MaxWeight) { 416219077Sdim float Weight = 0; 417219077Sdim for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 418219077Sdim LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 419221345Sdim // If there is 10 or more interferences, chances are one is heavier. 420221345Sdim if (Q.collectInterferingVRegs(10, MaxWeight) >= 10) 421219077Sdim return false; 422219077Sdim 423221345Sdim // Check if any interfering live range is heavier than MaxWeight. 424221345Sdim for (unsigned i = Q.interferingVRegs().size(); i; --i) { 425221345Sdim LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 426219077Sdim if (TargetRegisterInfo::isPhysicalRegister(Intf->reg)) 427219077Sdim return false; 428221345Sdim if (Intf->weight >= MaxWeight) 429219077Sdim return false; 430223017Sdim switch (canEvict(VirtReg, *Intf)) { 431223017Sdim case CE_Always: 432223017Sdim break; 433223017Sdim case CE_Never: 434223017Sdim return false; 435223017Sdim case CE_WithSplit: 436223017Sdim if (getStage(*Intf) > RS_Second) 437223017Sdim return false; 438223017Sdim break; 439223017Sdim } 440219077Sdim Weight = std::max(Weight, Intf->weight); 441218885Sdim } 442218885Sdim } 443219077Sdim MaxWeight = Weight; 444219077Sdim return true; 445219077Sdim} 446218885Sdim 447219077Sdim/// tryEvict - Try to evict all interferences for a physreg. 448219077Sdim/// @param VirtReg Currently unassigned virtual register. 449219077Sdim/// @param Order Physregs to try. 450219077Sdim/// @return Physreg to assign VirtReg, or 0. 451219077Sdimunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 452219077Sdim AllocationOrder &Order, 453221345Sdim SmallVectorImpl<LiveInterval*> &NewVRegs, 454221345Sdim unsigned CostPerUseLimit) { 455219077Sdim NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 456219077Sdim 457219077Sdim // Keep track of the lightest single interference seen so far. 458223017Sdim float BestWeight = HUGE_VALF; 459219077Sdim unsigned BestPhys = 0; 460219077Sdim 461219077Sdim Order.rewind(); 462219077Sdim while (unsigned PhysReg = Order.next()) { 463221345Sdim if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 464219077Sdim continue; 465221345Sdim // The first use of a register in a function has cost 1. 466221345Sdim if (CostPerUseLimit == 1 && !MRI->isPhysRegUsed(PhysReg)) 467221345Sdim continue; 468219077Sdim 469221345Sdim float Weight = BestWeight; 470221345Sdim if (!canEvictInterference(VirtReg, PhysReg, Weight)) 471221345Sdim continue; 472221345Sdim 473219077Sdim // This is an eviction candidate. 474221345Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = " 475219077Sdim << Weight << '\n'); 476219077Sdim if (BestPhys && Weight >= BestWeight) 477219077Sdim continue; 478219077Sdim 479219077Sdim // Best so far. 480219077Sdim BestPhys = PhysReg; 481219077Sdim BestWeight = Weight; 482219077Sdim // Stop if the hint can be used. 483219077Sdim if (Order.isHint(PhysReg)) 484219077Sdim break; 485218885Sdim } 486218885Sdim 487219077Sdim if (!BestPhys) 488219077Sdim return 0; 489219077Sdim 490219077Sdim DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n"); 491219077Sdim for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) { 492219077Sdim LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 493219077Sdim assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 494219077Sdim for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 495219077Sdim LiveInterval *Intf = Q.interferingVRegs()[i]; 496219077Sdim unassign(*Intf, VRM->getPhys(Intf->reg)); 497219077Sdim ++NumEvicted; 498219077Sdim NewVRegs.push_back(Intf); 499223017Sdim // Prevent looping by forcing the evicted ranges to be split before they 500223017Sdim // can evict anything else. 501223017Sdim if (getStage(*Intf) < RS_Second && 502223017Sdim canEvict(VirtReg, *Intf) == CE_WithSplit) 503223017Sdim LRStage[Intf->reg] = RS_Second; 504219077Sdim } 505219077Sdim } 506219077Sdim return BestPhys; 507218885Sdim} 508218885Sdim 509218885Sdim 510218885Sdim//===----------------------------------------------------------------------===// 511218885Sdim// Region Splitting 512218885Sdim//===----------------------------------------------------------------------===// 513218885Sdim 514221345Sdim/// addSplitConstraints - Fill out the SplitConstraints vector based on the 515221345Sdim/// interference pattern in Physreg and its aliases. Add the constraints to 516221345Sdim/// SpillPlacement and return the static cost of this split in Cost, assuming 517221345Sdim/// that all preferences in SplitConstraints are met. 518221345Sdim/// Return false if there are no bundles with positive bias. 519221345Sdimbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 520221345Sdim float &Cost) { 521221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 522221345Sdim 523218885Sdim // Reset interference dependent info. 524221345Sdim SplitConstraints.resize(UseBlocks.size()); 525221345Sdim float StaticCost = 0; 526221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 527221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 528221345Sdim SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 529221345Sdim 530218885Sdim BC.Number = BI.MBB->getNumber(); 531221345Sdim Intf.moveToBlock(BC.Number); 532221345Sdim BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 533221345Sdim BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 534218885Sdim 535221345Sdim if (!Intf.hasInterference()) 536218885Sdim continue; 537218885Sdim 538221345Sdim // Number of spill code instructions to insert. 539221345Sdim unsigned Ins = 0; 540218885Sdim 541221345Sdim // Interference for the live-in value. 542221345Sdim if (BI.LiveIn) { 543221345Sdim if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 544221345Sdim BC.Entry = SpillPlacement::MustSpill, ++Ins; 545221345Sdim else if (Intf.first() < BI.FirstUse) 546221345Sdim BC.Entry = SpillPlacement::PrefSpill, ++Ins; 547223017Sdim else if (Intf.first() < BI.LastUse) 548221345Sdim ++Ins; 549221345Sdim } 550218885Sdim 551221345Sdim // Interference for the live-out value. 552221345Sdim if (BI.LiveOut) { 553221345Sdim if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 554221345Sdim BC.Exit = SpillPlacement::MustSpill, ++Ins; 555221345Sdim else if (Intf.last() > BI.LastUse) 556221345Sdim BC.Exit = SpillPlacement::PrefSpill, ++Ins; 557223017Sdim else if (Intf.last() > BI.FirstUse) 558221345Sdim ++Ins; 559218885Sdim } 560218885Sdim 561221345Sdim // Accumulate the total frequency of inserted spill code. 562221345Sdim if (Ins) 563221345Sdim StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 564221345Sdim } 565221345Sdim Cost = StaticCost; 566218885Sdim 567221345Sdim // Add constraints for use-blocks. Note that these are the only constraints 568221345Sdim // that may add a positive bias, it is downhill from here. 569221345Sdim SpillPlacer->addConstraints(SplitConstraints); 570221345Sdim return SpillPlacer->scanActiveBundles(); 571221345Sdim} 572218885Sdim 573218885Sdim 574221345Sdim/// addThroughConstraints - Add constraints and links to SpillPlacer from the 575221345Sdim/// live-through blocks in Blocks. 576221345Sdimvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 577221345Sdim ArrayRef<unsigned> Blocks) { 578221345Sdim const unsigned GroupSize = 8; 579221345Sdim SpillPlacement::BlockConstraint BCS[GroupSize]; 580221345Sdim unsigned TBS[GroupSize]; 581221345Sdim unsigned B = 0, T = 0; 582218885Sdim 583221345Sdim for (unsigned i = 0; i != Blocks.size(); ++i) { 584221345Sdim unsigned Number = Blocks[i]; 585221345Sdim Intf.moveToBlock(Number); 586218885Sdim 587221345Sdim if (!Intf.hasInterference()) { 588221345Sdim assert(T < GroupSize && "Array overflow"); 589221345Sdim TBS[T] = Number; 590221345Sdim if (++T == GroupSize) { 591221345Sdim SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 592221345Sdim T = 0; 593218885Sdim } 594221345Sdim continue; 595221345Sdim } 596218885Sdim 597221345Sdim assert(B < GroupSize && "Array overflow"); 598221345Sdim BCS[B].Number = Number; 599218885Sdim 600221345Sdim // Interference for the live-in value. 601221345Sdim if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 602221345Sdim BCS[B].Entry = SpillPlacement::MustSpill; 603221345Sdim else 604221345Sdim BCS[B].Entry = SpillPlacement::PrefSpill; 605218885Sdim 606221345Sdim // Interference for the live-out value. 607221345Sdim if (Intf.last() >= SA->getLastSplitPoint(Number)) 608221345Sdim BCS[B].Exit = SpillPlacement::MustSpill; 609221345Sdim else 610221345Sdim BCS[B].Exit = SpillPlacement::PrefSpill; 611221345Sdim 612221345Sdim if (++B == GroupSize) { 613221345Sdim ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 614221345Sdim SpillPlacer->addConstraints(Array); 615221345Sdim B = 0; 616218885Sdim } 617218885Sdim } 618218885Sdim 619221345Sdim ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 620221345Sdim SpillPlacer->addConstraints(Array); 621221345Sdim SpillPlacer->addLinks(ArrayRef<unsigned>(TBS, T)); 622221345Sdim} 623218885Sdim 624221345Sdimvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand, 625221345Sdim InterferenceCache::Cursor Intf) { 626221345Sdim // Keep track of through blocks that have not been added to SpillPlacer. 627221345Sdim BitVector Todo = SA->getThroughBlocks(); 628221345Sdim SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 629221345Sdim unsigned AddedTo = 0; 630221345Sdim#ifndef NDEBUG 631221345Sdim unsigned Visited = 0; 632221345Sdim#endif 633218885Sdim 634221345Sdim for (;;) { 635221345Sdim ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 636221345Sdim if (NewBundles.empty()) 637221345Sdim break; 638221345Sdim // Find new through blocks in the periphery of PrefRegBundles. 639221345Sdim for (int i = 0, e = NewBundles.size(); i != e; ++i) { 640221345Sdim unsigned Bundle = NewBundles[i]; 641221345Sdim // Look at all blocks connected to Bundle in the full graph. 642221345Sdim ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 643221345Sdim for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 644221345Sdim I != E; ++I) { 645221345Sdim unsigned Block = *I; 646221345Sdim if (!Todo.test(Block)) 647221345Sdim continue; 648221345Sdim Todo.reset(Block); 649221345Sdim // This is a new through block. Add it to SpillPlacer later. 650221345Sdim ActiveBlocks.push_back(Block); 651221345Sdim#ifndef NDEBUG 652221345Sdim ++Visited; 653221345Sdim#endif 654221345Sdim } 655221345Sdim } 656221345Sdim // Any new blocks to add? 657221345Sdim if (ActiveBlocks.size() > AddedTo) { 658221345Sdim ArrayRef<unsigned> Add(&ActiveBlocks[AddedTo], 659221345Sdim ActiveBlocks.size() - AddedTo); 660221345Sdim addThroughConstraints(Intf, Add); 661221345Sdim AddedTo = ActiveBlocks.size(); 662221345Sdim } 663221345Sdim // Perhaps iterating can enable more bundles? 664221345Sdim SpillPlacer->iterate(); 665221345Sdim } 666221345Sdim DEBUG(dbgs() << ", v=" << Visited); 667221345Sdim} 668218885Sdim 669221345Sdim/// calcSpillCost - Compute how expensive it would be to split the live range in 670221345Sdim/// SA around all use blocks instead of forming bundle regions. 671221345Sdimfloat RAGreedy::calcSpillCost() { 672221345Sdim float Cost = 0; 673221345Sdim const LiveInterval &LI = SA->getParent(); 674221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 675221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 676221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 677221345Sdim unsigned Number = BI.MBB->getNumber(); 678221345Sdim // We normally only need one spill instruction - a load or a store. 679221345Sdim Cost += SpillPlacer->getBlockFrequency(Number); 680221345Sdim 681221345Sdim // Unless the value is redefined in the block. 682221345Sdim if (BI.LiveIn && BI.LiveOut) { 683221345Sdim SlotIndex Start, Stop; 684221345Sdim tie(Start, Stop) = Indexes->getMBBRange(Number); 685221345Sdim LiveInterval::const_iterator I = LI.find(Start); 686221345Sdim assert(I != LI.end() && "Expected live-in value"); 687221345Sdim // Is there a different live-out value? If so, we need an extra spill 688221345Sdim // instruction. 689221345Sdim if (I->end < Stop) 690221345Sdim Cost += SpillPlacer->getBlockFrequency(Number); 691221345Sdim } 692218885Sdim } 693221345Sdim return Cost; 694218885Sdim} 695218885Sdim 696218885Sdim/// calcGlobalSplitCost - Return the global split cost of following the split 697218885Sdim/// pattern in LiveBundles. This cost should be added to the local cost of the 698221345Sdim/// interference pattern in SplitConstraints. 699218885Sdim/// 700221345Sdimfloat RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand, 701221345Sdim InterferenceCache::Cursor Intf) { 702218885Sdim float GlobalCost = 0; 703221345Sdim const BitVector &LiveBundles = Cand.LiveBundles; 704221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 705221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 706221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 707221345Sdim SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 708221345Sdim bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 709221345Sdim bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 710221345Sdim unsigned Ins = 0; 711221345Sdim 712221345Sdim if (BI.LiveIn) 713221345Sdim Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 714221345Sdim if (BI.LiveOut) 715221345Sdim Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 716221345Sdim if (Ins) 717221345Sdim GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number); 718218885Sdim } 719221345Sdim 720221345Sdim for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 721221345Sdim unsigned Number = Cand.ActiveBlocks[i]; 722221345Sdim bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 723221345Sdim bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 724221345Sdim if (!RegIn && !RegOut) 725221345Sdim continue; 726221345Sdim if (RegIn && RegOut) { 727221345Sdim // We need double spill code if this block has interference. 728221345Sdim Intf.moveToBlock(Number); 729221345Sdim if (Intf.hasInterference()) 730221345Sdim GlobalCost += 2*SpillPlacer->getBlockFrequency(Number); 731221345Sdim continue; 732221345Sdim } 733221345Sdim // live-in / stack-out or stack-in live-out. 734221345Sdim GlobalCost += SpillPlacer->getBlockFrequency(Number); 735221345Sdim } 736218885Sdim return GlobalCost; 737218885Sdim} 738218885Sdim 739218885Sdim/// splitAroundRegion - Split VirtReg around the region determined by 740218885Sdim/// LiveBundles. Make an effort to avoid interference from PhysReg. 741218885Sdim/// 742218885Sdim/// The 'register' interval is going to contain as many uses as possible while 743218885Sdim/// avoiding interference. The 'stack' interval is the complement constructed by 744218885Sdim/// SplitEditor. It will contain the rest. 745218885Sdim/// 746221345Sdimvoid RAGreedy::splitAroundRegion(LiveInterval &VirtReg, 747221345Sdim GlobalSplitCandidate &Cand, 748218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 749221345Sdim const BitVector &LiveBundles = Cand.LiveBundles; 750221345Sdim 751218885Sdim DEBUG({ 752221345Sdim dbgs() << "Splitting around region for " << PrintReg(Cand.PhysReg, TRI) 753218885Sdim << " with bundles"; 754218885Sdim for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 755218885Sdim dbgs() << " EB#" << i; 756218885Sdim dbgs() << ".\n"; 757218885Sdim }); 758218885Sdim 759221345Sdim InterferenceCache::Cursor Intf(IntfCache, Cand.PhysReg); 760221345Sdim LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 761221345Sdim SE->reset(LREdit); 762218885Sdim 763218885Sdim // Create the main cross-block interval. 764221345Sdim const unsigned MainIntv = SE->openIntv(); 765218885Sdim 766218885Sdim // First add all defs that are live out of a block. 767221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 768221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 769221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 770218885Sdim bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 771218885Sdim bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 772218885Sdim 773221345Sdim // Create separate intervals for isolated blocks with multiple uses. 774221345Sdim if (!RegIn && !RegOut && BI.FirstUse != BI.LastUse) { 775221345Sdim DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 776221345Sdim SE->splitSingleBlock(BI); 777221345Sdim SE->selectIntv(MainIntv); 778221345Sdim continue; 779221345Sdim } 780221345Sdim 781218885Sdim // Should the register be live out? 782218885Sdim if (!BI.LiveOut || !RegOut) 783218885Sdim continue; 784218885Sdim 785218885Sdim SlotIndex Start, Stop; 786218885Sdim tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 787221345Sdim Intf.moveToBlock(BI.MBB->getNumber()); 788218885Sdim DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 789218885Sdim << Bundles->getBundle(BI.MBB->getNumber(), 1) 790221345Sdim << " [" << Start << ';' 791221345Sdim << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 792221345Sdim << ") intf [" << Intf.first() << ';' << Intf.last() << ')'); 793218885Sdim 794218885Sdim // The interference interval should either be invalid or overlap MBB. 795221345Sdim assert((!Intf.hasInterference() || Intf.first() < Stop) 796221345Sdim && "Bad interference"); 797221345Sdim assert((!Intf.hasInterference() || Intf.last() > Start) 798221345Sdim && "Bad interference"); 799218885Sdim 800218885Sdim // Check interference leaving the block. 801221345Sdim if (!Intf.hasInterference()) { 802218885Sdim // Block is interference-free. 803218885Sdim DEBUG(dbgs() << ", no interference"); 804218885Sdim if (!BI.LiveThrough) { 805218885Sdim DEBUG(dbgs() << ", not live-through.\n"); 806223017Sdim SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 807218885Sdim continue; 808218885Sdim } 809218885Sdim if (!RegIn) { 810218885Sdim // Block is live-through, but entry bundle is on the stack. 811218885Sdim // Reload just before the first use. 812218885Sdim DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 813221345Sdim SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop); 814218885Sdim continue; 815218885Sdim } 816218885Sdim DEBUG(dbgs() << ", live-through.\n"); 817218885Sdim continue; 818218885Sdim } 819218885Sdim 820218885Sdim // Block has interference. 821221345Sdim DEBUG(dbgs() << ", interference to " << Intf.last()); 822218885Sdim 823223017Sdim if (!BI.LiveThrough && Intf.last() <= BI.FirstUse) { 824218885Sdim // The interference doesn't reach the outgoing segment. 825223017Sdim DEBUG(dbgs() << " doesn't affect def from " << BI.FirstUse << '\n'); 826223017Sdim SE->useIntv(BI.FirstUse, Stop); 827218885Sdim continue; 828218885Sdim } 829218885Sdim 830221345Sdim SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 831221345Sdim if (Intf.last().getBoundaryIndex() < BI.LastUse) { 832218885Sdim // There are interference-free uses at the end of the block. 833218885Sdim // Find the first use that can get the live-out register. 834218885Sdim SmallVectorImpl<SlotIndex>::const_iterator UI = 835218885Sdim std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 836221345Sdim Intf.last().getBoundaryIndex()); 837218885Sdim assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 838218885Sdim SlotIndex Use = *UI; 839218885Sdim assert(Use <= BI.LastUse && "Couldn't find last use"); 840218885Sdim // Only attempt a split befroe the last split point. 841221345Sdim if (Use.getBaseIndex() <= LastSplitPoint) { 842218885Sdim DEBUG(dbgs() << ", free use at " << Use << ".\n"); 843221345Sdim SlotIndex SegStart = SE->enterIntvBefore(Use); 844221345Sdim assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 845221345Sdim assert(SegStart < LastSplitPoint && "Impossible split point"); 846221345Sdim SE->useIntv(SegStart, Stop); 847218885Sdim continue; 848218885Sdim } 849218885Sdim } 850218885Sdim 851218885Sdim // Interference is after the last use. 852218885Sdim DEBUG(dbgs() << " after last use.\n"); 853221345Sdim SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB); 854221345Sdim assert(SegStart >= Intf.last() && "Couldn't avoid interference"); 855218885Sdim } 856218885Sdim 857218885Sdim // Now all defs leading to live bundles are handled, do everything else. 858221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 859221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 860218885Sdim bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 861218885Sdim bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 862218885Sdim 863218885Sdim // Is the register live-in? 864218885Sdim if (!BI.LiveIn || !RegIn) 865218885Sdim continue; 866218885Sdim 867218885Sdim // We have an incoming register. Check for interference. 868218885Sdim SlotIndex Start, Stop; 869218885Sdim tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 870221345Sdim Intf.moveToBlock(BI.MBB->getNumber()); 871218885Sdim DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 872221345Sdim << " -> BB#" << BI.MBB->getNumber() << " [" << Start << ';' 873221345Sdim << SA->getLastSplitPoint(BI.MBB->getNumber()) << '-' << Stop 874221345Sdim << ')'); 875218885Sdim 876218885Sdim // Check interference entering the block. 877221345Sdim if (!Intf.hasInterference()) { 878218885Sdim // Block is interference-free. 879218885Sdim DEBUG(dbgs() << ", no interference"); 880218885Sdim if (!BI.LiveThrough) { 881218885Sdim DEBUG(dbgs() << ", killed in block.\n"); 882223017Sdim SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 883218885Sdim continue; 884218885Sdim } 885218885Sdim if (!RegOut) { 886221345Sdim SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber()); 887218885Sdim // Block is live-through, but exit bundle is on the stack. 888218885Sdim // Spill immediately after the last use. 889221345Sdim if (BI.LastUse < LastSplitPoint) { 890218885Sdim DEBUG(dbgs() << ", uses, stack-out.\n"); 891221345Sdim SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse)); 892218885Sdim continue; 893218885Sdim } 894218885Sdim // The last use is after the last split point, it is probably an 895218885Sdim // indirect jump. 896218885Sdim DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 897221345Sdim << LastSplitPoint << ", stack-out.\n"); 898221345Sdim SlotIndex SegEnd = SE->leaveIntvBefore(LastSplitPoint); 899221345Sdim SE->useIntv(Start, SegEnd); 900218885Sdim // Run a double interval from the split to the last use. 901218885Sdim // This makes it possible to spill the complement without affecting the 902218885Sdim // indirect branch. 903221345Sdim SE->overlapIntv(SegEnd, BI.LastUse); 904218885Sdim continue; 905218885Sdim } 906218885Sdim // Register is live-through. 907218885Sdim DEBUG(dbgs() << ", uses, live-through.\n"); 908221345Sdim SE->useIntv(Start, Stop); 909218885Sdim continue; 910218885Sdim } 911218885Sdim 912218885Sdim // Block has interference. 913221345Sdim DEBUG(dbgs() << ", interference from " << Intf.first()); 914218885Sdim 915223017Sdim if (!BI.LiveThrough && Intf.first() >= BI.LastUse) { 916218885Sdim // The interference doesn't reach the outgoing segment. 917223017Sdim DEBUG(dbgs() << " doesn't affect kill at " << BI.LastUse << '\n'); 918223017Sdim SE->useIntv(Start, BI.LastUse); 919218885Sdim continue; 920218885Sdim } 921218885Sdim 922221345Sdim if (Intf.first().getBaseIndex() > BI.FirstUse) { 923218885Sdim // There are interference-free uses at the beginning of the block. 924218885Sdim // Find the last use that can get the register. 925218885Sdim SmallVectorImpl<SlotIndex>::const_iterator UI = 926218885Sdim std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 927221345Sdim Intf.first().getBaseIndex()); 928218885Sdim assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 929218885Sdim SlotIndex Use = (--UI)->getBoundaryIndex(); 930218885Sdim DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 931221345Sdim SlotIndex SegEnd = SE->leaveIntvAfter(Use); 932221345Sdim assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 933221345Sdim SE->useIntv(Start, SegEnd); 934218885Sdim continue; 935218885Sdim } 936218885Sdim 937218885Sdim // Interference is before the first use. 938218885Sdim DEBUG(dbgs() << " before first use.\n"); 939221345Sdim SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB); 940221345Sdim assert(SegEnd <= Intf.first() && "Couldn't avoid interference"); 941218885Sdim } 942218885Sdim 943221345Sdim // Handle live-through blocks. 944221345Sdim for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 945221345Sdim unsigned Number = Cand.ActiveBlocks[i]; 946221345Sdim bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 947221345Sdim bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 948221345Sdim DEBUG(dbgs() << "Live through BB#" << Number << '\n'); 949221345Sdim if (RegIn && RegOut) { 950221345Sdim Intf.moveToBlock(Number); 951221345Sdim if (!Intf.hasInterference()) { 952221345Sdim SE->useIntv(Indexes->getMBBStartIdx(Number), 953221345Sdim Indexes->getMBBEndIdx(Number)); 954221345Sdim continue; 955221345Sdim } 956221345Sdim } 957221345Sdim MachineBasicBlock *MBB = MF->getBlockNumbered(Number); 958221345Sdim if (RegIn) 959221345Sdim SE->leaveIntvAtTop(*MBB); 960221345Sdim if (RegOut) 961221345Sdim SE->enterIntvAtEnd(*MBB); 962221345Sdim } 963218885Sdim 964218885Sdim ++NumGlobalSplits; 965218885Sdim 966221345Sdim SmallVector<unsigned, 8> IntvMap; 967221345Sdim SE->finish(&IntvMap); 968223017Sdim DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 969223017Sdim 970221345Sdim LRStage.resize(MRI->getNumVirtRegs()); 971223017Sdim unsigned OrigBlocks = SA->getNumLiveBlocks(); 972218885Sdim 973221345Sdim // Sort out the new intervals created by splitting. We get four kinds: 974221345Sdim // - Remainder intervals should not be split again. 975221345Sdim // - Candidate intervals can be assigned to Cand.PhysReg. 976221345Sdim // - Block-local splits are candidates for local splitting. 977221345Sdim // - DCE leftovers should go back on the queue. 978221345Sdim for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 979221345Sdim unsigned Reg = LREdit.get(i)->reg; 980221345Sdim 981221345Sdim // Ignore old intervals from DCE. 982221345Sdim if (LRStage[Reg] != RS_New) 983221345Sdim continue; 984221345Sdim 985221345Sdim // Remainder interval. Don't try splitting again, spill if it doesn't 986221345Sdim // allocate. 987221345Sdim if (IntvMap[i] == 0) { 988221345Sdim LRStage[Reg] = RS_Global; 989221345Sdim continue; 990221345Sdim } 991221345Sdim 992221345Sdim // Main interval. Allow repeated splitting as long as the number of live 993221345Sdim // blocks is strictly decreasing. 994221345Sdim if (IntvMap[i] == MainIntv) { 995221345Sdim if (SA->countLiveBlocks(LREdit.get(i)) >= OrigBlocks) { 996221345Sdim DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 997221345Sdim << " blocks as original.\n"); 998221345Sdim // Don't allow repeated splitting as a safe guard against looping. 999221345Sdim LRStage[Reg] = RS_Global; 1000218885Sdim } 1001221345Sdim continue; 1002221345Sdim } 1003221345Sdim 1004221345Sdim // Other intervals are treated as new. This includes local intervals created 1005221345Sdim // for blocks with multiple uses, and anything created by DCE. 1006218885Sdim } 1007221345Sdim 1008221345Sdim if (VerifyEnabled) 1009221345Sdim MF->verify(this, "After splitting live range around region"); 1010218885Sdim} 1011218885Sdim 1012218885Sdimunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1013218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 1014221345Sdim float BestCost = Hysteresis * calcSpillCost(); 1015221345Sdim DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 1016221345Sdim const unsigned NoCand = ~0u; 1017221345Sdim unsigned BestCand = NoCand; 1018221345Sdim 1019218885Sdim Order.rewind(); 1020221345Sdim for (unsigned Cand = 0; unsigned PhysReg = Order.next(); ++Cand) { 1021221345Sdim if (GlobalCand.size() <= Cand) 1022221345Sdim GlobalCand.resize(Cand+1); 1023221345Sdim GlobalCand[Cand].reset(PhysReg); 1024221345Sdim 1025221345Sdim SpillPlacer->prepare(GlobalCand[Cand].LiveBundles); 1026221345Sdim float Cost; 1027221345Sdim InterferenceCache::Cursor Intf(IntfCache, PhysReg); 1028221345Sdim if (!addSplitConstraints(Intf, Cost)) { 1029221345Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 1030218885Sdim continue; 1031221345Sdim } 1032221345Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1033221345Sdim if (Cost >= BestCost) { 1034221345Sdim DEBUG({ 1035221345Sdim if (BestCand == NoCand) 1036221345Sdim dbgs() << " worse than no bundles\n"; 1037221345Sdim else 1038221345Sdim dbgs() << " worse than " 1039221345Sdim << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1040221345Sdim }); 1041221345Sdim continue; 1042221345Sdim } 1043221345Sdim growRegion(GlobalCand[Cand], Intf); 1044218885Sdim 1045221345Sdim SpillPlacer->finish(); 1046221345Sdim 1047218885Sdim // No live bundles, defer to splitSingleBlocks(). 1048221345Sdim if (!GlobalCand[Cand].LiveBundles.any()) { 1049221345Sdim DEBUG(dbgs() << " no bundles.\n"); 1050218885Sdim continue; 1051221345Sdim } 1052218885Sdim 1053221345Sdim Cost += calcGlobalSplitCost(GlobalCand[Cand], Intf); 1054221345Sdim DEBUG({ 1055221345Sdim dbgs() << ", total = " << Cost << " with bundles"; 1056221345Sdim for (int i = GlobalCand[Cand].LiveBundles.find_first(); i>=0; 1057221345Sdim i = GlobalCand[Cand].LiveBundles.find_next(i)) 1058221345Sdim dbgs() << " EB#" << i; 1059221345Sdim dbgs() << ".\n"; 1060221345Sdim }); 1061221345Sdim if (Cost < BestCost) { 1062221345Sdim BestCand = Cand; 1063221345Sdim BestCost = Hysteresis * Cost; // Prevent rounding effects. 1064218885Sdim } 1065218885Sdim } 1066218885Sdim 1067221345Sdim if (BestCand == NoCand) 1068218885Sdim return 0; 1069218885Sdim 1070221345Sdim splitAroundRegion(VirtReg, GlobalCand[BestCand], NewVRegs); 1071218885Sdim return 0; 1072218885Sdim} 1073218885Sdim 1074218885Sdim 1075218885Sdim//===----------------------------------------------------------------------===// 1076218885Sdim// Local Splitting 1077218885Sdim//===----------------------------------------------------------------------===// 1078218885Sdim 1079218885Sdim 1080218885Sdim/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1081218885Sdim/// in order to use PhysReg between two entries in SA->UseSlots. 1082218885Sdim/// 1083218885Sdim/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1084218885Sdim/// 1085218885Sdimvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1086218885Sdim SmallVectorImpl<float> &GapWeight) { 1087221345Sdim assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1088221345Sdim const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1089218885Sdim const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1090218885Sdim const unsigned NumGaps = Uses.size()-1; 1091218885Sdim 1092218885Sdim // Start and end points for the interference check. 1093218885Sdim SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 1094218885Sdim SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 1095218885Sdim 1096218885Sdim GapWeight.assign(NumGaps, 0.0f); 1097218885Sdim 1098218885Sdim // Add interference from each overlapping register. 1099218885Sdim for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1100218885Sdim if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 1101218885Sdim .checkInterference()) 1102218885Sdim continue; 1103218885Sdim 1104218885Sdim // We know that VirtReg is a continuous interval from FirstUse to LastUse, 1105218885Sdim // so we don't need InterferenceQuery. 1106218885Sdim // 1107218885Sdim // Interference that overlaps an instruction is counted in both gaps 1108218885Sdim // surrounding the instruction. The exception is interference before 1109218885Sdim // StartIdx and after StopIdx. 1110218885Sdim // 1111218885Sdim LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 1112218885Sdim for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1113218885Sdim // Skip the gaps before IntI. 1114218885Sdim while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1115218885Sdim if (++Gap == NumGaps) 1116218885Sdim break; 1117218885Sdim if (Gap == NumGaps) 1118218885Sdim break; 1119218885Sdim 1120218885Sdim // Update the gaps covered by IntI. 1121218885Sdim const float weight = IntI.value()->weight; 1122218885Sdim for (; Gap != NumGaps; ++Gap) { 1123218885Sdim GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1124218885Sdim if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1125218885Sdim break; 1126218885Sdim } 1127218885Sdim if (Gap == NumGaps) 1128218885Sdim break; 1129218885Sdim } 1130218885Sdim } 1131218885Sdim} 1132218885Sdim 1133218885Sdim/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1134218885Sdim/// basic block. 1135218885Sdim/// 1136218885Sdimunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1137218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 1138221345Sdim assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1139221345Sdim const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1140218885Sdim 1141218885Sdim // Note that it is possible to have an interval that is live-in or live-out 1142218885Sdim // while only covering a single block - A phi-def can use undef values from 1143218885Sdim // predecessors, and the block could be a single-block loop. 1144218885Sdim // We don't bother doing anything clever about such a case, we simply assume 1145218885Sdim // that the interval is continuous from FirstUse to LastUse. We should make 1146218885Sdim // sure that we don't do anything illegal to such an interval, though. 1147218885Sdim 1148218885Sdim const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 1149218885Sdim if (Uses.size() <= 2) 1150218885Sdim return 0; 1151218885Sdim const unsigned NumGaps = Uses.size()-1; 1152218885Sdim 1153218885Sdim DEBUG({ 1154218885Sdim dbgs() << "tryLocalSplit: "; 1155218885Sdim for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1156218885Sdim dbgs() << ' ' << SA->UseSlots[i]; 1157218885Sdim dbgs() << '\n'; 1158218885Sdim }); 1159218885Sdim 1160223017Sdim // Since we allow local split results to be split again, there is a risk of 1161223017Sdim // creating infinite loops. It is tempting to require that the new live 1162223017Sdim // ranges have less instructions than the original. That would guarantee 1163223017Sdim // convergence, but it is too strict. A live range with 3 instructions can be 1164223017Sdim // split 2+3 (including the COPY), and we want to allow that. 1165223017Sdim // 1166223017Sdim // Instead we use these rules: 1167223017Sdim // 1168223017Sdim // 1. Allow any split for ranges with getStage() < RS_Local. (Except for the 1169223017Sdim // noop split, of course). 1170223017Sdim // 2. Require progress be made for ranges with getStage() >= RS_Local. All 1171223017Sdim // the new ranges must have fewer instructions than before the split. 1172223017Sdim // 3. New ranges with the same number of instructions are marked RS_Local, 1173223017Sdim // smaller ranges are marked RS_New. 1174223017Sdim // 1175223017Sdim // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1176223017Sdim // excessive splitting and infinite loops. 1177223017Sdim // 1178223017Sdim bool ProgressRequired = getStage(VirtReg) >= RS_Local; 1179218885Sdim 1180223017Sdim // Best split candidate. 1181218885Sdim unsigned BestBefore = NumGaps; 1182218885Sdim unsigned BestAfter = 0; 1183218885Sdim float BestDiff = 0; 1184218885Sdim 1185221345Sdim const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber()); 1186218885Sdim SmallVector<float, 8> GapWeight; 1187218885Sdim 1188218885Sdim Order.rewind(); 1189218885Sdim while (unsigned PhysReg = Order.next()) { 1190218885Sdim // Keep track of the largest spill weight that would need to be evicted in 1191218885Sdim // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1192218885Sdim calcGapWeights(PhysReg, GapWeight); 1193218885Sdim 1194218885Sdim // Try to find the best sequence of gaps to close. 1195218885Sdim // The new spill weight must be larger than any gap interference. 1196218885Sdim 1197218885Sdim // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1198223017Sdim unsigned SplitBefore = 0, SplitAfter = 1; 1199218885Sdim 1200218885Sdim // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1201218885Sdim // It is the spill weight that needs to be evicted. 1202218885Sdim float MaxGap = GapWeight[0]; 1203218885Sdim 1204218885Sdim for (;;) { 1205218885Sdim // Live before/after split? 1206218885Sdim const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1207218885Sdim const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1208218885Sdim 1209218885Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1210218885Sdim << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1211218885Sdim << " i=" << MaxGap); 1212218885Sdim 1213218885Sdim // Stop before the interval gets so big we wouldn't be making progress. 1214218885Sdim if (!LiveBefore && !LiveAfter) { 1215218885Sdim DEBUG(dbgs() << " all\n"); 1216218885Sdim break; 1217218885Sdim } 1218218885Sdim // Should the interval be extended or shrunk? 1219218885Sdim bool Shrink = true; 1220218885Sdim 1221223017Sdim // How many gaps would the new range have? 1222223017Sdim unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1223223017Sdim 1224223017Sdim // Legally, without causing looping? 1225223017Sdim bool Legal = !ProgressRequired || NewGaps < NumGaps; 1226223017Sdim 1227223017Sdim if (Legal && MaxGap < HUGE_VALF) { 1228223017Sdim // Estimate the new spill weight. Each instruction reads or writes the 1229223017Sdim // register. Conservatively assume there are no read-modify-write 1230223017Sdim // instructions. 1231218885Sdim // 1232223017Sdim // Try to guess the size of the new interval. 1233223017Sdim const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1234223017Sdim Uses[SplitBefore].distance(Uses[SplitAfter]) + 1235223017Sdim (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1236218885Sdim // Would this split be possible to allocate? 1237218885Sdim // Never allocate all gaps, we wouldn't be making progress. 1238221345Sdim DEBUG(dbgs() << " w=" << EstWeight); 1239221345Sdim if (EstWeight * Hysteresis >= MaxGap) { 1240218885Sdim Shrink = false; 1241221345Sdim float Diff = EstWeight - MaxGap; 1242218885Sdim if (Diff > BestDiff) { 1243218885Sdim DEBUG(dbgs() << " (best)"); 1244221345Sdim BestDiff = Hysteresis * Diff; 1245218885Sdim BestBefore = SplitBefore; 1246218885Sdim BestAfter = SplitAfter; 1247218885Sdim } 1248218885Sdim } 1249218885Sdim } 1250218885Sdim 1251218885Sdim // Try to shrink. 1252218885Sdim if (Shrink) { 1253223017Sdim if (++SplitBefore < SplitAfter) { 1254218885Sdim DEBUG(dbgs() << " shrink\n"); 1255218885Sdim // Recompute the max when necessary. 1256218885Sdim if (GapWeight[SplitBefore - 1] >= MaxGap) { 1257218885Sdim MaxGap = GapWeight[SplitBefore]; 1258218885Sdim for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1259218885Sdim MaxGap = std::max(MaxGap, GapWeight[i]); 1260218885Sdim } 1261218885Sdim continue; 1262218885Sdim } 1263218885Sdim MaxGap = 0; 1264218885Sdim } 1265218885Sdim 1266218885Sdim // Try to extend the interval. 1267218885Sdim if (SplitAfter >= NumGaps) { 1268218885Sdim DEBUG(dbgs() << " end\n"); 1269218885Sdim break; 1270218885Sdim } 1271218885Sdim 1272218885Sdim DEBUG(dbgs() << " extend\n"); 1273223017Sdim MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1274218885Sdim } 1275218885Sdim } 1276218885Sdim 1277218885Sdim // Didn't find any candidates? 1278218885Sdim if (BestBefore == NumGaps) 1279218885Sdim return 0; 1280218885Sdim 1281218885Sdim DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1282218885Sdim << '-' << Uses[BestAfter] << ", " << BestDiff 1283218885Sdim << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1284218885Sdim 1285221345Sdim LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1286221345Sdim SE->reset(LREdit); 1287218885Sdim 1288221345Sdim SE->openIntv(); 1289221345Sdim SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1290221345Sdim SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1291221345Sdim SE->useIntv(SegStart, SegStop); 1292223017Sdim SmallVector<unsigned, 8> IntvMap; 1293223017Sdim SE->finish(&IntvMap); 1294223017Sdim DebugVars->splitRegister(VirtReg.reg, LREdit.regs()); 1295223017Sdim 1296223017Sdim // If the new range has the same number of instructions as before, mark it as 1297223017Sdim // RS_Local so the next split will be forced to make progress. Otherwise, 1298223017Sdim // leave the new intervals as RS_New so they can compete. 1299223017Sdim bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1300223017Sdim bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1301223017Sdim unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1302223017Sdim if (NewGaps >= NumGaps) { 1303223017Sdim DEBUG(dbgs() << "Tagging non-progress ranges: "); 1304223017Sdim assert(!ProgressRequired && "Didn't make progress when it was required."); 1305223017Sdim LRStage.resize(MRI->getNumVirtRegs()); 1306223017Sdim for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1307223017Sdim if (IntvMap[i] == 1) { 1308223017Sdim LRStage[LREdit.get(i)->reg] = RS_Local; 1309223017Sdim DEBUG(dbgs() << PrintReg(LREdit.get(i)->reg)); 1310223017Sdim } 1311223017Sdim DEBUG(dbgs() << '\n'); 1312223017Sdim } 1313218885Sdim ++NumLocalSplits; 1314218885Sdim 1315218885Sdim return 0; 1316218885Sdim} 1317218885Sdim 1318218885Sdim//===----------------------------------------------------------------------===// 1319218885Sdim// Live Range Splitting 1320218885Sdim//===----------------------------------------------------------------------===// 1321218885Sdim 1322218885Sdim/// trySplit - Try to split VirtReg or one of its interferences, making it 1323218885Sdim/// assignable. 1324218885Sdim/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1325218885Sdimunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1326218885Sdim SmallVectorImpl<LiveInterval*>&NewVRegs) { 1327218885Sdim // Local intervals are handled separately. 1328218885Sdim if (LIS->intervalIsInOneMBB(VirtReg)) { 1329218885Sdim NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1330221345Sdim SA->analyze(&VirtReg); 1331218885Sdim return tryLocalSplit(VirtReg, Order, NewVRegs); 1332218885Sdim } 1333218885Sdim 1334218885Sdim NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1335218885Sdim 1336221345Sdim // Don't iterate global splitting. 1337221345Sdim // Move straight to spilling if this range was produced by a global split. 1338221345Sdim if (getStage(VirtReg) >= RS_Global) 1339221345Sdim return 0; 1340221345Sdim 1341221345Sdim SA->analyze(&VirtReg); 1342221345Sdim 1343223017Sdim // FIXME: SplitAnalysis may repair broken live ranges coming from the 1344223017Sdim // coalescer. That may cause the range to become allocatable which means that 1345223017Sdim // tryRegionSplit won't be making progress. This check should be replaced with 1346223017Sdim // an assertion when the coalescer is fixed. 1347223017Sdim if (SA->didRepairRange()) { 1348223017Sdim // VirtReg has changed, so all cached queries are invalid. 1349223017Sdim invalidateVirtRegs(); 1350223017Sdim if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1351223017Sdim return PhysReg; 1352223017Sdim } 1353223017Sdim 1354218885Sdim // First try to split around a region spanning multiple blocks. 1355218885Sdim unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1356218885Sdim if (PhysReg || !NewVRegs.empty()) 1357218885Sdim return PhysReg; 1358218885Sdim 1359218885Sdim // Then isolate blocks with multiple uses. 1360218885Sdim SplitAnalysis::BlockPtrSet Blocks; 1361218885Sdim if (SA->getMultiUseBlocks(Blocks)) { 1362221345Sdim LiveRangeEdit LREdit(VirtReg, NewVRegs, this); 1363221345Sdim SE->reset(LREdit); 1364221345Sdim SE->splitSingleBlocks(Blocks); 1365221345Sdim setStage(NewVRegs.begin(), NewVRegs.end(), RS_Global); 1366218885Sdim if (VerifyEnabled) 1367218885Sdim MF->verify(this, "After splitting live range around basic blocks"); 1368218885Sdim } 1369218885Sdim 1370218885Sdim // Don't assign any physregs. 1371218885Sdim return 0; 1372218885Sdim} 1373218885Sdim 1374218885Sdim 1375218885Sdim//===----------------------------------------------------------------------===// 1376218885Sdim// Main Entry Point 1377218885Sdim//===----------------------------------------------------------------------===// 1378218885Sdim 1379218885Sdimunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1380218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 1381218885Sdim // First try assigning a free register. 1382223017Sdim AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 1383221345Sdim if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1384218885Sdim return PhysReg; 1385218885Sdim 1386223017Sdim LiveRangeStage Stage = getStage(VirtReg); 1387223017Sdim DEBUG(dbgs() << StageName[Stage] << '\n'); 1388219077Sdim 1389223017Sdim // Try to evict a less worthy live range, but only for ranges from the primary 1390223017Sdim // queue. The RS_Second ranges already failed to do this, and they should not 1391223017Sdim // get a second chance until they have been split. 1392223017Sdim if (Stage != RS_Second) 1393223017Sdim if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1394223017Sdim return PhysReg; 1395223017Sdim 1396218885Sdim assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1397218885Sdim 1398219077Sdim // The first time we see a live range, don't try to split or spill. 1399219077Sdim // Wait until the second time, when all smaller ranges have been allocated. 1400219077Sdim // This gives a better picture of the interference to split around. 1401221345Sdim if (Stage == RS_First) { 1402221345Sdim LRStage[VirtReg.reg] = RS_Second; 1403221345Sdim DEBUG(dbgs() << "wait for second round\n"); 1404219077Sdim NewVRegs.push_back(&VirtReg); 1405219077Sdim return 0; 1406219077Sdim } 1407219077Sdim 1408223017Sdim // If we couldn't allocate a register from spilling, there is probably some 1409223017Sdim // invalid inline assembly. The base class wil report it. 1410223017Sdim if (Stage >= RS_Spill) 1411223017Sdim return ~0u; 1412221345Sdim 1413218885Sdim // Try splitting VirtReg or interferences. 1414218885Sdim unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1415218885Sdim if (PhysReg || !NewVRegs.empty()) 1416218885Sdim return PhysReg; 1417218885Sdim 1418218885Sdim // Finally spill VirtReg itself. 1419218885Sdim NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1420221345Sdim LiveRangeEdit LRE(VirtReg, NewVRegs, this); 1421221345Sdim spiller().spill(LRE); 1422221345Sdim setStage(NewVRegs.begin(), NewVRegs.end(), RS_Spill); 1423218885Sdim 1424221345Sdim if (VerifyEnabled) 1425221345Sdim MF->verify(this, "After spilling"); 1426221345Sdim 1427218885Sdim // The live virtual register requesting allocation was spilled, so tell 1428218885Sdim // the caller not to allocate anything during this round. 1429218885Sdim return 0; 1430218885Sdim} 1431218885Sdim 1432218885Sdimbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1433218885Sdim DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1434218885Sdim << "********** Function: " 1435218885Sdim << ((Value*)mf.getFunction())->getName() << '\n'); 1436218885Sdim 1437218885Sdim MF = &mf; 1438218885Sdim if (VerifyEnabled) 1439218885Sdim MF->verify(this, "Before greedy register allocator"); 1440218885Sdim 1441218885Sdim RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1442218885Sdim Indexes = &getAnalysis<SlotIndexes>(); 1443218885Sdim DomTree = &getAnalysis<MachineDominatorTree>(); 1444218885Sdim SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1445218885Sdim Loops = &getAnalysis<MachineLoopInfo>(); 1446218885Sdim LoopRanges = &getAnalysis<MachineLoopRanges>(); 1447218885Sdim Bundles = &getAnalysis<EdgeBundles>(); 1448218885Sdim SpillPlacer = &getAnalysis<SpillPlacement>(); 1449223017Sdim DebugVars = &getAnalysis<LiveDebugVariables>(); 1450218885Sdim 1451218885Sdim SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1452221345Sdim SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree)); 1453221345Sdim LRStage.clear(); 1454221345Sdim LRStage.resize(MRI->getNumVirtRegs()); 1455221345Sdim IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI); 1456218885Sdim 1457218885Sdim allocatePhysRegs(); 1458218885Sdim addMBBLiveIns(MF); 1459218885Sdim LIS->addKillFlags(); 1460218885Sdim 1461218885Sdim // Run rewriter 1462218885Sdim { 1463218885Sdim NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1464218885Sdim VRM->rewrite(Indexes); 1465218885Sdim } 1466218885Sdim 1467221345Sdim // Write out new DBG_VALUE instructions. 1468223017Sdim DebugVars->emitDebugValues(VRM); 1469221345Sdim 1470218885Sdim // The pass output is in VirtRegMap. Release all the transient data. 1471218885Sdim releaseMemory(); 1472218885Sdim 1473218885Sdim return true; 1474218885Sdim} 1475