https://github.com/suoyuan666 created https://github.com/llvm/llvm-project/pull/208890
This commit mainly address the suggestion in https://github.com/llvm/llvm-project/pull/204592#discussion_r3523582077 to use `ImmutableList` for the DFS nodes in `buildOriginFlowChain`, and also updates the unreachable messages. >From 9d667b1da7631efd70dcfa1723ff689d6b3a2948 Mon Sep 17 00:00:00 2001 From: Yuan Suo <[email protected]> Date: Sat, 11 Jul 2026 16:22:16 +0800 Subject: [PATCH] [LifetimeSafety] Use ImmutableList for buildOriginFlowChain DFS nodes This commit mainly address the suggestion in https://github.com/llvm/llvm-project/pull/204592#discussion_r3523582077 to use `ImmutableList` for the DFS nodes in `buildOriginFlowChain`, and also updates the unreachable messages. Signed-off-by: Yuan Suo <[email protected]> --- .../Analyses/LifetimeSafety/LoanPropagation.h | 23 +++++----- clang/lib/Analysis/LifetimeSafety/Checker.cpp | 2 +- .../LifetimeSafety/LifetimeSafety.cpp | 5 ++- .../LifetimeSafety/LoanPropagation.cpp | 42 +++++++++++-------- clang/lib/Sema/SemaLifetimeSafety.h | 4 +- .../unittests/Analysis/LifetimeSafetyTest.cpp | 22 +++++----- 6 files changed, 56 insertions(+), 42 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h index 838daa024c953..3d489965a5aa6 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/LoanPropagation.h @@ -18,6 +18,7 @@ #include "clang/Analysis/Analyses/LifetimeSafety/Facts.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" +#include "llvm/ADT/ImmutableList.h" #include "llvm/ADT/ImmutableMap.h" #include "llvm/ADT/ImmutableSet.h" @@ -31,9 +32,11 @@ using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>; class LoanPropagationAnalysis { public: - LoanPropagationAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F, - OriginLoanMap::Factory &OriginLoanMapFactory, - LoanSet::Factory &LoanSetFactory); + LoanPropagationAnalysis( + const CFG &C, AnalysisDeclContext &AC, FactManager &F, + OriginLoanMap::Factory &OriginLoanMapFactory, + LoanSet::Factory &LoanSetFactory, + llvm::ImmutableList<OriginID>::Factory &OriginFlowChainFactory); ~LoanPropagationAnalysis(); LoanSet getLoans(OriginID OID, ProgramPoint P) const; @@ -47,14 +50,14 @@ class LoanPropagationAnalysis { /// The traversal follows OriginFlowFacts backwards to reconstruct the /// sequence of origins through which the loan flowed, ending at the origin /// where the loan was originally issued. - llvm::SmallVector<OriginID> buildOriginFlowChain(ProgramPoint StartPoint, - const OriginID StartOID, - const LoanID TargetLoan, - const CFG *Cfg) const; + llvm::ImmutableList<OriginID> buildOriginFlowChain(ProgramPoint StartPoint, + const OriginID StartOID, + const LoanID TargetLoan, + const CFG *Cfg) const; - llvm::SmallVector<OriginID> buildOriginFlowChain(const UseFact *UF, - const LoanID TargetLoan, - const CFG *Cfg) const; + llvm::ImmutableList<OriginID> buildOriginFlowChain(const UseFact *UF, + const LoanID TargetLoan, + const CFG *Cfg) const; private: class Impl; diff --git a/clang/lib/Analysis/LifetimeSafety/Checker.cpp b/clang/lib/Analysis/LifetimeSafety/Checker.cpp index f72f7f80abbc0..3b7248b28b945 100644 --- a/clang/lib/Analysis/LifetimeSafety/Checker.cpp +++ b/clang/lib/Analysis/LifetimeSafety/Checker.cpp @@ -527,7 +527,7 @@ class LifetimeChecker { /// extracts the corresponding expressions for each origin. Origins that refer /// to declarations (rather than expressions) are skipped. llvm::SmallVector<const Expr *> - getExprChain(llvm::ArrayRef<OriginID> OriginFlowChain) { + getExprChain(llvm::ImmutableList<OriginID> OriginFlowChain) { llvm::SmallVector<const Expr *> rs; for (const OriginID CurrOID : OriginFlowChain) if (const Expr *CurrExpr = diff --git a/clang/lib/Analysis/LifetimeSafety/LifetimeSafety.cpp b/clang/lib/Analysis/LifetimeSafety/LifetimeSafety.cpp index 798812327d3ab..50fc8e033d81b 100644 --- a/clang/lib/Analysis/LifetimeSafety/LifetimeSafety.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LifetimeSafety.cpp @@ -86,8 +86,11 @@ void LifetimeSafetyAnalysis::run() { /// the analysis. /// 3. Collapse ExpireFacts belonging to same source location into a single /// Fact. + + llvm::ImmutableList<OriginID>::Factory OriginFlowChainFactory; LoanPropagation = std::make_unique<LoanPropagationAnalysis>( - Cfg, AC, *FactMgr, Factory.OriginMapFactory, Factory.LoanSetFactory); + Cfg, AC, *FactMgr, Factory.OriginMapFactory, Factory.LoanSetFactory, + OriginFlowChainFactory); LiveOrigins = std::make_unique<LiveOriginsAnalysis>( Cfg, AC, *FactMgr, Factory.LivenessMapFactory); diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index 078892bd48c10..56e17c080db3d 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -18,6 +18,7 @@ #include "clang/Analysis/CFG.h" #include "clang/Basic/LLVM.h" #include "llvm/ADT/BitVector.h" +#include "llvm/ADT/ImmutableList.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/TimeProfiler.h" @@ -136,9 +137,11 @@ class AnalysisImpl public: AnalysisImpl(const CFG &C, AnalysisDeclContext &AC, FactManager &F, OriginLoanMap::Factory &OriginLoanMapFactory, - LoanSet::Factory &LoanSetFactory) + LoanSet::Factory &LoanSetFactory, + llvm::ImmutableList<OriginID>::Factory &OriginFlowChainFactory) : DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory), LoanSetFactory(LoanSetFactory), + OriginFlowChainFactory(OriginFlowChainFactory), PersistentOrigins(computePersistentOrigins(F, C)) {} using Base::transfer; @@ -203,10 +206,10 @@ class AnalysisImpl return getLoans(getState(P), OID); } - llvm::SmallVector<OriginID> buildOriginFlowChain(ProgramPoint StartPoint, - const OriginID StartOID, - const LoanID TargetLoan, - const CFG *Cfg) const { + llvm::ImmutableList<OriginID> buildOriginFlowChain(ProgramPoint StartPoint, + const OriginID StartOID, + const LoanID TargetLoan, + const CFG *Cfg) const { assert(getLoans(StartOID, StartPoint).contains(TargetLoan) && "TargetLoan must be present in the StartOID at the StartPoint"); @@ -225,12 +228,13 @@ class AnalysisImpl using SearchState = std::pair<const CFGBlock *, OriginID>; struct DFSNode { SearchState CurrState; - llvm::SmallVector<OriginID> OriginFlowChain; + llvm::ImmutableList<OriginID> OriginFlowChain; }; llvm::SmallVector<DFSNode> PendingStates; llvm::SmallSet<SearchState, 16> VistedStates; - PendingStates.push_back({{EndBlock, StartOID}, {}}); + PendingStates.push_back( + {{EndBlock, StartOID}, OriginFlowChainFactory.getEmptyList()}); // DFS loop to trace loan backwards through CFG while (!PendingStates.empty()) { @@ -241,7 +245,9 @@ class AnalysisImpl const auto [BuildResult, Complete] = buildOriginFlowChain(CurrBlock, CurrOID, TargetLoan); if (!BuildResult.empty()) { - CurrNode.OriginFlowChain.append(BuildResult); + for (OriginID OID : BuildResult) + CurrNode.OriginFlowChain = + OriginFlowChainFactory.add(OID, CurrNode.OriginFlowChain); CurrOID = BuildResult.back(); } @@ -259,13 +265,13 @@ class AnalysisImpl } } - llvm_unreachable( - "buildOriginFlowChain did not reach IssueFact for TargetLoan"); + llvm_unreachable("Could not reconstruct origin flow. Search finished " + "without reaching IssueFact"); } - llvm::SmallVector<OriginID> buildOriginFlowChain(const UseFact *UF, - const LoanID TargetLoan, - const CFG *Cfg) const { + llvm::ImmutableList<OriginID> buildOriginFlowChain(const UseFact *UF, + const LoanID TargetLoan, + const CFG *Cfg) const { for (const OriginList *Cur = UF->getUsedOrigins(); Cur; Cur = Cur->peelOuterOrigin()) if (getLoans(Cur->getOuterOriginID(), UF).contains(TargetLoan)) @@ -333,6 +339,7 @@ class AnalysisImpl OriginLoanMap::Factory &OriginLoanMapFactory; LoanSet::Factory &LoanSetFactory; + llvm::ImmutableList<OriginID>::Factory &OriginFlowChainFactory; /// Boolean vector indexed by origin ID. If true, the origin appears in /// multiple basic blocks and must participate in join operations. If false, /// the origin is block-local and can be discarded at block boundaries. @@ -347,9 +354,10 @@ class LoanPropagationAnalysis::Impl final : public AnalysisImpl { LoanPropagationAnalysis::LoanPropagationAnalysis( const CFG &C, AnalysisDeclContext &AC, FactManager &F, OriginLoanMap::Factory &OriginLoanMapFactory, - LoanSet::Factory &LoanSetFactory) + LoanSet::Factory &LoanSetFactory, + llvm::ImmutableList<OriginID>::Factory &OriginFlowChainFactory) : PImpl(std::make_unique<Impl>(C, AC, F, OriginLoanMapFactory, - LoanSetFactory)) { + LoanSetFactory, OriginFlowChainFactory)) { PImpl->run(); } @@ -359,13 +367,13 @@ LoanSet LoanPropagationAnalysis::getLoans(OriginID OID, ProgramPoint P) const { return PImpl->getLoans(OID, P); } -llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( +llvm::ImmutableList<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( ProgramPoint StartPoint, const OriginID StartOID, const LoanID TargetLoan, const CFG *Cfg) const { return PImpl->buildOriginFlowChain(StartPoint, StartOID, TargetLoan, Cfg); } -llvm::SmallVector<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( +llvm::ImmutableList<OriginID> LoanPropagationAnalysis::buildOriginFlowChain( const UseFact *UF, const LoanID TargetLoan, const CFG *Cfg) const { return PImpl->buildOriginFlowChain(UF, TargetLoan, Cfg); } diff --git a/clang/lib/Sema/SemaLifetimeSafety.h b/clang/lib/Sema/SemaLifetimeSafety.h index 48edf5f3f070f..c36402b393729 100644 --- a/clang/lib/Sema/SemaLifetimeSafety.h +++ b/clang/lib/Sema/SemaLifetimeSafety.h @@ -668,10 +668,10 @@ class LifetimeSafetySemaHelperImpl : public LifetimeSafetySemaHelper { if (OriginExprChain.empty()) return; - const Expr *LastExpr = OriginExprChain.back(); + const Expr *LastExpr = OriginExprChain.front(); std::string IssueStr = getDiagSubjectDescription(LastExpr); - for (const Expr *CurrExpr : reverse(OriginExprChain.drop_back())) { + for (const Expr *CurrExpr : OriginExprChain.drop_front()) { if (!shouldShowInAliasChain(CurrExpr, LastExpr)) continue; S.Diag(CurrExpr->getBeginLoc(), diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp b/clang/unittests/Analysis/LifetimeSafetyTest.cpp index 57cf7068affae..cb69b440c482c 100644 --- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp +++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp @@ -205,18 +205,18 @@ class LifetimeTestHelper { return Runner.getAnalysis().getFactManager().getBlockContaining(P); } - llvm::SmallVector<OriginID> + llvm::ImmutableList<OriginID> buildOriginFlowChain(llvm::StringRef StartOriginVar, llvm::StringRef EndLoanVar, llvm::StringRef Annotation) { std::optional<OriginID> StartOriginID = getOriginForDecl(StartOriginVar); std::vector<LoanID> EndLoanIDs = getLoansForVar(EndLoanVar); for (LoanID LID : EndLoanIDs) { - llvm::SmallVector<OriginID> OriginFlowChain = + llvm::ImmutableList<OriginID> OriginFlowChain = Runner.getAnalysis().getLoanPropagation().buildOriginFlowChain( getProgramPoint(Annotation), *StartOriginID, LID, Runner.getAnalysisContext().getCFG()); - if (!OriginFlowChain.empty()) + if (!OriginFlowChain.isEmpty()) return OriginFlowChain; } @@ -2001,11 +2001,11 @@ TEST_F(LifetimeAnalysisTest, BuildOriginFlowChain) { } )"); - llvm::SmallVector<OriginID> ChainForTgtA = + llvm::ImmutableList<OriginID> ChainForTgtA = Helper->buildOriginFlowChain("s", "tgta", "after_nested_merge"); - llvm::SmallVector<OriginID> ChainForTgtB = + llvm::ImmutableList<OriginID> ChainForTgtB = Helper->buildOriginFlowChain("s", "tgtb", "after_nested_merge"); - llvm::SmallVector<OriginID> ChainForTgtC = + llvm::ImmutableList<OriginID> ChainForTgtC = Helper->buildOriginFlowChain("s", "tgtc", "after_nested_merge"); EXPECT_THAT(ChainForTgtA, Contains(*Helper->getOriginForDecl("a"))); @@ -2050,7 +2050,7 @@ TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithSelfAssignment) { } )"); - const llvm::SmallVector<OriginID> OriginFlowChain = + const llvm::ImmutableList<OriginID> OriginFlowChain = Helper->buildOriginFlowChain("s", "tgt", "after_use"); EXPECT_THAT(OriginFlowChain, Contains(*Helper->getOriginForDecl("a"))); @@ -2067,7 +2067,7 @@ TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithMultiAssignInSameStmt) { } )"); - const llvm::SmallVector<OriginID> OriginFlowChain = + const llvm::ImmutableList<OriginID> OriginFlowChain = Helper->buildOriginFlowChain("s", "tgt", "after_use"); EXPECT_THAT(OriginFlowChain, Contains(*Helper->getOriginForDecl("a"))); @@ -2088,7 +2088,7 @@ TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithOverwritingAssignments) { } )"); - const llvm::SmallVector<OriginID> OriginFlowChain = + const llvm::ImmutableList<OriginID> OriginFlowChain = Helper->buildOriginFlowChain("s", "tgt1", "after_use"); EXPECT_THAT(OriginFlowChain, Contains(*Helper->getOriginForDecl("a"))); @@ -2110,9 +2110,9 @@ TEST_F(LifetimeAnalysisTest, BuildOriginFlowChainWithLifetimeBound) { } )"); - llvm::SmallVector<OriginID> ChainForTgtA = + llvm::ImmutableList<OriginID> ChainForTgtA = Helper->buildOriginFlowChain("s", "tgta", "after_use"); - llvm::SmallVector<OriginID> ChainForTgtB = + llvm::ImmutableList<OriginID> ChainForTgtB = Helper->buildOriginFlowChain("s", "tgtb", "after_use"); EXPECT_THAT(ChainForTgtA, Contains(*Helper->getOriginForDecl("a"))); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
