RegAllocGreedy.cpp revision 218885
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" 17218885Sdim#include "LiveIntervalUnion.h" 18218885Sdim#include "LiveRangeEdit.h" 19218885Sdim#include "RegAllocBase.h" 20218885Sdim#include "Spiller.h" 21218885Sdim#include "SpillPlacement.h" 22218885Sdim#include "SplitKit.h" 23218885Sdim#include "VirtRegMap.h" 24218885Sdim#include "llvm/ADT/Statistic.h" 25218885Sdim#include "llvm/Analysis/AliasAnalysis.h" 26218885Sdim#include "llvm/Function.h" 27218885Sdim#include "llvm/PassAnalysisSupport.h" 28218885Sdim#include "llvm/CodeGen/CalcSpillWeights.h" 29218885Sdim#include "llvm/CodeGen/EdgeBundles.h" 30218885Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 31218885Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 32218885Sdim#include "llvm/CodeGen/MachineDominators.h" 33218885Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 34218885Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 35218885Sdim#include "llvm/CodeGen/MachineLoopRanges.h" 36218885Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 37218885Sdim#include "llvm/CodeGen/Passes.h" 38218885Sdim#include "llvm/CodeGen/RegAllocRegistry.h" 39218885Sdim#include "llvm/CodeGen/RegisterCoalescer.h" 40218885Sdim#include "llvm/Target/TargetOptions.h" 41218885Sdim#include "llvm/Support/Debug.h" 42218885Sdim#include "llvm/Support/ErrorHandling.h" 43218885Sdim#include "llvm/Support/raw_ostream.h" 44218885Sdim#include "llvm/Support/Timer.h" 45218885Sdim 46218885Sdimusing namespace llvm; 47218885Sdim 48218885SdimSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 49218885SdimSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 50218885SdimSTATISTIC(NumReassigned, "Number of interferences reassigned"); 51218885SdimSTATISTIC(NumEvicted, "Number of interferences evicted"); 52218885Sdim 53218885Sdimstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 54218885Sdim createGreedyRegisterAllocator); 55218885Sdim 56218885Sdimnamespace { 57218885Sdimclass RAGreedy : public MachineFunctionPass, public RegAllocBase { 58218885Sdim // context 59218885Sdim MachineFunction *MF; 60218885Sdim BitVector ReservedRegs; 61218885Sdim 62218885Sdim // analyses 63218885Sdim SlotIndexes *Indexes; 64218885Sdim LiveStacks *LS; 65218885Sdim MachineDominatorTree *DomTree; 66218885Sdim MachineLoopInfo *Loops; 67218885Sdim MachineLoopRanges *LoopRanges; 68218885Sdim EdgeBundles *Bundles; 69218885Sdim SpillPlacement *SpillPlacer; 70218885Sdim 71218885Sdim // state 72218885Sdim std::auto_ptr<Spiller> SpillerInstance; 73218885Sdim std::auto_ptr<SplitAnalysis> SA; 74218885Sdim 75218885Sdim // splitting state. 76218885Sdim 77218885Sdim /// All basic blocks where the current register is live. 78218885Sdim SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints; 79218885Sdim 80218885Sdim /// For every instruction in SA->UseSlots, store the previous non-copy 81218885Sdim /// instruction. 82218885Sdim SmallVector<SlotIndex, 8> PrevSlot; 83218885Sdim 84218885Sdimpublic: 85218885Sdim RAGreedy(); 86218885Sdim 87218885Sdim /// Return the pass name. 88218885Sdim virtual const char* getPassName() const { 89218885Sdim return "Greedy Register Allocator"; 90218885Sdim } 91218885Sdim 92218885Sdim /// RAGreedy analysis usage. 93218885Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 94218885Sdim 95218885Sdim virtual void releaseMemory(); 96218885Sdim 97218885Sdim virtual Spiller &spiller() { return *SpillerInstance; } 98218885Sdim 99218885Sdim virtual float getPriority(LiveInterval *LI); 100218885Sdim 101218885Sdim virtual unsigned selectOrSplit(LiveInterval&, 102218885Sdim SmallVectorImpl<LiveInterval*>&); 103218885Sdim 104218885Sdim /// Perform register allocation. 105218885Sdim virtual bool runOnMachineFunction(MachineFunction &mf); 106218885Sdim 107218885Sdim static char ID; 108218885Sdim 109218885Sdimprivate: 110218885Sdim bool checkUncachedInterference(LiveInterval&, unsigned); 111218885Sdim LiveInterval *getSingleInterference(LiveInterval&, unsigned); 112218885Sdim bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg); 113218885Sdim float calcInterferenceWeight(LiveInterval&, unsigned); 114218885Sdim float calcInterferenceInfo(LiveInterval&, unsigned); 115218885Sdim float calcGlobalSplitCost(const BitVector&); 116218885Sdim void splitAroundRegion(LiveInterval&, unsigned, const BitVector&, 117218885Sdim SmallVectorImpl<LiveInterval*>&); 118218885Sdim void calcGapWeights(unsigned, SmallVectorImpl<float>&); 119218885Sdim SlotIndex getPrevMappedIndex(const MachineInstr*); 120218885Sdim void calcPrevSlots(); 121218885Sdim unsigned nextSplitPoint(unsigned); 122218885Sdim 123218885Sdim unsigned tryReassignOrEvict(LiveInterval&, AllocationOrder&, 124218885Sdim SmallVectorImpl<LiveInterval*>&); 125218885Sdim unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 126218885Sdim SmallVectorImpl<LiveInterval*>&); 127218885Sdim unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 128218885Sdim SmallVectorImpl<LiveInterval*>&); 129218885Sdim unsigned trySplit(LiveInterval&, AllocationOrder&, 130218885Sdim SmallVectorImpl<LiveInterval*>&); 131218885Sdim unsigned trySpillInterferences(LiveInterval&, AllocationOrder&, 132218885Sdim SmallVectorImpl<LiveInterval*>&); 133218885Sdim}; 134218885Sdim} // end anonymous namespace 135218885Sdim 136218885Sdimchar RAGreedy::ID = 0; 137218885Sdim 138218885SdimFunctionPass* llvm::createGreedyRegisterAllocator() { 139218885Sdim return new RAGreedy(); 140218885Sdim} 141218885Sdim 142218885SdimRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 143218885Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 144218885Sdim initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 145218885Sdim initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 146218885Sdim initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); 147218885Sdim initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry()); 148218885Sdim initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 149218885Sdim initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 150218885Sdim initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 151218885Sdim initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 152218885Sdim initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry()); 153218885Sdim initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 154218885Sdim initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 155218885Sdim initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 156218885Sdim} 157218885Sdim 158218885Sdimvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 159218885Sdim AU.setPreservesCFG(); 160218885Sdim AU.addRequired<AliasAnalysis>(); 161218885Sdim AU.addPreserved<AliasAnalysis>(); 162218885Sdim AU.addRequired<LiveIntervals>(); 163218885Sdim AU.addRequired<SlotIndexes>(); 164218885Sdim AU.addPreserved<SlotIndexes>(); 165218885Sdim if (StrongPHIElim) 166218885Sdim AU.addRequiredID(StrongPHIEliminationID); 167218885Sdim AU.addRequiredTransitive<RegisterCoalescer>(); 168218885Sdim AU.addRequired<CalculateSpillWeights>(); 169218885Sdim AU.addRequired<LiveStacks>(); 170218885Sdim AU.addPreserved<LiveStacks>(); 171218885Sdim AU.addRequired<MachineDominatorTree>(); 172218885Sdim AU.addPreserved<MachineDominatorTree>(); 173218885Sdim AU.addRequired<MachineLoopInfo>(); 174218885Sdim AU.addPreserved<MachineLoopInfo>(); 175218885Sdim AU.addRequired<MachineLoopRanges>(); 176218885Sdim AU.addPreserved<MachineLoopRanges>(); 177218885Sdim AU.addRequired<VirtRegMap>(); 178218885Sdim AU.addPreserved<VirtRegMap>(); 179218885Sdim AU.addRequired<EdgeBundles>(); 180218885Sdim AU.addRequired<SpillPlacement>(); 181218885Sdim MachineFunctionPass::getAnalysisUsage(AU); 182218885Sdim} 183218885Sdim 184218885Sdimvoid RAGreedy::releaseMemory() { 185218885Sdim SpillerInstance.reset(0); 186218885Sdim RegAllocBase::releaseMemory(); 187218885Sdim} 188218885Sdim 189218885Sdimfloat RAGreedy::getPriority(LiveInterval *LI) { 190218885Sdim float Priority = LI->weight; 191218885Sdim 192218885Sdim // Prioritize hinted registers so they are allocated first. 193218885Sdim std::pair<unsigned, unsigned> Hint; 194218885Sdim if (Hint.first || Hint.second) { 195218885Sdim // The hint can be target specific, a virtual register, or a physreg. 196218885Sdim Priority *= 2; 197218885Sdim 198218885Sdim // Prefer physreg hints above anything else. 199218885Sdim if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second)) 200218885Sdim Priority *= 2; 201218885Sdim } 202218885Sdim return Priority; 203218885Sdim} 204218885Sdim 205218885Sdim 206218885Sdim//===----------------------------------------------------------------------===// 207218885Sdim// Register Reassignment 208218885Sdim//===----------------------------------------------------------------------===// 209218885Sdim 210218885Sdim// Check interference without using the cache. 211218885Sdimbool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg, 212218885Sdim unsigned PhysReg) { 213218885Sdim for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 214218885Sdim LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]); 215218885Sdim if (subQ.checkInterference()) 216218885Sdim return true; 217218885Sdim } 218218885Sdim return false; 219218885Sdim} 220218885Sdim 221218885Sdim/// getSingleInterference - Return the single interfering virtual register 222218885Sdim/// assigned to PhysReg. Return 0 if more than one virtual register is 223218885Sdim/// interfering. 224218885SdimLiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg, 225218885Sdim unsigned PhysReg) { 226218885Sdim // Check physreg and aliases. 227218885Sdim LiveInterval *Interference = 0; 228218885Sdim for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) { 229218885Sdim LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI); 230218885Sdim if (Q.checkInterference()) { 231218885Sdim if (Interference) 232218885Sdim return 0; 233218885Sdim Q.collectInterferingVRegs(1); 234218885Sdim if (!Q.seenAllInterferences()) 235218885Sdim return 0; 236218885Sdim Interference = Q.interferingVRegs().front(); 237218885Sdim } 238218885Sdim } 239218885Sdim return Interference; 240218885Sdim} 241218885Sdim 242218885Sdim// Attempt to reassign this virtual register to a different physical register. 243218885Sdim// 244218885Sdim// FIXME: we are not yet caching these "second-level" interferences discovered 245218885Sdim// in the sub-queries. These interferences can change with each call to 246218885Sdim// selectOrSplit. However, we could implement a "may-interfere" cache that 247218885Sdim// could be conservatively dirtied when we reassign or split. 248218885Sdim// 249218885Sdim// FIXME: This may result in a lot of alias queries. We could summarize alias 250218885Sdim// live intervals in their parent register's live union, but it's messy. 251218885Sdimbool RAGreedy::reassignVReg(LiveInterval &InterferingVReg, 252218885Sdim unsigned WantedPhysReg) { 253218885Sdim assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) && 254218885Sdim "Can only reassign virtual registers"); 255218885Sdim assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) && 256218885Sdim "inconsistent phys reg assigment"); 257218885Sdim 258218885Sdim AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs); 259218885Sdim while (unsigned PhysReg = Order.next()) { 260218885Sdim // Don't reassign to a WantedPhysReg alias. 261218885Sdim if (TRI->regsOverlap(PhysReg, WantedPhysReg)) 262218885Sdim continue; 263218885Sdim 264218885Sdim if (checkUncachedInterference(InterferingVReg, PhysReg)) 265218885Sdim continue; 266218885Sdim 267218885Sdim // Reassign the interfering virtual reg to this physical reg. 268218885Sdim unsigned OldAssign = VRM->getPhys(InterferingVReg.reg); 269218885Sdim DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " << 270218885Sdim TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n'); 271218885Sdim unassign(InterferingVReg, OldAssign); 272218885Sdim assign(InterferingVReg, PhysReg); 273218885Sdim ++NumReassigned; 274218885Sdim return true; 275218885Sdim } 276218885Sdim return false; 277218885Sdim} 278218885Sdim 279218885Sdim/// tryReassignOrEvict - Try to reassign a single interferences to a different 280218885Sdim/// physreg, or evict a single interference with a lower spill weight. 281218885Sdim/// @param VirtReg Currently unassigned virtual register. 282218885Sdim/// @param Order Physregs to try. 283218885Sdim/// @return Physreg to assign VirtReg, or 0. 284218885Sdimunsigned RAGreedy::tryReassignOrEvict(LiveInterval &VirtReg, 285218885Sdim AllocationOrder &Order, 286218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs){ 287218885Sdim NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled); 288218885Sdim 289218885Sdim // Keep track of the lightest single interference seen so far. 290218885Sdim float BestWeight = VirtReg.weight; 291218885Sdim LiveInterval *BestVirt = 0; 292218885Sdim unsigned BestPhys = 0; 293218885Sdim 294218885Sdim Order.rewind(); 295218885Sdim while (unsigned PhysReg = Order.next()) { 296218885Sdim LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg); 297218885Sdim if (!InterferingVReg) 298218885Sdim continue; 299218885Sdim if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg)) 300218885Sdim continue; 301218885Sdim if (reassignVReg(*InterferingVReg, PhysReg)) 302218885Sdim return PhysReg; 303218885Sdim 304218885Sdim // Cannot reassign, is this an eviction candidate? 305218885Sdim if (InterferingVReg->weight < BestWeight) { 306218885Sdim BestVirt = InterferingVReg; 307218885Sdim BestPhys = PhysReg; 308218885Sdim BestWeight = InterferingVReg->weight; 309218885Sdim } 310218885Sdim } 311218885Sdim 312218885Sdim // Nothing reassigned, can we evict a lighter single interference? 313218885Sdim if (BestVirt) { 314218885Sdim DEBUG(dbgs() << "evicting lighter " << *BestVirt << '\n'); 315218885Sdim unassign(*BestVirt, VRM->getPhys(BestVirt->reg)); 316218885Sdim ++NumEvicted; 317218885Sdim NewVRegs.push_back(BestVirt); 318218885Sdim return BestPhys; 319218885Sdim } 320218885Sdim 321218885Sdim return 0; 322218885Sdim} 323218885Sdim 324218885Sdim 325218885Sdim//===----------------------------------------------------------------------===// 326218885Sdim// Region Splitting 327218885Sdim//===----------------------------------------------------------------------===// 328218885Sdim 329218885Sdim/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints 330218885Sdim/// when considering interference from PhysReg. Also compute an optimistic local 331218885Sdim/// cost of this interference pattern. 332218885Sdim/// 333218885Sdim/// The final cost of a split is the local cost + global cost of preferences 334218885Sdim/// broken by SpillPlacement. 335218885Sdim/// 336218885Sdimfloat RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) { 337218885Sdim // Reset interference dependent info. 338218885Sdim SpillConstraints.resize(SA->LiveBlocks.size()); 339218885Sdim for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 340218885Sdim SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 341218885Sdim SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 342218885Sdim BC.Number = BI.MBB->getNumber(); 343218885Sdim BC.Entry = (BI.Uses && BI.LiveIn) ? 344218885Sdim SpillPlacement::PrefReg : SpillPlacement::DontCare; 345218885Sdim BC.Exit = (BI.Uses && BI.LiveOut) ? 346218885Sdim SpillPlacement::PrefReg : SpillPlacement::DontCare; 347218885Sdim BI.OverlapEntry = BI.OverlapExit = false; 348218885Sdim } 349218885Sdim 350218885Sdim // Add interference info from each PhysReg alias. 351218885Sdim for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 352218885Sdim if (!query(VirtReg, *AI).checkInterference()) 353218885Sdim continue; 354218885Sdim LiveIntervalUnion::SegmentIter IntI = 355218885Sdim PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 356218885Sdim if (!IntI.valid()) 357218885Sdim continue; 358218885Sdim 359218885Sdim // Determine which blocks have interference live in or after the last split 360218885Sdim // point. 361218885Sdim for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 362218885Sdim SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 363218885Sdim SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 364218885Sdim SlotIndex Start, Stop; 365218885Sdim tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 366218885Sdim 367218885Sdim // Skip interference-free blocks. 368218885Sdim if (IntI.start() >= Stop) 369218885Sdim continue; 370218885Sdim 371218885Sdim // Is the interference live-in? 372218885Sdim if (BI.LiveIn) { 373218885Sdim IntI.advanceTo(Start); 374218885Sdim if (!IntI.valid()) 375218885Sdim break; 376218885Sdim if (IntI.start() <= Start) 377218885Sdim BC.Entry = SpillPlacement::MustSpill; 378218885Sdim } 379218885Sdim 380218885Sdim // Is the interference overlapping the last split point? 381218885Sdim if (BI.LiveOut) { 382218885Sdim if (IntI.stop() < BI.LastSplitPoint) 383218885Sdim IntI.advanceTo(BI.LastSplitPoint.getPrevSlot()); 384218885Sdim if (!IntI.valid()) 385218885Sdim break; 386218885Sdim if (IntI.start() < Stop) 387218885Sdim BC.Exit = SpillPlacement::MustSpill; 388218885Sdim } 389218885Sdim } 390218885Sdim 391218885Sdim // Rewind iterator and check other interferences. 392218885Sdim IntI.find(VirtReg.beginIndex()); 393218885Sdim for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 394218885Sdim SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 395218885Sdim SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 396218885Sdim SlotIndex Start, Stop; 397218885Sdim tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 398218885Sdim 399218885Sdim // Skip interference-free blocks. 400218885Sdim if (IntI.start() >= Stop) 401218885Sdim continue; 402218885Sdim 403218885Sdim // Handle transparent blocks with interference separately. 404218885Sdim // Transparent blocks never incur any fixed cost. 405218885Sdim if (BI.LiveThrough && !BI.Uses) { 406218885Sdim IntI.advanceTo(Start); 407218885Sdim if (!IntI.valid()) 408218885Sdim break; 409218885Sdim if (IntI.start() >= Stop) 410218885Sdim continue; 411218885Sdim 412218885Sdim if (BC.Entry != SpillPlacement::MustSpill) 413218885Sdim BC.Entry = SpillPlacement::PrefSpill; 414218885Sdim if (BC.Exit != SpillPlacement::MustSpill) 415218885Sdim BC.Exit = SpillPlacement::PrefSpill; 416218885Sdim continue; 417218885Sdim } 418218885Sdim 419218885Sdim // Now we only have blocks with uses left. 420218885Sdim // Check if the interference overlaps the uses. 421218885Sdim assert(BI.Uses && "Non-transparent block without any uses"); 422218885Sdim 423218885Sdim // Check interference on entry. 424218885Sdim if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) { 425218885Sdim IntI.advanceTo(Start); 426218885Sdim if (!IntI.valid()) 427218885Sdim break; 428218885Sdim // Not live in, but before the first use. 429218885Sdim if (IntI.start() < BI.FirstUse) 430218885Sdim BC.Entry = SpillPlacement::PrefSpill; 431218885Sdim } 432218885Sdim 433218885Sdim // Does interference overlap the uses in the entry segment 434218885Sdim // [FirstUse;Kill)? 435218885Sdim if (BI.LiveIn && !BI.OverlapEntry) { 436218885Sdim IntI.advanceTo(BI.FirstUse); 437218885Sdim if (!IntI.valid()) 438218885Sdim break; 439218885Sdim // A live-through interval has no kill. 440218885Sdim // Check [FirstUse;LastUse) instead. 441218885Sdim if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill)) 442218885Sdim BI.OverlapEntry = true; 443218885Sdim } 444218885Sdim 445218885Sdim // Does interference overlap the uses in the exit segment [Def;LastUse)? 446218885Sdim if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) { 447218885Sdim IntI.advanceTo(BI.Def); 448218885Sdim if (!IntI.valid()) 449218885Sdim break; 450218885Sdim if (IntI.start() < BI.LastUse) 451218885Sdim BI.OverlapExit = true; 452218885Sdim } 453218885Sdim 454218885Sdim // Check interference on exit. 455218885Sdim if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) { 456218885Sdim // Check interference between LastUse and Stop. 457218885Sdim if (BC.Exit != SpillPlacement::PrefSpill) { 458218885Sdim IntI.advanceTo(BI.LastUse); 459218885Sdim if (!IntI.valid()) 460218885Sdim break; 461218885Sdim if (IntI.start() < Stop) 462218885Sdim BC.Exit = SpillPlacement::PrefSpill; 463218885Sdim } 464218885Sdim } 465218885Sdim } 466218885Sdim } 467218885Sdim 468218885Sdim // Accumulate a local cost of this interference pattern. 469218885Sdim float LocalCost = 0; 470218885Sdim for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 471218885Sdim SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 472218885Sdim if (!BI.Uses) 473218885Sdim continue; 474218885Sdim SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 475218885Sdim unsigned Inserts = 0; 476218885Sdim 477218885Sdim // Do we need spill code for the entry segment? 478218885Sdim if (BI.LiveIn) 479218885Sdim Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg; 480218885Sdim 481218885Sdim // For the exit segment? 482218885Sdim if (BI.LiveOut) 483218885Sdim Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg; 484218885Sdim 485218885Sdim // The local cost of spill code in this block is the block frequency times 486218885Sdim // the number of spill instructions inserted. 487218885Sdim if (Inserts) 488218885Sdim LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB); 489218885Sdim } 490218885Sdim DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = " 491218885Sdim << LocalCost << '\n'); 492218885Sdim return LocalCost; 493218885Sdim} 494218885Sdim 495218885Sdim/// calcGlobalSplitCost - Return the global split cost of following the split 496218885Sdim/// pattern in LiveBundles. This cost should be added to the local cost of the 497218885Sdim/// interference pattern in SpillConstraints. 498218885Sdim/// 499218885Sdimfloat RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) { 500218885Sdim float GlobalCost = 0; 501218885Sdim for (unsigned i = 0, e = SpillConstraints.size(); i != e; ++i) { 502218885Sdim SpillPlacement::BlockConstraint &BC = SpillConstraints[i]; 503218885Sdim unsigned Inserts = 0; 504218885Sdim // Broken entry preference? 505218885Sdim Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] != 506218885Sdim (BC.Entry == SpillPlacement::PrefReg); 507218885Sdim // Broken exit preference? 508218885Sdim Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] != 509218885Sdim (BC.Exit == SpillPlacement::PrefReg); 510218885Sdim if (Inserts) 511218885Sdim GlobalCost += 512218885Sdim Inserts * SpillPlacer->getBlockFrequency(SA->LiveBlocks[i].MBB); 513218885Sdim } 514218885Sdim DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n'); 515218885Sdim return GlobalCost; 516218885Sdim} 517218885Sdim 518218885Sdim/// splitAroundRegion - Split VirtReg around the region determined by 519218885Sdim/// LiveBundles. Make an effort to avoid interference from PhysReg. 520218885Sdim/// 521218885Sdim/// The 'register' interval is going to contain as many uses as possible while 522218885Sdim/// avoiding interference. The 'stack' interval is the complement constructed by 523218885Sdim/// SplitEditor. It will contain the rest. 524218885Sdim/// 525218885Sdimvoid RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg, 526218885Sdim const BitVector &LiveBundles, 527218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 528218885Sdim DEBUG({ 529218885Sdim dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI) 530218885Sdim << " with bundles"; 531218885Sdim for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i)) 532218885Sdim dbgs() << " EB#" << i; 533218885Sdim dbgs() << ".\n"; 534218885Sdim }); 535218885Sdim 536218885Sdim // First compute interference ranges in the live blocks. 537218885Sdim typedef std::pair<SlotIndex, SlotIndex> IndexPair; 538218885Sdim SmallVector<IndexPair, 8> InterferenceRanges; 539218885Sdim InterferenceRanges.resize(SA->LiveBlocks.size()); 540218885Sdim for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 541218885Sdim if (!query(VirtReg, *AI).checkInterference()) 542218885Sdim continue; 543218885Sdim LiveIntervalUnion::SegmentIter IntI = 544218885Sdim PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex()); 545218885Sdim if (!IntI.valid()) 546218885Sdim continue; 547218885Sdim for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 548218885Sdim const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 549218885Sdim IndexPair &IP = InterferenceRanges[i]; 550218885Sdim SlotIndex Start, Stop; 551218885Sdim tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 552218885Sdim // Skip interference-free blocks. 553218885Sdim if (IntI.start() >= Stop) 554218885Sdim continue; 555218885Sdim 556218885Sdim // First interference in block. 557218885Sdim if (BI.LiveIn) { 558218885Sdim IntI.advanceTo(Start); 559218885Sdim if (!IntI.valid()) 560218885Sdim break; 561218885Sdim if (IntI.start() >= Stop) 562218885Sdim continue; 563218885Sdim if (!IP.first.isValid() || IntI.start() < IP.first) 564218885Sdim IP.first = IntI.start(); 565218885Sdim } 566218885Sdim 567218885Sdim // Last interference in block. 568218885Sdim if (BI.LiveOut) { 569218885Sdim IntI.advanceTo(Stop); 570218885Sdim if (!IntI.valid() || IntI.start() >= Stop) 571218885Sdim --IntI; 572218885Sdim if (IntI.stop() <= Start) 573218885Sdim continue; 574218885Sdim if (!IP.second.isValid() || IntI.stop() > IP.second) 575218885Sdim IP.second = IntI.stop(); 576218885Sdim } 577218885Sdim } 578218885Sdim } 579218885Sdim 580218885Sdim SmallVector<LiveInterval*, 4> SpillRegs; 581218885Sdim LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 582218885Sdim SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit); 583218885Sdim 584218885Sdim // Create the main cross-block interval. 585218885Sdim SE.openIntv(); 586218885Sdim 587218885Sdim // First add all defs that are live out of a block. 588218885Sdim for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 589218885Sdim SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 590218885Sdim bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 591218885Sdim bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 592218885Sdim 593218885Sdim // Should the register be live out? 594218885Sdim if (!BI.LiveOut || !RegOut) 595218885Sdim continue; 596218885Sdim 597218885Sdim IndexPair &IP = InterferenceRanges[i]; 598218885Sdim SlotIndex Start, Stop; 599218885Sdim tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 600218885Sdim 601218885Sdim DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#" 602218885Sdim << Bundles->getBundle(BI.MBB->getNumber(), 1) 603218885Sdim << " intf [" << IP.first << ';' << IP.second << ')'); 604218885Sdim 605218885Sdim // The interference interval should either be invalid or overlap MBB. 606218885Sdim assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference"); 607218885Sdim assert((!IP.second.isValid() || IP.second > Start) && "Bad interference"); 608218885Sdim 609218885Sdim // Check interference leaving the block. 610218885Sdim if (!IP.second.isValid()) { 611218885Sdim // Block is interference-free. 612218885Sdim DEBUG(dbgs() << ", no interference"); 613218885Sdim if (!BI.Uses) { 614218885Sdim assert(BI.LiveThrough && "No uses, but not live through block?"); 615218885Sdim // Block is live-through without interference. 616218885Sdim DEBUG(dbgs() << ", no uses" 617218885Sdim << (RegIn ? ", live-through.\n" : ", stack in.\n")); 618218885Sdim if (!RegIn) 619218885Sdim SE.enterIntvAtEnd(*BI.MBB); 620218885Sdim continue; 621218885Sdim } 622218885Sdim if (!BI.LiveThrough) { 623218885Sdim DEBUG(dbgs() << ", not live-through.\n"); 624218885Sdim SE.useIntv(SE.enterIntvBefore(BI.Def), Stop); 625218885Sdim continue; 626218885Sdim } 627218885Sdim if (!RegIn) { 628218885Sdim // Block is live-through, but entry bundle is on the stack. 629218885Sdim // Reload just before the first use. 630218885Sdim DEBUG(dbgs() << ", not live-in, enter before first use.\n"); 631218885Sdim SE.useIntv(SE.enterIntvBefore(BI.FirstUse), Stop); 632218885Sdim continue; 633218885Sdim } 634218885Sdim DEBUG(dbgs() << ", live-through.\n"); 635218885Sdim continue; 636218885Sdim } 637218885Sdim 638218885Sdim // Block has interference. 639218885Sdim DEBUG(dbgs() << ", interference to " << IP.second); 640218885Sdim 641218885Sdim if (!BI.LiveThrough && IP.second <= BI.Def) { 642218885Sdim // The interference doesn't reach the outgoing segment. 643218885Sdim DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n'); 644218885Sdim SE.useIntv(BI.Def, Stop); 645218885Sdim continue; 646218885Sdim } 647218885Sdim 648218885Sdim 649218885Sdim if (!BI.Uses) { 650218885Sdim // No uses in block, avoid interference by reloading as late as possible. 651218885Sdim DEBUG(dbgs() << ", no uses.\n"); 652218885Sdim SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB); 653218885Sdim assert(SegStart >= IP.second && "Couldn't avoid interference"); 654218885Sdim continue; 655218885Sdim } 656218885Sdim 657218885Sdim if (IP.second.getBoundaryIndex() < BI.LastUse) { 658218885Sdim // There are interference-free uses at the end of the block. 659218885Sdim // Find the first use that can get the live-out register. 660218885Sdim SmallVectorImpl<SlotIndex>::const_iterator UI = 661218885Sdim std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 662218885Sdim IP.second.getBoundaryIndex()); 663218885Sdim assert(UI != SA->UseSlots.end() && "Couldn't find last use"); 664218885Sdim SlotIndex Use = *UI; 665218885Sdim assert(Use <= BI.LastUse && "Couldn't find last use"); 666218885Sdim // Only attempt a split befroe the last split point. 667218885Sdim if (Use.getBaseIndex() <= BI.LastSplitPoint) { 668218885Sdim DEBUG(dbgs() << ", free use at " << Use << ".\n"); 669218885Sdim SlotIndex SegStart = SE.enterIntvBefore(Use); 670218885Sdim assert(SegStart >= IP.second && "Couldn't avoid interference"); 671218885Sdim assert(SegStart < BI.LastSplitPoint && "Impossible split point"); 672218885Sdim SE.useIntv(SegStart, Stop); 673218885Sdim continue; 674218885Sdim } 675218885Sdim } 676218885Sdim 677218885Sdim // Interference is after the last use. 678218885Sdim DEBUG(dbgs() << " after last use.\n"); 679218885Sdim SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB); 680218885Sdim assert(SegStart >= IP.second && "Couldn't avoid interference"); 681218885Sdim } 682218885Sdim 683218885Sdim // Now all defs leading to live bundles are handled, do everything else. 684218885Sdim for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) { 685218885Sdim SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i]; 686218885Sdim bool RegIn = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)]; 687218885Sdim bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)]; 688218885Sdim 689218885Sdim // Is the register live-in? 690218885Sdim if (!BI.LiveIn || !RegIn) 691218885Sdim continue; 692218885Sdim 693218885Sdim // We have an incoming register. Check for interference. 694218885Sdim IndexPair &IP = InterferenceRanges[i]; 695218885Sdim SlotIndex Start, Stop; 696218885Sdim tie(Start, Stop) = Indexes->getMBBRange(BI.MBB); 697218885Sdim 698218885Sdim DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0) 699218885Sdim << " -> BB#" << BI.MBB->getNumber()); 700218885Sdim 701218885Sdim // Check interference entering the block. 702218885Sdim if (!IP.first.isValid()) { 703218885Sdim // Block is interference-free. 704218885Sdim DEBUG(dbgs() << ", no interference"); 705218885Sdim if (!BI.Uses) { 706218885Sdim assert(BI.LiveThrough && "No uses, but not live through block?"); 707218885Sdim // Block is live-through without interference. 708218885Sdim if (RegOut) { 709218885Sdim DEBUG(dbgs() << ", no uses, live-through.\n"); 710218885Sdim SE.useIntv(Start, Stop); 711218885Sdim } else { 712218885Sdim DEBUG(dbgs() << ", no uses, stack-out.\n"); 713218885Sdim SE.leaveIntvAtTop(*BI.MBB); 714218885Sdim } 715218885Sdim continue; 716218885Sdim } 717218885Sdim if (!BI.LiveThrough) { 718218885Sdim DEBUG(dbgs() << ", killed in block.\n"); 719218885Sdim SE.useIntv(Start, SE.leaveIntvAfter(BI.Kill)); 720218885Sdim continue; 721218885Sdim } 722218885Sdim if (!RegOut) { 723218885Sdim // Block is live-through, but exit bundle is on the stack. 724218885Sdim // Spill immediately after the last use. 725218885Sdim if (BI.LastUse < BI.LastSplitPoint) { 726218885Sdim DEBUG(dbgs() << ", uses, stack-out.\n"); 727218885Sdim SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse)); 728218885Sdim continue; 729218885Sdim } 730218885Sdim // The last use is after the last split point, it is probably an 731218885Sdim // indirect jump. 732218885Sdim DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point " 733218885Sdim << BI.LastSplitPoint << ", stack-out.\n"); 734218885Sdim SlotIndex SegEnd = SE.leaveIntvBefore(BI.LastSplitPoint); 735218885Sdim SE.useIntv(Start, SegEnd); 736218885Sdim // Run a double interval from the split to the last use. 737218885Sdim // This makes it possible to spill the complement without affecting the 738218885Sdim // indirect branch. 739218885Sdim SE.overlapIntv(SegEnd, BI.LastUse); 740218885Sdim continue; 741218885Sdim } 742218885Sdim // Register is live-through. 743218885Sdim DEBUG(dbgs() << ", uses, live-through.\n"); 744218885Sdim SE.useIntv(Start, Stop); 745218885Sdim continue; 746218885Sdim } 747218885Sdim 748218885Sdim // Block has interference. 749218885Sdim DEBUG(dbgs() << ", interference from " << IP.first); 750218885Sdim 751218885Sdim if (!BI.LiveThrough && IP.first >= BI.Kill) { 752218885Sdim // The interference doesn't reach the outgoing segment. 753218885Sdim DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n'); 754218885Sdim SE.useIntv(Start, BI.Kill); 755218885Sdim continue; 756218885Sdim } 757218885Sdim 758218885Sdim if (!BI.Uses) { 759218885Sdim // No uses in block, avoid interference by spilling as soon as possible. 760218885Sdim DEBUG(dbgs() << ", no uses.\n"); 761218885Sdim SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB); 762218885Sdim assert(SegEnd <= IP.first && "Couldn't avoid interference"); 763218885Sdim continue; 764218885Sdim } 765218885Sdim if (IP.first.getBaseIndex() > BI.FirstUse) { 766218885Sdim // There are interference-free uses at the beginning of the block. 767218885Sdim // Find the last use that can get the register. 768218885Sdim SmallVectorImpl<SlotIndex>::const_iterator UI = 769218885Sdim std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), 770218885Sdim IP.first.getBaseIndex()); 771218885Sdim assert(UI != SA->UseSlots.begin() && "Couldn't find first use"); 772218885Sdim SlotIndex Use = (--UI)->getBoundaryIndex(); 773218885Sdim DEBUG(dbgs() << ", free use at " << *UI << ".\n"); 774218885Sdim SlotIndex SegEnd = SE.leaveIntvAfter(Use); 775218885Sdim assert(SegEnd <= IP.first && "Couldn't avoid interference"); 776218885Sdim SE.useIntv(Start, SegEnd); 777218885Sdim continue; 778218885Sdim } 779218885Sdim 780218885Sdim // Interference is before the first use. 781218885Sdim DEBUG(dbgs() << " before first use.\n"); 782218885Sdim SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB); 783218885Sdim assert(SegEnd <= IP.first && "Couldn't avoid interference"); 784218885Sdim } 785218885Sdim 786218885Sdim SE.closeIntv(); 787218885Sdim 788218885Sdim // FIXME: Should we be more aggressive about splitting the stack region into 789218885Sdim // per-block segments? The current approach allows the stack region to 790218885Sdim // separate into connected components. Some components may be allocatable. 791218885Sdim SE.finish(); 792218885Sdim ++NumGlobalSplits; 793218885Sdim 794218885Sdim if (VerifyEnabled) { 795218885Sdim MF->verify(this, "After splitting live range around region"); 796218885Sdim 797218885Sdim#ifndef NDEBUG 798218885Sdim // Make sure that at least one of the new intervals can allocate to PhysReg. 799218885Sdim // That was the whole point of splitting the live range. 800218885Sdim bool found = false; 801218885Sdim for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E; 802218885Sdim ++I) 803218885Sdim if (!checkUncachedInterference(**I, PhysReg)) { 804218885Sdim found = true; 805218885Sdim break; 806218885Sdim } 807218885Sdim assert(found && "No allocatable intervals after pointless splitting"); 808218885Sdim#endif 809218885Sdim } 810218885Sdim} 811218885Sdim 812218885Sdimunsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 813218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 814218885Sdim BitVector LiveBundles, BestBundles; 815218885Sdim float BestCost = 0; 816218885Sdim unsigned BestReg = 0; 817218885Sdim Order.rewind(); 818218885Sdim while (unsigned PhysReg = Order.next()) { 819218885Sdim float Cost = calcInterferenceInfo(VirtReg, PhysReg); 820218885Sdim if (BestReg && Cost >= BestCost) 821218885Sdim continue; 822218885Sdim 823218885Sdim SpillPlacer->placeSpills(SpillConstraints, LiveBundles); 824218885Sdim // No live bundles, defer to splitSingleBlocks(). 825218885Sdim if (!LiveBundles.any()) 826218885Sdim continue; 827218885Sdim 828218885Sdim Cost += calcGlobalSplitCost(LiveBundles); 829218885Sdim if (!BestReg || Cost < BestCost) { 830218885Sdim BestReg = PhysReg; 831218885Sdim BestCost = Cost; 832218885Sdim BestBundles.swap(LiveBundles); 833218885Sdim } 834218885Sdim } 835218885Sdim 836218885Sdim if (!BestReg) 837218885Sdim return 0; 838218885Sdim 839218885Sdim splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs); 840218885Sdim return 0; 841218885Sdim} 842218885Sdim 843218885Sdim 844218885Sdim//===----------------------------------------------------------------------===// 845218885Sdim// Local Splitting 846218885Sdim//===----------------------------------------------------------------------===// 847218885Sdim 848218885Sdim 849218885Sdim/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 850218885Sdim/// in order to use PhysReg between two entries in SA->UseSlots. 851218885Sdim/// 852218885Sdim/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 853218885Sdim/// 854218885Sdimvoid RAGreedy::calcGapWeights(unsigned PhysReg, 855218885Sdim SmallVectorImpl<float> &GapWeight) { 856218885Sdim assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 857218885Sdim const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 858218885Sdim const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 859218885Sdim const unsigned NumGaps = Uses.size()-1; 860218885Sdim 861218885Sdim // Start and end points for the interference check. 862218885Sdim SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse; 863218885Sdim SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse; 864218885Sdim 865218885Sdim GapWeight.assign(NumGaps, 0.0f); 866218885Sdim 867218885Sdim // Add interference from each overlapping register. 868218885Sdim for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 869218885Sdim if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI) 870218885Sdim .checkInterference()) 871218885Sdim continue; 872218885Sdim 873218885Sdim // We know that VirtReg is a continuous interval from FirstUse to LastUse, 874218885Sdim // so we don't need InterferenceQuery. 875218885Sdim // 876218885Sdim // Interference that overlaps an instruction is counted in both gaps 877218885Sdim // surrounding the instruction. The exception is interference before 878218885Sdim // StartIdx and after StopIdx. 879218885Sdim // 880218885Sdim LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx); 881218885Sdim for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 882218885Sdim // Skip the gaps before IntI. 883218885Sdim while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 884218885Sdim if (++Gap == NumGaps) 885218885Sdim break; 886218885Sdim if (Gap == NumGaps) 887218885Sdim break; 888218885Sdim 889218885Sdim // Update the gaps covered by IntI. 890218885Sdim const float weight = IntI.value()->weight; 891218885Sdim for (; Gap != NumGaps; ++Gap) { 892218885Sdim GapWeight[Gap] = std::max(GapWeight[Gap], weight); 893218885Sdim if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 894218885Sdim break; 895218885Sdim } 896218885Sdim if (Gap == NumGaps) 897218885Sdim break; 898218885Sdim } 899218885Sdim } 900218885Sdim} 901218885Sdim 902218885Sdim/// getPrevMappedIndex - Return the slot index of the last non-copy instruction 903218885Sdim/// before MI that has a slot index. If MI is the first mapped instruction in 904218885Sdim/// its block, return the block start index instead. 905218885Sdim/// 906218885SdimSlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) { 907218885Sdim assert(MI && "Missing MachineInstr"); 908218885Sdim const MachineBasicBlock *MBB = MI->getParent(); 909218885Sdim MachineBasicBlock::const_iterator B = MBB->begin(), I = MI; 910218885Sdim while (I != B) 911218885Sdim if (!(--I)->isDebugValue() && !I->isCopy()) 912218885Sdim return Indexes->getInstructionIndex(I); 913218885Sdim return Indexes->getMBBStartIdx(MBB); 914218885Sdim} 915218885Sdim 916218885Sdim/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous 917218885Sdim/// real non-copy instruction for each instruction in SA->UseSlots. 918218885Sdim/// 919218885Sdimvoid RAGreedy::calcPrevSlots() { 920218885Sdim const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 921218885Sdim PrevSlot.clear(); 922218885Sdim PrevSlot.reserve(Uses.size()); 923218885Sdim for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 924218885Sdim const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]); 925218885Sdim PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex()); 926218885Sdim } 927218885Sdim} 928218885Sdim 929218885Sdim/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may 930218885Sdim/// be beneficial to split before UseSlots[i]. 931218885Sdim/// 932218885Sdim/// 0 is always a valid split point 933218885Sdimunsigned RAGreedy::nextSplitPoint(unsigned i) { 934218885Sdim const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 935218885Sdim const unsigned Size = Uses.size(); 936218885Sdim assert(i != Size && "No split points after the end"); 937218885Sdim // Allow split before i when Uses[i] is not adjacent to the previous use. 938218885Sdim while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex()) 939218885Sdim ; 940218885Sdim return i; 941218885Sdim} 942218885Sdim 943218885Sdim/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 944218885Sdim/// basic block. 945218885Sdim/// 946218885Sdimunsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 947218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 948218885Sdim assert(SA->LiveBlocks.size() == 1 && "Not a local interval"); 949218885Sdim const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front(); 950218885Sdim 951218885Sdim // Note that it is possible to have an interval that is live-in or live-out 952218885Sdim // while only covering a single block - A phi-def can use undef values from 953218885Sdim // predecessors, and the block could be a single-block loop. 954218885Sdim // We don't bother doing anything clever about such a case, we simply assume 955218885Sdim // that the interval is continuous from FirstUse to LastUse. We should make 956218885Sdim // sure that we don't do anything illegal to such an interval, though. 957218885Sdim 958218885Sdim const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots; 959218885Sdim if (Uses.size() <= 2) 960218885Sdim return 0; 961218885Sdim const unsigned NumGaps = Uses.size()-1; 962218885Sdim 963218885Sdim DEBUG({ 964218885Sdim dbgs() << "tryLocalSplit: "; 965218885Sdim for (unsigned i = 0, e = Uses.size(); i != e; ++i) 966218885Sdim dbgs() << ' ' << SA->UseSlots[i]; 967218885Sdim dbgs() << '\n'; 968218885Sdim }); 969218885Sdim 970218885Sdim // For every use, find the previous mapped non-copy instruction. 971218885Sdim // We use this to detect valid split points, and to estimate new interval 972218885Sdim // sizes. 973218885Sdim calcPrevSlots(); 974218885Sdim 975218885Sdim unsigned BestBefore = NumGaps; 976218885Sdim unsigned BestAfter = 0; 977218885Sdim float BestDiff = 0; 978218885Sdim 979218885Sdim const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB); 980218885Sdim SmallVector<float, 8> GapWeight; 981218885Sdim 982218885Sdim Order.rewind(); 983218885Sdim while (unsigned PhysReg = Order.next()) { 984218885Sdim // Keep track of the largest spill weight that would need to be evicted in 985218885Sdim // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 986218885Sdim calcGapWeights(PhysReg, GapWeight); 987218885Sdim 988218885Sdim // Try to find the best sequence of gaps to close. 989218885Sdim // The new spill weight must be larger than any gap interference. 990218885Sdim 991218885Sdim // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 992218885Sdim unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1; 993218885Sdim 994218885Sdim // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 995218885Sdim // It is the spill weight that needs to be evicted. 996218885Sdim float MaxGap = GapWeight[0]; 997218885Sdim for (unsigned i = 1; i != SplitAfter; ++i) 998218885Sdim MaxGap = std::max(MaxGap, GapWeight[i]); 999218885Sdim 1000218885Sdim for (;;) { 1001218885Sdim // Live before/after split? 1002218885Sdim const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1003218885Sdim const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1004218885Sdim 1005218885Sdim DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1006218885Sdim << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1007218885Sdim << " i=" << MaxGap); 1008218885Sdim 1009218885Sdim // Stop before the interval gets so big we wouldn't be making progress. 1010218885Sdim if (!LiveBefore && !LiveAfter) { 1011218885Sdim DEBUG(dbgs() << " all\n"); 1012218885Sdim break; 1013218885Sdim } 1014218885Sdim // Should the interval be extended or shrunk? 1015218885Sdim bool Shrink = true; 1016218885Sdim if (MaxGap < HUGE_VALF) { 1017218885Sdim // Estimate the new spill weight. 1018218885Sdim // 1019218885Sdim // Each instruction reads and writes the register, except the first 1020218885Sdim // instr doesn't read when !FirstLive, and the last instr doesn't write 1021218885Sdim // when !LastLive. 1022218885Sdim // 1023218885Sdim // We will be inserting copies before and after, so the total number of 1024218885Sdim // reads and writes is 2 * EstUses. 1025218885Sdim // 1026218885Sdim const unsigned EstUses = 2*(SplitAfter - SplitBefore) + 1027218885Sdim 2*(LiveBefore + LiveAfter); 1028218885Sdim 1029218885Sdim // Try to guess the size of the new interval. This should be trivial, 1030218885Sdim // but the slot index of an inserted copy can be a lot smaller than the 1031218885Sdim // instruction it is inserted before if there are many dead indexes 1032218885Sdim // between them. 1033218885Sdim // 1034218885Sdim // We measure the distance from the instruction before SplitBefore to 1035218885Sdim // get a conservative estimate. 1036218885Sdim // 1037218885Sdim // The final distance can still be different if inserting copies 1038218885Sdim // triggers a slot index renumbering. 1039218885Sdim // 1040218885Sdim const float EstWeight = normalizeSpillWeight(blockFreq * EstUses, 1041218885Sdim PrevSlot[SplitBefore].distance(Uses[SplitAfter])); 1042218885Sdim // Would this split be possible to allocate? 1043218885Sdim // Never allocate all gaps, we wouldn't be making progress. 1044218885Sdim float Diff = EstWeight - MaxGap; 1045218885Sdim DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff); 1046218885Sdim if (Diff > 0) { 1047218885Sdim Shrink = false; 1048218885Sdim if (Diff > BestDiff) { 1049218885Sdim DEBUG(dbgs() << " (best)"); 1050218885Sdim BestDiff = Diff; 1051218885Sdim BestBefore = SplitBefore; 1052218885Sdim BestAfter = SplitAfter; 1053218885Sdim } 1054218885Sdim } 1055218885Sdim } 1056218885Sdim 1057218885Sdim // Try to shrink. 1058218885Sdim if (Shrink) { 1059218885Sdim SplitBefore = nextSplitPoint(SplitBefore); 1060218885Sdim if (SplitBefore < SplitAfter) { 1061218885Sdim DEBUG(dbgs() << " shrink\n"); 1062218885Sdim // Recompute the max when necessary. 1063218885Sdim if (GapWeight[SplitBefore - 1] >= MaxGap) { 1064218885Sdim MaxGap = GapWeight[SplitBefore]; 1065218885Sdim for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1066218885Sdim MaxGap = std::max(MaxGap, GapWeight[i]); 1067218885Sdim } 1068218885Sdim continue; 1069218885Sdim } 1070218885Sdim MaxGap = 0; 1071218885Sdim } 1072218885Sdim 1073218885Sdim // Try to extend the interval. 1074218885Sdim if (SplitAfter >= NumGaps) { 1075218885Sdim DEBUG(dbgs() << " end\n"); 1076218885Sdim break; 1077218885Sdim } 1078218885Sdim 1079218885Sdim DEBUG(dbgs() << " extend\n"); 1080218885Sdim for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1; 1081218885Sdim SplitAfter != e; ++SplitAfter) 1082218885Sdim MaxGap = std::max(MaxGap, GapWeight[SplitAfter]); 1083218885Sdim continue; 1084218885Sdim } 1085218885Sdim } 1086218885Sdim 1087218885Sdim // Didn't find any candidates? 1088218885Sdim if (BestBefore == NumGaps) 1089218885Sdim return 0; 1090218885Sdim 1091218885Sdim DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1092218885Sdim << '-' << Uses[BestAfter] << ", " << BestDiff 1093218885Sdim << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1094218885Sdim 1095218885Sdim SmallVector<LiveInterval*, 4> SpillRegs; 1096218885Sdim LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 1097218885Sdim SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit); 1098218885Sdim 1099218885Sdim SE.openIntv(); 1100218885Sdim SlotIndex SegStart = SE.enterIntvBefore(Uses[BestBefore]); 1101218885Sdim SlotIndex SegStop = SE.leaveIntvAfter(Uses[BestAfter]); 1102218885Sdim SE.useIntv(SegStart, SegStop); 1103218885Sdim SE.closeIntv(); 1104218885Sdim SE.finish(); 1105218885Sdim ++NumLocalSplits; 1106218885Sdim 1107218885Sdim return 0; 1108218885Sdim} 1109218885Sdim 1110218885Sdim//===----------------------------------------------------------------------===// 1111218885Sdim// Live Range Splitting 1112218885Sdim//===----------------------------------------------------------------------===// 1113218885Sdim 1114218885Sdim/// trySplit - Try to split VirtReg or one of its interferences, making it 1115218885Sdim/// assignable. 1116218885Sdim/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1117218885Sdimunsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1118218885Sdim SmallVectorImpl<LiveInterval*>&NewVRegs) { 1119218885Sdim SA->analyze(&VirtReg); 1120218885Sdim 1121218885Sdim // Local intervals are handled separately. 1122218885Sdim if (LIS->intervalIsInOneMBB(VirtReg)) { 1123218885Sdim NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1124218885Sdim return tryLocalSplit(VirtReg, Order, NewVRegs); 1125218885Sdim } 1126218885Sdim 1127218885Sdim NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1128218885Sdim 1129218885Sdim // First try to split around a region spanning multiple blocks. 1130218885Sdim unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1131218885Sdim if (PhysReg || !NewVRegs.empty()) 1132218885Sdim return PhysReg; 1133218885Sdim 1134218885Sdim // Then isolate blocks with multiple uses. 1135218885Sdim SplitAnalysis::BlockPtrSet Blocks; 1136218885Sdim if (SA->getMultiUseBlocks(Blocks)) { 1137218885Sdim SmallVector<LiveInterval*, 4> SpillRegs; 1138218885Sdim LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs); 1139218885Sdim SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks); 1140218885Sdim if (VerifyEnabled) 1141218885Sdim MF->verify(this, "After splitting live range around basic blocks"); 1142218885Sdim } 1143218885Sdim 1144218885Sdim // Don't assign any physregs. 1145218885Sdim return 0; 1146218885Sdim} 1147218885Sdim 1148218885Sdim 1149218885Sdim//===----------------------------------------------------------------------===// 1150218885Sdim// Spilling 1151218885Sdim//===----------------------------------------------------------------------===// 1152218885Sdim 1153218885Sdim/// calcInterferenceWeight - Calculate the combined spill weight of 1154218885Sdim/// interferences when assigning VirtReg to PhysReg. 1155218885Sdimfloat RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){ 1156218885Sdim float Sum = 0; 1157218885Sdim for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) { 1158218885Sdim LiveIntervalUnion::Query &Q = query(VirtReg, *AI); 1159218885Sdim Q.collectInterferingVRegs(); 1160218885Sdim if (Q.seenUnspillableVReg()) 1161218885Sdim return HUGE_VALF; 1162218885Sdim for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) 1163218885Sdim Sum += Q.interferingVRegs()[i]->weight; 1164218885Sdim } 1165218885Sdim return Sum; 1166218885Sdim} 1167218885Sdim 1168218885Sdim/// trySpillInterferences - Try to spill interfering registers instead of the 1169218885Sdim/// current one. Only do it if the accumulated spill weight is smaller than the 1170218885Sdim/// current spill weight. 1171218885Sdimunsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg, 1172218885Sdim AllocationOrder &Order, 1173218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 1174218885Sdim NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled); 1175218885Sdim unsigned BestPhys = 0; 1176218885Sdim float BestWeight = 0; 1177218885Sdim 1178218885Sdim Order.rewind(); 1179218885Sdim while (unsigned PhysReg = Order.next()) { 1180218885Sdim float Weight = calcInterferenceWeight(VirtReg, PhysReg); 1181218885Sdim if (Weight == HUGE_VALF || Weight >= VirtReg.weight) 1182218885Sdim continue; 1183218885Sdim if (!BestPhys || Weight < BestWeight) 1184218885Sdim BestPhys = PhysReg, BestWeight = Weight; 1185218885Sdim } 1186218885Sdim 1187218885Sdim // No candidates found. 1188218885Sdim if (!BestPhys) 1189218885Sdim return 0; 1190218885Sdim 1191218885Sdim // Collect all interfering registers. 1192218885Sdim SmallVector<LiveInterval*, 8> Spills; 1193218885Sdim for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) { 1194218885Sdim LiveIntervalUnion::Query &Q = query(VirtReg, *AI); 1195218885Sdim Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end()); 1196218885Sdim for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { 1197218885Sdim LiveInterval *VReg = Q.interferingVRegs()[i]; 1198218885Sdim unassign(*VReg, *AI); 1199218885Sdim } 1200218885Sdim } 1201218885Sdim 1202218885Sdim // Spill them all. 1203218885Sdim DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight " 1204218885Sdim << BestWeight << '\n'); 1205218885Sdim for (unsigned i = 0, e = Spills.size(); i != e; ++i) 1206218885Sdim spiller().spill(Spills[i], NewVRegs, Spills); 1207218885Sdim return BestPhys; 1208218885Sdim} 1209218885Sdim 1210218885Sdim 1211218885Sdim//===----------------------------------------------------------------------===// 1212218885Sdim// Main Entry Point 1213218885Sdim//===----------------------------------------------------------------------===// 1214218885Sdim 1215218885Sdimunsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 1216218885Sdim SmallVectorImpl<LiveInterval*> &NewVRegs) { 1217218885Sdim // First try assigning a free register. 1218218885Sdim AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs); 1219218885Sdim while (unsigned PhysReg = Order.next()) { 1220218885Sdim if (!checkPhysRegInterference(VirtReg, PhysReg)) 1221218885Sdim return PhysReg; 1222218885Sdim } 1223218885Sdim 1224218885Sdim // Try to reassign interferences. 1225218885Sdim if (unsigned PhysReg = tryReassignOrEvict(VirtReg, Order, NewVRegs)) 1226218885Sdim return PhysReg; 1227218885Sdim 1228218885Sdim assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 1229218885Sdim 1230218885Sdim // Try splitting VirtReg or interferences. 1231218885Sdim unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 1232218885Sdim if (PhysReg || !NewVRegs.empty()) 1233218885Sdim return PhysReg; 1234218885Sdim 1235218885Sdim // Try to spill another interfering reg with less spill weight. 1236218885Sdim PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs); 1237218885Sdim if (PhysReg) 1238218885Sdim return PhysReg; 1239218885Sdim 1240218885Sdim // Finally spill VirtReg itself. 1241218885Sdim NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 1242218885Sdim SmallVector<LiveInterval*, 1> pendingSpills; 1243218885Sdim spiller().spill(&VirtReg, NewVRegs, pendingSpills); 1244218885Sdim 1245218885Sdim // The live virtual register requesting allocation was spilled, so tell 1246218885Sdim // the caller not to allocate anything during this round. 1247218885Sdim return 0; 1248218885Sdim} 1249218885Sdim 1250218885Sdimbool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 1251218885Sdim DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 1252218885Sdim << "********** Function: " 1253218885Sdim << ((Value*)mf.getFunction())->getName() << '\n'); 1254218885Sdim 1255218885Sdim MF = &mf; 1256218885Sdim if (VerifyEnabled) 1257218885Sdim MF->verify(this, "Before greedy register allocator"); 1258218885Sdim 1259218885Sdim RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>()); 1260218885Sdim Indexes = &getAnalysis<SlotIndexes>(); 1261218885Sdim DomTree = &getAnalysis<MachineDominatorTree>(); 1262218885Sdim ReservedRegs = TRI->getReservedRegs(*MF); 1263218885Sdim SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 1264218885Sdim Loops = &getAnalysis<MachineLoopInfo>(); 1265218885Sdim LoopRanges = &getAnalysis<MachineLoopRanges>(); 1266218885Sdim Bundles = &getAnalysis<EdgeBundles>(); 1267218885Sdim SpillPlacer = &getAnalysis<SpillPlacement>(); 1268218885Sdim 1269218885Sdim SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 1270218885Sdim 1271218885Sdim allocatePhysRegs(); 1272218885Sdim addMBBLiveIns(MF); 1273218885Sdim LIS->addKillFlags(); 1274218885Sdim 1275218885Sdim // Run rewriter 1276218885Sdim { 1277218885Sdim NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled); 1278218885Sdim VRM->rewrite(Indexes); 1279218885Sdim } 1280218885Sdim 1281218885Sdim // The pass output is in VirtRegMap. Release all the transient data. 1282218885Sdim releaseMemory(); 1283218885Sdim 1284218885Sdim return true; 1285218885Sdim} 1286