https://github.com/felix314159 created https://github.com/llvm/llvm-project/pull/219441
`CallDescriptionMap::lookup()` and `lookupAsWritten()` currently test every description linearly, even though ordinary callees can only match descriptions with the same unqualified name. This makes large checker maps repeat the full matching logic for every unrelated call. Build an optional name index for maps with at least eight descriptions and use it for ordinary identifier callees. Keep the existing linear path for builtins, fortified `_...` names, constructors, operators, and unresolved calls, where matching may be fuzzy or lack a simple identifier. The regression tests exercise both the indexed and fallback paths. I tested this out on a Release+assertions build, analyzing 200,000 unrelated calls with the default checkers improved from `2.68 s` to `2.17 s` mean wall time across ten alternating, CPU-pinned pairs, a 19.2% reduction. The full Clang unit suite passed and `check-clang-analysis` also passed. >From 9deca0a3d9b145006821a83dac00a1816453f405 Mon Sep 17 00:00:00 2001 From: felix h <[email protected]> Date: Fri, 28 Aug 2026 13:02:49 +0200 Subject: [PATCH] [analyzer] Speed up CallDescriptionMap lookups --- .../Core/PathSensitive/CallDescription.h | 87 ++++++++++++++----- .../StaticAnalyzer/CallDescriptionTest.cpp | 36 +++++++- 2 files changed, 100 insertions(+), 23 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h index 3c242898ef6cd..f701187674ad4 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h @@ -17,7 +17,10 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringMap.h" #include "llvm/Support/Compiler.h" +#include <memory> #include <optional> #include <vector> @@ -194,20 +197,69 @@ class CallDescription { template <typename T> class CallDescriptionMap { friend class CallDescriptionSet; - // Some call descriptions aren't easily hashable (eg., the ones with qualified - // names in which some sections are omitted), so let's put them - // in a simple vector and use linear lookup. - // TODO: Implement an actual map for fast lookup for "hashable" call - // descriptions (eg., the ones for C functions that just match the name). + // Some call descriptions aren't easily hashable (eg., the ones with + // qualified names in which some sections are omitted), so keep the complete + // descriptions in a vector. std::vector<std::pair<CallDescription, T>> LinearMap; + // Most callees have an ordinary identifier and can only match descriptions + // with that exact unqualified name. Index sufficiently large maps to avoid + // calling the full matcher for every differently named entry. Keep this + // optional so that the common small maps don't pay for the index. + using NameIndexTy = llvm::StringMap<llvm::SmallVector<unsigned, 1>>; + std::unique_ptr<NameIndexTy> NameIndex; + + static constexpr unsigned MinNameIndexSize = 8; + + void buildNameIndex() { + if (LinearMap.size() < MinNameIndexSize) + return; + + NameIndex = std::make_unique<NameIndexTy>(); + for (unsigned I = 0, E = LinearMap.size(); I != E; ++I) + (*NameIndex)[LinearMap[I].first.getFunctionName()].push_back(I); + } + + template <typename Matcher> + [[nodiscard]] const T *lookupImpl(const FunctionDecl *FD, + Matcher Matches) const { + if (NameIndex && FD && FD->getBuiltinID() == 0 && + FD->getDeclName().isIdentifier()) { + StringRef Name = FD->getName(); + + // Builtins and names beginning with "__" may be accepted by the fuzzy + // C-library and fortified-function matching rules. Special declaration + // names such as constructors and operators have no identifier name. + // Preserve the complete linear matcher for all of these cases. + if (!Name.empty() && !Name.starts_with("__")) { + auto It = NameIndex->find(Name); + if (It == NameIndex->end()) + return nullptr; + + for (unsigned I : It->second) + if (Matches(LinearMap[I].first)) + return &LinearMap[I].second; + return nullptr; + } + } + + for (const std::pair<CallDescription, T> &I : LinearMap) + if (Matches(I.first)) + return &I.second; + return nullptr; + } + public: CallDescriptionMap( std::initializer_list<std::pair<CallDescription, T>> &&List) - : LinearMap(List) {} + : LinearMap(List) { + buildNameIndex(); + } template <typename InputIt> - CallDescriptionMap(InputIt First, InputIt Last) : LinearMap(First, Last) {} + CallDescriptionMap(InputIt First, InputIt Last) : LinearMap(First, Last) { + buildNameIndex(); + } ~CallDescriptionMap() = default; @@ -220,13 +272,9 @@ template <typename T> class CallDescriptionMap { CallDescriptionMap &operator=(CallDescriptionMap &&) = default; [[nodiscard]] const T *lookup(const CallEvent &Call) const { - // Slow path: linear lookup. - // TODO: Implement some sort of fast path. - for (const std::pair<CallDescription, T> &I : LinearMap) - if (I.first.matches(Call)) - return &I.second; - - return nullptr; + const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); + return lookupImpl( + FD, [&](const CallDescription &CD) { return CD.matches(Call); }); } /// When available, always prefer lookup with a CallEvent! This function @@ -242,13 +290,10 @@ template <typename T> class CallDescriptionMap { /// CallEvent::getNumArgs), the called function if it was called through a /// function pointer, and other information not available syntactically. [[nodiscard]] const T *lookupAsWritten(const CallExpr &Call) const { - // Slow path: linear lookup. - // TODO: Implement some sort of fast path. - for (const std::pair<CallDescription, T> &I : LinearMap) - if (I.first.matchesAsWritten(Call)) - return &I.second; - - return nullptr; + const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getCalleeDecl()); + return lookupImpl(FD, [&](const CallDescription &CD) { + return CD.matchesAsWritten(Call); + }); } }; diff --git a/clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp b/clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp index bdc0699c5cc67..060c725b54be6 100644 --- a/clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp +++ b/clang/unittests/StaticAnalyzer/CallDescriptionTest.cpp @@ -142,6 +142,21 @@ TEST(CallDescription, SimpleNameMatching) { "void foo(); void bar() { foo(); }")); } +TEST(CallDescription, IndexedNameMatching) { + EXPECT_TRUE(tooling::runToolOnCode( + std::unique_ptr<FrontendAction>(new CallDescriptionAction<>({ + {{CDM::SimpleFunc, {"not_foo_0"}}, false}, + {{CDM::SimpleFunc, {"not_foo_1"}}, false}, + {{CDM::SimpleFunc, {"not_foo_2"}}, false}, + {{CDM::SimpleFunc, {"not_foo_3"}}, false}, + {{CDM::SimpleFunc, {"not_foo_4"}}, false}, + {{CDM::SimpleFunc, {"not_foo_5"}}, false}, + {{CDM::SimpleFunc, {"not_foo_6"}}, false}, + {{CDM::SimpleFunc, {"foo"}}, true}, + })), + "void foo(); void bar() { foo(); }")); +} + TEST(CallDescription, RequiredArguments) { EXPECT_TRUE(tooling::runToolOnCode( std::unique_ptr<FrontendAction>(new CallDescriptionAction<>({ @@ -200,6 +215,13 @@ TEST(CallDescription, MatchConstructor) { EXPECT_TRUE(tooling::runToolOnCode( std::unique_ptr<FrontendAction>( new CallDescriptionAction<CXXConstructExpr>({ + {{CDM::CXXMethod, {"not_basic_string_0"}}, false}, + {{CDM::CXXMethod, {"not_basic_string_1"}}, false}, + {{CDM::CXXMethod, {"not_basic_string_2"}}, false}, + {{CDM::CXXMethod, {"not_basic_string_3"}}, false}, + {{CDM::CXXMethod, {"not_basic_string_4"}}, false}, + {{CDM::CXXMethod, {"not_basic_string_5"}}, false}, + {{CDM::CXXMethod, {"not_basic_string_6"}}, false}, {{CDM::CXXMethod, {"std", "basic_string", "basic_string"}, 2, 2}, true}, })), @@ -486,7 +508,12 @@ TEST(CallDescription, MatchBuiltins) { SCOPED_TRACE("hardened variants of functions"); EXPECT_TRUE(tooling::runToolOnCode( std::unique_ptr<FrontendAction>(new CallDescriptionAction<>( - {{{CDM::Unspecified, {"memset"}, 3}, false}, + {{{CDM::Unspecified, {"not_memset_0"}}, false}, + {{CDM::Unspecified, {"not_memset_1"}}, false}, + {{CDM::Unspecified, {"not_memset_2"}}, false}, + {{CDM::Unspecified, {"not_memset_3"}}, false}, + {{CDM::Unspecified, {"not_memset_4"}}, false}, + {{CDM::Unspecified, {"memset"}, 3}, false}, {{CDM::CLibrary, {"memset"}, 3}, false}, {{CDM::CLibraryMaybeHardened, {"memset"}, 3}, true}})), "void foo() {" @@ -590,7 +617,12 @@ TEST(CallDescription, MatchBuiltins) { class CallDescChecker : public Checker<check::PreCall, check::PreStmt<CallExpr>> { - CallDescriptionSet Set = {{CDM::SimpleFunc, {"bar"}, 0}}; + CallDescriptionSet Set = { + {CDM::SimpleFunc, {"not_bar_0"}, 0}, {CDM::SimpleFunc, {"not_bar_1"}, 0}, + {CDM::SimpleFunc, {"not_bar_2"}, 0}, {CDM::SimpleFunc, {"not_bar_3"}, 0}, + {CDM::SimpleFunc, {"not_bar_4"}, 0}, {CDM::SimpleFunc, {"not_bar_5"}, 0}, + {CDM::SimpleFunc, {"not_bar_6"}, 0}, {CDM::SimpleFunc, {"bar"}, 0}, + }; public: void checkPreCall(const CallEvent &Call, CheckerContext &C) const { _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
