Author: Ziqing Luo Date: 2026-05-26T11:55:19-07:00 New Revision: 631d16eaaa88ab76feaa6c672ce4a4ca4bfcf14b
URL: https://github.com/llvm/llvm-project/commit/631d16eaaa88ab76feaa6c672ce4a4ca4bfcf14b DIFF: https://github.com/llvm/llvm-project/commit/631d16eaaa88ab76feaa6c672ce4a4ca4bfcf14b.diff LOG: [SSAF][WPA] Bounds propagation graph is a supergraph of the pointer-flow graph (#198889) Background: The whole-program UnsafeBufferReachableAnalysis propagates bounds between pointers. It uses the pointer-flow graph extracted and linked from translation units. This commit patches the gap between the semantics of bounds propagation and pointer-flow: the bounds propagation graph is a super graph of the pointer-flow graph in that a pointer-flow graph edge `(src, i) -> (dst, j)` is the projection of a finite set of bounds propagation graph edges `{(src, i+d) -> (dst, j+d) | 0 <= d < UB}` for a small constant upper bound UB. See the following example for the idea: ``` void f(int ***p, int **q) { *p = q; (**p)[5] = 0; } ``` There is one edge for the static pointer assignment: '(p, 2) -> (q, 1)'. In terms of bounds propagation, this assignment implies that if 'p' at pointer level 2 requires bounds, 'q' at pointer level 1 must also have them. Furthermore, this relationship propagates to deeper indirection levels: if 'p' at level 3 requires bounds (due to '(**p)[5]'), so does 'q' at level 2. Added: Modified: clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp Removed: ################################################################################ diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h index eda7f138d9e9b..2b5bcfc650486 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlow.h @@ -6,9 +6,9 @@ // //===----------------------------------------------------------------------===// // -// This file defines an analysis that builds directed graphs where nodes -// are pointers and edges are assignment operations, each of which bridges two -// nodes. +// This file defines the per-translation-unit summary type for the +// pointer-flow analysis, which records static pointer assignment sites +// as directed graph edges (EdgeSet). // //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_SCALABLESTATICANALYSISFRAMEWORK_ANALYSES_POINTERFLOW_POINTERFLOW_H @@ -19,7 +19,8 @@ namespace clang::ssaf { -/// Maps each source node to its destination nodes: +/// Maps each LHS pointer (source / assignee) to the set of RHS pointers +/// (destinations / assigned values) at static assignment sites. using EdgeSet = std::map<EntityPointerLevel, EntityPointerLevelSet>; class PointerFlowEntitySummary final : public EntitySummary { diff --git a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h index f0d5c779a3298..38cbd7d634895 100644 --- a/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h +++ b/clang/include/clang/ScalableStaticAnalysisFramework/Analyses/PointerFlow/PointerFlowAnalysis.h @@ -6,9 +6,8 @@ // //===----------------------------------------------------------------------===// // -// Defines -// - PointerFlowAnalysisResult -// - the plain PointerFlow info collected from the whole program. +// Defines PointerFlowAnalysisResult — the whole-program pointer-flow graph +// aggregated from per-translation-unit EdgeSet summaries. // //===----------------------------------------------------------------------===// @@ -27,16 +26,13 @@ namespace clang::ssaf { constexpr llvm::StringLiteral PointerFlowAnalysisResultName = "PointerFlowAnalysisResult"; -/// 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. +/// The whole-program pointer-flow graph. Each directed edge 'src -> dest' +/// records a static assignment site where 'src' (the LHS / assignee) is +/// assigned the value of 'dest' (the RHS / assigned value). +/// +/// This edge direction matches property-propagation direction: if a property +/// (such as a bounds requirement) holds for 'src', it must also hold for +/// 'dest', because 'dest' supplies the value that 'src' will hold. struct PointerFlowAnalysisResult final : AnalysisResult { static AnalysisName analysisName() { return AnalysisName(PointerFlowAnalysisResultName.str()); diff --git a/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp index b7a913d627022..b141ca6cf829c 100644 --- a/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysisFramework/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp @@ -131,11 +131,64 @@ 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. + /// BoundsPropagationGraph adds bounds propagation semantics to the + /// pointer-flow graph, which represents the set of static pointer assignment + /// sites collected from the source code. Consider the following example: + /// + /// void f(int ***p, int **q) { + /// *p = q; + /// (**p)[5] = 0; + /// } + /// + /// There is one static pointer assignment thus one pointer-flow edge: (p, 2) + /// -> (q, 1). In terms of bounds propagation, this assignment implies that if + /// 'p' at pointer level 2 requires bounds, 'q' at pointer level 1 must also + /// have them. Furthermore, this relationship propagates to deeper indirection + /// levels: if 'p' at level 3 requires bounds, so does 'q' at level 2. + /// + /// In the example above, `(**p)` requires bounds (due to the array index), + /// and therefore `*q` must require bounds as well. + /// + /// To generalize the idea, the BoundsPropagationGraph is defined as a super + /// graph of the input pointer-flow graph by: + /// + /// For each edge (src, i) -> (dest, j) in the pointer-flow graph, the + /// BoundsPropagationGraph has a finite set of edges + /// {(src, i + d) -> (dest, j + d) | 0 <= d < UB}, where UB is an upper + /// bound based on the maximum pointer level the pointer type can have. + struct BoundsPropagationGraph { + private: + const std::map<EntityPointerLevel, EntityPointerLevelSet> &PointerFlows; + + public: + BoundsPropagationGraph(const EdgeSet &PointerFlows) + : PointerFlows(PointerFlows) {} + + /// Returns the EntityPointerLevelSet that are reachable from \p Src by + /// one edge in the BoundsPropagationGraph. + EntityPointerLevelSet getDestNodes(const EntityPointerLevel &Src) const { + unsigned SrcPtrLv = Src.getPointerLevel(); + EntityPointerLevelSet Result; + + for (unsigned P = 1; P <= SrcPtrLv; ++P) { + auto I = PointerFlows.find(buildEntityPointerLevel(Src.getEntity(), P)); + + if (I != PointerFlows.end()) { + unsigned Delta = SrcPtrLv - P; + for (const auto &EPL : I->second) + Result.insert(buildEntityPointerLevel( + EPL.getEntity(), EPL.getPointerLevel() + Delta)); + } + } + return Result; + } + }; + + std::map<EntityId, BoundsPropagationGraph> BPG; + + // Use pointers for efficiency. EPLs are in tree-based containers that only + // grow. So pointers to them are stable. using EPLPtr = const EntityPointerLevel *; // Find all outgoing edges from `EPL` in the `Graph`, insert their @@ -143,25 +196,23 @@ class UnsafeBufferReachableAnalysis // `Worklist`: void updateReachablesWithOutgoings(EPLPtr EPL, std::vector<EPLPtr> &WorkList) { - for (auto &[Id, SubGraph] : *Graph) { - auto I = SubGraph.find(*EPL); - EntityPointerLevelSet &ReachablesOfId = getResult().Reachables[Id]; - - if (I != SubGraph.end()) { - for (const auto &EPL : I->second) { - auto [Ignored, Inserted] = ReachablesOfId.insert(EPL); - if (Inserted) - WorkList.push_back(&EPL); - } + for (auto &[Id, SubGraph] : BPG) { + auto R = SubGraph.getDestNodes(*EPL); + + for (const auto &Dst : R) { + auto [It, Inserted] = getResult().Reachables[Id].insert(Dst); + if (Inserted) + WorkList.push_back(&*It); } } } public: llvm::Error - initialize(const PointerFlowAnalysisResult &Graph, + initialize(const PointerFlowAnalysisResult &PtrFlowGraph, const UnsafeBufferUsageAnalysisResult &Starter) override { - this->Graph = &Graph.Edges; + for (auto &[Id, SubGraph] : PtrFlowGraph.Edges) + BPG.try_emplace(Id, BoundsPropagationGraph(SubGraph)); assert(getResult().Reachables.empty()); getResult().Reachables.insert(Starter.begin(), Starter.end()); return llvm::Error::success(); diff --git a/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp index c3a98b6b8e87d..1ad0bcd2a04d5 100644 --- a/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp +++ b/clang/unittests/ScalableStaticAnalysisFramework/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp @@ -19,7 +19,7 @@ #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 "llvm/ADT/ArrayRef.h" #include "gtest/gtest.h" #include <map> #include <memory> @@ -73,21 +73,29 @@ class UnsafeBufferReachableAnalysisTest : public TestFixture { 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; - } + class LetterEntityBiMap { + std::map<char, EntityId> Forward; + std::map<EntityId, char> Reverse; + + public: + void insert(char C, EntityId Id) { + Forward.try_emplace(C, Id); + Reverse[Id] = C; + } - /// 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; + EntityId operator[](char C) const { return Forward.at(C); } + char operator[](EntityId Id) const { return Reverse.at(Id); } + size_t size() const { return Forward.size(); } + }; + + /// Create entities for the entity domain \p EntDom in \p LU. For simplicity, + /// entities are given by letters in \p EntDom. Return a "bi-directional map" + /// between letters and EntityIds. + LetterEntityBiMap createEntities(LUSummary &LU, llvm::ArrayRef<char> EntDom) { + LetterEntityBiMap Result; + for (char Name : EntDom) + Result.insert(Name, addEntity(LU, ("E" + llvm::Twine(Name)).str())); + return Result; } /// Insert both PointerFlow and UnsafeBufferUsage summaries for an entity @@ -128,6 +136,9 @@ class UnsafeBufferReachableAnalysisTest : public TestFixture { return Result; } + using Node = std::pair<char, unsigned>; + using Edge = std::pair<Node, Node>; + // FIXME: When we use more advanced search algorithms, it may involve // a divide-and-conquer approach on sub-graphs organized by contributors. // In that case, we may want to enumerate all possible partitions of @@ -135,244 +146,436 @@ class UnsafeBufferReachableAnalysisTest : public TestFixture { // `singlePartition`. /// Compute reachables from \p StarterLayout in the graph defined by \p - /// EdgeLayout. Edges and starters are all belong to Entity 0. - std::optional<std::set<unsigned>> - singlePartition(unsigned NumEnt, - llvm::ArrayRef<std::pair<unsigned, unsigned>> EdgeLayout, - llvm::ArrayRef<unsigned> StarterLayout, unsigned Line) { + /// EdgeLayout. Edges and starters are all belong to one contributor. + std::set<Node> singlePartition(llvm::ArrayRef<char> EntityDomain, + llvm::ArrayRef<Edge> EdgeLayout, + llvm::ArrayRef<Node> StarterLayout, + unsigned Line) { auto LU = makeLUSummary(); - auto Entities = createEntities(*LU, NumEnt); - auto N = createEPLs(Entities); + auto Entities = createEntities(*LU, EntityDomain); + auto GetEPL = [&Entities](const Node &N) -> EntityPointerLevel { + return buildEntityPointerLevel(Entities[N.first], N.second); + }; + auto GetNode = [&Entities](const EntityPointerLevel &N) -> Node { + return {Entities[N.getEntity()], N.getPointerLevel()}; + }; std::vector<EPLEdge> Edges; for (const auto &[F, T] : EdgeLayout) - Edges.push_back({N[F], N[T]}); + Edges.push_back({GetEPL(F), GetEPL(T)}); std::vector<EntityPointerLevel> Starters; - for (unsigned Idx : StarterLayout) - Starters.push_back(N[Idx]); + for (const Node &N : StarterLayout) + Starters.push_back(GetEPL(N)); - insertSummaries(*LU, Entities[0], Edges, Starters); - for (unsigned Idx = 1; Idx < NumEnt; ++Idx) - insertSummaries(*LU, Entities[Idx], {}, {}); + insertSummaries(*LU, Entities[EntityDomain[0]], Edges, Starters); + for (size_t Idx = 1; Idx < EntityDomain.size(); ++Idx) + insertSummaries(*LU, Entities[EntityDomain[Idx]], {}, {}); auto Reachables = computeReachables(std::move(LU), Line); - if (!Reachables.has_value()) - return std::nullopt; + if (!Reachables) + return {}; - std::set<unsigned> ReachableIndices; - for (unsigned I : llvm::seq(0U, NumEnt)) - if (Reachables->count(N[I])) - ReachableIndices.insert(I); + std::set<Node> Result; + for (auto &EPL : *Reachables) + Result.insert(GetNode(EPL)); - return ReachableIndices; + return Result; } }; //////////////////////////////////////////////////////////////////////////////// -// 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. +// Tests below focus on pointer flow graph topology and the starter set. +// Letters represent distinct entities; numbers represent pointer levels. +// +// For example, `LinearChain` tests a graph forming a linear chain with 3 +// edges: (a,1) -> (b,1) -> (c,1) -> (d,1) with starter {(a,1)}. Thus, {(a,1), +// (b,1), (c,1), (d,1)} is the expected reachable set. //////////////////////////////////////////////////////////////////////////////// -// Linear chain: 0 -> 1 -> 2 -> 3. -// Start from {0} => {0, 1, 2, 3} +// Linear chain: (a,1) -> (b,1) -> (c,1) -> (d,1). +// Start from {(a,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain) { auto Reachables = singlePartition( - /* NumEnt */ 4, - /* EdgeLayout */ {{0, 1}, {1, 2}, {2, 3}}, - /* StarterLayout */ {0}, __LINE__); - ASSERT_TRUE(Reachables.has_value()); - EXPECT_EQ(Reachables->size(), 4u); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, {{'b', 1}, {'c', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 4u); +} + +// Linear chain: (a,1) -> (b,2), (b,1) -> (c,2), (c,1) -> (d,2). +// Start from {(a,2)} => {(a,2), (b,3), (c,4), (d,5)} +TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 2}}, {{'b', 1}, {'c', 2}}, {{'c', 1}, {'d', 2}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables.size(), 4u); + EXPECT_EQ(Reachables, + (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 4}, {'d', 5}})); } -// Linear chain: 0 -> 1 -> 2 -> 3. -// Start from mid-chain {2} => {2, 3} +// Linear chain: (a,1) -> (b,2), (b,4) -> (c,1) -> (d,1). +// Start from {(a,2)} => {(a,2), (b,3)} (halted at (b,3) — no key (b,j<=3)) +TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain3) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 2}}, {{'b', 4}, {'c', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables.size(), 2u); + EXPECT_EQ(Reachables, (std::set<Node>{{'a', 2}, {'b', 3}})); +} + +// Linear chain: (a,1) -> (b,1) -> (c,1) -> (d,1). +// Start from mid-chain {(c,1)} => {(c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, LinearChainFromMiddle) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, {{'b', 1}, {'c', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'c', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 2u); + EXPECT_TRUE(Reachables.count({'c', 1})); + EXPECT_TRUE(Reachables.count({'d', 1})); } -// Diamond: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. -// Start from {0} => {0, 1, 2, 3} +// Diamond: (a,1) -> (b,1), (a,1) -> (c,1), (b,1) -> (d,1), (c,1) -> (d,1). +// Start from {(a,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, Diamond) { auto Reachables = singlePartition( - /* NumEnt */ 4, - /* EdgeLayout */ {{0, 1}, {0, 2}, {1, 3}, {2, 3}}, - /* StarterLayout */ {0}, __LINE__); - ASSERT_TRUE(Reachables.has_value()); - EXPECT_EQ(Reachables->size(), 4u); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'a', 1}, {'c', 1}}, + {{'b', 1}, {'d', 1}}, + {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 4u); +} + +// Diamond: (a,1) -> (b,2), (a,1) -> (c,2), (b,1) -> (d,2), (c,1) -> (d,2). +// Start from {(a,2)} => {(a,2), (b,3), (c,3), (d,4)} +TEST_F(UnsafeBufferReachableAnalysisTest, Diamond2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 2}}, + {{'a', 1}, {'c', 2}}, + {{'b', 1}, {'d', 2}}, + {{'c', 1}, {'d', 2}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables, + (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 3}, {'d', 4}})); +} + +// DisconnectedDiamond: (a,1) -> (b,2), (a,1) -> (c,2), (b,5) -> (d,1), (c,5) -> +// (d,1). Start from {(a,2)} => {(a,2), (b,3), (c,3)} +TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedDiamond) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 2}}, + {{'a', 1}, {'c', 2}}, + {{'b', 5}, {'d', 1}}, + {{'c', 5}, {'d', 1}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables, (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 3}})); } -// Diamond: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. -// Start from one branch {1} => {1, 3} +// Diamond: (a,1) -> (b,1), (a,1) -> (c,1), (b,1) -> (d,1), (c,1) -> (d,1). +// Start from one branch {(b,1)} => {(b,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, DiamondFromBranch) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'a', 1}, {'c', 1}}, + {{'b', 1}, {'d', 1}}, + {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'b', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 2u); + EXPECT_TRUE(Reachables.count({'b', 1})); + EXPECT_TRUE(Reachables.count({'d', 1})); } -// Disconnected subgraphs: 0 -> 1, 2 -> 3. -// Start from {0} => {0, 1} +// Disconnected subgraphs: (a,1) -> (b,1), (c,1) -> (d,1). +// Start from {(a,1)} => {(a,1), (b,1)} TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphs) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ {{{'a', 1}, {'b', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 2u); + EXPECT_TRUE(Reachables.count({'a', 1})); + EXPECT_TRUE(Reachables.count({'b', 1})); } -// Disconnected subgraphs: 0 -> 1, 2 -> 3. -// Start from tail {1} => {1} -TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphsFromTail) { +// Disconnected subgraphs: (a,1) -> (b,1), (c,1) -> (d,1). +// Start from tail {(b,1)} => {(b,1)} +TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphs2) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ {{{'a', 1}, {'b', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'b', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 1u); + EXPECT_TRUE(Reachables.count({'b', 1})); } -// Cycle: 0 -> 1 -> 2 -> 3 -> 0. -// Start from {2} => {0, 1, 2, 3} +// Cycle: (a,1) -> (b,1) -> (c,1) -> (d,1) -> (a,1). +// Start from {(c,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, Cycle) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'b', 1}, {'c', 1}}, + {{'c', 1}, {'d', 1}}, + {{'d', 1}, {'a', 1}}}, + /* StarterLayout */ {{'c', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 4u); + EXPECT_TRUE(Reachables.count({'a', 1})); + EXPECT_TRUE(Reachables.count({'b', 1})); + EXPECT_TRUE(Reachables.count({'c', 1})); + EXPECT_TRUE(Reachables.count({'d', 1})); +} + +// Cycle: (a,1) -> (b,1) -> (c,1) -> (d,1) -> (a,1). +// Start from {(c,2)} => {(a,2), (b,2), (c,2), (d,2)} +TEST_F(UnsafeBufferReachableAnalysisTest, Cycle2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'b', 1}, {'c', 1}}, + {{'c', 1}, {'d', 1}}, + {{'d', 1}, {'a', 1}}}, + /* StarterLayout */ {{'c', 2}}, __LINE__); + EXPECT_EQ(Reachables, + (std::set<Node>{{'a', 2}, {'b', 2}, {'c', 2}, {'d', 2}})); +} + +// Cycle: (a,1) -> (b,2) -> (c,3) -> (d,4) -> (a,1). +// Start from {(a,2)} => {(a,2), (b,3), (c,4), (d,5)} +TEST_F(UnsafeBufferReachableAnalysisTest, Cycle3) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 2}}, + {{'b', 2}, {'c', 3}}, + {{'c', 3}, {'d', 4}}, + {{'d', 4}, {'a', 1}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables, + (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 4}, {'d', 5}})); } -// Empty graph: no edges, start from {0} => {0} +// Empty graph: no edges, start from {(a,1)} => {(a,1)} TEST_F(UnsafeBufferReachableAnalysisTest, EmptyGraph) { auto Reachables = singlePartition( - /* NumEnt */ 4, + /* EntityDomain */ {'a'}, /* EdgeLayout */ {}, - /* StarterLayout */ {0}, __LINE__); - ASSERT_TRUE(Reachables.has_value()); - EXPECT_EQ(Reachables->size(), 1u); - EXPECT_TRUE(Reachables->count(0)); + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 1u); + EXPECT_TRUE(Reachables.count({'a', 1})); } -// Star: 0 -> 1, 0 -> 2, 0 -> 3. -// Start from {0} => {0, 1, 2, 3} +// Star: (a,1) -> (b,1), (a,1) -> (c,1), (a,1) -> (d,1). +// Start from {(a,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub) { auto Reachables = singlePartition( - /* NumEnt */ 4, - /* EdgeLayout */ {{0, 1}, {0, 2}, {0, 3}}, - /* StarterLayout */ {0}, __LINE__); - ASSERT_TRUE(Reachables.has_value()); - EXPECT_EQ(Reachables->size(), 4u); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, {{'a', 1}, {'c', 1}}, {{'a', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 4u); +} + +// Star: (a,1) -> (b,2), (a,1) -> (c,2), (a,1) -> (d,2). +// Start from {(a,2)} => {(a,2), (b,3), (c,3), (d,3)} +TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 2}}, {{'a', 1}, {'c', 2}}, {{'a', 1}, {'d', 2}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables, + (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 3}, {'d', 3}})); +} + +// Star: (a,2) -> (b,1), (a,2) -> (c,1), (a,2) -> (d,1). +// Start from {(a,1)} => {(a,1)} +TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub3) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 2}, {'b', 1}}, {{'a', 2}, {'c', 1}}, {{'a', 2}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables, (std::set<Node>{{'a', 1}})); } -// Star: 0 -> 1, 0 -> 2, 0 -> 3. -// Start from leaf {2} => {2} +// Star: (a,1) -> (b,1), (a,1) -> (c,1), (a,1) -> (d,1). +// Start from leaf {(c,1)} => {(c,1)} TEST_F(UnsafeBufferReachableAnalysisTest, StarFromLeaf) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, {{'a', 1}, {'c', 1}}, {{'a', 1}, {'d', 1}}}, + /* StarterLayout */ {{'c', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 1u); + EXPECT_TRUE(Reachables.count({'c', 1})); } -// Reverse star: 0 -> 3, 1 -> 3, 2 -> 3. -// Start from {0} => {0, 3} +// Reverse star: (a,1) -> (d,1), (b,1) -> (d,1), (c,1) -> (d,1). +// Start from {(a,1)} => {(a,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSource) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'d', 1}}, {{'b', 1}, {'d', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 2u); + EXPECT_TRUE(Reachables.count({'a', 1})); + EXPECT_TRUE(Reachables.count({'d', 1})); } -// Reverse star: 0 -> 3, 1 -> 3, 2 -> 3. -// Start from sink {3} => {3} +// Reverse star: (a,1) -> (d,2), (b,1) -> (d,2), (c,1) -> (d,2). +// Start from {(a,2)} => {(a,2), (d,3)} +TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSource2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'d', 2}}, {{'b', 1}, {'d', 2}}, {{'c', 1}, {'d', 2}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables, (std::set<Node>{{'a', 2}, {'d', 3}})); +} + +// Reverse star: (a,1) -> (d,1), (b,1) -> (d,1), (c,1) -> (d,1). +// Start from sink {(d,1)} => {(d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSink) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'d', 1}}, {{'b', 1}, {'d', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'d', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 1u); + EXPECT_TRUE(Reachables.count({'d', 1})); +} + +// Reverse star: (a,1) -> (d,1), (b,1) -> (d,1), (c,1) -> (d,1). +// Start from sink {(d,2)} => {(d,2)} +TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSink2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'d', 1}}, {{'b', 1}, {'d', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'d', 2}}, __LINE__); + EXPECT_EQ(Reachables, (std::set<Node>{{'d', 2}})); } -// Self-loop: 0 -> 1, 1 -> 1, 1 -> 2, 2 -> 3. -// Start from {0} => {0, 1, 2, 3} +// Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,1) -> (d,1). +// Start from {(a,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromRoot) { auto Reachables = singlePartition( - /* NumEnt */ 4, - /* EdgeLayout */ {{0, 1}, {1, 1}, {1, 2}, {2, 3}}, - /* StarterLayout */ {0}, __LINE__); - ASSERT_TRUE(Reachables.has_value()); - EXPECT_EQ(Reachables->size(), 4u); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'b', 1}, {'b', 1}}, + {{'b', 1}, {'c', 1}}, + {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 4u); } -// Self-loop: 0 -> 1, 1 -> 1, 1 -> 2, 2 -> 3. -// Start from {1} => {1, 2, 3} +// Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,2) -> (d,2). +// Start from {(a,2)} => {(a,2), (b,2), (c,3), (d,4)} +TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromRoot2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'b', 1}, {'b', 1}}, + {{'b', 1}, {'c', 2}}, + {{'c', 1}, {'d', 2}}}, + /* StarterLayout */ {{'a', 2}}, __LINE__); + EXPECT_EQ(Reachables, + (std::set<Node>{{'a', 2}, {'b', 2}, {'c', 3}, {'d', 4}})); +} + +// Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,1) -> (d,1). +// Start from {(b,1)} => {(b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromLoopNode) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'b', 1}, {'b', 1}}, + {{'b', 1}, {'c', 1}}, + {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'b', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 3u); + EXPECT_TRUE(Reachables.count({'b', 1})); + EXPECT_TRUE(Reachables.count({'c', 1})); + EXPECT_TRUE(Reachables.count({'d', 1})); +} + +// Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,2) -> (d,2). +// Start from {(b,2)} => {(b,2), (c,3), (d,4)} +TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromLoopNode2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ + {{{'a', 1}, {'b', 1}}, + {{'b', 1}, {'b', 1}}, + {{'b', 1}, {'c', 2}}, + {{'c', 1}, {'d', 2}}}, + /* StarterLayout */ {{'b', 2}}, __LINE__); + EXPECT_EQ(Reachables, (std::set<Node>{{'b', 2}, {'c', 3}, {'d', 4}})); } -// Multiple starters: 0 -> 1, 2 -> 3 (disconnected). -// Start from {0, 2} => {0, 1, 2, 3} +// Multiple starters: (a,1) -> (b,1), (c,1) -> (d,1) (disconnected). +// Start from {(a,1), (c,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersBothChains) { auto Reachables = singlePartition( - /* NumEnt */ 4, - /* EdgeLayout */ {{0, 1}, {2, 3}}, - /* StarterLayout */ {0, 2}, __LINE__); - ASSERT_TRUE(Reachables.has_value()); - EXPECT_EQ(Reachables->size(), 4u); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ {{{'a', 1}, {'b', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'a', 1}, {'c', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 4u); } -// Multiple starters: 0 -> 1, 2 -> 3 (disconnected). -// Start from leaves {1, 3} => {1, 3} +// Multiple starters: (a,1) -> (b,2), (c,1) -> (d,2). +// Start from {(a,2), (c,2)} => {(a,2), (b,3), (c,2), (d,3)} +TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersBothChains2) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ {{{'a', 1}, {'b', 2}}, {{'c', 1}, {'d', 2}}}, + /* StarterLayout */ {{'a', 2}, {'c', 2}}, __LINE__); + EXPECT_EQ(Reachables, + (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 2}, {'d', 3}})); +} + +// Multiple starters: (a,1) -> (b,1), (c,1) -> (d,1) (disconnected). +// Start from leaves {(b,1), (d,1)} => {(b,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersLeaves) { auto Reachables = singlePartition( - /* 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)); + /* EntityDomain */ {'a', 'b', 'c', 'd'}, + /* EdgeLayout */ {{{'a', 1}, {'b', 1}}, {{'c', 1}, {'d', 1}}}, + /* StarterLayout */ {{'b', 1}, {'d', 1}}, __LINE__); + EXPECT_EQ(Reachables.size(), 2u); + EXPECT_TRUE(Reachables.count({'b', 1})); + EXPECT_TRUE(Reachables.count({'d', 1})); +} + +// Multi-key, same source entity: (a,1) -> (b,1), (a,2) -> (c,1). +// Start from {(a,3)} => {(a,3), (b,3), (c,2)} +TEST_F(UnsafeBufferReachableAnalysisTest, MultipleKeysSameEntity) { + auto Reachables = singlePartition( + /* EntityDomain */ {'a', 'b', 'c'}, + /* EdgeLayout */ {{{'a', 1}, {'b', 1}}, {{'a', 2}, {'c', 1}}}, + /* StarterLayout */ {{'a', 3}}, __LINE__); + EXPECT_EQ(Reachables, (std::set<Node>{{'a', 3}, {'b', 3}, {'c', 2}})); } } // namespace _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
