https://github.com/suoyuan666 updated https://github.com/llvm/llvm-project/pull/196075
>From 4a7f75220b9f90a591b93ee2a82adecf4c8d16c0 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Wed, 6 May 2026 21:00:04 +0800 Subject: [PATCH 1/9] [NFC][LifetimeSafety]: Track assignment history within a single CFGBlock Tracking assignment history allows us to backtrack and provide more informative error messages, helping users better understand the root cause. The complete backtracking implementation requires significant changes, including the core logic and its integration into various diagnostic paths. This patch submits the foundational part: the logic to track assignment history within a single CFGBlock. Signed-off-by: Yuan Suo <[email protected]> --- .../Analyses/LifetimeSafety/AssignmentQuery.h | 39 ++++ .../Analyses/LifetimeSafety/Origins.h | 7 + .../LifetimeSafety/AssignmentQuery.cpp | 186 ++++++++++++++++++ .../Analysis/LifetimeSafety/CMakeLists.txt | 1 + .../unittests/Analysis/LifetimeSafetyTest.cpp | 47 +++++ 5 files changed, 280 insertions(+) create mode 100644 clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h create mode 100644 clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h new file mode 100644 index 0000000000000..047de6e65b280 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h @@ -0,0 +1,39 @@ +//===- AssignmentQuery.cpp - C++ Lifetime Safety Checker --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements the LifetimeChecker, which detects use-after-free +// errors by checking if live origins hold loans that have expired. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_ASSIGNMENTQUERY_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_ASSIGNMENTQUERY_H + +#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" +#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h" + +namespace clang::lifetimes::internal { +using AssignmentPair = std::pair<DestOriginEntity, SrcOriginEntity>; + +struct AssignmentQueryContext { + const LoanPropagationAnalysis &LoanPropagation; + FactManager &FactMgr; +}; + +/// Get assignment history when an error is detected. +/// +/// To help user understand the data flow, we track where the problematic +/// address originated. +void trackAssignmentHistory( + const AssignmentQueryContext &Context, + llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, + const CFGBlock *StartBlock, const OriginID StartOID, + const LoanID EndLoanID); +} // namespace clang::lifetimes::internal + +#endif diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h index c2db59c579060..ccab535122896 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h @@ -27,6 +27,13 @@ namespace clang::lifetimes::internal { using OriginID = utils::ID<struct OriginTag>; +/// Represents all possible expressions or declarations that function +/// as the Src/Dest Origin in a visible assignment. +using DestOriginEntity = + llvm::PointerUnion<const DeclRefExpr *, const ValueDecl *, + const MemberExpr *>; +using SrcOriginEntity = const Expr *; + inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, OriginID ID) { return OS << ID.Value; } diff --git a/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp b/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp new file mode 100644 index 0000000000000..a79e497fdab2d --- /dev/null +++ b/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp @@ -0,0 +1,186 @@ +//===- AssignmentQuery.cpp - C++ Lifetime Safety Checker --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements the LifetimeChecker, which detects use-after-free +// errors by checking if live origins hold loans that have expired. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h" +#include <optional> + +namespace { +using namespace clang; +using namespace clang::lifetimes; +using namespace clang::lifetimes::internal; + +/// Locate the rightmost sub expression of the RHS, given that the LHS is +/// already known. To ensure printability, we invoke `Explorc->isValid()`. +/// +/// Typically, we select the rightmost subexpression, as it can be further +/// decomposed and parsed recursively. +/// +/// Since we are traversing assignments in reverse order, this function used +/// to determines whether `TargetExpr` meets the requirements of the RHS. +/// A match here triggers a subsequent attempt to match the LHS. +/// Because the function is not re-invoked until the LHS is matched, +/// it generally precludes the possibility of matching multiple +/// subexpressions within the same RHS. +const Expr *getRootSrcExpr(const Expr *TargetExpr) { + assert(TargetExpr); + const Expr *SExpr = TargetExpr->IgnoreParenCasts(); + + if (isa_and_nonnull<DeclRefExpr, CXXTemporaryObjectExpr, CXXConstructExpr, + MemberExpr, CXXMemberCallExpr, UnaryOperator, + CXXBindTemporaryExpr>(SExpr) && + SExpr->getExprLoc().isValid()) + return SExpr; + + if (const auto *SCExpr = dyn_cast_or_null<CallExpr>(SExpr); + SCExpr && SCExpr->getExprLoc().isValid() && + SCExpr->getCallee()->IgnoreParenCasts()->getExprLoc().isValid()) + return SCExpr; + + return nullptr; +} + +/// Obtain the actual LHS Expr from `WriteUF->getUseExpr()` based on the Decl +/// retrieved from `DestOrigin->getDecl()` in the `OriginFlowFact` +DestOriginEntity getDestEntity(const UseFact *UF, const OriginID &OID) { + for (const OriginList *Cur = UF->getUsedOrigins(); Cur; + Cur = Cur->peelOuterOrigin()) { + if (Cur->getOuterOriginID() != OID || !UF->isWritten()) + continue; + if (const auto *DestExpr = + dyn_cast_or_null<DeclRefExpr>(getRootSrcExpr(UF->getUseExpr()))) { + return DestExpr; + } + } + return nullptr; +} + +DestOriginEntity getDestEntity(const AssignmentQueryContext &Context, + const OriginFlowFact *OFF) { + const Origin &DestOrigin = + Context.FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); + const Origin &SrcOrigin = + Context.FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); + + if (const ValueDecl *DestDecl = DestOrigin.getDecl(); + DestDecl && DestDecl->getLocation().isValid()) { + return DestDecl; + } + + // This logic specifically handles the isa<FieldDecl>(DestOrigin->getDecl()) + // case. In `OriginFlowFact`, we store the Decl of the corresponding variable + // as the Origin rather than the LHS Origin itself. + // + // For a general `ValueDecl`, we typically find the corresponding `UseFact` + // following the `OriginFlowFact`. However, for a `FieldDecl`, the subsequent + // `OriginFlowFact` is associated with a `MemberExpr`. In this scenario, + // `DestOrigin` represents the `MemberExpr`, while SrcOrigin represents the + // Origin of the `CXXThisExpr` (CXXMethodDecl). + const Expr *DestExpr = DestOrigin.getExpr(); + const ValueDecl *SrcDecl = SrcOrigin.getDecl(); + if (isa_and_nonnull<MemberExpr>(DestExpr) && + isa_and_nonnull<CXXMethodDecl>(SrcDecl)) + return dyn_cast<MemberExpr>(DestExpr); + + return nullptr; +} + +SrcOriginEntity getSrcEntity(const AssignmentQueryContext &Context, + const OriginFlowFact *OFF) { + const Origin &DestOrigin = + Context.FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); + + const Expr *SExpr = getRootSrcExpr(DestOrigin.getExpr()); + if (!SExpr) { + const Origin &SrcOrigin = + Context.FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); + SExpr = getRootSrcExpr(SrcOrigin.getExpr()); + } + + return SExpr; +} + +bool trackAssignmentHistoryCore( + const AssignmentQueryContext &Context, + llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, + const CFGBlock *Block, OriginID *TargetOID, const LoanID EndLoanID) { + DestOriginEntity CurrDestEntity = nullptr; + bool NeedSearchOriginDestWithoutLoan = false; + std::optional<OriginID> CurrOriginID = std::nullopt; + llvm::ArrayRef<const Fact *> Facts = Context.FactMgr.getFacts(Block); + + const auto TryInsertAssignmentList = [&](const OriginFlowFact *OFF) { + if (NeedSearchOriginDestWithoutLoan) { + if (const MemberExpr *DestMemberExpr = + dyn_cast_or_null<const MemberExpr *>( + getDestEntity(Context, OFF))) { + CurrDestEntity = DestMemberExpr; + NeedSearchOriginDestWithoutLoan = false; + } + } + + if (OFF->getDestOriginID() == *TargetOID && + Context.LoanPropagation.getLoans(OFF->getSrcOriginID(), OFF) + .contains(EndLoanID)) { + if (!CurrDestEntity) { + DestOriginEntity DestEntity = getDestEntity(Context, OFF); + auto *DestValueDecl = dyn_cast_or_null<const ValueDecl *>(DestEntity); + if (DestValueDecl) + CurrOriginID = *TargetOID; + + if (llvm::isa_and_nonnull<FieldDecl>(DestValueDecl)) + NeedSearchOriginDestWithoutLoan = true; + else + CurrDestEntity = DestEntity; + } else { + SrcOriginEntity CurrSrcEntity = getSrcEntity(Context, OFF); + if (CurrSrcEntity) { + AssignmentList.push_back({CurrDestEntity, CurrSrcEntity}); + CurrDestEntity = nullptr; + CurrOriginID = std::nullopt; + } + } + *TargetOID = OFF->getSrcOriginID(); + } + }; + + for (const Fact *F : llvm::reverse(Facts)) { + if (const auto *OFF = F->getAs<OriginFlowFact>()) { + TryInsertAssignmentList(OFF); + } else if (const auto *IF = F->getAs<IssueFact>()) { + if (IF->getLoanID() == EndLoanID) + return true; + } else if (const auto *UF = F->getAs<UseFact>()) { + if (CurrOriginID) { + DestOriginEntity DestEntity = getDestEntity(UF, CurrOriginID.value()); + if (DestEntity) + CurrDestEntity = DestEntity; + } + } + } + + return false; +} +} // namespace + +namespace clang::lifetimes::internal { + +void trackAssignmentHistory( + const AssignmentQueryContext &Context, + llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, + const CFGBlock *StartBlock, OriginID StartOID, const LoanID EndLoanID) { + if (!trackAssignmentHistoryCore(Context, AssignmentList, StartBlock, + &StartOID, EndLoanID)) + llvm::errs() << "Assignment History Tracking may have failed\n"; + std::reverse(AssignmentList.begin(), AssignmentList.end()); +} +} // namespace clang::lifetimes::internal diff --git a/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt b/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt index 247377c7256d9..6c4d4e123908a 100644 --- a/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt +++ b/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt @@ -1,4 +1,5 @@ add_clang_library(clangAnalysisLifetimeSafety + AssignmentQuery.cpp Checker.cpp Facts.cpp FactsGenerator.cpp diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 6cf65dd64ef83..0713edbbbd52a 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -9,6 +9,7 @@ #include "clang/Analysis/Analyses/LifetimeSafety/LifetimeSafety.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h" #include "clang/Analysis/Analyses/LifetimeSafety/Loans.h" #include "clang/Testing/TestAST.h" #include "llvm/ADT/StringMap.h" @@ -204,6 +205,26 @@ class LifetimeTestHelper { return Runner.getAnalysis().getFactManager().getBlockContaining(P); } + void trackAssignmentHistoryInOneBlock( + llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, + llvm::StringRef StartOriginVar, llvm::StringRef EndLoanVar) { + const CFG *CurrCFG = Runner.getAnalysisContext().getCFG(); + AssignmentQueryContext Context = {Runner.getAnalysis().getLoanPropagation(), + Runner.getAnalysis().getFactManager()}; + + std::optional<OriginID> StartOriginID = getOriginForDecl(StartOriginVar); + std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); + + for (const CFGBlock *CurrCFGBlock : *CurrCFG) { + for (LoanID &LID : EndLoanIDs) { + trackAssignmentHistory(Context, AssignmentList, CurrCFGBlock, + *StartOriginID, LID); + if (!AssignmentList.empty()) + return; + } + } + } + private: template <typename DeclT> DeclT *findDecl(llvm::StringRef Name) { auto &Ctx = Runner.getASTContext(); @@ -1951,5 +1972,31 @@ TEST_F(LifetimeAnalysisTest, LambdaInitCaptureViewByValue) { )"); EXPECT_THAT(Origin("lambda"), HasLoansTo({"obj"}, "after_lambda")); } + +// ========================================================================= // +// Tests for trackAssignmentHistory +// ========================================================================= // + +TEST_F(LifetimeAnalysisTest, TrackLinearAssignmentHistoryInOneBlock) { + SetupTest(R"( + void target() { + int *s; + { + int tgt = 2; + int *a = &tgt; + int *c = a; + int *b = a; + int *e = b; + s = e; + } + (void)s; + } + )"); + + llvm::SmallVector<AssignmentPair> AssignmentList; + Helper->trackAssignmentHistoryInOneBlock(AssignmentList, "s", "tgt"); + + EXPECT_EQ(4u, AssignmentList.size()); +} } // anonymous namespace } // namespace clang::lifetimes::internal >From c9355408fec4c16e91f7b72ec555958877467d25 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Thu, 7 May 2026 12:10:29 +0800 Subject: [PATCH 2/9] code cleanup and addressed review comments Followed the review suggestions to improve code quality, including renaming types, updating comments, and removing redundant structures. Signed-off-by: Yuan Suo <[email protected]> --- .../Analyses/LifetimeSafety/AssignmentQuery.h | 15 ++++----- .../LifetimeSafety/AssignmentQuery.cpp | 33 ++++++++++--------- .../unittests/Analysis/LifetimeSafetyTest.cpp | 7 ++-- 3 files changed, 25 insertions(+), 30 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h index 047de6e65b280..bd8a7f68fa761 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h @@ -6,8 +6,8 @@ // //===----------------------------------------------------------------------===// // -// This file implements the LifetimeChecker, which detects use-after-free -// errors by checking if live origins hold loans that have expired. +// This file defines functions for tracing assignment history, +// as well as future data structures or other helper functions. // //===----------------------------------------------------------------------===// @@ -20,17 +20,14 @@ namespace clang::lifetimes::internal { using AssignmentPair = std::pair<DestOriginEntity, SrcOriginEntity>; -struct AssignmentQueryContext { - const LoanPropagationAnalysis &LoanPropagation; - FactManager &FactMgr; -}; - -/// Get assignment history when an error is detected. +/// Traces the provenance of a pointer to provide contextual notes for +/// lifetime-related diagnostics. /// /// To help user understand the data flow, we track where the problematic /// address originated. void trackAssignmentHistory( - const AssignmentQueryContext &Context, + const FactManager &FactMgr, + const LoanPropagationAnalysis &LoanPropagation, llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, const CFGBlock *StartBlock, const OriginID StartOID, const LoanID EndLoanID); diff --git a/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp b/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp index a79e497fdab2d..9945013bd9ee4 100644 --- a/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp +++ b/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp @@ -6,8 +6,7 @@ // //===----------------------------------------------------------------------===// // -// This file implements the LifetimeChecker, which detects use-after-free -// errors by checking if live origins hold loans that have expired. +// This file implements trackAssignmentHistory. // //===----------------------------------------------------------------------===// @@ -64,12 +63,12 @@ DestOriginEntity getDestEntity(const UseFact *UF, const OriginID &OID) { return nullptr; } -DestOriginEntity getDestEntity(const AssignmentQueryContext &Context, +DestOriginEntity getDestEntity(const FactManager &FactMgr, const OriginFlowFact *OFF) { const Origin &DestOrigin = - Context.FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); + FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); const Origin &SrcOrigin = - Context.FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); + FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); if (const ValueDecl *DestDecl = DestOrigin.getDecl(); DestDecl && DestDecl->getLocation().isValid()) { @@ -94,15 +93,15 @@ DestOriginEntity getDestEntity(const AssignmentQueryContext &Context, return nullptr; } -SrcOriginEntity getSrcEntity(const AssignmentQueryContext &Context, +SrcOriginEntity getSrcEntity(const FactManager &FactMgr, const OriginFlowFact *OFF) { const Origin &DestOrigin = - Context.FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); + FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); const Expr *SExpr = getRootSrcExpr(DestOrigin.getExpr()); if (!SExpr) { const Origin &SrcOrigin = - Context.FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); + FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); SExpr = getRootSrcExpr(SrcOrigin.getExpr()); } @@ -110,29 +109,30 @@ SrcOriginEntity getSrcEntity(const AssignmentQueryContext &Context, } bool trackAssignmentHistoryCore( - const AssignmentQueryContext &Context, + const FactManager &FactMgr, + const LoanPropagationAnalysis &LoanPropagation, llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, const CFGBlock *Block, OriginID *TargetOID, const LoanID EndLoanID) { DestOriginEntity CurrDestEntity = nullptr; bool NeedSearchOriginDestWithoutLoan = false; std::optional<OriginID> CurrOriginID = std::nullopt; - llvm::ArrayRef<const Fact *> Facts = Context.FactMgr.getFacts(Block); + llvm::ArrayRef<const Fact *> Facts = FactMgr.getFacts(Block); const auto TryInsertAssignmentList = [&](const OriginFlowFact *OFF) { if (NeedSearchOriginDestWithoutLoan) { if (const MemberExpr *DestMemberExpr = dyn_cast_or_null<const MemberExpr *>( - getDestEntity(Context, OFF))) { + getDestEntity(FactMgr, OFF))) { CurrDestEntity = DestMemberExpr; NeedSearchOriginDestWithoutLoan = false; } } if (OFF->getDestOriginID() == *TargetOID && - Context.LoanPropagation.getLoans(OFF->getSrcOriginID(), OFF) + LoanPropagation.getLoans(OFF->getSrcOriginID(), OFF) .contains(EndLoanID)) { if (!CurrDestEntity) { - DestOriginEntity DestEntity = getDestEntity(Context, OFF); + DestOriginEntity DestEntity = getDestEntity(FactMgr, OFF); auto *DestValueDecl = dyn_cast_or_null<const ValueDecl *>(DestEntity); if (DestValueDecl) CurrOriginID = *TargetOID; @@ -142,7 +142,7 @@ bool trackAssignmentHistoryCore( else CurrDestEntity = DestEntity; } else { - SrcOriginEntity CurrSrcEntity = getSrcEntity(Context, OFF); + SrcOriginEntity CurrSrcEntity = getSrcEntity(FactMgr, OFF); if (CurrSrcEntity) { AssignmentList.push_back({CurrDestEntity, CurrSrcEntity}); CurrDestEntity = nullptr; @@ -175,10 +175,11 @@ bool trackAssignmentHistoryCore( namespace clang::lifetimes::internal { void trackAssignmentHistory( - const AssignmentQueryContext &Context, + const FactManager &FactMgr, + const LoanPropagationAnalysis &LoanPropagation, llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, const CFGBlock *StartBlock, OriginID StartOID, const LoanID EndLoanID) { - if (!trackAssignmentHistoryCore(Context, AssignmentList, StartBlock, + if (!trackAssignmentHistoryCore(FactMgr, LoanPropagation, AssignmentList, StartBlock, &StartOID, EndLoanID)) llvm::errs() << "Assignment History Tracking may have failed\n"; std::reverse(AssignmentList.begin(), AssignmentList.end()); diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 0713edbbbd52a..ae4215d7312d5 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -209,15 +209,12 @@ class LifetimeTestHelper { llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, llvm::StringRef StartOriginVar, llvm::StringRef EndLoanVar) { const CFG *CurrCFG = Runner.getAnalysisContext().getCFG(); - AssignmentQueryContext Context = {Runner.getAnalysis().getLoanPropagation(), - Runner.getAnalysis().getFactManager()}; - std::optional<OriginID> StartOriginID = getOriginForDecl(StartOriginVar); std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); for (const CFGBlock *CurrCFGBlock : *CurrCFG) { - for (LoanID &LID : EndLoanIDs) { - trackAssignmentHistory(Context, AssignmentList, CurrCFGBlock, + for (const LoanID &LID : EndLoanIDs) { + trackAssignmentHistory(Runner.getAnalysis().getFactManager(), Runner.getAnalysis().getLoanPropagation(), AssignmentList, CurrCFGBlock, *StartOriginID, LID); if (!AssignmentList.empty()) return; >From abec8ac7f9b36ac7aa850a2ab88c24fbe6911d5c Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Fri, 8 May 2026 13:23:08 +0800 Subject: [PATCH 3/9] refactor tracing to use Origin instead of expression Switched from tracing expressions to tracing Origins. I initially opted for expressions to accommodate future `Sema` diagnostics, but tracing Origins is more straightforward for this specific task. Only SrcOrigin tracing is implemented in this change. Signed-off-by: Yuan Suo <[email protected]> --- .../Analyses/LifetimeSafety/AssignmentQuery.h | 10 +- .../Analysis/Analyses/LifetimeSafety/Facts.h | 10 + .../Analyses/LifetimeSafety/Origins.h | 7 - .../LifetimeSafety/AssignmentQuery.cpp | 173 ++---------------- clang/lib/Analysis/LifetimeSafety/Facts.cpp | 8 +- .../unittests/Analysis/LifetimeSafetyTest.cpp | 32 +++- 6 files changed, 53 insertions(+), 187 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h index bd8a7f68fa761..06dc77e914554 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h @@ -18,7 +18,8 @@ #include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h" namespace clang::lifetimes::internal { -using AssignmentPair = std::pair<DestOriginEntity, SrcOriginEntity>; + +using AssignmentUnit = Origin; /// Traces the provenance of a pointer to provide contextual notes for /// lifetime-related diagnostics. @@ -26,11 +27,10 @@ using AssignmentPair = std::pair<DestOriginEntity, SrcOriginEntity>; /// To help user understand the data flow, we track where the problematic /// address originated. void trackAssignmentHistory( - const FactManager &FactMgr, - const LoanPropagationAnalysis &LoanPropagation, - llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, + const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, + llvm::SmallVectorImpl<AssignmentUnit> &AssignmentList, const CFGBlock *StartBlock, const OriginID StartOID, - const LoanID EndLoanID); + const LoanID &EndLoanID); } // namespace clang::lifetimes::internal #endif diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h index 88b509e1b94df..232bbb9b3d2c5 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h @@ -346,6 +346,16 @@ class FactManager { return BlockToFacts[B->getBlockID()]; } + std::optional<size_t> getBlockID(const Fact *TargetFact) const { + for (size_t i = 0; i < BlockToFacts.size(); ++i) { + for (const Fact *F : BlockToFacts[i]) { + if (F == TargetFact) + return i; + } + } + return std::nullopt; + } + void addBlockFacts(const CFGBlock *B, llvm::ArrayRef<Fact *> NewFacts) { if (!NewFacts.empty()) BlockToFacts[B->getBlockID()].assign(NewFacts.begin(), NewFacts.end()); diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h index ccab535122896..c2db59c579060 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Origins.h @@ -27,13 +27,6 @@ namespace clang::lifetimes::internal { using OriginID = utils::ID<struct OriginTag>; -/// Represents all possible expressions or declarations that function -/// as the Src/Dest Origin in a visible assignment. -using DestOriginEntity = - llvm::PointerUnion<const DeclRefExpr *, const ValueDecl *, - const MemberExpr *>; -using SrcOriginEntity = const Expr *; - inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, OriginID ID) { return OS << ID.Value; } diff --git a/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp b/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp index 9945013bd9ee4..c50f88165268d 100644 --- a/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp +++ b/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp @@ -11,177 +11,30 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h" -#include <optional> -namespace { -using namespace clang; -using namespace clang::lifetimes; -using namespace clang::lifetimes::internal; - -/// Locate the rightmost sub expression of the RHS, given that the LHS is -/// already known. To ensure printability, we invoke `Explorc->isValid()`. -/// -/// Typically, we select the rightmost subexpression, as it can be further -/// decomposed and parsed recursively. -/// -/// Since we are traversing assignments in reverse order, this function used -/// to determines whether `TargetExpr` meets the requirements of the RHS. -/// A match here triggers a subsequent attempt to match the LHS. -/// Because the function is not re-invoked until the LHS is matched, -/// it generally precludes the possibility of matching multiple -/// subexpressions within the same RHS. -const Expr *getRootSrcExpr(const Expr *TargetExpr) { - assert(TargetExpr); - const Expr *SExpr = TargetExpr->IgnoreParenCasts(); - - if (isa_and_nonnull<DeclRefExpr, CXXTemporaryObjectExpr, CXXConstructExpr, - MemberExpr, CXXMemberCallExpr, UnaryOperator, - CXXBindTemporaryExpr>(SExpr) && - SExpr->getExprLoc().isValid()) - return SExpr; - - if (const auto *SCExpr = dyn_cast_or_null<CallExpr>(SExpr); - SCExpr && SCExpr->getExprLoc().isValid() && - SCExpr->getCallee()->IgnoreParenCasts()->getExprLoc().isValid()) - return SCExpr; - - return nullptr; -} - -/// Obtain the actual LHS Expr from `WriteUF->getUseExpr()` based on the Decl -/// retrieved from `DestOrigin->getDecl()` in the `OriginFlowFact` -DestOriginEntity getDestEntity(const UseFact *UF, const OriginID &OID) { - for (const OriginList *Cur = UF->getUsedOrigins(); Cur; - Cur = Cur->peelOuterOrigin()) { - if (Cur->getOuterOriginID() != OID || !UF->isWritten()) - continue; - if (const auto *DestExpr = - dyn_cast_or_null<DeclRefExpr>(getRootSrcExpr(UF->getUseExpr()))) { - return DestExpr; - } - } - return nullptr; -} - -DestOriginEntity getDestEntity(const FactManager &FactMgr, - const OriginFlowFact *OFF) { - const Origin &DestOrigin = - FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); - const Origin &SrcOrigin = - FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); - - if (const ValueDecl *DestDecl = DestOrigin.getDecl(); - DestDecl && DestDecl->getLocation().isValid()) { - return DestDecl; - } - - // This logic specifically handles the isa<FieldDecl>(DestOrigin->getDecl()) - // case. In `OriginFlowFact`, we store the Decl of the corresponding variable - // as the Origin rather than the LHS Origin itself. - // - // For a general `ValueDecl`, we typically find the corresponding `UseFact` - // following the `OriginFlowFact`. However, for a `FieldDecl`, the subsequent - // `OriginFlowFact` is associated with a `MemberExpr`. In this scenario, - // `DestOrigin` represents the `MemberExpr`, while SrcOrigin represents the - // Origin of the `CXXThisExpr` (CXXMethodDecl). - const Expr *DestExpr = DestOrigin.getExpr(); - const ValueDecl *SrcDecl = SrcOrigin.getDecl(); - if (isa_and_nonnull<MemberExpr>(DestExpr) && - isa_and_nonnull<CXXMethodDecl>(SrcDecl)) - return dyn_cast<MemberExpr>(DestExpr); - - return nullptr; -} - -SrcOriginEntity getSrcEntity(const FactManager &FactMgr, - const OriginFlowFact *OFF) { - const Origin &DestOrigin = - FactMgr.getOriginMgr().getOrigin(OFF->getDestOriginID()); - - const Expr *SExpr = getRootSrcExpr(DestOrigin.getExpr()); - if (!SExpr) { - const Origin &SrcOrigin = - FactMgr.getOriginMgr().getOrigin(OFF->getSrcOriginID()); - SExpr = getRootSrcExpr(SrcOrigin.getExpr()); - } - - return SExpr; -} - -bool trackAssignmentHistoryCore( - const FactManager &FactMgr, - const LoanPropagationAnalysis &LoanPropagation, - llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, - const CFGBlock *Block, OriginID *TargetOID, const LoanID EndLoanID) { - DestOriginEntity CurrDestEntity = nullptr; - bool NeedSearchOriginDestWithoutLoan = false; - std::optional<OriginID> CurrOriginID = std::nullopt; - llvm::ArrayRef<const Fact *> Facts = FactMgr.getFacts(Block); - - const auto TryInsertAssignmentList = [&](const OriginFlowFact *OFF) { - if (NeedSearchOriginDestWithoutLoan) { - if (const MemberExpr *DestMemberExpr = - dyn_cast_or_null<const MemberExpr *>( - getDestEntity(FactMgr, OFF))) { - CurrDestEntity = DestMemberExpr; - NeedSearchOriginDestWithoutLoan = false; - } - } - - if (OFF->getDestOriginID() == *TargetOID && +namespace clang::lifetimes::internal { +void trackAssignmentHistory( + const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, + llvm::SmallVectorImpl<AssignmentUnit> &AssignmentList, + const CFGBlock *StartBlock, OriginID StartOID, const LoanID &EndLoanID) { + const auto TryInsertPropagationChain = [&](const OriginFlowFact *OFF) { + if (OFF->getDestOriginID() == StartOID && LoanPropagation.getLoans(OFF->getSrcOriginID(), OFF) .contains(EndLoanID)) { - if (!CurrDestEntity) { - DestOriginEntity DestEntity = getDestEntity(FactMgr, OFF); - auto *DestValueDecl = dyn_cast_or_null<const ValueDecl *>(DestEntity); - if (DestValueDecl) - CurrOriginID = *TargetOID; - - if (llvm::isa_and_nonnull<FieldDecl>(DestValueDecl)) - NeedSearchOriginDestWithoutLoan = true; - else - CurrDestEntity = DestEntity; - } else { - SrcOriginEntity CurrSrcEntity = getSrcEntity(FactMgr, OFF); - if (CurrSrcEntity) { - AssignmentList.push_back({CurrDestEntity, CurrSrcEntity}); - CurrDestEntity = nullptr; - CurrOriginID = std::nullopt; - } - } - *TargetOID = OFF->getSrcOriginID(); + const OriginID SrcOriginID = OFF->getSrcOriginID(); + AssignmentList.push_back(FactMgr.getOriginMgr().getOrigin(SrcOriginID)); + StartOID = SrcOriginID; } }; + llvm::ArrayRef<const Fact *> Facts = FactMgr.getFacts(StartBlock); for (const Fact *F : llvm::reverse(Facts)) { if (const auto *OFF = F->getAs<OriginFlowFact>()) { - TryInsertAssignmentList(OFF); + TryInsertPropagationChain(OFF); } else if (const auto *IF = F->getAs<IssueFact>()) { if (IF->getLoanID() == EndLoanID) - return true; - } else if (const auto *UF = F->getAs<UseFact>()) { - if (CurrOriginID) { - DestOriginEntity DestEntity = getDestEntity(UF, CurrOriginID.value()); - if (DestEntity) - CurrDestEntity = DestEntity; - } + return; } } - - return false; -} -} // namespace - -namespace clang::lifetimes::internal { - -void trackAssignmentHistory( - const FactManager &FactMgr, - const LoanPropagationAnalysis &LoanPropagation, - llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, - const CFGBlock *StartBlock, OriginID StartOID, const LoanID EndLoanID) { - if (!trackAssignmentHistoryCore(FactMgr, LoanPropagation, AssignmentList, StartBlock, - &StartOID, EndLoanID)) - llvm::errs() << "Assignment History Tracking may have failed\n"; - std::reverse(AssignmentList.begin(), AssignmentList.end()); } } // namespace clang::lifetimes::internal diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index 3d7fbcdacc830..8a71fb8404cfe 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp @@ -145,11 +145,9 @@ void FactManager::dump(const CFG &Cfg, AnalysisDeclContext &AC) const { llvm::ArrayRef<const Fact *> FactManager::getBlockContaining(ProgramPoint P) const { - for (const auto &BlockToFactsVec : BlockToFacts) { - for (const Fact *F : BlockToFactsVec) - if (F == P) - return BlockToFactsVec; - } + std::optional<size_t> BlockIndex = getBlockID(P); + if (BlockIndex) + return BlockToFacts[BlockIndex.value()]; return {}; } diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index ae4215d7312d5..97a45d40b989d 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -205,21 +205,32 @@ class LifetimeTestHelper { return Runner.getAnalysis().getFactManager().getBlockContaining(P); } + std::optional<size_t> getBlockID(ProgramPoint P) { + return Runner.getAnalysis().getFactManager().getBlockID(P); + } + void trackAssignmentHistoryInOneBlock( - llvm::SmallVectorImpl<AssignmentPair> &AssignmentList, + llvm::SmallVectorImpl<AssignmentUnit> &AssignmentList, llvm::StringRef StartOriginVar, llvm::StringRef EndLoanVar) { - const CFG *CurrCFG = Runner.getAnalysisContext().getCFG(); std::optional<OriginID> StartOriginID = getOriginForDecl(StartOriginVar); std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); - for (const CFGBlock *CurrCFGBlock : *CurrCFG) { - for (const LoanID &LID : EndLoanIDs) { - trackAssignmentHistory(Runner.getAnalysis().getFactManager(), Runner.getAnalysis().getLoanPropagation(), AssignmentList, CurrCFGBlock, - *StartOriginID, LID); - if (!AssignmentList.empty()) - return; + const CFGBlock *StartBlock = nullptr; + const size_t BlockID = getBlockID(getProgramPoint("after_use")).value(); + for (const CFGBlock *CurrBlock : *Runner.getAnalysisContext().getCFG()) { + if (CurrBlock->getBlockID() == BlockID) { + StartBlock = CurrBlock; + break; } } + + for (const LoanID &LID : EndLoanIDs) { + trackAssignmentHistory(Runner.getAnalysis().getFactManager(), + Runner.getAnalysis().getLoanPropagation(), + AssignmentList, StartBlock, *StartOriginID, LID); + if (!AssignmentList.empty()) + return; + } } private: @@ -1987,13 +1998,14 @@ TEST_F(LifetimeAnalysisTest, TrackLinearAssignmentHistoryInOneBlock) { s = e; } (void)s; + POINT(after_use); } )"); - llvm::SmallVector<AssignmentPair> AssignmentList; + llvm::SmallVector<AssignmentUnit> AssignmentList; Helper->trackAssignmentHistoryInOneBlock(AssignmentList, "s", "tgt"); - EXPECT_EQ(4u, AssignmentList.size()); + EXPECT_EQ(8u, AssignmentList.size()); } } // anonymous namespace } // namespace clang::lifetimes::internal >From 624d842899d6a763a5696ce59a3d1c92e4bbf66f Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Tue, 12 May 2026 22:41:16 +0800 Subject: [PATCH 4/9] address feedback from usx95's initial deep review This primarily involves naming changes. for instance, renaming `trackAssignmentHistory` to `buildOriginFlowChain`. There are also some minor modifications to the code structure. Note, the `StartBlock` parameter in `buildOriginFlowChain` has been replaced by `StartProgramPoint`; consequently, we no longer rely on CFG Blocks and simply require a `ProgramPoint` to serve as the starting point. Signed-off-by: Yuan Suo <[email protected]> --- .../Analysis/Analyses/LifetimeSafety/Facts.h | 10 ---- .../{AssignmentQuery.h => OriginFlowChain.h} | 24 +++++----- .../LifetimeSafety/AssignmentQuery.cpp | 40 ---------------- .../Analysis/LifetimeSafety/CMakeLists.txt | 2 +- clang/lib/Analysis/LifetimeSafety/Facts.cpp | 8 ++-- .../LifetimeSafety/OriginFlowChain.cpp | 46 +++++++++++++++++++ .../unittests/Analysis/LifetimeSafetyTest.cpp | 38 ++++++--------- 7 files changed, 76 insertions(+), 92 deletions(-) rename clang/include/clang/Analysis/Analyses/LifetimeSafety/{AssignmentQuery.h => OriginFlowChain.h} (54%) delete mode 100644 clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp create mode 100644 clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h index 232bbb9b3d2c5..88b509e1b94df 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h @@ -346,16 +346,6 @@ class FactManager { return BlockToFacts[B->getBlockID()]; } - std::optional<size_t> getBlockID(const Fact *TargetFact) const { - for (size_t i = 0; i < BlockToFacts.size(); ++i) { - for (const Fact *F : BlockToFacts[i]) { - if (F == TargetFact) - return i; - } - } - return std::nullopt; - } - void addBlockFacts(const CFGBlock *B, llvm::ArrayRef<Fact *> NewFacts) { if (!NewFacts.empty()) BlockToFacts[B->getBlockID()].assign(NewFacts.begin(), NewFacts.end()); diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h similarity index 54% rename from clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h rename to clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h index 06dc77e914554..85e8b057da302 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h @@ -1,4 +1,4 @@ -//===- AssignmentQuery.cpp - C++ Lifetime Safety Checker --------*- C++ -*-===// +//====- OriginFlowChain.h - C++ Lifetime Safety Checker --------*- 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,8 +6,9 @@ // //===----------------------------------------------------------------------===// // -// This file defines functions for tracing assignment history, -// as well as future data structures or other helper functions. +// This file defines buildOriginFlowChain, which is used to build the +// propagation flow of a given Loan within a specified Origin, starting +// from a particular ProgramPoint. // //===----------------------------------------------------------------------===// @@ -19,18 +20,15 @@ namespace clang::lifetimes::internal { -using AssignmentUnit = Origin; - -/// Traces the provenance of a pointer to provide contextual notes for -/// lifetime-related diagnostics. +/// Builds a chain of origin flows for a specific loan. It tracks how the Loan +/// moves and transforms. /// -/// To help user understand the data flow, we track where the problematic -/// address originated. -void trackAssignmentHistory( +/// This function starts from a given ProgramPoint and builds the propagation +/// flow of the specified LoanID within the context of a given OriginID. +llvm::SmallVector<OriginID> buildOriginFlowChain( const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, - llvm::SmallVectorImpl<AssignmentUnit> &AssignmentList, - const CFGBlock *StartBlock, const OriginID StartOID, - const LoanID &EndLoanID); + ProgramPoint StartPoint, const OriginID StartOID, + const LoanID TargetLoan); } // namespace clang::lifetimes::internal #endif diff --git a/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp b/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp deleted file mode 100644 index c50f88165268d..0000000000000 --- a/clang/lib/Analysis/LifetimeSafety/AssignmentQuery.cpp +++ /dev/null @@ -1,40 +0,0 @@ -//===- AssignmentQuery.cpp - C++ Lifetime Safety Checker --------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file implements trackAssignmentHistory. -// -//===----------------------------------------------------------------------===// - -#include "clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h" - -namespace clang::lifetimes::internal { -void trackAssignmentHistory( - const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, - llvm::SmallVectorImpl<AssignmentUnit> &AssignmentList, - const CFGBlock *StartBlock, OriginID StartOID, const LoanID &EndLoanID) { - const auto TryInsertPropagationChain = [&](const OriginFlowFact *OFF) { - if (OFF->getDestOriginID() == StartOID && - LoanPropagation.getLoans(OFF->getSrcOriginID(), OFF) - .contains(EndLoanID)) { - const OriginID SrcOriginID = OFF->getSrcOriginID(); - AssignmentList.push_back(FactMgr.getOriginMgr().getOrigin(SrcOriginID)); - StartOID = SrcOriginID; - } - }; - - llvm::ArrayRef<const Fact *> Facts = FactMgr.getFacts(StartBlock); - for (const Fact *F : llvm::reverse(Facts)) { - if (const auto *OFF = F->getAs<OriginFlowFact>()) { - TryInsertPropagationChain(OFF); - } else if (const auto *IF = F->getAs<IssueFact>()) { - if (IF->getLoanID() == EndLoanID) - return; - } - } -} -} // namespace clang::lifetimes::internal diff --git a/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt b/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt index 6c4d4e123908a..0888b24ebfd5f 100644 --- a/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt +++ b/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt @@ -1,5 +1,4 @@ add_clang_library(clangAnalysisLifetimeSafety - AssignmentQuery.cpp Checker.cpp Facts.cpp FactsGenerator.cpp @@ -10,6 +9,7 @@ add_clang_library(clangAnalysisLifetimeSafety Loans.cpp LoanPropagation.cpp MovedLoans.cpp + OriginFlowChain.cpp Origins.cpp LINK_LIBS diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index 8a71fb8404cfe..3d7fbcdacc830 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp @@ -145,9 +145,11 @@ void FactManager::dump(const CFG &Cfg, AnalysisDeclContext &AC) const { llvm::ArrayRef<const Fact *> FactManager::getBlockContaining(ProgramPoint P) const { - std::optional<size_t> BlockIndex = getBlockID(P); - if (BlockIndex) - return BlockToFacts[BlockIndex.value()]; + for (const auto &BlockToFactsVec : BlockToFacts) { + for (const Fact *F : BlockToFactsVec) + if (F == P) + return BlockToFactsVec; + } return {}; } diff --git a/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp b/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp new file mode 100644 index 0000000000000..62ec8cd477b9f --- /dev/null +++ b/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp @@ -0,0 +1,46 @@ +//===- OriginFlowChain.cpp - C++ Lifetime Safety Checker --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements buildOriginFlowChain. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h" + +namespace clang::lifetimes::internal { +llvm::SmallVector<OriginID> buildOriginFlowChain( + const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, + ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan) { + + const auto hasLoanAtOrigin = [&LoanPropagation](OriginID OID, LoanID LID, ProgramPoint CurrPoint) { + return LoanPropagation.getLoans(OID, CurrPoint).contains(LID); + }; + + assert(hasLoanAtOrigin(StartOID, TargetLoan, StartPoint) && "TargetLoan must be present in the initial propagation point"); + + OriginID CurrOID = StartOID; + llvm::SmallVector<OriginID> AssignmentList; + llvm::ArrayRef<const Fact *> Facts = FactMgr.getBlockContaining(StartPoint); + + for (const Fact *F : llvm::reverse(Facts)) { + if (const auto *OFF = F->getAs<OriginFlowFact>()) { + const OriginID SrcOriginID = OFF->getSrcOriginID(); + if (OFF->getDestOriginID() != CurrOID) continue; + if (!hasLoanAtOrigin(SrcOriginID, TargetLoan, OFF)) + continue; + AssignmentList.push_back(SrcOriginID); + CurrOID = SrcOriginID; + } else if (const auto *IF = F->getAs<IssueFact>()) { + if (IF->getLoanID() == TargetLoan) + return AssignmentList; + } + } + + return AssignmentList; +} +} // namespace clang::lifetimes::internal diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 97a45d40b989d..6a841ab3c8e07 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -9,8 +9,8 @@ #include "clang/Analysis/Analyses/LifetimeSafety/LifetimeSafety.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" -#include "clang/Analysis/Analyses/LifetimeSafety/AssignmentQuery.h" #include "clang/Analysis/Analyses/LifetimeSafety/Loans.h" +#include "clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h" #include "clang/Testing/TestAST.h" #include "llvm/ADT/StringMap.h" #include "gmock/gmock.h" @@ -205,32 +205,20 @@ class LifetimeTestHelper { return Runner.getAnalysis().getFactManager().getBlockContaining(P); } - std::optional<size_t> getBlockID(ProgramPoint P) { - return Runner.getAnalysis().getFactManager().getBlockID(P); - } - - void trackAssignmentHistoryInOneBlock( - llvm::SmallVectorImpl<AssignmentUnit> &AssignmentList, - llvm::StringRef StartOriginVar, llvm::StringRef EndLoanVar) { + llvm::SmallVector<OriginID> buildOriginFlowChainInOneBlock( + llvm::StringRef StartOriginVar, llvm::StringRef EndLoanVar, llvm::StringRef Annotation) { std::optional<OriginID> StartOriginID = getOriginForDecl(StartOriginVar); std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); - const CFGBlock *StartBlock = nullptr; - const size_t BlockID = getBlockID(getProgramPoint("after_use")).value(); - for (const CFGBlock *CurrBlock : *Runner.getAnalysisContext().getCFG()) { - if (CurrBlock->getBlockID() == BlockID) { - StartBlock = CurrBlock; - break; - } - } - for (const LoanID &LID : EndLoanIDs) { - trackAssignmentHistory(Runner.getAnalysis().getFactManager(), + const llvm::SmallVector<OriginID> OriginFlowChain = buildOriginFlowChain(Runner.getAnalysis().getFactManager(), Runner.getAnalysis().getLoanPropagation(), - AssignmentList, StartBlock, *StartOriginID, LID); - if (!AssignmentList.empty()) - return; + getProgramPoint(Annotation), *StartOriginID, LID); + if (!OriginFlowChain.empty()) + return OriginFlowChain; } + + return {}; } private: @@ -1985,7 +1973,7 @@ TEST_F(LifetimeAnalysisTest, LambdaInitCaptureViewByValue) { // Tests for trackAssignmentHistory // ========================================================================= // -TEST_F(LifetimeAnalysisTest, TrackLinearAssignmentHistoryInOneBlock) { +TEST_F(LifetimeAnalysisTest, BuildLinearOriginFlowChainInOneBlock) { SetupTest(R"( void target() { int *s; @@ -2002,10 +1990,10 @@ TEST_F(LifetimeAnalysisTest, TrackLinearAssignmentHistoryInOneBlock) { } )"); - llvm::SmallVector<AssignmentUnit> AssignmentList; - Helper->trackAssignmentHistoryInOneBlock(AssignmentList, "s", "tgt"); + const llvm::SmallVector<OriginID> OriginFlowChain = Helper->buildOriginFlowChainInOneBlock("s", "tgt", "after_use"); - EXPECT_EQ(8u, AssignmentList.size()); + // 8 == 2 * (e + b + a + tgt) + EXPECT_EQ(8u, OriginFlowChain.size()); } } // anonymous namespace } // namespace clang::lifetimes::internal >From 55e7fea714a7c3652c05946af2809403b1d027a2 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Tue, 12 May 2026 22:49:18 +0800 Subject: [PATCH 5/9] fix for clang-format Signed-off-by: Yuan Suo <[email protected]> --- .../Analyses/LifetimeSafety/OriginFlowChain.h | 3 +-- .../Analysis/LifetimeSafety/OriginFlowChain.cpp | 9 ++++++--- clang/unittests/Analysis/LifetimeSafetyTest.cpp | 16 ++++++++++------ 3 files changed, 17 insertions(+), 11 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h index 85e8b057da302..090a18560923b 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h @@ -27,8 +27,7 @@ namespace clang::lifetimes::internal { /// flow of the specified LoanID within the context of a given OriginID. llvm::SmallVector<OriginID> buildOriginFlowChain( const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, - ProgramPoint StartPoint, const OriginID StartOID, - const LoanID TargetLoan); + ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan); } // namespace clang::lifetimes::internal #endif diff --git a/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp b/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp index 62ec8cd477b9f..dcd7229f452cb 100644 --- a/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp +++ b/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp @@ -17,11 +17,13 @@ llvm::SmallVector<OriginID> buildOriginFlowChain( const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan) { - const auto hasLoanAtOrigin = [&LoanPropagation](OriginID OID, LoanID LID, ProgramPoint CurrPoint) { + const auto hasLoanAtOrigin = [&LoanPropagation](OriginID OID, LoanID LID, + ProgramPoint CurrPoint) { return LoanPropagation.getLoans(OID, CurrPoint).contains(LID); }; - assert(hasLoanAtOrigin(StartOID, TargetLoan, StartPoint) && "TargetLoan must be present in the initial propagation point"); + assert(hasLoanAtOrigin(StartOID, TargetLoan, StartPoint) && + "TargetLoan must be present in the initial propagation point"); OriginID CurrOID = StartOID; llvm::SmallVector<OriginID> AssignmentList; @@ -30,7 +32,8 @@ llvm::SmallVector<OriginID> buildOriginFlowChain( for (const Fact *F : llvm::reverse(Facts)) { if (const auto *OFF = F->getAs<OriginFlowFact>()) { const OriginID SrcOriginID = OFF->getSrcOriginID(); - if (OFF->getDestOriginID() != CurrOID) continue; + if (OFF->getDestOriginID() != CurrOID) + continue; if (!hasLoanAtOrigin(SrcOriginID, TargetLoan, OFF)) continue; AssignmentList.push_back(SrcOriginID); diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 6a841ab3c8e07..d8eefc23f4f44 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -205,15 +205,18 @@ class LifetimeTestHelper { return Runner.getAnalysis().getFactManager().getBlockContaining(P); } - llvm::SmallVector<OriginID> buildOriginFlowChainInOneBlock( - llvm::StringRef StartOriginVar, llvm::StringRef EndLoanVar, llvm::StringRef Annotation) { + llvm::SmallVector<OriginID> + buildOriginFlowChainInOneBlock(llvm::StringRef StartOriginVar, + llvm::StringRef EndLoanVar, + llvm::StringRef Annotation) { std::optional<OriginID> StartOriginID = getOriginForDecl(StartOriginVar); std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); for (const LoanID &LID : EndLoanIDs) { - const llvm::SmallVector<OriginID> OriginFlowChain = buildOriginFlowChain(Runner.getAnalysis().getFactManager(), - Runner.getAnalysis().getLoanPropagation(), - getProgramPoint(Annotation), *StartOriginID, LID); + const llvm::SmallVector<OriginID> OriginFlowChain = buildOriginFlowChain( + Runner.getAnalysis().getFactManager(), + Runner.getAnalysis().getLoanPropagation(), + getProgramPoint(Annotation), *StartOriginID, LID); if (!OriginFlowChain.empty()) return OriginFlowChain; } @@ -1990,7 +1993,8 @@ TEST_F(LifetimeAnalysisTest, BuildLinearOriginFlowChainInOneBlock) { } )"); - const llvm::SmallVector<OriginID> OriginFlowChain = Helper->buildOriginFlowChainInOneBlock("s", "tgt", "after_use"); + const llvm::SmallVector<OriginID> OriginFlowChain = + Helper->buildOriginFlowChainInOneBlock("s", "tgt", "after_use"); // 8 == 2 * (e + b + a + tgt) EXPECT_EQ(8u, OriginFlowChain.size()); >From dd4352150e8776418940dc3fd8b924da1ed86e80 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Thu, 14 May 2026 20:51:28 +0800 Subject: [PATCH 6/9] fix style and logic for previous commit Address forgotten naming updates, reduce for-loop nesting depth, and fix an incorrect return behavior. Signed-off-by: Yuan Suo <[email protected]> --- .../Analyses/LifetimeSafety/OriginFlowChain.h | 4 +-- .../LifetimeSafety/OriginFlowChain.cpp | 28 ++++++++++--------- .../unittests/Analysis/LifetimeSafetyTest.cpp | 4 +-- 3 files changed, 19 insertions(+), 17 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h index 090a18560923b..c1440cd99a695 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_ASSIGNMENTQUERY_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_ASSIGNMENTQUERY_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINFLOWCHAIN_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINFLOWCHAIN_H #include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" #include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h" diff --git a/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp b/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp index dcd7229f452cb..f684d62bccc99 100644 --- a/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp +++ b/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp @@ -26,24 +26,26 @@ llvm::SmallVector<OriginID> buildOriginFlowChain( "TargetLoan must be present in the initial propagation point"); OriginID CurrOID = StartOID; - llvm::SmallVector<OriginID> AssignmentList; + llvm::SmallVector<OriginID> OriginFlowChain; llvm::ArrayRef<const Fact *> Facts = FactMgr.getBlockContaining(StartPoint); for (const Fact *F : llvm::reverse(Facts)) { - if (const auto *OFF = F->getAs<OriginFlowFact>()) { - const OriginID SrcOriginID = OFF->getSrcOriginID(); - if (OFF->getDestOriginID() != CurrOID) - continue; - if (!hasLoanAtOrigin(SrcOriginID, TargetLoan, OFF)) - continue; - AssignmentList.push_back(SrcOriginID); - CurrOID = SrcOriginID; - } else if (const auto *IF = F->getAs<IssueFact>()) { + if (const auto *IF = F->getAs<IssueFact>()) if (IF->getLoanID() == TargetLoan) - return AssignmentList; - } + return OriginFlowChain; + + const auto *OFF = F->getAs<OriginFlowFact>(); + if (!OFF) + continue; + const OriginID SrcOriginID = OFF->getSrcOriginID(); + if (OFF->getDestOriginID() != CurrOID) + continue; + if (!hasLoanAtOrigin(SrcOriginID, TargetLoan, OFF)) + continue; + OriginFlowChain.push_back(SrcOriginID); + CurrOID = SrcOriginID; } - return AssignmentList; + return {}; } } // namespace clang::lifetimes::internal diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index d8eefc23f4f44..32fdd839b39c3 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -212,7 +212,7 @@ class LifetimeTestHelper { std::optional<OriginID> StartOriginID = getOriginForDecl(StartOriginVar); std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); - for (const LoanID &LID : EndLoanIDs) { + for (LoanID LID : EndLoanIDs) { const llvm::SmallVector<OriginID> OriginFlowChain = buildOriginFlowChain( Runner.getAnalysis().getFactManager(), Runner.getAnalysis().getLoanPropagation(), @@ -1973,7 +1973,7 @@ TEST_F(LifetimeAnalysisTest, LambdaInitCaptureViewByValue) { } // ========================================================================= // -// Tests for trackAssignmentHistory +// Tests for buildOriginFlowChain // ========================================================================= // TEST_F(LifetimeAnalysisTest, BuildLinearOriginFlowChainInOneBlock) { >From eedb6c1fef9152486168abceac554a1df0214008 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Thu, 14 May 2026 21:05:11 +0800 Subject: [PATCH 7/9] add a death test Since an assert was added to `buildOriginFlowChain`, we can now verify this behavior in unit tests. Signed-off-by: Yuan Suo <[email protected]> --- clang/unittests/Analysis/LifetimeSafetyTest.cpp | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 32fdd839b39c3..5c9ee558b63c7 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -1998,6 +1998,11 @@ TEST_F(LifetimeAnalysisTest, BuildLinearOriginFlowChainInOneBlock) { // 8 == 2 * (e + b + a + tgt) EXPECT_EQ(8u, OriginFlowChain.size()); + +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(Helper->buildOriginFlowChainInOneBlock("s", "e", "after_use"), + "TargetLoan must be present in the initial propagation point"); +#endif } } // anonymous namespace } // namespace clang::lifetimes::internal >From 1c05c655b0b03700f3a3409c4f398a938cedfed6 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Mon, 18 May 2026 14:24:47 +0800 Subject: [PATCH 8/9] move buildOriginFlowChain into LoanPropagationAnalysis This is because `buildOriginFlowChain` is currently simple enough to not warrant a separate file, and this also simplifies the API's arguments. Add more test cases to the unit tests. Signed-off-by: Yuan Suo <[email protected]> --- .../Analyses/LifetimeSafety/LoanPropagation.h | 10 ++++ .../Analyses/LifetimeSafety/OriginFlowChain.h | 33 ------------ .../Analysis/LifetimeSafety/CMakeLists.txt | 1 - .../LifetimeSafety/LoanPropagation.cpp | 36 +++++++++++++ .../LifetimeSafety/OriginFlowChain.cpp | 51 ------------------- .../unittests/Analysis/LifetimeSafetyTest.cpp | 49 +++++++++--------- 6 files changed, 72 insertions(+), 108 deletions(-) delete mode 100644 clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h delete mode 100644 clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h index 447d05ca898fd..168223c42e2b2 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h @@ -38,6 +38,16 @@ class LoanPropagationAnalysis { LoanSet getLoans(OriginID OID, ProgramPoint P) const; + /// Builds the chain of origins through which a loan has propagated. + /// + /// Starting from StartPoint where StartOID currently holds TargetLoan, + /// this function traces backwards through OriginFlowFacts to identify the + /// sequence of origins through which the loan flowed, ending at the origin + /// where the loan was originally issued. + llvm::SmallVector<OriginID> + buildOriginFlowChain(const FactManager &FactMgr, ProgramPoint StartPoint, + const OriginID StartOID, const LoanID TargetLoan) const; + private: class Impl; std::unique_ptr<Impl> PImpl; diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h deleted file mode 100644 index c1440cd99a695..0000000000000 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h +++ /dev/null @@ -1,33 +0,0 @@ -//====- OriginFlowChain.h - C++ Lifetime Safety Checker --------*- C++ -*-====// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file defines buildOriginFlowChain, which is used to build the -// propagation flow of a given Loan within a specified Origin, starting -// from a particular ProgramPoint. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINFLOWCHAIN_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_ORIGINFLOWCHAIN_H - -#include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" -#include "clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h" - -namespace clang::lifetimes::internal { - -/// Builds a chain of origin flows for a specific loan. It tracks how the Loan -/// moves and transforms. -/// -/// This function starts from a given ProgramPoint and builds the propagation -/// flow of the specified LoanID within the context of a given OriginID. -llvm::SmallVector<OriginID> buildOriginFlowChain( - const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, - ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan); -} // namespace clang::lifetimes::internal - -#endif diff --git a/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt b/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt index 0888b24ebfd5f..247377c7256d9 100644 --- a/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt +++ b/clang/lib/Analysis/LifetimeSafety/CMakeLists.txt @@ -9,7 +9,6 @@ add_clang_library(clangAnalysisLifetimeSafety Loans.cpp LoanPropagation.cpp MovedLoans.cpp - OriginFlowChain.cpp Origins.cpp LINK_LIBS diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index adbc0458516e1..f85dddd6107bc 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -247,4 +247,40 @@ LoanPropagationAnalysis::~LoanPropagationAnalysis() = default; LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const { return PImpl->getLoans(OID, P); } + +llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( + const FactManager &FactMgr, ProgramPoint StartPoint, + const OriginID StartOID, const LoanID TargetLoan) const { + assert(getLoans(StartOID, StartPoint).contains(TargetLoan) && + "TargetLoan must be present in the StartOID at the StartPoint"); + + OriginID CurrOID = StartOID; + llvm::SmallVector<OriginID> OriginFlowChain; + llvm::ArrayRef<const Fact *> Facts = FactMgr.getBlockContaining(StartPoint); + + for (const Fact *F : llvm::reverse(Facts)) { + if (const auto *IF = F->getAs<IssueFact>()) + if (IF->getLoanID() == TargetLoan && IF->getOriginID() == CurrOID) + return OriginFlowChain; + + const auto *OFF = F->getAs<OriginFlowFact>(); + if (!OFF) + continue; + if (OFF->getDestOriginID() != CurrOID) + continue; + + const OriginID SrcOriginID = OFF->getSrcOriginID(); + if (!getLoans(SrcOriginID, OFF).contains(TargetLoan)) + continue; + OriginFlowChain.push_back(SrcOriginID); + CurrOID = SrcOriginID; + } + + // FIXME: Ideally, this return is unreachable and should be an assert because + // we expect to return via IssueFact. But since current traversal is limited + // to a single CFG block, multi-block OriginFlowChain construction might miss + // the IssueFact. + // We should add llvm_unreachable here once multi-block support is implemented + return {}; +} } // namespace clang::lifetimes::internal diff --git a/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp b/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp deleted file mode 100644 index f684d62bccc99..0000000000000 --- a/clang/lib/Analysis/LifetimeSafety/OriginFlowChain.cpp +++ /dev/null @@ -1,51 +0,0 @@ -//===- OriginFlowChain.cpp - C++ Lifetime Safety Checker --------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file implements buildOriginFlowChain. -// -//===----------------------------------------------------------------------===// - -#include "clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h" - -namespace clang::lifetimes::internal { -llvm::SmallVector<OriginID> buildOriginFlowChain( - const FactManager &FactMgr, const LoanPropagationAnalysis &LoanPropagation, - ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan) { - - const auto hasLoanAtOrigin = [&LoanPropagation](OriginID OID, LoanID LID, - ProgramPoint CurrPoint) { - return LoanPropagation.getLoans(OID, CurrPoint).contains(LID); - }; - - assert(hasLoanAtOrigin(StartOID, TargetLoan, StartPoint) && - "TargetLoan must be present in the initial propagation point"); - - OriginID CurrOID = StartOID; - llvm::SmallVector<OriginID> OriginFlowChain; - llvm::ArrayRef<const Fact *> Facts = FactMgr.getBlockContaining(StartPoint); - - for (const Fact *F : llvm::reverse(Facts)) { - if (const auto *IF = F->getAs<IssueFact>()) - if (IF->getLoanID() == TargetLoan) - return OriginFlowChain; - - const auto *OFF = F->getAs<OriginFlowFact>(); - if (!OFF) - continue; - const OriginID SrcOriginID = OFF->getSrcOriginID(); - if (OFF->getDestOriginID() != CurrOID) - continue; - if (!hasLoanAtOrigin(SrcOriginID, TargetLoan, OFF)) - continue; - OriginFlowChain.push_back(SrcOriginID); - CurrOID = SrcOriginID; - } - - return {}; -} -} // namespace clang::lifetimes::internal diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 5c9ee558b63c7..ba991c9d25c9e 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -10,7 +10,6 @@ #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/Analysis/Analyses/LifetimeSafety/Loans.h" -#include "clang/Analysis/Analyses/LifetimeSafety/OriginFlowChain.h" #include "clang/Testing/TestAST.h" #include "llvm/ADT/StringMap.h" #include "gmock/gmock.h" @@ -213,10 +212,10 @@ class LifetimeTestHelper { std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); for (LoanID LID : EndLoanIDs) { - const llvm::SmallVector<OriginID> OriginFlowChain = buildOriginFlowChain( - Runner.getAnalysis().getFactManager(), - Runner.getAnalysis().getLoanPropagation(), - getProgramPoint(Annotation), *StartOriginID, LID); + const llvm::SmallVector<OriginID> OriginFlowChain = + Runner.getAnalysis().getLoanPropagation().buildOriginFlowChain( + Runner.getAnalysis().getFactManager(), + getProgramPoint(Annotation), *StartOriginID, LID); if (!OriginFlowChain.empty()) return OriginFlowChain; } @@ -1976,19 +1975,28 @@ TEST_F(LifetimeAnalysisTest, LambdaInitCaptureViewByValue) { // Tests for buildOriginFlowChain // ========================================================================= // -TEST_F(LifetimeAnalysisTest, BuildLinearOriginFlowChainInOneBlock) { +TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithErrorTargetLoan) { SetupTest(R"( void target() { - int *s; - { - int tgt = 2; - int *a = &tgt; - int *c = a; - int *b = a; - int *e = b; - s = e; - } - (void)s; + int tgt = 2; + int *a = &tgt; + int *s = a; + POINT(after_use); + } + )"); + +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(Helper->buildOriginFlowChainInOneBlock("s", "a", "after_use"), + "TargetLoan must be present in the StartOID at the StartPoint"); +#endif +} + +TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithSelfAssignment) { + SetupTest(R"( + void target() { + int tgt = 2; + int *a = &tgt; + int *s = a; POINT(after_use); } )"); @@ -1996,13 +2004,8 @@ TEST_F(LifetimeAnalysisTest, BuildLinearOriginFlowChainInOneBlock) { const llvm::SmallVector<OriginID> OriginFlowChain = Helper->buildOriginFlowChainInOneBlock("s", "tgt", "after_use"); - // 8 == 2 * (e + b + a + tgt) - EXPECT_EQ(8u, OriginFlowChain.size()); - -#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST - EXPECT_DEATH(Helper->buildOriginFlowChainInOneBlock("s", "e", "after_use"), - "TargetLoan must be present in the initial propagation point"); -#endif + EXPECT_TRUE( + llvm::is_contained(OriginFlowChain, *Helper->getOriginForDecl("a"))); } } // anonymous namespace } // namespace clang::lifetimes::internal >From 390405c2e1ecc00a309245661123704f84c83ac2 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Mon, 18 May 2026 17:54:59 +0800 Subject: [PATCH 9/9] address review comments and polish previous changes Signed-off-by: Yuan Suo <[email protected]> --- .../LifetimeSafety/LoanPropagation.cpp | 21 +++++--- .../unittests/Analysis/LifetimeSafetyTest.cpp | 53 +++++++++++++++++++ 2 files changed, 68 insertions(+), 6 deletions(-) diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index f85dddd6107bc..59cbffb65c24d 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -254,14 +254,22 @@ llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( assert(getLoans(StartOID, StartPoint).contains(TargetLoan) && "TargetLoan must be present in the StartOID at the StartPoint"); + size_t StartIndex = 0; OriginID CurrOID = StartOID; llvm::SmallVector<OriginID> OriginFlowChain; llvm::ArrayRef<const Fact *> Facts = FactMgr.getBlockContaining(StartPoint); - for (const Fact *F : llvm::reverse(Facts)) { + for (; StartIndex < Facts.size(); ++StartIndex) + if (Facts[StartIndex] == StartPoint) + break; + + for (size_t i = StartIndex + 1; i > 0; --i) { + const Fact *F = Facts[i - 1]; if (const auto *IF = F->getAs<IssueFact>()) - if (IF->getLoanID() == TargetLoan && IF->getOriginID() == CurrOID) + if (IF->getLoanID() == TargetLoan) { + assert(IF->getOriginID() == CurrOID); return OriginFlowChain; + } const auto *OFF = F->getAs<OriginFlowFact>(); if (!OFF) @@ -277,10 +285,11 @@ llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( } // FIXME: Ideally, this return is unreachable and should be an assert because - // we expect to return via IssueFact. But since current traversal is limited - // to a single CFG block, multi-block OriginFlowChain construction might miss - // the IssueFact. - // We should add llvm_unreachable here once multi-block support is implemented + // we expect to always finish at a IssueFact. But since current traversal is + // limited to a single CFG block, multi-block OriginFlowChain construction + // might miss the IssueFact. + // We should add llvm_unreachable here once multi-block support is + // implemented. return {}; } } // namespace clang::lifetimes::internal diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index ba991c9d25c9e..26bd0fe970044 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -1996,6 +1996,9 @@ TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithSelfAssignment) { void target() { int tgt = 2; int *a = &tgt; + int *b = a; + a = b; + a = a; int *s = a; POINT(after_use); } @@ -2007,5 +2010,55 @@ TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithSelfAssignment) { EXPECT_TRUE( llvm::is_contained(OriginFlowChain, *Helper->getOriginForDecl("a"))); } + +TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithLifetimeBound) { + SetupTest(R"( + int* choose(int* a [[clang::lifetimebound]], int* b [[clang::lifetimebound]]); + void target() { + int tgta = 1, tgtb = 2; + int *a = &tgta; + int *b = &tgtb; + int *result = choose(a, b); + result = choose(result , result); + int *s = result; + POINT(after_use); + } + )"); + + const llvm::SmallVector<OriginID> OriginFlowChainForTgtA = + Helper->buildOriginFlowChainInOneBlock("s", "tgta", "after_use"); + + const llvm::SmallVector<OriginID> OriginFlowChainForTgtB = + Helper->buildOriginFlowChainInOneBlock("s", "tgtb", "after_use"); + + EXPECT_TRUE(llvm::is_contained(OriginFlowChainForTgtA, + *Helper->getOriginForDecl("a"))); + EXPECT_FALSE(llvm::is_contained(OriginFlowChainForTgtA, + *Helper->getOriginForDecl("b"))); + EXPECT_TRUE(llvm::is_contained(OriginFlowChainForTgtB, + *Helper->getOriginForDecl("b"))); + EXPECT_FALSE(llvm::is_contained(OriginFlowChainForTgtB, + *Helper->getOriginForDecl("a"))); +} + +TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithMultiAssignInSameStmt) { + SetupTest(R"( + void target() { + int tgt = 2; + int *a, *b, *c; + a = b = c = &tgt; + int *s = a; + POINT(after_use); + } + )"); + +// FIXME: Handle chained assignments. The current implementation lacks this +// support, causing the assertion failure. +// https://github.com/llvm/llvm-project/pull/196075#discussion_r3264392605 +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(Helper->buildOriginFlowChainInOneBlock("s", "a", "after_use"), + "TargetLoan must be present in the StartOID at the StartPoint"); +#endif +} } // anonymous namespace } // namespace clang::lifetimes::internal _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
