https://github.com/usx95 updated
https://github.com/llvm/llvm-project/pull/148976
>From e1327406119cc0887f473ebd93a02d6eb383b234 Mon Sep 17 00:00:00 2001
From: Utkarsh Saxena <u...@google.com>
Date: Tue, 15 Jul 2025 22:19:48 +0000
Subject: [PATCH] add-liveness-finally
---
.../clang/Analysis/Analyses/LifetimeSafety.h | 5 +
clang/lib/Analysis/LifetimeSafety.cpp | 83 +++++++++++
.../unittests/Analysis/LifetimeSafetyTest.cpp | 136 ++++++++++++++++++
3 files changed, 224 insertions(+)
diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
index 1c00558d32f63..1b7cb82fbe891 100644
--- a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
+++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
@@ -34,6 +34,7 @@ class Fact;
class FactManager;
class LoanPropagationAnalysis;
class ExpiredLoansAnalysis;
+class LiveOriginAnalysis;
struct LifetimeFactory;
/// A generic, type-safe wrapper for an ID, distinguished by its `Tag` type.
@@ -97,6 +98,9 @@ class LifetimeSafetyAnalysis {
/// their Path.
std::vector<LoanID> getLoanIDForVar(const VarDecl *VD) const;
+ /// Returns the set of live origins at a specific program point.
+ OriginSet getLiveOriginsAtPoint(ProgramPoint PP) const;
+
/// Retrieves program points that were specially marked in the source code
/// for testing.
///
@@ -114,6 +118,7 @@ class LifetimeSafetyAnalysis {
std::unique_ptr<FactManager> FactMgr;
std::unique_ptr<LoanPropagationAnalysis> LoanPropagation;
std::unique_ptr<ExpiredLoansAnalysis> ExpiredLoans;
+ std::unique_ptr<LiveOriginAnalysis> LiveOrigins;
};
} // namespace internal
} // namespace clang::lifetimes
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp
b/clang/lib/Analysis/LifetimeSafety.cpp
index 815a36e13412c..a717681c4ea44 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -727,12 +727,14 @@ join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V>
B,
// ========================================================================= //
using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>;
+using OriginSet = llvm::ImmutableSet<OriginID>;
/// An object to hold the factories for immutable collections, ensuring
/// that all created states share the same underlying memory management.
struct LifetimeFactory {
OriginLoanMap::Factory OriginMapFactory;
LoanSet::Factory LoanSetFactory;
+ OriginSet::Factory OriginSetFactory;
/// Creates a singleton set containing only the given loan ID.
LoanSet createLoanSet(LoanID LID) {
@@ -833,6 +835,78 @@ class LoanPropagationAnalysis
}
};
+// ========================================================================= //
+// Live Origins Analysis
+// ========================================================================= //
+
+/// The dataflow lattice for origin liveness analysis.
+/// It tracks the set of origins that are live at a given program point.
+struct LivenessLattice {
+ OriginSet LiveOrigins;
+
+ LivenessLattice() : LiveOrigins(nullptr) {};
+ explicit LivenessLattice(OriginSet S) : LiveOrigins(S) {}
+
+ bool operator==(const LivenessLattice &Other) const {
+ return LiveOrigins == Other.LiveOrigins;
+ }
+ bool operator!=(const LivenessLattice &Other) const {
+ return !(*this == Other);
+ }
+
+ void dump(llvm::raw_ostream &OS) const {
+ OS << "LivenessLattice State:\n";
+ if (LiveOrigins.isEmpty())
+ OS << " <empty>\n";
+ for (const OriginID &OID : LiveOrigins)
+ OS << " Origin " << OID << " is live\n";
+ }
+};
+
+/// The analysis that tracks which origins are live. This is a backward
+/// analysis.
+class LiveOriginAnalysis
+ : public DataflowAnalysis<LiveOriginAnalysis, LivenessLattice,
+ Direction::Backward> {
+
+ OriginSet::Factory &SetFactory;
+
+public:
+ LiveOriginAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
+ OriginSet::Factory &SF)
+ : DataflowAnalysis(C, AC, F), SetFactory(SF) {}
+
+ using DataflowAnalysis<LiveOriginAnalysis, Lattice,
+ Direction::Backward>::transfer;
+
+ StringRef getAnalysisName() const { return "LiveOrigins"; }
+
+ Lattice getInitialState() { return Lattice(SetFactory.getEmptySet()); }
+
+ /// Merges two lattices by taking the union of the live origin sets.
+ Lattice join(Lattice L1, Lattice L2) const {
+ return Lattice(utils::join(L1.LiveOrigins, L2.LiveOrigins, SetFactory));
+ }
+
+ /// An assignment `p = q` kills the liveness of `p` and generates liveness
+ /// for `q`.
+ Lattice transfer(Lattice In, const AssignOriginFact &F) {
+ OriginSet S = SetFactory.remove(In.LiveOrigins, F.getDestOriginID());
+ S = SetFactory.add(S, F.getSrcOriginID());
+ return Lattice(S);
+ }
+
+ /// Issuing a new loan to an origin kills its liveness.
+ Lattice transfer(Lattice In, const IssueFact &F) {
+ return Lattice(SetFactory.remove(In.LiveOrigins, F.getOriginID()));
+ }
+
+ /// A return statement generates liveness for the returned origin.
+ Lattice transfer(Lattice In, const ReturnOfOriginFact &F) {
+ return Lattice(SetFactory.add(In.LiveOrigins, F.getReturnedOriginID()));
+ }
+};
+
// ========================================================================= //
// Expired Loans Analysis
// ========================================================================= //
@@ -937,6 +1011,10 @@ void LifetimeSafetyAnalysis::run() {
ExpiredLoans =
std::make_unique<ExpiredLoansAnalysis>(Cfg, AC, *FactMgr, *Factory);
ExpiredLoans->run();
+
+ LiveOrigins = std::make_unique<LiveOriginAnalysis>(Cfg, AC, *FactMgr,
+
Factory->OriginSetFactory);
+ LiveOrigins->run();
}
LoanSet LifetimeSafetyAnalysis::getLoansAtPoint(OriginID OID,
@@ -969,6 +1047,11 @@ LifetimeSafetyAnalysis::getLoanIDForVar(const VarDecl
*VD) const {
return Result;
}
+OriginSet LifetimeSafetyAnalysis::getLiveOriginsAtPoint(ProgramPoint PP) const
{
+ assert(LiveOrigins && "LiveOriginAnalysis has not been run.");
+ return LiveOrigins->getState(PP).LiveOrigins;
+}
+
llvm::StringMap<ProgramPoint> LifetimeSafetyAnalysis::getTestPoints() const {
assert(FactMgr && "FactManager not initialized");
llvm::StringMap<ProgramPoint> AnnotationToPointMap;
diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
index a48fcfd9865a8..7f2cf0eec654f 100644
--- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
+++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
@@ -125,6 +125,13 @@ class LifetimeTestHelper {
return Analysis.getExpiredLoansAtPoint(PP);
}
+ std::optional<OriginSet> getLiveOriginsAtPoint(llvm::StringRef Annotation) {
+ ProgramPoint PP = Runner.getProgramPoint(Annotation);
+ if (!PP)
+ return std::nullopt;
+ return Analysis.getLiveOriginsAtPoint(PP);
+ }
+
private:
template <typename DeclT> DeclT *findDecl(llvm::StringRef Name) {
auto &Ctx = Runner.getASTContext();
@@ -162,6 +169,15 @@ class OriginInfo {
LifetimeTestHelper &Helper;
};
+// A helper class to represent a set of origins, identified by variable names.
+class OriginsInfo {
+public:
+ OriginsInfo(const std::vector<std::string> &Vars, LifetimeTestHelper &H)
+ : OriginVars(Vars), Helper(H) {}
+ std::vector<std::string> OriginVars;
+ LifetimeTestHelper &Helper;
+};
+
/// Matcher to verify the set of loans held by an origin at a specific
/// program point.
///
@@ -232,6 +248,34 @@ MATCHER_P(AreExpiredAt, Annotation, "") {
ActualExpiredLoans, result_listener);
}
+/// Matcher to verify the complete set of live origins at a program point.
+MATCHER_P(AreLiveAt, Annotation, "") {
+ const OriginsInfo &Info = arg;
+ auto &Helper = Info.Helper;
+
+ auto ActualLiveSetOpt = Helper.getLiveOriginsAtPoint(Annotation);
+ if (!ActualLiveSetOpt) {
+ *result_listener << "could not get a valid live origin set at point '"
+ << Annotation << "'";
+ return false;
+ }
+ std::vector<OriginID> ActualLiveOrigins(ActualLiveSetOpt->begin(),
+ ActualLiveSetOpt->end());
+
+ std::vector<OriginID> ExpectedLiveOrigins;
+ for (const auto &VarName : Info.OriginVars) {
+ auto OriginIDOpt = Helper.getOriginForDecl(VarName);
+ if (!OriginIDOpt) {
+ *result_listener << "could not find an origin for variable '" << VarName
+ << "'";
+ return false;
+ }
+ ExpectedLiveOrigins.push_back(*OriginIDOpt);
+ }
+ return ExplainMatchResult(UnorderedElementsAreArray(ExpectedLiveOrigins),
+ ActualLiveOrigins, result_listener);
+}
+
// Base test fixture to manage the runner and helper.
class LifetimeAnalysisTest : public ::testing::Test {
protected:
@@ -244,6 +288,13 @@ class LifetimeAnalysisTest : public ::testing::Test {
return OriginInfo(OriginVar, *Helper);
}
+ /// Factory function that hides the std::vector creation.
+ OriginsInfo Origins(std::initializer_list<std::string> OriginVars) {
+ return OriginsInfo({OriginVars}, *Helper);
+ }
+
+ OriginsInfo NoOrigins() { return Origins({}); }
+
/// Factory function that hides the std::vector creation.
LoanSetInfo LoansTo(std::initializer_list<std::string> LoanVars) {
return LoanSetInfo({LoanVars}, *Helper);
@@ -706,5 +757,90 @@ TEST_F(LifetimeAnalysisTest,
ReassignedPointerThenOriginalExpires) {
EXPECT_THAT(LoansTo({"s1", "s2"}), AreExpiredAt("p_after_s1_expires"));
}
+TEST_F(LifetimeAnalysisTest, LivenessDeadPointer) {
+ SetupTest(R"(
+ void target() {
+ POINT(p2);
+ MyObj s;
+ MyObj* p = &s;
+ POINT(p1);
+ }
+ )");
+ EXPECT_THAT(NoOrigins(), AreLiveAt("p1"));
+ EXPECT_THAT(NoOrigins(), AreLiveAt("p2"));
+}
+
+TEST_F(LifetimeAnalysisTest, LivenessSimpleReturn) {
+ SetupTest(R"(
+ MyObj* target() {
+ MyObj s;
+ MyObj* p = &s;
+ POINT(p1);
+ return p;
+ }
+ )");
+ EXPECT_THAT(Origins({"p"}), AreLiveAt("p1"));
+}
+
+TEST_F(LifetimeAnalysisTest, LivenessKilledByReassignment) {
+ SetupTest(R"(
+ MyObj* target() {
+ MyObj s1, s2;
+ MyObj* p = &s1;
+ POINT(p1);
+ p = &s2;
+ POINT(p2);
+ return p;
+ }
+ )");
+ EXPECT_THAT(Origins({"p"}), AreLiveAt("p2"));
+ EXPECT_THAT(NoOrigins(), AreLiveAt("p1"));
+}
+
+TEST_F(LifetimeAnalysisTest, LivenessAcrossBranches) {
+ SetupTest(R"(
+ MyObj* target(bool c) {
+ MyObj x, y;
+ MyObj* p = nullptr;
+ POINT(p1);
+ if (c) {
+ p = &x;
+ POINT(p2);
+ } else {
+ p = &y;
+ POINT(p3);
+ }
+ return p;
+ }
+ )");
+ EXPECT_THAT(Origins({"p"}), AreLiveAt("p2"));
+ EXPECT_THAT(Origins({"p"}), AreLiveAt("p3"));
+ // Before the `if`, the value of `p` (`nullptr`) is always overwritten before
+ EXPECT_THAT(NoOrigins(), AreLiveAt("p1"));
+}
+
+TEST_F(LifetimeAnalysisTest, LivenessInLoop) {
+ SetupTest(R"(
+ MyObj* target(bool c) {
+ MyObj s1, s2;
+ MyObj* p = &s1;
+ MyObj* q = &s2;
+ POINT(p1);
+ while(c) {
+ POINT(p2);
+ p = q;
+ POINT(p3);
+ }
+ POINT(p4);
+ return p;
+ }
+ )");
+
+ EXPECT_THAT(Origins({"p"}), AreLiveAt("p4"));
+ EXPECT_THAT(Origins({"p", "q"}), AreLiveAt("p3"));
+ EXPECT_THAT(Origins({"q"}), AreLiveAt("p2"));
+ EXPECT_THAT(Origins({"p", "q"}), AreLiveAt("p1"));
+}
+
} // 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
