https://github.com/arsenm updated https://github.com/llvm/llvm-project/pull/234791
>From 3df0f7e33b89c022e6ce773d19e66760455cebd3 Mon Sep 17 00:00:00 2001 From: Matt Arsenault <[email protected]> Date: Thu, 22 Oct 2026 10:20:39 -0700 Subject: [PATCH] TableGen: Avoid binary searches for sub-registers of similar registers inferMatchingSuperRegClass looks up the sub-register at one index for every member of a register class. Members of a class almost always have the same sub-register indices, so the index is usually at the same position in each member's sorted array. Pass the position found in the previous member as a hint, and only binary search if it doesn't match. AMDGPU tablegen runs that build the register bank: Gigainstructions Gigacycles CPU seconds Before 720 442 138 After 701 (-2.7%) 437 (-1.2%) 137 (-1.2%) Co-authored-by: Claude Opus 5.5 <[email protected]> --- llvm/utils/TableGen/Common/CodeGenRegisters.cpp | 11 ++++++++--- llvm/utils/TableGen/Common/CodeGenRegisters.h | 8 ++++++-- 2 files changed, 14 insertions(+), 5 deletions(-) diff --git a/llvm/utils/TableGen/Common/CodeGenRegisters.cpp b/llvm/utils/TableGen/Common/CodeGenRegisters.cpp index 6f42766161aa9..0af3a5a3c7d3a 100644 --- a/llvm/utils/TableGen/Common/CodeGenRegisters.cpp +++ b/llvm/utils/TableGen/Common/CodeGenRegisters.cpp @@ -551,15 +551,19 @@ void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) { } } -CodeGenRegister * -CodeGenRegister::getSubReg(const CodeGenSubRegIndex *Idx) const { +CodeGenRegister *CodeGenRegister::getSubReg(const CodeGenSubRegIndex *Idx, + unsigned &Hint) const { assert(SuperRegsComplete && "Must precompute super-registers"); + if (Hint < FinalSubRegs.size() && FinalSubRegs[Hint].first == Idx) + return FinalSubRegs[Hint].second; + auto It = llvm::lower_bound(FinalSubRegs, Idx->EnumValue, [](const auto &Entry, unsigned EnumValue) { return Entry.first->EnumValue < EnumValue; }); if (It == FinalSubRegs.end() || It->first != Idx) return nullptr; + Hint = It - FinalSubRegs.begin(); return It->second; } @@ -2616,10 +2620,11 @@ void CodeGenRegBank::inferMatchingSuperRegClass( // that the list may contain entries with the same Sub but different Supers. SubRegs.clear(); TopoSigs.reset(); + unsigned Hint = 0; for (const CodeGenRegister *Super : RC->getMembers()) { if (Super->Artificial) continue; - const CodeGenRegister *Sub = Super->getSubReg(SubIdx); + const CodeGenRegister *Sub = Super->getSubReg(SubIdx, Hint); assert(Sub && "Missing sub-register"); SubRegs.push_back(Sub); TopoSigs.set(Sub->getTopoSig()); diff --git a/llvm/utils/TableGen/Common/CodeGenRegisters.h b/llvm/utils/TableGen/Common/CodeGenRegisters.h index 2c4172e5ec04c..6f30e517c758a 100644 --- a/llvm/utils/TableGen/Common/CodeGenRegisters.h +++ b/llvm/utils/TableGen/Common/CodeGenRegisters.h @@ -265,8 +265,12 @@ class CodeGenRegister { } // Return the sub-register at Idx, or NULL if there is none. Only valid after - // computeSuperRegs(). - CodeGenRegister *getSubReg(const CodeGenSubRegIndex *Idx) const; + // computeSuperRegs(). Check position Hint first, and update it to the + // position of Idx. Registers with the same sub-register indices store Idx at + // the same position, so this avoids the search when looking up the same + // index in many similar registers. + CodeGenRegister *getSubReg(const CodeGenSubRegIndex *Idx, + unsigned &Hint) const; using SuperRegList = std::vector<const CodeGenRegister *>; _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
