Author: Jan Korous Date: 2025-12-19T16:49:23-08:00 New Revision: 1a4596c1d7cc0045c1616643b02a56b39f173865
URL: https://github.com/llvm/llvm-project/commit/1a4596c1d7cc0045c1616643b02a56b39f173865 DIFF: https://github.com/llvm/llvm-project/commit/1a4596c1d7cc0045c1616643b02a56b39f173865.diff LOG: [clang][ssaf] Add EntityId and EntityIdTable for efficient entity handling (#171660) Introduce EntityId and EntityIdTable to provide efficient, lightweight handles for working with EntityNames in the Scalable Static Analysis Framework (SSAF). Introduces two key components: - EntityId: Lightweight opaque handle representing an entity in an EntityIdTable - EntityIdTable: Entity name interning table that maps unique EntityNames to EntityIds The interning table ensures each EntityName maps to exactly one EntityId, providing fast equality comparisons and lookups. EntityIds are index-based and remain stable for the lifetime of their table. This enables efficient entity tracking and comparison operations needed for TU summary extraction and serialization. --------- Co-authored-by: Yitzhak Mandelbaum <[email protected]> Added: clang/include/clang/Analysis/Scalable/Model/EntityId.h clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp clang/unittests/Analysis/Scalable/EntityIdTest.cpp Modified: clang/lib/Analysis/Scalable/CMakeLists.txt clang/unittests/Analysis/Scalable/CMakeLists.txt Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/Scalable/Model/EntityId.h b/clang/include/clang/Analysis/Scalable/Model/EntityId.h new file mode 100644 index 0000000000000..6fa059445d853 --- /dev/null +++ b/clang/include/clang/Analysis/Scalable/Model/EntityId.h @@ -0,0 +1,47 @@ +//===- EntityId.h -----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the EntityId class, which provides a lightweight opaque +// handle to entities in an EntityIdTable. EntityIds are index-based for +// efficient comparison and lookup. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITY_ID_H +#define LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITY_ID_H + +#include <cstddef> + +namespace clang::ssaf { + +class EntityIdTable; + +/// Lightweight opaque handle representing an entity in an EntityIdTable. +/// +/// EntityIds are created by EntityIdTable. Equality and ordering comparisons +/// are well-defined for EntityIds created by the same EntityIdTable. +/// +/// \see EntityIdTable +class EntityId { + friend class EntityIdTable; + + size_t Index; + + explicit EntityId(size_t Index) : Index(Index) {} + + EntityId() = delete; + +public: + bool operator==(const EntityId &Other) const { return Index == Other.Index; } + bool operator<(const EntityId &Other) const { return Index < Other.Index; } + bool operator!=(const EntityId &Other) const { return !(*this == Other); } +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITY_ID_H diff --git a/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h new file mode 100644 index 0000000000000..cf4bb83efddd0 --- /dev/null +++ b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h @@ -0,0 +1,50 @@ +//===- EntityIdTable.h ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITY_ID_TABLE_H +#define LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITY_ID_TABLE_H + +#include "clang/Analysis/Scalable/Model/EntityId.h" +#include "clang/Analysis/Scalable/Model/EntityName.h" +#include <functional> +#include <map> + +namespace clang::ssaf { + +/// Manages entity name interning and provides efficient EntityId handles. +/// +/// The table maps each unique EntityName to exactly one EntityId. +/// Entities are never removed. +class EntityIdTable { + std::map<EntityName, EntityId> Entities; + +public: + EntityIdTable() = default; + + /// Creates or retrieves an EntityId for the given EntityName. + /// + /// If the entity already exists in the table, returns its existing Id. + /// Otherwise, creates and returns a new Id. This operation is idempotent. + EntityId getId(const EntityName &Name); + + /// Returns true if an entity with the given name exists in the table. + bool contains(const EntityName &Name) const; + + /// Invokes the callback for each entity in the table. + /// + /// Iteration order is unspecified. + void forEach( + llvm::function_ref<void(const EntityName &, EntityId)> Callback) const; + + /// Returns the number of unique entities in the table. + size_t count() const { return Entities.size(); } +}; + +} // namespace clang::ssaf + +#endif // LLVM_CLANG_ANALYSIS_SCALABLE_MODEL_ENTITY_ID_TABLE_H diff --git a/clang/lib/Analysis/Scalable/CMakeLists.txt b/clang/lib/Analysis/Scalable/CMakeLists.txt index ea4693f102cb2..146c5c1ddcf80 100644 --- a/clang/lib/Analysis/Scalable/CMakeLists.txt +++ b/clang/lib/Analysis/Scalable/CMakeLists.txt @@ -5,6 +5,7 @@ set(LLVM_LINK_COMPONENTS add_clang_library(clangAnalysisScalable ASTEntityMapping.cpp Model/BuildNamespace.cpp + Model/EntityIdTable.cpp Model/EntityName.cpp LINK_LIBS diff --git a/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp new file mode 100644 index 0000000000000..134ead3f2881c --- /dev/null +++ b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp @@ -0,0 +1,31 @@ +//===- EntityIdTable.cpp ----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Scalable/Model/EntityIdTable.h" +#include <cassert> + +namespace clang::ssaf { + +EntityId EntityIdTable::getId(const EntityName &Name) { + EntityId Id(Entities.size()); + const auto Res = Entities.try_emplace(Name, Id); + return Res.first->second; +} + +bool EntityIdTable::contains(const EntityName &Name) const { + return Entities.find(Name) != Entities.end(); +} + +void EntityIdTable::forEach( + llvm::function_ref<void(const EntityName &, EntityId)> Callback) const { + for (const auto &NameIdPair : Entities) { + Callback(NameIdPair.first, NameIdPair.second); + } +} + +} // namespace clang::ssaf diff --git a/clang/unittests/Analysis/Scalable/CMakeLists.txt b/clang/unittests/Analysis/Scalable/CMakeLists.txt index a4c03b278d7fa..8b7f41d458b80 100644 --- a/clang/unittests/Analysis/Scalable/CMakeLists.txt +++ b/clang/unittests/Analysis/Scalable/CMakeLists.txt @@ -1,6 +1,8 @@ add_distinct_clang_unittest(ClangScalableAnalysisTests ASTEntityMappingTest.cpp BuildNamespaceTest.cpp + EntityIdTest.cpp + EntityIdTableTest.cpp EntityNameTest.cpp SummaryNameTest.cpp diff --git a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp new file mode 100644 index 0000000000000..922b121849236 --- /dev/null +++ b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp @@ -0,0 +1,142 @@ +//===- unittests/Analysis/Scalable/EntityIdTableTest.cpp -----------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Scalable/Model/EntityIdTable.h" +#include "clang/Analysis/Scalable/Model/BuildNamespace.h" +#include "clang/Analysis/Scalable/Model/EntityId.h" +#include "clang/Analysis/Scalable/Model/EntityName.h" +#include "gtest/gtest.h" + +namespace clang { +namespace ssaf { +namespace { + +TEST(EntityIdTableTest, CreateNewEntity) { + EntityIdTable Table; + + EntityName Entity("c:@F@foo", "", {}); + Table.getId(Entity); + + EXPECT_TRUE(Table.contains(Entity)); +} + +TEST(EntityIdTableTest, Idempotency) { + EntityIdTable Table; + + EntityName Entity("c:@F@foo", "", {}); + EntityName EntityCopy = Entity; + + EntityId Id1 = Table.getId(Entity); + EntityId Id2 = Table.getId(Entity); + EntityId Id3 = Table.getId(EntityCopy); + + EXPECT_EQ(Id1, Id2); + EXPECT_EQ(Id2, Id3); + EXPECT_EQ(Id1, Id3); +} + +TEST(EntityIdTableTest, ExistsTrue) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@V@bar", "", {}); + + Table.getId(Entity1); + Table.getId(Entity2); + + EXPECT_TRUE(Table.contains(Entity1)); + EXPECT_TRUE(Table.contains(Entity2)); +} + +TEST(EntityIdTableTest, ExistsFalse) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@F@bar", "", {}); + + Table.getId(Entity1); + + EXPECT_TRUE(Table.contains(Entity1)); + EXPECT_FALSE(Table.contains(Entity2)); +} + +TEST(EntityIdTableTest, MultipleEntities) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@F@bar", "", {}); + EntityName Entity3("c:@V@baz", "", {}); + + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + EntityId Id3 = Table.getId(Entity3); + + EXPECT_NE(Id1, Id2); + EXPECT_NE(Id1, Id3); + EXPECT_NE(Id2, Id3); +} + +TEST(EntityIdTableTest, WithBuildNamespace) { + EntityIdTable Table; + + NestedBuildNamespace NS = NestedBuildNamespace::makeCompilationUnit("test.o"); + + EntityName Entity1("c:@F@foo", "", NS); + EntityName Entity2("c:@F@foo", "", + NestedBuildNamespace::makeCompilationUnit("other.o")); + + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + + EXPECT_NE(Id1, Id2); +} + +TEST(EntityIdTableTest, ForEachEmptyTable) { + EntityIdTable Table; + + int CallbackCount = 0; + Table.forEach( + [&CallbackCount](const EntityName &, EntityId) { CallbackCount++; }); + + EXPECT_EQ(CallbackCount, 0); +} + +TEST(EntityIdTableTest, ForEachMultipleEntities) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@F@bar", "", {}); + EntityName Entity3("c:@V@baz", "", {}); + + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + EntityId Id3 = Table.getId(Entity3); + + std::set<EntityId> VisitedIds; + std::set<EntityName> VisitedNames; + + Table.forEach([&](const EntityName &Name, EntityId Id) { + VisitedIds.insert(Id); + VisitedNames.insert(Name); + }); + + EXPECT_EQ(VisitedIds.size(), 3u); + EXPECT_EQ(VisitedNames.size(), 3u); + + EXPECT_TRUE(VisitedIds.count(Id1)); + EXPECT_TRUE(VisitedIds.count(Id2)); + EXPECT_TRUE(VisitedIds.count(Id3)); + + EXPECT_TRUE(VisitedNames.count(Entity1)); + EXPECT_TRUE(VisitedNames.count(Entity2)); + EXPECT_TRUE(VisitedNames.count(Entity3)); +} + +} // namespace +} // namespace ssaf +} // namespace clang diff --git a/clang/unittests/Analysis/Scalable/EntityIdTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp new file mode 100644 index 0000000000000..712c03a86ee80 --- /dev/null +++ b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp @@ -0,0 +1,65 @@ +//===- unittests/Analysis/Scalable/EntityIdTest.cpp ----------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Scalable/Model/EntityId.h" +#include "clang/Analysis/Scalable/Model/EntityIdTable.h" +#include "clang/Analysis/Scalable/Model/EntityName.h" +#include "gtest/gtest.h" + +namespace clang::ssaf { +namespace { + +TEST(EntityIdTest, Equality) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@F@bar", "", {}); + + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + EntityId Id1Copy = Table.getId(Entity1); + + EXPECT_EQ(Id1, Id1Copy); + EXPECT_FALSE(Id1 != Id1Copy); + EXPECT_FALSE(Id1 < Id1Copy); + EXPECT_FALSE(Id1Copy < Id1); + + EXPECT_NE(Id1, Id2); + EXPECT_FALSE(Id1 == Id2); + EXPECT_TRUE(Id1 < Id2 || Id2 < Id1); +} + +TEST(EntityIdTest, LessThan) { + EntityIdTable Table; + + EntityName Entity1("c:@F@aaa", "", {}); + EntityName Entity2("c:@F@bbb", "", {}); + + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + + EXPECT_TRUE(Id1 < Id2 || Id2 < Id1); +} + +TEST(EntityIdTest, Transitivity) { + EntityIdTable Table; + + EntityName Entity1("c:@F@xxx", "", {}); + EntityName Entity2("c:@F@yyy", "", {}); + EntityName Entity3("c:@F@zzz", "", {}); + + EntityId Ids[3] = {Table.getId(Entity1), Table.getId(Entity2), + Table.getId(Entity3)}; + + std::sort(Ids, Ids + 3); + + EXPECT_TRUE(Ids[0] < Ids[1] && Ids[1] < Ids[2]); +} + +} // namespace +} // namespace clang::ssaf _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
