https://github.com/suoyuan666 created https://github.com/llvm/llvm-project/pull/196075
## Summary Tracking assignment history allows us to backtrack and provide more informative error messages, helping users better understand the root cause. As discussed in https://github.com/llvm/llvm-project/pull/188467#issuecomment-4359071778, I am splitting the original #188467 into smaller parts. This PR submits the core logic: performing a reverse search for assignment history within a single CFG block. A simple unit test has been added to verify the basic functionality of the algorithm. ## Details The backtracking logic follows these steps: 1. Identify the LHS in `OriginFlowFact` - In a standard assignment like `a = b`, `DestOrigin` typically stores the `ValueDecl` of `a` rather than the specific `DeclRefExpr`. Therefore, we need to inspect the adjacent `UseFact && UseFact->isWritten()` to retrieve the corresponding `UseExpr`. This ensures we can capture the precise source location for later diagnostic output. 2. Identify the RHS - Once the LHS is secured, the logic looks for an `Expr` in subsequent `OriginFlowFact` that can serve as the RHS. I have omitted "same-line" comparisons. Since the identification logic for LHS and RHS is distinct enough to prevent overlaps, the algorithm can safely transition to RHS retrieval immediately after the LHS is found, effectively skipping the rest of the current line's context. >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] [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 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
