//===- RegAllocGreedy.cpp - greedy register allocator ---------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file defines the RAGreedy function pass for register allocation in // optimized builds. // //===----------------------------------------------------------------------===// #include "RegAllocGreedy.h" #include "AllocationOrder.h" #include "InterferenceCache.h" #include "RegAllocBase.h" #include "RegAllocEvictionAdvisor.h" #include "RegAllocPriorityAdvisor.h" #include "SpillPlacement.h" #include "SplitKit.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/EdgeBundles.h" #include "llvm/CodeGen/LiveDebugVariables.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveIntervalUnion.h" #include "llvm/CodeGen/LiveIntervals.h" #include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/LiveRegMatrix.h" #include "llvm/CodeGen/LiveStacks.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/CodeGen/RegisterClassInfo.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/CodeGen/Spiller.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/CodeGen/VirtRegMap.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/Function.h" #include "llvm/IR/LLVMContext.h" #include "llvm/InitializePasses.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/Pass.h" #include "llvm/Support/BlockFrequency.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/Timer.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> #include <cassert> #include <cstdint> #include <utility> usingnamespacellvm; #define DEBUG_TYPE … STATISTIC(NumGlobalSplits, "Number of split global live ranges"); STATISTIC(NumLocalSplits, "Number of split local live ranges"); STATISTIC(NumEvicted, "Number of interferences evicted"); static cl::opt<SplitEditor::ComplementSpillMode> SplitSpillMode( "split-spill-mode", cl::Hidden, cl::desc("Spill mode for splitting live ranges"), cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")), cl::init(SplitEditor::SM_Speed)); static cl::opt<unsigned> LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5)); static cl::opt<unsigned> LastChanceRecoloringMaxInterference( "lcr-max-interf", cl::Hidden, cl::desc("Last chance recoloring maximum number of considered" " interference at a time"), cl::init(8)); static cl::opt<bool> ExhaustiveSearch( "exhaustive-register-search", cl::NotHidden, cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring"), cl::Hidden); static cl::opt<bool> EnableDeferredSpilling( "enable-deferred-spilling", cl::Hidden, cl::desc("Instead of spilling a variable right away, defer the actual " "code insertion to the end of the allocation. That way the " "allocator might still find a suitable coloring for this " "variable because of other evicted variables."), cl::init(false)); // FIXME: Find a good default for this flag and remove the flag. static cl::opt<unsigned> CSRFirstTimeCost("regalloc-csr-first-time-cost", cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden); static cl::opt<unsigned long> GrowRegionComplexityBudget( "grow-region-complexity-budget", cl::desc("growRegion() does not scale with the number of BB edges, so " "limit its budget and bail out once we reach the limit."), cl::init(10000), cl::Hidden); static cl::opt<bool> GreedyRegClassPriorityTrumpsGlobalness( "greedy-regclass-priority-trumps-globalness", cl::desc("Change the greedy register allocator's live range priority " "calculation to make the AllocationPriority of the register class " "more important then whether the range is global"), cl::Hidden); static cl::opt<bool> GreedyReverseLocalAssignment( "greedy-reverse-local-assignment", cl::desc("Reverse allocation order of local live ranges, such that " "shorter local live ranges will tend to be allocated first"), cl::Hidden); static cl::opt<unsigned> SplitThresholdForRegWithHint( "split-threshold-for-reg-with-hint", cl::desc("The threshold for splitting a virtual register with a hint, in " "percentate"), cl::init(75), cl::Hidden); static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator); char RAGreedy::ID = …; char &llvm::RAGreedyID = …; INITIALIZE_PASS_BEGIN(RAGreedy, "greedy", "Greedy Register Allocator", false, false) INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass) INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass) INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) INITIALIZE_PASS_DEPENDENCY(MachineScheduler) INITIALIZE_PASS_DEPENDENCY(LiveStacks) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(VirtRegMap) INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix) INITIALIZE_PASS_DEPENDENCY(EdgeBundles) INITIALIZE_PASS_DEPENDENCY(SpillPlacement) INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass) INITIALIZE_PASS_DEPENDENCY(RegAllocEvictionAdvisorAnalysis) INITIALIZE_PASS_DEPENDENCY(RegAllocPriorityAdvisorAnalysis) INITIALIZE_PASS_END(RAGreedy, "greedy", "Greedy Register Allocator", false, false) #ifndef NDEBUG const char *const RAGreedy::StageName[] = { "RS_New", "RS_Assign", "RS_Split", "RS_Split2", "RS_Spill", "RS_Memory", "RS_Done" }; #endif // Hysteresis to use when comparing floats. // This helps stabilize decisions based on float comparisons. const float Hysteresis = …; // 0.97998046875 FunctionPass* llvm::createGreedyRegisterAllocator() { … } FunctionPass *llvm::createGreedyRegisterAllocator(RegAllocFilterFunc Ftor) { … } RAGreedy::RAGreedy(RegAllocFilterFunc F) : … { … } void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const { … } //===----------------------------------------------------------------------===// // LiveRangeEdit delegate methods //===----------------------------------------------------------------------===// bool RAGreedy::LRE_CanEraseVirtReg(Register VirtReg) { … } void RAGreedy::LRE_WillShrinkVirtReg(Register VirtReg) { … } void RAGreedy::LRE_DidCloneVirtReg(Register New, Register Old) { … } void RAGreedy::ExtraRegInfo::LRE_DidCloneVirtReg(Register New, Register Old) { … } void RAGreedy::releaseMemory() { … } void RAGreedy::enqueueImpl(const LiveInterval *LI) { … } void RAGreedy::enqueue(PQueue &CurQueue, const LiveInterval *LI) { … } unsigned DefaultPriorityAdvisor::getPriority(const LiveInterval &LI) const { … } const LiveInterval *RAGreedy::dequeue() { … } const LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) { … } //===----------------------------------------------------------------------===// // Direct Assignment //===----------------------------------------------------------------------===// /// tryAssign - Try to assign VirtReg to an available register. MCRegister RAGreedy::tryAssign(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs, const SmallVirtRegSet &FixedRegisters) { … } //===----------------------------------------------------------------------===// // Interference eviction //===----------------------------------------------------------------------===// bool RegAllocEvictionAdvisor::canReassign(const LiveInterval &VirtReg, MCRegister FromReg) const { … } /// evictInterference - Evict any interferring registers that prevent VirtReg /// from being assigned to Physreg. This assumes that canEvictInterference /// returned true. void RAGreedy::evictInterference(const LiveInterval &VirtReg, MCRegister PhysReg, SmallVectorImpl<Register> &NewVRegs) { … } /// Returns true if the given \p PhysReg is a callee saved register and has not /// been used for allocation yet. bool RegAllocEvictionAdvisor::isUnusedCalleeSavedReg(MCRegister PhysReg) const { … } std::optional<unsigned> RegAllocEvictionAdvisor::getOrderLimit(const LiveInterval &VirtReg, const AllocationOrder &Order, unsigned CostPerUseLimit) const { … } bool RegAllocEvictionAdvisor::canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const { … } /// tryEvict - Try to evict all interferences for a physreg. /// @param VirtReg Currently unassigned virtual register. /// @param Order Physregs to try. /// @return Physreg to assign VirtReg, or 0. MCRegister RAGreedy::tryEvict(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs, uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) { … } //===----------------------------------------------------------------------===// // Region Splitting //===----------------------------------------------------------------------===// /// addSplitConstraints - Fill out the SplitConstraints vector based on the /// interference pattern in Physreg and its aliases. Add the constraints to /// SpillPlacement and return the static cost of this split in Cost, assuming /// that all preferences in SplitConstraints are met. /// Return false if there are no bundles with positive bias. bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf, BlockFrequency &Cost) { … } /// addThroughConstraints - Add constraints and links to SpillPlacer from the /// live-through blocks in Blocks. bool RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf, ArrayRef<unsigned> Blocks) { … } bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) { … } /// calcCompactRegion - Compute the set of edge bundles that should be live /// when splitting the current live range into compact regions. Compact /// regions can be computed without looking at interference. They are the /// regions formed by removing all the live-through blocks from the live range. /// /// Returns false if the current live range is already compact, or if the /// compact regions would form single block regions anyway. bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) { … } /// calcSpillCost - Compute how expensive it would be to split the live range in /// SA around all use blocks instead of forming bundle regions. BlockFrequency RAGreedy::calcSpillCost() { … } /// calcGlobalSplitCost - Return the global split cost of following the split /// pattern in LiveBundles. This cost should be added to the local cost of the /// interference pattern in SplitConstraints. /// BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand, const AllocationOrder &Order) { … } /// splitAroundRegion - Split the current live range around the regions /// determined by BundleCand and GlobalCand. /// /// Before calling this function, GlobalCand and BundleCand must be initialized /// so each bundle is assigned to a valid candidate, or NoCand for the /// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor /// objects must be initialized for the current live range, and intervals /// created for the used candidates. /// /// @param LREdit The LiveRangeEdit object handling the current split. /// @param UsedCands List of used GlobalCand entries. Every BundleCand value /// must appear in this list. void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit, ArrayRef<unsigned> UsedCands) { … } MCRegister RAGreedy::tryRegionSplit(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs) { … } unsigned RAGreedy::calculateRegionSplitCostAroundReg(MCPhysReg PhysReg, AllocationOrder &Order, BlockFrequency &BestCost, unsigned &NumCands, unsigned &BestCand) { … } unsigned RAGreedy::calculateRegionSplitCost(const LiveInterval &VirtReg, AllocationOrder &Order, BlockFrequency &BestCost, unsigned &NumCands, bool IgnoreCSR) { … } unsigned RAGreedy::doRegionSplit(const LiveInterval &VirtReg, unsigned BestCand, bool HasCompact, SmallVectorImpl<Register> &NewVRegs) { … } // VirtReg has a physical Hint, this function tries to split VirtReg around // Hint if we can place new COPY instructions in cold blocks. bool RAGreedy::trySplitAroundHintReg(MCPhysReg Hint, const LiveInterval &VirtReg, SmallVectorImpl<Register> &NewVRegs, AllocationOrder &Order) { … } //===----------------------------------------------------------------------===// // Per-Block Splitting //===----------------------------------------------------------------------===// /// tryBlockSplit - Split a global live range around every block with uses. This /// creates a lot of local live ranges, that will be split by tryLocalSplit if /// they don't allocate. unsigned RAGreedy::tryBlockSplit(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs) { … } //===----------------------------------------------------------------------===// // Per-Instruction Splitting //===----------------------------------------------------------------------===// /// Get the number of allocatable registers that match the constraints of \p Reg /// on \p MI and that are also in \p SuperRC. static unsigned getNumAllocatableRegsForConstraints( const MachineInstr *MI, Register Reg, const TargetRegisterClass *SuperRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, const RegisterClassInfo &RCI) { … } static LaneBitmask getInstReadLaneMask(const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, const MachineInstr &FirstMI, Register Reg) { … } /// Return true if \p MI at \P Use reads a subset of the lanes live in \p /// VirtReg. static bool readsLaneSubset(const MachineRegisterInfo &MRI, const MachineInstr *MI, const LiveInterval &VirtReg, const TargetRegisterInfo *TRI, SlotIndex Use, const TargetInstrInfo *TII) { … } /// tryInstructionSplit - Split a live range around individual instructions. /// This is normally not worthwhile since the spiller is doing essentially the /// same thing. However, when the live range is in a constrained register /// class, it may help to insert copies such that parts of the live range can /// be moved to a larger register class. /// /// This is similar to spilling to a larger register class. unsigned RAGreedy::tryInstructionSplit(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs) { … } //===----------------------------------------------------------------------===// // Local Splitting //===----------------------------------------------------------------------===// /// calcGapWeights - Compute the maximum spill weight that needs to be evicted /// in order to use PhysReg between two entries in SA->UseSlots. /// /// GapWeight[I] represents the gap between UseSlots[I] and UseSlots[I + 1]. /// void RAGreedy::calcGapWeights(MCRegister PhysReg, SmallVectorImpl<float> &GapWeight) { … } /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only /// basic block. /// unsigned RAGreedy::tryLocalSplit(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs) { … } //===----------------------------------------------------------------------===// // Live Range Splitting //===----------------------------------------------------------------------===// /// trySplit - Try to split VirtReg or one of its interferences, making it /// assignable. /// @return Physreg when VirtReg may be assigned and/or new NewVRegs. unsigned RAGreedy::trySplit(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs, const SmallVirtRegSet &FixedRegisters) { … } //===----------------------------------------------------------------------===// // Last Chance Recoloring //===----------------------------------------------------------------------===// /// Return true if \p reg has any tied def operand. static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg) { … } /// Return true if the existing assignment of \p Intf overlaps, but is not the /// same, as \p PhysReg. static bool assignedRegPartiallyOverlaps(const TargetRegisterInfo &TRI, const VirtRegMap &VRM, MCRegister PhysReg, const LiveInterval &Intf) { … } /// mayRecolorAllInterferences - Check if the virtual registers that /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be /// recolored to free \p PhysReg. /// When true is returned, \p RecoloringCandidates has been augmented with all /// the live intervals that need to be recolored in order to free \p PhysReg /// for \p VirtReg. /// \p FixedRegisters contains all the virtual registers that cannot be /// recolored. bool RAGreedy::mayRecolorAllInterferences( MCRegister PhysReg, const LiveInterval &VirtReg, SmallLISet &RecoloringCandidates, const SmallVirtRegSet &FixedRegisters) { … } /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring /// its interferences. /// Last chance recoloring chooses a color for \p VirtReg and recolors every /// virtual register that was using it. The recoloring process may recursively /// use the last chance recoloring. Therefore, when a virtual register has been /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot /// be last-chance-recolored again during this recoloring "session". /// E.g., /// Let /// vA can use {R1, R2 } /// vB can use { R2, R3} /// vC can use {R1 } /// Where vA, vB, and vC cannot be split anymore (they are reloads for /// instance) and they all interfere. /// /// vA is assigned R1 /// vB is assigned R2 /// vC tries to evict vA but vA is already done. /// Regular register allocation fails. /// /// Last chance recoloring kicks in: /// vC does as if vA was evicted => vC uses R1. /// vC is marked as fixed. /// vA needs to find a color. /// None are available. /// vA cannot evict vC: vC is a fixed virtual register now. /// vA does as if vB was evicted => vA uses R2. /// vB needs to find a color. /// R3 is available. /// Recoloring => vC = R1, vA = R2, vB = R3 /// /// \p Order defines the preferred allocation order for \p VirtReg. /// \p NewRegs will contain any new virtual register that have been created /// (split, spill) during the process and that must be assigned. /// \p FixedRegisters contains all the virtual registers that cannot be /// recolored. /// /// \p RecolorStack tracks the original assignments of successfully recolored /// registers. /// /// \p Depth gives the current depth of the last chance recoloring. /// \return a physical register that can be used for VirtReg or ~0u if none /// exists. unsigned RAGreedy::tryLastChanceRecoloring(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs, SmallVirtRegSet &FixedRegisters, RecoloringStack &RecolorStack, unsigned Depth) { … } /// tryRecoloringCandidates - Try to assign a new color to every register /// in \RecoloringQueue. /// \p NewRegs will contain any new virtual register created during the /// recoloring process. /// \p FixedRegisters[in/out] contains all the registers that have been /// recolored. /// \return true if all virtual registers in RecoloringQueue were successfully /// recolored, false otherwise. bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue, SmallVectorImpl<Register> &NewVRegs, SmallVirtRegSet &FixedRegisters, RecoloringStack &RecolorStack, unsigned Depth) { … } //===----------------------------------------------------------------------===// // Main Entry Point //===----------------------------------------------------------------------===// MCRegister RAGreedy::selectOrSplit(const LiveInterval &VirtReg, SmallVectorImpl<Register> &NewVRegs) { … } /// Using a CSR for the first time has a cost because it causes push|pop /// to be added to prologue|epilogue. Splitting a cold section of the live /// range can have lower cost than using the CSR for the first time; /// Spilling a live range in the cold path can have lower cost than using /// the CSR for the first time. Returns the physical register if we decide /// to use the CSR; otherwise return 0. MCRegister RAGreedy::tryAssignCSRFirstTime( const LiveInterval &VirtReg, AllocationOrder &Order, MCRegister PhysReg, uint8_t &CostPerUseLimit, SmallVectorImpl<Register> &NewVRegs) { … } void RAGreedy::aboutToRemoveInterval(const LiveInterval &LI) { … } void RAGreedy::initializeCSRCost() { … } /// Collect the hint info for \p Reg. /// The results are stored into \p Out. /// \p Out is not cleared before being populated. void RAGreedy::collectHintInfo(Register Reg, HintsInfo &Out) { … } /// Using the given \p List, compute the cost of the broken hints if /// \p PhysReg was used. /// \return The cost of \p List for \p PhysReg. BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List, MCRegister PhysReg) { … } /// Using the register assigned to \p VirtReg, try to recolor /// all the live ranges that are copy-related with \p VirtReg. /// The recoloring is then propagated to all the live-ranges that have /// been recolored and so on, until no more copies can be coalesced or /// it is not profitable. /// For a given live range, profitability is determined by the sum of the /// frequencies of the non-identity copies it would introduce with the old /// and new register. void RAGreedy::tryHintRecoloring(const LiveInterval &VirtReg) { … } /// Try to recolor broken hints. /// Broken hints may be repaired by recoloring when an evicted variable /// freed up a register for a larger live-range. /// Consider the following example: /// BB1: /// a = /// b = /// BB2: /// ... /// = b /// = a /// Let us assume b gets split: /// BB1: /// a = /// b = /// BB2: /// c = b /// ... /// d = c /// = d /// = a /// Because of how the allocation work, b, c, and d may be assigned different /// colors. Now, if a gets evicted later: /// BB1: /// a = /// st a, SpillSlot /// b = /// BB2: /// c = b /// ... /// d = c /// = d /// e = ld SpillSlot /// = e /// This is likely that we can assign the same register for b, c, and d, /// getting rid of 2 copies. void RAGreedy::tryHintsRecoloring() { … } MCRegister RAGreedy::selectOrSplitImpl(const LiveInterval &VirtReg, SmallVectorImpl<Register> &NewVRegs, SmallVirtRegSet &FixedRegisters, RecoloringStack &RecolorStack, unsigned Depth) { … } void RAGreedy::RAGreedyStats::report(MachineOptimizationRemarkMissed &R) { … } RAGreedy::RAGreedyStats RAGreedy::computeStats(MachineBasicBlock &MBB) { … } RAGreedy::RAGreedyStats RAGreedy::reportStats(MachineLoop *L) { … } void RAGreedy::reportStats() { … } bool RAGreedy::hasVirtRegAlloc() { … } bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { … }
Codebase Browser
llvm