https://github.com/usx95 updated https://github.com/llvm/llvm-project/pull/207520
>From fd655f5e41e817fffb8668cc3c0a3f9d22c5e836 Mon Sep 17 00:00:00 2001 From: Utkarsh Saxena <[email protected]> Date: Sat, 4 Jul 2026 16:25:06 +0000 Subject: [PATCH] [LifetimeSafety] Support field-sensitivity in lifetime tracking This patch enables field-sensitivity when tracking lifetimes of nested objects. - FactsGenerator now generates `PathElement::getField` for `MemberExpr` accesses, mapping fields to loans. - LoanPropagation now propagates field paths along flow facts, appending fields to base loans. - Removes false-positive warnings in `invalidations.cpp` where modifications to one field were incorrectly reported as invalidating iterators/pointers to another field. - Adds comprehensive unit tests checking nested field access and placeholder fields. TAG=agy CONV=2cfd8d00-18d7-4a03-8d78-2aba2f9a8f23 --- .../Analysis/Analyses/LifetimeSafety/Facts.h | 13 ++- .../Analysis/Analyses/LifetimeSafety/Loans.h | 27 +++++ clang/lib/Analysis/LifetimeSafety/Facts.cpp | 4 + .../LifetimeSafety/FactsGenerator.cpp | 6 +- .../LifetimeSafety/LoanPropagation.cpp | 38 +++++- clang/lib/Analysis/LifetimeSafety/Loans.cpp | 30 +++++ .../Sema/LifetimeSafety/invalidations.cpp | 90 +++++++++++++-- .../unittests/Analysis/LifetimeSafetyTest.cpp | 109 ++++++++++++------ 8 files changed, 265 insertions(+), 52 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h index d2552c69b029f..e871ca704dc74 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Facts.h @@ -142,6 +142,13 @@ class OriginFlowFact : public Fact { /// True if the destination origin should be killed (i.e., its current loans /// cleared) before the source origin's loans are flowed into it. bool KillDest; + /// If set, the source origin's loans are extended by this path element before + /// flowing into the destination. + /// + /// Example: If source has loan to `x` and Element=field, then destination + /// receives loan to `x.field`. This is used for member expressions like + /// `p = obj.field;` where `p` gets a loan to `obj.field`. + std::optional<PathElement> AddToPath; public: @@ -149,13 +156,15 @@ class OriginFlowFact : public Fact { return F->getKind() == Kind::OriginFlow; } - OriginFlowFact(OriginID OIDDest, OriginID OIDSrc, bool KillDest) + OriginFlowFact(OriginID OIDDest, OriginID OIDSrc, bool KillDest, + std::optional<PathElement> AddToPath = std::nullopt) : Fact(Kind::OriginFlow), OIDDest(OIDDest), OIDSrc(OIDSrc), - KillDest(KillDest) {} + KillDest(KillDest), AddToPath(AddToPath) {} OriginID getDestOriginID() const { return OIDDest; } OriginID getSrcOriginID() const { return OIDSrc; } bool getKillDest() const { return KillDest; } + std::optional<PathElement> getPathElement() const { return AddToPath; } void dump(llvm::raw_ostream &OS, const LoanManager &, const OriginManager &OM, diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h index bf6b913efeccd..c1da7d57a55bf 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Loans.h @@ -211,6 +211,7 @@ class Loan { /// Manages the creation, storage and retrieval of loans. class LoanManager { + using ExtensionCacheKey = std::pair<LoanID, PathElement>; public: @@ -227,6 +228,15 @@ class LoanManager { const PlaceholderBase *getOrCreatePlaceholderBase(const ParmVarDecl *PVD); const PlaceholderBase *getOrCreatePlaceholderBase(const CXXMethodDecl *MD); + /// Gets or creates a loan by extending BaseLoanID with Element. + /// Caches the result to ensure convergence in LoanPropagation. + Loan *getOrCreateExtendedLoan(LoanID BaseLoanID, PathElement Element); + + /// Finds the base loan IDs that could have been extended to produce + /// ExtendedLoanID. + llvm::SmallVector<LoanID, 2> getBaseLoans(LoanID ExtendedLoanID, + PathElement Element) const; + const Loan *getLoan(LoanID ID) const { @@ -242,6 +252,11 @@ class LoanManager { LoanID NextLoanID{0}; llvm::FoldingSet<PlaceholderBase> PlaceholderBases; + /// Cache for extended loans. Maps (BaseLoanID, PathElement) to the extended + /// loan. Ensures that extending the same loan with the same path element + /// always returns the same loan object, which is necessary for dataflow + /// analysis convergence. + llvm::DenseMap<ExtensionCacheKey, Loan *> ExtensionCache; /// TODO(opt): Profile and evaluate the usefullness of small buffer @@ -251,5 +266,17 @@ class LoanManager { }; } // namespace clang::lifetimes::internal +namespace llvm { +template <> struct DenseMapInfo<clang::lifetimes::internal::PathElement> { + using PathElement = clang::lifetimes::internal::PathElement; + static unsigned getHashValue(const PathElement &Val) { + return llvm::hash_combine(Val.isInterior(), Val.getFieldDecl()); + } + static bool isEqual(const PathElement &LHS, const PathElement &RHS) { + return LHS == RHS; + } +}; +} // namespace llvm + #endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_LOANS_H diff --git a/clang/lib/Analysis/LifetimeSafety/Facts.cpp b/clang/lib/Analysis/LifetimeSafety/Facts.cpp index 15b666fbdf7ca..5dfc2c37f8852 100644 --- a/clang/lib/Analysis/LifetimeSafety/Facts.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Facts.cpp @@ -63,6 +63,10 @@ void OriginFlowFact::dump(llvm::raw_ostream &OS, const LoanManager &LM, OS << "\tSrc: "; OM.dump(getSrcOriginID(), OS); OS << (getKillDest() ? "" : ", Merge"); + if (auto Path = getPathElement()) { + OS << "\n\tAdd path: "; + Path->dump(OS); + } OS << "\n"; } diff --git a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp index f4203d0220da0..aae30bb220c27 100644 --- a/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp +++ b/clang/lib/Analysis/LifetimeSafety/FactsGenerator.cpp @@ -283,11 +283,11 @@ void FactsGenerator::VisitMemberExpr(const MemberExpr *ME) { assert(Dst && "Field member should have an origin list as it is GL value"); OriginList *Src = getOriginsList(*ME->getBase()); assert(Src && "Base expression should be a pointer/reference type"); - // The field's glvalue (outermost origin) holds the same loans as the base - // expression. + // Flow loans from base to field, extending each loan's path with the field. + // E.g., if base has loan to `obj`, field gets loan to `obj.field`. CurrentBlockFacts.push_back(FactMgr.createFact<OriginFlowFact>( Dst->getOuterOriginID(), Src->getOuterOriginID(), - /*Kill=*/true)); + /*Kill=*/true, PathElement::getField(FD))); } } diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index a67b1b3c0f826..762042d361a52 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -176,14 +176,28 @@ class AnalysisImpl /// A flow from source to destination. If `KillDest` is true, this replaces /// the destination's loans with the source's. Otherwise, the source's loans /// are merged into the destination's. + /// If OriginFlowFact has a PathElement, loans from source are extended + /// before propagating (e.g., loan to `x` becomes loan to `x.field`). Lattice transfer(Lattice In, const OriginFlowFact &F) { OriginID DestOID = F.getDestOriginID(); OriginID SrcOID = F.getSrcOriginID(); + LoanSet SrcLoans = getLoans(In, SrcOID); + LoanSet LoansToFlow = SrcLoans; + + // Extend loans if a path element is specified (e.g., for field access). + if (auto Element = F.getPathElement()) { + LoansToFlow = LoanSetFactory.getEmptySet(); + for (LoanID LID : SrcLoans) { + Loan *ExtendedLoan = + FactMgr.getLoanMgr().getOrCreateExtendedLoan(LID, *Element); + LoansToFlow = LoanSetFactory.add(LoansToFlow, ExtendedLoan->getID()); + } + } + LoanSet DestLoans = F.getKillDest() ? LoanSetFactory.getEmptySet() : getLoans(In, DestOID); - LoanSet SrcLoans = getLoans(In, SrcOID); - LoanSet MergedLoans = utils::join(DestLoans, SrcLoans, LoanSetFactory); + LoanSet MergedLoans = utils::join(DestLoans, LoansToFlow, LoanSetFactory); return setLoans(In, DestOID, MergedLoans); } @@ -208,6 +222,7 @@ class AnalysisImpl assert(getLoans(StartOID, StartPoint).contains(TargetLoan) && "TargetLoan must be present in the StartOID at the StartPoint"); + LoanID CurrLoanID = TargetLoan; OriginID CurrOID = StartOID; llvm::SmallVector<OriginID> OriginFlowChain; llvm::ArrayRef<const Fact *> Facts = FactMgr.getBlockContaining(StartPoint); @@ -217,7 +232,7 @@ class AnalysisImpl for (const Fact *F : llvm::reverse(llvm::make_range(Facts.begin(), StartIt))) { if (const auto *IF = F->getAs<IssueFact>()) - if (IF->getLoanID() == TargetLoan) { + if (IF->getLoanID() == CurrLoanID) { assert(IF->getOriginID() == CurrOID); return OriginFlowChain; } @@ -229,8 +244,23 @@ class AnalysisImpl continue; const OriginID SrcOriginID = OFF->getSrcOriginID(); - if (!getLoans(SrcOriginID, OFF).contains(TargetLoan)) + std::optional<LoanID> NextLoanID; + if (auto AddPath = OFF->getPathElement()) { + auto Candidates = + FactMgr.getLoanMgr().getBaseLoans(CurrLoanID, *AddPath); + for (LoanID Candidate : Candidates) { + if (getLoans(SrcOriginID, OFF).contains(Candidate)) { + NextLoanID = Candidate; + break; + } + } + } else { + if (getLoans(SrcOriginID, OFF).contains(CurrLoanID)) + NextLoanID = CurrLoanID; + } + if (!NextLoanID) continue; + CurrLoanID = *NextLoanID; OriginFlowChain.push_back(SrcOriginID); CurrOID = SrcOriginID; } diff --git a/clang/lib/Analysis/LifetimeSafety/Loans.cpp b/clang/lib/Analysis/LifetimeSafety/Loans.cpp index 826a66c49200c..9692b5ff33f48 100644 --- a/clang/lib/Analysis/LifetimeSafety/Loans.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Loans.cpp @@ -65,5 +65,35 @@ LoanManager::getOrCreatePlaceholderBase(const CXXMethodDecl *MD) { return NewPB; } +Loan *LoanManager::getOrCreateExtendedLoan(LoanID BaseLoanID, + PathElement Element) { + ExtensionCacheKey Key = {BaseLoanID, Element}; + auto It = ExtensionCache.find(Key); + if (It != ExtensionCache.end()) + return It->second; + const auto *BaseLoan = getLoan(BaseLoanID); + // TODO: Polish comment: Do not add interior access if the base loan path + // already contains that at the end. + if (Element.isInterior() && + !BaseLoan->getAccessPath().getElements().empty() && + BaseLoan->getAccessPath().getElements().back().isInterior()) + return ExtensionCache[Key] = const_cast<Loan *>(BaseLoan); + + AccessPath ExtendedPath(BaseLoan->getAccessPath(), Element); + return ExtensionCache[Key] = + createLoan(ExtendedPath, BaseLoan->getIssueExpr()); +} + +llvm::SmallVector<LoanID, 2> +LoanManager::getBaseLoans(LoanID ExtendedLoanID, PathElement Element) const { + llvm::SmallVector<LoanID, 2> Result; + for (const auto &Entry : ExtensionCache) { + if (Entry.second->getID() == ExtendedLoanID && + Entry.first.second == Element) { + Result.push_back(Entry.first.first); + } + } + return Result; +} } // namespace clang::lifetimes::internal diff --git a/clang/test/Sema/LifetimeSafety/invalidations.cpp b/clang/test/Sema/LifetimeSafety/invalidations.cpp index be1acc6bc7fbc..1572e78a27e14 100644 --- a/clang/test/Sema/LifetimeSafety/invalidations.cpp +++ b/clang/test/Sema/LifetimeSafety/invalidations.cpp @@ -485,13 +485,12 @@ void ConditionalFieldInvalidatesIterator(bool flag) { (flag ? s.strings1 : s.strings2).push_back("1"); *it; } -// FIXME: Requires field-sensitive AccessPaths to fix. void Invalidate1Use2ViaRefIsOk() { S s; - auto it = s.strings2.begin(); // expected-warning {{local variable 's' is later invalidated}} + auto it = s.strings2.begin(); auto& strings1 = s.strings1; - strings1.push_back("1"); // expected-note {{local variable 's' is invalidated here}} - *it; // expected-note {{later used here}} + strings1.push_back("1"); // OK + *it; } void Invalidate1UseSIsOk() { S s; @@ -894,12 +893,11 @@ struct StringOwner { std::string s, t; }; -// FIXME: False-positive void member_destructor_invalidates_pointer() { StringOwner owner = {"42", "43"}; - const char *p = owner.s.data(); // expected-warning {{local variable 'owner' is later invalidated}} - owner.t.~basic_string(); // expected-note {{local variable 'owner' is invalidated here}} - (void)*p; // expected-note {{later used here}} + const char *p = owner.s.data(); + owner.t.~basic_string(); // OK + (void)*p; } } // namespace explicit_destructor @@ -937,3 +935,79 @@ void invalid_after_ternary_reset(bool flag) { } } // namespace unique_ptr_invalidation + +namespace DeepFieldNesting { +struct Level3 { + std::vector<std::string> vec; + int x; +}; +struct Level2 { + Level3 inner3_1; + Level3 inner3_2; +}; +struct Level1 { + Level2 inner2_1; + Level2 inner2_2; +}; + +// Modifying sibling at Level 3: OK +void SiblingLevel3Ok() { + Level1 obj; + auto it = obj.inner2_1.inner3_1.vec.begin(); + obj.inner2_1.inner3_2.vec.push_back("1"); + *it; +} + +// Modifying sibling at Level 2: OK +void SiblingLevel2Ok() { + Level1 obj; + auto it = obj.inner2_1.inner3_1.vec.begin(); + obj.inner2_2.inner3_1.vec.push_back("1"); + *it; +} + +// Modifying sibling non-container field at Level 3: OK +void SiblingFieldLevel3Ok() { + Level1 obj; + auto it = obj.inner2_1.inner3_1.vec.begin(); + obj.inner2_1.inner3_1.x = 42; + *it; +} + +// Modifying parent structure after use: OK +void ParentModifiedAfterUseOk() { + Level1 obj; + auto it = obj.inner2_1.inner3_1.vec.begin(); + *it; // Use here + Level3 new_val; + obj.inner2_1.inner3_1 = new_val; // OK, because 'it' is no longer used! +} + +// Pointers with sibling modification: OK +void PointerSiblingLevel3Ok(Level1* ptr) { + auto it = ptr->inner2_1.inner3_1.vec.begin(); + ptr->inner2_1.inner3_2.vec.push_back("1"); // OK + *it; +} + +// References with sibling modification: OK +void ReferenceSiblingLevel3Ok(Level1& ref) { + auto it = ref.inner2_1.inner3_1.vec.begin(); + ref.inner2_1.inner3_2.vec.push_back("1"); // OK + *it; +} +} // namespace DeepFieldNesting + +namespace StructFieldDisambiguation { +struct S { + std::vector<int> v; + int x; +}; + +void TestStructVsField(S& s) { + int* px = &s.x; + s.v.push_back(1); // Invalidates s.v.* (interior), but must NOT invalidate s.x + *px = 42; // OK +} +} // namespace StructFieldDisambiguation + diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 78b7449958140..e13b8f88cb834 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -12,6 +12,7 @@ #include "clang/Analysis/Analyses/LifetimeSafety/Loans.h" #include "clang/Testing/TestAST.h" #include "llvm/ADT/StringMap.h" +#include "llvm/Support/raw_ostream.h" #include "gmock/gmock.h" #include "gtest/gtest.h" #include <optional> @@ -136,11 +137,16 @@ class LifetimeTestHelper { } bool isLoanToATemporary(LoanID LID) { - return Analysis.getFactManager() - .getLoanMgr() - .getLoan(LID) - ->getAccessPath() - .getAsMaterializeTemporaryExpr() != nullptr; + const Loan *L = Analysis.getFactManager().getLoanMgr().getLoan(LID); + return L->getAccessPath().getAsMaterializeTemporaryExpr() != nullptr; + } + + std::string getAccessPathString(LoanID LID) { + const Loan *L = Analysis.getFactManager().getLoanMgr().getLoan(LID); + std::string S; + llvm::raw_string_ostream OS(S); + L->getAccessPath().dump(OS); + return S; } // Gets the set of loans that are live at the given program point. A loan is @@ -287,7 +293,7 @@ class OriginsInfo { /// variable expected to be the source of a loan. /// \param Annotation A string identifying the program point (created with /// POINT()) where the check should be performed. -MATCHER_P2(HasLoansToImpl, LoanVars, Annotation, "") { +MATCHER_P2(HasLoansToImpl, LoanPathStrs, Annotation, "") { const OriginInfo &Info = arg; std::optional<OriginID> OIDOpt = Info.Helper.getOriginForDecl(Info.OriginVar); if (!OIDOpt) { @@ -303,36 +309,12 @@ MATCHER_P2(HasLoansToImpl, LoanVars, Annotation, "") { << Annotation << "'"; return false; } - std::vector<LoanID> ActualLoans(ActualLoansSetOpt->begin(), - ActualLoansSetOpt->end()); - - std::vector<LoanID> ExpectedLoans; - for (const auto &LoanVar : LoanVars) { - std::vector<LoanID> ExpectedLIDs = Info.Helper.getLoansForVar(LoanVar); - if (ExpectedLIDs.empty()) { - *result_listener << "could not find loan for var '" << LoanVar << "'"; - return false; - } - ExpectedLoans.insert(ExpectedLoans.end(), ExpectedLIDs.begin(), - ExpectedLIDs.end()); - } - std::sort(ExpectedLoans.begin(), ExpectedLoans.end()); - std::sort(ActualLoans.begin(), ActualLoans.end()); - if (ExpectedLoans != ActualLoans) { - *result_listener << "Expected: {"; - for (const auto &LoanID : ExpectedLoans) { - *result_listener << LoanID.Value << ", "; - } - *result_listener << "} Actual: {"; - for (const auto &LoanID : ActualLoans) { - *result_listener << LoanID.Value << ", "; - } - *result_listener << "}"; - return false; - } + std::vector<std::string> ActualLoanPaths; + for (LoanID LID : *ActualLoansSetOpt) + ActualLoanPaths.push_back(Info.Helper.getAccessPathString(LID)); - return ExplainMatchResult(UnorderedElementsAreArray(ExpectedLoans), - ActualLoans, result_listener); + return ExplainMatchResult(UnorderedElementsAreArray(LoanPathStrs), + ActualLoanPaths, result_listener); } enum class LivenessKindFilter { Maybe, Must, All }; @@ -1213,6 +1195,63 @@ TEST_F(LifetimeAnalysisTest, LifetimeboundConversionOperator) { EXPECT_THAT(Origin("v"), HasLoansTo({"owner"}, "p1")); } +TEST_F(LifetimeAnalysisTest, NestedFieldAccess) { + SetupTest(R"( + struct Inner { int val; }; + struct Outer { Inner f; }; + void target() { + Outer o; + Outer *p = &o; + int* p1 = &o.f.val; + POINT(a); + int* p2 = &p->f.val; + POINT(b); + } + )"); + EXPECT_THAT(Origin("p1"), HasLoansTo({"o.f.val"}, "a")); + EXPECT_THAT(Origin("p2"), HasLoansTo({"o.f.val"}, "b")); +} + +TEST_F(LifetimeAnalysisTest, PlaceholderParamField) { + SetupTest(R"( + struct S { int val; }; + void target(S* p) { + int* p1 = &p->val; + POINT(a); + } + )"); + EXPECT_THAT(Origin("p1"), HasLoansTo({"$p.val"}, "a")); +} + +TEST_F(LifetimeAnalysisTest, PlaceholderThisField) { + SetupTest(R"( + struct S { + int f; + void target() { + int* p1 = &f; + POINT(a); + } + }; + )"); + EXPECT_THAT(Origin("p1"), HasLoansTo({"$this.f"}, "a")); +} + +TEST_F(LifetimeAnalysisTest, PlaceholderThisNestedField) { + SetupTest(R"( + struct S1 { + int f; + }; + struct S { + S1 s1; + void target() { + int* p1 = &s1.f; + POINT(a); + } + }; + )"); + EXPECT_THAT(Origin("p1"), HasLoansTo({"$this.s1.f"}, "a")); +} + TEST_F(LifetimeAnalysisTest, LivenessDeadPointer) { SetupTest(R"( void target() { _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
