Author: Ziqing Luo Date: 2026-08-29T17:40:28-07:00 New Revision: 45c256b552caf38f5ff6841af3eb96141a7417d3
URL: https://github.com/llvm/llvm-project/commit/45c256b552caf38f5ff6841af3eb96141a7417d3 DIFF: https://github.com/llvm/llvm-project/commit/45c256b552caf38f5ff6841af3eb96141a7417d3.diff LOG: [SSAF][PointerFlow] A pointer assignment may yield more than one edge (#218207) This commit is a redesign of #198889, which introduced a non-termination bug. Problem: The current pointer-flow graph has exactly one edge corresponding to an assignment in the source code. For example, a pointer assignment p = q; results in an edge `(p, i) -> (q, j)` for some pointer levels i and j. In unsafe buffer propagation, the edge encodes the meaning that if `p` is bounded, so must `q` be; additionally, if `*p (or p[x])` is bounded, so must `*q (or q[y])` be; and so on until the maximum pointer level of `p` or `q` is reached. Therefore, during the graph search (WPA phase), a node `(p, i+1)` can reach `(q, j+1)` through the edge `(p, i) -> (q, j)`. This is correct ONLY when `p` and `q` have compatible types, which is true for most cases due to type checking. However, this assumption does not hold in the presence of reinterpreting casts—a pointer assignment `a = (T)b` (for some pointer type `T`) contributes an edge `(a, x) -> (b, y)` where a and b do not have compatible types. Consequently, one can have two such edges in the graph, causing WPA to hang on examples such as: ``` a = *b; // (a, 1) -> (b, 2) b = (char ***)*a; // (b, 1) -> (a, 2) ``` Note that during the graph search phase, type information has been abstracted out. Therefore, we do not know the exact pointer level upper bounds to limit pointer level growth. Solution: To fix this, the pointer-flow graph must explicitly include the finite set of edges encoded by each assignment. Since type information is abstracted away before WPA, this commit moves the expansion logic back into the PointerFlowExtractor, where types are still available during graph construction. The difference this makes to the PointerFlowExtractor is that the output was previously "compressed" (because one graph edge represented multiple levels) and is now "uncompressed". This simplifies WPA because the meaning of each graph edge is now straightforward. In the future, we may want to make the edge expansion optional so that it can be disabled when propagating non-type properties. Second step of: rdar://183529483 --------- Co-authored-by: Balázs Benics <[email protected]> Added: Modified: clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp Removed: ################################################################################ diff --git a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h index 6e8971bd2eb8d..6a4e4c2879ae1 100644 --- a/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h +++ b/clang/include/clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h @@ -153,12 +153,6 @@ createEntityPointerLevel(const NamedDecl *ND, TUSummaryExtractor &Extractor, /// pointer level of each element is bounded by the type of \p DPL's NamedDecl. DeclPointerLevelVec elaborateHigherDeclPointerLevels(const DeclPointerLevel &DPL); - -/// Creates a new EntityPointerLevel (EPL) from `E` by incrementing `E`'s -/// pointer level. -/// \return the EPL that is associated with the pointee (or array element) type -/// of `E`'s associated pointer/array type of the same entity. -EntityPointerLevel incrementPointerLevel(const EntityPointerLevel &E); } // namespace clang::ssaf #endif // LLVM_CLANG_SCALABLESTATICANALYSIS_ANALYSES_ENTITYPOINTERLEVEL_ENTITYPOINTERLEVEL_H diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp index 83786185de06e..b1275f1eb3427 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.cpp @@ -118,10 +118,6 @@ class EntityPointerLevelTranslator return buildEntityPointerLevel(Base->getEntity(), D.PointerLevel); } - static EntityPointerLevel incrementPointerLevel(const EntityPointerLevel &E) { - return EntityPointerLevel({E.getEntity(), E.getPointerLevel() + 1}); - } - private: Expected<DeclPointerLevelVec> VisitStmt(const Stmt *E) { return fallback(E); } @@ -423,11 +419,6 @@ clang::ssaf::toEntityPointerLevel(const DeclPointerLevel &DPL, ASTContext &Ctx, return Translator.toEntityPointerLevel(DPL); } -EntityPointerLevel -clang::ssaf::incrementPointerLevel(const EntityPointerLevel &E) { - return EntityPointerLevelTranslator::incrementPointerLevel(E); -} - EntityPointerLevel clang::ssaf::buildEntityPointerLevel(EntityId Id, unsigned PtrLv) { return EntityPointerLevel({Id, PtrLv}); diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp index 42d5b5a7de041..719929bd7d43a 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowExtractor.cpp @@ -15,21 +15,16 @@ #include "clang/AST/ExprCXX.h" #include "clang/AST/Stmt.h" #include "clang/AST/TypeBase.h" -#include "clang/Frontend/SSAFOptions.h" #include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h" #include "clang/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlow.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" -#include "clang/ScalableStaticAnalysis/Core/Model/EntityName.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/ExtractorRegistry.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryBuilder.h" #include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryExtractor.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/STLFunctionalExtras.h" -#include "llvm/ADT/Sequence.h" -#include "llvm/Support/Debug.h" #include "llvm/Support/Error.h" #include <memory> -#include <optional> namespace clang::ssaf { extern PointerFlowEntitySummary buildPointerFlowEntitySummary(EdgeSet Edges); @@ -59,15 +54,16 @@ class PointerFlowMatcher { llvm::Error matchesDecl(const Decl *D, const NamedDecl *RootDecl); private: - std::function<EntityId(const EntityName &)> AddEntity; + llvm::Error addEdges(Expected<DeclPointerLevelVec> &&LHS, + Expected<DeclPointerLevelVec> &&RHS); - Expected<EntityPointerLevelSet> toEPL(const NamedDecl *N, - bool IsRet = false) const; - - Expected<EntityPointerLevelSet> toEPL(const Expr *N) const; + Expected<DeclPointerLevelVec> toDPL(const Expr *N) const { + return translateDeclPointerLevel(N, Ctx, Extractor); + } - llvm::Error addEdges(Expected<EntityPointerLevelSet> &&LHS, - Expected<EntityPointerLevelSet> &&RHS); + static DeclPointerLevel toDPL(const NamedDecl *N, bool IsRet = false) { + return createDeclPointerLevel(N, IsRet); + } template <typename ParmsProvider, typename ArgsProvider> llvm::Error matchesArgsWithParams(unsigned ArgIdxStart, ParmsProvider *PP, @@ -79,7 +75,8 @@ class PointerFlowMatcher { ++ArgIdx, ++ParmIdx) { if (const ParmVarDecl *PD = PP->getParamDecl(ParmIdx); PD && hasPtrOrArrType(PD)) { - if (auto Err = addEdges(toEPL(PD), toEPL(AP->getArg(ArgIdx)))) + if (auto Err = addEdges(DeclPointerLevelVec{toDPL(PD)}, + toDPL(AP->getArg(ArgIdx)))) return Err; } } @@ -87,22 +84,8 @@ class PointerFlowMatcher { } }; -Expected<EntityPointerLevelSet> PointerFlowMatcher::toEPL(const NamedDecl *N, - bool IsRet) const { - auto Ret = createEntityPointerLevel(N, Extractor, IsRet); - - if (Ret) - return EntityPointerLevelSet{*Ret}; - return Ret.takeError(); -} - -Expected<EntityPointerLevelSet> PointerFlowMatcher::toEPL(const Expr *N) const { - return translateEntityPointerLevel(N, Ctx, Extractor); -} - -llvm::Error -PointerFlowMatcher::addEdges(Expected<EntityPointerLevelSet> &&LHS, - Expected<EntityPointerLevelSet> &&RHS) { +llvm::Error PointerFlowMatcher::addEdges(Expected<DeclPointerLevelVec> &&LHS, + Expected<DeclPointerLevelVec> &&RHS) { if (!LHS && !RHS) return llvm::joinErrors(LHS.takeError(), RHS.takeError()); if (!LHS) @@ -111,15 +94,48 @@ PointerFlowMatcher::addEdges(Expected<EntityPointerLevelSet> &&LHS, return RHS.takeError(); if (RHS->empty()) return llvm::Error::success(); - for (auto L : *LHS) - Results[L].insert(RHS->begin(), RHS->end()); + + std::vector<DeclPointerLevelVec> LVecs, RVecs; + + LVecs.reserve(LHS->size()); + for (const auto &L : *LHS) + LVecs.push_back(elaborateHigherDeclPointerLevels(L)); + RVecs.reserve(RHS->size()); + for (const auto &R : *RHS) + RVecs.push_back(elaborateHigherDeclPointerLevels(R)); + + // Imagine an assignment from pointer q to p: 'p = q'. It encodes that if 'p' + // has some property, so must 'q'; moreover, if '*p/p[i]' has some property, + // so must '*q/q[i]' and so on. Therefore, for each edge '(a, n) -> (b, m)' + // that represents an explicitly spelled place in the source code, we also add + // '(a, n + 1) -> (b, m + 1)', + // '(a, n + 2) -> (b, m + 2)', ... continuing until either 'a' or 'b' reaches + // its maximum pointer level, whichever happens first. + // + // Note that type checking ensures that 'p' and 'q' have + // identical pointer levels, but '(a, n)' and '(b, m)' may have diff erent + // upper bounds on their pointer levels, when, for example, 'q' is a + // reinterpret-cast expression, which can have diff erent pointer level than + // its sub-expression. + + for (const DeclPointerLevelVec &L : LVecs) + for (const DeclPointerLevelVec &R : RVecs) + for (const auto &[LDPL, RDPL] : llvm::zip(L, R)) { + auto LEPL = toEntityPointerLevel(LDPL, Ctx, Extractor); + if (!LEPL) + return LEPL.takeError(); + auto REPL = toEntityPointerLevel(RDPL, Ctx, Extractor); + if (!REPL) + return REPL.takeError(); + Results[*LEPL].insert(*REPL); + } return llvm::Error::success(); } /// Match and extract pointer flow. /// The extraction function 'XF' can be described by the following rules: /// -/// XF(l = r) := add edge "toEPL(l) -> toEPL(r))" +/// XF(l = r) := addEdges(toDPL(l), toDPL(r)) /// XF(foo(a, b, ...)) := XF(Param_1 = a), XF(Param_2 = b), ... /// XF(return e;) := XF(FunRet = e), where 'FunRet' is the return /// entity of the enclosing @@ -130,7 +146,7 @@ PointerFlowMatcher::addEdges(Expected<EntityPointerLevelSet> &&LHS, /// ctor's body will be visited separately. /// XF(T var = e) := XF(var = e) /// XF(T var = init-list) := see \ref -/// PointerFlowMatcher::matchInitializerList +/// PointerFlowMatcher::matchesInitializerList llvm::Error PointerFlowMatcher::matches(const DynTypedNode &DynNode, const NamedDecl *RootDecl) { if (const Stmt *S = DynNode.get<Stmt>()) @@ -145,7 +161,7 @@ llvm::Error PointerFlowMatcher::matchesStmt(const Stmt *S, // Match 'p = q' whenever it has pointer or array type: if (const auto *BO = dyn_cast<BinaryOperator>(S); BO && BO->getOpcode() == BO_Assign && hasPtrOrArrType(BO)) { - return addEdges(toEPL(BO->getLHS()), toEPL(BO->getRHS())); + return addEdges(toDPL(BO->getLHS()), toDPL(BO->getRHS())); } // Match arg-to-param passing (in CallExpr) for any pointer type argument: @@ -172,7 +188,7 @@ llvm::Error PointerFlowMatcher::matchesStmt(const Stmt *S, const Expr *RetExpr = RS->getRetValue(); if (!RetExpr || !hasPtrOrArrType(RetExpr)) return llvm::Error::success(); - return addEdges(toEPL(RootDecl, true), toEPL(RetExpr)); + return addEdges(DeclPointerLevelVec{toDPL(RootDecl, true)}, toDPL(RetExpr)); } return llvm::Error::success(); } @@ -193,7 +209,7 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, // Match initializers to variables/fields of a pointer type: if (InitExpr && hasPtrOrArrType(VD)) - return addEdges(toEPL(VD), toEPL(InitExpr)); + return addEdges(DeclPointerLevelVec{toDPL(VD)}, toDPL(InitExpr)); } // Match C++ constructor member-initializers: @@ -202,7 +218,8 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, if (E->isDelegatingInitializer()) return matches(DynTypedNode::create(*E->getInit()), RootDecl); if (const FieldDecl *FD = E->getMember(); FD && hasPtrOrArrType(FD)) { - if (auto Err = addEdges(toEPL(E->getMember()), toEPL(E->getInit()))) + if (auto Err = addEdges(DeclPointerLevelVec{toDPL(E->getMember())}, + toDPL(E->getInit()))) return Err; } } @@ -210,7 +227,7 @@ llvm::Error PointerFlowMatcher::matchesDecl(const Decl *D, return llvm::Error::success(); } -// Helper function for matchInitializerList that handles record: +// Helper function for matchesInitializerList that handles record: llvm::Error matchInitializerListForRecordDecl(PointerFlowMatcher &Matcher, const RecordDecl *RecordTy, const InitListExpr *ILE) { @@ -242,7 +259,7 @@ llvm::Error matchInitializerListForRecordDecl(PointerFlowMatcher &Matcher, return llvm::Error::success(); } -// Helper function for matchInitializerList that handles array: +// Helper function for matchesInitializerList that handles array: llvm::Error matchInitializerListForArray(PointerFlowMatcher &Matcher, const ValueDecl *Array, const InitListExpr *ILE, @@ -267,7 +284,7 @@ llvm::Error matchInitializerListForArray(PointerFlowMatcher &Matcher, /// /// The process is recursive: 'a', 'b', 'c', ... may themselves be /// initializer lists. We therefore use \p ArrayElementIndirectLevel to keep -/// track of the pointer level the left-hand side. +/// track of the pointer level of the left-hand side. llvm::Error PointerFlowMatcher::matchesInitializerList(const ValueDecl *Base, const Expr *InitExpr, @@ -278,20 +295,10 @@ PointerFlowMatcher::matchesInitializerList(const ValueDecl *Base, if (!hasPtrOrArrType(InitExpr)) return llvm::Error::success(); - auto BaseEPL = toEPL(Base); - - if (!BaseEPL) - return BaseEPL.takeError(); - - // Apply ArrayElementIndirectLevel to BaseEPL - auto R = llvm::map_range(*BaseEPL, [&ArrayElementIndirectLevel]( - const EntityPointerLevel &EPL) { - EntityPointerLevel Result = EPL; - for ([[maybe_unused]] auto Ignored : llvm::seq(ArrayElementIndirectLevel)) - Result = incrementPointerLevel(Result); - return Result; - }); - return addEdges(EntityPointerLevelSet{R.begin(), R.end()}, toEPL(InitExpr)); + auto BaseDPL = toDPL(Base); + // Apply ArrayElementIndirectLevel to BaseDPL + BaseDPL.PointerLevel += ArrayElementIndirectLevel; + return addEdges(DeclPointerLevelVec{BaseDPL}, toDPL(InitExpr)); } // Note that `Base`'s type is NOT the real LHS type when // ArrayElementIndirectLevel > 0: diff --git a/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp b/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp index 1260aad81a8bf..1f5b3d697c35c 100644 --- a/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp +++ b/clang/unittests/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowTest.cpp @@ -751,7 +751,10 @@ TEST_F(PointerFlowTest, LocalVarDeclInit2) { auto *Sum = getEntitySummary("foo"); ASSERT_NE(Sum, nullptr); - EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"p", 1U}, {"arr", 1U}}})); + // 'p' and 'arr' are both 'int (*)[10]' (max level 2: pointer + array), so the + // base edge (p, 1) -> (arr, 1) is elaborated with (p, 2) -> (arr, 2). + EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"p", 1U}, {"arr", 1U}}, + {{"p", 2U}, {"arr", 2U}}})); } TEST_F(PointerFlowTest, FieldInit) { @@ -1113,6 +1116,26 @@ TEST_F(PointerFlowTest, MultipleReturnEdges) { })); } +// A function returning a reference to a multi-level pointer. The return +// type `int **&` has two pointer levels once the reference is stripped, so the +// (foo_ret, n) -> (gpp, m) edge should be elaborated up to level 2. +TEST_F(PointerFlowTest, ReturnRefToMultiLevelPointer) { + ASSERT_TRUE(setUpTest(R"cpp( + int **gpp; + int **&foo() { + return gpp; + } + )cpp")); + + auto *Sum = getEntitySummary("foo"); + + ASSERT_NE(Sum, nullptr); + EXPECT_EQ(*Sum, makeEdges(__LINE__, { + {{"foo", 1U, true}, {"gpp", 1U}}, + {{"foo", 2U, true}, {"gpp", 2U}}, + })); +} + TEST_F(PointerFlowTest, NoReturnEdgeForNonPointerReturnType) { ASSERT_EQ(setUpTest(R"cpp( int foo(int *p, int x) { @@ -1390,9 +1413,13 @@ TEST_F(PointerFlowTest, StructuredBindingWithPointers) { testing::internal::CaptureStderr(); ASSERT_TRUE(setUpTest(Code)); - // Verify the warning was logged + // Verify the warning was logged: + // The structured-binding initializer is an ArrayInitLoopExpr (an element-wise + // array copy), which the translator does not support. It is reported as a + // warning rather than crashing, and no summary is produced for 'foo'. ASSERT_TRUE(StringRef(testing::internal::GetCapturedStderr()) - .contains("failed to create EntityId for Decomposition")); + .contains("attempt to translate ArrayInitLoopExpr to " + "EntityPointerLevels")); } #endif @@ -1440,7 +1467,10 @@ TEST_F(PointerFlowTest, ArgToRefParamLevel2) { auto *Sum = getEntitySummary("caller"); ASSERT_TRUE(Sum); - EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"rp", 1U}, {"pp", 1U}}})); + // Both 'rp' and 'pp' are 'int**' (max level 2), so the base edge + // (rp, 1) -> (pp, 1) is elaborated with the higher-level (rp, 2) -> (pp, 2). + EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"rp", 1U}, {"pp", 1U}}, + {{"rp", 2U}, {"pp", 2U}}})); } TEST_F(PointerFlowTest, InitRefPtr) { @@ -1543,7 +1573,10 @@ TEST_F(PointerFlowTest, RefBindMultiLevel) { auto *Sum = getEntitySummary<VarDecl>("r"); ASSERT_NE(Sum, nullptr); - EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"r", 1U}, {"gpp", 1U}}})); + // Both 'r' and 'gpp' are 'int**' (max level 2), so the base edge + // (r, 1) -> (gpp, 1) is elaborated with the higher-level (r, 2) -> (gpp, 2). + EXPECT_EQ(*Sum, makeEdges(__LINE__, {{{"r", 1U}, {"gpp", 1U}}, + {{"r", 2U}, {"gpp", 2U}}})); } TEST_F(PointerFlowTest, RefBindTernaryInit) { _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
