https://github.com/localspook created https://github.com/llvm/llvm-project/pull/187630
About half of this check's code is dedicated to implementing a pair of set containers with optimizations for when the element count is small. But the check only uses these containers while constructing the warning message. The code path when we've already determined we're going to warn is not generally a hot path in any check. Just to confirm, I ran the check over `clang/lib/Sema/Sema.cpp` and all its included headers before and after, and saw no performance difference. So, these containers seem like unnecessary complexity. >From 7971e36818eb424a8dce3405b98933e842846173 Mon Sep 17 00:00:00 2001 From: Victor Chernyakin <[email protected]> Date: Fri, 20 Mar 2026 03:30:37 +0000 Subject: [PATCH] [clang-tidy][NFC] Remove optimized container implementations in `misc-no-recursion` --- .../clang-tidy/misc/NoRecursionCheck.cpp | 141 +----------------- 1 file changed, 5 insertions(+), 136 deletions(-) diff --git a/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp b/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp index e1c0612336df5..eb189a6979083 100644 --- a/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp +++ b/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp @@ -16,157 +16,26 @@ using namespace clang::ast_matchers; namespace clang::tidy::misc { -namespace { - -/// Much like SmallSet, with two differences: -/// 1. It can *only* be constructed from an ArrayRef<>. If the element count -/// is small, there is no copy and said storage *must* outlive us. -/// 2. it is immutable, the way it was constructed it will stay. -template <typename T, unsigned SmallSize> class ImmutableSmallSet { - ArrayRef<T> Vector; - llvm::DenseSet<T> Set; - - static_assert(SmallSize <= 32, "N should be small"); - - bool isSmall() const { return Set.empty(); } - -public: - using size_type = size_t; - - ImmutableSmallSet() = delete; - ImmutableSmallSet(const ImmutableSmallSet &) = delete; - ImmutableSmallSet(ImmutableSmallSet &&) = delete; - T &operator=(const ImmutableSmallSet &) = delete; - T &operator=(ImmutableSmallSet &&) = delete; - - // WARNING: Storage *must* outlive us if we decide that the size is small. - ImmutableSmallSet(ArrayRef<T> Storage) { - // Is size small-enough to just keep using the existing storage? - if (Storage.size() <= SmallSize) { - Vector = Storage; - return; - } - - // We've decided that it isn't performant to keep using vector. - // Let's migrate the data into Set. - Set.reserve(Storage.size()); - Set.insert_range(Storage); - } - - /// count - Return 1 if the element is in the set, 0 otherwise. - size_type count(const T &V) const { - if (isSmall()) { - // Since the collection is small, just do a linear search. - return llvm::is_contained(Vector, V) ? 1 : 0; - } - - return Set.count(V); - } -}; - -/// Much like SmallSetVector, but with one difference: -/// when the size is \p SmallSize or less, when checking whether an element is -/// already in the set or not, we perform linear search over the vector, -/// but if the size is larger than \p SmallSize, we look in set. -/// FIXME: upstream this into SetVector/SmallSetVector itself. -template <typename T, unsigned SmallSize> class SmartSmallSetVector { -public: - using size_type = size_t; - -private: - SmallVector<T, SmallSize> Vector; - llvm::DenseSet<T> Set; - - static_assert(SmallSize <= 32, "N should be small"); - - // Are we still using Vector for uniqness tracking? - bool isSmall() const { return Set.empty(); } - - // Will one more entry cause Vector to switch away from small-size storage? - bool entiretyOfVectorSmallSizeIsOccupied() const { - assert(isSmall() && Vector.size() <= SmallSize && - "Shouldn't ask if we have already [should have] migrated into Set."); - return Vector.size() == SmallSize; - } - - void populateSet() { - assert(Set.empty() && "Should not have already utilized the Set."); - // Magical growth factor prediction - to how many elements do we expect to - // sanely grow after switching away from small-size storage? - const size_t NewMaxElts = 4 * Vector.size(); - Vector.reserve(NewMaxElts); - Set.reserve(NewMaxElts); - Set.insert_range(Vector); - } - - /// count - Return 1 if the element is in the set, 0 otherwise. - size_type count(const T &V) const { - if (isSmall()) { - // Since the collection is small, just do a linear search. - return llvm::is_contained(Vector, V) ? 1 : 0; - } - // Look-up in the Set. - return Set.count(V); - } - - bool setInsert(const T &V) { - if (count(V) != 0) - return false; // Already exists. - // Does not exist, Can/need to record it. - if (isSmall()) { // Are we still using Vector for uniqness tracking? - // Will one more entry fit within small-sized Vector? - if (!entiretyOfVectorSmallSizeIsOccupied()) - return true; // We'll insert into vector right afterwards anyway. - // Time to switch to Set. - populateSet(); - } - // Set time! - // Note that this must be after `populateSet()` might have been called. - const bool SetInsertionSucceeded = Set.insert(V).second; - (void)SetInsertionSucceeded; - assert(SetInsertionSucceeded && "We did check that no such value existed"); - return true; - } - -public: - /// Insert a new element into the SmartSmallSetVector. - /// \returns true if the element was inserted into the SmartSmallSetVector. - bool insert(const T &X) { - const bool Result = setInsert(X); - if (Result) - Vector.push_back(X); - return Result; - } - - /// Clear the SmartSmallSetVector and return the underlying vector. - decltype(Vector) takeVector() { - Set.clear(); - return std::move(Vector); - } -}; - -constexpr unsigned SmallCallStackSize = 16; -constexpr unsigned SmallSCCSize = 32; +static constexpr unsigned SmallCallStackSize = 16; +static constexpr unsigned SmallSCCSize = 32; using CallStackTy = SmallVector<CallGraphNode::CallRecord, SmallCallStackSize>; -} // namespace - // In given SCC, find *some* call stack that will be cyclic. // This will only find *one* such stack, it might not be the smallest one, // and there may be other loops. static CallStackTy pathfindSomeCycle(ArrayRef<CallGraphNode *> SCC) { // We'll need to be able to performantly look up whether some CallGraphNode // is in SCC or not, so cache all the SCC elements in a set. - const ImmutableSmallSet<CallGraphNode *, SmallSCCSize> SCCElts(SCC); + const llvm::SmallPtrSet<CallGraphNode *, SmallSCCSize> SCCElts(llvm::from_range, SCC); // Is node N part if the current SCC? auto NodeIsPartOfSCC = [&SCCElts](CallGraphNode *N) { - return SCCElts.count(N) != 0; + return SCCElts.contains(N); }; // Track the call stack that will cause a cycle. - SmartSmallSetVector<CallGraphNode::CallRecord, SmallCallStackSize> + llvm::SmallSetVector<CallGraphNode::CallRecord, SmallCallStackSize> CallStackSet; // Arbitrarily take the first element of SCC as entry point. _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
