================
@@ -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(
----------------
nicovank wrote:
`SmallPtrSet` already has/had the same optimization of using linear search in
user-defined small cases, and hash-based search in cases beyond the defined
small size. So really this was only saving the array copy.
https://github.com/llvm/llvm-project/pull/187630
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
