RegAllocGreedy.cpp revision 303975
1170754Sdelphij//===-- RegAllocGreedy.cpp - greedy register allocator --------------------===// 2170754Sdelphij// 3170754Sdelphij// The LLVM Compiler Infrastructure 4170754Sdelphij// 5170754Sdelphij// This file is distributed under the University of Illinois Open Source 6170754Sdelphij// License. See LICENSE.TXT for details. 7170754Sdelphij// 8170754Sdelphij//===----------------------------------------------------------------------===// 9170754Sdelphij// 10170754Sdelphij// This file defines the RAGreedy function pass for register allocation in 11170754Sdelphij// optimized builds. 12170754Sdelphij// 13170754Sdelphij//===----------------------------------------------------------------------===// 14170754Sdelphij 15170754Sdelphij#include "llvm/CodeGen/Passes.h" 16170754Sdelphij#include "AllocationOrder.h" 17170754Sdelphij#include "InterferenceCache.h" 18170754Sdelphij#include "LiveDebugVariables.h" 19170754Sdelphij#include "RegAllocBase.h" 20170754Sdelphij#include "SpillPlacement.h" 21170754Sdelphij#include "Spiller.h" 22170754Sdelphij#include "SplitKit.h" 23170754Sdelphij#include "llvm/ADT/Statistic.h" 24170754Sdelphij#include "llvm/Analysis/AliasAnalysis.h" 25170754Sdelphij#include "llvm/CodeGen/CalcSpillWeights.h" 26170754Sdelphij#include "llvm/CodeGen/EdgeBundles.h" 27170754Sdelphij#include "llvm/CodeGen/LiveIntervalAnalysis.h" 28170754Sdelphij#include "llvm/CodeGen/LiveRangeEdit.h" 29170754Sdelphij#include "llvm/CodeGen/LiveRegMatrix.h" 30170754Sdelphij#include "llvm/CodeGen/LiveStackAnalysis.h" 31170754Sdelphij#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 32170754Sdelphij#include "llvm/CodeGen/MachineDominators.h" 33170754Sdelphij#include "llvm/CodeGen/MachineFunctionPass.h" 34170754Sdelphij#include "llvm/CodeGen/MachineLoopInfo.h" 35170754Sdelphij#include "llvm/CodeGen/MachineRegisterInfo.h" 36170754Sdelphij#include "llvm/CodeGen/RegAllocRegistry.h" 37170754Sdelphij#include "llvm/CodeGen/RegisterClassInfo.h" 38170754Sdelphij#include "llvm/CodeGen/VirtRegMap.h" 39170754Sdelphij#include "llvm/IR/LLVMContext.h" 40170754Sdelphij#include "llvm/PassAnalysisSupport.h" 41170754Sdelphij#include "llvm/Support/BranchProbability.h" 42170754Sdelphij#include "llvm/Support/CommandLine.h" 43170754Sdelphij#include "llvm/Support/Debug.h" 44170754Sdelphij#include "llvm/Support/ErrorHandling.h" 45170754Sdelphij#include "llvm/Support/Timer.h" 46170754Sdelphij#include "llvm/Support/raw_ostream.h" 47170754Sdelphij#include "llvm/Target/TargetSubtargetInfo.h" 48170754Sdelphij#include <queue> 49170754Sdelphij 50170754Sdelphijusing namespace llvm; 51170754Sdelphij 52170754Sdelphij#define DEBUG_TYPE "regalloc" 53170754Sdelphij 54170754SdelphijSTATISTIC(NumGlobalSplits, "Number of split global live ranges"); 55170754SdelphijSTATISTIC(NumLocalSplits, "Number of split local live ranges"); 56170754SdelphijSTATISTIC(NumEvicted, "Number of interferences evicted"); 57170754Sdelphij 58170754Sdelphijstatic cl::opt<SplitEditor::ComplementSpillMode> 59170754SdelphijSplitSpillMode("split-spill-mode", cl::Hidden, 60170754Sdelphij cl::desc("Spill mode for splitting live ranges"), 61170754Sdelphij cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), 62170754Sdelphij clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), 63170754Sdelphij clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"), 64170754Sdelphij clEnumValEnd), 65170754Sdelphij cl::init(SplitEditor::SM_Partition)); 66170754Sdelphij 67170754Sdelphijstatic cl::opt<unsigned> 68170754SdelphijLastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, 69170754Sdelphij cl::desc("Last chance recoloring max depth"), 70170754Sdelphij cl::init(5)); 71170754Sdelphij 72170754Sdelphijstatic cl::opt<unsigned> LastChanceRecoloringMaxInterference( 73170754Sdelphij "lcr-max-interf", cl::Hidden, 74170754Sdelphij cl::desc("Last chance recoloring maximum number of considered" 75170754Sdelphij " interference at a time"), 76170754Sdelphij cl::init(8)); 77170754Sdelphij 78170754Sdelphijstatic cl::opt<bool> 79170754SdelphijExhaustiveSearch("exhaustive-register-search", cl::NotHidden, 80170754Sdelphij cl::desc("Exhaustive Search for registers bypassing the depth " 81170754Sdelphij "and interference cutoffs of last chance recoloring")); 82170754Sdelphij 83170754Sdelphijstatic cl::opt<bool> EnableLocalReassignment( 84170754Sdelphij "enable-local-reassign", cl::Hidden, 85170754Sdelphij cl::desc("Local reassignment can yield better allocation decisions, but " 86170754Sdelphij "may be compile time intensive"), 87170754Sdelphij cl::init(false)); 88170754Sdelphij 89170754Sdelphijstatic cl::opt<bool> EnableDeferredSpilling( 90170754Sdelphij "enable-deferred-spilling", cl::Hidden, 91170754Sdelphij cl::desc("Instead of spilling a variable right away, defer the actual " 92170754Sdelphij "code insertion to the end of the allocation. That way the " 93170754Sdelphij "allocator might still find a suitable coloring for this " 94170754Sdelphij "variable because of other evicted variables."), 95170754Sdelphij cl::init(false)); 96170754Sdelphij 97170754Sdelphij// FIXME: Find a good default for this flag and remove the flag. 98170754Sdelphijstatic cl::opt<unsigned> 99170754SdelphijCSRFirstTimeCost("regalloc-csr-first-time-cost", 100170754Sdelphij cl::desc("Cost for first time use of callee-saved register."), 101170754Sdelphij cl::init(0), cl::Hidden); 102170754Sdelphij 103170754Sdelphijstatic RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", 104170754Sdelphij createGreedyRegisterAllocator); 105170754Sdelphij 106170754Sdelphijnamespace { 107170754Sdelphijclass RAGreedy : public MachineFunctionPass, 108170754Sdelphij public RegAllocBase, 109170754Sdelphij private LiveRangeEdit::Delegate { 110170754Sdelphij // Convenient shortcuts. 111170754Sdelphij typedef std::priority_queue<std::pair<unsigned, unsigned> > PQueue; 112170754Sdelphij typedef SmallPtrSet<LiveInterval *, 4> SmallLISet; 113170754Sdelphij typedef SmallSet<unsigned, 16> SmallVirtRegSet; 114170754Sdelphij 115170754Sdelphij // context 116170754Sdelphij MachineFunction *MF; 117170754Sdelphij 118170754Sdelphij // Shortcuts to some useful interface. 119170754Sdelphij const TargetInstrInfo *TII; 120170754Sdelphij const TargetRegisterInfo *TRI; 121170754Sdelphij RegisterClassInfo RCI; 122170754Sdelphij 123170754Sdelphij // analyses 124170754Sdelphij SlotIndexes *Indexes; 125170754Sdelphij MachineBlockFrequencyInfo *MBFI; 126170754Sdelphij MachineDominatorTree *DomTree; 127170754Sdelphij MachineLoopInfo *Loops; 128170754Sdelphij EdgeBundles *Bundles; 129170754Sdelphij SpillPlacement *SpillPlacer; 130170754Sdelphij LiveDebugVariables *DebugVars; 131170754Sdelphij 132170754Sdelphij // state 133170754Sdelphij std::unique_ptr<Spiller> SpillerInstance; 134170754Sdelphij PQueue Queue; 135170754Sdelphij unsigned NextCascade; 136170754Sdelphij 137170754Sdelphij // Live ranges pass through a number of stages as we try to allocate them. 138170754Sdelphij // Some of the stages may also create new live ranges: 139170754Sdelphij // 140170754Sdelphij // - Region splitting. 141170754Sdelphij // - Per-block splitting. 142170754Sdelphij // - Local splitting. 143170754Sdelphij // - Spilling. 144170754Sdelphij // 145170754Sdelphij // Ranges produced by one of the stages skip the previous stages when they are 146170754Sdelphij // dequeued. This improves performance because we can skip interference checks 147170754Sdelphij // that are unlikely to give any results. It also guarantees that the live 148170754Sdelphij // range splitting algorithm terminates, something that is otherwise hard to 149170754Sdelphij // ensure. 150170754Sdelphij enum LiveRangeStage { 151170754Sdelphij /// Newly created live range that has never been queued. 152170754Sdelphij RS_New, 153170754Sdelphij 154170754Sdelphij /// Only attempt assignment and eviction. Then requeue as RS_Split. 155170754Sdelphij RS_Assign, 156170754Sdelphij 157170754Sdelphij /// Attempt live range splitting if assignment is impossible. 158170754Sdelphij RS_Split, 159170754Sdelphij 160170754Sdelphij /// Attempt more aggressive live range splitting that is guaranteed to make 161170754Sdelphij /// progress. This is used for split products that may not be making 162170754Sdelphij /// progress. 163170754Sdelphij RS_Split2, 164170754Sdelphij 165170754Sdelphij /// Live range will be spilled. No more splitting will be attempted. 166170754Sdelphij RS_Spill, 167170754Sdelphij 168170754Sdelphij 169170754Sdelphij /// Live range is in memory. Because of other evictions, it might get moved 170170754Sdelphij /// in a register in the end. 171170754Sdelphij RS_Memory, 172170754Sdelphij 173170754Sdelphij /// There is nothing more we can do to this live range. Abort compilation 174170754Sdelphij /// if it can't be assigned. 175170754Sdelphij RS_Done 176170754Sdelphij }; 177170754Sdelphij 178170754Sdelphij // Enum CutOffStage to keep a track whether the register allocation failed 179170754Sdelphij // because of the cutoffs encountered in last chance recoloring. 180170754Sdelphij // Note: This is used as bitmask. New value should be next power of 2. 181170754Sdelphij enum CutOffStage { 182170754Sdelphij // No cutoffs encountered 183170754Sdelphij CO_None = 0, 184170754Sdelphij 185170754Sdelphij // lcr-max-depth cutoff encountered 186170754Sdelphij CO_Depth = 1, 187170754Sdelphij 188170754Sdelphij // lcr-max-interf cutoff encountered 189170754Sdelphij CO_Interf = 2 190170754Sdelphij }; 191170754Sdelphij 192170754Sdelphij uint8_t CutOffInfo; 193170754Sdelphij 194170754Sdelphij#ifndef NDEBUG 195170754Sdelphij static const char *const StageName[]; 196170754Sdelphij#endif 197170754Sdelphij 198170754Sdelphij // RegInfo - Keep additional information about each live range. 199170754Sdelphij struct RegInfo { 200170754Sdelphij LiveRangeStage Stage; 201170754Sdelphij 202170754Sdelphij // Cascade - Eviction loop prevention. See canEvictInterference(). 203170754Sdelphij unsigned Cascade; 204170754Sdelphij 205170754Sdelphij RegInfo() : Stage(RS_New), Cascade(0) {} 206170754Sdelphij }; 207170754Sdelphij 208170754Sdelphij IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo; 209170754Sdelphij 210170754Sdelphij LiveRangeStage getStage(const LiveInterval &VirtReg) const { 211170754Sdelphij return ExtraRegInfo[VirtReg.reg].Stage; 212170754Sdelphij } 213170754Sdelphij 214170754Sdelphij void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) { 215170754Sdelphij ExtraRegInfo.resize(MRI->getNumVirtRegs()); 216170754Sdelphij ExtraRegInfo[VirtReg.reg].Stage = Stage; 217170754Sdelphij } 218170754Sdelphij 219170754Sdelphij template<typename Iterator> 220170754Sdelphij void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) { 221170754Sdelphij ExtraRegInfo.resize(MRI->getNumVirtRegs()); 222170754Sdelphij for (;Begin != End; ++Begin) { 223170754Sdelphij unsigned Reg = *Begin; 224170754Sdelphij if (ExtraRegInfo[Reg].Stage == RS_New) 225170754Sdelphij ExtraRegInfo[Reg].Stage = NewStage; 226170754Sdelphij } 227170754Sdelphij } 228170754Sdelphij 229170754Sdelphij /// Cost of evicting interference. 230170754Sdelphij struct EvictionCost { 231170754Sdelphij unsigned BrokenHints; ///< Total number of broken hints. 232170754Sdelphij float MaxWeight; ///< Maximum spill weight evicted. 233170754Sdelphij 234170754Sdelphij EvictionCost(): BrokenHints(0), MaxWeight(0) {} 235170754Sdelphij 236170754Sdelphij bool isMax() const { return BrokenHints == ~0u; } 237170754Sdelphij 238170754Sdelphij void setMax() { BrokenHints = ~0u; } 239170754Sdelphij 240170754Sdelphij void setBrokenHints(unsigned NHints) { BrokenHints = NHints; } 241170754Sdelphij 242170754Sdelphij bool operator<(const EvictionCost &O) const { 243170754Sdelphij return std::tie(BrokenHints, MaxWeight) < 244170754Sdelphij std::tie(O.BrokenHints, O.MaxWeight); 245170754Sdelphij } 246170754Sdelphij }; 247170754Sdelphij 248170754Sdelphij // splitting state. 249170754Sdelphij std::unique_ptr<SplitAnalysis> SA; 250170754Sdelphij std::unique_ptr<SplitEditor> SE; 251170754Sdelphij 252170754Sdelphij /// Cached per-block interference maps 253170754Sdelphij InterferenceCache IntfCache; 254170754Sdelphij 255170754Sdelphij /// All basic blocks where the current register has uses. 256170754Sdelphij SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints; 257170754Sdelphij 258170754Sdelphij /// Global live range splitting candidate info. 259170754Sdelphij struct GlobalSplitCandidate { 260170754Sdelphij // Register intended for assignment, or 0. 261170754Sdelphij unsigned PhysReg; 262170754Sdelphij 263170754Sdelphij // SplitKit interval index for this candidate. 264170754Sdelphij unsigned IntvIdx; 265170754Sdelphij 266170754Sdelphij // Interference for PhysReg. 267170754Sdelphij InterferenceCache::Cursor Intf; 268170754Sdelphij 269170754Sdelphij // Bundles where this candidate should be live. 270170754Sdelphij BitVector LiveBundles; 271170754Sdelphij SmallVector<unsigned, 8> ActiveBlocks; 272170754Sdelphij 273170754Sdelphij void reset(InterferenceCache &Cache, unsigned Reg) { 274170754Sdelphij PhysReg = Reg; 275170754Sdelphij IntvIdx = 0; 276170754Sdelphij Intf.setPhysReg(Cache, Reg); 277170754Sdelphij LiveBundles.clear(); 278170754Sdelphij ActiveBlocks.clear(); 279170754Sdelphij } 280170754Sdelphij 281170754Sdelphij // Set B[i] = C for every live bundle where B[i] was NoCand. 282170754Sdelphij unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) { 283170754Sdelphij unsigned Count = 0; 284170754Sdelphij for (int i = LiveBundles.find_first(); i >= 0; 285170754Sdelphij i = LiveBundles.find_next(i)) 286170754Sdelphij if (B[i] == NoCand) { 287170754Sdelphij B[i] = C; 288170754Sdelphij Count++; 289170754Sdelphij } 290170754Sdelphij return Count; 291170754Sdelphij } 292170754Sdelphij }; 293170754Sdelphij 294170754Sdelphij /// Candidate info for each PhysReg in AllocationOrder. 295170754Sdelphij /// This vector never shrinks, but grows to the size of the largest register 296170754Sdelphij /// class. 297170754Sdelphij SmallVector<GlobalSplitCandidate, 32> GlobalCand; 298170754Sdelphij 299170754Sdelphij enum : unsigned { NoCand = ~0u }; 300170754Sdelphij 301170754Sdelphij /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to 302170754Sdelphij /// NoCand which indicates the stack interval. 303170754Sdelphij SmallVector<unsigned, 32> BundleCand; 304170754Sdelphij 305170754Sdelphij /// Callee-save register cost, calculated once per machine function. 306170754Sdelphij BlockFrequency CSRCost; 307170754Sdelphij 308170754Sdelphij /// Run or not the local reassignment heuristic. This information is 309170754Sdelphij /// obtained from the TargetSubtargetInfo. 310170754Sdelphij bool EnableLocalReassign; 311170754Sdelphij 312170754Sdelphij /// Set of broken hints that may be reconciled later because of eviction. 313170754Sdelphij SmallSetVector<LiveInterval *, 8> SetOfBrokenHints; 314170754Sdelphij 315170754Sdelphijpublic: 316170754Sdelphij RAGreedy(); 317170754Sdelphij 318170754Sdelphij /// Return the pass name. 319170754Sdelphij const char* getPassName() const override { 320170754Sdelphij return "Greedy Register Allocator"; 321170754Sdelphij } 322170754Sdelphij 323170754Sdelphij /// RAGreedy analysis usage. 324170754Sdelphij void getAnalysisUsage(AnalysisUsage &AU) const override; 325170754Sdelphij void releaseMemory() override; 326170754Sdelphij Spiller &spiller() override { return *SpillerInstance; } 327170754Sdelphij void enqueue(LiveInterval *LI) override; 328170754Sdelphij LiveInterval *dequeue() override; 329170754Sdelphij unsigned selectOrSplit(LiveInterval&, SmallVectorImpl<unsigned>&) override; 330170754Sdelphij void aboutToRemoveInterval(LiveInterval &) override; 331170754Sdelphij 332170754Sdelphij /// Perform register allocation. 333170754Sdelphij bool runOnMachineFunction(MachineFunction &mf) override; 334170754Sdelphij 335170754Sdelphij static char ID; 336170754Sdelphij 337170754Sdelphijprivate: 338170754Sdelphij unsigned selectOrSplitImpl(LiveInterval &, SmallVectorImpl<unsigned> &, 339170754Sdelphij SmallVirtRegSet &, unsigned = 0); 340170754Sdelphij 341170754Sdelphij bool LRE_CanEraseVirtReg(unsigned) override; 342170754Sdelphij void LRE_WillShrinkVirtReg(unsigned) override; 343170754Sdelphij void LRE_DidCloneVirtReg(unsigned, unsigned) override; 344170754Sdelphij void enqueue(PQueue &CurQueue, LiveInterval *LI); 345170754Sdelphij LiveInterval *dequeue(PQueue &CurQueue); 346170754Sdelphij 347170754Sdelphij BlockFrequency calcSpillCost(); 348170754Sdelphij bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&); 349170754Sdelphij void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>); 350170754Sdelphij void growRegion(GlobalSplitCandidate &Cand); 351170754Sdelphij BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate&); 352170754Sdelphij bool calcCompactRegion(GlobalSplitCandidate&); 353170754Sdelphij void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>); 354170754Sdelphij void calcGapWeights(unsigned, SmallVectorImpl<float>&); 355170754Sdelphij unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg); 356170754Sdelphij bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool); 357170754Sdelphij bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&); 358170754Sdelphij void evictInterference(LiveInterval&, unsigned, 359170754Sdelphij SmallVectorImpl<unsigned>&); 360170754Sdelphij bool mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg, 361170754Sdelphij SmallLISet &RecoloringCandidates, 362170754Sdelphij const SmallVirtRegSet &FixedRegisters); 363170754Sdelphij 364170754Sdelphij unsigned tryAssign(LiveInterval&, AllocationOrder&, 365170754Sdelphij SmallVectorImpl<unsigned>&); 366170754Sdelphij unsigned tryEvict(LiveInterval&, AllocationOrder&, 367170754Sdelphij SmallVectorImpl<unsigned>&, unsigned = ~0u); 368170754Sdelphij unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, 369170754Sdelphij SmallVectorImpl<unsigned>&); 370170754Sdelphij /// Calculate cost of region splitting. 371170754Sdelphij unsigned calculateRegionSplitCost(LiveInterval &VirtReg, 372170754Sdelphij AllocationOrder &Order, 373170754Sdelphij BlockFrequency &BestCost, 374170754Sdelphij unsigned &NumCands, bool IgnoreCSR); 375170754Sdelphij /// Perform region splitting. 376170754Sdelphij unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand, 377170754Sdelphij bool HasCompact, 378170754Sdelphij SmallVectorImpl<unsigned> &NewVRegs); 379170754Sdelphij /// Check other options before using a callee-saved register for the first 380170754Sdelphij /// time. 381170754Sdelphij unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order, 382170754Sdelphij unsigned PhysReg, unsigned &CostPerUseLimit, 383170754Sdelphij SmallVectorImpl<unsigned> &NewVRegs); 384170754Sdelphij void initializeCSRCost(); 385170754Sdelphij unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, 386170754Sdelphij SmallVectorImpl<unsigned>&); 387170754Sdelphij unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&, 388170754Sdelphij SmallVectorImpl<unsigned>&); 389170754Sdelphij unsigned tryLocalSplit(LiveInterval&, AllocationOrder&, 390170754Sdelphij SmallVectorImpl<unsigned>&); 391170754Sdelphij unsigned trySplit(LiveInterval&, AllocationOrder&, 392170754Sdelphij SmallVectorImpl<unsigned>&); 393170754Sdelphij unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &, 394170754Sdelphij SmallVectorImpl<unsigned> &, 395170754Sdelphij SmallVirtRegSet &, unsigned); 396170754Sdelphij bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<unsigned> &, 397170754Sdelphij SmallVirtRegSet &, unsigned); 398170754Sdelphij void tryHintRecoloring(LiveInterval &); 399170754Sdelphij void tryHintsRecoloring(); 400170754Sdelphij 401170754Sdelphij /// Model the information carried by one end of a copy. 402170754Sdelphij struct HintInfo { 403170754Sdelphij /// The frequency of the copy. 404170754Sdelphij BlockFrequency Freq; 405170754Sdelphij /// The virtual register or physical register. 406170754Sdelphij unsigned Reg; 407170754Sdelphij /// Its currently assigned register. 408170754Sdelphij /// In case of a physical register Reg == PhysReg. 409170754Sdelphij unsigned PhysReg; 410170754Sdelphij HintInfo(BlockFrequency Freq, unsigned Reg, unsigned PhysReg) 411170754Sdelphij : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {} 412170754Sdelphij }; 413170754Sdelphij typedef SmallVector<HintInfo, 4> HintsInfo; 414170754Sdelphij BlockFrequency getBrokenHintFreq(const HintsInfo &, unsigned); 415170754Sdelphij void collectHintInfo(unsigned, HintsInfo &); 416170754Sdelphij 417170754Sdelphij bool isUnusedCalleeSavedReg(unsigned PhysReg) const; 418170754Sdelphij}; 419170754Sdelphij} // end anonymous namespace 420170754Sdelphij 421170754Sdelphijchar RAGreedy::ID = 0; 422170754Sdelphij 423170754Sdelphij#ifndef NDEBUG 424170754Sdelphijconst char *const RAGreedy::StageName[] = { 425170754Sdelphij "RS_New", 426170754Sdelphij "RS_Assign", 427170754Sdelphij "RS_Split", 428170754Sdelphij "RS_Split2", 429170754Sdelphij "RS_Spill", 430170754Sdelphij "RS_Memory", 431170754Sdelphij "RS_Done" 432170754Sdelphij}; 433170754Sdelphij#endif 434170754Sdelphij 435170754Sdelphij// Hysteresis to use when comparing floats. 436170754Sdelphij// This helps stabilize decisions based on float comparisons. 437170754Sdelphijconst float Hysteresis = (2007 / 2048.0f); // 0.97998046875 438170754Sdelphij 439170754Sdelphij 440170754SdelphijFunctionPass* llvm::createGreedyRegisterAllocator() { 441170754Sdelphij return new RAGreedy(); 442170754Sdelphij} 443170754Sdelphij 444170754SdelphijRAGreedy::RAGreedy(): MachineFunctionPass(ID) { 445170754Sdelphij initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 446170754Sdelphij initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 447170754Sdelphij initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 448170754Sdelphij initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 449170754Sdelphij initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 450170754Sdelphij initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 451170754Sdelphij initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 452170754Sdelphij initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); 453170754Sdelphij initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 454170754Sdelphij initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 455170754Sdelphij initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry()); 456170754Sdelphij initializeEdgeBundlesPass(*PassRegistry::getPassRegistry()); 457170754Sdelphij initializeSpillPlacementPass(*PassRegistry::getPassRegistry()); 458170754Sdelphij} 459170754Sdelphij 460170754Sdelphijvoid RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { 461170754Sdelphij AU.setPreservesCFG(); 462170754Sdelphij AU.addRequired<MachineBlockFrequencyInfo>(); 463170754Sdelphij AU.addPreserved<MachineBlockFrequencyInfo>(); 464170754Sdelphij AU.addRequired<AAResultsWrapperPass>(); 465170754Sdelphij AU.addPreserved<AAResultsWrapperPass>(); 466170754Sdelphij AU.addRequired<LiveIntervals>(); 467170754Sdelphij AU.addPreserved<LiveIntervals>(); 468170754Sdelphij AU.addRequired<SlotIndexes>(); 469170754Sdelphij AU.addPreserved<SlotIndexes>(); 470170754Sdelphij AU.addRequired<LiveDebugVariables>(); 471170754Sdelphij AU.addPreserved<LiveDebugVariables>(); 472170754Sdelphij AU.addRequired<LiveStacks>(); 473170754Sdelphij AU.addPreserved<LiveStacks>(); 474170754Sdelphij AU.addRequired<MachineDominatorTree>(); 475170754Sdelphij AU.addPreserved<MachineDominatorTree>(); 476170754Sdelphij AU.addRequired<MachineLoopInfo>(); 477170754Sdelphij AU.addPreserved<MachineLoopInfo>(); 478170754Sdelphij AU.addRequired<VirtRegMap>(); 479170754Sdelphij AU.addPreserved<VirtRegMap>(); 480170754Sdelphij AU.addRequired<LiveRegMatrix>(); 481170754Sdelphij AU.addPreserved<LiveRegMatrix>(); 482170754Sdelphij AU.addRequired<EdgeBundles>(); 483170754Sdelphij AU.addRequired<SpillPlacement>(); 484170754Sdelphij MachineFunctionPass::getAnalysisUsage(AU); 485170754Sdelphij} 486170754Sdelphij 487170754Sdelphij 488170754Sdelphij//===----------------------------------------------------------------------===// 489170754Sdelphij// LiveRangeEdit delegate methods 490170754Sdelphij//===----------------------------------------------------------------------===// 491170754Sdelphij 492170754Sdelphijbool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) { 493170754Sdelphij if (VRM->hasPhys(VirtReg)) { 494170754Sdelphij LiveInterval &LI = LIS->getInterval(VirtReg); 495170754Sdelphij Matrix->unassign(LI); 496170754Sdelphij aboutToRemoveInterval(LI); 497170754Sdelphij return true; 498170754Sdelphij } 499170754Sdelphij // Unassigned virtreg is probably in the priority queue. 500170754Sdelphij // RegAllocBase will erase it after dequeueing. 501170754Sdelphij return false; 502170754Sdelphij} 503170754Sdelphij 504170754Sdelphijvoid RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) { 505170754Sdelphij if (!VRM->hasPhys(VirtReg)) 506170754Sdelphij return; 507170754Sdelphij 508170754Sdelphij // Register is assigned, put it back on the queue for reassignment. 509170754Sdelphij LiveInterval &LI = LIS->getInterval(VirtReg); 510170754Sdelphij Matrix->unassign(LI); 511170754Sdelphij enqueue(&LI); 512170754Sdelphij} 513170754Sdelphij 514170754Sdelphijvoid RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { 515170754Sdelphij // Cloning a register we haven't even heard about yet? Just ignore it. 516170754Sdelphij if (!ExtraRegInfo.inBounds(Old)) 517170754Sdelphij return; 518170754Sdelphij 519170754Sdelphij // LRE may clone a virtual register because dead code elimination causes it to 520170754Sdelphij // be split into connected components. The new components are much smaller 521170754Sdelphij // than the original, so they should get a new chance at being assigned. 522170754Sdelphij // same stage as the parent. 523170754Sdelphij ExtraRegInfo[Old].Stage = RS_Assign; 524170754Sdelphij ExtraRegInfo.grow(New); 525170754Sdelphij ExtraRegInfo[New] = ExtraRegInfo[Old]; 526170754Sdelphij} 527170754Sdelphij 528170754Sdelphijvoid RAGreedy::releaseMemory() { 529170754Sdelphij SpillerInstance.reset(); 530170754Sdelphij ExtraRegInfo.clear(); 531170754Sdelphij GlobalCand.clear(); 532170754Sdelphij} 533170754Sdelphij 534170754Sdelphijvoid RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); } 535170754Sdelphij 536170754Sdelphijvoid RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) { 537170754Sdelphij // Prioritize live ranges by size, assigning larger ranges first. 538170754Sdelphij // The queue holds (size, reg) pairs. 539170754Sdelphij const unsigned Size = LI->getSize(); 540170754Sdelphij const unsigned Reg = LI->reg; 541170754Sdelphij assert(TargetRegisterInfo::isVirtualRegister(Reg) && 542170754Sdelphij "Can only enqueue virtual registers"); 543170754Sdelphij unsigned Prio; 544170754Sdelphij 545170754Sdelphij ExtraRegInfo.grow(Reg); 546170754Sdelphij if (ExtraRegInfo[Reg].Stage == RS_New) 547170754Sdelphij ExtraRegInfo[Reg].Stage = RS_Assign; 548170754Sdelphij 549170754Sdelphij if (ExtraRegInfo[Reg].Stage == RS_Split) { 550170754Sdelphij // Unsplit ranges that couldn't be allocated immediately are deferred until 551170754Sdelphij // everything else has been allocated. 552170754Sdelphij Prio = Size; 553170754Sdelphij } else if (ExtraRegInfo[Reg].Stage == RS_Memory) { 554170754Sdelphij // Memory operand should be considered last. 555170754Sdelphij // Change the priority such that Memory operand are assigned in 556170754Sdelphij // the reverse order that they came in. 557170754Sdelphij // TODO: Make this a member variable and probably do something about hints. 558170754Sdelphij static unsigned MemOp = 0; 559170754Sdelphij Prio = MemOp++; 560170754Sdelphij } else { 561170754Sdelphij // Giant live ranges fall back to the global assignment heuristic, which 562170754Sdelphij // prevents excessive spilling in pathological cases. 563170754Sdelphij bool ReverseLocal = TRI->reverseLocalAssignment(); 564170754Sdelphij const TargetRegisterClass &RC = *MRI->getRegClass(Reg); 565170754Sdelphij bool ForceGlobal = !ReverseLocal && 566170754Sdelphij (Size / SlotIndex::InstrDist) > (2 * RC.getNumRegs()); 567170754Sdelphij 568170754Sdelphij if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() && 569170754Sdelphij LIS->intervalIsInOneMBB(*LI)) { 570170754Sdelphij // Allocate original local ranges in linear instruction order. Since they 571170754Sdelphij // are singly defined, this produces optimal coloring in the absence of 572170754Sdelphij // global interference and other constraints. 573170754Sdelphij if (!ReverseLocal) 574170754Sdelphij Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex()); 575170754Sdelphij else { 576170754Sdelphij // Allocating bottom up may allow many short LRGs to be assigned first 577170754Sdelphij // to one of the cheap registers. This could be much faster for very 578170754Sdelphij // large blocks on targets with many physical registers. 579170754Sdelphij Prio = Indexes->getZeroIndex().getInstrDistance(LI->endIndex()); 580170754Sdelphij } 581170754Sdelphij Prio |= RC.AllocationPriority << 24; 582170754Sdelphij } else { 583170754Sdelphij // Allocate global and split ranges in long->short order. Long ranges that 584170754Sdelphij // don't fit should be spilled (or split) ASAP so they don't create 585170754Sdelphij // interference. Mark a bit to prioritize global above local ranges. 586170754Sdelphij Prio = (1u << 29) + Size; 587170754Sdelphij } 588170754Sdelphij // Mark a higher bit to prioritize global and local above RS_Split. 589170754Sdelphij Prio |= (1u << 31); 590170754Sdelphij 591170754Sdelphij // Boost ranges that have a physical register hint. 592170754Sdelphij if (VRM->hasKnownPreference(Reg)) 593170754Sdelphij Prio |= (1u << 30); 594170754Sdelphij } 595170754Sdelphij // The virtual register number is a tie breaker for same-sized ranges. 596170754Sdelphij // Give lower vreg numbers higher priority to assign them first. 597170754Sdelphij CurQueue.push(std::make_pair(Prio, ~Reg)); 598170754Sdelphij} 599170754Sdelphij 600170754SdelphijLiveInterval *RAGreedy::dequeue() { return dequeue(Queue); } 601170754Sdelphij 602170754SdelphijLiveInterval *RAGreedy::dequeue(PQueue &CurQueue) { 603170754Sdelphij if (CurQueue.empty()) 604170754Sdelphij return nullptr; 605170754Sdelphij LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second); 606170754Sdelphij CurQueue.pop(); 607170754Sdelphij return LI; 608170754Sdelphij} 609170754Sdelphij 610170754Sdelphij 611170754Sdelphij//===----------------------------------------------------------------------===// 612170754Sdelphij// Direct Assignment 613170754Sdelphij//===----------------------------------------------------------------------===// 614170754Sdelphij 615170754Sdelphij/// tryAssign - Try to assign VirtReg to an available register. 616170754Sdelphijunsigned RAGreedy::tryAssign(LiveInterval &VirtReg, 617170754Sdelphij AllocationOrder &Order, 618170754Sdelphij SmallVectorImpl<unsigned> &NewVRegs) { 619170754Sdelphij Order.rewind(); 620170754Sdelphij unsigned PhysReg; 621170754Sdelphij while ((PhysReg = Order.next())) 622170754Sdelphij if (!Matrix->checkInterference(VirtReg, PhysReg)) 623170754Sdelphij break; 624170754Sdelphij if (!PhysReg || Order.isHint()) 625170754Sdelphij return PhysReg; 626170754Sdelphij 627170754Sdelphij // PhysReg is available, but there may be a better choice. 628170754Sdelphij 629170754Sdelphij // If we missed a simple hint, try to cheaply evict interference from the 630170754Sdelphij // preferred register. 631170754Sdelphij if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg)) 632170754Sdelphij if (Order.isHint(Hint)) { 633170754Sdelphij DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n'); 634170754Sdelphij EvictionCost MaxCost; 635170754Sdelphij MaxCost.setBrokenHints(1); 636170754Sdelphij if (canEvictInterference(VirtReg, Hint, true, MaxCost)) { 637170754Sdelphij evictInterference(VirtReg, Hint, NewVRegs); 638170754Sdelphij return Hint; 639170754Sdelphij } 640170754Sdelphij } 641170754Sdelphij 642170754Sdelphij // Try to evict interference from a cheaper alternative. 643170754Sdelphij unsigned Cost = TRI->getCostPerUse(PhysReg); 644170754Sdelphij 645170754Sdelphij // Most registers have 0 additional cost. 646170754Sdelphij if (!Cost) 647170754Sdelphij return PhysReg; 648170754Sdelphij 649170754Sdelphij DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost 650170754Sdelphij << '\n'); 651170754Sdelphij unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost); 652170754Sdelphij return CheapReg ? CheapReg : PhysReg; 653170754Sdelphij} 654170754Sdelphij 655170754Sdelphij 656170754Sdelphij//===----------------------------------------------------------------------===// 657170754Sdelphij// Interference eviction 658170754Sdelphij//===----------------------------------------------------------------------===// 659170754Sdelphij 660170754Sdelphijunsigned RAGreedy::canReassign(LiveInterval &VirtReg, unsigned PrevReg) { 661170754Sdelphij AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix); 662170754Sdelphij unsigned PhysReg; 663170754Sdelphij while ((PhysReg = Order.next())) { 664170754Sdelphij if (PhysReg == PrevReg) 665170754Sdelphij continue; 666170754Sdelphij 667170754Sdelphij MCRegUnitIterator Units(PhysReg, TRI); 668170754Sdelphij for (; Units.isValid(); ++Units) { 669170754Sdelphij // Instantiate a "subquery", not to be confused with the Queries array. 670170754Sdelphij LiveIntervalUnion::Query subQ(&VirtReg, &Matrix->getLiveUnions()[*Units]); 671170754Sdelphij if (subQ.checkInterference()) 672170754Sdelphij break; 673170754Sdelphij } 674170754Sdelphij // If no units have interference, break out with the current PhysReg. 675170754Sdelphij if (!Units.isValid()) 676170754Sdelphij break; 677170754Sdelphij } 678170754Sdelphij if (PhysReg) 679170754Sdelphij DEBUG(dbgs() << "can reassign: " << VirtReg << " from " 680170754Sdelphij << PrintReg(PrevReg, TRI) << " to " << PrintReg(PhysReg, TRI) 681170754Sdelphij << '\n'); 682170754Sdelphij return PhysReg; 683170754Sdelphij} 684170754Sdelphij 685170754Sdelphij/// shouldEvict - determine if A should evict the assigned live range B. The 686170754Sdelphij/// eviction policy defined by this function together with the allocation order 687170754Sdelphij/// defined by enqueue() decides which registers ultimately end up being split 688170754Sdelphij/// and spilled. 689170754Sdelphij/// 690170754Sdelphij/// Cascade numbers are used to prevent infinite loops if this function is a 691170754Sdelphij/// cyclic relation. 692170754Sdelphij/// 693170754Sdelphij/// @param A The live range to be assigned. 694170754Sdelphij/// @param IsHint True when A is about to be assigned to its preferred 695170754Sdelphij/// register. 696170754Sdelphij/// @param B The live range to be evicted. 697170754Sdelphij/// @param BreaksHint True when B is already assigned to its preferred register. 698170754Sdelphijbool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint, 699170754Sdelphij LiveInterval &B, bool BreaksHint) { 700170754Sdelphij bool CanSplit = getStage(B) < RS_Spill; 701170754Sdelphij 702170754Sdelphij // Be fairly aggressive about following hints as long as the evictee can be 703170754Sdelphij // split. 704170754Sdelphij if (CanSplit && IsHint && !BreaksHint) 705170754Sdelphij return true; 706170754Sdelphij 707170754Sdelphij if (A.weight > B.weight) { 708170754Sdelphij DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight << '\n'); 709170754Sdelphij return true; 710170754Sdelphij } 711170754Sdelphij return false; 712170754Sdelphij} 713170754Sdelphij 714170754Sdelphij/// canEvictInterference - Return true if all interferences between VirtReg and 715170754Sdelphij/// PhysReg can be evicted. 716170754Sdelphij/// 717170754Sdelphij/// @param VirtReg Live range that is about to be assigned. 718170754Sdelphij/// @param PhysReg Desired register for assignment. 719170754Sdelphij/// @param IsHint True when PhysReg is VirtReg's preferred register. 720170754Sdelphij/// @param MaxCost Only look for cheaper candidates and update with new cost 721170754Sdelphij/// when returning true. 722170754Sdelphij/// @returns True when interference can be evicted cheaper than MaxCost. 723170754Sdelphijbool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, 724170754Sdelphij bool IsHint, EvictionCost &MaxCost) { 725170754Sdelphij // It is only possible to evict virtual register interference. 726170754Sdelphij if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) 727170754Sdelphij return false; 728170754Sdelphij 729170754Sdelphij bool IsLocal = LIS->intervalIsInOneMBB(VirtReg); 730170754Sdelphij 731170754Sdelphij // Find VirtReg's cascade number. This will be unassigned if VirtReg was never 732170754Sdelphij // involved in an eviction before. If a cascade number was assigned, deny 733170754Sdelphij // evicting anything with the same or a newer cascade number. This prevents 734170754Sdelphij // infinite eviction loops. 735170754Sdelphij // 736170754Sdelphij // This works out so a register without a cascade number is allowed to evict 737170754Sdelphij // anything, and it can be evicted by anything. 738170754Sdelphij unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 739170754Sdelphij if (!Cascade) 740170754Sdelphij Cascade = NextCascade; 741170754Sdelphij 742170754Sdelphij EvictionCost Cost; 743170754Sdelphij for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 744170754Sdelphij LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 745170754Sdelphij // If there is 10 or more interferences, chances are one is heavier. 746170754Sdelphij if (Q.collectInterferingVRegs(10) >= 10) 747170754Sdelphij return false; 748170754Sdelphij 749170754Sdelphij // Check if any interfering live range is heavier than MaxWeight. 750170754Sdelphij for (unsigned i = Q.interferingVRegs().size(); i; --i) { 751170754Sdelphij LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 752170754Sdelphij assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) && 753170754Sdelphij "Only expecting virtual register interference from query"); 754170754Sdelphij // Never evict spill products. They cannot split or spill. 755170754Sdelphij if (getStage(*Intf) == RS_Done) 756170754Sdelphij return false; 757170754Sdelphij // Once a live range becomes small enough, it is urgent that we find a 758170754Sdelphij // register for it. This is indicated by an infinite spill weight. These 759170754Sdelphij // urgent live ranges get to evict almost anything. 760170754Sdelphij // 761170754Sdelphij // Also allow urgent evictions of unspillable ranges from a strictly 762170754Sdelphij // larger allocation order. 763170754Sdelphij bool Urgent = !VirtReg.isSpillable() && 764170754Sdelphij (Intf->isSpillable() || 765170754Sdelphij RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) < 766170754Sdelphij RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg))); 767170754Sdelphij // Only evict older cascades or live ranges without a cascade. 768170754Sdelphij unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade; 769170754Sdelphij if (Cascade <= IntfCascade) { 770170754Sdelphij if (!Urgent) 771170754Sdelphij return false; 772170754Sdelphij // We permit breaking cascades for urgent evictions. It should be the 773170754Sdelphij // last resort, though, so make it really expensive. 774170754Sdelphij Cost.BrokenHints += 10; 775170754Sdelphij } 776170754Sdelphij // Would this break a satisfied hint? 777170754Sdelphij bool BreaksHint = VRM->hasPreferredPhys(Intf->reg); 778170754Sdelphij // Update eviction cost. 779170754Sdelphij Cost.BrokenHints += BreaksHint; 780170754Sdelphij Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight); 781170754Sdelphij // Abort if this would be too expensive. 782170754Sdelphij if (!(Cost < MaxCost)) 783170754Sdelphij return false; 784170754Sdelphij if (Urgent) 785170754Sdelphij continue; 786170754Sdelphij // Apply the eviction policy for non-urgent evictions. 787170754Sdelphij if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint)) 788170754Sdelphij return false; 789170754Sdelphij // If !MaxCost.isMax(), then we're just looking for a cheap register. 790170754Sdelphij // Evicting another local live range in this case could lead to suboptimal 791170754Sdelphij // coloring. 792170754Sdelphij if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) && 793170754Sdelphij (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) { 794170754Sdelphij return false; 795170754Sdelphij } 796170754Sdelphij } 797170754Sdelphij } 798170754Sdelphij MaxCost = Cost; 799170754Sdelphij return true; 800170754Sdelphij} 801170754Sdelphij 802170754Sdelphij/// evictInterference - Evict any interferring registers that prevent VirtReg 803170754Sdelphij/// from being assigned to Physreg. This assumes that canEvictInterference 804170754Sdelphij/// returned true. 805170754Sdelphijvoid RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg, 806170754Sdelphij SmallVectorImpl<unsigned> &NewVRegs) { 807170754Sdelphij // Make sure that VirtReg has a cascade number, and assign that cascade 808170754Sdelphij // number to every evicted register. These live ranges than then only be 809170754Sdelphij // evicted by a newer cascade, preventing infinite loops. 810170754Sdelphij unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade; 811170754Sdelphij if (!Cascade) 812170754Sdelphij Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++; 813170754Sdelphij 814170754Sdelphij DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI) 815170754Sdelphij << " interference: Cascade " << Cascade << '\n'); 816170754Sdelphij 817170754Sdelphij // Collect all interfering virtregs first. 818170754Sdelphij SmallVector<LiveInterval*, 8> Intfs; 819170754Sdelphij for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 820170754Sdelphij LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 821170754Sdelphij assert(Q.seenAllInterferences() && "Didn't check all interfererences."); 822170754Sdelphij ArrayRef<LiveInterval*> IVR = Q.interferingVRegs(); 823170754Sdelphij Intfs.append(IVR.begin(), IVR.end()); 824170754Sdelphij } 825170754Sdelphij 826170754Sdelphij // Evict them second. This will invalidate the queries. 827170754Sdelphij for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { 828170754Sdelphij LiveInterval *Intf = Intfs[i]; 829170754Sdelphij // The same VirtReg may be present in multiple RegUnits. Skip duplicates. 830170754Sdelphij if (!VRM->hasPhys(Intf->reg)) 831170754Sdelphij continue; 832170754Sdelphij Matrix->unassign(*Intf); 833170754Sdelphij assert((ExtraRegInfo[Intf->reg].Cascade < Cascade || 834170754Sdelphij VirtReg.isSpillable() < Intf->isSpillable()) && 835170754Sdelphij "Cannot decrease cascade number, illegal eviction"); 836170754Sdelphij ExtraRegInfo[Intf->reg].Cascade = Cascade; 837170754Sdelphij ++NumEvicted; 838170754Sdelphij NewVRegs.push_back(Intf->reg); 839170754Sdelphij } 840170754Sdelphij} 841170754Sdelphij 842170754Sdelphij/// Returns true if the given \p PhysReg is a callee saved register and has not 843170754Sdelphij/// been used for allocation yet. 844170754Sdelphijbool RAGreedy::isUnusedCalleeSavedReg(unsigned PhysReg) const { 845170754Sdelphij unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg); 846170754Sdelphij if (CSR == 0) 847170754Sdelphij return false; 848170754Sdelphij 849170754Sdelphij return !Matrix->isPhysRegUsed(PhysReg); 850170754Sdelphij} 851170754Sdelphij 852170754Sdelphij/// tryEvict - Try to evict all interferences for a physreg. 853170754Sdelphij/// @param VirtReg Currently unassigned virtual register. 854170754Sdelphij/// @param Order Physregs to try. 855170754Sdelphij/// @return Physreg to assign VirtReg, or 0. 856170754Sdelphijunsigned RAGreedy::tryEvict(LiveInterval &VirtReg, 857170754Sdelphij AllocationOrder &Order, 858170754Sdelphij SmallVectorImpl<unsigned> &NewVRegs, 859170754Sdelphij unsigned CostPerUseLimit) { 860170754Sdelphij NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled); 861170754Sdelphij 862170754Sdelphij // Keep track of the cheapest interference seen so far. 863170754Sdelphij EvictionCost BestCost; 864170754Sdelphij BestCost.setMax(); 865170754Sdelphij unsigned BestPhys = 0; 866170754Sdelphij unsigned OrderLimit = Order.getOrder().size(); 867170754Sdelphij 868170754Sdelphij // When we are just looking for a reduced cost per use, don't break any 869170754Sdelphij // hints, and only evict smaller spill weights. 870170754Sdelphij if (CostPerUseLimit < ~0u) { 871170754Sdelphij BestCost.BrokenHints = 0; 872170754Sdelphij BestCost.MaxWeight = VirtReg.weight; 873170754Sdelphij 874170754Sdelphij // Check of any registers in RC are below CostPerUseLimit. 875170754Sdelphij const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg); 876170754Sdelphij unsigned MinCost = RegClassInfo.getMinCost(RC); 877170754Sdelphij if (MinCost >= CostPerUseLimit) { 878170754Sdelphij DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = " << MinCost 879170754Sdelphij << ", no cheaper registers to be found.\n"); 880170754Sdelphij return 0; 881170754Sdelphij } 882170754Sdelphij 883170754Sdelphij // It is normal for register classes to have a long tail of registers with 884170754Sdelphij // the same cost. We don't need to look at them if they're too expensive. 885170754Sdelphij if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) { 886170754Sdelphij OrderLimit = RegClassInfo.getLastCostChange(RC); 887170754Sdelphij DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n"); 888170754Sdelphij } 889170754Sdelphij } 890170754Sdelphij 891170754Sdelphij Order.rewind(); 892170754Sdelphij while (unsigned PhysReg = Order.next(OrderLimit)) { 893170754Sdelphij if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit) 894170754Sdelphij continue; 895170754Sdelphij // The first use of a callee-saved register in a function has cost 1. 896170754Sdelphij // Don't start using a CSR when the CostPerUseLimit is low. 897170754Sdelphij if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) { 898170754Sdelphij DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR " 899170754Sdelphij << PrintReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI) 900170754Sdelphij << '\n'); 901170754Sdelphij continue; 902170754Sdelphij } 903170754Sdelphij 904170754Sdelphij if (!canEvictInterference(VirtReg, PhysReg, false, BestCost)) 905170754Sdelphij continue; 906170754Sdelphij 907170754Sdelphij // Best so far. 908170754Sdelphij BestPhys = PhysReg; 909170754Sdelphij 910170754Sdelphij // Stop if the hint can be used. 911170754Sdelphij if (Order.isHint()) 912170754Sdelphij break; 913170754Sdelphij } 914170754Sdelphij 915170754Sdelphij if (!BestPhys) 916170754Sdelphij return 0; 917170754Sdelphij 918170754Sdelphij evictInterference(VirtReg, BestPhys, NewVRegs); 919170754Sdelphij return BestPhys; 920170754Sdelphij} 921170754Sdelphij 922170754Sdelphij 923170754Sdelphij//===----------------------------------------------------------------------===// 924170754Sdelphij// Region Splitting 925170754Sdelphij//===----------------------------------------------------------------------===// 926170754Sdelphij 927170754Sdelphij/// addSplitConstraints - Fill out the SplitConstraints vector based on the 928170754Sdelphij/// interference pattern in Physreg and its aliases. Add the constraints to 929170754Sdelphij/// SpillPlacement and return the static cost of this split in Cost, assuming 930170754Sdelphij/// that all preferences in SplitConstraints are met. 931170754Sdelphij/// Return false if there are no bundles with positive bias. 932170754Sdelphijbool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, 933170754Sdelphij BlockFrequency &Cost) { 934170754Sdelphij ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 935170754Sdelphij 936170754Sdelphij // Reset interference dependent info. 937170754Sdelphij SplitConstraints.resize(UseBlocks.size()); 938170754Sdelphij BlockFrequency StaticCost = 0; 939170754Sdelphij for (unsigned i = 0; i != UseBlocks.size(); ++i) { 940170754Sdelphij const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 941170754Sdelphij SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 942170754Sdelphij 943170754Sdelphij BC.Number = BI.MBB->getNumber(); 944170754Sdelphij Intf.moveToBlock(BC.Number); 945170754Sdelphij BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 946170754Sdelphij BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare; 947170754Sdelphij BC.ChangesValue = BI.FirstDef.isValid(); 948170754Sdelphij 949170754Sdelphij if (!Intf.hasInterference()) 950170754Sdelphij continue; 951170754Sdelphij 952170754Sdelphij // Number of spill code instructions to insert. 953170754Sdelphij unsigned Ins = 0; 954170754Sdelphij 955170754Sdelphij // Interference for the live-in value. 956170754Sdelphij if (BI.LiveIn) { 957170754Sdelphij if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) 958170754Sdelphij BC.Entry = SpillPlacement::MustSpill, ++Ins; 959170754Sdelphij else if (Intf.first() < BI.FirstInstr) 960170754Sdelphij BC.Entry = SpillPlacement::PrefSpill, ++Ins; 961170754Sdelphij else if (Intf.first() < BI.LastInstr) 962170754Sdelphij ++Ins; 963170754Sdelphij } 964170754Sdelphij 965170754Sdelphij // Interference for the live-out value. 966170754Sdelphij if (BI.LiveOut) { 967170754Sdelphij if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) 968170754Sdelphij BC.Exit = SpillPlacement::MustSpill, ++Ins; 969170754Sdelphij else if (Intf.last() > BI.LastInstr) 970170754Sdelphij BC.Exit = SpillPlacement::PrefSpill, ++Ins; 971170754Sdelphij else if (Intf.last() > BI.FirstInstr) 972170754Sdelphij ++Ins; 973170754Sdelphij } 974170754Sdelphij 975170754Sdelphij // Accumulate the total frequency of inserted spill code. 976170754Sdelphij while (Ins--) 977170754Sdelphij StaticCost += SpillPlacer->getBlockFrequency(BC.Number); 978170754Sdelphij } 979170754Sdelphij Cost = StaticCost; 980170754Sdelphij 981170754Sdelphij // Add constraints for use-blocks. Note that these are the only constraints 982170754Sdelphij // that may add a positive bias, it is downhill from here. 983170754Sdelphij SpillPlacer->addConstraints(SplitConstraints); 984170754Sdelphij return SpillPlacer->scanActiveBundles(); 985170754Sdelphij} 986170754Sdelphij 987170754Sdelphij 988170754Sdelphij/// addThroughConstraints - Add constraints and links to SpillPlacer from the 989170754Sdelphij/// live-through blocks in Blocks. 990170754Sdelphijvoid RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, 991170754Sdelphij ArrayRef<unsigned> Blocks) { 992170754Sdelphij const unsigned GroupSize = 8; 993170754Sdelphij SpillPlacement::BlockConstraint BCS[GroupSize]; 994170754Sdelphij unsigned TBS[GroupSize]; 995170754Sdelphij unsigned B = 0, T = 0; 996170754Sdelphij 997170754Sdelphij for (unsigned i = 0; i != Blocks.size(); ++i) { 998170754Sdelphij unsigned Number = Blocks[i]; 999170754Sdelphij Intf.moveToBlock(Number); 1000170754Sdelphij 1001170754Sdelphij if (!Intf.hasInterference()) { 1002170754Sdelphij assert(T < GroupSize && "Array overflow"); 1003170754Sdelphij TBS[T] = Number; 1004170754Sdelphij if (++T == GroupSize) { 1005170754Sdelphij SpillPlacer->addLinks(makeArrayRef(TBS, T)); 1006170754Sdelphij T = 0; 1007170754Sdelphij } 1008170754Sdelphij continue; 1009170754Sdelphij } 1010170754Sdelphij 1011170754Sdelphij assert(B < GroupSize && "Array overflow"); 1012170754Sdelphij BCS[B].Number = Number; 1013170754Sdelphij 1014170754Sdelphij // Interference for the live-in value. 1015170754Sdelphij if (Intf.first() <= Indexes->getMBBStartIdx(Number)) 1016170754Sdelphij BCS[B].Entry = SpillPlacement::MustSpill; 1017170754Sdelphij else 1018170754Sdelphij BCS[B].Entry = SpillPlacement::PrefSpill; 1019170754Sdelphij 1020170754Sdelphij // Interference for the live-out value. 1021170754Sdelphij if (Intf.last() >= SA->getLastSplitPoint(Number)) 1022170754Sdelphij BCS[B].Exit = SpillPlacement::MustSpill; 1023170754Sdelphij else 1024170754Sdelphij BCS[B].Exit = SpillPlacement::PrefSpill; 1025170754Sdelphij 1026170754Sdelphij if (++B == GroupSize) { 1027170754Sdelphij SpillPlacer->addConstraints(makeArrayRef(BCS, B)); 1028170754Sdelphij B = 0; 1029170754Sdelphij } 1030170754Sdelphij } 1031170754Sdelphij 1032170754Sdelphij SpillPlacer->addConstraints(makeArrayRef(BCS, B)); 1033170754Sdelphij SpillPlacer->addLinks(makeArrayRef(TBS, T)); 1034170754Sdelphij} 1035170754Sdelphij 1036170754Sdelphijvoid RAGreedy::growRegion(GlobalSplitCandidate &Cand) { 1037170754Sdelphij // Keep track of through blocks that have not been added to SpillPlacer. 1038170754Sdelphij BitVector Todo = SA->getThroughBlocks(); 1039170754Sdelphij SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks; 1040170754Sdelphij unsigned AddedTo = 0; 1041170754Sdelphij#ifndef NDEBUG 1042170754Sdelphij unsigned Visited = 0; 1043170754Sdelphij#endif 1044170754Sdelphij 1045170754Sdelphij for (;;) { 1046170754Sdelphij ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); 1047170754Sdelphij // Find new through blocks in the periphery of PrefRegBundles. 1048170754Sdelphij for (int i = 0, e = NewBundles.size(); i != e; ++i) { 1049170754Sdelphij unsigned Bundle = NewBundles[i]; 1050170754Sdelphij // Look at all blocks connected to Bundle in the full graph. 1051170754Sdelphij ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); 1052170754Sdelphij for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 1053170754Sdelphij I != E; ++I) { 1054170754Sdelphij unsigned Block = *I; 1055170754Sdelphij if (!Todo.test(Block)) 1056170754Sdelphij continue; 1057170754Sdelphij Todo.reset(Block); 1058170754Sdelphij // This is a new through block. Add it to SpillPlacer later. 1059170754Sdelphij ActiveBlocks.push_back(Block); 1060170754Sdelphij#ifndef NDEBUG 1061170754Sdelphij ++Visited; 1062170754Sdelphij#endif 1063170754Sdelphij } 1064170754Sdelphij } 1065170754Sdelphij // Any new blocks to add? 1066170754Sdelphij if (ActiveBlocks.size() == AddedTo) 1067170754Sdelphij break; 1068170754Sdelphij 1069170754Sdelphij // Compute through constraints from the interference, or assume that all 1070170754Sdelphij // through blocks prefer spilling when forming compact regions. 1071170754Sdelphij auto NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo); 1072170754Sdelphij if (Cand.PhysReg) 1073170754Sdelphij addThroughConstraints(Cand.Intf, NewBlocks); 1074170754Sdelphij else 1075170754Sdelphij // Provide a strong negative bias on through blocks to prevent unwanted 1076170754Sdelphij // liveness on loop backedges. 1077170754Sdelphij SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); 1078170754Sdelphij AddedTo = ActiveBlocks.size(); 1079170754Sdelphij 1080170754Sdelphij // Perhaps iterating can enable more bundles? 1081170754Sdelphij SpillPlacer->iterate(); 1082170754Sdelphij } 1083170754Sdelphij DEBUG(dbgs() << ", v=" << Visited); 1084170754Sdelphij} 1085170754Sdelphij 1086170754Sdelphij/// calcCompactRegion - Compute the set of edge bundles that should be live 1087170754Sdelphij/// when splitting the current live range into compact regions. Compact 1088170754Sdelphij/// regions can be computed without looking at interference. They are the 1089170754Sdelphij/// regions formed by removing all the live-through blocks from the live range. 1090170754Sdelphij/// 1091170754Sdelphij/// Returns false if the current live range is already compact, or if the 1092170754Sdelphij/// compact regions would form single block regions anyway. 1093170754Sdelphijbool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { 1094170754Sdelphij // Without any through blocks, the live range is already compact. 1095170754Sdelphij if (!SA->getNumThroughBlocks()) 1096170754Sdelphij return false; 1097170754Sdelphij 1098170754Sdelphij // Compact regions don't correspond to any physreg. 1099170754Sdelphij Cand.reset(IntfCache, 0); 1100170754Sdelphij 1101170754Sdelphij DEBUG(dbgs() << "Compact region bundles"); 1102170754Sdelphij 1103170754Sdelphij // Use the spill placer to determine the live bundles. GrowRegion pretends 1104170754Sdelphij // that all the through blocks have interference when PhysReg is unset. 1105170754Sdelphij SpillPlacer->prepare(Cand.LiveBundles); 1106170754Sdelphij 1107170754Sdelphij // The static split cost will be zero since Cand.Intf reports no interference. 1108170754Sdelphij BlockFrequency Cost; 1109170754Sdelphij if (!addSplitConstraints(Cand.Intf, Cost)) { 1110170754Sdelphij DEBUG(dbgs() << ", none.\n"); 1111170754Sdelphij return false; 1112170754Sdelphij } 1113170754Sdelphij 1114170754Sdelphij growRegion(Cand); 1115170754Sdelphij SpillPlacer->finish(); 1116170754Sdelphij 1117170754Sdelphij if (!Cand.LiveBundles.any()) { 1118170754Sdelphij DEBUG(dbgs() << ", none.\n"); 1119170754Sdelphij return false; 1120170754Sdelphij } 1121170754Sdelphij 1122170754Sdelphij DEBUG({ 1123170754Sdelphij for (int i = Cand.LiveBundles.find_first(); i>=0; 1124170754Sdelphij i = Cand.LiveBundles.find_next(i)) 1125170754Sdelphij dbgs() << " EB#" << i; 1126170754Sdelphij dbgs() << ".\n"; 1127170754Sdelphij }); 1128170754Sdelphij return true; 1129170754Sdelphij} 1130170754Sdelphij 1131170754Sdelphij/// calcSpillCost - Compute how expensive it would be to split the live range in 1132170754Sdelphij/// SA around all use blocks instead of forming bundle regions. 1133170754SdelphijBlockFrequency RAGreedy::calcSpillCost() { 1134170754Sdelphij BlockFrequency Cost = 0; 1135170754Sdelphij ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1136170754Sdelphij for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1137170754Sdelphij const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1138170754Sdelphij unsigned Number = BI.MBB->getNumber(); 1139170754Sdelphij // We normally only need one spill instruction - a load or a store. 1140170754Sdelphij Cost += SpillPlacer->getBlockFrequency(Number); 1141170754Sdelphij 1142170754Sdelphij // Unless the value is redefined in the block. 1143170754Sdelphij if (BI.LiveIn && BI.LiveOut && BI.FirstDef) 1144170754Sdelphij Cost += SpillPlacer->getBlockFrequency(Number); 1145170754Sdelphij } 1146170754Sdelphij return Cost; 1147170754Sdelphij} 1148170754Sdelphij 1149170754Sdelphij/// calcGlobalSplitCost - Return the global split cost of following the split 1150170754Sdelphij/// pattern in LiveBundles. This cost should be added to the local cost of the 1151170754Sdelphij/// interference pattern in SplitConstraints. 1152170754Sdelphij/// 1153170754SdelphijBlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) { 1154170754Sdelphij BlockFrequency GlobalCost = 0; 1155170754Sdelphij const BitVector &LiveBundles = Cand.LiveBundles; 1156170754Sdelphij ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1157170754Sdelphij for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1158170754Sdelphij const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1159170754Sdelphij SpillPlacement::BlockConstraint &BC = SplitConstraints[i]; 1160170754Sdelphij bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)]; 1161170754Sdelphij bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)]; 1162170754Sdelphij unsigned Ins = 0; 1163170754Sdelphij 1164170754Sdelphij if (BI.LiveIn) 1165170754Sdelphij Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg); 1166170754Sdelphij if (BI.LiveOut) 1167170754Sdelphij Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg); 1168170754Sdelphij while (Ins--) 1169170754Sdelphij GlobalCost += SpillPlacer->getBlockFrequency(BC.Number); 1170170754Sdelphij } 1171170754Sdelphij 1172170754Sdelphij for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) { 1173170754Sdelphij unsigned Number = Cand.ActiveBlocks[i]; 1174170754Sdelphij bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)]; 1175170754Sdelphij bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)]; 1176170754Sdelphij if (!RegIn && !RegOut) 1177170754Sdelphij continue; 1178170754Sdelphij if (RegIn && RegOut) { 1179170754Sdelphij // We need double spill code if this block has interference. 1180170754Sdelphij Cand.Intf.moveToBlock(Number); 1181170754Sdelphij if (Cand.Intf.hasInterference()) { 1182170754Sdelphij GlobalCost += SpillPlacer->getBlockFrequency(Number); 1183170754Sdelphij GlobalCost += SpillPlacer->getBlockFrequency(Number); 1184170754Sdelphij } 1185170754Sdelphij continue; 1186170754Sdelphij } 1187170754Sdelphij // live-in / stack-out or stack-in live-out. 1188170754Sdelphij GlobalCost += SpillPlacer->getBlockFrequency(Number); 1189170754Sdelphij } 1190170754Sdelphij return GlobalCost; 1191170754Sdelphij} 1192170754Sdelphij 1193170754Sdelphij/// splitAroundRegion - Split the current live range around the regions 1194170754Sdelphij/// determined by BundleCand and GlobalCand. 1195170754Sdelphij/// 1196170754Sdelphij/// Before calling this function, GlobalCand and BundleCand must be initialized 1197170754Sdelphij/// so each bundle is assigned to a valid candidate, or NoCand for the 1198170754Sdelphij/// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor 1199170754Sdelphij/// objects must be initialized for the current live range, and intervals 1200170754Sdelphij/// created for the used candidates. 1201170754Sdelphij/// 1202170754Sdelphij/// @param LREdit The LiveRangeEdit object handling the current split. 1203170754Sdelphij/// @param UsedCands List of used GlobalCand entries. Every BundleCand value 1204170754Sdelphij/// must appear in this list. 1205170754Sdelphijvoid RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, 1206170754Sdelphij ArrayRef<unsigned> UsedCands) { 1207170754Sdelphij // These are the intervals created for new global ranges. We may create more 1208170754Sdelphij // intervals for local ranges. 1209170754Sdelphij const unsigned NumGlobalIntvs = LREdit.size(); 1210170754Sdelphij DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n"); 1211170754Sdelphij assert(NumGlobalIntvs && "No global intervals configured"); 1212170754Sdelphij 1213170754Sdelphij // Isolate even single instructions when dealing with a proper sub-class. 1214170754Sdelphij // That guarantees register class inflation for the stack interval because it 1215170754Sdelphij // is all copies. 1216170754Sdelphij unsigned Reg = SA->getParent().reg; 1217170754Sdelphij bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 1218170754Sdelphij 1219170754Sdelphij // First handle all the blocks with uses. 1220170754Sdelphij ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1221170754Sdelphij for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1222170754Sdelphij const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1223170754Sdelphij unsigned Number = BI.MBB->getNumber(); 1224170754Sdelphij unsigned IntvIn = 0, IntvOut = 0; 1225170754Sdelphij SlotIndex IntfIn, IntfOut; 1226 if (BI.LiveIn) { 1227 unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 1228 if (CandIn != NoCand) { 1229 GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 1230 IntvIn = Cand.IntvIdx; 1231 Cand.Intf.moveToBlock(Number); 1232 IntfIn = Cand.Intf.first(); 1233 } 1234 } 1235 if (BI.LiveOut) { 1236 unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 1237 if (CandOut != NoCand) { 1238 GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 1239 IntvOut = Cand.IntvIdx; 1240 Cand.Intf.moveToBlock(Number); 1241 IntfOut = Cand.Intf.last(); 1242 } 1243 } 1244 1245 // Create separate intervals for isolated blocks with multiple uses. 1246 if (!IntvIn && !IntvOut) { 1247 DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n"); 1248 if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1249 SE->splitSingleBlock(BI); 1250 continue; 1251 } 1252 1253 if (IntvIn && IntvOut) 1254 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 1255 else if (IntvIn) 1256 SE->splitRegInBlock(BI, IntvIn, IntfIn); 1257 else 1258 SE->splitRegOutBlock(BI, IntvOut, IntfOut); 1259 } 1260 1261 // Handle live-through blocks. The relevant live-through blocks are stored in 1262 // the ActiveBlocks list with each candidate. We need to filter out 1263 // duplicates. 1264 BitVector Todo = SA->getThroughBlocks(); 1265 for (unsigned c = 0; c != UsedCands.size(); ++c) { 1266 ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks; 1267 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 1268 unsigned Number = Blocks[i]; 1269 if (!Todo.test(Number)) 1270 continue; 1271 Todo.reset(Number); 1272 1273 unsigned IntvIn = 0, IntvOut = 0; 1274 SlotIndex IntfIn, IntfOut; 1275 1276 unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)]; 1277 if (CandIn != NoCand) { 1278 GlobalSplitCandidate &Cand = GlobalCand[CandIn]; 1279 IntvIn = Cand.IntvIdx; 1280 Cand.Intf.moveToBlock(Number); 1281 IntfIn = Cand.Intf.first(); 1282 } 1283 1284 unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)]; 1285 if (CandOut != NoCand) { 1286 GlobalSplitCandidate &Cand = GlobalCand[CandOut]; 1287 IntvOut = Cand.IntvIdx; 1288 Cand.Intf.moveToBlock(Number); 1289 IntfOut = Cand.Intf.last(); 1290 } 1291 if (!IntvIn && !IntvOut) 1292 continue; 1293 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); 1294 } 1295 } 1296 1297 ++NumGlobalSplits; 1298 1299 SmallVector<unsigned, 8> IntvMap; 1300 SE->finish(&IntvMap); 1301 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); 1302 1303 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1304 unsigned OrigBlocks = SA->getNumLiveBlocks(); 1305 1306 // Sort out the new intervals created by splitting. We get four kinds: 1307 // - Remainder intervals should not be split again. 1308 // - Candidate intervals can be assigned to Cand.PhysReg. 1309 // - Block-local splits are candidates for local splitting. 1310 // - DCE leftovers should go back on the queue. 1311 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1312 LiveInterval &Reg = LIS->getInterval(LREdit.get(i)); 1313 1314 // Ignore old intervals from DCE. 1315 if (getStage(Reg) != RS_New) 1316 continue; 1317 1318 // Remainder interval. Don't try splitting again, spill if it doesn't 1319 // allocate. 1320 if (IntvMap[i] == 0) { 1321 setStage(Reg, RS_Spill); 1322 continue; 1323 } 1324 1325 // Global intervals. Allow repeated splitting as long as the number of live 1326 // blocks is strictly decreasing. 1327 if (IntvMap[i] < NumGlobalIntvs) { 1328 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { 1329 DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks 1330 << " blocks as original.\n"); 1331 // Don't allow repeated splitting as a safe guard against looping. 1332 setStage(Reg, RS_Split2); 1333 } 1334 continue; 1335 } 1336 1337 // Other intervals are treated as new. This includes local intervals created 1338 // for blocks with multiple uses, and anything created by DCE. 1339 } 1340 1341 if (VerifyEnabled) 1342 MF->verify(this, "After splitting live range around region"); 1343} 1344 1345unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1346 SmallVectorImpl<unsigned> &NewVRegs) { 1347 unsigned NumCands = 0; 1348 BlockFrequency BestCost; 1349 1350 // Check if we can split this live range around a compact region. 1351 bool HasCompact = calcCompactRegion(GlobalCand.front()); 1352 if (HasCompact) { 1353 // Yes, keep GlobalCand[0] as the compact region candidate. 1354 NumCands = 1; 1355 BestCost = BlockFrequency::getMaxFrequency(); 1356 } else { 1357 // No benefit from the compact region, our fallback will be per-block 1358 // splitting. Make sure we find a solution that is cheaper than spilling. 1359 BestCost = calcSpillCost(); 1360 DEBUG(dbgs() << "Cost of isolating all blocks = "; 1361 MBFI->printBlockFreq(dbgs(), BestCost) << '\n'); 1362 } 1363 1364 unsigned BestCand = 1365 calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands, 1366 false/*IgnoreCSR*/); 1367 1368 // No solutions found, fall back to single block splitting. 1369 if (!HasCompact && BestCand == NoCand) 1370 return 0; 1371 1372 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs); 1373} 1374 1375unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg, 1376 AllocationOrder &Order, 1377 BlockFrequency &BestCost, 1378 unsigned &NumCands, 1379 bool IgnoreCSR) { 1380 unsigned BestCand = NoCand; 1381 Order.rewind(); 1382 while (unsigned PhysReg = Order.next()) { 1383 if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg)) 1384 continue; 1385 1386 // Discard bad candidates before we run out of interference cache cursors. 1387 // This will only affect register classes with a lot of registers (>32). 1388 if (NumCands == IntfCache.getMaxCursors()) { 1389 unsigned WorstCount = ~0u; 1390 unsigned Worst = 0; 1391 for (unsigned i = 0; i != NumCands; ++i) { 1392 if (i == BestCand || !GlobalCand[i].PhysReg) 1393 continue; 1394 unsigned Count = GlobalCand[i].LiveBundles.count(); 1395 if (Count < WorstCount) 1396 Worst = i, WorstCount = Count; 1397 } 1398 --NumCands; 1399 GlobalCand[Worst] = GlobalCand[NumCands]; 1400 if (BestCand == NumCands) 1401 BestCand = Worst; 1402 } 1403 1404 if (GlobalCand.size() <= NumCands) 1405 GlobalCand.resize(NumCands+1); 1406 GlobalSplitCandidate &Cand = GlobalCand[NumCands]; 1407 Cand.reset(IntfCache, PhysReg); 1408 1409 SpillPlacer->prepare(Cand.LiveBundles); 1410 BlockFrequency Cost; 1411 if (!addSplitConstraints(Cand.Intf, Cost)) { 1412 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n"); 1413 continue; 1414 } 1415 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = "; 1416 MBFI->printBlockFreq(dbgs(), Cost)); 1417 if (Cost >= BestCost) { 1418 DEBUG({ 1419 if (BestCand == NoCand) 1420 dbgs() << " worse than no bundles\n"; 1421 else 1422 dbgs() << " worse than " 1423 << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n'; 1424 }); 1425 continue; 1426 } 1427 growRegion(Cand); 1428 1429 SpillPlacer->finish(); 1430 1431 // No live bundles, defer to splitSingleBlocks(). 1432 if (!Cand.LiveBundles.any()) { 1433 DEBUG(dbgs() << " no bundles.\n"); 1434 continue; 1435 } 1436 1437 Cost += calcGlobalSplitCost(Cand); 1438 DEBUG({ 1439 dbgs() << ", total = "; MBFI->printBlockFreq(dbgs(), Cost) 1440 << " with bundles"; 1441 for (int i = Cand.LiveBundles.find_first(); i>=0; 1442 i = Cand.LiveBundles.find_next(i)) 1443 dbgs() << " EB#" << i; 1444 dbgs() << ".\n"; 1445 }); 1446 if (Cost < BestCost) { 1447 BestCand = NumCands; 1448 BestCost = Cost; 1449 } 1450 ++NumCands; 1451 } 1452 return BestCand; 1453} 1454 1455unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand, 1456 bool HasCompact, 1457 SmallVectorImpl<unsigned> &NewVRegs) { 1458 SmallVector<unsigned, 8> UsedCands; 1459 // Prepare split editor. 1460 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1461 SE->reset(LREdit, SplitSpillMode); 1462 1463 // Assign all edge bundles to the preferred candidate, or NoCand. 1464 BundleCand.assign(Bundles->getNumBundles(), NoCand); 1465 1466 // Assign bundles for the best candidate region. 1467 if (BestCand != NoCand) { 1468 GlobalSplitCandidate &Cand = GlobalCand[BestCand]; 1469 if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { 1470 UsedCands.push_back(BestCand); 1471 Cand.IntvIdx = SE->openIntv(); 1472 DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in " 1473 << B << " bundles, intv " << Cand.IntvIdx << ".\n"); 1474 (void)B; 1475 } 1476 } 1477 1478 // Assign bundles for the compact region. 1479 if (HasCompact) { 1480 GlobalSplitCandidate &Cand = GlobalCand.front(); 1481 assert(!Cand.PhysReg && "Compact region has no physreg"); 1482 if (unsigned B = Cand.getBundles(BundleCand, 0)) { 1483 UsedCands.push_back(0); 1484 Cand.IntvIdx = SE->openIntv(); 1485 DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv " 1486 << Cand.IntvIdx << ".\n"); 1487 (void)B; 1488 } 1489 } 1490 1491 splitAroundRegion(LREdit, UsedCands); 1492 return 0; 1493} 1494 1495 1496//===----------------------------------------------------------------------===// 1497// Per-Block Splitting 1498//===----------------------------------------------------------------------===// 1499 1500/// tryBlockSplit - Split a global live range around every block with uses. This 1501/// creates a lot of local live ranges, that will be split by tryLocalSplit if 1502/// they don't allocate. 1503unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1504 SmallVectorImpl<unsigned> &NewVRegs) { 1505 assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); 1506 unsigned Reg = VirtReg.reg; 1507 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); 1508 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1509 SE->reset(LREdit, SplitSpillMode); 1510 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); 1511 for (unsigned i = 0; i != UseBlocks.size(); ++i) { 1512 const SplitAnalysis::BlockInfo &BI = UseBlocks[i]; 1513 if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) 1514 SE->splitSingleBlock(BI); 1515 } 1516 // No blocks were split. 1517 if (LREdit.empty()) 1518 return 0; 1519 1520 // We did split for some blocks. 1521 SmallVector<unsigned, 8> IntvMap; 1522 SE->finish(&IntvMap); 1523 1524 // Tell LiveDebugVariables about the new ranges. 1525 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); 1526 1527 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1528 1529 // Sort out the new intervals created by splitting. The remainder interval 1530 // goes straight to spilling, the new local ranges get to stay RS_New. 1531 for (unsigned i = 0, e = LREdit.size(); i != e; ++i) { 1532 LiveInterval &LI = LIS->getInterval(LREdit.get(i)); 1533 if (getStage(LI) == RS_New && IntvMap[i] == 0) 1534 setStage(LI, RS_Spill); 1535 } 1536 1537 if (VerifyEnabled) 1538 MF->verify(this, "After splitting live range around basic blocks"); 1539 return 0; 1540} 1541 1542 1543//===----------------------------------------------------------------------===// 1544// Per-Instruction Splitting 1545//===----------------------------------------------------------------------===// 1546 1547/// Get the number of allocatable registers that match the constraints of \p Reg 1548/// on \p MI and that are also in \p SuperRC. 1549static unsigned getNumAllocatableRegsForConstraints( 1550 const MachineInstr *MI, unsigned Reg, const TargetRegisterClass *SuperRC, 1551 const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, 1552 const RegisterClassInfo &RCI) { 1553 assert(SuperRC && "Invalid register class"); 1554 1555 const TargetRegisterClass *ConstrainedRC = 1556 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI, 1557 /* ExploreBundle */ true); 1558 if (!ConstrainedRC) 1559 return 0; 1560 return RCI.getNumAllocatableRegs(ConstrainedRC); 1561} 1562 1563/// tryInstructionSplit - Split a live range around individual instructions. 1564/// This is normally not worthwhile since the spiller is doing essentially the 1565/// same thing. However, when the live range is in a constrained register 1566/// class, it may help to insert copies such that parts of the live range can 1567/// be moved to a larger register class. 1568/// 1569/// This is similar to spilling to a larger register class. 1570unsigned 1571RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1572 SmallVectorImpl<unsigned> &NewVRegs) { 1573 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg); 1574 // There is no point to this if there are no larger sub-classes. 1575 if (!RegClassInfo.isProperSubClass(CurRC)) 1576 return 0; 1577 1578 // Always enable split spill mode, since we're effectively spilling to a 1579 // register. 1580 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1581 SE->reset(LREdit, SplitEditor::SM_Size); 1582 1583 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1584 if (Uses.size() <= 1) 1585 return 0; 1586 1587 DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n"); 1588 1589 const TargetRegisterClass *SuperRC = 1590 TRI->getLargestLegalSuperClass(CurRC, *MF); 1591 unsigned SuperRCNumAllocatableRegs = RCI.getNumAllocatableRegs(SuperRC); 1592 // Split around every non-copy instruction if this split will relax 1593 // the constraints on the virtual register. 1594 // Otherwise, splitting just inserts uncoalescable copies that do not help 1595 // the allocation. 1596 for (unsigned i = 0; i != Uses.size(); ++i) { 1597 if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i])) 1598 if (MI->isFullCopy() || 1599 SuperRCNumAllocatableRegs == 1600 getNumAllocatableRegsForConstraints(MI, VirtReg.reg, SuperRC, TII, 1601 TRI, RCI)) { 1602 DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI); 1603 continue; 1604 } 1605 SE->openIntv(); 1606 SlotIndex SegStart = SE->enterIntvBefore(Uses[i]); 1607 SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]); 1608 SE->useIntv(SegStart, SegStop); 1609 } 1610 1611 if (LREdit.empty()) { 1612 DEBUG(dbgs() << "All uses were copies.\n"); 1613 return 0; 1614 } 1615 1616 SmallVector<unsigned, 8> IntvMap; 1617 SE->finish(&IntvMap); 1618 DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS); 1619 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 1620 1621 // Assign all new registers to RS_Spill. This was the last chance. 1622 setStage(LREdit.begin(), LREdit.end(), RS_Spill); 1623 return 0; 1624} 1625 1626 1627//===----------------------------------------------------------------------===// 1628// Local Splitting 1629//===----------------------------------------------------------------------===// 1630 1631 1632/// calcGapWeights - Compute the maximum spill weight that needs to be evicted 1633/// in order to use PhysReg between two entries in SA->UseSlots. 1634/// 1635/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1]. 1636/// 1637void RAGreedy::calcGapWeights(unsigned PhysReg, 1638 SmallVectorImpl<float> &GapWeight) { 1639 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1640 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1641 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1642 const unsigned NumGaps = Uses.size()-1; 1643 1644 // Start and end points for the interference check. 1645 SlotIndex StartIdx = 1646 BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr; 1647 SlotIndex StopIdx = 1648 BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr; 1649 1650 GapWeight.assign(NumGaps, 0.0f); 1651 1652 // Add interference from each overlapping register. 1653 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1654 if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units) 1655 .checkInterference()) 1656 continue; 1657 1658 // We know that VirtReg is a continuous interval from FirstInstr to 1659 // LastInstr, so we don't need InterferenceQuery. 1660 // 1661 // Interference that overlaps an instruction is counted in both gaps 1662 // surrounding the instruction. The exception is interference before 1663 // StartIdx and after StopIdx. 1664 // 1665 LiveIntervalUnion::SegmentIter IntI = 1666 Matrix->getLiveUnions()[*Units] .find(StartIdx); 1667 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) { 1668 // Skip the gaps before IntI. 1669 while (Uses[Gap+1].getBoundaryIndex() < IntI.start()) 1670 if (++Gap == NumGaps) 1671 break; 1672 if (Gap == NumGaps) 1673 break; 1674 1675 // Update the gaps covered by IntI. 1676 const float weight = IntI.value()->weight; 1677 for (; Gap != NumGaps; ++Gap) { 1678 GapWeight[Gap] = std::max(GapWeight[Gap], weight); 1679 if (Uses[Gap+1].getBaseIndex() >= IntI.stop()) 1680 break; 1681 } 1682 if (Gap == NumGaps) 1683 break; 1684 } 1685 } 1686 1687 // Add fixed interference. 1688 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 1689 const LiveRange &LR = LIS->getRegUnit(*Units); 1690 LiveRange::const_iterator I = LR.find(StartIdx); 1691 LiveRange::const_iterator E = LR.end(); 1692 1693 // Same loop as above. Mark any overlapped gaps as HUGE_VALF. 1694 for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) { 1695 while (Uses[Gap+1].getBoundaryIndex() < I->start) 1696 if (++Gap == NumGaps) 1697 break; 1698 if (Gap == NumGaps) 1699 break; 1700 1701 for (; Gap != NumGaps; ++Gap) { 1702 GapWeight[Gap] = llvm::huge_valf; 1703 if (Uses[Gap+1].getBaseIndex() >= I->end) 1704 break; 1705 } 1706 if (Gap == NumGaps) 1707 break; 1708 } 1709 } 1710} 1711 1712/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only 1713/// basic block. 1714/// 1715unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order, 1716 SmallVectorImpl<unsigned> &NewVRegs) { 1717 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); 1718 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); 1719 1720 // Note that it is possible to have an interval that is live-in or live-out 1721 // while only covering a single block - A phi-def can use undef values from 1722 // predecessors, and the block could be a single-block loop. 1723 // We don't bother doing anything clever about such a case, we simply assume 1724 // that the interval is continuous from FirstInstr to LastInstr. We should 1725 // make sure that we don't do anything illegal to such an interval, though. 1726 1727 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); 1728 if (Uses.size() <= 2) 1729 return 0; 1730 const unsigned NumGaps = Uses.size()-1; 1731 1732 DEBUG({ 1733 dbgs() << "tryLocalSplit: "; 1734 for (unsigned i = 0, e = Uses.size(); i != e; ++i) 1735 dbgs() << ' ' << Uses[i]; 1736 dbgs() << '\n'; 1737 }); 1738 1739 // If VirtReg is live across any register mask operands, compute a list of 1740 // gaps with register masks. 1741 SmallVector<unsigned, 8> RegMaskGaps; 1742 if (Matrix->checkRegMaskInterference(VirtReg)) { 1743 // Get regmask slots for the whole block. 1744 ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber()); 1745 DEBUG(dbgs() << RMS.size() << " regmasks in block:"); 1746 // Constrain to VirtReg's live range. 1747 unsigned ri = std::lower_bound(RMS.begin(), RMS.end(), 1748 Uses.front().getRegSlot()) - RMS.begin(); 1749 unsigned re = RMS.size(); 1750 for (unsigned i = 0; i != NumGaps && ri != re; ++i) { 1751 // Look for Uses[i] <= RMS <= Uses[i+1]. 1752 assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i])); 1753 if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri])) 1754 continue; 1755 // Skip a regmask on the same instruction as the last use. It doesn't 1756 // overlap the live range. 1757 if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps) 1758 break; 1759 DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]); 1760 RegMaskGaps.push_back(i); 1761 // Advance ri to the next gap. A regmask on one of the uses counts in 1762 // both gaps. 1763 while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1])) 1764 ++ri; 1765 } 1766 DEBUG(dbgs() << '\n'); 1767 } 1768 1769 // Since we allow local split results to be split again, there is a risk of 1770 // creating infinite loops. It is tempting to require that the new live 1771 // ranges have less instructions than the original. That would guarantee 1772 // convergence, but it is too strict. A live range with 3 instructions can be 1773 // split 2+3 (including the COPY), and we want to allow that. 1774 // 1775 // Instead we use these rules: 1776 // 1777 // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the 1778 // noop split, of course). 1779 // 2. Require progress be made for ranges with getStage() == RS_Split2. All 1780 // the new ranges must have fewer instructions than before the split. 1781 // 3. New ranges with the same number of instructions are marked RS_Split2, 1782 // smaller ranges are marked RS_New. 1783 // 1784 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent 1785 // excessive splitting and infinite loops. 1786 // 1787 bool ProgressRequired = getStage(VirtReg) >= RS_Split2; 1788 1789 // Best split candidate. 1790 unsigned BestBefore = NumGaps; 1791 unsigned BestAfter = 0; 1792 float BestDiff = 0; 1793 1794 const float blockFreq = 1795 SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() * 1796 (1.0f / MBFI->getEntryFreq()); 1797 SmallVector<float, 8> GapWeight; 1798 1799 Order.rewind(); 1800 while (unsigned PhysReg = Order.next()) { 1801 // Keep track of the largest spill weight that would need to be evicted in 1802 // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1]. 1803 calcGapWeights(PhysReg, GapWeight); 1804 1805 // Remove any gaps with regmask clobbers. 1806 if (Matrix->checkRegMaskInterference(VirtReg, PhysReg)) 1807 for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i) 1808 GapWeight[RegMaskGaps[i]] = llvm::huge_valf; 1809 1810 // Try to find the best sequence of gaps to close. 1811 // The new spill weight must be larger than any gap interference. 1812 1813 // We will split before Uses[SplitBefore] and after Uses[SplitAfter]. 1814 unsigned SplitBefore = 0, SplitAfter = 1; 1815 1816 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). 1817 // It is the spill weight that needs to be evicted. 1818 float MaxGap = GapWeight[0]; 1819 1820 for (;;) { 1821 // Live before/after split? 1822 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn; 1823 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut; 1824 1825 DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' ' 1826 << Uses[SplitBefore] << '-' << Uses[SplitAfter] 1827 << " i=" << MaxGap); 1828 1829 // Stop before the interval gets so big we wouldn't be making progress. 1830 if (!LiveBefore && !LiveAfter) { 1831 DEBUG(dbgs() << " all\n"); 1832 break; 1833 } 1834 // Should the interval be extended or shrunk? 1835 bool Shrink = true; 1836 1837 // How many gaps would the new range have? 1838 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; 1839 1840 // Legally, without causing looping? 1841 bool Legal = !ProgressRequired || NewGaps < NumGaps; 1842 1843 if (Legal && MaxGap < llvm::huge_valf) { 1844 // Estimate the new spill weight. Each instruction reads or writes the 1845 // register. Conservatively assume there are no read-modify-write 1846 // instructions. 1847 // 1848 // Try to guess the size of the new interval. 1849 const float EstWeight = normalizeSpillWeight( 1850 blockFreq * (NewGaps + 1), 1851 Uses[SplitBefore].distance(Uses[SplitAfter]) + 1852 (LiveBefore + LiveAfter) * SlotIndex::InstrDist, 1853 1); 1854 // Would this split be possible to allocate? 1855 // Never allocate all gaps, we wouldn't be making progress. 1856 DEBUG(dbgs() << " w=" << EstWeight); 1857 if (EstWeight * Hysteresis >= MaxGap) { 1858 Shrink = false; 1859 float Diff = EstWeight - MaxGap; 1860 if (Diff > BestDiff) { 1861 DEBUG(dbgs() << " (best)"); 1862 BestDiff = Hysteresis * Diff; 1863 BestBefore = SplitBefore; 1864 BestAfter = SplitAfter; 1865 } 1866 } 1867 } 1868 1869 // Try to shrink. 1870 if (Shrink) { 1871 if (++SplitBefore < SplitAfter) { 1872 DEBUG(dbgs() << " shrink\n"); 1873 // Recompute the max when necessary. 1874 if (GapWeight[SplitBefore - 1] >= MaxGap) { 1875 MaxGap = GapWeight[SplitBefore]; 1876 for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i) 1877 MaxGap = std::max(MaxGap, GapWeight[i]); 1878 } 1879 continue; 1880 } 1881 MaxGap = 0; 1882 } 1883 1884 // Try to extend the interval. 1885 if (SplitAfter >= NumGaps) { 1886 DEBUG(dbgs() << " end\n"); 1887 break; 1888 } 1889 1890 DEBUG(dbgs() << " extend\n"); 1891 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]); 1892 } 1893 } 1894 1895 // Didn't find any candidates? 1896 if (BestBefore == NumGaps) 1897 return 0; 1898 1899 DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] 1900 << '-' << Uses[BestAfter] << ", " << BestDiff 1901 << ", " << (BestAfter - BestBefore + 1) << " instrs\n"); 1902 1903 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 1904 SE->reset(LREdit); 1905 1906 SE->openIntv(); 1907 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); 1908 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); 1909 SE->useIntv(SegStart, SegStop); 1910 SmallVector<unsigned, 8> IntvMap; 1911 SE->finish(&IntvMap); 1912 DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS); 1913 1914 // If the new range has the same number of instructions as before, mark it as 1915 // RS_Split2 so the next split will be forced to make progress. Otherwise, 1916 // leave the new intervals as RS_New so they can compete. 1917 bool LiveBefore = BestBefore != 0 || BI.LiveIn; 1918 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut; 1919 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; 1920 if (NewGaps >= NumGaps) { 1921 DEBUG(dbgs() << "Tagging non-progress ranges: "); 1922 assert(!ProgressRequired && "Didn't make progress when it was required."); 1923 for (unsigned i = 0, e = IntvMap.size(); i != e; ++i) 1924 if (IntvMap[i] == 1) { 1925 setStage(LIS->getInterval(LREdit.get(i)), RS_Split2); 1926 DEBUG(dbgs() << PrintReg(LREdit.get(i))); 1927 } 1928 DEBUG(dbgs() << '\n'); 1929 } 1930 ++NumLocalSplits; 1931 1932 return 0; 1933} 1934 1935//===----------------------------------------------------------------------===// 1936// Live Range Splitting 1937//===----------------------------------------------------------------------===// 1938 1939/// trySplit - Try to split VirtReg or one of its interferences, making it 1940/// assignable. 1941/// @return Physreg when VirtReg may be assigned and/or new NewVRegs. 1942unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order, 1943 SmallVectorImpl<unsigned>&NewVRegs) { 1944 // Ranges must be Split2 or less. 1945 if (getStage(VirtReg) >= RS_Spill) 1946 return 0; 1947 1948 // Local intervals are handled separately. 1949 if (LIS->intervalIsInOneMBB(VirtReg)) { 1950 NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled); 1951 SA->analyze(&VirtReg); 1952 unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs); 1953 if (PhysReg || !NewVRegs.empty()) 1954 return PhysReg; 1955 return tryInstructionSplit(VirtReg, Order, NewVRegs); 1956 } 1957 1958 NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled); 1959 1960 SA->analyze(&VirtReg); 1961 1962 // FIXME: SplitAnalysis may repair broken live ranges coming from the 1963 // coalescer. That may cause the range to become allocatable which means that 1964 // tryRegionSplit won't be making progress. This check should be replaced with 1965 // an assertion when the coalescer is fixed. 1966 if (SA->didRepairRange()) { 1967 // VirtReg has changed, so all cached queries are invalid. 1968 Matrix->invalidateVirtRegs(); 1969 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) 1970 return PhysReg; 1971 } 1972 1973 // First try to split around a region spanning multiple blocks. RS_Split2 1974 // ranges already made dubious progress with region splitting, so they go 1975 // straight to single block splitting. 1976 if (getStage(VirtReg) < RS_Split2) { 1977 unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs); 1978 if (PhysReg || !NewVRegs.empty()) 1979 return PhysReg; 1980 } 1981 1982 // Then isolate blocks. 1983 return tryBlockSplit(VirtReg, Order, NewVRegs); 1984} 1985 1986//===----------------------------------------------------------------------===// 1987// Last Chance Recoloring 1988//===----------------------------------------------------------------------===// 1989 1990/// mayRecolorAllInterferences - Check if the virtual registers that 1991/// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be 1992/// recolored to free \p PhysReg. 1993/// When true is returned, \p RecoloringCandidates has been augmented with all 1994/// the live intervals that need to be recolored in order to free \p PhysReg 1995/// for \p VirtReg. 1996/// \p FixedRegisters contains all the virtual registers that cannot be 1997/// recolored. 1998bool 1999RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg, 2000 SmallLISet &RecoloringCandidates, 2001 const SmallVirtRegSet &FixedRegisters) { 2002 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg); 2003 2004 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 2005 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 2006 // If there is LastChanceRecoloringMaxInterference or more interferences, 2007 // chances are one would not be recolorable. 2008 if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >= 2009 LastChanceRecoloringMaxInterference && !ExhaustiveSearch) { 2010 DEBUG(dbgs() << "Early abort: too many interferences.\n"); 2011 CutOffInfo |= CO_Interf; 2012 return false; 2013 } 2014 for (unsigned i = Q.interferingVRegs().size(); i; --i) { 2015 LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 2016 // If Intf is done and sit on the same register class as VirtReg, 2017 // it would not be recolorable as it is in the same state as VirtReg. 2018 if ((getStage(*Intf) == RS_Done && 2019 MRI->getRegClass(Intf->reg) == CurRC) || 2020 FixedRegisters.count(Intf->reg)) { 2021 DEBUG(dbgs() << "Early abort: the inteference is not recolorable.\n"); 2022 return false; 2023 } 2024 RecoloringCandidates.insert(Intf); 2025 } 2026 } 2027 return true; 2028} 2029 2030/// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring 2031/// its interferences. 2032/// Last chance recoloring chooses a color for \p VirtReg and recolors every 2033/// virtual register that was using it. The recoloring process may recursively 2034/// use the last chance recoloring. Therefore, when a virtual register has been 2035/// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot 2036/// be last-chance-recolored again during this recoloring "session". 2037/// E.g., 2038/// Let 2039/// vA can use {R1, R2 } 2040/// vB can use { R2, R3} 2041/// vC can use {R1 } 2042/// Where vA, vB, and vC cannot be split anymore (they are reloads for 2043/// instance) and they all interfere. 2044/// 2045/// vA is assigned R1 2046/// vB is assigned R2 2047/// vC tries to evict vA but vA is already done. 2048/// Regular register allocation fails. 2049/// 2050/// Last chance recoloring kicks in: 2051/// vC does as if vA was evicted => vC uses R1. 2052/// vC is marked as fixed. 2053/// vA needs to find a color. 2054/// None are available. 2055/// vA cannot evict vC: vC is a fixed virtual register now. 2056/// vA does as if vB was evicted => vA uses R2. 2057/// vB needs to find a color. 2058/// R3 is available. 2059/// Recoloring => vC = R1, vA = R2, vB = R3 2060/// 2061/// \p Order defines the preferred allocation order for \p VirtReg. 2062/// \p NewRegs will contain any new virtual register that have been created 2063/// (split, spill) during the process and that must be assigned. 2064/// \p FixedRegisters contains all the virtual registers that cannot be 2065/// recolored. 2066/// \p Depth gives the current depth of the last chance recoloring. 2067/// \return a physical register that can be used for VirtReg or ~0u if none 2068/// exists. 2069unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg, 2070 AllocationOrder &Order, 2071 SmallVectorImpl<unsigned> &NewVRegs, 2072 SmallVirtRegSet &FixedRegisters, 2073 unsigned Depth) { 2074 DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n'); 2075 // Ranges must be Done. 2076 assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) && 2077 "Last chance recoloring should really be last chance"); 2078 // Set the max depth to LastChanceRecoloringMaxDepth. 2079 // We may want to reconsider that if we end up with a too large search space 2080 // for target with hundreds of registers. 2081 // Indeed, in that case we may want to cut the search space earlier. 2082 if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) { 2083 DEBUG(dbgs() << "Abort because max depth has been reached.\n"); 2084 CutOffInfo |= CO_Depth; 2085 return ~0u; 2086 } 2087 2088 // Set of Live intervals that will need to be recolored. 2089 SmallLISet RecoloringCandidates; 2090 // Record the original mapping virtual register to physical register in case 2091 // the recoloring fails. 2092 DenseMap<unsigned, unsigned> VirtRegToPhysReg; 2093 // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in 2094 // this recoloring "session". 2095 FixedRegisters.insert(VirtReg.reg); 2096 2097 Order.rewind(); 2098 while (unsigned PhysReg = Order.next()) { 2099 DEBUG(dbgs() << "Try to assign: " << VirtReg << " to " 2100 << PrintReg(PhysReg, TRI) << '\n'); 2101 RecoloringCandidates.clear(); 2102 VirtRegToPhysReg.clear(); 2103 2104 // It is only possible to recolor virtual register interference. 2105 if (Matrix->checkInterference(VirtReg, PhysReg) > 2106 LiveRegMatrix::IK_VirtReg) { 2107 DEBUG(dbgs() << "Some inteferences are not with virtual registers.\n"); 2108 2109 continue; 2110 } 2111 2112 // Early give up on this PhysReg if it is obvious we cannot recolor all 2113 // the interferences. 2114 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates, 2115 FixedRegisters)) { 2116 DEBUG(dbgs() << "Some inteferences cannot be recolored.\n"); 2117 continue; 2118 } 2119 2120 // RecoloringCandidates contains all the virtual registers that interfer 2121 // with VirtReg on PhysReg (or one of its aliases). 2122 // Enqueue them for recoloring and perform the actual recoloring. 2123 PQueue RecoloringQueue; 2124 for (SmallLISet::iterator It = RecoloringCandidates.begin(), 2125 EndIt = RecoloringCandidates.end(); 2126 It != EndIt; ++It) { 2127 unsigned ItVirtReg = (*It)->reg; 2128 enqueue(RecoloringQueue, *It); 2129 assert(VRM->hasPhys(ItVirtReg) && 2130 "Interferences are supposed to be with allocated vairables"); 2131 2132 // Record the current allocation. 2133 VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg); 2134 // unset the related struct. 2135 Matrix->unassign(**It); 2136 } 2137 2138 // Do as if VirtReg was assigned to PhysReg so that the underlying 2139 // recoloring has the right information about the interferes and 2140 // available colors. 2141 Matrix->assign(VirtReg, PhysReg); 2142 2143 // Save the current recoloring state. 2144 // If we cannot recolor all the interferences, we will have to start again 2145 // at this point for the next physical register. 2146 SmallVirtRegSet SaveFixedRegisters(FixedRegisters); 2147 if (tryRecoloringCandidates(RecoloringQueue, NewVRegs, FixedRegisters, 2148 Depth)) { 2149 // Do not mess up with the global assignment process. 2150 // I.e., VirtReg must be unassigned. 2151 Matrix->unassign(VirtReg); 2152 return PhysReg; 2153 } 2154 2155 DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to " 2156 << PrintReg(PhysReg, TRI) << '\n'); 2157 2158 // The recoloring attempt failed, undo the changes. 2159 FixedRegisters = SaveFixedRegisters; 2160 Matrix->unassign(VirtReg); 2161 2162 for (SmallLISet::iterator It = RecoloringCandidates.begin(), 2163 EndIt = RecoloringCandidates.end(); 2164 It != EndIt; ++It) { 2165 unsigned ItVirtReg = (*It)->reg; 2166 if (VRM->hasPhys(ItVirtReg)) 2167 Matrix->unassign(**It); 2168 unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg]; 2169 Matrix->assign(**It, ItPhysReg); 2170 } 2171 } 2172 2173 // Last chance recoloring did not worked either, give up. 2174 return ~0u; 2175} 2176 2177/// tryRecoloringCandidates - Try to assign a new color to every register 2178/// in \RecoloringQueue. 2179/// \p NewRegs will contain any new virtual register created during the 2180/// recoloring process. 2181/// \p FixedRegisters[in/out] contains all the registers that have been 2182/// recolored. 2183/// \return true if all virtual registers in RecoloringQueue were successfully 2184/// recolored, false otherwise. 2185bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue, 2186 SmallVectorImpl<unsigned> &NewVRegs, 2187 SmallVirtRegSet &FixedRegisters, 2188 unsigned Depth) { 2189 while (!RecoloringQueue.empty()) { 2190 LiveInterval *LI = dequeue(RecoloringQueue); 2191 DEBUG(dbgs() << "Try to recolor: " << *LI << '\n'); 2192 unsigned PhysReg; 2193 PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1); 2194 if (PhysReg == ~0u || !PhysReg) 2195 return false; 2196 DEBUG(dbgs() << "Recoloring of " << *LI 2197 << " succeeded with: " << PrintReg(PhysReg, TRI) << '\n'); 2198 Matrix->assign(*LI, PhysReg); 2199 FixedRegisters.insert(LI->reg); 2200 } 2201 return true; 2202} 2203 2204//===----------------------------------------------------------------------===// 2205// Main Entry Point 2206//===----------------------------------------------------------------------===// 2207 2208unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, 2209 SmallVectorImpl<unsigned> &NewVRegs) { 2210 CutOffInfo = CO_None; 2211 LLVMContext &Ctx = MF->getFunction()->getContext(); 2212 SmallVirtRegSet FixedRegisters; 2213 unsigned Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters); 2214 if (Reg == ~0U && (CutOffInfo != CO_None)) { 2215 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf); 2216 if (CutOffEncountered == CO_Depth) 2217 Ctx.emitError("register allocation failed: maximum depth for recoloring " 2218 "reached. Use -fexhaustive-register-search to skip " 2219 "cutoffs"); 2220 else if (CutOffEncountered == CO_Interf) 2221 Ctx.emitError("register allocation failed: maximum interference for " 2222 "recoloring reached. Use -fexhaustive-register-search " 2223 "to skip cutoffs"); 2224 else if (CutOffEncountered == (CO_Depth | CO_Interf)) 2225 Ctx.emitError("register allocation failed: maximum interference and " 2226 "depth for recoloring reached. Use " 2227 "-fexhaustive-register-search to skip cutoffs"); 2228 } 2229 return Reg; 2230} 2231 2232/// Using a CSR for the first time has a cost because it causes push|pop 2233/// to be added to prologue|epilogue. Splitting a cold section of the live 2234/// range can have lower cost than using the CSR for the first time; 2235/// Spilling a live range in the cold path can have lower cost than using 2236/// the CSR for the first time. Returns the physical register if we decide 2237/// to use the CSR; otherwise return 0. 2238unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg, 2239 AllocationOrder &Order, 2240 unsigned PhysReg, 2241 unsigned &CostPerUseLimit, 2242 SmallVectorImpl<unsigned> &NewVRegs) { 2243 if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) { 2244 // We choose spill over using the CSR for the first time if the spill cost 2245 // is lower than CSRCost. 2246 SA->analyze(&VirtReg); 2247 if (calcSpillCost() >= CSRCost) 2248 return PhysReg; 2249 2250 // We are going to spill, set CostPerUseLimit to 1 to make sure that 2251 // we will not use a callee-saved register in tryEvict. 2252 CostPerUseLimit = 1; 2253 return 0; 2254 } 2255 if (getStage(VirtReg) < RS_Split) { 2256 // We choose pre-splitting over using the CSR for the first time if 2257 // the cost of splitting is lower than CSRCost. 2258 SA->analyze(&VirtReg); 2259 unsigned NumCands = 0; 2260 BlockFrequency BestCost = CSRCost; // Don't modify CSRCost. 2261 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost, 2262 NumCands, true /*IgnoreCSR*/); 2263 if (BestCand == NoCand) 2264 // Use the CSR if we can't find a region split below CSRCost. 2265 return PhysReg; 2266 2267 // Perform the actual pre-splitting. 2268 doRegionSplit(VirtReg, BestCand, false/*HasCompact*/, NewVRegs); 2269 return 0; 2270 } 2271 return PhysReg; 2272} 2273 2274void RAGreedy::aboutToRemoveInterval(LiveInterval &LI) { 2275 // Do not keep invalid information around. 2276 SetOfBrokenHints.remove(&LI); 2277} 2278 2279void RAGreedy::initializeCSRCost() { 2280 // We use the larger one out of the command-line option and the value report 2281 // by TRI. 2282 CSRCost = BlockFrequency( 2283 std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost())); 2284 if (!CSRCost.getFrequency()) 2285 return; 2286 2287 // Raw cost is relative to Entry == 2^14; scale it appropriately. 2288 uint64_t ActualEntry = MBFI->getEntryFreq(); 2289 if (!ActualEntry) { 2290 CSRCost = 0; 2291 return; 2292 } 2293 uint64_t FixedEntry = 1 << 14; 2294 if (ActualEntry < FixedEntry) 2295 CSRCost *= BranchProbability(ActualEntry, FixedEntry); 2296 else if (ActualEntry <= UINT32_MAX) 2297 // Invert the fraction and divide. 2298 CSRCost /= BranchProbability(FixedEntry, ActualEntry); 2299 else 2300 // Can't use BranchProbability in general, since it takes 32-bit numbers. 2301 CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry); 2302} 2303 2304/// \brief Collect the hint info for \p Reg. 2305/// The results are stored into \p Out. 2306/// \p Out is not cleared before being populated. 2307void RAGreedy::collectHintInfo(unsigned Reg, HintsInfo &Out) { 2308 for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) { 2309 if (!Instr.isFullCopy()) 2310 continue; 2311 // Look for the other end of the copy. 2312 unsigned OtherReg = Instr.getOperand(0).getReg(); 2313 if (OtherReg == Reg) { 2314 OtherReg = Instr.getOperand(1).getReg(); 2315 if (OtherReg == Reg) 2316 continue; 2317 } 2318 // Get the current assignment. 2319 unsigned OtherPhysReg = TargetRegisterInfo::isPhysicalRegister(OtherReg) 2320 ? OtherReg 2321 : VRM->getPhys(OtherReg); 2322 // Push the collected information. 2323 Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg, 2324 OtherPhysReg)); 2325 } 2326} 2327 2328/// \brief Using the given \p List, compute the cost of the broken hints if 2329/// \p PhysReg was used. 2330/// \return The cost of \p List for \p PhysReg. 2331BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List, 2332 unsigned PhysReg) { 2333 BlockFrequency Cost = 0; 2334 for (const HintInfo &Info : List) { 2335 if (Info.PhysReg != PhysReg) 2336 Cost += Info.Freq; 2337 } 2338 return Cost; 2339} 2340 2341/// \brief Using the register assigned to \p VirtReg, try to recolor 2342/// all the live ranges that are copy-related with \p VirtReg. 2343/// The recoloring is then propagated to all the live-ranges that have 2344/// been recolored and so on, until no more copies can be coalesced or 2345/// it is not profitable. 2346/// For a given live range, profitability is determined by the sum of the 2347/// frequencies of the non-identity copies it would introduce with the old 2348/// and new register. 2349void RAGreedy::tryHintRecoloring(LiveInterval &VirtReg) { 2350 // We have a broken hint, check if it is possible to fix it by 2351 // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted 2352 // some register and PhysReg may be available for the other live-ranges. 2353 SmallSet<unsigned, 4> Visited; 2354 SmallVector<unsigned, 2> RecoloringCandidates; 2355 HintsInfo Info; 2356 unsigned Reg = VirtReg.reg; 2357 unsigned PhysReg = VRM->getPhys(Reg); 2358 // Start the recoloring algorithm from the input live-interval, then 2359 // it will propagate to the ones that are copy-related with it. 2360 Visited.insert(Reg); 2361 RecoloringCandidates.push_back(Reg); 2362 2363 DEBUG(dbgs() << "Trying to reconcile hints for: " << PrintReg(Reg, TRI) << '(' 2364 << PrintReg(PhysReg, TRI) << ")\n"); 2365 2366 do { 2367 Reg = RecoloringCandidates.pop_back_val(); 2368 2369 // We cannot recolor physcal register. 2370 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 2371 continue; 2372 2373 assert(VRM->hasPhys(Reg) && "We have unallocated variable!!"); 2374 2375 // Get the live interval mapped with this virtual register to be able 2376 // to check for the interference with the new color. 2377 LiveInterval &LI = LIS->getInterval(Reg); 2378 unsigned CurrPhys = VRM->getPhys(Reg); 2379 // Check that the new color matches the register class constraints and 2380 // that it is free for this live range. 2381 if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(PhysReg) || 2382 Matrix->checkInterference(LI, PhysReg))) 2383 continue; 2384 2385 DEBUG(dbgs() << PrintReg(Reg, TRI) << '(' << PrintReg(CurrPhys, TRI) 2386 << ") is recolorable.\n"); 2387 2388 // Gather the hint info. 2389 Info.clear(); 2390 collectHintInfo(Reg, Info); 2391 // Check if recoloring the live-range will increase the cost of the 2392 // non-identity copies. 2393 if (CurrPhys != PhysReg) { 2394 DEBUG(dbgs() << "Checking profitability:\n"); 2395 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys); 2396 BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg); 2397 DEBUG(dbgs() << "Old Cost: " << OldCopiesCost.getFrequency() 2398 << "\nNew Cost: " << NewCopiesCost.getFrequency() << '\n'); 2399 if (OldCopiesCost < NewCopiesCost) { 2400 DEBUG(dbgs() << "=> Not profitable.\n"); 2401 continue; 2402 } 2403 // At this point, the cost is either cheaper or equal. If it is 2404 // equal, we consider this is profitable because it may expose 2405 // more recoloring opportunities. 2406 DEBUG(dbgs() << "=> Profitable.\n"); 2407 // Recolor the live-range. 2408 Matrix->unassign(LI); 2409 Matrix->assign(LI, PhysReg); 2410 } 2411 // Push all copy-related live-ranges to keep reconciling the broken 2412 // hints. 2413 for (const HintInfo &HI : Info) { 2414 if (Visited.insert(HI.Reg).second) 2415 RecoloringCandidates.push_back(HI.Reg); 2416 } 2417 } while (!RecoloringCandidates.empty()); 2418} 2419 2420/// \brief Try to recolor broken hints. 2421/// Broken hints may be repaired by recoloring when an evicted variable 2422/// freed up a register for a larger live-range. 2423/// Consider the following example: 2424/// BB1: 2425/// a = 2426/// b = 2427/// BB2: 2428/// ... 2429/// = b 2430/// = a 2431/// Let us assume b gets split: 2432/// BB1: 2433/// a = 2434/// b = 2435/// BB2: 2436/// c = b 2437/// ... 2438/// d = c 2439/// = d 2440/// = a 2441/// Because of how the allocation work, b, c, and d may be assigned different 2442/// colors. Now, if a gets evicted later: 2443/// BB1: 2444/// a = 2445/// st a, SpillSlot 2446/// b = 2447/// BB2: 2448/// c = b 2449/// ... 2450/// d = c 2451/// = d 2452/// e = ld SpillSlot 2453/// = e 2454/// This is likely that we can assign the same register for b, c, and d, 2455/// getting rid of 2 copies. 2456void RAGreedy::tryHintsRecoloring() { 2457 for (LiveInterval *LI : SetOfBrokenHints) { 2458 assert(TargetRegisterInfo::isVirtualRegister(LI->reg) && 2459 "Recoloring is possible only for virtual registers"); 2460 // Some dead defs may be around (e.g., because of debug uses). 2461 // Ignore those. 2462 if (!VRM->hasPhys(LI->reg)) 2463 continue; 2464 tryHintRecoloring(*LI); 2465 } 2466} 2467 2468unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg, 2469 SmallVectorImpl<unsigned> &NewVRegs, 2470 SmallVirtRegSet &FixedRegisters, 2471 unsigned Depth) { 2472 unsigned CostPerUseLimit = ~0u; 2473 // First try assigning a free register. 2474 AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix); 2475 if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) { 2476 // When NewVRegs is not empty, we may have made decisions such as evicting 2477 // a virtual register, go with the earlier decisions and use the physical 2478 // register. 2479 if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) && 2480 NewVRegs.empty()) { 2481 unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg, 2482 CostPerUseLimit, NewVRegs); 2483 if (CSRReg || !NewVRegs.empty()) 2484 // Return now if we decide to use a CSR or create new vregs due to 2485 // pre-splitting. 2486 return CSRReg; 2487 } else 2488 return PhysReg; 2489 } 2490 2491 LiveRangeStage Stage = getStage(VirtReg); 2492 DEBUG(dbgs() << StageName[Stage] 2493 << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n'); 2494 2495 // Try to evict a less worthy live range, but only for ranges from the primary 2496 // queue. The RS_Split ranges already failed to do this, and they should not 2497 // get a second chance until they have been split. 2498 if (Stage != RS_Split) 2499 if (unsigned PhysReg = 2500 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) { 2501 unsigned Hint = MRI->getSimpleHint(VirtReg.reg); 2502 // If VirtReg has a hint and that hint is broken record this 2503 // virtual register as a recoloring candidate for broken hint. 2504 // Indeed, since we evicted a variable in its neighborhood it is 2505 // likely we can at least partially recolor some of the 2506 // copy-related live-ranges. 2507 if (Hint && Hint != PhysReg) 2508 SetOfBrokenHints.insert(&VirtReg); 2509 return PhysReg; 2510 } 2511 2512 assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); 2513 2514 // The first time we see a live range, don't try to split or spill. 2515 // Wait until the second time, when all smaller ranges have been allocated. 2516 // This gives a better picture of the interference to split around. 2517 if (Stage < RS_Split) { 2518 setStage(VirtReg, RS_Split); 2519 DEBUG(dbgs() << "wait for second round\n"); 2520 NewVRegs.push_back(VirtReg.reg); 2521 return 0; 2522 } 2523 2524 // If we couldn't allocate a register from spilling, there is probably some 2525 // invalid inline assembly. The base class wil report it. 2526 if (Stage >= RS_Done || !VirtReg.isSpillable()) 2527 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters, 2528 Depth); 2529 2530 // Try splitting VirtReg or interferences. 2531 unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs); 2532 if (PhysReg || !NewVRegs.empty()) 2533 return PhysReg; 2534 2535 // Finally spill VirtReg itself. 2536 if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) { 2537 // TODO: This is experimental and in particular, we do not model 2538 // the live range splitting done by spilling correctly. 2539 // We would need a deep integration with the spiller to do the 2540 // right thing here. Anyway, that is still good for early testing. 2541 setStage(VirtReg, RS_Memory); 2542 DEBUG(dbgs() << "Do as if this register is in memory\n"); 2543 NewVRegs.push_back(VirtReg.reg); 2544 } else { 2545 NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled); 2546 LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this); 2547 spiller().spill(LRE); 2548 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); 2549 2550 if (VerifyEnabled) 2551 MF->verify(this, "After spilling"); 2552 } 2553 2554 // The live virtual register requesting allocation was spilled, so tell 2555 // the caller not to allocate anything during this round. 2556 return 0; 2557} 2558 2559bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { 2560 DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n" 2561 << "********** Function: " << mf.getName() << '\n'); 2562 2563 MF = &mf; 2564 TRI = MF->getSubtarget().getRegisterInfo(); 2565 TII = MF->getSubtarget().getInstrInfo(); 2566 RCI.runOnMachineFunction(mf); 2567 2568 EnableLocalReassign = EnableLocalReassignment || 2569 MF->getSubtarget().enableRALocalReassignment( 2570 MF->getTarget().getOptLevel()); 2571 2572 if (VerifyEnabled) 2573 MF->verify(this, "Before greedy register allocator"); 2574 2575 RegAllocBase::init(getAnalysis<VirtRegMap>(), 2576 getAnalysis<LiveIntervals>(), 2577 getAnalysis<LiveRegMatrix>()); 2578 Indexes = &getAnalysis<SlotIndexes>(); 2579 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 2580 DomTree = &getAnalysis<MachineDominatorTree>(); 2581 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 2582 Loops = &getAnalysis<MachineLoopInfo>(); 2583 Bundles = &getAnalysis<EdgeBundles>(); 2584 SpillPlacer = &getAnalysis<SpillPlacement>(); 2585 DebugVars = &getAnalysis<LiveDebugVariables>(); 2586 2587 initializeCSRCost(); 2588 2589 calculateSpillWeightsAndHints(*LIS, mf, VRM, *Loops, *MBFI); 2590 2591 DEBUG(LIS->dump()); 2592 2593 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops)); 2594 SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI)); 2595 ExtraRegInfo.clear(); 2596 ExtraRegInfo.resize(MRI->getNumVirtRegs()); 2597 NextCascade = 1; 2598 IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); 2599 GlobalCand.resize(32); // This will grow as needed. 2600 SetOfBrokenHints.clear(); 2601 2602 allocatePhysRegs(); 2603 tryHintsRecoloring(); 2604 releaseMemory(); 2605 return true; 2606} 2607