summaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/RegAllocGreedy.cpp')
-rw-r--r--llvm/lib/CodeGen/RegAllocGreedy.cpp183
1 files changed, 5 insertions, 178 deletions
diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp
index 6ea6dbcbbb74..7870574df5b2 100644
--- a/llvm/lib/CodeGen/RegAllocGreedy.cpp
+++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp
@@ -440,143 +440,6 @@ Register RegAllocEvictionAdvisor::canReassign(LiveInterval &VirtReg,
return PhysReg;
}
-/// shouldEvict - determine if A should evict the assigned live range B. The
-/// eviction policy defined by this function together with the allocation order
-/// defined by enqueue() decides which registers ultimately end up being split
-/// and spilled.
-///
-/// Cascade numbers are used to prevent infinite loops if this function is a
-/// cyclic relation.
-///
-/// @param A The live range to be assigned.
-/// @param IsHint True when A is about to be assigned to its preferred
-/// register.
-/// @param B The live range to be evicted.
-/// @param BreaksHint True when B is already assigned to its preferred register.
-bool DefaultEvictionAdvisor::shouldEvict(LiveInterval &A, bool IsHint,
- LiveInterval &B,
- bool BreaksHint) const {
- bool CanSplit = RA.getExtraInfo().getStage(B) < RS_Spill;
-
- // Be fairly aggressive about following hints as long as the evictee can be
- // split.
- if (CanSplit && IsHint && !BreaksHint)
- return true;
-
- if (A.weight() > B.weight()) {
- LLVM_DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight() << '\n');
- return true;
- }
- return false;
-}
-
-/// canEvictHintInterference - return true if the interference for VirtReg
-/// on the PhysReg, which is VirtReg's hint, can be evicted in favor of VirtReg.
-bool DefaultEvictionAdvisor::canEvictHintInterference(
- LiveInterval &VirtReg, MCRegister PhysReg,
- const SmallVirtRegSet &FixedRegisters) const {
- EvictionCost MaxCost;
- MaxCost.setBrokenHints(1);
- return canEvictInterferenceBasedOnCost(VirtReg, PhysReg, true, MaxCost,
- FixedRegisters);
-}
-
-/// canEvictInterferenceBasedOnCost - Return true if all interferences between
-/// VirtReg and PhysReg can be evicted.
-///
-/// @param VirtReg Live range that is about to be assigned.
-/// @param PhysReg Desired register for assignment.
-/// @param IsHint True when PhysReg is VirtReg's preferred register.
-/// @param MaxCost Only look for cheaper candidates and update with new cost
-/// when returning true.
-/// @returns True when interference can be evicted cheaper than MaxCost.
-bool DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost(
- LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
- EvictionCost &MaxCost, const SmallVirtRegSet &FixedRegisters) const {
- // It is only possible to evict virtual register interference.
- if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
- return false;
-
- bool IsLocal = VirtReg.empty() || LIS->intervalIsInOneMBB(VirtReg);
-
- // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
- // involved in an eviction before. If a cascade number was assigned, deny
- // evicting anything with the same or a newer cascade number. This prevents
- // infinite eviction loops.
- //
- // This works out so a register without a cascade number is allowed to evict
- // anything, and it can be evicted by anything.
- unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(VirtReg.reg());
-
- EvictionCost Cost;
- for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
- LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
- // If there is 10 or more interferences, chances are one is heavier.
- const auto &Interferences = Q.interferingVRegs(10);
- if (Interferences.size() >= 10)
- return false;
-
- // Check if any interfering live range is heavier than MaxWeight.
- for (LiveInterval *Intf : reverse(Interferences)) {
- assert(Register::isVirtualRegister(Intf->reg()) &&
- "Only expecting virtual register interference from query");
-
- // Do not allow eviction of a virtual register if we are in the middle
- // of last-chance recoloring and this virtual register is one that we
- // have scavenged a physical register for.
- if (FixedRegisters.count(Intf->reg()))
- return false;
-
- // Never evict spill products. They cannot split or spill.
- if (RA.getExtraInfo().getStage(*Intf) == RS_Done)
- return false;
- // Once a live range becomes small enough, it is urgent that we find a
- // register for it. This is indicated by an infinite spill weight. These
- // urgent live ranges get to evict almost anything.
- //
- // Also allow urgent evictions of unspillable ranges from a strictly
- // larger allocation order.
- bool Urgent =
- !VirtReg.isSpillable() &&
- (Intf->isSpillable() ||
- RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg())) <
- RegClassInfo.getNumAllocatableRegs(
- MRI->getRegClass(Intf->reg())));
- // Only evict older cascades or live ranges without a cascade.
- unsigned IntfCascade = RA.getExtraInfo().getCascade(Intf->reg());
- if (Cascade <= IntfCascade) {
- if (!Urgent)
- return false;
- // We permit breaking cascades for urgent evictions. It should be the
- // last resort, though, so make it really expensive.
- Cost.BrokenHints += 10;
- }
- // Would this break a satisfied hint?
- bool BreaksHint = VRM->hasPreferredPhys(Intf->reg());
- // Update eviction cost.
- Cost.BrokenHints += BreaksHint;
- Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight());
- // Abort if this would be too expensive.
- if (!(Cost < MaxCost))
- return false;
- if (Urgent)
- continue;
- // Apply the eviction policy for non-urgent evictions.
- if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
- return false;
- // If !MaxCost.isMax(), then we're just looking for a cheap register.
- // Evicting another local live range in this case could lead to suboptimal
- // coloring.
- if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
- (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
- return false;
- }
- }
- }
- MaxCost = Cost;
- return true;
-}
-
/// Return true if all interferences between VirtReg and PhysReg between
/// Start and End can be evicted.
///
@@ -757,44 +620,6 @@ bool RegAllocEvictionAdvisor::canAllocatePhysReg(unsigned CostPerUseLimit,
return true;
}
-MCRegister DefaultEvictionAdvisor::tryFindEvictionCandidate(
- LiveInterval &VirtReg, const AllocationOrder &Order,
- uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
- // Keep track of the cheapest interference seen so far.
- EvictionCost BestCost;
- BestCost.setMax();
- MCRegister BestPhys;
- auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);
- if (!MaybeOrderLimit)
- return MCRegister::NoRegister;
- unsigned OrderLimit = *MaybeOrderLimit;
-
- // When we are just looking for a reduced cost per use, don't break any
- // hints, and only evict smaller spill weights.
- if (CostPerUseLimit < uint8_t(~0u)) {
- BestCost.BrokenHints = 0;
- BestCost.MaxWeight = VirtReg.weight();
- }
-
- for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
- ++I) {
- MCRegister PhysReg = *I;
- assert(PhysReg);
- if (!canAllocatePhysReg(CostPerUseLimit, PhysReg) ||
- !canEvictInterferenceBasedOnCost(VirtReg, PhysReg, false, BestCost,
- FixedRegisters))
- continue;
-
- // Best so far.
- BestPhys = PhysReg;
-
- // Stop if the hint can be used.
- if (I.isHint())
- break;
- }
- return BestPhys;
-}
-
/// tryEvict - Try to evict all interferences for a physreg.
/// @param VirtReg Currently unassigned virtual register.
/// @param Order Physregs to try.
@@ -2922,6 +2747,10 @@ bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
RegCosts = TRI->getRegisterCosts(*MF);
+ ExtraInfo.emplace();
+ EvictAdvisor =
+ getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(*MF, *this);
+
VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *LIS, *VRM, *Loops, *MBFI);
SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM, *VRAI));
@@ -2931,9 +2760,7 @@ bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI, *VRAI));
- ExtraInfo.emplace();
- EvictAdvisor =
- getAnalysis<RegAllocEvictionAdvisorAnalysis>().getAdvisor(*MF, *this);
+
IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
GlobalCand.resize(32); // This will grow as needed.
SetOfBrokenHints.clear();
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-19 11:36:17 +0000