https://github.com/jkorous-apple updated https://github.com/llvm/llvm-project/pull/171660
>From 5cfd50489b8295fc20bbf4eeef217be5c4addee0 Mon Sep 17 00:00:00 2001 From: Jan Korous <[email protected]> Date: Mon, 8 Dec 2025 16:14:32 -0800 Subject: [PATCH 1/6] [clang][ssaf] Add EntityId and EntityIdTable for efficient entity handling 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 whole-program analysis. --- .../clang/Analysis/Scalable/Model/EntityId.h | 49 +++++++++ .../Analysis/Scalable/Model/EntityIdTable.h | 54 ++++++++++ clang/lib/Analysis/Scalable/CMakeLists.txt | 1 + .../Analysis/Scalable/Model/EntityIdTable.cpp | 49 +++++++++ .../Analysis/Scalable/CMakeLists.txt | 2 + .../Analysis/Scalable/EntityIdTableTest.cpp | 99 +++++++++++++++++++ .../Analysis/Scalable/EntityIdTest.cpp | 58 +++++++++++ 7 files changed, 312 insertions(+) create mode 100644 clang/include/clang/Analysis/Scalable/Model/EntityId.h create mode 100644 clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h create mode 100644 clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp create mode 100644 clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp create mode 100644 clang/unittests/Analysis/Scalable/EntityIdTest.cpp 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..7640051699457 --- /dev/null +++ b/clang/include/clang/Analysis/Scalable/Model/EntityId.h @@ -0,0 +1,49 @@ +//===- 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 { +namespace 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 ssaf +} // namespace clang + +#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..9df19b36c395f --- /dev/null +++ b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h @@ -0,0 +1,54 @@ +//===- 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 <set> +#include <vector> + +namespace clang { +namespace ssaf { + +/// Manages entity name interning and provides efficient EntityId handles. +/// +/// The table maps each unique EntityName maps to exactly one EntityId. +/// Entities are never removed. +class EntityIdTable { + std::set<EntityName> Entities; + + std::vector<const EntityName*> IdToEntity; + +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 createEntityId(const EntityName& Name); + + /// Returns true if an entity with the given name exists in the table. + bool exists(const EntityName& Name) const; + + /// Invokes the callback for each entity in the table. + /// + /// Iteration order is unspecified. + void forEach(std::function<void(const EntityName&, EntityId)> Callback) const; + + /// Returns the number of unique entities in the table. + size_t count() const; +}; + +} // namespace ssaf +} // namespace clang + +#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..b47d8d512c01c --- /dev/null +++ b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp @@ -0,0 +1,49 @@ +//===- 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> +#include <algorithm> + +namespace clang { +namespace ssaf { + +EntityId EntityIdTable::createEntityId(const EntityName& Name) { + auto [It, Inserted] = Entities.insert(Name); + + if (Inserted) { + IdToEntity.push_back(&(*It)); + return EntityId(IdToEntity.size() - 1); + } + + const EntityName* EntityPtr = &(*It); + auto IdIt = std::find(IdToEntity.begin(), IdToEntity.end(), EntityPtr); + assert(IdIt != IdToEntity.end() && "Entity exists but has no ID"); + + size_t Index = std::distance(IdToEntity.begin(), IdIt); + return EntityId(Index); +} + +bool EntityIdTable::exists(const EntityName& Name) const { + return Entities.find(Name) != Entities.end(); +} + +void EntityIdTable::forEach(std::function<void(const EntityName&, EntityId)> Callback) const { + for (size_t Index = 0; Index < IdToEntity.size(); ++Index) { + EntityId EId(Index); + const EntityName& Name = *IdToEntity[Index]; + Callback(Name, EId); + } +} + +size_t EntityIdTable::count() const { + return IdToEntity.size(); +} + +} // namespace ssaf +} // namespace clang diff --git a/clang/unittests/Analysis/Scalable/CMakeLists.txt b/clang/unittests/Analysis/Scalable/CMakeLists.txt index e545e314b49ac..51126f6a00d7a 100644 --- a/clang/unittests/Analysis/Scalable/CMakeLists.txt +++ b/clang/unittests/Analysis/Scalable/CMakeLists.txt @@ -1,6 +1,8 @@ add_distinct_clang_unittest(ClangScalableAnalysisFrameworkTests ASTEntityMappingTest.cpp BuildNamespaceTest.cpp + EntityIdTest.cpp + EntityIdTableTest.cpp EntityNameTest.cpp CLANG_LIBS diff --git a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp new file mode 100644 index 0000000000000..396361efe7233 --- /dev/null +++ b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp @@ -0,0 +1,99 @@ +//===- 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/EntityId.h" +#include "clang/Analysis/Scalable/Model/EntityName.h" +#include "clang/Analysis/Scalable/Model/BuildNamespace.h" +#include "gtest/gtest.h" + +namespace clang { +namespace ssaf { +namespace { + +TEST(EntityIdTableTest, CreateNewEntity) { + EntityIdTable Table; + + EntityName Entity("c:@F@foo", "", {}); + Table.createEntityId(Entity); + + EXPECT_TRUE(Table.exists(Entity)); +} + +TEST(EntityIdTableTest, Idempotency) { + EntityIdTable Table; + + EntityName Entity("c:@F@foo", "", {}); + + EntityId Id1 = Table.createEntityId(Entity); + EntityId Id2 = Table.createEntityId(Entity); + EntityId Id3 = Table.createEntityId(Entity); + + 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.createEntityId(Entity1); + Table.createEntityId(Entity2); + + EXPECT_TRUE(Table.exists(Entity1)); + EXPECT_TRUE(Table.exists(Entity2)); +} + +TEST(EntityIdTableTest, ExistsFalse) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@F@bar", "", {}); + + Table.createEntityId(Entity1); + + EXPECT_TRUE(Table.exists(Entity1)); + EXPECT_FALSE(Table.exists(Entity2)); +} + +TEST(EntityIdTableTest, MultipleEntities) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@F@bar", "", {}); + EntityName Entity3("c:@V@baz", "", {}); + + EntityId Id1 = Table.createEntityId(Entity1); + EntityId Id2 = Table.createEntityId(Entity2); + EntityId Id3 = Table.createEntityId(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.createEntityId(Entity1); + EntityId Id2 = Table.createEntityId(Entity2); + + EXPECT_NE(Id1, Id2); +} + +} // 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..5f711a70b216f --- /dev/null +++ b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp @@ -0,0 +1,58 @@ +//===- 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 { +namespace ssaf { +namespace { + +TEST(EntityIdTest, Equality) { + EntityIdTable Table; + + EntityName Entity1("c:@F@foo", "", {}); + EntityName Entity2("c:@F@bar", "", {}); + + EntityId Id1 = Table.createEntityId(Entity1); + EntityId Id2 = Table.createEntityId(Entity2); + EntityId Id1Copy = Table.createEntityId(Entity1); + + EXPECT_EQ(Id1, Id1Copy); + EXPECT_FALSE(Id1 != Id1Copy); + + EXPECT_NE(Id1, Id2); + EXPECT_FALSE(Id1 == Id2); +} + +TEST(EntityIdTest, LessThan) { + EntityIdTable Table; + + EntityName Entity1("c:@F@aaa", "", {}); + EntityName Entity2("c:@F@bbb", "", {}); + EntityName Entity3("c:@F@ccc", "", {}); + + EntityId Id1 = Table.createEntityId(Entity1); + EntityId Id2 = Table.createEntityId(Entity2); + EntityId Id3 = Table.createEntityId(Entity3); + + EXPECT_TRUE(Id1 < Id2 || Id2 < Id1); + EXPECT_TRUE(Id1 < Id3 || Id3 < Id1); + EXPECT_TRUE(Id2 < Id3 || Id3 < Id2); + + // Transitivity: if a < b and b < c, then a < c + if (Id1 < Id2 && Id2 < Id3) { + EXPECT_TRUE(Id1 < Id3); + } +} + +} // namespace +} // namespace ssaf +} // namespace clang >From 6056c7b433c4d1c2e76ec82e79a82f2362327c8d Mon Sep 17 00:00:00 2001 From: Jan Korous <[email protected]> Date: Mon, 8 Dec 2025 17:24:15 -0800 Subject: [PATCH 2/6] [clang][ssaf][NFC] Improve transitivity test for EntityId --- .../Analysis/Scalable/EntityIdTest.cpp | 25 +++++++++++++------ 1 file changed, 17 insertions(+), 8 deletions(-) diff --git a/clang/unittests/Analysis/Scalable/EntityIdTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp index 5f711a70b216f..bf6c9be1327fd 100644 --- a/clang/unittests/Analysis/Scalable/EntityIdTest.cpp +++ b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp @@ -37,20 +37,29 @@ TEST(EntityIdTest, LessThan) { EntityName Entity1("c:@F@aaa", "", {}); EntityName Entity2("c:@F@bbb", "", {}); - EntityName Entity3("c:@F@ccc", "", {}); EntityId Id1 = Table.createEntityId(Entity1); EntityId Id2 = Table.createEntityId(Entity2); - EntityId Id3 = Table.createEntityId(Entity3); EXPECT_TRUE(Id1 < Id2 || Id2 < Id1); - EXPECT_TRUE(Id1 < Id3 || Id3 < Id1); - EXPECT_TRUE(Id2 < Id3 || Id3 < Id2); +} + +TEST(EntityIdTest, Transitivity) { + EntityIdTable Table; + + EntityName Entity1("c:@F@xxx", "", {}); + EntityName Entity2("c:@F@yyy", "", {}); + EntityName Entity3("c:@F@zzz", "", {}); + + EntityId Ids[3] = { + Table.createEntityId(Entity1), + Table.createEntityId(Entity2), + Table.createEntityId(Entity3) + }; + + std::sort(Ids, Ids + 3); - // Transitivity: if a < b and b < c, then a < c - if (Id1 < Id2 && Id2 < Id3) { - EXPECT_TRUE(Id1 < Id3); - } + EXPECT_TRUE(Ids[0] < Ids[1] && Ids[1] < Ids[2]); } } // namespace >From 6aacecc44321d815bcceccff6e3d9e46f4d02bab Mon Sep 17 00:00:00 2001 From: Jan Korous <[email protected]> Date: Mon, 8 Dec 2025 17:52:06 -0800 Subject: [PATCH 3/6] [clang][ssaf][NFC] Add unit tests for EntityTable::forEach --- .../Analysis/Scalable/EntityIdTableTest.cpp | 42 +++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp index 396361efe7233..4f8a164db1cf5 100644 --- a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp +++ b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp @@ -94,6 +94,48 @@ TEST(EntityIdTableTest, WithBuildNamespace) { 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.createEntityId(Entity1); + EntityId Id2 = Table.createEntityId(Entity2); + EntityId Id3 = Table.createEntityId(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 >From 3753da69a23016d8951a571249102eb7198b0962 Mon Sep 17 00:00:00 2001 From: Jan Korous <[email protected]> Date: Wed, 10 Dec 2025 09:47:32 -0800 Subject: [PATCH 4/6] [clang][ssaf] clang-format --- .../clang/Analysis/Scalable/Model/EntityId.h | 6 +++--- .../Analysis/Scalable/Model/EntityIdTable.h | 9 +++++---- .../Analysis/Scalable/Model/EntityIdTable.cpp | 17 ++++++++--------- .../Analysis/Scalable/EntityIdTableTest.cpp | 12 ++++++------ .../Analysis/Scalable/EntityIdTest.cpp | 8 +++----- 5 files changed, 25 insertions(+), 27 deletions(-) diff --git a/clang/include/clang/Analysis/Scalable/Model/EntityId.h b/clang/include/clang/Analysis/Scalable/Model/EntityId.h index 7640051699457..62160c0b5bd14 100644 --- a/clang/include/clang/Analysis/Scalable/Model/EntityId.h +++ b/clang/include/clang/Analysis/Scalable/Model/EntityId.h @@ -38,9 +38,9 @@ class EntityId { 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); } + 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 ssaf diff --git a/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h index 9df19b36c395f..572c7d3efa1aa 100644 --- a/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h +++ b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h @@ -25,7 +25,7 @@ namespace ssaf { class EntityIdTable { std::set<EntityName> Entities; - std::vector<const EntityName*> IdToEntity; + std::vector<const EntityName *> IdToEntity; public: EntityIdTable() = default; @@ -34,15 +34,16 @@ class EntityIdTable { /// /// If the entity already exists in the table, returns its existing Id. /// Otherwise, creates and returns a new Id. This operation is idempotent. - EntityId createEntityId(const EntityName& Name); + EntityId createEntityId(const EntityName &Name); /// Returns true if an entity with the given name exists in the table. - bool exists(const EntityName& Name) const; + bool exists(const EntityName &Name) const; /// Invokes the callback for each entity in the table. /// /// Iteration order is unspecified. - void forEach(std::function<void(const EntityName&, EntityId)> Callback) const; + void + forEach(std::function<void(const EntityName &, EntityId)> Callback) const; /// Returns the number of unique entities in the table. size_t count() const; diff --git a/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp index b47d8d512c01c..7322ff604f6aa 100644 --- a/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp +++ b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp @@ -7,13 +7,13 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/Scalable/Model/EntityIdTable.h" -#include <cassert> #include <algorithm> +#include <cassert> namespace clang { namespace ssaf { -EntityId EntityIdTable::createEntityId(const EntityName& Name) { +EntityId EntityIdTable::createEntityId(const EntityName &Name) { auto [It, Inserted] = Entities.insert(Name); if (Inserted) { @@ -21,7 +21,7 @@ EntityId EntityIdTable::createEntityId(const EntityName& Name) { return EntityId(IdToEntity.size() - 1); } - const EntityName* EntityPtr = &(*It); + const EntityName *EntityPtr = &(*It); auto IdIt = std::find(IdToEntity.begin(), IdToEntity.end(), EntityPtr); assert(IdIt != IdToEntity.end() && "Entity exists but has no ID"); @@ -29,21 +29,20 @@ EntityId EntityIdTable::createEntityId(const EntityName& Name) { return EntityId(Index); } -bool EntityIdTable::exists(const EntityName& Name) const { +bool EntityIdTable::exists(const EntityName &Name) const { return Entities.find(Name) != Entities.end(); } -void EntityIdTable::forEach(std::function<void(const EntityName&, EntityId)> Callback) const { +void EntityIdTable::forEach( + std::function<void(const EntityName &, EntityId)> Callback) const { for (size_t Index = 0; Index < IdToEntity.size(); ++Index) { EntityId EId(Index); - const EntityName& Name = *IdToEntity[Index]; + const EntityName &Name = *IdToEntity[Index]; Callback(Name, EId); } } -size_t EntityIdTable::count() const { - return IdToEntity.size(); -} +size_t EntityIdTable::count() const { return IdToEntity.size(); } } // namespace ssaf } // namespace clang diff --git a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp index 4f8a164db1cf5..b1376092788cb 100644 --- a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp +++ b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp @@ -7,9 +7,9 @@ //===----------------------------------------------------------------------===// #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 "clang/Analysis/Scalable/Model/BuildNamespace.h" #include "gtest/gtest.h" namespace clang { @@ -86,7 +86,8 @@ TEST(EntityIdTableTest, WithBuildNamespace) { NestedBuildNamespace NS = NestedBuildNamespace::makeCompilationUnit("test.o"); EntityName Entity1("c:@F@foo", "", NS); - EntityName Entity2("c:@F@foo", "", NestedBuildNamespace::makeCompilationUnit("other.o")); + EntityName Entity2("c:@F@foo", "", + NestedBuildNamespace::makeCompilationUnit("other.o")); EntityId Id1 = Table.createEntityId(Entity1); EntityId Id2 = Table.createEntityId(Entity2); @@ -98,9 +99,8 @@ TEST(EntityIdTableTest, ForEachEmptyTable) { EntityIdTable Table; int CallbackCount = 0; - Table.forEach([&CallbackCount](const EntityName&, EntityId) { - CallbackCount++; - }); + Table.forEach( + [&CallbackCount](const EntityName &, EntityId) { CallbackCount++; }); EXPECT_EQ(CallbackCount, 0); } @@ -119,7 +119,7 @@ TEST(EntityIdTableTest, ForEachMultipleEntities) { std::set<EntityId> VisitedIds; std::set<EntityName> VisitedNames; - Table.forEach([&](const EntityName& Name, EntityId Id) { + Table.forEach([&](const EntityName &Name, EntityId Id) { VisitedIds.insert(Id); VisitedNames.insert(Name); }); diff --git a/clang/unittests/Analysis/Scalable/EntityIdTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp index bf6c9be1327fd..669c12a37e49d 100644 --- a/clang/unittests/Analysis/Scalable/EntityIdTest.cpp +++ b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp @@ -51,11 +51,9 @@ TEST(EntityIdTest, Transitivity) { EntityName Entity2("c:@F@yyy", "", {}); EntityName Entity3("c:@F@zzz", "", {}); - EntityId Ids[3] = { - Table.createEntityId(Entity1), - Table.createEntityId(Entity2), - Table.createEntityId(Entity3) - }; + EntityId Ids[3] = {Table.createEntityId(Entity1), + Table.createEntityId(Entity2), + Table.createEntityId(Entity3)}; std::sort(Ids, Ids + 3); >From ff81bbea95edf3a9c2176e649b885f4e5f65dbd8 Mon Sep 17 00:00:00 2001 From: Jan Korous <[email protected]> Date: Wed, 10 Dec 2025 16:59:51 -0800 Subject: [PATCH 5/6] [clang][ssaf] Fix performance of EntityIdTable --- .../Analysis/Scalable/Model/EntityIdTable.h | 7 ++--- .../Analysis/Scalable/Model/EntityIdTable.cpp | 26 +++++++------------ 2 files changed, 11 insertions(+), 22 deletions(-) diff --git a/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h index 572c7d3efa1aa..c8893dae39301 100644 --- a/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h +++ b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h @@ -12,8 +12,7 @@ #include "clang/Analysis/Scalable/Model/EntityId.h" #include "clang/Analysis/Scalable/Model/EntityName.h" #include <functional> -#include <set> -#include <vector> +#include <map> namespace clang { namespace ssaf { @@ -23,9 +22,7 @@ namespace ssaf { /// The table maps each unique EntityName maps to exactly one EntityId. /// Entities are never removed. class EntityIdTable { - std::set<EntityName> Entities; - - std::vector<const EntityName *> IdToEntity; + std::map<EntityName, EntityId> Entities; public: EntityIdTable() = default; diff --git a/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp index 7322ff604f6aa..aea22c150a639 100644 --- a/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp +++ b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp @@ -7,26 +7,20 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/Scalable/Model/EntityIdTable.h" -#include <algorithm> #include <cassert> namespace clang { namespace ssaf { EntityId EntityIdTable::createEntityId(const EntityName &Name) { - auto [It, Inserted] = Entities.insert(Name); - - if (Inserted) { - IdToEntity.push_back(&(*It)); - return EntityId(IdToEntity.size() - 1); + const auto It = Entities.find(Name); + if (It == Entities.end()) { + EntityId Id(Entities.size()); + Entities.emplace(Name, Id); + return Id; } - const EntityName *EntityPtr = &(*It); - auto IdIt = std::find(IdToEntity.begin(), IdToEntity.end(), EntityPtr); - assert(IdIt != IdToEntity.end() && "Entity exists but has no ID"); - - size_t Index = std::distance(IdToEntity.begin(), IdIt); - return EntityId(Index); + return It->second; } bool EntityIdTable::exists(const EntityName &Name) const { @@ -35,14 +29,12 @@ bool EntityIdTable::exists(const EntityName &Name) const { void EntityIdTable::forEach( std::function<void(const EntityName &, EntityId)> Callback) const { - for (size_t Index = 0; Index < IdToEntity.size(); ++Index) { - EntityId EId(Index); - const EntityName &Name = *IdToEntity[Index]; - Callback(Name, EId); + for (const auto& [Name, Id] : Entities) { + Callback(Name, Id); } } -size_t EntityIdTable::count() const { return IdToEntity.size(); } +size_t EntityIdTable::count() const { return Entities.size(); } } // namespace ssaf } // namespace clang >From 544fedb5c6c47c3f7c6d1968c76444fb6a11b5ab Mon Sep 17 00:00:00 2001 From: Jan Korous <[email protected]> Date: Wed, 10 Dec 2025 17:01:00 -0800 Subject: [PATCH 6/6] [clang][ssaf] Rename EntityId method --- .../Analysis/Scalable/Model/EntityIdTable.h | 2 +- .../Analysis/Scalable/Model/EntityIdTable.cpp | 2 +- .../Analysis/Scalable/EntityIdTableTest.cpp | 30 +++++++++---------- .../Analysis/Scalable/EntityIdTest.cpp | 16 +++++----- 4 files changed, 25 insertions(+), 25 deletions(-) diff --git a/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h index c8893dae39301..ecf0de2ff4866 100644 --- a/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h +++ b/clang/include/clang/Analysis/Scalable/Model/EntityIdTable.h @@ -31,7 +31,7 @@ class EntityIdTable { /// /// If the entity already exists in the table, returns its existing Id. /// Otherwise, creates and returns a new Id. This operation is idempotent. - EntityId createEntityId(const EntityName &Name); + EntityId getId(const EntityName &Name); /// Returns true if an entity with the given name exists in the table. bool exists(const EntityName &Name) const; diff --git a/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp index aea22c150a639..b66ad7dfb9a98 100644 --- a/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp +++ b/clang/lib/Analysis/Scalable/Model/EntityIdTable.cpp @@ -12,7 +12,7 @@ namespace clang { namespace ssaf { -EntityId EntityIdTable::createEntityId(const EntityName &Name) { +EntityId EntityIdTable::getId(const EntityName &Name) { const auto It = Entities.find(Name); if (It == Entities.end()) { EntityId Id(Entities.size()); diff --git a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp index b1376092788cb..e3e06a2e0aa73 100644 --- a/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp +++ b/clang/unittests/Analysis/Scalable/EntityIdTableTest.cpp @@ -20,7 +20,7 @@ TEST(EntityIdTableTest, CreateNewEntity) { EntityIdTable Table; EntityName Entity("c:@F@foo", "", {}); - Table.createEntityId(Entity); + Table.getId(Entity); EXPECT_TRUE(Table.exists(Entity)); } @@ -30,9 +30,9 @@ TEST(EntityIdTableTest, Idempotency) { EntityName Entity("c:@F@foo", "", {}); - EntityId Id1 = Table.createEntityId(Entity); - EntityId Id2 = Table.createEntityId(Entity); - EntityId Id3 = Table.createEntityId(Entity); + EntityId Id1 = Table.getId(Entity); + EntityId Id2 = Table.getId(Entity); + EntityId Id3 = Table.getId(Entity); EXPECT_EQ(Id1, Id2); EXPECT_EQ(Id2, Id3); @@ -45,8 +45,8 @@ TEST(EntityIdTableTest, ExistsTrue) { EntityName Entity1("c:@F@foo", "", {}); EntityName Entity2("c:@V@bar", "", {}); - Table.createEntityId(Entity1); - Table.createEntityId(Entity2); + Table.getId(Entity1); + Table.getId(Entity2); EXPECT_TRUE(Table.exists(Entity1)); EXPECT_TRUE(Table.exists(Entity2)); @@ -58,7 +58,7 @@ TEST(EntityIdTableTest, ExistsFalse) { EntityName Entity1("c:@F@foo", "", {}); EntityName Entity2("c:@F@bar", "", {}); - Table.createEntityId(Entity1); + Table.getId(Entity1); EXPECT_TRUE(Table.exists(Entity1)); EXPECT_FALSE(Table.exists(Entity2)); @@ -71,9 +71,9 @@ TEST(EntityIdTableTest, MultipleEntities) { EntityName Entity2("c:@F@bar", "", {}); EntityName Entity3("c:@V@baz", "", {}); - EntityId Id1 = Table.createEntityId(Entity1); - EntityId Id2 = Table.createEntityId(Entity2); - EntityId Id3 = Table.createEntityId(Entity3); + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + EntityId Id3 = Table.getId(Entity3); EXPECT_NE(Id1, Id2); EXPECT_NE(Id1, Id3); @@ -89,8 +89,8 @@ TEST(EntityIdTableTest, WithBuildNamespace) { EntityName Entity2("c:@F@foo", "", NestedBuildNamespace::makeCompilationUnit("other.o")); - EntityId Id1 = Table.createEntityId(Entity1); - EntityId Id2 = Table.createEntityId(Entity2); + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); EXPECT_NE(Id1, Id2); } @@ -112,9 +112,9 @@ TEST(EntityIdTableTest, ForEachMultipleEntities) { EntityName Entity2("c:@F@bar", "", {}); EntityName Entity3("c:@V@baz", "", {}); - EntityId Id1 = Table.createEntityId(Entity1); - EntityId Id2 = Table.createEntityId(Entity2); - EntityId Id3 = Table.createEntityId(Entity3); + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + EntityId Id3 = Table.getId(Entity3); std::set<EntityId> VisitedIds; std::set<EntityName> VisitedNames; diff --git a/clang/unittests/Analysis/Scalable/EntityIdTest.cpp b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp index 669c12a37e49d..a18b615c03443 100644 --- a/clang/unittests/Analysis/Scalable/EntityIdTest.cpp +++ b/clang/unittests/Analysis/Scalable/EntityIdTest.cpp @@ -21,9 +21,9 @@ TEST(EntityIdTest, Equality) { EntityName Entity1("c:@F@foo", "", {}); EntityName Entity2("c:@F@bar", "", {}); - EntityId Id1 = Table.createEntityId(Entity1); - EntityId Id2 = Table.createEntityId(Entity2); - EntityId Id1Copy = Table.createEntityId(Entity1); + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); + EntityId Id1Copy = Table.getId(Entity1); EXPECT_EQ(Id1, Id1Copy); EXPECT_FALSE(Id1 != Id1Copy); @@ -38,8 +38,8 @@ TEST(EntityIdTest, LessThan) { EntityName Entity1("c:@F@aaa", "", {}); EntityName Entity2("c:@F@bbb", "", {}); - EntityId Id1 = Table.createEntityId(Entity1); - EntityId Id2 = Table.createEntityId(Entity2); + EntityId Id1 = Table.getId(Entity1); + EntityId Id2 = Table.getId(Entity2); EXPECT_TRUE(Id1 < Id2 || Id2 < Id1); } @@ -51,9 +51,9 @@ TEST(EntityIdTest, Transitivity) { EntityName Entity2("c:@F@yyy", "", {}); EntityName Entity3("c:@F@zzz", "", {}); - EntityId Ids[3] = {Table.createEntityId(Entity1), - Table.createEntityId(Entity2), - Table.createEntityId(Entity3)}; + EntityId Ids[3] = {Table.getId(Entity1), + Table.getId(Entity2), + Table.getId(Entity3)}; std::sort(Ids, Ids + 3); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
