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" 16249423Sdim#include "llvm/CodeGen/Passes.h" 17218885Sdim#include "AllocationOrder.h" 18221345Sdim#include "InterferenceCache.h" 19221345Sdim#include "LiveDebugVariables.h" 20218885Sdim#include "RegAllocBase.h" 21249423Sdim#include "SpillPlacement.h" 22218885Sdim#include "Spiller.h" 23218885Sdim#include "SplitKit.h" 24218885Sdim#include "llvm/ADT/Statistic.h" 25218885Sdim#include "llvm/Analysis/AliasAnalysis.h" 26218885Sdim#include "llvm/CodeGen/CalcSpillWeights.h" 27218885Sdim#include "llvm/CodeGen/EdgeBundles.h" 28218885Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 29234353Sdim#include "llvm/CodeGen/LiveRangeEdit.h" 30249423Sdim#include "llvm/CodeGen/LiveRegMatrix.h" 31218885Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 32263508Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 33218885Sdim#include "llvm/CodeGen/MachineDominators.h" 34218885Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 35218885Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 36218885Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 37218885Sdim#include "llvm/CodeGen/RegAllocRegistry.h" 38249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 39249423Sdim#include "llvm/PassAnalysisSupport.h" 40226633Sdim#include "llvm/Support/CommandLine.h" 41218885Sdim#include "llvm/Support/Debug.h" 42218885Sdim#include "llvm/Support/ErrorHandling.h" 43249423Sdim#include "llvm/Support/Timer.h" 44218885Sdim#include "llvm/Support/raw_ostream.h" 45219077Sdim#include <queue> 46219077Sdim 47218885Sdimusing namespace llvm; 48218885Sdim 49218885SdimSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 50218885SdimSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 51218885SdimSTATISTIC(NumEvicted, "Number of interferences evicted"); 52218885Sdim 53226633Sdimstatic cl::opt<SplitEditor::ComplementSpillMode> 54226633SdimSplitSpillMode("split-spill-mode", cl::Hidden, 55226633Sdim cl::desc("Spill mode for splitting live ranges"), 56226633Sdim cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), 57226633Sdim clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), 58226633Sdim clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"), 59226633Sdim clEnumValEnd), 60226633Sdim cl::init(SplitEditor::SM_Partition)); 61226633Sdim 62218885Sdimstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 63218885Sdim createGreedyRegisterAllocator); 64218885Sdim 65218885Sdimnamespace { 66221345Sdimclass RAGreedy : public MachineFunctionPass, 67221345Sdim public RegAllocBase, 68221345Sdim private LiveRangeEdit::Delegate { 69221345Sdim 70218885Sdim // context 71218885Sdim MachineFunction *MF; 72218885Sdim 73218885Sdim // analyses 74218885Sdim SlotIndexes *Indexes; 75263508Sdim MachineBlockFrequencyInfo *MBFI; 76218885Sdim MachineDominatorTree *DomTree; 77218885Sdim MachineLoopInfo *Loops; 78218885Sdim EdgeBundles *Bundles; 79218885Sdim SpillPlacement *SpillPlacer; 80223017Sdim LiveDebugVariables *DebugVars; 81218885Sdim 82218885Sdim // state 83251662Sdim OwningPtr<Spiller> SpillerInstance; 84219077Sdim std::priority_queue<std::pair<unsigned, unsigned> > Queue; 85224145Sdim unsigned NextCascade; 86218885Sdim 87221345Sdim // Live ranges pass through a number of stages as we try to allocate them. 88221345Sdim // Some of the stages may also create new live ranges: 89221345Sdim // 90221345Sdim // - Region splitting. 91221345Sdim // - Per-block splitting. 92221345Sdim // - Local splitting. 93221345Sdim // - Spilling. 94221345Sdim // 95221345Sdim // Ranges produced by one of the stages skip the previous stages when they are 96221345Sdim // dequeued. This improves performance because we can skip interference checks 97221345Sdim // that are unlikely to give any results. It also guarantees that the live 98221345Sdim // range splitting algorithm terminates, something that is otherwise hard to 99221345Sdim // ensure. 100221345Sdim enum LiveRangeStage { 101226633Sdim /// Newly created live range that has never been queued. 102226633Sdim RS_New, 103226633Sdim 104226633Sdim /// Only attempt assignment and eviction. Then requeue as RS_Split. 105226633Sdim RS_Assign, 106226633Sdim 107226633Sdim /// Attempt live range splitting if assignment is impossible. 108226633Sdim RS_Split, 109226633Sdim 110226633Sdim /// Attempt more aggressive live range splitting that is guaranteed to make 111226633Sdim /// progress. This is used for split products that may not be making 112226633Sdim /// progress. 113226633Sdim RS_Split2, 114226633Sdim 115226633Sdim /// Live range will be spilled. No more splitting will be attempted. 116226633Sdim RS_Spill, 117226633Sdim 118226633Sdim /// There is nothing more we can do to this live range. Abort compilation 119226633Sdim /// if it can't be assigned. 120226633Sdim RS_Done 121221345Sdim }; 122221345Sdim 123263508Sdim#ifndef NDEBUG 124223017Sdim static const char *const StageName[]; 125263508Sdim#endif 126223017Sdim 127224145Sdim // RegInfo - Keep additional information about each live range. 128224145Sdim struct RegInfo { 129224145Sdim LiveRangeStage Stage; 130221345Sdim 131224145Sdim // Cascade - Eviction loop prevention. See canEvictInterference(). 132224145Sdim unsigned Cascade; 133224145Sdim 134224145Sdim RegInfo() : Stage(RS_New), Cascade(0) {} 135224145Sdim }; 136224145Sdim 137224145Sdim IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo; 138224145Sdim 139221345Sdim LiveRangeStage getStage(const LiveInterval &VirtReg) const { 140224145Sdim return ExtraRegInfo[VirtReg.reg].Stage; 141221345Sdim } 142221345Sdim 143224145Sdim void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) { 144224145Sdim ExtraRegInfo.resize(MRI->getNumVirtRegs()); 145224145Sdim ExtraRegInfo[VirtReg.reg].Stage = Stage; 146224145Sdim } 147224145Sdim 148221345Sdim template<typename Iterator> 149221345Sdim void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 150224145Sdim ExtraRegInfo.resize(MRI->getNumVirtRegs()); 151221345Sdim for (;Begin != End; ++Begin) { 152263508Sdim unsigned Reg = *Begin; 153224145Sdim if (ExtraRegInfo[Reg].Stage == RS_New) 154224145Sdim ExtraRegInfo[Reg].Stage = NewStage; 155221345Sdim } 156221345Sdim } 157221345Sdim 158224145Sdim /// Cost of evicting interference. 159224145Sdim struct EvictionCost { 160224145Sdim unsigned BrokenHints; ///< Total number of broken hints. 161224145Sdim float MaxWeight; ///< Maximum spill weight evicted. 162224145Sdim 163224145Sdim EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {} 164224145Sdim 165263508Sdim bool isMax() const { return BrokenHints == ~0u; } 166263508Sdim 167224145Sdim bool operator<(const EvictionCost &O) const { 168224145Sdim if (BrokenHints != O.BrokenHints) 169224145Sdim return BrokenHints < O.BrokenHints; 170224145Sdim return MaxWeight < O.MaxWeight; 171224145Sdim } 172223017Sdim }; 173223017Sdim 174218885Sdim // splitting state. 175251662Sdim OwningPtr<SplitAnalysis> SA; 176251662Sdim OwningPtr<SplitEditor> SE; 177218885Sdim 178221345Sdim /// Cached per-block interference maps 179221345Sdim InterferenceCache IntfCache; 180218885Sdim 181221345Sdim /// All basic blocks where the current register has uses. 182221345Sdim SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 183221345Sdim 184221345Sdim /// Global live range splitting candidate info. 185221345Sdim struct GlobalSplitCandidate { 186226633Sdim // Register intended for assignment, or 0. 187221345Sdim unsigned PhysReg; 188226633Sdim 189226633Sdim // SplitKit interval index for this candidate. 190226633Sdim unsigned IntvIdx; 191226633Sdim 192226633Sdim // Interference for PhysReg. 193224145Sdim InterferenceCache::Cursor Intf; 194226633Sdim 195226633Sdim // Bundles where this candidate should be live. 196221345Sdim BitVector LiveBundles; 197221345Sdim SmallVector<unsigned, 8> ActiveBlocks; 198221345Sdim 199224145Sdim void reset(InterferenceCache &Cache, unsigned Reg) { 200221345Sdim PhysReg = Reg; 201226633Sdim IntvIdx = 0; 202224145Sdim Intf.setPhysReg(Cache, Reg); 203221345Sdim LiveBundles.clear(); 204221345Sdim ActiveBlocks.clear(); 205221345Sdim } 206226633Sdim 207226633Sdim // Set B[i] = C for every live bundle where B[i] was NoCand. 208226633Sdim unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 209226633Sdim unsigned Count = 0; 210226633Sdim for (int i = LiveBundles.find_first(); i >= 0; 211226633Sdim i = LiveBundles.find_next(i)) 212226633Sdim if (B[i] == NoCand) { 213226633Sdim B[i] = C; 214226633Sdim Count++; 215226633Sdim } 216226633Sdim return Count; 217226633Sdim } 218221345Sdim }; 219221345Sdim 220221345Sdim /// Candidate info for for each PhysReg in AllocationOrder. 221221345Sdim /// This vector never shrinks, but grows to the size of the largest register 222221345Sdim /// class. 223221345Sdim SmallVector<GlobalSplitCandidate, 32> GlobalCand; 224221345Sdim 225263508Sdim enum LLVM_ENUM_INT_TYPE(unsigned) { NoCand = ~0u }; 226226633Sdim 227226633Sdim /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 228226633Sdim /// NoCand which indicates the stack interval. 229226633Sdim SmallVector<unsigned, 32> BundleCand; 230226633Sdim 231218885Sdimpublic: 232218885Sdim RAGreedy(); 233218885Sdim 234218885Sdim /// Return the pass name. 235218885Sdim virtual const char* getPassName() const { 236218885Sdim return "Greedy Register Allocator"; 237218885Sdim } 238218885Sdim 239218885Sdim /// RAGreedy analysis usage. 240218885Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 241218885Sdim virtual void releaseMemory(); 242218885Sdim virtual Spiller &spiller() { return *SpillerInstance; } 243219077Sdim virtual void enqueue(LiveInterval *LI); 244219077Sdim virtual LiveInterval *dequeue(); 245218885Sdim virtual unsigned selectOrSplit(LiveInterval&, 246263508Sdim SmallVectorImpl<unsigned>&); 247218885Sdim 248218885Sdim /// Perform register allocation. 249218885Sdim virtual bool runOnMachineFunction(MachineFunction &mf); 250218885Sdim 251218885Sdim static char ID; 252218885Sdim 253218885Sdimprivate: 254221345Sdim bool LRE_CanEraseVirtReg(unsigned); 255221345Sdim void LRE_WillShrinkVirtReg(unsigned); 256221345Sdim void LRE_DidCloneVirtReg(unsigned, unsigned); 257221345Sdim 258263508Sdim BlockFrequency calcSpillCost(); 259263508Sdim bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&); 260221345Sdim void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 261224145Sdim void growRegion(GlobalSplitCandidate &Cand); 262263508Sdim BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate&); 263226633Sdim bool calcCompactRegion(GlobalSplitCandidate&); 264226633Sdim void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>); 265218885Sdim void calcGapWeights(unsigned, SmallVectorImpl<float>&); 266263508Sdim unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg); 267224145Sdim bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); 268224145Sdim bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); 269224145Sdim void evictInterference(LiveInterval&, unsigned, 270263508Sdim SmallVectorImpl<unsigned>&); 271218885Sdim 272221345Sdim unsigned tryAssign(LiveInterval&, AllocationOrder&, 273263508Sdim SmallVectorImpl<unsigned>&); 274219077Sdim unsigned tryEvict(LiveInterval&, AllocationOrder&, 275263508Sdim SmallVectorImpl<unsigned>&, unsigned = ~0u); 276218885Sdim unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 277263508Sdim SmallVectorImpl<unsigned>&); 278226633Sdim unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, 279263508Sdim SmallVectorImpl<unsigned>&); 280239462Sdim unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&, 281263508Sdim SmallVectorImpl<unsigned>&); 282218885Sdim unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 283263508Sdim SmallVectorImpl<unsigned>&); 284218885Sdim unsigned trySplit(LiveInterval&, AllocationOrder&, 285263508Sdim SmallVectorImpl<unsigned>&); 286218885Sdim}; 287218885Sdim} // end anonymous namespace 288218885Sdim 289218885Sdimchar RAGreedy::ID = 0; 290218885Sdim 291223017Sdim#ifndef NDEBUG 292223017Sdimconst char *const RAGreedy::StageName[] = { 293226633Sdim "RS_New", 294226633Sdim "RS_Assign", 295226633Sdim "RS_Split", 296226633Sdim "RS_Split2", 297226633Sdim "RS_Spill", 298226633Sdim "RS_Done" 299223017Sdim}; 300223017Sdim#endif 301223017Sdim 302221345Sdim// Hysteresis to use when comparing floats. 303221345Sdim// This helps stabilize decisions based on float comparisons. 304221345Sdimconst float Hysteresis = 0.98f; 305221345Sdim 306221345Sdim 307218885SdimFunctionPass* llvm::createGreedyRegisterAllocator() { 308218885Sdim return new RAGreedy(); 309218885Sdim} 310218885Sdim 311224145SdimRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 312221345Sdim initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 313218885Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 314218885Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 315218885Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 316224145Sdim initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 317234353Sdim initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 318218885Sdim initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 319218885Sdim initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 320218885Sdim initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 321218885Sdim initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 322239462Sdim initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry()); 323218885Sdim initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 324218885Sdim initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 325218885Sdim} 326218885Sdim 327218885Sdimvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 328218885Sdim AU.setPreservesCFG(); 329263508Sdim AU.addRequired<MachineBlockFrequencyInfo>(); 330263508Sdim AU.addPreserved<MachineBlockFrequencyInfo>(); 331218885Sdim AU.addRequired<AliasAnalysis>(); 332218885Sdim AU.addPreserved<AliasAnalysis>(); 333218885Sdim AU.addRequired<LiveIntervals>(); 334239462Sdim AU.addPreserved<LiveIntervals>(); 335218885Sdim AU.addRequired<SlotIndexes>(); 336218885Sdim AU.addPreserved<SlotIndexes>(); 337221345Sdim AU.addRequired<LiveDebugVariables>(); 338221345Sdim AU.addPreserved<LiveDebugVariables>(); 339218885Sdim AU.addRequired<LiveStacks>(); 340218885Sdim AU.addPreserved<LiveStacks>(); 341218885Sdim AU.addRequired<MachineDominatorTree>(); 342218885Sdim AU.addPreserved<MachineDominatorTree>(); 343218885Sdim AU.addRequired<MachineLoopInfo>(); 344218885Sdim AU.addPreserved<MachineLoopInfo>(); 345218885Sdim AU.addRequired<VirtRegMap>(); 346218885Sdim AU.addPreserved<VirtRegMap>(); 347239462Sdim AU.addRequired<LiveRegMatrix>(); 348239462Sdim AU.addPreserved<LiveRegMatrix>(); 349218885Sdim AU.addRequired<EdgeBundles>(); 350218885Sdim AU.addRequired<SpillPlacement>(); 351218885Sdim MachineFunctionPass::getAnalysisUsage(AU); 352218885Sdim} 353218885Sdim 354221345Sdim 355221345Sdim//===----------------------------------------------------------------------===// 356221345Sdim// LiveRangeEdit delegate methods 357221345Sdim//===----------------------------------------------------------------------===// 358221345Sdim 359221345Sdimbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 360239462Sdim if (VRM->hasPhys(VirtReg)) { 361239462Sdim Matrix->unassign(LIS->getInterval(VirtReg)); 362221345Sdim return true; 363221345Sdim } 364221345Sdim // Unassigned virtreg is probably in the priority queue. 365221345Sdim // RegAllocBase will erase it after dequeueing. 366221345Sdim return false; 367221345Sdim} 368221345Sdim 369221345Sdimvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 370239462Sdim if (!VRM->hasPhys(VirtReg)) 371221345Sdim return; 372221345Sdim 373221345Sdim // Register is assigned, put it back on the queue for reassignment. 374221345Sdim LiveInterval &LI = LIS->getInterval(VirtReg); 375239462Sdim Matrix->unassign(LI); 376221345Sdim enqueue(&LI); 377221345Sdim} 378221345Sdim 379221345Sdimvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 380226633Sdim // Cloning a register we haven't even heard about yet? Just ignore it. 381226633Sdim if (!ExtraRegInfo.inBounds(Old)) 382226633Sdim return; 383226633Sdim 384221345Sdim // LRE may clone a virtual register because dead code elimination causes it to 385226633Sdim // be split into connected components. The new components are much smaller 386226633Sdim // than the original, so they should get a new chance at being assigned. 387221345Sdim // same stage as the parent. 388226633Sdim ExtraRegInfo[Old].Stage = RS_Assign; 389224145Sdim ExtraRegInfo.grow(New); 390224145Sdim ExtraRegInfo[New] = ExtraRegInfo[Old]; 391221345Sdim} 392221345Sdim 393218885Sdimvoid RAGreedy::releaseMemory() { 394218885Sdim SpillerInstance.reset(0); 395224145Sdim ExtraRegInfo.clear(); 396221345Sdim GlobalCand.clear(); 397218885Sdim} 398218885Sdim 399219077Sdimvoid RAGreedy::enqueue(LiveInterval *LI) { 400219077Sdim // Prioritize live ranges by size, assigning larger ranges first. 401219077Sdim // The queue holds (size, reg) pairs. 402219077Sdim const unsigned Size = LI->getSize(); 403219077Sdim const unsigned Reg = LI->reg; 404219077Sdim assert(TargetRegisterInfo::isVirtualRegister(Reg) && 405219077Sdim "Can only enqueue virtual registers"); 406219077Sdim unsigned Prio; 407218885Sdim 408224145Sdim ExtraRegInfo.grow(Reg); 409224145Sdim if (ExtraRegInfo[Reg].Stage == RS_New) 410226633Sdim ExtraRegInfo[Reg].Stage = RS_Assign; 411221345Sdim 412226633Sdim if (ExtraRegInfo[Reg].Stage == RS_Split) { 413221345Sdim // Unsplit ranges that couldn't be allocated immediately are deferred until 414226633Sdim // everything else has been allocated. 415226633Sdim Prio = Size; 416226633Sdim } else { 417263508Sdim if (ExtraRegInfo[Reg].Stage == RS_Assign && !LI->empty() && 418263508Sdim LIS->intervalIsInOneMBB(*LI)) { 419263508Sdim // Allocate original local ranges in linear instruction order. Since they 420263508Sdim // are singly defined, this produces optimal coloring in the absence of 421263508Sdim // global interference and other constraints. 422263508Sdim Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex()); 423263508Sdim } 424263508Sdim else { 425263508Sdim // Allocate global and split ranges in long->short order. Long ranges that 426263508Sdim // don't fit should be spilled (or split) ASAP so they don't create 427263508Sdim // interference. Mark a bit to prioritize global above local ranges. 428263508Sdim Prio = (1u << 29) + Size; 429263508Sdim } 430263508Sdim // Mark a higher bit to prioritize global and local above RS_Split. 431263508Sdim Prio |= (1u << 31); 432218885Sdim 433221345Sdim // Boost ranges that have a physical register hint. 434249423Sdim if (VRM->hasKnownPreference(Reg)) 435221345Sdim Prio |= (1u << 30); 436221345Sdim } 437263508Sdim // The virtual register number is a tie breaker for same-sized ranges. 438263508Sdim // Give lower vreg numbers higher priority to assign them first. 439234353Sdim Queue.push(std::make_pair(Prio, ~Reg)); 440218885Sdim} 441218885Sdim 442219077SdimLiveInterval *RAGreedy::dequeue() { 443219077Sdim if (Queue.empty()) 444219077Sdim return 0; 445234353Sdim LiveInterval *LI = &LIS->getInterval(~Queue.top().second); 446219077Sdim Queue.pop(); 447219077Sdim return LI; 448219077Sdim} 449218885Sdim 450221345Sdim 451218885Sdim//===----------------------------------------------------------------------===// 452221345Sdim// Direct Assignment 453218885Sdim//===----------------------------------------------------------------------===// 454218885Sdim 455221345Sdim/// tryAssign - Try to assign VirtReg to an available register. 456221345Sdimunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 457221345Sdim AllocationOrder &Order, 458263508Sdim SmallVectorImpl<unsigned> &NewVRegs) { 459221345Sdim Order.rewind(); 460221345Sdim unsigned PhysReg; 461239462Sdim while ((PhysReg = Order.next())) 462239462Sdim if (!Matrix->checkInterference(VirtReg, PhysReg)) 463221345Sdim break; 464249423Sdim if (!PhysReg || Order.isHint()) 465221345Sdim return PhysReg; 466218885Sdim 467224145Sdim // PhysReg is available, but there may be a better choice. 468224145Sdim 469224145Sdim // If we missed a simple hint, try to cheaply evict interference from the 470224145Sdim // preferred register. 471224145Sdim if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg)) 472239462Sdim if (Order.isHint(Hint)) { 473224145Sdim DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n'); 474224145Sdim EvictionCost MaxCost(1); 475224145Sdim if (canEvictInterference(VirtReg, Hint, true, MaxCost)) { 476224145Sdim evictInterference(VirtReg, Hint, NewVRegs); 477224145Sdim return Hint; 478224145Sdim } 479224145Sdim } 480224145Sdim 481224145Sdim // Try to evict interference from a cheaper alternative. 482221345Sdim unsigned Cost = TRI->getCostPerUse(PhysReg); 483218885Sdim 484221345Sdim // Most registers have 0 additional cost. 485221345Sdim if (!Cost) 486221345Sdim return PhysReg; 487218885Sdim 488221345Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 489221345Sdim << '\n'); 490221345Sdim unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 491221345Sdim return CheapReg ? CheapReg : PhysReg; 492218885Sdim} 493218885Sdim 494218885Sdim 495219077Sdim//===----------------------------------------------------------------------===// 496219077Sdim// Interference eviction 497219077Sdim//===----------------------------------------------------------------------===// 498219077Sdim 499263508Sdimunsigned RAGreedy::canReassign(LiveInterval &VirtReg, unsigned PrevReg) { 500263508Sdim AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 501263508Sdim unsigned PhysReg; 502263508Sdim while ((PhysReg = Order.next())) { 503263508Sdim if (PhysReg == PrevReg) 504263508Sdim continue; 505263508Sdim 506263508Sdim MCRegUnitIterator Units(PhysReg, TRI); 507263508Sdim for (; Units.isValid(); ++Units) { 508263508Sdim // Instantiate a "subquery", not to be confused with the Queries array. 509263508Sdim LiveIntervalUnion::Query subQ(&VirtReg, &Matrix->getLiveUnions()[*Units]); 510263508Sdim if (subQ.checkInterference()) 511263508Sdim break; 512263508Sdim } 513263508Sdim // If no units have interference, break out with the current PhysReg. 514263508Sdim if (!Units.isValid()) 515263508Sdim break; 516263508Sdim } 517263508Sdim if (PhysReg) 518263508Sdim DEBUG(dbgs() << "can reassign: " << VirtReg << " from " 519263508Sdim << PrintReg(PrevReg, TRI) << " to " << PrintReg(PhysReg, TRI) 520263508Sdim << '\n'); 521263508Sdim return PhysReg; 522263508Sdim} 523263508Sdim 524224145Sdim/// shouldEvict - determine if A should evict the assigned live range B. The 525224145Sdim/// eviction policy defined by this function together with the allocation order 526224145Sdim/// defined by enqueue() decides which registers ultimately end up being split 527224145Sdim/// and spilled. 528223017Sdim/// 529224145Sdim/// Cascade numbers are used to prevent infinite loops if this function is a 530224145Sdim/// cyclic relation. 531224145Sdim/// 532224145Sdim/// @param A The live range to be assigned. 533224145Sdim/// @param IsHint True when A is about to be assigned to its preferred 534224145Sdim/// register. 535224145Sdim/// @param B The live range to be evicted. 536224145Sdim/// @param BreaksHint True when B is already assigned to its preferred register. 537224145Sdimbool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint, 538224145Sdim LiveInterval &B, bool BreaksHint) { 539226633Sdim bool CanSplit = getStage(B) < RS_Spill; 540224145Sdim 541224145Sdim // Be fairly aggressive about following hints as long as the evictee can be 542224145Sdim // split. 543224145Sdim if (CanSplit && IsHint && !BreaksHint) 544224145Sdim return true; 545224145Sdim 546224145Sdim return A.weight > B.weight; 547223017Sdim} 548223017Sdim 549224145Sdim/// canEvictInterference - Return true if all interferences between VirtReg and 550224145Sdim/// PhysReg can be evicted. When OnlyCheap is set, don't do anything 551224145Sdim/// 552224145Sdim/// @param VirtReg Live range that is about to be assigned. 553224145Sdim/// @param PhysReg Desired register for assignment. 554243830Sdim/// @param IsHint True when PhysReg is VirtReg's preferred register. 555224145Sdim/// @param MaxCost Only look for cheaper candidates and update with new cost 556224145Sdim/// when returning true. 557224145Sdim/// @returns True when interference can be evicted cheaper than MaxCost. 558219077Sdimbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 559224145Sdim bool IsHint, EvictionCost &MaxCost) { 560239462Sdim // It is only possible to evict virtual register interference. 561239462Sdim if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) 562239462Sdim return false; 563239462Sdim 564263508Sdim bool IsLocal = LIS->intervalIsInOneMBB(VirtReg); 565263508Sdim 566224145Sdim // Find VirtReg's cascade number. This will be unassigned if VirtReg was never 567224145Sdim // involved in an eviction before. If a cascade number was assigned, deny 568224145Sdim // evicting anything with the same or a newer cascade number. This prevents 569224145Sdim // infinite eviction loops. 570224145Sdim // 571224145Sdim // This works out so a register without a cascade number is allowed to evict 572224145Sdim // anything, and it can be evicted by anything. 573224145Sdim unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 574224145Sdim if (!Cascade) 575224145Sdim Cascade = NextCascade; 576224145Sdim 577224145Sdim EvictionCost Cost; 578239462Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 579239462Sdim LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 580221345Sdim // If there is 10 or more interferences, chances are one is heavier. 581224145Sdim if (Q.collectInterferingVRegs(10) >= 10) 582219077Sdim return false; 583219077Sdim 584221345Sdim // Check if any interfering live range is heavier than MaxWeight. 585221345Sdim for (unsigned i = Q.interferingVRegs().size(); i; --i) { 586221345Sdim LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 587239462Sdim assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) && 588239462Sdim "Only expecting virtual register interference from query"); 589224145Sdim // Never evict spill products. They cannot split or spill. 590226633Sdim if (getStage(*Intf) == RS_Done) 591219077Sdim return false; 592224145Sdim // Once a live range becomes small enough, it is urgent that we find a 593224145Sdim // register for it. This is indicated by an infinite spill weight. These 594224145Sdim // urgent live ranges get to evict almost anything. 595239462Sdim // 596239462Sdim // Also allow urgent evictions of unspillable ranges from a strictly 597239462Sdim // larger allocation order. 598239462Sdim bool Urgent = !VirtReg.isSpillable() && 599239462Sdim (Intf->isSpillable() || 600239462Sdim RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) < 601239462Sdim RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg))); 602224145Sdim // Only evict older cascades or live ranges without a cascade. 603224145Sdim unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade; 604224145Sdim if (Cascade <= IntfCascade) { 605224145Sdim if (!Urgent) 606223017Sdim return false; 607224145Sdim // We permit breaking cascades for urgent evictions. It should be the 608224145Sdim // last resort, though, so make it really expensive. 609224145Sdim Cost.BrokenHints += 10; 610223017Sdim } 611224145Sdim // Would this break a satisfied hint? 612224145Sdim bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); 613224145Sdim // Update eviction cost. 614224145Sdim Cost.BrokenHints += BreaksHint; 615224145Sdim Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); 616224145Sdim // Abort if this would be too expensive. 617224145Sdim if (!(Cost < MaxCost)) 618224145Sdim return false; 619263508Sdim if (Urgent) 620263508Sdim continue; 621263508Sdim // If !MaxCost.isMax(), then we're just looking for a cheap register. 622263508Sdim // Evicting another local live range in this case could lead to suboptimal 623263508Sdim // coloring. 624263508Sdim if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) && 625263508Sdim !canReassign(*Intf, PhysReg)) { 626263508Sdim return false; 627263508Sdim } 628224145Sdim // Finally, apply the eviction policy for non-urgent evictions. 629263508Sdim if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint)) 630224145Sdim return false; 631218885Sdim } 632218885Sdim } 633224145Sdim MaxCost = Cost; 634219077Sdim return true; 635219077Sdim} 636218885Sdim 637224145Sdim/// evictInterference - Evict any interferring registers that prevent VirtReg 638224145Sdim/// from being assigned to Physreg. This assumes that canEvictInterference 639224145Sdim/// returned true. 640224145Sdimvoid RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg, 641263508Sdim SmallVectorImpl<unsigned> &NewVRegs) { 642224145Sdim // Make sure that VirtReg has a cascade number, and assign that cascade 643224145Sdim // number to every evicted register. These live ranges than then only be 644224145Sdim // evicted by a newer cascade, preventing infinite loops. 645224145Sdim unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 646224145Sdim if (!Cascade) 647224145Sdim Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++; 648224145Sdim 649224145Sdim DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI) 650224145Sdim << " interference: Cascade " << Cascade << '\n'); 651239462Sdim 652239462Sdim // Collect all interfering virtregs first. 653239462Sdim SmallVector<LiveInterval*, 8> Intfs; 654239462Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 655239462Sdim LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 656224145Sdim assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 657239462Sdim ArrayRef<LiveInterval*> IVR = Q.interferingVRegs(); 658239462Sdim Intfs.append(IVR.begin(), IVR.end()); 659224145Sdim } 660239462Sdim 661239462Sdim // Evict them second. This will invalidate the queries. 662239462Sdim for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { 663239462Sdim LiveInterval *Intf = Intfs[i]; 664239462Sdim // The same VirtReg may be present in multiple RegUnits. Skip duplicates. 665239462Sdim if (!VRM->hasPhys(Intf->reg)) 666239462Sdim continue; 667239462Sdim Matrix->unassign(*Intf); 668239462Sdim assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || 669239462Sdim VirtReg.isSpillable() < Intf->isSpillable()) && 670239462Sdim "Cannot decrease cascade number, illegal eviction"); 671239462Sdim ExtraRegInfo[Intf->reg].Cascade = Cascade; 672239462Sdim ++NumEvicted; 673263508Sdim NewVRegs.push_back(Intf->reg); 674239462Sdim } 675224145Sdim} 676224145Sdim 677219077Sdim/// tryEvict - Try to evict all interferences for a physreg. 678219077Sdim/// @param VirtReg Currently unassigned virtual register. 679219077Sdim/// @param Order Physregs to try. 680219077Sdim/// @return Physreg to assign VirtReg, or 0. 681219077Sdimunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 682219077Sdim AllocationOrder &Order, 683263508Sdim SmallVectorImpl<unsigned> &NewVRegs, 684221345Sdim unsigned CostPerUseLimit) { 685219077Sdim NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 686219077Sdim 687224145Sdim // Keep track of the cheapest interference seen so far. 688224145Sdim EvictionCost BestCost(~0u); 689219077Sdim unsigned BestPhys = 0; 690249423Sdim unsigned OrderLimit = Order.getOrder().size(); 691219077Sdim 692224145Sdim // When we are just looking for a reduced cost per use, don't break any 693224145Sdim // hints, and only evict smaller spill weights. 694224145Sdim if (CostPerUseLimit < ~0u) { 695224145Sdim BestCost.BrokenHints = 0; 696224145Sdim BestCost.MaxWeight = VirtReg.weight; 697249423Sdim 698249423Sdim // Check of any registers in RC are below CostPerUseLimit. 699249423Sdim const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg); 700249423Sdim unsigned MinCost = RegClassInfo.getMinCost(RC); 701249423Sdim if (MinCost >= CostPerUseLimit) { 702249423Sdim DEBUG(dbgs() << RC->getName() << " minimum cost = " << MinCost 703249423Sdim << ", no cheaper registers to be found.\n"); 704249423Sdim return 0; 705249423Sdim } 706249423Sdim 707249423Sdim // It is normal for register classes to have a long tail of registers with 708249423Sdim // the same cost. We don't need to look at them if they're too expensive. 709249423Sdim if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) { 710249423Sdim OrderLimit = RegClassInfo.getLastCostChange(RC); 711249423Sdim DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n"); 712249423Sdim } 713224145Sdim } 714224145Sdim 715219077Sdim Order.rewind(); 716249423Sdim while (unsigned PhysReg = Order.nextWithDups(OrderLimit)) { 717221345Sdim if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 718219077Sdim continue; 719224145Sdim // The first use of a callee-saved register in a function has cost 1. 720224145Sdim // Don't start using a CSR when the CostPerUseLimit is low. 721224145Sdim if (CostPerUseLimit == 1) 722224145Sdim if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg)) 723224145Sdim if (!MRI->isPhysRegUsed(CSR)) { 724224145Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR " 725224145Sdim << PrintReg(CSR, TRI) << '\n'); 726224145Sdim continue; 727224145Sdim } 728219077Sdim 729224145Sdim if (!canEvictInterference(VirtReg, PhysReg, false, BestCost)) 730221345Sdim continue; 731221345Sdim 732219077Sdim // Best so far. 733219077Sdim BestPhys = PhysReg; 734224145Sdim 735219077Sdim // Stop if the hint can be used. 736249423Sdim if (Order.isHint()) 737219077Sdim break; 738218885Sdim } 739218885Sdim 740219077Sdim if (!BestPhys) 741219077Sdim return 0; 742219077Sdim 743224145Sdim evictInterference(VirtReg, BestPhys, NewVRegs); 744219077Sdim return BestPhys; 745218885Sdim} 746218885Sdim 747218885Sdim 748218885Sdim//===----------------------------------------------------------------------===// 749218885Sdim// Region Splitting 750218885Sdim//===----------------------------------------------------------------------===// 751218885Sdim 752221345Sdim/// addSplitConstraints - Fill out the SplitConstraints vector based on the 753221345Sdim/// interference pattern in Physreg and its aliases. Add the constraints to 754221345Sdim/// SpillPlacement and return the static cost of this split in Cost, assuming 755221345Sdim/// that all preferences in SplitConstraints are met. 756221345Sdim/// Return false if there are no bundles with positive bias. 757221345Sdimbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 758263508Sdim BlockFrequency &Cost) { 759221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 760221345Sdim 761218885Sdim // Reset interference dependent info. 762221345Sdim SplitConstraints.resize(UseBlocks.size()); 763263508Sdim BlockFrequency StaticCost = 0; 764221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 765221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 766221345Sdim SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 767221345Sdim 768218885Sdim BC.Number = BI.MBB->getNumber(); 769221345Sdim Intf.moveToBlock(BC.Number); 770221345Sdim BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 771221345Sdim BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 772263508Sdim BC.ChangesValue = BI.FirstDef.isValid(); 773218885Sdim 774221345Sdim if (!Intf.hasInterference()) 775218885Sdim continue; 776218885Sdim 777221345Sdim // Number of spill code instructions to insert. 778221345Sdim unsigned Ins = 0; 779218885Sdim 780221345Sdim // Interference for the live-in value. 781221345Sdim if (BI.LiveIn) { 782221345Sdim if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 783221345Sdim BC.Entry = SpillPlacement::MustSpill, ++Ins; 784226633Sdim else if (Intf.first() < BI.FirstInstr) 785221345Sdim BC.Entry = SpillPlacement::PrefSpill, ++Ins; 786226633Sdim else if (Intf.first() < BI.LastInstr) 787221345Sdim ++Ins; 788221345Sdim } 789218885Sdim 790221345Sdim // Interference for the live-out value. 791221345Sdim if (BI.LiveOut) { 792221345Sdim if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 793221345Sdim BC.Exit = SpillPlacement::MustSpill, ++Ins; 794226633Sdim else if (Intf.last() > BI.LastInstr) 795221345Sdim BC.Exit = SpillPlacement::PrefSpill, ++Ins; 796226633Sdim else if (Intf.last() > BI.FirstInstr) 797221345Sdim ++Ins; 798218885Sdim } 799218885Sdim 800221345Sdim // Accumulate the total frequency of inserted spill code. 801263508Sdim while (Ins--) 802263508Sdim StaticCost += SpillPlacer->getBlockFrequency(BC.Number); 803221345Sdim } 804221345Sdim Cost = StaticCost; 805218885Sdim 806221345Sdim // Add constraints for use-blocks. Note that these are the only constraints 807221345Sdim // that may add a positive bias, it is downhill from here. 808221345Sdim SpillPlacer->addConstraints(SplitConstraints); 809221345Sdim return SpillPlacer->scanActiveBundles(); 810221345Sdim} 811218885Sdim 812218885Sdim 813221345Sdim/// addThroughConstraints - Add constraints and links to SpillPlacer from the 814221345Sdim/// live-through blocks in Blocks. 815221345Sdimvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 816221345Sdim ArrayRef<unsigned> Blocks) { 817221345Sdim const unsigned GroupSize = 8; 818221345Sdim SpillPlacement::BlockConstraint BCS[GroupSize]; 819221345Sdim unsigned TBS[GroupSize]; 820221345Sdim unsigned B = 0, T = 0; 821218885Sdim 822221345Sdim for (unsigned i = 0; i != Blocks.size(); ++i) { 823221345Sdim unsigned Number = Blocks[i]; 824221345Sdim Intf.moveToBlock(Number); 825218885Sdim 826221345Sdim if (!Intf.hasInterference()) { 827221345Sdim assert(T < GroupSize && "Array overflow"); 828221345Sdim TBS[T] = Number; 829221345Sdim if (++T == GroupSize) { 830226633Sdim SpillPlacer->addLinks(makeArrayRef(TBS, T)); 831221345Sdim T = 0; 832218885Sdim } 833221345Sdim continue; 834221345Sdim } 835218885Sdim 836221345Sdim assert(B < GroupSize && "Array overflow"); 837221345Sdim BCS[B].Number = Number; 838218885Sdim 839221345Sdim // Interference for the live-in value. 840221345Sdim if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 841221345Sdim BCS[B].Entry = SpillPlacement::MustSpill; 842221345Sdim else 843221345Sdim BCS[B].Entry = SpillPlacement::PrefSpill; 844218885Sdim 845221345Sdim // Interference for the live-out value. 846221345Sdim if (Intf.last() >= SA->getLastSplitPoint(Number)) 847221345Sdim BCS[B].Exit = SpillPlacement::MustSpill; 848221345Sdim else 849221345Sdim BCS[B].Exit = SpillPlacement::PrefSpill; 850221345Sdim 851221345Sdim if (++B == GroupSize) { 852221345Sdim ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 853221345Sdim SpillPlacer->addConstraints(Array); 854221345Sdim B = 0; 855218885Sdim } 856218885Sdim } 857218885Sdim 858221345Sdim ArrayRef<SpillPlacement::BlockConstraint> Array(BCS, B); 859221345Sdim SpillPlacer->addConstraints(Array); 860226633Sdim SpillPlacer->addLinks(makeArrayRef(TBS, T)); 861221345Sdim} 862218885Sdim 863224145Sdimvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand) { 864221345Sdim // Keep track of through blocks that have not been added to SpillPlacer. 865221345Sdim BitVector Todo = SA->getThroughBlocks(); 866221345Sdim SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 867221345Sdim unsigned AddedTo = 0; 868221345Sdim#ifndef NDEBUG 869221345Sdim unsigned Visited = 0; 870221345Sdim#endif 871218885Sdim 872221345Sdim for (;;) { 873221345Sdim ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 874221345Sdim // Find new through blocks in the periphery of PrefRegBundles. 875221345Sdim for (int i = 0, e = NewBundles.size(); i != e; ++i) { 876221345Sdim unsigned Bundle = NewBundles[i]; 877221345Sdim // Look at all blocks connected to Bundle in the full graph. 878221345Sdim ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 879221345Sdim for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 880221345Sdim I != E; ++I) { 881221345Sdim unsigned Block = *I; 882221345Sdim if (!Todo.test(Block)) 883221345Sdim continue; 884221345Sdim Todo.reset(Block); 885221345Sdim // This is a new through block. Add it to SpillPlacer later. 886221345Sdim ActiveBlocks.push_back(Block); 887221345Sdim#ifndef NDEBUG 888221345Sdim ++Visited; 889221345Sdim#endif 890221345Sdim } 891221345Sdim } 892221345Sdim // Any new blocks to add? 893224145Sdim if (ActiveBlocks.size() == AddedTo) 894224145Sdim break; 895226633Sdim 896226633Sdim // Compute through constraints from the interference, or assume that all 897226633Sdim // through blocks prefer spilling when forming compact regions. 898226633Sdim ArrayRef<unsigned> NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo); 899226633Sdim if (Cand.PhysReg) 900226633Sdim addThroughConstraints(Cand.Intf, NewBlocks); 901226633Sdim else 902226633Sdim // Provide a strong negative bias on through blocks to prevent unwanted 903226633Sdim // liveness on loop backedges. 904226633Sdim SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); 905224145Sdim AddedTo = ActiveBlocks.size(); 906224145Sdim 907221345Sdim // Perhaps iterating can enable more bundles? 908221345Sdim SpillPlacer->iterate(); 909221345Sdim } 910221345Sdim DEBUG(dbgs() << ", v=" << Visited); 911221345Sdim} 912218885Sdim 913226633Sdim/// calcCompactRegion - Compute the set of edge bundles that should be live 914226633Sdim/// when splitting the current live range into compact regions. Compact 915226633Sdim/// regions can be computed without looking at interference. They are the 916226633Sdim/// regions formed by removing all the live-through blocks from the live range. 917226633Sdim/// 918226633Sdim/// Returns false if the current live range is already compact, or if the 919226633Sdim/// compact regions would form single block regions anyway. 920226633Sdimbool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { 921226633Sdim // Without any through blocks, the live range is already compact. 922226633Sdim if (!SA->getNumThroughBlocks()) 923226633Sdim return false; 924226633Sdim 925226633Sdim // Compact regions don't correspond to any physreg. 926226633Sdim Cand.reset(IntfCache, 0); 927226633Sdim 928226633Sdim DEBUG(dbgs() << "Compact region bundles"); 929226633Sdim 930226633Sdim // Use the spill placer to determine the live bundles. GrowRegion pretends 931226633Sdim // that all the through blocks have interference when PhysReg is unset. 932226633Sdim SpillPlacer->prepare(Cand.LiveBundles); 933226633Sdim 934226633Sdim // The static split cost will be zero since Cand.Intf reports no interference. 935263508Sdim BlockFrequency Cost; 936226633Sdim if (!addSplitConstraints(Cand.Intf, Cost)) { 937226633Sdim DEBUG(dbgs() << ", none.\n"); 938226633Sdim return false; 939226633Sdim } 940226633Sdim 941226633Sdim growRegion(Cand); 942226633Sdim SpillPlacer->finish(); 943226633Sdim 944226633Sdim if (!Cand.LiveBundles.any()) { 945226633Sdim DEBUG(dbgs() << ", none.\n"); 946226633Sdim return false; 947226633Sdim } 948226633Sdim 949226633Sdim DEBUG({ 950226633Sdim for (int i = Cand.LiveBundles.find_first(); i>=0; 951226633Sdim i = Cand.LiveBundles.find_next(i)) 952226633Sdim dbgs() << " EB#" << i; 953226633Sdim dbgs() << ".\n"; 954226633Sdim }); 955226633Sdim return true; 956226633Sdim} 957226633Sdim 958221345Sdim/// calcSpillCost - Compute how expensive it would be to split the live range in 959221345Sdim/// SA around all use blocks instead of forming bundle regions. 960263508SdimBlockFrequency RAGreedy::calcSpillCost() { 961263508Sdim BlockFrequency Cost = 0; 962221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 963221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 964221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 965221345Sdim unsigned Number = BI.MBB->getNumber(); 966221345Sdim // We normally only need one spill instruction - a load or a store. 967221345Sdim Cost += SpillPlacer->getBlockFrequency(Number); 968221345Sdim 969221345Sdim // Unless the value is redefined in the block. 970226633Sdim if (BI.LiveIn && BI.LiveOut && BI.FirstDef) 971226633Sdim Cost += SpillPlacer->getBlockFrequency(Number); 972218885Sdim } 973221345Sdim return Cost; 974218885Sdim} 975218885Sdim 976218885Sdim/// calcGlobalSplitCost - Return the global split cost of following the split 977218885Sdim/// pattern in LiveBundles. This cost should be added to the local cost of the 978221345Sdim/// interference pattern in SplitConstraints. 979218885Sdim/// 980263508SdimBlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { 981263508Sdim BlockFrequency GlobalCost = 0; 982221345Sdim const BitVector &LiveBundles = Cand.LiveBundles; 983221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 984221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 985221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 986221345Sdim SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 987221345Sdim bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 988221345Sdim bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 989221345Sdim unsigned Ins = 0; 990221345Sdim 991221345Sdim if (BI.LiveIn) 992221345Sdim Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 993221345Sdim if (BI.LiveOut) 994221345Sdim Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 995263508Sdim while (Ins--) 996263508Sdim GlobalCost += SpillPlacer->getBlockFrequency(BC.Number); 997218885Sdim } 998221345Sdim 999221345Sdim for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 1000221345Sdim unsigned Number = Cand.ActiveBlocks[i]; 1001221345Sdim bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 1002221345Sdim bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 1003221345Sdim if (!RegIn && !RegOut) 1004221345Sdim continue; 1005221345Sdim if (RegIn && RegOut) { 1006221345Sdim // We need double spill code if this block has interference. 1007224145Sdim Cand.Intf.moveToBlock(Number); 1008263508Sdim if (Cand.Intf.hasInterference()) { 1009263508Sdim GlobalCost += SpillPlacer->getBlockFrequency(Number); 1010263508Sdim GlobalCost += SpillPlacer->getBlockFrequency(Number); 1011263508Sdim } 1012221345Sdim continue; 1013221345Sdim } 1014221345Sdim // live-in / stack-out or stack-in live-out. 1015221345Sdim GlobalCost += SpillPlacer->getBlockFrequency(Number); 1016221345Sdim } 1017218885Sdim return GlobalCost; 1018218885Sdim} 1019218885Sdim 1020226633Sdim/// splitAroundRegion - Split the current live range around the regions 1021226633Sdim/// determined by BundleCand and GlobalCand. 1022218885Sdim/// 1023226633Sdim/// Before calling this function, GlobalCand and BundleCand must be initialized 1024226633Sdim/// so each bundle is assigned to a valid candidate, or NoCand for the 1025226633Sdim/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor 1026226633Sdim/// objects must be initialized for the current live range, and intervals 1027226633Sdim/// created for the used candidates. 1028218885Sdim/// 1029226633Sdim/// @param LREdit The LiveRangeEdit object handling the current split. 1030226633Sdim/// @param UsedCands List of used GlobalCand entries. Every BundleCand value 1031226633Sdim/// must appear in this list. 1032226633Sdimvoid RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, 1033226633Sdim ArrayRef<unsigned> UsedCands) { 1034226633Sdim // These are the intervals created for new global ranges. We may create more 1035226633Sdim // intervals for local ranges. 1036226633Sdim const unsigned NumGlobalIntvs = LREdit.size(); 1037226633Sdim DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n"); 1038226633Sdim assert(NumGlobalIntvs && "No global intervals configured"); 1039221345Sdim 1040226633Sdim // Isolate even single instructions when dealing with a proper sub-class. 1041226633Sdim // That guarantees register class inflation for the stack interval because it 1042226633Sdim // is all copies. 1043226633Sdim unsigned Reg = SA->getParent().reg; 1044226633Sdim bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 1045218885Sdim 1046224145Sdim // First handle all the blocks with uses. 1047221345Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1048221345Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1049221345Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1050226633Sdim unsigned Number = BI.MBB->getNumber(); 1051226633Sdim unsigned IntvIn = 0, IntvOut = 0; 1052226633Sdim SlotIndex IntfIn, IntfOut; 1053226633Sdim if (BI.LiveIn) { 1054226633Sdim unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 1055226633Sdim if (CandIn != NoCand) { 1056226633Sdim GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 1057226633Sdim IntvIn = Cand.IntvIdx; 1058226633Sdim Cand.Intf.moveToBlock(Number); 1059226633Sdim IntfIn = Cand.Intf.first(); 1060226633Sdim } 1061226633Sdim } 1062226633Sdim if (BI.LiveOut) { 1063226633Sdim unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 1064226633Sdim if (CandOut != NoCand) { 1065226633Sdim GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 1066226633Sdim IntvOut = Cand.IntvIdx; 1067226633Sdim Cand.Intf.moveToBlock(Number); 1068226633Sdim IntfOut = Cand.Intf.last(); 1069226633Sdim } 1070226633Sdim } 1071218885Sdim 1072221345Sdim // Create separate intervals for isolated blocks with multiple uses. 1073226633Sdim if (!IntvIn && !IntvOut) { 1074221345Sdim DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 1075226633Sdim if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1076224145Sdim SE->splitSingleBlock(BI); 1077218885Sdim continue; 1078218885Sdim } 1079218885Sdim 1080226633Sdim if (IntvIn && IntvOut) 1081226633Sdim SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 1082226633Sdim else if (IntvIn) 1083226633Sdim SE->splitRegInBlock(BI, IntvIn, IntfIn); 1084224145Sdim else 1085226633Sdim SE->splitRegOutBlock(BI, IntvOut, IntfOut); 1086218885Sdim } 1087218885Sdim 1088226633Sdim // Handle live-through blocks. The relevant live-through blocks are stored in 1089226633Sdim // the ActiveBlocks list with each candidate. We need to filter out 1090226633Sdim // duplicates. 1091226633Sdim BitVector Todo = SA->getThroughBlocks(); 1092226633Sdim for (unsigned c = 0; c != UsedCands.size(); ++c) { 1093226633Sdim ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks; 1094226633Sdim for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 1095226633Sdim unsigned Number = Blocks[i]; 1096226633Sdim if (!Todo.test(Number)) 1097226633Sdim continue; 1098226633Sdim Todo.reset(Number); 1099226633Sdim 1100226633Sdim unsigned IntvIn = 0, IntvOut = 0; 1101226633Sdim SlotIndex IntfIn, IntfOut; 1102226633Sdim 1103226633Sdim unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 1104226633Sdim if (CandIn != NoCand) { 1105226633Sdim GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 1106226633Sdim IntvIn = Cand.IntvIdx; 1107226633Sdim Cand.Intf.moveToBlock(Number); 1108226633Sdim IntfIn = Cand.Intf.first(); 1109226633Sdim } 1110226633Sdim 1111226633Sdim unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 1112226633Sdim if (CandOut != NoCand) { 1113226633Sdim GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 1114226633Sdim IntvOut = Cand.IntvIdx; 1115226633Sdim Cand.Intf.moveToBlock(Number); 1116226633Sdim IntfOut = Cand.Intf.last(); 1117226633Sdim } 1118226633Sdim if (!IntvIn && !IntvOut) 1119226633Sdim continue; 1120226633Sdim SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 1121226633Sdim } 1122221345Sdim } 1123218885Sdim 1124218885Sdim ++NumGlobalSplits; 1125218885Sdim 1126221345Sdim SmallVector<unsigned, 8> IntvMap; 1127221345Sdim SE->finish(&IntvMap); 1128263508Sdim DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); 1129223017Sdim 1130224145Sdim ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1131223017Sdim unsigned OrigBlocks = SA->getNumLiveBlocks(); 1132218885Sdim 1133221345Sdim // Sort out the new intervals created by splitting. We get four kinds: 1134221345Sdim // - Remainder intervals should not be split again. 1135221345Sdim // - Candidate intervals can be assigned to Cand.PhysReg. 1136221345Sdim // - Block-local splits are candidates for local splitting. 1137221345Sdim // - DCE leftovers should go back on the queue. 1138221345Sdim for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1139263508Sdim LiveInterval &Reg = LIS->getInterval(LREdit.get(i)); 1140221345Sdim 1141221345Sdim // Ignore old intervals from DCE. 1142224145Sdim if (getStage(Reg) != RS_New) 1143221345Sdim continue; 1144221345Sdim 1145221345Sdim // Remainder interval. Don't try splitting again, spill if it doesn't 1146221345Sdim // allocate. 1147221345Sdim if (IntvMap[i] == 0) { 1148226633Sdim setStage(Reg, RS_Spill); 1149221345Sdim continue; 1150221345Sdim } 1151221345Sdim 1152226633Sdim // Global intervals. Allow repeated splitting as long as the number of live 1153221345Sdim // blocks is strictly decreasing. 1154226633Sdim if (IntvMap[i] < NumGlobalIntvs) { 1155224145Sdim if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { 1156221345Sdim DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 1157221345Sdim << " blocks as original.\n"); 1158221345Sdim // Don't allow repeated splitting as a safe guard against looping. 1159226633Sdim setStage(Reg, RS_Split2); 1160218885Sdim } 1161221345Sdim continue; 1162221345Sdim } 1163221345Sdim 1164221345Sdim // Other intervals are treated as new. This includes local intervals created 1165221345Sdim // for blocks with multiple uses, and anything created by DCE. 1166218885Sdim } 1167221345Sdim 1168221345Sdim if (VerifyEnabled) 1169221345Sdim MF->verify(this, "After splitting live range around region"); 1170218885Sdim} 1171218885Sdim 1172218885Sdimunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1173263508Sdim SmallVectorImpl<unsigned> &NewVRegs) { 1174226633Sdim unsigned NumCands = 0; 1175221345Sdim unsigned BestCand = NoCand; 1176263508Sdim BlockFrequency BestCost; 1177226633Sdim SmallVector<unsigned, 8> UsedCands; 1178221345Sdim 1179226633Sdim // Check if we can split this live range around a compact region. 1180226633Sdim bool HasCompact = calcCompactRegion(GlobalCand.front()); 1181226633Sdim if (HasCompact) { 1182226633Sdim // Yes, keep GlobalCand[0] as the compact region candidate. 1183226633Sdim NumCands = 1; 1184263508Sdim BestCost = BlockFrequency::getMaxFrequency(); 1185226633Sdim } else { 1186226633Sdim // No benefit from the compact region, our fallback will be per-block 1187226633Sdim // splitting. Make sure we find a solution that is cheaper than spilling. 1188263508Sdim BestCost = calcSpillCost(); 1189226633Sdim DEBUG(dbgs() << "Cost of isolating all blocks = " << BestCost << '\n'); 1190226633Sdim } 1191226633Sdim 1192218885Sdim Order.rewind(); 1193224145Sdim while (unsigned PhysReg = Order.next()) { 1194224145Sdim // Discard bad candidates before we run out of interference cache cursors. 1195224145Sdim // This will only affect register classes with a lot of registers (>32). 1196224145Sdim if (NumCands == IntfCache.getMaxCursors()) { 1197224145Sdim unsigned WorstCount = ~0u; 1198224145Sdim unsigned Worst = 0; 1199224145Sdim for (unsigned i = 0; i != NumCands; ++i) { 1200226633Sdim if (i == BestCand || !GlobalCand[i].PhysReg) 1201224145Sdim continue; 1202224145Sdim unsigned Count = GlobalCand[i].LiveBundles.count(); 1203224145Sdim if (Count < WorstCount) 1204224145Sdim Worst = i, WorstCount = Count; 1205224145Sdim } 1206224145Sdim --NumCands; 1207224145Sdim GlobalCand[Worst] = GlobalCand[NumCands]; 1208234353Sdim if (BestCand == NumCands) 1209234353Sdim BestCand = Worst; 1210224145Sdim } 1211221345Sdim 1212224145Sdim if (GlobalCand.size() <= NumCands) 1213224145Sdim GlobalCand.resize(NumCands+1); 1214224145Sdim GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1215224145Sdim Cand.reset(IntfCache, PhysReg); 1216224145Sdim 1217224145Sdim SpillPlacer->prepare(Cand.LiveBundles); 1218263508Sdim BlockFrequency Cost; 1219224145Sdim if (!addSplitConstraints(Cand.Intf, Cost)) { 1220221345Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 1221218885Sdim continue; 1222221345Sdim } 1223221345Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost); 1224221345Sdim if (Cost >= BestCost) { 1225221345Sdim DEBUG({ 1226221345Sdim if (BestCand == NoCand) 1227221345Sdim dbgs() << " worse than no bundles\n"; 1228221345Sdim else 1229221345Sdim dbgs() << " worse than " 1230221345Sdim << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1231221345Sdim }); 1232221345Sdim continue; 1233221345Sdim } 1234224145Sdim growRegion(Cand); 1235218885Sdim 1236221345Sdim SpillPlacer->finish(); 1237221345Sdim 1238218885Sdim // No live bundles, defer to splitSingleBlocks(). 1239224145Sdim if (!Cand.LiveBundles.any()) { 1240221345Sdim DEBUG(dbgs() << " no bundles.\n"); 1241218885Sdim continue; 1242221345Sdim } 1243218885Sdim 1244224145Sdim Cost += calcGlobalSplitCost(Cand); 1245221345Sdim DEBUG({ 1246221345Sdim dbgs() << ", total = " << Cost << " with bundles"; 1247224145Sdim for (int i = Cand.LiveBundles.find_first(); i>=0; 1248224145Sdim i = Cand.LiveBundles.find_next(i)) 1249221345Sdim dbgs() << " EB#" << i; 1250221345Sdim dbgs() << ".\n"; 1251221345Sdim }); 1252221345Sdim if (Cost < BestCost) { 1253224145Sdim BestCand = NumCands; 1254263508Sdim BestCost = Cost; 1255218885Sdim } 1256224145Sdim ++NumCands; 1257218885Sdim } 1258218885Sdim 1259226633Sdim // No solutions found, fall back to single block splitting. 1260226633Sdim if (!HasCompact && BestCand == NoCand) 1261218885Sdim return 0; 1262218885Sdim 1263226633Sdim // Prepare split editor. 1264239462Sdim LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1265226633Sdim SE->reset(LREdit, SplitSpillMode); 1266226633Sdim 1267226633Sdim // Assign all edge bundles to the preferred candidate, or NoCand. 1268226633Sdim BundleCand.assign(Bundles->getNumBundles(), NoCand); 1269226633Sdim 1270226633Sdim // Assign bundles for the best candidate region. 1271226633Sdim if (BestCand != NoCand) { 1272226633Sdim GlobalSplitCandidate &Cand = GlobalCand[BestCand]; 1273226633Sdim if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { 1274226633Sdim UsedCands.push_back(BestCand); 1275226633Sdim Cand.IntvIdx = SE->openIntv(); 1276226633Sdim DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in " 1277226633Sdim << B << " bundles, intv " << Cand.IntvIdx << ".\n"); 1278226633Sdim (void)B; 1279226633Sdim } 1280226633Sdim } 1281226633Sdim 1282226633Sdim // Assign bundles for the compact region. 1283226633Sdim if (HasCompact) { 1284226633Sdim GlobalSplitCandidate &Cand = GlobalCand.front(); 1285226633Sdim assert(!Cand.PhysReg && "Compact region has no physreg"); 1286226633Sdim if (unsigned B = Cand.getBundles(BundleCand, 0)) { 1287226633Sdim UsedCands.push_back(0); 1288226633Sdim Cand.IntvIdx = SE->openIntv(); 1289226633Sdim DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv " 1290226633Sdim << Cand.IntvIdx << ".\n"); 1291226633Sdim (void)B; 1292226633Sdim } 1293226633Sdim } 1294226633Sdim 1295226633Sdim splitAroundRegion(LREdit, UsedCands); 1296218885Sdim return 0; 1297218885Sdim} 1298218885Sdim 1299218885Sdim 1300218885Sdim//===----------------------------------------------------------------------===// 1301226633Sdim// Per-Block Splitting 1302226633Sdim//===----------------------------------------------------------------------===// 1303226633Sdim 1304226633Sdim/// tryBlockSplit - Split a global live range around every block with uses. This 1305226633Sdim/// creates a lot of local live ranges, that will be split by tryLocalSplit if 1306226633Sdim/// they don't allocate. 1307226633Sdimunsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1308263508Sdim SmallVectorImpl<unsigned> &NewVRegs) { 1309226633Sdim assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); 1310226633Sdim unsigned Reg = VirtReg.reg; 1311226633Sdim bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 1312239462Sdim LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1313226633Sdim SE->reset(LREdit, SplitSpillMode); 1314226633Sdim ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1315226633Sdim for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1316226633Sdim const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1317226633Sdim if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1318226633Sdim SE->splitSingleBlock(BI); 1319226633Sdim } 1320226633Sdim // No blocks were split. 1321226633Sdim if (LREdit.empty()) 1322226633Sdim return 0; 1323226633Sdim 1324226633Sdim // We did split for some blocks. 1325226633Sdim SmallVector<unsigned, 8> IntvMap; 1326226633Sdim SE->finish(&IntvMap); 1327226633Sdim 1328226633Sdim // Tell LiveDebugVariables about the new ranges. 1329263508Sdim DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); 1330226633Sdim 1331226633Sdim ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1332226633Sdim 1333226633Sdim // Sort out the new intervals created by splitting. The remainder interval 1334226633Sdim // goes straight to spilling, the new local ranges get to stay RS_New. 1335226633Sdim for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1336263508Sdim LiveInterval &LI = LIS->getInterval(LREdit.get(i)); 1337226633Sdim if (getStage(LI) == RS_New && IntvMap[i] == 0) 1338226633Sdim setStage(LI, RS_Spill); 1339226633Sdim } 1340226633Sdim 1341226633Sdim if (VerifyEnabled) 1342226633Sdim MF->verify(this, "After splitting live range around basic blocks"); 1343226633Sdim return 0; 1344226633Sdim} 1345226633Sdim 1346239462Sdim 1347226633Sdim//===----------------------------------------------------------------------===// 1348239462Sdim// Per-Instruction Splitting 1349239462Sdim//===----------------------------------------------------------------------===// 1350239462Sdim 1351239462Sdim/// tryInstructionSplit - Split a live range around individual instructions. 1352239462Sdim/// This is normally not worthwhile since the spiller is doing essentially the 1353239462Sdim/// same thing. However, when the live range is in a constrained register 1354239462Sdim/// class, it may help to insert copies such that parts of the live range can 1355239462Sdim/// be moved to a larger register class. 1356239462Sdim/// 1357239462Sdim/// This is similar to spilling to a larger register class. 1358239462Sdimunsigned 1359239462SdimRAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1360263508Sdim SmallVectorImpl<unsigned> &NewVRegs) { 1361239462Sdim // There is no point to this if there are no larger sub-classes. 1362239462Sdim if (!RegClassInfo.isProperSubClass(MRI->getRegClass(VirtReg.reg))) 1363239462Sdim return 0; 1364239462Sdim 1365239462Sdim // Always enable split spill mode, since we're effectively spilling to a 1366239462Sdim // register. 1367239462Sdim LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1368239462Sdim SE->reset(LREdit, SplitEditor::SM_Size); 1369239462Sdim 1370239462Sdim ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1371239462Sdim if (Uses.size() <= 1) 1372239462Sdim return 0; 1373239462Sdim 1374239462Sdim DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n"); 1375239462Sdim 1376239462Sdim // Split around every non-copy instruction. 1377239462Sdim for (unsigned i = 0; i != Uses.size(); ++i) { 1378239462Sdim if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i])) 1379239462Sdim if (MI->isFullCopy()) { 1380239462Sdim DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI); 1381239462Sdim continue; 1382239462Sdim } 1383239462Sdim SE->openIntv(); 1384239462Sdim SlotIndex SegStart = SE->enterIntvBefore(Uses[i]); 1385239462Sdim SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]); 1386239462Sdim SE->useIntv(SegStart, SegStop); 1387239462Sdim } 1388239462Sdim 1389239462Sdim if (LREdit.empty()) { 1390239462Sdim DEBUG(dbgs() << "All uses were copies.\n"); 1391239462Sdim return 0; 1392239462Sdim } 1393239462Sdim 1394239462Sdim SmallVector<unsigned, 8> IntvMap; 1395239462Sdim SE->finish(&IntvMap); 1396263508Sdim DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS); 1397239462Sdim ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1398239462Sdim 1399239462Sdim // Assign all new registers to RS_Spill. This was the last chance. 1400239462Sdim setStage(LREdit.begin(), LREdit.end(), RS_Spill); 1401239462Sdim return 0; 1402239462Sdim} 1403239462Sdim 1404239462Sdim 1405239462Sdim//===----------------------------------------------------------------------===// 1406218885Sdim// Local Splitting 1407218885Sdim//===----------------------------------------------------------------------===// 1408218885Sdim 1409218885Sdim 1410218885Sdim/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1411218885Sdim/// in order to use PhysReg between two entries in SA->UseSlots. 1412218885Sdim/// 1413218885Sdim/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1414218885Sdim/// 1415218885Sdimvoid RAGreedy::calcGapWeights(unsigned PhysReg, 1416218885Sdim SmallVectorImpl<float> &GapWeight) { 1417221345Sdim assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1418221345Sdim const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1419234353Sdim ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1420218885Sdim const unsigned NumGaps = Uses.size()-1; 1421218885Sdim 1422218885Sdim // Start and end points for the interference check. 1423226633Sdim SlotIndex StartIdx = 1424226633Sdim BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr; 1425226633Sdim SlotIndex StopIdx = 1426226633Sdim BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr; 1427218885Sdim 1428218885Sdim GapWeight.assign(NumGaps, 0.0f); 1429218885Sdim 1430218885Sdim // Add interference from each overlapping register. 1431239462Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1432239462Sdim if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units) 1433239462Sdim .checkInterference()) 1434218885Sdim continue; 1435218885Sdim 1436226633Sdim // We know that VirtReg is a continuous interval from FirstInstr to 1437226633Sdim // LastInstr, so we don't need InterferenceQuery. 1438218885Sdim // 1439218885Sdim // Interference that overlaps an instruction is counted in both gaps 1440218885Sdim // surrounding the instruction. The exception is interference before 1441218885Sdim // StartIdx and after StopIdx. 1442218885Sdim // 1443239462Sdim LiveIntervalUnion::SegmentIter IntI = 1444239462Sdim Matrix->getLiveUnions()[*Units] .find(StartIdx); 1445218885Sdim for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1446218885Sdim // Skip the gaps before IntI. 1447218885Sdim while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1448218885Sdim if (++Gap == NumGaps) 1449218885Sdim break; 1450218885Sdim if (Gap == NumGaps) 1451218885Sdim break; 1452218885Sdim 1453218885Sdim // Update the gaps covered by IntI. 1454218885Sdim const float weight = IntI.value()->weight; 1455218885Sdim for (; Gap != NumGaps; ++Gap) { 1456218885Sdim GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1457218885Sdim if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1458218885Sdim break; 1459218885Sdim } 1460218885Sdim if (Gap == NumGaps) 1461218885Sdim break; 1462218885Sdim } 1463218885Sdim } 1464239462Sdim 1465239462Sdim // Add fixed interference. 1466239462Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1467263508Sdim const LiveRange &LR = LIS->getRegUnit(*Units); 1468263508Sdim LiveRange::const_iterator I = LR.find(StartIdx); 1469263508Sdim LiveRange::const_iterator E = LR.end(); 1470239462Sdim 1471239462Sdim // Same loop as above. Mark any overlapped gaps as HUGE_VALF. 1472239462Sdim for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) { 1473239462Sdim while (Uses[Gap+1].getBoundaryIndex() < I->start) 1474239462Sdim if (++Gap == NumGaps) 1475239462Sdim break; 1476239462Sdim if (Gap == NumGaps) 1477239462Sdim break; 1478239462Sdim 1479239462Sdim for (; Gap != NumGaps; ++Gap) { 1480263508Sdim GapWeight[Gap] = llvm::huge_valf; 1481239462Sdim if (Uses[Gap+1].getBaseIndex() >= I->end) 1482239462Sdim break; 1483239462Sdim } 1484239462Sdim if (Gap == NumGaps) 1485239462Sdim break; 1486239462Sdim } 1487239462Sdim } 1488218885Sdim} 1489218885Sdim 1490218885Sdim/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1491218885Sdim/// basic block. 1492218885Sdim/// 1493218885Sdimunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1494263508Sdim SmallVectorImpl<unsigned> &NewVRegs) { 1495221345Sdim assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1496221345Sdim const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1497218885Sdim 1498218885Sdim // Note that it is possible to have an interval that is live-in or live-out 1499218885Sdim // while only covering a single block - A phi-def can use undef values from 1500218885Sdim // predecessors, and the block could be a single-block loop. 1501218885Sdim // We don't bother doing anything clever about such a case, we simply assume 1502226633Sdim // that the interval is continuous from FirstInstr to LastInstr. We should 1503226633Sdim // make sure that we don't do anything illegal to such an interval, though. 1504218885Sdim 1505234353Sdim ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1506218885Sdim if (Uses.size() <= 2) 1507218885Sdim return 0; 1508218885Sdim const unsigned NumGaps = Uses.size()-1; 1509218885Sdim 1510218885Sdim DEBUG({ 1511218885Sdim dbgs() << "tryLocalSplit: "; 1512218885Sdim for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1513234353Sdim dbgs() << ' ' << Uses[i]; 1514218885Sdim dbgs() << '\n'; 1515218885Sdim }); 1516218885Sdim 1517234353Sdim // If VirtReg is live across any register mask operands, compute a list of 1518234353Sdim // gaps with register masks. 1519234353Sdim SmallVector<unsigned, 8> RegMaskGaps; 1520239462Sdim if (Matrix->checkRegMaskInterference(VirtReg)) { 1521234353Sdim // Get regmask slots for the whole block. 1522234353Sdim ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber()); 1523234353Sdim DEBUG(dbgs() << RMS.size() << " regmasks in block:"); 1524234353Sdim // Constrain to VirtReg's live range. 1525234353Sdim unsigned ri = std::lower_bound(RMS.begin(), RMS.end(), 1526234353Sdim Uses.front().getRegSlot()) - RMS.begin(); 1527234353Sdim unsigned re = RMS.size(); 1528234353Sdim for (unsigned i = 0; i != NumGaps && ri != re; ++i) { 1529234353Sdim // Look for Uses[i] <= RMS <= Uses[i+1]. 1530234353Sdim assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i])); 1531234353Sdim if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri])) 1532234353Sdim continue; 1533234353Sdim // Skip a regmask on the same instruction as the last use. It doesn't 1534234353Sdim // overlap the live range. 1535234353Sdim if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps) 1536234353Sdim break; 1537234353Sdim DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]); 1538234353Sdim RegMaskGaps.push_back(i); 1539234353Sdim // Advance ri to the next gap. A regmask on one of the uses counts in 1540234353Sdim // both gaps. 1541234353Sdim while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1])) 1542234353Sdim ++ri; 1543234353Sdim } 1544234353Sdim DEBUG(dbgs() << '\n'); 1545234353Sdim } 1546234353Sdim 1547223017Sdim // Since we allow local split results to be split again, there is a risk of 1548223017Sdim // creating infinite loops. It is tempting to require that the new live 1549223017Sdim // ranges have less instructions than the original. That would guarantee 1550223017Sdim // convergence, but it is too strict. A live range with 3 instructions can be 1551223017Sdim // split 2+3 (including the COPY), and we want to allow that. 1552223017Sdim // 1553223017Sdim // Instead we use these rules: 1554223017Sdim // 1555226633Sdim // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the 1556223017Sdim // noop split, of course). 1557226633Sdim // 2. Require progress be made for ranges with getStage() == RS_Split2. All 1558223017Sdim // the new ranges must have fewer instructions than before the split. 1559226633Sdim // 3. New ranges with the same number of instructions are marked RS_Split2, 1560223017Sdim // smaller ranges are marked RS_New. 1561223017Sdim // 1562223017Sdim // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1563223017Sdim // excessive splitting and infinite loops. 1564223017Sdim // 1565226633Sdim bool ProgressRequired = getStage(VirtReg) >= RS_Split2; 1566218885Sdim 1567223017Sdim // Best split candidate. 1568218885Sdim unsigned BestBefore = NumGaps; 1569218885Sdim unsigned BestAfter = 0; 1570218885Sdim float BestDiff = 0; 1571218885Sdim 1572263508Sdim const float blockFreq = 1573263508Sdim SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() * 1574263508Sdim (1.0f / BlockFrequency::getEntryFrequency()); 1575218885Sdim SmallVector<float, 8> GapWeight; 1576218885Sdim 1577218885Sdim Order.rewind(); 1578218885Sdim while (unsigned PhysReg = Order.next()) { 1579218885Sdim // Keep track of the largest spill weight that would need to be evicted in 1580218885Sdim // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1581218885Sdim calcGapWeights(PhysReg, GapWeight); 1582218885Sdim 1583234353Sdim // Remove any gaps with regmask clobbers. 1584239462Sdim if (Matrix->checkRegMaskInterference(VirtReg, PhysReg)) 1585234353Sdim for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i) 1586263508Sdim GapWeight[RegMaskGaps[i]] = llvm::huge_valf; 1587234353Sdim 1588218885Sdim // Try to find the best sequence of gaps to close. 1589218885Sdim // The new spill weight must be larger than any gap interference. 1590218885Sdim 1591218885Sdim // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1592223017Sdim unsigned SplitBefore = 0, SplitAfter = 1; 1593218885Sdim 1594218885Sdim // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1595218885Sdim // It is the spill weight that needs to be evicted. 1596218885Sdim float MaxGap = GapWeight[0]; 1597218885Sdim 1598218885Sdim for (;;) { 1599218885Sdim // Live before/after split? 1600218885Sdim const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1601218885Sdim const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1602218885Sdim 1603218885Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1604218885Sdim << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1605218885Sdim << " i=" << MaxGap); 1606218885Sdim 1607218885Sdim // Stop before the interval gets so big we wouldn't be making progress. 1608218885Sdim if (!LiveBefore && !LiveAfter) { 1609218885Sdim DEBUG(dbgs() << " all\n"); 1610218885Sdim break; 1611218885Sdim } 1612218885Sdim // Should the interval be extended or shrunk? 1613218885Sdim bool Shrink = true; 1614218885Sdim 1615223017Sdim // How many gaps would the new range have? 1616223017Sdim unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1617223017Sdim 1618223017Sdim // Legally, without causing looping? 1619223017Sdim bool Legal = !ProgressRequired || NewGaps < NumGaps; 1620223017Sdim 1621263508Sdim if (Legal && MaxGap < llvm::huge_valf) { 1622223017Sdim // Estimate the new spill weight. Each instruction reads or writes the 1623223017Sdim // register. Conservatively assume there are no read-modify-write 1624223017Sdim // instructions. 1625218885Sdim // 1626223017Sdim // Try to guess the size of the new interval. 1627223017Sdim const float EstWeight = normalizeSpillWeight(blockFreq * (NewGaps + 1), 1628223017Sdim Uses[SplitBefore].distance(Uses[SplitAfter]) + 1629223017Sdim (LiveBefore + LiveAfter)*SlotIndex::InstrDist); 1630218885Sdim // Would this split be possible to allocate? 1631218885Sdim // Never allocate all gaps, we wouldn't be making progress. 1632221345Sdim DEBUG(dbgs() << " w=" << EstWeight); 1633221345Sdim if (EstWeight * Hysteresis >= MaxGap) { 1634218885Sdim Shrink = false; 1635221345Sdim float Diff = EstWeight - MaxGap; 1636218885Sdim if (Diff > BestDiff) { 1637218885Sdim DEBUG(dbgs() << " (best)"); 1638221345Sdim BestDiff = Hysteresis * Diff; 1639218885Sdim BestBefore = SplitBefore; 1640218885Sdim BestAfter = SplitAfter; 1641218885Sdim } 1642218885Sdim } 1643218885Sdim } 1644218885Sdim 1645218885Sdim // Try to shrink. 1646218885Sdim if (Shrink) { 1647223017Sdim if (++SplitBefore < SplitAfter) { 1648218885Sdim DEBUG(dbgs() << " shrink\n"); 1649218885Sdim // Recompute the max when necessary. 1650218885Sdim if (GapWeight[SplitBefore - 1] >= MaxGap) { 1651218885Sdim MaxGap = GapWeight[SplitBefore]; 1652218885Sdim for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1653218885Sdim MaxGap = std::max(MaxGap, GapWeight[i]); 1654218885Sdim } 1655218885Sdim continue; 1656218885Sdim } 1657218885Sdim MaxGap = 0; 1658218885Sdim } 1659218885Sdim 1660218885Sdim // Try to extend the interval. 1661218885Sdim if (SplitAfter >= NumGaps) { 1662218885Sdim DEBUG(dbgs() << " end\n"); 1663218885Sdim break; 1664218885Sdim } 1665218885Sdim 1666218885Sdim DEBUG(dbgs() << " extend\n"); 1667223017Sdim MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1668218885Sdim } 1669218885Sdim } 1670218885Sdim 1671218885Sdim // Didn't find any candidates? 1672218885Sdim if (BestBefore == NumGaps) 1673218885Sdim return 0; 1674218885Sdim 1675218885Sdim DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1676218885Sdim << '-' << Uses[BestAfter] << ", " << BestDiff 1677218885Sdim << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1678218885Sdim 1679239462Sdim LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1680221345Sdim SE->reset(LREdit); 1681218885Sdim 1682221345Sdim SE->openIntv(); 1683221345Sdim SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1684221345Sdim SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1685221345Sdim SE->useIntv(SegStart, SegStop); 1686223017Sdim SmallVector<unsigned, 8> IntvMap; 1687223017Sdim SE->finish(&IntvMap); 1688263508Sdim DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS); 1689223017Sdim 1690223017Sdim // If the new range has the same number of instructions as before, mark it as 1691226633Sdim // RS_Split2 so the next split will be forced to make progress. Otherwise, 1692223017Sdim // leave the new intervals as RS_New so they can compete. 1693223017Sdim bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1694223017Sdim bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1695223017Sdim unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1696223017Sdim if (NewGaps >= NumGaps) { 1697223017Sdim DEBUG(dbgs() << "Tagging non-progress ranges: "); 1698223017Sdim assert(!ProgressRequired && "Didn't make progress when it was required."); 1699223017Sdim for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1700223017Sdim if (IntvMap[i] == 1) { 1701263508Sdim setStage(LIS->getInterval(LREdit.get(i)), RS_Split2); 1702263508Sdim DEBUG(dbgs() << PrintReg(LREdit.get(i))); 1703223017Sdim } 1704223017Sdim DEBUG(dbgs() << '\n'); 1705223017Sdim } 1706218885Sdim ++NumLocalSplits; 1707218885Sdim 1708218885Sdim return 0; 1709218885Sdim} 1710218885Sdim 1711218885Sdim//===----------------------------------------------------------------------===// 1712218885Sdim// Live Range Splitting 1713218885Sdim//===----------------------------------------------------------------------===// 1714218885Sdim 1715218885Sdim/// trySplit - Try to split VirtReg or one of its interferences, making it 1716218885Sdim/// assignable. 1717218885Sdim/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1718218885Sdimunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1719263508Sdim SmallVectorImpl<unsigned>&NewVRegs) { 1720226633Sdim // Ranges must be Split2 or less. 1721226633Sdim if (getStage(VirtReg) >= RS_Spill) 1722226633Sdim return 0; 1723226633Sdim 1724218885Sdim // Local intervals are handled separately. 1725218885Sdim if (LIS->intervalIsInOneMBB(VirtReg)) { 1726218885Sdim NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1727221345Sdim SA->analyze(&VirtReg); 1728239462Sdim unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs); 1729239462Sdim if (PhysReg || !NewVRegs.empty()) 1730239462Sdim return PhysReg; 1731239462Sdim return tryInstructionSplit(VirtReg, Order, NewVRegs); 1732218885Sdim } 1733218885Sdim 1734218885Sdim NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1735218885Sdim 1736221345Sdim SA->analyze(&VirtReg); 1737221345Sdim 1738223017Sdim // FIXME: SplitAnalysis may repair broken live ranges coming from the 1739223017Sdim // coalescer. That may cause the range to become allocatable which means that 1740223017Sdim // tryRegionSplit won't be making progress. This check should be replaced with 1741223017Sdim // an assertion when the coalescer is fixed. 1742223017Sdim if (SA->didRepairRange()) { 1743223017Sdim // VirtReg has changed, so all cached queries are invalid. 1744239462Sdim Matrix->invalidateVirtRegs(); 1745223017Sdim if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1746223017Sdim return PhysReg; 1747223017Sdim } 1748223017Sdim 1749226633Sdim // First try to split around a region spanning multiple blocks. RS_Split2 1750226633Sdim // ranges already made dubious progress with region splitting, so they go 1751226633Sdim // straight to single block splitting. 1752226633Sdim if (getStage(VirtReg) < RS_Split2) { 1753226633Sdim unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1754226633Sdim if (PhysReg || !NewVRegs.empty()) 1755226633Sdim return PhysReg; 1756218885Sdim } 1757218885Sdim 1758226633Sdim // Then isolate blocks. 1759226633Sdim return tryBlockSplit(VirtReg, Order, NewVRegs); 1760218885Sdim} 1761218885Sdim 1762218885Sdim 1763218885Sdim//===----------------------------------------------------------------------===// 1764218885Sdim// Main Entry Point 1765218885Sdim//===----------------------------------------------------------------------===// 1766218885Sdim 1767218885Sdimunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1768263508Sdim SmallVectorImpl<unsigned> &NewVRegs) { 1769218885Sdim // First try assigning a free register. 1770223017Sdim AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo); 1771221345Sdim if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1772218885Sdim return PhysReg; 1773218885Sdim 1774223017Sdim LiveRangeStage Stage = getStage(VirtReg); 1775224145Sdim DEBUG(dbgs() << StageName[Stage] 1776224145Sdim << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 1777219077Sdim 1778223017Sdim // Try to evict a less worthy live range, but only for ranges from the primary 1779226633Sdim // queue. The RS_Split ranges already failed to do this, and they should not 1780223017Sdim // get a second chance until they have been split. 1781226633Sdim if (Stage != RS_Split) 1782223017Sdim if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs)) 1783223017Sdim return PhysReg; 1784223017Sdim 1785218885Sdim assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1786218885Sdim 1787219077Sdim // The first time we see a live range, don't try to split or spill. 1788219077Sdim // Wait until the second time, when all smaller ranges have been allocated. 1789219077Sdim // This gives a better picture of the interference to split around. 1790226633Sdim if (Stage < RS_Split) { 1791226633Sdim setStage(VirtReg, RS_Split); 1792221345Sdim DEBUG(dbgs() << "wait for second round\n"); 1793263508Sdim NewVRegs.push_back(VirtReg.reg); 1794219077Sdim return 0; 1795219077Sdim } 1796219077Sdim 1797223017Sdim // If we couldn't allocate a register from spilling, there is probably some 1798223017Sdim // invalid inline assembly. The base class wil report it. 1799226633Sdim if (Stage >= RS_Done || !VirtReg.isSpillable()) 1800223017Sdim return ~0u; 1801221345Sdim 1802218885Sdim // Try splitting VirtReg or interferences. 1803218885Sdim unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1804218885Sdim if (PhysReg || !NewVRegs.empty()) 1805218885Sdim return PhysReg; 1806218885Sdim 1807218885Sdim // Finally spill VirtReg itself. 1808218885Sdim NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1809239462Sdim LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1810221345Sdim spiller().spill(LRE); 1811226633Sdim setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); 1812218885Sdim 1813221345Sdim if (VerifyEnabled) 1814221345Sdim MF->verify(this, "After spilling"); 1815221345Sdim 1816218885Sdim // The live virtual register requesting allocation was spilled, so tell 1817218885Sdim // the caller not to allocate anything during this round. 1818218885Sdim return 0; 1819218885Sdim} 1820218885Sdim 1821218885Sdimbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1822218885Sdim DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1823243830Sdim << "********** Function: " << mf.getName() << '\n'); 1824218885Sdim 1825218885Sdim MF = &mf; 1826218885Sdim if (VerifyEnabled) 1827218885Sdim MF->verify(this, "Before greedy register allocator"); 1828218885Sdim 1829239462Sdim RegAllocBase::init(getAnalysis<VirtRegMap>(), 1830239462Sdim getAnalysis<LiveIntervals>(), 1831239462Sdim getAnalysis<LiveRegMatrix>()); 1832218885Sdim Indexes = &getAnalysis<SlotIndexes>(); 1833263508Sdim MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 1834218885Sdim DomTree = &getAnalysis<MachineDominatorTree>(); 1835218885Sdim SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1836218885Sdim Loops = &getAnalysis<MachineLoopInfo>(); 1837218885Sdim Bundles = &getAnalysis<EdgeBundles>(); 1838218885Sdim SpillPlacer = &getAnalysis<SpillPlacement>(); 1839223017Sdim DebugVars = &getAnalysis<LiveDebugVariables>(); 1840218885Sdim 1841263508Sdim calculateSpillWeightsAndHints(*LIS, mf, *Loops, *MBFI); 1842263508Sdim 1843263508Sdim DEBUG(LIS->dump()); 1844263508Sdim 1845218885Sdim SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1846263508Sdim SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI)); 1847224145Sdim ExtraRegInfo.clear(); 1848224145Sdim ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1849224145Sdim NextCascade = 1; 1850239462Sdim IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); 1851226633Sdim GlobalCand.resize(32); // This will grow as needed. 1852218885Sdim 1853218885Sdim allocatePhysRegs(); 1854218885Sdim releaseMemory(); 1855218885Sdim return true; 1856218885Sdim} 1857