https://github.com/BeMg updated https://github.com/llvm/llvm-project/pull/239530
>From d6573eee58644c84f50a3fb11f2918bd2a24e2ca Mon Sep 17 00:00:00 2001 From: Piyou Chen <[email protected]> Date: Thu, 5 Nov 2026 23:18:29 -0800 Subject: [PATCH 1/2] [RegAlloc] Make tryAssignCSRFirstTime consider Remat/Spill --- .../include/llvm/CodeGen/TargetRegisterInfo.h | 8 + llvm/lib/CodeGen/RegAllocGreedy.cpp | 180 +++++++++++++++++- llvm/lib/CodeGen/RegAllocGreedy.h | 15 ++ 3 files changed, 201 insertions(+), 2 deletions(-) diff --git a/llvm/include/llvm/CodeGen/TargetRegisterInfo.h b/llvm/include/llvm/CodeGen/TargetRegisterInfo.h index a7bc58ad247184..27f16ff978cbb7 100644 --- a/llvm/include/llvm/CodeGen/TargetRegisterInfo.h +++ b/llvm/include/llvm/CodeGen/TargetRegisterInfo.h @@ -892,6 +892,14 @@ class LLVM_ABI TargetRegisterInfo : public MCRegisterInfo { return 30; } + /// Return true if the greedy register allocator should take + /// the lowest-cost choice before using an unused CSR. + /// This uses tryAssignCSRFirstTimeMinCost instead of + /// tryAssignCSRFirstTime. + virtual bool enableCSRFirstTimeMinCost(const MachineFunction &MF) const { + return false; + } + /// Returns true if the target requires (and can make use of) the register /// scavenger. virtual bool requiresRegisterScavenging(const MachineFunction &MF) const { diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp index f7655e97b99427..acce796d5ff651 100644 --- a/llvm/lib/CodeGen/RegAllocGreedy.cpp +++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp @@ -2471,6 +2471,49 @@ BlockFrequency RAGreedy::calcRematCost(const LiveInterval &VirtReg, return HasUse ? RematCost : BlockFrequency::max(); } +/// Return true if the spiller can rematerialize each use of \p LI. +/// And it can rematerialize for only one def. +static bool isRematerializableFromOriginal(const LiveInterval &LI, + const LiveIntervals &LIS, + const VirtRegMap &VRM, + const MachineRegisterInfo &MRI, + const TargetInstrInfo &TII) { + const LiveInterval &OrigLI = LIS.getInterval(VRM.getOriginal(LI.reg())); + const MachineInstr *Def = nullptr; + for (const VNInfo *VNI : OrigLI.valnos) { + if (VNI->isUnused()) + continue; + // Maybe more than one value def for VirtReg + if (VNI->isPHIDef() || Def) + return false; + Def = LIS.getInstructionFromIndex(VNI->def); + if (!Def || !TII.isReMaterializable(*Def)) + return false; + } + if (!Def) + return false; + for (const MachineInstr &MI : MRI.use_nodbg_instructions(LI.reg())) + if (!VirtRegAuxInfo::allUsesAvailableAt(Def, LIS.getInstructionIndex(MI), + LIS, MRI, TII)) + return false; + return true; +} + +/// The cost of rematerializing \p LI before each of its uses. +static BlockFrequency calcRematCostAtUses(const LiveInterval &LI, + const MachineRegisterInfo &MRI, + const SpillPlacement &SpillPlacer) { + uint64_t RematCost = 0; + SmallPtrSet<const MachineInstr *, 8> Seen; + for (const MachineInstr &MI : MRI.use_nodbg_instructions(LI.reg())) { + if (MI.isMetaInstruction() || !Seen.insert(&MI).second) + continue; + RematCost += SpillPlacer.getBlockFrequency(MI.getParent()->getNumber()) + .getFrequency(); + } + return BlockFrequency(RematCost); +} + /// 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; @@ -2524,6 +2567,135 @@ MCRegister RAGreedy::tryAssignCSRFirstTime( return PhysReg; } +// Like tryAssignCSRFirstTime before assign the unused CSR to VirtReg, try +// other choices. There are four results: +// 1. Pre-split VirtReg +// 2. Remat/Spill VirtReg +// 3. Evict rematerializable live ranges if that reg is not unused CSR. +// 4. Use the CSR for this VirtReg +// The goal is using the less cost register. +MCRegister RAGreedy::tryAssignCSRFirstTimeMinCost( + const LiveInterval &VirtReg, AllocationOrder &Order, MCRegister PhysReg, + uint8_t &CostPerUseLimit, SmallVectorImpl<Register> &NewVRegs) { + // Compute Remat cost. + std::optional<BlockFrequency> RematCost; + if (VirtReg.isSpillable() && + isRematerializableFromOriginal(VirtReg, *LIS, *VRM, *MRI, *TII)) + RematCost = calcRematCostAtUses(VirtReg, *MRI, *SpillPlacer); + + std::optional<BlockFrequency> SpillRematCost; + if (VirtReg.isSpillable()) { + SpillRematCost = calcSpillCost(VirtReg); + if (RematCost) + SpillRematCost = std::min(*SpillRematCost, *RematCost); + } + + LiveRangeStage Stage = ExtraInfo->getStage(VirtReg); + + if (Stage == RS_Spill && VirtReg.isSpillable()) { + // We choose spill or rematerialize over using the CSR for the first time if + // the spill cost is lower than CSRCost. + if (*SpillRematCost >= CSRCost) + return PhysReg; + + // We are going to spill or rematerialize, set CostPerUseLimit to 1 to make + // sure that we will not use a callee-saved register in tryEvict. + CostPerUseLimit = 1; + return MCRegister(); + } + + if (Stage < RS_Split) { + SA->analyze(&VirtReg); + // A pre-split must cost less than CSRCost. + // CSRCost is the cost for place the CSR save/restore. And it be set by + // target. + BlockFrequency SplitCost = CSRCost; + unsigned NumCands = 0; + unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, SplitCost, + NumCands, true /*IgnoreCSR*/); + + bool SpillRematCostsLess = SpillRematCost && *SpillRematCost < SplitCost; + if (BestCand != NoCand && !SpillRematCostsLess) { + doRegionSplit(VirtReg, BestCand, false /*HasCompact*/, NewVRegs); + return MCRegister(); + } + } + + bool SpillCostsLess = SpillRematCost && *SpillRematCost < CSRCost; + BlockFrequency EvictLimit = SpillCostsLess ? *SpillRematCost : CSRCost; + // Use Evict Reg + if (MCRegister Reg = + tryEvictRematForCSR(VirtReg, Order, NewVRegs, EvictLimit)) + return Reg; + + // Use CSR + if (!SpillCostsLess) + return PhysReg; + + // Use Spill/Remat + // We are going to spill, set CostPerUseLimit to 1 to make sure that + // we will not use a callee-saved register in tryEvict. + ExtraInfo->setStage(VirtReg, RS_Spill); + CostPerUseLimit = 1; + return MCRegister(); +} + +/// Return the cost of evicting and rematerializing all the live ranges that +/// interfere with \p VirtReg in \p PhysReg. +/// Return std::nullopt when +/// 1. has lower Cascade than \p Cascade. +/// 2. can't be spilled. +/// 3. can't be rematerialized. +std::optional<BlockFrequency> +RAGreedy::calcEvictRematCost(const LiveInterval &VirtReg, MCRegister PhysReg, + unsigned Cascade) const { + BlockFrequency Cost(0); + SmallPtrSet<const LiveInterval *, 4> Seen; + for (MCRegUnit Unit : TRI->regunits(PhysReg)) { + for (const LiveInterval *Intf : + Matrix->query(VirtReg, Unit).interferingVRegs()) { + if (!Seen.insert(Intf).second) + continue; + if (ExtraInfo->getCascade(Intf->reg()) >= Cascade || + !Intf->isSpillable() || + !isRematerializableFromOriginal(*Intf, *LIS, *VRM, *MRI, *TII)) + return std::nullopt; + Cost += calcRematCostAtUses(*Intf, *MRI, *SpillPlacer); + } + } + return Cost; +} + +/// Before \p VirtReg uses a CSR for the first time, look for a register that +/// is not an unused CSR and that only rematerializable live ranges occupy. +/// If rematerializing them costs less than \p MaxCost, evict them and +/// return the register. +MCRegister RAGreedy::tryEvictRematForCSR(const LiveInterval &VirtReg, + AllocationOrder &Order, + SmallVectorImpl<Register> &NewVRegs, + BlockFrequency MaxCost) { + unsigned Cascade = ExtraInfo->getCascadeOrCurrentNext(VirtReg.reg()); + MCRegister BestReg; + BlockFrequency BestCost = MaxCost; + for (MCRegister PhysReg : Order.getOrder()) { + if (EvictAdvisor->getUnusedCalleeSavedReg(VirtReg, PhysReg) || + Matrix->checkInterference(VirtReg, PhysReg) != + LiveRegMatrix::IK_VirtReg) + continue; + std::optional<BlockFrequency> Cost = + calcEvictRematCost(VirtReg, PhysReg, Cascade); + if (Cost && *Cost < BestCost) { + BestCost = *Cost; + BestReg = PhysReg; + } + } + if (!BestReg) + return MCRegister(); + + evictInterference(VirtReg, BestReg, NewVRegs); + return BestReg; +} + void RAGreedy::aboutToRemoveInterval(const LiveInterval &LI) { // Do not keep invalid information around. SetOfBrokenHints.remove(&LI); @@ -2791,8 +2963,12 @@ MCRegister RAGreedy::selectOrSplitImpl(const LiveInterval &VirtReg, if (CSRCost.getFrequency() && EvictAdvisor->getUnusedCalleeSavedReg(VirtReg, PhysReg) && NewVRegs.empty()) { - MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg, - CostPerUseLimit, NewVRegs); + MCRegister CSRReg = + TRI->enableCSRFirstTimeMinCost(*MF) + ? tryAssignCSRFirstTimeMinCost(VirtReg, Order, PhysReg, + CostPerUseLimit, NewVRegs) + : tryAssignCSRFirstTime(VirtReg, Order, PhysReg, CostPerUseLimit, + NewVRegs); if (CSRReg || !NewVRegs.empty()) // Return now if we decide to use a CSR or create new vregs due to // pre-splitting. diff --git a/llvm/lib/CodeGen/RegAllocGreedy.h b/llvm/lib/CodeGen/RegAllocGreedy.h index 138da362a1e76f..c9c1d68f623c00 100644 --- a/llvm/lib/CodeGen/RegAllocGreedy.h +++ b/llvm/lib/CodeGen/RegAllocGreedy.h @@ -365,6 +365,21 @@ class LLVM_LIBRARY_VISIBILITY RAGreedy : public RegAllocBase, /// rematerialization is not possible. BlockFrequency calcRematCost(const LiveInterval &VirtReg, AllocationOrder &Order) const; + /// Like tryAssignCSRFirstTime, but take the choice with the lowest cost of: + /// a pre-split, spilling or rematerializing VirtReg, evicting + /// rematerializable live ranges, and the first use of the CSR. + MCRegister tryAssignCSRFirstTimeMinCost(const LiveInterval &VirtReg, + AllocationOrder &Order, + MCRegister PhysReg, + uint8_t &CostPerUseLimit, + SmallVectorImpl<Register> &NewVRegs); + std::optional<BlockFrequency> + calcEvictRematCost(const LiveInterval &VirtReg, MCRegister PhysReg, + unsigned Cascade) const; + MCRegister tryEvictRematForCSR(const LiveInterval &VirtReg, + AllocationOrder &Order, + SmallVectorImpl<Register> &NewVRegs, + BlockFrequency MaxCost); BlockFrequency calcSpillCost(const LiveInterval &LI); void initializeCSRCost(); MCRegister tryBlockSplit(const LiveInterval &, AllocationOrder &, >From 5ad4b79516741038b9a1a15eb97157edd56fd425 Mon Sep 17 00:00:00 2001 From: Piyou Chen <[email protected]> Date: Sun, 8 Nov 2026 18:07:25 -0800 Subject: [PATCH 2/2] !fixup fix format --- llvm/lib/CodeGen/RegAllocGreedy.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/llvm/lib/CodeGen/RegAllocGreedy.h b/llvm/lib/CodeGen/RegAllocGreedy.h index c9c1d68f623c00..43353439423206 100644 --- a/llvm/lib/CodeGen/RegAllocGreedy.h +++ b/llvm/lib/CodeGen/RegAllocGreedy.h @@ -373,9 +373,9 @@ class LLVM_LIBRARY_VISIBILITY RAGreedy : public RegAllocBase, MCRegister PhysReg, uint8_t &CostPerUseLimit, SmallVectorImpl<Register> &NewVRegs); - std::optional<BlockFrequency> - calcEvictRematCost(const LiveInterval &VirtReg, MCRegister PhysReg, - unsigned Cascade) const; + std::optional<BlockFrequency> calcEvictRematCost(const LiveInterval &VirtReg, + MCRegister PhysReg, + unsigned Cascade) const; MCRegister tryEvictRematForCSR(const LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<Register> &NewVRegs, _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
