https://github.com/usx95 updated
https://github.com/llvm/llvm-project/pull/148712
>From c29040affacaf2f58fa8e218adfbdec30fac20b5 Mon Sep 17 00:00:00 2001
From: Utkarsh Saxena <u...@google.com>
Date: Mon, 14 Jul 2025 19:37:49 +0000
Subject: [PATCH] [LifetimeSafety] Add loan expiry analysis
---
.../clang/Analysis/Analyses/LifetimeSafety.h | 9 +
clang/lib/Analysis/LifetimeSafety.cpp | 77 ++++-
.../unittests/Analysis/LifetimeSafetyTest.cpp | 279 +++++++++++++++++-
3 files changed, 357 insertions(+), 8 deletions(-)
diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
index beeb0aaba5d0d..1c00558d32f63 100644
--- a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
+++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
@@ -33,6 +33,7 @@ namespace internal {
class Fact;
class FactManager;
class LoanPropagationAnalysis;
+class ExpiredLoansAnalysis;
struct LifetimeFactory;
/// A generic, type-safe wrapper for an ID, distinguished by its `Tag` type.
@@ -52,6 +53,10 @@ template <typename Tag> struct ID {
IDBuilder.AddInteger(Value);
}
};
+template <typename Tag>
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ID<Tag> ID) {
+ return OS << ID.Value;
+}
using LoanID = ID<struct LoanTag>;
using OriginID = ID<struct OriginTag>;
@@ -81,6 +86,9 @@ class LifetimeSafetyAnalysis {
/// Returns the set of loans an origin holds at a specific program point.
LoanSet getLoansAtPoint(OriginID OID, ProgramPoint PP) const;
+ /// Returns the set of loans that have expired at a specific program point.
+ LoanSet getExpiredLoansAtPoint(ProgramPoint PP) const;
+
/// Finds the OriginID for a given declaration.
/// Returns a null optional if not found.
std::optional<OriginID> getOriginIDForDecl(const ValueDecl *D) const;
@@ -105,6 +113,7 @@ class LifetimeSafetyAnalysis {
std::unique_ptr<LifetimeFactory> Factory;
std::unique_ptr<FactManager> FactMgr;
std::unique_ptr<LoanPropagationAnalysis> LoanPropagation;
+ std::unique_ptr<ExpiredLoansAnalysis> ExpiredLoans;
};
} // namespace internal
} // namespace clang::lifetimes
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp
b/clang/lib/Analysis/LifetimeSafety.cpp
index ae6ec9f76cbf6..815a36e13412c 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -23,14 +23,15 @@
#include "llvm/Support/Debug.h"
#include "llvm/Support/TimeProfiler.h"
#include <cstdint>
+#include <memory>
namespace clang::lifetimes {
namespace internal {
namespace {
-template <typename Tag>
-inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ID<Tag> ID) {
- return OS << ID.Value;
-}
+// template <typename Tag>
+// inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ID<Tag> ID) {
+// return OS << ID.Value;
+// }
} // namespace
/// Represents the storage location being borrowed, e.g., a specific stack
@@ -832,6 +833,65 @@ class LoanPropagationAnalysis
}
};
+// ========================================================================= //
+// Expired Loans Analysis
+// ========================================================================= //
+
+/// The dataflow lattice for tracking the set of expired loans.
+struct ExpiredLattice {
+ LoanSet Expired;
+
+ ExpiredLattice() : Expired(nullptr) {};
+ explicit ExpiredLattice(LoanSet S) : Expired(S) {}
+
+ bool operator==(const ExpiredLattice &Other) const {
+ return Expired == Other.Expired;
+ }
+ bool operator!=(const ExpiredLattice &Other) const {
+ return !(*this == Other);
+ }
+
+ void dump(llvm::raw_ostream &OS) const {
+ OS << "ExpiredLattice State:\n";
+ if (Expired.isEmpty())
+ OS << " <empty>\n";
+ for (const LoanID &LID : Expired)
+ OS << " Loan " << LID << " is expired\n";
+ }
+};
+
+/// The analysis that tracks which loans have expired.
+class ExpiredLoansAnalysis
+ : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice,
+ Direction::Forward> {
+
+ LoanSet::Factory &Factory;
+
+public:
+ ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
+ LifetimeFactory &Factory)
+ : DataflowAnalysis(C, AC, F), Factory(Factory.LoanSetFactory) {}
+
+ using Base::transfer;
+
+ StringRef getAnalysisName() const { return "ExpiredLoans"; }
+
+ Lattice getInitialState() { return Lattice(Factory.getEmptySet()); }
+
+ /// Merges two lattices by taking the union of the expired loan sets.
+ Lattice join(Lattice L1, Lattice L2) const {
+ return Lattice(utils::join(L1.Expired, L2.Expired, Factory));
+ }
+
+ Lattice transfer(Lattice In, const ExpireFact &F) {
+ return Lattice(Factory.add(In.Expired, F.getLoanID()));
+ }
+
+ Lattice transfer(Lattice In, const IssueFact &F) {
+ return Lattice(Factory.remove(In.Expired, F.getLoanID()));
+ }
+};
+
// ========================================================================= //
// TODO:
// - Modify loan expiry analysis to answer `bool isExpired(Loan L, Point P)`
@@ -873,6 +933,10 @@ void LifetimeSafetyAnalysis::run() {
LoanPropagation =
std::make_unique<LoanPropagationAnalysis>(Cfg, AC, *FactMgr, *Factory);
LoanPropagation->run();
+
+ ExpiredLoans =
+ std::make_unique<ExpiredLoansAnalysis>(Cfg, AC, *FactMgr, *Factory);
+ ExpiredLoans->run();
}
LoanSet LifetimeSafetyAnalysis::getLoansAtPoint(OriginID OID,
@@ -881,6 +945,11 @@ LoanSet LifetimeSafetyAnalysis::getLoansAtPoint(OriginID
OID,
return LoanPropagation->getLoans(OID, PP);
}
+LoanSet LifetimeSafetyAnalysis::getExpiredLoansAtPoint(ProgramPoint PP) const {
+ assert(ExpiredLoans && "ExpiredLoansAnalysis has not been run.");
+ return ExpiredLoans->getState(PP).Expired;
+}
+
std::optional<OriginID>
LifetimeSafetyAnalysis::getOriginIDForDecl(const ValueDecl *D) const {
assert(FactMgr && "FactManager not initialized");
diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
index af4d63a38211e..a48fcfd9865a8 100644
--- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
+++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
@@ -45,7 +45,10 @@ class LifetimeTestRunner {
return;
}
AnalysisCtx = std::make_unique<AnalysisDeclContext>(nullptr, FD);
- AnalysisCtx->getCFGBuildOptions().setAllAlwaysAdd();
+ CFG::BuildOptions &BuildOptions = AnalysisCtx->getCFGBuildOptions();
+ BuildOptions.setAllAlwaysAdd();
+ BuildOptions.AddImplicitDtors = true;
+ BuildOptions.AddTemporaryDtors = true;
// Run the main analysis.
Analysis = std::make_unique<LifetimeSafetyAnalysis>(*AnalysisCtx);
@@ -115,6 +118,13 @@ class LifetimeTestHelper {
return Analysis.getLoansAtPoint(OID, PP);
}
+ std::optional<LoanSet> getExpiredLoansAtPoint(llvm::StringRef Annotation) {
+ ProgramPoint PP = Runner.getProgramPoint(Annotation);
+ if (!PP)
+ return std::nullopt;
+ return Analysis.getExpiredLoansAtPoint(PP);
+ }
+
private:
template <typename DeclT> DeclT *findDecl(llvm::StringRef Name) {
auto &Ctx = Runner.getASTContext();
@@ -134,6 +144,15 @@ class LifetimeTestHelper {
// GTest Matchers & Fixture
// ========================================================================= //
+// A helper class to represent a set of loans, identified by variable names.
+class LoanSetInfo {
+public:
+ LoanSetInfo(const std::vector<std::string> &Vars, LifetimeTestHelper &H)
+ : LoanVars(Vars), Helper(H) {}
+ std::vector<std::string> LoanVars;
+ LifetimeTestHelper &Helper;
+};
+
// It holds the name of the origin variable and a reference to the helper.
class OriginInfo {
public:
@@ -185,6 +204,34 @@ MATCHER_P2(HasLoansToImpl, LoanVars, Annotation, "") {
ActualLoans, result_listener);
}
+/// Matcher to verify that the complete set of expired loans at a program point
+/// matches the expected loan set.
+MATCHER_P(AreExpiredAt, Annotation, "") {
+ const LoanSetInfo &Info = arg;
+ auto &Helper = Info.Helper;
+
+ auto ActualExpiredSetOpt = Helper.getExpiredLoansAtPoint(Annotation);
+ if (!ActualExpiredSetOpt) {
+ *result_listener << "could not get a valid expired loan set at point '"
+ << Annotation << "'";
+ return false;
+ }
+ std::vector<LoanID> ActualExpiredLoans(ActualExpiredSetOpt->begin(),
+ ActualExpiredSetOpt->end());
+ std::vector<LoanID> ExpectedExpiredLoans;
+ for (const auto &VarName : Info.LoanVars) {
+ auto LoanIDOpt = Helper.getLoanForVar(VarName);
+ if (!LoanIDOpt) {
+ *result_listener << "could not find a loan for variable '" << VarName
+ << "'";
+ return false;
+ }
+ ExpectedExpiredLoans.push_back(*LoanIDOpt);
+ }
+ return ExplainMatchResult(UnorderedElementsAreArray(ExpectedExpiredLoans),
+ ActualExpiredLoans, result_listener);
+}
+
// Base test fixture to manage the runner and helper.
class LifetimeAnalysisTest : public ::testing::Test {
protected:
@@ -197,6 +244,14 @@ class LifetimeAnalysisTest : public ::testing::Test {
return OriginInfo(OriginVar, *Helper);
}
+ /// Factory function that hides the std::vector creation.
+ LoanSetInfo LoansTo(std::initializer_list<std::string> LoanVars) {
+ return LoanSetInfo({LoanVars}, *Helper);
+ }
+
+ /// A convenience helper for asserting that no loans are expired.
+ LoanSetInfo NoLoans() { return LoansTo({}); }
+
// Factory function that hides the std::vector creation.
auto HasLoansTo(std::initializer_list<std::string> LoanVars,
const char *Annotation) {
@@ -292,7 +347,6 @@ TEST_F(LifetimeAnalysisTest, ReassignToNull) {
}
)");
EXPECT_THAT(Origin("p"), HasLoansTo({"s1"}, "before_null"));
- // After assigning to null, the origin for `p` should have no loans.
EXPECT_THAT(Origin("p"), HasLoansTo({}, "after_null"));
}
@@ -347,15 +401,22 @@ TEST_F(LifetimeAnalysisTest, LoanInLoop) {
void target(bool condition) {
MyObj* p = nullptr;
while (condition) {
+ POINT(start_loop);
MyObj inner;
p = &inner;
- POINT(in_loop);
+ POINT(end_loop);
}
POINT(after_loop);
}
)");
- EXPECT_THAT(Origin("p"), HasLoansTo({"inner"}, "in_loop"));
+ EXPECT_THAT(Origin("p"), HasLoansTo({"inner"}, "start_loop"));
+ EXPECT_THAT(LoansTo({"inner"}), AreExpiredAt("start_loop"));
+
+ EXPECT_THAT(Origin("p"), HasLoansTo({"inner"}, "end_loop"));
+ EXPECT_THAT(NoLoans(), AreExpiredAt("end_loop"));
+
EXPECT_THAT(Origin("p"), HasLoansTo({"inner"}, "after_loop"));
+ EXPECT_THAT(LoansTo({"inner"}), AreExpiredAt("after_loop"));
}
TEST_F(LifetimeAnalysisTest, LoopWithBreak) {
@@ -413,6 +474,44 @@ TEST_F(LifetimeAnalysisTest, PointersInACycle) {
EXPECT_THAT(Origin("temp"), HasLoansTo({"v1", "v2", "v3"}, "after_loop"));
}
+TEST_F(LifetimeAnalysisTest, PointersAndExpirationInACycle) {
+ SetupTest(R"(
+ void target(bool condition) {
+ MyObj v1, v2;
+ MyObj *p1 = &v1, *p2 = &v2;
+
+ POINT(before_while);
+ while (condition) {
+ POINT(in_loop_before_temp);
+ MyObj temp;
+ p1 = &temp;
+ POINT(in_loop_after_temp);
+
+ MyObj* q = p1;
+ p1 = p2;
+ p2 = q;
+ }
+ POINT(after_loop);
+ }
+ )");
+ EXPECT_THAT(Origin("p1"), HasLoansTo({"v1"}, "before_while"));
+ EXPECT_THAT(Origin("p2"), HasLoansTo({"v2"}, "before_while"));
+ EXPECT_THAT(NoLoans(), AreExpiredAt("before_while"));
+
+ EXPECT_THAT(Origin("p1"),
+ HasLoansTo({"v1", "v2", "temp"}, "in_loop_before_temp"));
+ EXPECT_THAT(Origin("p2"), HasLoansTo({"v2", "temp"}, "in_loop_before_temp"));
+ EXPECT_THAT(LoansTo({"temp"}), AreExpiredAt("in_loop_before_temp"));
+
+ EXPECT_THAT(Origin("p1"), HasLoansTo({"temp"}, "in_loop_after_temp"));
+ EXPECT_THAT(Origin("p2"), HasLoansTo({"v2", "temp"}, "in_loop_after_temp"));
+ EXPECT_THAT(NoLoans(), AreExpiredAt("in_loop_after_temp"));
+
+ EXPECT_THAT(Origin("p1"), HasLoansTo({"v1", "v2", "temp"}, "after_loop"));
+ EXPECT_THAT(Origin("p2"), HasLoansTo({"v2", "temp"}, "after_loop"));
+ EXPECT_THAT(LoansTo({"temp"}), AreExpiredAt("after_loop"));
+}
+
TEST_F(LifetimeAnalysisTest, NestedScopes) {
SetupTest(R"(
void target() {
@@ -435,5 +534,177 @@ TEST_F(LifetimeAnalysisTest, NestedScopes) {
EXPECT_THAT(Origin("p"), HasLoansTo({"inner"}, "after_inner_scope"));
}
+TEST_F(LifetimeAnalysisTest, SimpleExpiry) {
+ SetupTest(R"(
+ void target() {
+ MyObj* p = nullptr;
+ {
+ MyObj s;
+ p = &s;
+ POINT(before_expiry);
+ } // s goes out of scope here
+ POINT(after_expiry);
+ }
+ )");
+ EXPECT_THAT(NoLoans(), AreExpiredAt("before_expiry"));
+ EXPECT_THAT(LoansTo({"s"}), AreExpiredAt("after_expiry"));
+}
+
+TEST_F(LifetimeAnalysisTest, NestedExpiry) {
+ SetupTest(R"(
+ void target() {
+ MyObj s1;
+ MyObj* p = &s1;
+ POINT(before_inner);
+ {
+ MyObj s2;
+ p = &s2;
+ POINT(in_inner);
+ } // s2 expires
+ POINT(after_inner);
+ }
+ )");
+ EXPECT_THAT(NoLoans(), AreExpiredAt("before_inner"));
+ EXPECT_THAT(NoLoans(), AreExpiredAt("in_inner"));
+ EXPECT_THAT(LoansTo({"s2"}), AreExpiredAt("after_inner"));
+}
+
+TEST_F(LifetimeAnalysisTest, ConditionalExpiry) {
+ SetupTest(R"(
+ void target(bool cond) {
+ MyObj s1;
+ MyObj* p = &s1;
+ POINT(before_if);
+ if (cond) {
+ MyObj s2;
+ p = &s2;
+ POINT(then_block);
+ } // s2 expires here
+ POINT(after_if);
+ }
+ )");
+ EXPECT_THAT(NoLoans(), AreExpiredAt("before_if"));
+ EXPECT_THAT(NoLoans(), AreExpiredAt("then_block"));
+ EXPECT_THAT(LoansTo({"s2"}), AreExpiredAt("after_if"));
+}
+
+TEST_F(LifetimeAnalysisTest, LoopExpiry) {
+ SetupTest(R"(
+ void target() {
+ MyObj *p = nullptr;
+ for (int i = 0; i < 2; ++i) {
+ POINT(start_loop);
+ MyObj s;
+ p = &s;
+ POINT(end_loop);
+ } // s expires here on each iteration
+ POINT(after_loop);
+ }
+ )");
+ EXPECT_THAT(LoansTo({"s"}), AreExpiredAt("start_loop"));
+ EXPECT_THAT(NoLoans(), AreExpiredAt("end_loop"));
+ EXPECT_THAT(LoansTo({"s"}), AreExpiredAt("after_loop"));
+}
+
+TEST_F(LifetimeAnalysisTest, MultipleExpiredLoans) {
+ SetupTest(R"(
+ void target() {
+ MyObj *p1, *p2, *p3;
+ {
+ MyObj s1;
+ p1 = &s1;
+ POINT(p1);
+ } // s1 expires
+ POINT(p2);
+ {
+ MyObj s2;
+ p2 = &s2;
+ MyObj s3;
+ p3 = &s3;
+ POINT(p3);
+ } // s2, s3 expire
+ POINT(p4);
+ }
+ )");
+ EXPECT_THAT(NoLoans(), AreExpiredAt("p1"));
+ EXPECT_THAT(LoansTo({"s1"}), AreExpiredAt("p2"));
+ EXPECT_THAT(LoansTo({"s1"}), AreExpiredAt("p3"));
+ EXPECT_THAT(LoansTo({"s1", "s2", "s3"}), AreExpiredAt("p4"));
+}
+
+TEST_F(LifetimeAnalysisTest, GotoJumpsOutOfScope) {
+ SetupTest(R"(
+ void target(bool cond) {
+ MyObj *p = nullptr;
+ {
+ MyObj s;
+ p = &s;
+ POINT(before_goto);
+ if (cond) {
+ goto end;
+ }
+ } // `s` expires here on the path that doesn't jump
+ POINT(after_scope);
+ end:
+ POINT(after_goto);
+ }
+ )");
+ EXPECT_THAT(NoLoans(), AreExpiredAt("before_goto"));
+ EXPECT_THAT(LoansTo({"s"}), AreExpiredAt("after_scope"));
+ EXPECT_THAT(LoansTo({"s"}), AreExpiredAt("after_goto"));
+}
+
+TEST_F(LifetimeAnalysisTest, ContinueInLoop) {
+ SetupTest(R"(
+ void target(int count) {
+ MyObj *p = nullptr;
+ MyObj outer;
+ p = &outer;
+ POINT(before_loop);
+
+ for (int i = 0; i < count; ++i) {
+ if (i % 2 == 0) {
+ MyObj s_even;
+ p = &s_even;
+ POINT(in_even_iter);
+ continue;
+ }
+ MyObj s_odd;
+ p = &s_odd;
+ POINT(in_odd_iter);
+ }
+ POINT(after_loop);
+ }
+ )");
+ EXPECT_THAT(NoLoans(), AreExpiredAt("before_loop"));
+ EXPECT_THAT(LoansTo({"s_odd"}), AreExpiredAt("in_even_iter"));
+ EXPECT_THAT(LoansTo({"s_even"}), AreExpiredAt("in_odd_iter"));
+ EXPECT_THAT(LoansTo({"s_even", "s_odd"}), AreExpiredAt("after_loop"));
+}
+
+TEST_F(LifetimeAnalysisTest, ReassignedPointerThenOriginalExpires) {
+ SetupTest(R"(
+ void target() {
+ MyObj* p = nullptr;
+ {
+ MyObj s1;
+ p = &s1;
+ POINT(p_has_s1);
+ {
+ MyObj s2;
+ p = &s2;
+ POINT(p_has_s2);
+ }
+ POINT(p_after_s2_expires);
+ } // s1 expires here.
+ POINT(p_after_s1_expires);
+ }
+ )");
+ EXPECT_THAT(NoLoans(), AreExpiredAt("p_has_s1"));
+ EXPECT_THAT(NoLoans(), AreExpiredAt("p_has_s2"));
+ EXPECT_THAT(LoansTo({"s2"}), AreExpiredAt("p_after_s2_expires"));
+ EXPECT_THAT(LoansTo({"s1", "s2"}), AreExpiredAt("p_after_s1_expires"));
+}
+
} // anonymous namespace
} // namespace clang::lifetimes::internal
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
