https://github.com/ziqingluo-90 updated https://github.com/llvm/llvm-project/pull/193097
>From d0600970f2e6bce76595b3271a202560a3178b71 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Mon, 20 Apr 2026 14:03:58 -0700 Subject: [PATCH 1/8] [NFC][SSAF][EntityPointerLevel] Move EntityID-to-EPL map serialization to the EPL module Factor out the serialization of `std::map<EntityId, EntityPointerLevelSet>` to `EntityPointerLevelFormat.h`. --- .../EntityPointerLevelFormat.h | 14 ++++++ .../UnsafeBufferUsageAnalysis.h | 7 ++- .../EntityPointerLevel/EntityPointerLevel.cpp | 50 +++++++++++++++++++ .../UnsafeBufferUsageAnalysis.cpp | 48 +++--------------- 4 files changed, 77 insertions(+), 42 deletions(-) diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h index 13ecd880001e6..2b2caf8644bab 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h @@ -10,8 +10,10 @@ #define LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_ANALYSES_ENTITYPOINTERLEVEL_ENTITYPOINTERLEVELFORMAT_H #include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityId.h" #include "clang/ScalableStaticAnalysisFramework/Core/Serialization/JSONFormat.h" #include "llvm/ADT/iterator_range.h" +#include <map> namespace clang::ssaf { llvm::json::Value @@ -29,6 +31,18 @@ llvm::json::Array entityPointerLevelSetToJSON( Expected<EntityPointerLevelSet> entityPointerLevelSetFromJSON(const llvm::json::Array &EPLsData, JSONFormat::EntityIdFromJSONFn EntityIdFromJSON); + +/// Serialize a map<EntityId, EntityPointerLevelSet> as a flat array of +/// alternating [EntityId, EntityPointerLevelSet, ...] pairs. +llvm::json::Array entityPointerLevelMapToJSON( + const std::map<EntityId, EntityPointerLevelSet> &Map, + JSONFormat::EntityIdToJSONFn IdToJSON); + +/// Deserialize a flat array of alternating [EntityId, EntityPointerLevelSet, +/// ...] pairs into a map. +Expected<std::map<EntityId, EntityPointerLevelSet>> +entityPointerLevelMapFromJSON(const llvm::json::Array &Content, + JSONFormat::EntityIdFromJSONFn IdFromJSON); } // namespace clang::ssaf #endif // LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_ANALYSES_ENTITYPOINTERLEVEL_ENTITYPOINTERLEVELFORMAT_H diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h index aba566498b44b..9cfd59e5c0333 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h @@ -1,4 +1,4 @@ -//===- UnsafeBufferUsageAnalysis.h --------------------------------*- C++ -*-===// +//===- UnsafeBufferUsageAnalysis.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. @@ -23,7 +23,7 @@ namespace clang::ssaf { -inline constexpr llvm::StringLiteral UnsafeBufferUsageAnalysisResultName = +constexpr llvm::StringLiteral UnsafeBufferUsageAnalysisResultName = "UnsafeBufferUsageAnalysisResult"; struct UnsafeBufferUsageAnalysisResult final : AnalysisResult { @@ -33,6 +33,9 @@ struct UnsafeBufferUsageAnalysisResult final : AnalysisResult { /// Whole-program set of unsafe buffer pointers: std::map<EntityId, EntityPointerLevelSet> UnsafeBuffers; + + auto begin() const { return UnsafeBuffers.begin(); } + auto end() const { return UnsafeBuffers.end(); } }; } // namespace clang::ssaf diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp index fb47fd76241f0..1f4c1ac9f5328 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -14,6 +14,7 @@ #include "clang/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h" #include "clang/ScalableStaticAnalysisFramework/Core/ASTEntityMapping.h" #include "clang/ScalableStaticAnalysisFramework/Core/Model/EntityName.h" +#include <map> #include <optional> using namespace clang; @@ -328,3 +329,52 @@ Expected<EntityPointerLevelSet> clang::ssaf::entityPointerLevelSetFromJSON( } return EPLs; } + +llvm::json::Array clang::ssaf::entityPointerLevelMapToJSON( + const std::map<EntityId, EntityPointerLevelSet> &Map, + JSONFormat::EntityIdToJSONFn IdToJSON) { + llvm::json::Array Content; + + for (const auto &[Id, EPLs] : Map) { + Content.push_back(IdToJSON(Id)); + Content.push_back(entityPointerLevelSetToJSON(EPLs, IdToJSON)); + } + return Content; +} + +Expected<std::map<EntityId, EntityPointerLevelSet>> +clang::ssaf::entityPointerLevelMapFromJSON( + const llvm::json::Array &Content, + JSONFormat::EntityIdFromJSONFn IdFromJSON) { + if (Content.size() % 2 != 0) + return makeSawButExpectedError( + Content, "an even number of elements, got %zu", Content.size()); + + std::map<EntityId, EntityPointerLevelSet> Result; + + for (size_t I = 0; I < Content.size(); I += 2) { + const llvm::json::Object *IdData = Content[I].getAsObject(); + + if (!IdData) + return makeSawButExpectedError(Content[I], + "an object representing EntityId"); + + auto Id = IdFromJSON(*IdData); + + if (!Id) + return Id.takeError(); + + const llvm::json::Array *EPLsData = Content[I + 1].getAsArray(); + + if (!EPLsData) + return makeSawButExpectedError( + Content[I + 1], "an array representing EntityPointerLevelSet"); + + auto EPLs = entityPointerLevelSetFromJSON(*EPLsData, IdFromJSON); + + if (!EPLs) + return EPLs.takeError(); + Result[*Id] = std::move(*EPLs); + } + return Result; +} diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp index 5aa798dd5f8b1..d62c2b8bb47da 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp @@ -31,63 +31,31 @@ namespace { json::Object serializeUnsafeBufferUsageAnalysisResult( const UnsafeBufferUsageAnalysisResult &R, JSONFormat::EntityIdToJSONFn IdToJSON) { - json::Array Content; - - // Flat key-value pairs into an array of values: - for (auto &[Id, EPLs] : R.UnsafeBuffers) { - Content.push_back(IdToJSON(Id)); - Content.push_back(entityPointerLevelSetToJSON(EPLs, IdToJSON)); - } - json::Object Result; - Result[UnsafeBufferUsageAnalysisResultName] = std::move(Content); + Result[UnsafeBufferUsageAnalysisResultName] = + entityPointerLevelMapToJSON(R.UnsafeBuffers, IdToJSON); return Result; } Expected<std::unique_ptr<AnalysisResult>> deserializeUnsafeBufferUsageAnalysisResult( const json::Object &Obj, JSONFormat::EntityIdFromJSONFn IdFromJSON) { - const json::Array *Content = Obj.getArray(UnsafeBufferUsageAnalysisResultName); + const json::Array *Content = + Obj.getArray(UnsafeBufferUsageAnalysisResultName); if (!Content) return makeSawButExpectedError(Obj, "an object with a key %s", UnsafeBufferUsageAnalysisResultName.data()); - if (Content->size() % 2 != 0) - return makeSawButExpectedError( - *Content, "an even number of elements, got %zu", Content->size()); - - std::map<EntityId, EntityPointerLevelSet> UnsafeBuffers; - - for (size_t I = 0; I < Content->size(); I += 2) { - const json::Object *IdData = (*Content)[I].getAsObject(); - - if (!IdData) - return makeSawButExpectedError((*Content)[I], - "an object representing EntityId"); + auto UnsafeBuffers = entityPointerLevelMapFromJSON(*Content, IdFromJSON); - auto Id = IdFromJSON(*IdData); - - if (!Id) - return Id.takeError(); - - const json::Array *EPLsData = (*Content)[I + 1].getAsArray(); - - if (!EPLsData) - return makeSawButExpectedError( - (*Content)[I + 1], "an array representing EntityPointerLevelSet"); - - auto EPLs = entityPointerLevelSetFromJSON(*EPLsData, IdFromJSON); - - if (!EPLs) - return EPLs.takeError(); - UnsafeBuffers[*Id] = std::move(*EPLs); - } + if (!UnsafeBuffers) + return UnsafeBuffers.takeError(); auto Ret = std::make_unique<UnsafeBufferUsageAnalysisResult>(); - Ret->UnsafeBuffers = std::move(UnsafeBuffers); + Ret->UnsafeBuffers = std::move(*UnsafeBuffers); return Ret; } >From 1d2bb7759e817ccf8649310700c3e37940bee2b2 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Mon, 20 Apr 2026 14:12:34 -0700 Subject: [PATCH 2/8] [SSAF][Analysis] Add PointerFlowReachableAnalysis PointerFlowReachableAnalysis uses PointerFlow and UnsafeBufferUsage summaries. It computes reachable nodes in the PointerFlow graph from unsafe buffer nodes in the UnsafeBufferUsage summary. rdar://174874942 --- .../PointerFlow/PointerFlowAnalysis.h | 23 +- .../Analyses/PointerFlow/PointerFlowFormat.h | 2 +- .../EntityPointerLevel/EntityPointerLevel.cpp | 3 +- .../Analyses/PointerFlow/PointerFlow.cpp | 2 +- .../PointerFlow/PointerFlowAnalysis.cpp | 134 +++++- .../Analyses/SSAFAnalysesCommon.cpp | 12 + .../Analyses/SSAFAnalysesCommon.h | 18 +- .../CMakeLists.txt | 1 + .../PointerFlowReachableAnalysisTest.cpp | 433 ++++++++++++++++++ 9 files changed, 598 insertions(+), 30 deletions(-) create mode 100644 clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h index 85694c779adf4..0129c21501bcf 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h @@ -1,4 +1,4 @@ -//===- PointerFlowAnalysis.h -------------------------------------*- C++ -*-===// +//===- PointerFlowAnalysis.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. @@ -6,14 +6,18 @@ // //===----------------------------------------------------------------------===// // -// Defines PointerFlowAnalysisResult, the whole-program analysis result type -// for PointerFlowAnalysis. +// 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" @@ -23,18 +27,27 @@ namespace clang::ssaf { -inline constexpr llvm::StringLiteral PointerFlowAnalysisResultName = +constexpr llvm::StringLiteral PointerFlowAnalysisResultName = "PointerFlowAnalysisResult"; +constexpr llvm::StringLiteral PointerFlowReachableAnalysisResultName = + "PointerFlowReachableAnalysisResult"; struct PointerFlowAnalysisResult final : AnalysisResult { static AnalysisName analysisName() { return AnalysisName(PointerFlowAnalysisResultName.str()); } - /// Whole-program map from EntityIds to their EdgeSets. std::map<EntityId, EdgeSet> Edges; }; +struct PointerFlowReachableAnalysisResult final : AnalysisResult { + static AnalysisName analysisName() { + return AnalysisName(PointerFlowReachableAnalysisResultName.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/PointerFlow/PointerFlowFormat.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowFormat.h index 729bb21f91d9b..86bf1de4aaea2 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowFormat.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowFormat.h @@ -22,7 +22,7 @@ namespace clang::ssaf { /// Serialize an EdgeSet as an array of arrays of EntityPointerLevels: /// [ [lhs, rhs, rhs, ...], [lhs, rhs, rhs, ...], ... ] llvm::json::Array -edgeSetToJSON(const llvm::iterator_range<EdgeSet::const_iterator> &Edges, +edgeSetToJSON(llvm::iterator_range<EdgeSet::const_iterator> Edges, JSONFormat::EntityIdToJSONFn IdToJSON); /// Deserialize an EdgeSet from the array format produced by `edgeSetToJSON`. diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp index 1f4c1ac9f5328..97ff52cdb5055 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -348,7 +348,8 @@ clang::ssaf::entityPointerLevelMapFromJSON( JSONFormat::EntityIdFromJSONFn IdFromJSON) { if (Content.size() % 2 != 0) return makeSawButExpectedError( - Content, "an even number of elements, got %zu", Content.size()); + Content, "an even number of elements, got %lu", + static_cast<unsigned long>(Content.size())); std::map<EntityId, EntityPointerLevelSet> Result; diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.cpp index 4d629bb4b2c66..ce45f4167016f 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.cpp @@ -36,7 +36,7 @@ ssaf::getEdges(const PointerFlowEntitySummary &Sum) { } Array ssaf::edgeSetToJSON( - const llvm::iterator_range<EdgeSet::const_iterator> &Edges, + llvm::iterator_range<EdgeSet::const_iterator> Edges, JSONFormat::EntityIdToJSONFn EntityId2JSON) { Array EdgesData; diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp index 8dab98d783346..cbb9fdd779017 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp @@ -5,28 +5,36 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -// PointerFlowAnalysis is a noop analysis. -// -// PointerFlowAnalysisResult is a map from EntityIds to -// EdgeSets. -//===----------------------------------------------------------------------===// +#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/PointerFlowAnalysis.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" +#include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/DerivedAnalysis.h" #include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/SummaryAnalysis.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/STLFunctionalExtras.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Error.h" #include "llvm/Support/JSON.h" #include <memory> +#include <unordered_set> using namespace clang::ssaf; using namespace llvm; namespace { +//===----------------------------------------------------------------------===// +// PointerFlowAnalysis---a no-op analysis +//===----------------------------------------------------------------------===// + // Serialized as a flat array of alternating [EntityId, EdgesArray, ...] pairs. json::Object serializePointerFlowAnalysisResult(const PointerFlowAnalysisResult &R, @@ -54,7 +62,8 @@ Expected<std::unique_ptr<AnalysisResult>> deserializePointerFlowAnalysisResult( if (Content->size() % 2 != 0) return makeSawButExpectedError( - *Content, "an even number of elements, got %zu", Content->size()); + *Content, "an even number of elements, got %lu", + static_cast<unsigned long>(Content->size())); std::map<EntityId, EdgeSet> Edges; @@ -109,6 +118,117 @@ class PointerFlowAnalysis final AnalysisRegistry::Add<PointerFlowAnalysis> RegisterPointerFlowAnalysis("Whole-program pointer flow analysis"); +//===----------------------------------------------------------------------===// +// PointerFlowReachableAnalysis---computes reachable node +//===----------------------------------------------------------------------===// + +json::Object serializePointerFlowReachableAnalysisResult( + const PointerFlowReachableAnalysisResult &R, + JSONFormat::EntityIdToJSONFn IdToJSON) { + json::Object Result; + + Result[PointerFlowReachableAnalysisResultName] = + 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(PointerFlowReachableAnalysisResultName); + + if (!Content) + return makeSawButExpectedError( + Obj, "an object with a key %s", + PointerFlowReachableAnalysisResultName.data()); + + auto Reachables = entityPointerLevelMapFromJSON(*Content, IdFromJSON); + + if (!Reachables) + return Reachables.takeError(); + + auto Ret = std::make_unique<PointerFlowReachableAnalysisResult>(); + + Ret->Reachables = std::move(*Reachables); + return Ret; +} + +JSONFormat::AnalysisResultRegistry::Add<PointerFlowReachableAnalysisResult> + RegisterPointerFlowReachableResultForJSON( + serializePointerFlowReachableAnalysisResult, + deserializePointerFlowReachableAnalysisResult); + +// For any AnalysisResult that is a set of pointers, it can be the starting set +// for reachable analysis. +template <typename AnalysisResultInPointerSet> +class PointerFlowReachableAnalysis + : public DerivedAnalysis<PointerFlowReachableAnalysisResult, + PointerFlowAnalysisResult, + AnalysisResultInPointerSet> { + 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->result().Reachables[Id].insert(EPL); + if (Inserted) + WorkList.push_back(&EPL); + } + } + } + } + +public: + // FIXME: we need a unique analysis name for each instantiation + + llvm::Error initialize(const PointerFlowAnalysisResult &Graph, + const AnalysisResultInPointerSet &Starter) override { + this->Graph = &Graph.Edges; + assert(this->result().Reachables.empty()); + this->result().Reachables.insert(Starter.begin(), Starter.end()); + return llvm::Error::success(); + } + + llvm::Expected<bool> step() override { + auto &Reachables = this->result().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< + PointerFlowReachableAnalysis<UnsafeBufferUsageAnalysisResult>> + RegisterPointerFlowReachableAnalysis( + "Reachable pointers from unsafe buffer usage in pointer flow graph"); + } // namespace // NOLINTNEXTLINE(misc-use-internal-linkage) diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.cpp index 774e7e94ac67a..cbd8ac92c5eaf 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.cpp @@ -10,6 +10,18 @@ using namespace clang; +std::string describeJSONValue(const llvm::json::Value &V) { + return llvm::formatv("{0:2}", V).str(); +} + +std::string describeJSONValue(const llvm::json::Array &A) { + return llvm::formatv("array of size {0}", A.size()).str(); +} + +std::string describeJSONValue(const llvm::json::Object &O) { + return llvm::formatv("an object of {0} key(s)", O.size()).str(); +} + namespace { // Traverses the AST and finds contributors. class ContributorFinder : public DynamicRecursiveASTVisitor { diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.h b/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.h index 7eb78d32bfdfb..c798789fd12a8 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.h +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/SSAFAnalysesCommon.h @@ -16,21 +16,9 @@ #include "clang/AST/Decl.h" #include "llvm/Support/JSON.h" -inline std::string describeJSONValue(const llvm::json::Value &V) { - return llvm::formatv("{0:2}", V).str(); -} - -/// Return a short description of a JSON array suitable for -/// diagnostics. -inline std::string describeJSONValue(const llvm::json::Array &A) { - return llvm::formatv("array of size {0}", A.size()).str(); -} - -/// Return a short description of a JSON object suitable for -/// diagnostics. -inline std::string describeJSONValue(const llvm::json::Object &O) { - return llvm::formatv("an object of {0} key(s)", O.size()).str(); -} +std::string describeJSONValue(const llvm::json::Value &V); +std::string describeJSONValue(const llvm::json::Array &A); +std::string describeJSONValue(const llvm::json::Object &O); template <typename NodeTy, typename... Ts> llvm::Error makeErrAtNode(clang::ASTContext &Ctx, const NodeTy *N, diff --git a/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt b/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt index d853dd1b79df5..6d2a009da994e 100644 --- a/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt +++ b/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt @@ -26,6 +26,7 @@ add_distinct_clang_unittest(ClangScalableAnalysisTests TestFixture.cpp TUSummaryBuilderTest.cpp WholeProgramAnalysis/AnalysisDriverTest.cpp + WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp CLANG_LIBS clangAST diff --git a/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp new file mode 100644 index 0000000000000..51b8c083d294e --- /dev/null +++ b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp @@ -0,0 +1,433 @@ +//===- PointerFlowReachableAnalysisTest.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 PointerFlowReachableAnalysisTest : 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, + PointerFlowReachableAnalysisResult>(); + if (!WPAOrErr) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(WPAOrErr.takeError()); + return std::nullopt; + } + auto ROrErr = WPAOrErr->get<PointerFlowReachableAnalysisResult>(); + 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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(PointerFlowReachableAnalysisTest, 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 >From 968b8b018af40b234ba5f080f92f2fc9989fd1c1 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Wed, 22 Apr 2026 13:35:47 -0700 Subject: [PATCH 3/8] change 'result()' to 'getResult()' --- .../Analyses/PointerFlow/PointerFlowAnalysis.cpp | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp index ec76d7ad9c3d7..32b2b8487e121 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp @@ -109,7 +109,7 @@ class PointerFlowAnalysis final const PointerFlowEntitySummary &Summary) override { auto EdgesOfEntity = getEdges(Summary); - getResult().Edges[Id] = EdgeSet(EdgesOfEntity.begin(), EdgesOfEntity.end()); + this->getResult().Edges[Id] = EdgeSet(EdgesOfEntity.begin(), EdgesOfEntity.end()); return llvm::Error::success(); } }; @@ -185,7 +185,7 @@ class PointerFlowReachableAnalysis if (I != SubGraph.end()) { for (const auto &EPL : I->second) { - auto [Ignored, Inserted] = this->result().Reachables[Id].insert(EPL); + auto [Ignored, Inserted] = this->getResult().Reachables[Id].insert(EPL); if (Inserted) WorkList.push_back(&EPL); } @@ -199,13 +199,13 @@ class PointerFlowReachableAnalysis llvm::Error initialize(const PointerFlowAnalysisResult &Graph, const AnalysisResultInPointerSet &Starter) override { this->Graph = &Graph.Edges; - assert(this->result().Reachables.empty()); - this->result().Reachables.insert(Starter.begin(), Starter.end()); + 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->result().Reachables; + auto &Reachables = this->getResult().Reachables; // Simple DFS: std::vector<EPLPtr> Worklist; >From 33ad3b4d74f9e30e4752b28619a9878fb76991bc Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Wed, 22 Apr 2026 13:47:30 -0700 Subject: [PATCH 4/8] fix clang-format --- .../Analyses/PointerFlow/PointerFlowAnalysis.cpp | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp index 32b2b8487e121..ef5f1d2839c53 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp @@ -109,7 +109,8 @@ class PointerFlowAnalysis final const PointerFlowEntitySummary &Summary) override { auto EdgesOfEntity = getEdges(Summary); - this->getResult().Edges[Id] = EdgeSet(EdgesOfEntity.begin(), EdgesOfEntity.end()); + this->getResult().Edges[Id] = + EdgeSet(EdgesOfEntity.begin(), EdgesOfEntity.end()); return llvm::Error::success(); } }; @@ -185,7 +186,8 @@ class PointerFlowReachableAnalysis if (I != SubGraph.end()) { for (const auto &EPL : I->second) { - auto [Ignored, Inserted] = this->getResult().Reachables[Id].insert(EPL); + auto [Ignored, Inserted] = + this->getResult().Reachables[Id].insert(EPL); if (Inserted) WorkList.push_back(&EPL); } >From cc65737e3c6db5f1f81c365d39d6d17baca09dac Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Fri, 24 Apr 2026 18:35:15 -0700 Subject: [PATCH 5/8] address comments --- .../PointerFlow/PointerFlowAnalysis.h | 8 +-- .../PointerFlow/PointerFlowAnalysis.cpp | 34 ++++++------- .../CMakeLists.txt | 2 +- ... => UnsafeBufferReachableAnalysisTest.cpp} | 51 +++++++++++-------- 4 files changed, 51 insertions(+), 44 deletions(-) rename clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/{PointerFlowReachableAnalysisTest.cpp => UnsafeBufferReachableAnalysisTest.cpp} (88%) diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h index 0129c21501bcf..e862df58a8200 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h @@ -29,8 +29,8 @@ namespace clang::ssaf { constexpr llvm::StringLiteral PointerFlowAnalysisResultName = "PointerFlowAnalysisResult"; -constexpr llvm::StringLiteral PointerFlowReachableAnalysisResultName = - "PointerFlowReachableAnalysisResult"; +constexpr llvm::StringLiteral UnsafeBufferReachableAnalysisResultName = + "UnsafeBufferReachableAnalysisResult"; struct PointerFlowAnalysisResult final : AnalysisResult { static AnalysisName analysisName() { @@ -40,9 +40,9 @@ struct PointerFlowAnalysisResult final : AnalysisResult { std::map<EntityId, EdgeSet> Edges; }; -struct PointerFlowReachableAnalysisResult final : AnalysisResult { +struct UnsafeBufferReachableAnalysisResult final : AnalysisResult { static AnalysisName analysisName() { - return AnalysisName(PointerFlowReachableAnalysisResultName.str()); + return AnalysisName(UnsafeBufferReachableAnalysisResultName.str()); } std::map<EntityId, EntityPointerLevelSet> Reachables; diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp index ef5f1d2839c53..83652c2f1147f 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp @@ -123,11 +123,11 @@ AnalysisRegistry::Add<PointerFlowAnalysis> //===----------------------------------------------------------------------===// json::Object serializePointerFlowReachableAnalysisResult( - const PointerFlowReachableAnalysisResult &R, + const UnsafeBufferReachableAnalysisResult &R, JSONFormat::EntityIdToJSONFn IdToJSON) { json::Object Result; - Result[PointerFlowReachableAnalysisResultName] = + Result[UnsafeBufferReachableAnalysisResultName] = entityPointerLevelMapToJSON(R.Reachables, IdToJSON); return Result; } @@ -136,36 +136,36 @@ Expected<std::unique_ptr<AnalysisResult>> deserializePointerFlowReachableAnalysisResult( const json::Object &Obj, JSONFormat::EntityIdFromJSONFn IdFromJSON) { const json::Array *Content = - Obj.getArray(PointerFlowReachableAnalysisResultName); + Obj.getArray(UnsafeBufferReachableAnalysisResultName); if (!Content) return makeSawButExpectedError( Obj, "an object with a key %s", - PointerFlowReachableAnalysisResultName.data()); + UnsafeBufferReachableAnalysisResultName.data()); auto Reachables = entityPointerLevelMapFromJSON(*Content, IdFromJSON); if (!Reachables) return Reachables.takeError(); - auto Ret = std::make_unique<PointerFlowReachableAnalysisResult>(); + auto Ret = std::make_unique<UnsafeBufferReachableAnalysisResult>(); Ret->Reachables = std::move(*Reachables); return Ret; } -JSONFormat::AnalysisResultRegistry::Add<PointerFlowReachableAnalysisResult> +JSONFormat::AnalysisResultRegistry::Add<UnsafeBufferReachableAnalysisResult> RegisterPointerFlowReachableResultForJSON( serializePointerFlowReachableAnalysisResult, deserializePointerFlowReachableAnalysisResult); -// For any AnalysisResult that is a set of pointers, it can be the starting set -// for reachable analysis. -template <typename AnalysisResultInPointerSet> -class PointerFlowReachableAnalysis - : public DerivedAnalysis<PointerFlowReachableAnalysisResult, +/// 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, - AnalysisResultInPointerSet> { + UnsafeBufferUsageAnalysisResult> { using GraphT = std::map<EntityId, EdgeSet>; const GraphT *Graph = nullptr; @@ -196,10 +196,9 @@ class PointerFlowReachableAnalysis } public: - // FIXME: we need a unique analysis name for each instantiation - - llvm::Error initialize(const PointerFlowAnalysisResult &Graph, - const AnalysisResultInPointerSet &Starter) override { + 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()); @@ -225,8 +224,7 @@ class PointerFlowReachableAnalysis } }; -AnalysisRegistry::Add< - PointerFlowReachableAnalysis<UnsafeBufferUsageAnalysisResult>> +AnalysisRegistry::Add<UnsafeBufferReachableAnalysis> RegisterPointerFlowReachableAnalysis( "Reachable pointers from unsafe buffer usage in pointer flow graph"); diff --git a/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt b/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt index 6d2a009da994e..992a9eb0f285e 100644 --- a/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt +++ b/clang/unittests/ScalableStaticAnalysisFramework/CMakeLists.txt @@ -26,7 +26,7 @@ add_distinct_clang_unittest(ClangScalableAnalysisTests TestFixture.cpp TUSummaryBuilderTest.cpp WholeProgramAnalysis/AnalysisDriverTest.cpp - WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp + WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp CLANG_LIBS clangAST diff --git a/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp similarity index 88% rename from clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp rename to clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp index 51b8c083d294e..1e45e151dceab 100644 --- a/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/PointerFlowReachableAnalysisTest.cpp +++ b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp @@ -1,4 +1,5 @@ -//===- PointerFlowReachableAnalysisTest.cpp -------------------------------===// +//===- 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. @@ -74,7 +75,7 @@ static std::vector<PartitionT> enumeratePartition(unsigned N, unsigned NumGrps, return Partitions; } -class PointerFlowReachableAnalysisTest : public TestFixture { +class UnsafeBufferReachableAnalysisTest : public TestFixture { protected: using EPLEdge = std::pair<EntityPointerLevel, EntityPointerLevel>; @@ -150,12 +151,12 @@ class PointerFlowReachableAnalysisTest : public TestFixture { AnalysisDriver Driver(std::move(LU)); auto WPAOrErr = Driver.run<PointerFlowAnalysisResult, UnsafeBufferUsageAnalysisResult, - PointerFlowReachableAnalysisResult>(); + UnsafeBufferReachableAnalysisResult>(); if (!WPAOrErr) { ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(WPAOrErr.takeError()); return std::nullopt; } - auto ROrErr = WPAOrErr->get<PointerFlowReachableAnalysisResult>(); + auto ROrErr = WPAOrErr->get<UnsafeBufferReachableAnalysisResult>(); if (!ROrErr) { ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(ROrErr.takeError()); return std::nullopt; @@ -232,11 +233,19 @@ class PointerFlowReachableAnalysisTest : public TestFixture { } }; -//- Test different graph topologic structures ----------------------// +//////////////////////////////////////////////////////////////////////////////// +// Tests below are written in a manner that focuses on pointer flow graph +// topology and the starter set, where numbers are used to represent distinct +// nodes (pointers). +// For example, `LinearChain` tests a graph forming a +// linear chain with 4 distinct nodes: 0 -> 1 -> 2 -> 3 with a starter set {0}, +// where, for example, 0 -> 1 represents an edge where node 0 is the source and +// node 1 is the destination. Thus, {0, 1, 2, 3} is the expected reachable set. +//////////////////////////////////////////////////////////////////////////////// // Linear chain: 0 -> 1 -> 2 -> 3. // Start from {0} => {0, 1, 2, 3} -TEST_F(PointerFlowReachableAnalysisTest, LinearChain) { +TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {1, 2}, {2, 3}}, @@ -247,7 +256,7 @@ TEST_F(PointerFlowReachableAnalysisTest, LinearChain) { // Linear chain: 0 -> 1 -> 2 -> 3. // Start from mid-chain {2} => {2, 3} -TEST_F(PointerFlowReachableAnalysisTest, LinearChainFromMiddle) { +TEST_F(UnsafeBufferReachableAnalysisTest, LinearChainFromMiddle) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {1, 2}, {2, 3}}, @@ -260,7 +269,7 @@ TEST_F(PointerFlowReachableAnalysisTest, LinearChainFromMiddle) { // Diamond: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. // Start from {0} => {0, 1, 2, 3} -TEST_F(PointerFlowReachableAnalysisTest, Diamond) { +TEST_F(UnsafeBufferReachableAnalysisTest, Diamond) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {0, 2}, {1, 3}, {2, 3}}, @@ -271,7 +280,7 @@ TEST_F(PointerFlowReachableAnalysisTest, Diamond) { // Diamond: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. // Start from one branch {1} => {1, 3} -TEST_F(PointerFlowReachableAnalysisTest, DiamondFromBranch) { +TEST_F(UnsafeBufferReachableAnalysisTest, DiamondFromBranch) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {0, 2}, {1, 3}, {2, 3}}, @@ -284,7 +293,7 @@ TEST_F(PointerFlowReachableAnalysisTest, DiamondFromBranch) { // Disconnected subgraphs: 0 -> 1, 2 -> 3. // Start from {0} => {0, 1} -TEST_F(PointerFlowReachableAnalysisTest, DisconnectedSubgraphs) { +TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphs) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {2, 3}}, @@ -297,7 +306,7 @@ TEST_F(PointerFlowReachableAnalysisTest, DisconnectedSubgraphs) { // Disconnected subgraphs: 0 -> 1, 2 -> 3. // Start from tail {1} => {1} -TEST_F(PointerFlowReachableAnalysisTest, DisconnectedSubgraphsFromTail) { +TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphsFromTail) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {2, 3}}, @@ -309,7 +318,7 @@ TEST_F(PointerFlowReachableAnalysisTest, DisconnectedSubgraphsFromTail) { // Cycle: 0 -> 1 -> 2 -> 3 -> 0. // Start from {2} => {0, 1, 2, 3} -TEST_F(PointerFlowReachableAnalysisTest, Cycle) { +TEST_F(UnsafeBufferReachableAnalysisTest, Cycle) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {1, 2}, {2, 3}, {3, 0}}, @@ -323,7 +332,7 @@ TEST_F(PointerFlowReachableAnalysisTest, Cycle) { } // Empty graph: no edges, start from {0} => {0} -TEST_F(PointerFlowReachableAnalysisTest, EmptyGraph) { +TEST_F(UnsafeBufferReachableAnalysisTest, EmptyGraph) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {}, @@ -335,7 +344,7 @@ TEST_F(PointerFlowReachableAnalysisTest, EmptyGraph) { // Star: 0 -> 1, 0 -> 2, 0 -> 3. // Start from {0} => {0, 1, 2, 3} -TEST_F(PointerFlowReachableAnalysisTest, StarFromHub) { +TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {0, 2}, {0, 3}}, @@ -346,7 +355,7 @@ TEST_F(PointerFlowReachableAnalysisTest, StarFromHub) { // Star: 0 -> 1, 0 -> 2, 0 -> 3. // Start from leaf {2} => {2} -TEST_F(PointerFlowReachableAnalysisTest, StarFromLeaf) { +TEST_F(UnsafeBufferReachableAnalysisTest, StarFromLeaf) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {0, 2}, {0, 3}}, @@ -358,7 +367,7 @@ TEST_F(PointerFlowReachableAnalysisTest, StarFromLeaf) { // Reverse star: 0 -> 3, 1 -> 3, 2 -> 3. // Start from {0} => {0, 3} -TEST_F(PointerFlowReachableAnalysisTest, ReverseStarFromSource) { +TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSource) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 3}, {1, 3}, {2, 3}}, @@ -371,7 +380,7 @@ TEST_F(PointerFlowReachableAnalysisTest, ReverseStarFromSource) { // Reverse star: 0 -> 3, 1 -> 3, 2 -> 3. // Start from sink {3} => {3} -TEST_F(PointerFlowReachableAnalysisTest, ReverseStarFromSink) { +TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSink) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 3}, {1, 3}, {2, 3}}, @@ -383,7 +392,7 @@ TEST_F(PointerFlowReachableAnalysisTest, ReverseStarFromSink) { // Self-loop: 0 -> 1, 1 -> 1, 1 -> 2, 2 -> 3. // Start from {0} => {0, 1, 2, 3} -TEST_F(PointerFlowReachableAnalysisTest, SelfLoopFromRoot) { +TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromRoot) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {1, 1}, {1, 2}, {2, 3}}, @@ -394,7 +403,7 @@ TEST_F(PointerFlowReachableAnalysisTest, SelfLoopFromRoot) { // Self-loop: 0 -> 1, 1 -> 1, 1 -> 2, 2 -> 3. // Start from {1} => {1, 2, 3} -TEST_F(PointerFlowReachableAnalysisTest, SelfLoopFromLoopNode) { +TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromLoopNode) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {1, 1}, {1, 2}, {2, 3}}, @@ -408,7 +417,7 @@ TEST_F(PointerFlowReachableAnalysisTest, SelfLoopFromLoopNode) { // Multiple starters: 0 -> 1, 2 -> 3 (disconnected). // Start from {0, 2} => {0, 1, 2, 3} -TEST_F(PointerFlowReachableAnalysisTest, MultipleStartersBothChains) { +TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersBothChains) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {2, 3}}, @@ -419,7 +428,7 @@ TEST_F(PointerFlowReachableAnalysisTest, MultipleStartersBothChains) { // Multiple starters: 0 -> 1, 2 -> 3 (disconnected). // Start from leaves {1, 3} => {1, 3} -TEST_F(PointerFlowReachableAnalysisTest, MultipleStartersLeaves) { +TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersLeaves) { auto Reachables = forEachPartition( /* NumEnt */ 4, /* EdgeLayout */ {{0, 1}, {2, 3}}, >From dc23c153faa137542d42aa21e2866e67319e5801 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Thu, 30 Apr 2026 14:56:22 -0700 Subject: [PATCH 6/8] Update clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h Co-authored-by: Jan Korous <[email protected]> --- .../Analyses/PointerFlow/PointerFlowAnalysis.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h index e862df58a8200..372ddc5db9103 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h @@ -1,4 +1,4 @@ -//===- PointerFlowAnalysis.h ------------------------------------*- C++-*-===// +//===- PointerFlowAnalysis.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. >From 86d58b2682a4a4b533d08859a03282ccdf5375c8 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Thu, 30 Apr 2026 16:14:53 -0700 Subject: [PATCH 7/8] address comments --- .../Analyses/PointerFlow/PointerFlowAnalysis.h | 10 ++++++++++ .../Analyses/PointerFlow/PointerFlowAnalysis.cpp | 16 ++++++++-------- 2 files changed, 18 insertions(+), 8 deletions(-) diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h index e862df58a8200..923661e61248f 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h @@ -32,6 +32,16 @@ constexpr llvm::StringLiteral PointerFlowAnalysisResultName = constexpr llvm::StringLiteral UnsafeBufferReachableAnalysisResultName = "UnsafeBufferReachableAnalysisResult"; +/// A PointerFlowAnalysisResult is a set of pointer-flow edges, i.e., +/// a pointer-flow graph. A directed edge src -> dest corresponds to an +/// assignment (of any of various kinds, e.g., assignment operator or +/// argument-passing) of pointer dest to pointer src in the source code. +/// The edge's direction is the opposite of how pointer values flow. This +/// is because PointerFlowAnalysisResult is used for analyzing property +/// propagation between pointers. For an assignment `src = dest`, the +/// propagation works such that if `src` has a property, `dest` must also +/// have that property; otherwise, the property would not be preserved +/// across the assignment. struct PointerFlowAnalysisResult final : AnalysisResult { static AnalysisName analysisName() { return AnalysisName(PointerFlowAnalysisResultName.str()); diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp index 83652c2f1147f..d5ca9f41e01b5 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp @@ -31,7 +31,8 @@ using namespace llvm; namespace { //===----------------------------------------------------------------------===// -// PointerFlowAnalysis---a no-op analysis +// PointerFlowAnalysis---converts PointerFlowEntitySummary(s) in an LUSummary to +// a PointerFlowAnalysisResult //===----------------------------------------------------------------------===// // Serialized as a flat array of alternating [EntityId, EdgesArray, ...] pairs. @@ -109,8 +110,7 @@ class PointerFlowAnalysis final const PointerFlowEntitySummary &Summary) override { auto EdgesOfEntity = getEdges(Summary); - this->getResult().Edges[Id] = - EdgeSet(EdgesOfEntity.begin(), EdgesOfEntity.end()); + getResult().Edges[Id] = EdgeSet(EdgesOfEntity.begin(), EdgesOfEntity.end()); return llvm::Error::success(); } }; @@ -186,8 +186,7 @@ class UnsafeBufferReachableAnalysis if (I != SubGraph.end()) { for (const auto &EPL : I->second) { - auto [Ignored, Inserted] = - this->getResult().Reachables[Id].insert(EPL); + auto [Ignored, Inserted] = getResult().Reachables[Id].insert(EPL); if (Inserted) WorkList.push_back(&EPL); } @@ -200,13 +199,13 @@ class UnsafeBufferReachableAnalysis 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()); + assert(getResult().Reachables.empty()); + getResult().Reachables.insert(Starter.begin(), Starter.end()); return llvm::Error::success(); } llvm::Expected<bool> step() override { - auto &Reachables = this->getResult().Reachables; + auto &Reachables = getResult().Reachables; // Simple DFS: std::vector<EPLPtr> Worklist; @@ -220,6 +219,7 @@ class UnsafeBufferReachableAnalysis updateReachablesWithOutgoings(Node, Worklist); } + // This is not an iterative algorithm so stop iteration by retruning false: return false; } }; >From 6a1afd4f754890d931c3a294212ecabc60b1b401 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Thu, 30 Apr 2026 16:45:59 -0700 Subject: [PATCH 8/8] continue to address comments --- .../Analyses/PointerFlow/PointerFlowAnalysis.h | 9 +++++---- .../Analyses/PointerFlow/PointerFlowAnalysis.cpp | 4 ---- 2 files changed, 5 insertions(+), 8 deletions(-) diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h index b965dbf13a94e..5b2e534368f98 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h @@ -7,10 +7,11 @@ //===----------------------------------------------------------------------===// // // 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. +// - 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. // //===----------------------------------------------------------------------===// diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp index d5ca9f41e01b5..c3916b38ae7ff 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.cpp @@ -23,7 +23,6 @@ #include "llvm/Support/Error.h" #include "llvm/Support/JSON.h" #include <memory> -#include <unordered_set> using namespace clang::ssaf; using namespace llvm; @@ -172,9 +171,6 @@ class UnsafeBufferReachableAnalysis // 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 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
