llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-tools-extra @llvm/pr-subscribers-clang-tidy Author: Victor Chernyakin (localspook) <details> <summary>Changes</summary> 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. That's 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 a false optimization. --- Full diff: https://github.com/llvm/llvm-project/pull/187630.diff 1 Files Affected: - (modified) clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp (+6-136) ``````````diff 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. `````````` </details> https://github.com/llvm/llvm-project/pull/187630 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
