https://github.com/localspook updated https://github.com/llvm/llvm-project/pull/187630
>From 06649a370d5087c2dd0757d9a123f2554ddc9c43 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 | 142 +----------------- 1 file changed, 6 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..00b48ca59553c 100644 --- a/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp +++ b/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp @@ -16,157 +16,27 @@ 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
