https://github.com/usx95 created https://github.com/llvm/llvm-project/pull/159991
None >From 23c0690fc4ed7b41885ed359f7974fb589fb3508 Mon Sep 17 00:00:00 2001 From: Utkarsh Saxena <[email protected]> Date: Sun, 21 Sep 2025 16:30:28 +0000 Subject: [PATCH] liveness-based-lifetime-policy --- .../clang/Analysis/Analyses/LifetimeSafety.h | 6 + clang/lib/Analysis/LifetimeSafety.cpp | 217 +++++++++++++----- .../unittests/Analysis/LifetimeSafetyTest.cpp | 135 +++++++++++ 3 files changed, 295 insertions(+), 63 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h index 512cb76cd6349..1eeac34cce456 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h @@ -55,6 +55,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. @@ -89,6 +90,7 @@ inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, OriginID ID) { // TODO(opt): Consider using a bitset to represent the set of loans. using LoanSet = llvm::ImmutableSet<LoanID>; using OriginSet = llvm::ImmutableSet<OriginID>; +using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>; /// A `ProgramPoint` identifies a location in the CFG by pointing to a specific /// `Fact`. identified by a lifetime-related event (`Fact`). @@ -113,6 +115,9 @@ class LifetimeSafetyAnalysis { /// Returns the set of loans that have expired at a specific program point. std::vector<LoanID> getExpiredLoansAtPoint(ProgramPoint PP) const; + /// TODO:Document. + std::vector<OriginID> getLiveOriginsAtPoint(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; @@ -139,6 +144,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 f63e95189e8f3..084cd8b4ddec0 100644 --- a/clang/lib/Analysis/LifetimeSafety.cpp +++ b/clang/lib/Analysis/LifetimeSafety.cpp @@ -1048,7 +1048,6 @@ join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B, // Loan Propagation Analysis // ========================================================================= // -using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>; using ExpiredLoanMap = llvm::ImmutableMap<LoanID, const ExpireFact *>; /// An object to hold the factories for immutable collections, ensuring @@ -1057,6 +1056,7 @@ struct LifetimeFactory { OriginLoanMap::Factory OriginMapFactory; LoanSet::Factory LoanSetFactory; ExpiredLoanMap::Factory ExpiredLoanMapFactory; + OriginSet::Factory OriginSetFactory; }; /// Represents the dataflow lattice for loan propagation. @@ -1261,6 +1261,74 @@ class ExpiredLoansAnalysis ExpiredLoanMap getExpiredLoans(ProgramPoint P) { return getState(P).Expired; } }; +// ========================================================================= // +// 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> { + FactManager &FactMgr; + OriginSet::Factory &Factory; + +public: + LiveOriginAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F, + OriginSet::Factory &SF) + : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF) {} + using DataflowAnalysis<LiveOriginAnalysis, Lattice, + Direction::Backward>::transfer; + + StringRef getAnalysisName() const { return "LiveOrigins"; } + + Lattice getInitialState() { return Lattice(Factory.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, Factory)); + } + + /// TODO:Document. + Lattice transfer(Lattice In, const UseFact &F) { + if (F.isWritten()) + return Lattice(Factory.remove(In.LiveOrigins, + F.getUsedOrigin(FactMgr.getOriginMgr()))); + return Lattice( + Factory.add(In.LiveOrigins, F.getUsedOrigin(FactMgr.getOriginMgr()))); + } + + /// Issuing a new loan to an origin kills its liveness. + Lattice transfer(Lattice In, const IssueFact &F) { + return Lattice(Factory.remove(In.LiveOrigins, F.getOriginID())); + } + + Lattice transfer(Lattice In, const KillOriginFact &F) { + return Lattice(Factory.remove(In.LiveOrigins, F.getOriginID())); + } + + OriginSet getLiveOrigins(ProgramPoint P) { return getState(P).LiveOrigins; } +}; + // ========================================================================= // // Lifetime checker and Error reporter // ========================================================================= // @@ -1276,85 +1344,99 @@ class LifetimeChecker { private: llvm::DenseMap<LoanID, PendingWarning> FinalWarningsMap; LoanPropagationAnalysis &LoanPropagation; - ExpiredLoansAnalysis &ExpiredLoans; + LiveOriginAnalysis &LiveOrigins; FactManager &FactMgr; AnalysisDeclContext &ADC; LifetimeSafetyReporter *Reporter; public: - LifetimeChecker(LoanPropagationAnalysis &LPA, ExpiredLoansAnalysis &ELA, + LifetimeChecker(LoanPropagationAnalysis &LPA, LiveOriginAnalysis &LOA, FactManager &FM, AnalysisDeclContext &ADC, LifetimeSafetyReporter *Reporter) - : LoanPropagation(LPA), ExpiredLoans(ELA), FactMgr(FM), ADC(ADC), + : LoanPropagation(LPA), LiveOrigins(LOA), FactMgr(FM), ADC(ADC), Reporter(Reporter) {} void run() { llvm::TimeTraceScope TimeProfile("LifetimeChecker"); + // for (const CFGBlock *B : *ADC.getAnalysis<PostOrderCFGView>()) + // for (const Fact *F : FactMgr.getFacts(B)) + // if (const auto *UF = F->getAs<ExpireFact>()) + // checkUse(UF); for (const CFGBlock *B : *ADC.getAnalysis<PostOrderCFGView>()) for (const Fact *F : FactMgr.getFacts(B)) - if (const auto *UF = F->getAs<UseFact>()) - checkUse(UF); + if (const auto *EF = F->getAs<ExpireFact>()) + checkExpiry(EF); issuePendingWarnings(); } + void checkExpiry(const ExpireFact *EF) { + LoanID ExpiredLoan = EF->getLoanID(); + OriginSet Origins = LiveOrigins.getLiveOrigins(EF); + for (OriginID OID : Origins) { + LoanSet HeldLoans = LoanPropagation.getLoans(OID, EF); + if (HeldLoans.contains(ExpiredLoan)) { + } + } + } + /// Checks for use-after-free errors for a given use of an Origin. /// /// This method is called for each 'UseFact' identified in the control flow /// graph. It determines if the loans held by the used origin have expired /// at the point of use. - void checkUse(const UseFact *UF) { - if (UF->isWritten()) - return; - OriginID O = UF->getUsedOrigin(FactMgr.getOriginMgr()); - - // Get the set of loans that the origin might hold at this program point. - LoanSet HeldLoans = LoanPropagation.getLoans(O, UF); - - // Get the set of all loans that have expired at this program point. - ExpiredLoanMap AllExpiredLoans = ExpiredLoans.getExpiredLoans(UF); - - // If the pointer holds no loans or no loans have expired, there's nothing - // to check. - if (HeldLoans.isEmpty() || AllExpiredLoans.isEmpty()) - return; - - // Identify loans that which have expired but are held by the pointer. Using - // them is a use-after-free. - llvm::SmallVector<LoanID> DefaultedLoans; - // A definite UaF error occurs if all loans the origin might hold have - // expired. - bool IsDefiniteError = true; - for (LoanID L : HeldLoans) { - if (AllExpiredLoans.contains(L)) - DefaultedLoans.push_back(L); - else - // If at least one loan is not expired, this use is not a definite UaF. - IsDefiniteError = false; - } - // If there are no defaulted loans, the use is safe. - if (DefaultedLoans.empty()) - return; - - // Determine the confidence level of the error (definite or maybe). - Confidence CurrentConfidence = - IsDefiniteError ? Confidence::Definite : Confidence::Maybe; - - // For each expired loan, create a pending warning. - for (LoanID DefaultedLoan : DefaultedLoans) { - // If we already have a warning for this loan with a higher or equal - // confidence, skip this one. - if (FinalWarningsMap.count(DefaultedLoan) && - CurrentConfidence <= FinalWarningsMap[DefaultedLoan].ConfidenceLevel) - continue; - - auto *EF = AllExpiredLoans.lookup(DefaultedLoan); - assert(EF && "Could not find ExpireFact for an expired loan."); - - FinalWarningsMap[DefaultedLoan] = {/*ExpiryLoc=*/(*EF)->getExpiryLoc(), - /*UseExpr=*/UF->getUseExpr(), - /*ConfidenceLevel=*/CurrentConfidence}; - } - } + // void checkUse(const UseFact *UF) { + // if (UF->isWritten()) + // return; + // OriginID O = UF->getUsedOrigin(FactMgr.getOriginMgr()); + + // // Get the set of loans that the origin might hold at this program point. + // LoanSet HeldLoans = LoanPropagation.getLoans(O, UF); + + // // Get the set of all loans that have expired at this program point. + // ExpiredLoanMap AllExpiredLoans = ExpiredLoans.getExpiredLoans(UF); + + // // If the pointer holds no loans or no loans have expired, there's nothing + // // to check. + // if (HeldLoans.isEmpty() || AllExpiredLoans.isEmpty()) + // return; + + // // Identify loans that which have expired but are held by the pointer. Using + // // them is a use-after-free. + // llvm::SmallVector<LoanID> DefaultedLoans; + // // A definite UaF error occurs if all loans the origin might hold have + // // expired. + // bool IsDefiniteError = true; + // for (LoanID L : HeldLoans) { + // if (AllExpiredLoans.contains(L)) + // DefaultedLoans.push_back(L); + // else + // // If at least one loan is not expired, this use is not a definite UaF. + // IsDefiniteError = false; + // } + // // If there are no defaulted loans, the use is safe. + // if (DefaultedLoans.empty()) + // return; + + // // Determine the confidence level of the error (definite or maybe). + // Confidence CurrentConfidence = + // IsDefiniteError ? Confidence::Definite : Confidence::Maybe; + + // // For each expired loan, create a pending warning. + // for (LoanID DefaultedLoan : DefaultedLoans) { + // // If we already have a warning for this loan with a higher or equal + // // confidence, skip this one. + // if (FinalWarningsMap.count(DefaultedLoan) && + // CurrentConfidence <= FinalWarningsMap[DefaultedLoan].ConfidenceLevel) + // continue; + + // auto *EF = AllExpiredLoans.lookup(DefaultedLoan); + // assert(EF && "Could not find ExpireFact for an expired loan."); + + // FinalWarningsMap[DefaultedLoan] = {/*ExpiryLoc=*/(*EF)->getExpiryLoc(), + // /*UseExpr=*/UF->getUseExpr(), + // /*ConfidenceLevel=*/CurrentConfidence}; + // } + // } void issuePendingWarnings() { if (!Reporter) @@ -1406,11 +1488,11 @@ void LifetimeSafetyAnalysis::run() { std::make_unique<LoanPropagationAnalysis>(Cfg, AC, *FactMgr, *Factory); LoanPropagation->run(); - ExpiredLoans = - std::make_unique<ExpiredLoansAnalysis>(Cfg, AC, *FactMgr, *Factory); - ExpiredLoans->run(); + LiveOrigins = std::make_unique<LiveOriginAnalysis>(Cfg, AC, *FactMgr, + Factory->OriginSetFactory); + LiveOrigins->run(); - LifetimeChecker Checker(*LoanPropagation, *ExpiredLoans, *FactMgr, AC, + LifetimeChecker Checker(*LoanPropagation, *LiveOrigins, *FactMgr, AC, Reporter); Checker.run(); } @@ -1449,6 +1531,15 @@ LifetimeSafetyAnalysis::getLoanIDForVar(const VarDecl *VD) const { return Result; } +std::vector<OriginID> +LifetimeSafetyAnalysis::getLiveOriginsAtPoint(ProgramPoint PP) const { + assert(LiveOrigins && "LiveOriginAnalysis has not been run."); + std::vector<OriginID> Result; + for (const OriginID &OID : LiveOrigins->getLiveOrigins(PP)) + Result.push_back(OID); + return Result; +} + 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 3821015f07fb1..b227ddb288df8 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -134,6 +134,14 @@ class LifetimeTestHelper { return Analysis.getExpiredLoansAtPoint(PP); } + std::optional<std::vector<OriginID>> + 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(); @@ -180,6 +188,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. /// @@ -264,6 +281,31 @@ 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 = std::move(ActualLiveSetOpt.value()); + 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: @@ -276,6 +318,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); @@ -1174,5 +1223,91 @@ TEST_F(LifetimeAnalysisTest, LifetimeboundConversionOperator) { )"); EXPECT_THAT(Origin("v"), HasLoansTo({"owner"}, "p1")); } + +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 [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
