[NFC][SSAF] Rename PointerFlowReachableAnalysis to UnsafeBufferReachableAnalysisusers/ziqingluo/PR-175802731-1

The previous-named PointerFlowReachableAnalysis is essentially
propagating unsafe buffers on a pointer flow graph.  The pointer flow
analysis is a dependency, instead of the subject.  So do the rename
and move.

5 files changed, 564 insertions, 129 deletions

diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h
index e862df58a820..852752270e8e 100644
--- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h
+++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h
@@ -9,15 +9,12 @@
 // Defines
 // - PointerFlowAnalysisResult---the plain PointerFlow info collected from
 //   the whole program.
-// - PointerFlowReachableAnalysisResult---the set of reachable pointers
-//   in the pointer flow graph from a provided starting set.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_ANALYSES_POINTERFLOW_POINTERFLOWANALYSIS_H
 #define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_ANALYSES_POINTERFLOW_POINTERFLOWANALYSIS_H
 
-#include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.h"
 #include "clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h"
 #include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityId.h"
 #include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/AnalysisName.h"
@@ -29,8 +26,6 @@ namespace clang::ssaf {
 
 constexpr llvm::StringLiteral PointerFlowAnalysisResultName =
     "PointerFlowAnalysisResult";
-constexpr llvm::StringLiteral UnsafeBufferReachableAnalysisResultName =
-    "UnsafeBufferReachableAnalysisResult";
 
 struct PointerFlowAnalysisResult final : AnalysisResult {
   static AnalysisName analysisName() {
@@ -40,14 +35,6 @@ struct PointerFlowAnalysisResult final : AnalysisResult {
   std::map<EntityId, EdgeSet> Edges;
 };
 
-struct UnsafeBufferReachableAnalysisResult final : AnalysisResult {
-  static AnalysisName analysisName() {
-    return AnalysisName(UnsafeBufferReachableAnalysisResultName.str());
-  }
-
-  std::map<EntityId, EntityPointerLevelSet> Reachables;
-};
-
 } // namespace clang::ssaf
 
 #endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_ANALYSES_POINTERFLOW_POINTERFLOWANALYSIS_H
diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h
index 9cfd59e5c033..1db62b30a4e6 100644
--- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h
+++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h
@@ -6,8 +6,15 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// Defines UnsafeBufferUsageAnalysisResult, the whole-program analysis result
-// type for UnsafeBufferUsageAnalysis.
+// Defines:
+// - UnsafeBufferUsageAnalysisResult, the whole-program analysis result
+//   type for UnsafeBufferUsageAnalysis. It collects unsafe buffer usages
+//   throughout the whole program.
+//
+// - UnsafeBufferReachableAnalysisResult, the whole-program analysis result
+//   type for UnsafeBufferReachableAnalysis. It propagates unsafe buffer usages
+//   through the pointer flow graph, starting from the initial set collected by
+//   UnsafeBufferUsageAnalysis.
 //
 //===----------------------------------------------------------------------===//
 
@@ -25,6 +32,8 @@ namespace clang::ssaf {
 
 constexpr llvm::StringLiteral UnsafeBufferUsageAnalysisResultName =
     "UnsafeBufferUsageAnalysisResult";
+constexpr llvm::StringLiteral UnsafeBufferReachableAnalysisResultName =
+    "UnsafeBufferReachableAnalysisResult";
 
 struct UnsafeBufferUsageAnalysisResult final : AnalysisResult {
   static AnalysisName analysisName() {
@@ -38,6 +47,14 @@ struct UnsafeBufferUsageAnalysisResult final : AnalysisResult {
   auto end() const { return UnsafeBuffers.end(); }
 };
 
+struct UnsafeBufferReachableAnalysisResult final : AnalysisResult {
+  static AnalysisName analysisName() {
+    return AnalysisName(UnsafeBufferReachableAnalysisResultName.str());
+  }
+
+  std::map<EntityId, EntityPointerLevelSet> Reachables;
+};
+
 } // namespace clang::ssaf
 
 #endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_ANALYSES_UNSAFEBUFFERUSAGE_UNSAFEBUFFERUSAGEANALYSIS_H
diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp
index 83652c2f1147..6334f742d615 100644
--- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp
+++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp
@@ -8,11 +8,8 @@
 
 #include "clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h"
 #include "SSAFAnalysesCommon.h"
-#include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.h"
-#include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h"
 #include "clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h"
 #include "clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowFormat.h"
-#include "clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h"
 #include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityId.h"
 #include "clang/ScalableStaticAnalysisFramework/Core/Serialization/JSONFormat.h"
 #include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/AnalysisRegistry.h"
@@ -23,7 +20,6 @@
 #include "llvm/Support/Error.h"
 #include "llvm/Support/JSON.h"
 #include <memory>
-#include <unordered_set>
 
 using namespace clang::ssaf;
 using namespace llvm;
@@ -118,116 +114,6 @@ public:
 AnalysisRegistry::Add<PointerFlowAnalysis>
     RegisterPointerFlowAnalysis("Whole-program pointer flow analysis");
 
-//===----------------------------------------------------------------------===//
-// PointerFlowReachableAnalysis---computes reachable node
-//===----------------------------------------------------------------------===//
-
-json::Object serializePointerFlowReachableAnalysisResult(
-    const UnsafeBufferReachableAnalysisResult &R,
-    JSONFormat::EntityIdToJSONFn IdToJSON) {
-  json::Object Result;
-
-  Result[UnsafeBufferReachableAnalysisResultName] =
-      entityPointerLevelMapToJSON(R.Reachables, IdToJSON);
-  return Result;
-}
-
-Expected<std::unique_ptr<AnalysisResult>>
-deserializePointerFlowReachableAnalysisResult(
-    const json::Object &Obj, JSONFormat::EntityIdFromJSONFn IdFromJSON) {
-  const json::Array *Content =
-      Obj.getArray(UnsafeBufferReachableAnalysisResultName);
-
-  if (!Content)
-    return makeSawButExpectedError(
-        Obj, "an object with a key %s",
-        UnsafeBufferReachableAnalysisResultName.data());
-
-  auto Reachables = entityPointerLevelMapFromJSON(*Content, IdFromJSON);
-
-  if (!Reachables)
-    return Reachables.takeError();
-
-  auto Ret = std::make_unique<UnsafeBufferReachableAnalysisResult>();
-
-  Ret->Reachables = std::move(*Reachables);
-  return Ret;
-}
-
-JSONFormat::AnalysisResultRegistry::Add<UnsafeBufferReachableAnalysisResult>
-    RegisterPointerFlowReachableResultForJSON(
-        serializePointerFlowReachableAnalysisResult,
-        deserializePointerFlowReachableAnalysisResult);
-
-/// Computes all the reachable "nodes" (pointers) in a pointer flow graph from a
-/// provided starter node set.  Specifically, the starter set is the unsafe
-/// pointers found by `UnsafeBufferUsageAnalysis`.
-class UnsafeBufferReachableAnalysis
-    : public DerivedAnalysis<UnsafeBufferReachableAnalysisResult,
-                             PointerFlowAnalysisResult,
-                             UnsafeBufferUsageAnalysisResult> {
-  using GraphT = std::map<EntityId, EdgeSet>;
-  const GraphT *Graph = nullptr;
-
-  // Use pointers for efficiency. Both `Graph` and `Reachables` in the result
-  // are tree-based containers that only grow. So pointers to them are stable.
-  using EPLPtr = const EntityPointerLevel *;
-  using EPLPtrSet = std::unordered_set<EPLPtr>;
-  // The analysis needs to track EPLs with their contributor IDs:
-  using EPLPtrSetWithId = std::map<EntityId, std::unordered_set<EPLPtr>>;
-
-  // Find all outgoing edges from `EPL` in the `Graph`, insert their
-  // destination nodes into `Reachables`, and add newly discovered nodes to
-  // `Worklist`:
-  void updateReachablesWithOutgoings(EPLPtr EPL,
-                                     std::vector<EPLPtr> &WorkList) {
-    for (auto &[Id, SubGraph] : *Graph) {
-      auto I = SubGraph.find(*EPL);
-
-      if (I != SubGraph.end()) {
-        for (const auto &EPL : I->second) {
-          auto [Ignored, Inserted] =
-              this->getResult().Reachables[Id].insert(EPL);
-          if (Inserted)
-            WorkList.push_back(&EPL);
-        }
-      }
-    }
-  }
-
-public:
-  llvm::Error
-  initialize(const PointerFlowAnalysisResult &Graph,
-             const UnsafeBufferUsageAnalysisResult &Starter) override {
-    this->Graph = &Graph.Edges;
-    assert(this->getResult().Reachables.empty());
-    this->getResult().Reachables.insert(Starter.begin(), Starter.end());
-    return llvm::Error::success();
-  }
-
-  llvm::Expected<bool> step() override {
-    auto &Reachables = this->getResult().Reachables;
-    // Simple DFS:
-    std::vector<EPLPtr> Worklist;
-
-    for (auto &[Id, EPLs] : Reachables)
-      for (auto &EPL : EPLs)
-        Worklist.push_back(&EPL);
-
-    while (!Worklist.empty()) {
-      EPLPtr Node = Worklist.back();
-      Worklist.pop_back();
-
-      updateReachablesWithOutgoings(Node, Worklist);
-    }
-    return false;
-  }
-};
-
-AnalysisRegistry::Add<UnsafeBufferReachableAnalysis>
-    RegisterPointerFlowReachableAnalysis(
-        "Reachable pointers from unsafe buffer usage in pointer flow graph");
-
 } // namespace
 
 // NOLINTNEXTLINE(misc-use-internal-linkage)
diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp
index 0a7b62f20786..62ff0eafe72f 100644
--- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp
+++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp
@@ -15,6 +15,7 @@
 #include "SSAFAnalysesCommon.h"
 #include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.h"
 #include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h"
+#include "clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h"
 #include "clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsage.h"
 #include "clang/ScalableStaticAnalysisFramework/Core/Serialization/JSONFormat.h"
 #include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/AnalysisRegistry.h"
@@ -82,6 +83,116 @@ AnalysisRegistry::Add<UnsafeBufferUsageAnalysis>
     RegisterUnsafeBufferUsageAnalysis(
         "Whole-program unsafe buffer usage analysis");
 
+//===----------------------------------------------------------------------===//
+// UnsafeBufferReachableAnalysis---computes reachable unsafe buffer nodes
+//===----------------------------------------------------------------------===//
+
+json::Object serializeUnsafeBufferReachableAnalysisResult(
+    const UnsafeBufferReachableAnalysisResult &R,
+    JSONFormat::EntityIdToJSONFn IdToJSON) {
+  json::Object Result;
+
+  Result[UnsafeBufferReachableAnalysisResultName] =
+      entityPointerLevelMapToJSON(R.Reachables, IdToJSON);
+  return Result;
+}
+
+Expected<std::unique_ptr<AnalysisResult>>
+deserializeUnsafeBufferReachableAnalysisResult(
+    const json::Object &Obj, JSONFormat::EntityIdFromJSONFn IdFromJSON) {
+  const json::Array *Content =
+      Obj.getArray(UnsafeBufferReachableAnalysisResultName);
+
+  if (!Content)
+    return makeSawButExpectedError(
+        Obj, "an object with a key %s",
+        UnsafeBufferReachableAnalysisResultName.data());
+
+  auto Reachables = entityPointerLevelMapFromJSON(*Content, IdFromJSON);
+
+  if (!Reachables)
+    return Reachables.takeError();
+
+  auto Ret = std::make_unique<UnsafeBufferReachableAnalysisResult>();
+
+  Ret->Reachables = std::move(*Reachables);
+  return Ret;
+}
+
+JSONFormat::AnalysisResultRegistry::Add<UnsafeBufferReachableAnalysisResult>
+    RegisterPointerFlowReachableResultForJSON(
+        serializeUnsafeBufferReachableAnalysisResult,
+        deserializeUnsafeBufferReachableAnalysisResult);
+
+/// Computes all the reachable "nodes" (pointers) in a pointer flow graph from a
+/// provided starter node set.  Specifically, the starter set is the unsafe
+/// pointers found by `UnsafeBufferUsageAnalysis`.
+class UnsafeBufferReachableAnalysis
+    : public DerivedAnalysis<UnsafeBufferReachableAnalysisResult,
+                             PointerFlowAnalysisResult,
+                             UnsafeBufferUsageAnalysisResult> {
+  using GraphT = std::map<EntityId, EdgeSet>;
+  const GraphT *Graph = nullptr;
+
+  // Use pointers for efficiency. Both `Graph` and `Reachables` in the result
+  // are tree-based containers that only grow. So pointers to them are stable.
+  using EPLPtr = const EntityPointerLevel *;
+  using EPLPtrSet = std::unordered_set<EPLPtr>;
+  // The analysis needs to track EPLs with their contributor IDs:
+  using EPLPtrSetWithId = std::map<EntityId, std::unordered_set<EPLPtr>>;
+
+  // Find all outgoing edges from `EPL` in the `Graph`, insert their
+  // destination nodes into `Reachables`, and add newly discovered nodes to
+  // `Worklist`:
+  void updateReachablesWithOutgoings(EPLPtr EPL,
+                                     std::vector<EPLPtr> &WorkList) {
+    for (auto &[Id, SubGraph] : *Graph) {
+      auto I = SubGraph.find(*EPL);
+
+      if (I != SubGraph.end()) {
+        for (const auto &EPL : I->second) {
+          auto [Ignored, Inserted] =
+              this->getResult().Reachables[Id].insert(EPL);
+          if (Inserted)
+            WorkList.push_back(&EPL);
+        }
+      }
+    }
+  }
+
+public:
+  llvm::Error
+  initialize(const PointerFlowAnalysisResult &Graph,
+             const UnsafeBufferUsageAnalysisResult &Starter) override {
+    this->Graph = &Graph.Edges;
+    assert(this->getResult().Reachables.empty());
+    this->getResult().Reachables.insert(Starter.begin(), Starter.end());
+    return llvm::Error::success();
+  }
+
+  llvm::Expected<bool> step() override {
+    auto &Reachables = this->getResult().Reachables;
+    // Simple DFS:
+    std::vector<EPLPtr> Worklist;
+
+    for (auto &[Id, EPLs] : Reachables)
+      for (auto &EPL : EPLs)
+        Worklist.push_back(&EPL);
+
+    while (!Worklist.empty()) {
+      EPLPtr Node = Worklist.back();
+      Worklist.pop_back();
+
+      updateReachablesWithOutgoings(Node, Worklist);
+    }
+    return false;
+  }
+};
+
+AnalysisRegistry::Add<UnsafeBufferReachableAnalysis>
+    RegisterUnsafeBufferReachableAnalysis(
+        "Propagate unsafe buffer usages throughout the program");
+
 } // namespace
 
 // NOLINTNEXTLINE(misc-use-internal-linkage)
diff --git a/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp
new file mode 100644
index 000000000000..cc303faf0925
--- /dev/null
+++ b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp
@@ -0,0 +1,434 @@
+//===- UnsafeBufferReachableAnalysisTest.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 "../TestFixture.h"
+#include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.h"
+#include "clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h"
+#include "clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h"
+#include "clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsage.h"
+#include "clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h"
+#include "clang/ScalableStaticAnalysisFramework/Core/EntityLinker/LUSummary.h"
+#include "clang/ScalableStaticAnalysisFramework/Core/Model/BuildNamespace.h"
+#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityId.h"
+#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityLinkage.h"
+#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityName.h"
+#include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/AnalysisDriver.h"
+#include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/WPASuite.h"
+#include "llvm/ADT/Sequence.h"
+#include "gtest/gtest.h"
+#include <map>
+#include <memory>
+#include <optional>
+
+using namespace clang;
+using namespace ssaf;
+
+namespace clang::ssaf {
+extern PointerFlowEntitySummary buildPointerFlowEntitySummary(EdgeSet Edges);
+extern UnsafeBufferUsageEntitySummary
+    buildUnsafeBufferUsageEntitySummary(EntityPointerLevelSet);
+} // namespace clang::ssaf
+
+namespace {
+
+/// Enumerate all possible partitions of `N` nodes into `NumGrps` groups.
+/// Both nodes and groups are unlabeled. For each partition, a non-increasing
+/// order is enforced to avoid equivalent permutations.
+///
+/// \return all possible partitions, each represented as an array of unsigned
+/// integers denoting the number of nodes in each group.
+/// \param N the number of nodes
+/// \param NumGrps the number of groups
+/// \param MaxPerGrp an upper bound on the number of nodes per group, used to
+/// enforce non-increasing order and prevent duplicate partitions.
+using PartitionT = std::vector<unsigned>;
+static std::vector<PartitionT> enumeratePartition(unsigned N, unsigned NumGrps,
+                                                  unsigned MaxPerGrp) {
+  if (NumGrps == 0) {
+    if (N == 0)
+      return {{}};
+    return {}; // Due to the non-increasing order enforcement, equivalent
+               // permutations become invalid partitions.
+  }
+
+  std::vector<PartitionT> Partitions;
+
+  MaxPerGrp = std::min(N, MaxPerGrp);
+  // Try to distribute `J` nodes to the current group:
+  for (unsigned J = MaxPerGrp;; --J) {
+    std::vector<PartitionT> PrefixPartitions =
+        enumeratePartition(N - J, NumGrps - 1, J);
+
+    for (auto &Partition : PrefixPartitions) {
+      Partition.push_back(J);
+      Partitions.push_back(std::move(Partition));
+    }
+    if (J == 0)
+      break;
+  }
+  return Partitions;
+}
+
+class UnsafeBufferReachableAnalysisTest : public TestFixture {
+protected:
+  using EPLEdge = std::pair<EntityPointerLevel, EntityPointerLevel>;
+
+  static constexpr EntityLinkage ExternalLinkage =
+      EntityLinkage(EntityLinkageType::External);
+
+  std::unique_ptr<LUSummary> makeLUSummary() {
+    NestedBuildNamespace NS(
+        {BuildNamespace(BuildNamespaceKind::LinkUnit, "TestLU")});
+    return std::make_unique<LUSummary>(std::move(NS));
+  }
+
+  EntityId addEntity(LUSummary &LU, llvm::StringRef USR) {
+    NestedBuildNamespace NS(
+        {BuildNamespace(BuildNamespaceKind::LinkUnit, "TestLU")});
+    EntityName Name(USR.str(), "", NS);
+    EntityId Id = getIdTable(LU).getId(Name);
+    getLinkageTable(LU).insert({Id, ExternalLinkage});
+    return Id;
+  }
+
+  /// Insert a PointerFlowEntitySummary for an entity.
+  void insertPointerFlowSummary(LUSummary &LU, EntityId Id, EdgeSet Edges) {
+    getData(LU)[PointerFlowEntitySummary::summaryName()][Id] =
+        std::make_unique<PointerFlowEntitySummary>(
+            buildPointerFlowEntitySummary(std::move(Edges)));
+  }
+
+  /// Insert an UnsafeBufferUsageEntitySummary for an entity.
+  void insertUnsafeBufferUsageSummary(LUSummary &LU, EntityId Id,
+                                      EntityPointerLevelSet UnsafeBuffers) {
+    getData(LU)[UnsafeBufferUsageEntitySummary::summaryName()][Id] =
+        std::make_unique<UnsafeBufferUsageEntitySummary>(
+            buildUnsafeBufferUsageEntitySummary(std::move(UnsafeBuffers)));
+  }
+
+  /// Create \p N entities in \p LU and return their EntityIds.
+  std::vector<EntityId> createEntities(LUSummary &LU, unsigned N) {
+    std::vector<EntityId> Ids;
+    for (unsigned I = 0; I < N; ++I)
+      Ids.push_back(addEntity(LU, ("E" + llvm::Twine(I)).str()));
+    return Ids;
+  }
+
+  /// Create \p N EPLs, one per entity.
+  std::vector<EntityPointerLevel>
+  createEPLs(llvm::ArrayRef<EntityId> Entities) {
+    std::vector<EntityPointerLevel> EPLs;
+    for (const auto &Id : Entities)
+      EPLs.push_back(buildEntityPointerLevel(Id, 1));
+    return EPLs;
+  }
+
+  /// Insert both PointerFlow and UnsafeBufferUsage summaries for an entity
+  /// from a list of edges and a list of starter EPLs.
+  void insertSummaries(LUSummary &LU, EntityId Id,
+                       llvm::ArrayRef<EPLEdge> EdgeList,
+                       llvm::ArrayRef<EntityPointerLevel> StarterList) {
+    EdgeSet Edges;
+    for (const auto &[From, To] : EdgeList)
+      Edges[From].insert(To);
+    insertPointerFlowSummary(LU, Id, std::move(Edges));
+
+    EntityPointerLevelSet Starters;
+    for (const auto &EPL : StarterList)
+      Starters.insert(EPL);
+    insertUnsafeBufferUsageSummary(LU, Id, std::move(Starters));
+  }
+
+  /// Run the driver and return the flattened reachable EPL set.
+  std::optional<EntityPointerLevelSet>
+  computeReachables(std::unique_ptr<LUSummary> LU, unsigned Line) {
+    AnalysisDriver Driver(std::move(LU));
+    auto WPAOrErr =
+        Driver.run<PointerFlowAnalysisResult, UnsafeBufferUsageAnalysisResult,
+                   UnsafeBufferReachableAnalysisResult>();
+    if (!WPAOrErr) {
+      ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(WPAOrErr.takeError());
+      return std::nullopt;
+    }
+    auto ROrErr = WPAOrErr->get<UnsafeBufferReachableAnalysisResult>();
+    if (!ROrErr) {
+      ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(ROrErr.takeError());
+      return std::nullopt;
+    }
+    EntityPointerLevelSet Result;
+    for (const auto &[Id, EPLs] : ROrErr->Reachables)
+      Result.insert(EPLs.begin(), EPLs.end());
+    return Result;
+  }
+
+  /// Partition edges and starter nodes into different sub-graphs (owned by
+  /// contributor Entities) and test different partitions.
+  ///
+  /// For every partition of edges and starters across \p NumEnt entities,
+  /// build the graph, run the analysis, and verify all partitions produce the
+  /// same reachable node indices.  Returns the common set of reachable indices.
+  std::optional<std::set<unsigned>>
+  forEachPartition(unsigned NumEnt,
+                   llvm::ArrayRef<std::pair<unsigned, unsigned>> EdgeLayout,
+                   llvm::ArrayRef<unsigned> StarterLayout, unsigned Line) {
+    auto EdgePartitions =
+        enumeratePartition(EdgeLayout.size(), NumEnt, EdgeLayout.size());
+    auto StarterPartitions =
+        enumeratePartition(StarterLayout.size(), NumEnt, StarterLayout.size());
+
+    std::optional<std::set<unsigned>> Expected;
+
+    for (const auto &EP : EdgePartitions) {
+      for (const auto &SP : StarterPartitions) {
+        auto LU = makeLUSummary();
+        auto Entities = createEntities(*LU, NumEnt);
+        auto N = createEPLs(Entities);
+
+        std::vector<EPLEdge> Edges;
+        for (const auto &[F, T] : EdgeLayout)
+          Edges.push_back({N[F], N[T]});
+
+        std::vector<EntityPointerLevel> Starters;
+        for (unsigned Idx : StarterLayout)
+          Starters.push_back(N[Idx]);
+
+        unsigned EdgesBegin = 0, StartersBegin = 0;
+        for (unsigned Idx = 0; Idx < NumEnt; ++Idx) {
+          auto EdgeGrp =
+              llvm::ArrayRef<EPLEdge>(Edges).slice(EdgesBegin, EP[Idx]);
+          EdgesBegin += EP[Idx];
+
+          auto StarterGrp = llvm::ArrayRef<EntityPointerLevel>(Starters).slice(
+              StartersBegin, SP[Idx]);
+          StartersBegin += SP[Idx];
+
+          insertSummaries(*LU, Entities[Idx], EdgeGrp, StarterGrp);
+        }
+
+        auto Reachables = computeReachables(std::move(LU), Line);
+        if (!Reachables.has_value())
+          return std::nullopt;
+
+        // Convert to index set for comparison across partitions.
+        std::set<unsigned> ReachableIndices;
+        for (unsigned I : llvm::seq(0U, NumEnt))
+          if (Reachables->count(N[I]))
+            ReachableIndices.insert(I);
+
+        if (!Expected) {
+          Expected = ReachableIndices;
+        } else {
+          EXPECT_EQ(*Expected, ReachableIndices)
+              << "Inconsistent reachables across partitions";
+        }
+      }
+    }
+    return Expected;
+  }
+};
+
+//- Test different graph topologic structures ----------------------//
+
+// Linear chain: 0 -> 1 -> 2 -> 3.
+// Start from {0} => {0, 1, 2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {1, 2}, {2, 3}},
+      /* StarterLayout */ {0}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 4u);
+}
+
+// Linear chain: 0 -> 1 -> 2 -> 3.
+// Start from mid-chain {2} => {2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, LinearChainFromMiddle) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {1, 2}, {2, 3}},
+      /* StarterLayout */ {2}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 2u);
+  EXPECT_TRUE(Reachables->count(2));
+  EXPECT_TRUE(Reachables->count(3));
+}
+
+// Diamond: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3.
+// Start from {0} => {0, 1, 2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, Diamond) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {0, 2}, {1, 3}, {2, 3}},
+      /* StarterLayout */ {0}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 4u);
+}
+
+// Diamond: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3.
+// Start from one branch {1} => {1, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, DiamondFromBranch) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {0, 2}, {1, 3}, {2, 3}},
+      /* StarterLayout */ {1}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 2u);
+  EXPECT_TRUE(Reachables->count(1));
+  EXPECT_TRUE(Reachables->count(3));
+}
+
+// Disconnected subgraphs: 0 -> 1, 2 -> 3.
+// Start from {0} => {0, 1}
+TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphs) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {2, 3}},
+      /* StarterLayout */ {0}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 2u);
+  EXPECT_TRUE(Reachables->count(0));
+  EXPECT_TRUE(Reachables->count(1));
+}
+
+// Disconnected subgraphs: 0 -> 1, 2 -> 3.
+// Start from tail {1} => {1}
+TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphsFromTail) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {2, 3}},
+      /* StarterLayout */ {1}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 1u);
+  EXPECT_TRUE(Reachables->count(1));
+}
+
+// Cycle: 0 -> 1 -> 2 -> 3 -> 0.
+// Start from {2} => {0, 1, 2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, Cycle) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {1, 2}, {2, 3}, {3, 0}},
+      /* StarterLayout */ {2}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 4u);
+  EXPECT_TRUE(Reachables->count(0));
+  EXPECT_TRUE(Reachables->count(1));
+  EXPECT_TRUE(Reachables->count(2));
+  EXPECT_TRUE(Reachables->count(3));
+}
+
+// Empty graph: no edges, start from {0} => {0}
+TEST_F(UnsafeBufferReachableAnalysisTest, EmptyGraph) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {},
+      /* StarterLayout */ {0}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 1u);
+  EXPECT_TRUE(Reachables->count(0));
+}
+
+// Star: 0 -> 1, 0 -> 2, 0 -> 3.
+// Start from {0} => {0, 1, 2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {0, 2}, {0, 3}},
+      /* StarterLayout */ {0}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 4u);
+}
+
+// Star: 0 -> 1, 0 -> 2, 0 -> 3.
+// Start from leaf {2} => {2}
+TEST_F(UnsafeBufferReachableAnalysisTest, StarFromLeaf) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {0, 2}, {0, 3}},
+      /* StarterLayout */ {2}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 1u);
+  EXPECT_TRUE(Reachables->count(2));
+}
+
+// Reverse star: 0 -> 3, 1 -> 3, 2 -> 3.
+// Start from {0} => {0, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSource) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 3}, {1, 3}, {2, 3}},
+      /* StarterLayout */ {0}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 2u);
+  EXPECT_TRUE(Reachables->count(0));
+  EXPECT_TRUE(Reachables->count(3));
+}
+
+// Reverse star: 0 -> 3, 1 -> 3, 2 -> 3.
+// Start from sink {3} => {3}
+TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSink) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 3}, {1, 3}, {2, 3}},
+      /* StarterLayout */ {3}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 1u);
+  EXPECT_TRUE(Reachables->count(3));
+}
+
+// Self-loop: 0 -> 1, 1 -> 1, 1 -> 2, 2 -> 3.
+// Start from {0} => {0, 1, 2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromRoot) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {1, 1}, {1, 2}, {2, 3}},
+      /* StarterLayout */ {0}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 4u);
+}
+
+// Self-loop: 0 -> 1, 1 -> 1, 1 -> 2, 2 -> 3.
+// Start from {1} => {1, 2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromLoopNode) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {1, 1}, {1, 2}, {2, 3}},
+      /* StarterLayout */ {1}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 3u);
+  EXPECT_TRUE(Reachables->count(1));
+  EXPECT_TRUE(Reachables->count(2));
+  EXPECT_TRUE(Reachables->count(3));
+}
+
+// Multiple starters: 0 -> 1, 2 -> 3 (disconnected).
+// Start from {0, 2} => {0, 1, 2, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersBothChains) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {2, 3}},
+      /* StarterLayout */ {0, 2}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 4u);
+}
+
+// Multiple starters: 0 -> 1, 2 -> 3 (disconnected).
+// Start from leaves {1, 3} => {1, 3}
+TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersLeaves) {
+  auto Reachables = forEachPartition(
+      /* NumEnt */ 4,
+      /* EdgeLayout */ {{0, 1}, {2, 3}},
+      /* StarterLayout */ {1, 3}, __LINE__);
+  ASSERT_TRUE(Reachables.has_value());
+  EXPECT_EQ(Reachables->size(), 2u);
+  EXPECT_TRUE(Reachables->count(1));
+  EXPECT_TRUE(Reachables->count(3));
+}
+
+} // namespace