https://github.com/adams381 created https://github.com/llvm/llvm-project/pull/195883
applyReplacements() previously called replaceAllSymbolUses() for each replacement, which walks the entire module every time — O(R × M) for R replacements and M operations. For C++ programs with heavy template instantiation (e.g., Eigen), this quadratic behavior dominated compile time. Replace the per-replacement module walk with a single SymbolUserMap built once (O(M)), then use replaceAllUsesWith() which scopes each replacement to only the actual user operations. The debug-only verifyPointerTypeArgs helper is also updated to reuse the map. Measured on Eigen's basicstuff.cpp (356 lines, heavy template instantiation): compile time dropped from 20m29s to 1m2s (20x speedup). CIR-to-classic ratio improved from 117x to 7.2x. Made with [Cursor](https://cursor.com) >From b94f1a257f8febf2c4f2a0f76b4ed7992a1ec67b Mon Sep 17 00:00:00 2001 From: Adam Smith <[email protected]> Date: Mon, 4 May 2026 09:08:41 -0700 Subject: [PATCH] [CIR] Use SymbolUserMap in applyReplacements to fix quadratic behavior MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit applyReplacements() previously called replaceAllSymbolUses() for each replacement, which walks the entire module every time — O(R × M) for R replacements and M operations. For C++ programs with heavy template instantiation (e.g., Eigen), this quadratic behavior dominated compile time. Replace the per-replacement module walk with a single SymbolUserMap built once (O(M)), then use replaceAllUsesWith() which scopes each replacement to only the actual user operations. The debug-only verifyPointerTypeArgs helper is also updated to reuse the map. Measured on Eigen's basicstuff.cpp: compile time dropped from 20m29s to 1m2s (20x speedup). CIR-to-classic ratio improved from 117x to 7.2x. Co-authored-by: Cursor <[email protected]> --- clang/lib/CIR/CodeGen/CIRGenModule.cpp | 39 ++++++++++++++------------ 1 file changed, 21 insertions(+), 18 deletions(-) diff --git a/clang/lib/CIR/CodeGen/CIRGenModule.cpp b/clang/lib/CIR/CodeGen/CIRGenModule.cpp index af8fd52bef017..db84967bd74a9 100644 --- a/clang/lib/CIR/CodeGen/CIRGenModule.cpp +++ b/clang/lib/CIR/CodeGen/CIRGenModule.cpp @@ -33,6 +33,7 @@ #include "clang/CIR/Dialect/IR/CIRTypes.h" #include "clang/CIR/Interfaces/CIROpInterfaces.h" #include "clang/CIR/MissingFeatures.h" +#include "mlir/IR/SymbolTable.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" @@ -1648,15 +1649,10 @@ void CIRGenModule::addReplacement(StringRef name, mlir::Operation *op) { } #ifndef NDEBUG -static bool verifyPointerTypeArgs(mlir::ModuleOp modOp, cir::FuncOp oldF, - cir::FuncOp newF) { - std::optional<mlir::SymbolTable::UseRange> optionalUseRange = - oldF.getSymbolUses(modOp); - if (!optionalUseRange) - return true; - - for (const mlir::SymbolTable::SymbolUse &u : *optionalUseRange) { - auto call = mlir::dyn_cast<cir::CallOp>(u.getUser()); +static bool verifyPointerTypeArgs(cir::FuncOp oldF, cir::FuncOp newF, + mlir::SymbolUserMap &userMap) { + for (mlir::Operation *user : userMap.getUsers(oldF)) { + auto call = mlir::dyn_cast<cir::CallOp>(user); if (!call) continue; @@ -1672,6 +1668,15 @@ static bool verifyPointerTypeArgs(mlir::ModuleOp modOp, cir::FuncOp oldF, #endif // NDEBUG void CIRGenModule::applyReplacements() { + if (replacements.empty()) + return; + + // Build a symbol user map once — this walks the module O(M) one time. + // Previously, each replaceAllSymbolUses call walked the entire module, + // giving O(R × M) quadratic behavior for R replacements. + mlir::SymbolTableCollection symbolTableCollection; + mlir::SymbolUserMap userMap(symbolTableCollection, theModule); + for (auto &i : replacements) { StringRef mangledName = i.first; mlir::Operation *replacement = i.second; @@ -1687,17 +1692,15 @@ void CIRGenModule::applyReplacements() { continue; } - assert(verifyPointerTypeArgs(theModule, oldF, newF) && + assert(verifyPointerTypeArgs(oldF, newF, userMap) && "call argument types do not match replacement function"); - // Replace old with new, but keep the old order. - if (oldF.replaceAllSymbolUses(newF.getSymNameAttr(), theModule).failed()) - llvm_unreachable("internal error, cannot RAUW symbol"); - if (newF) { - newF->moveBefore(oldF); - eraseGlobalSymbol(oldF); - oldF->erase(); - } + // Replace old with new, but keep the old order. Uses + // SymbolUserMap to touch only actual users, not the whole module. + userMap.replaceAllUsesWith(oldF, newF.getSymNameAttr()); + newF->moveBefore(oldF); + eraseGlobalSymbol(oldF); + oldF->erase(); } } _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
