https://github.com/usx95 updated
https://github.com/llvm/llvm-project/pull/159991
>From 8a7ec9fe4b3e098b629102219cf52a116472e9a2 Mon Sep 17 00:00:00 2001
From: Utkarsh Saxena <u...@google.com>
Date: Sun, 21 Sep 2025 16:30:28 +0000
Subject: [PATCH] liveness-based-lifetime-policy
---
.../clang/Analysis/Analyses/LifetimeSafety.h | 18 +-
clang/lib/Analysis/LifetimeSafety.cpp | 461 +++++++++-------
.../test/Analysis/LifetimeSafety/benchmark.py | 82 ++-
clang/test/Sema/warn-lifetime-safety.cpp | 138 +++--
.../unittests/Analysis/LifetimeSafetyTest.cpp | 501 +++++++++---------
5 files changed, 713 insertions(+), 487 deletions(-)
diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
index 512cb76cd6349..6d3e3f61446e0 100644
--- a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
+++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h
@@ -29,7 +29,7 @@
namespace clang::lifetimes {
/// Enum to track the confidence level of a potential error.
-enum class Confidence {
+enum class Confidence : uint8_t {
None,
Maybe, // Reported as a potential error (-Wlifetime-safety-strict)
Definite // Reported as a definite error (-Wlifetime-safety-permissive)
@@ -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`).
@@ -110,8 +112,16 @@ 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.
- std::vector<LoanID> getExpiredLoansAtPoint(ProgramPoint PP) const;
+ /// Returns the set of origins that are live at a specific program point,
+ /// along with the confidence level of their liveness.
+ ///
+ /// An origin is considered live if there are potential future uses of that
+ /// origin after the given program point. The confidence level indicates
+ /// whether the origin is definitely live (Definite) due to being domintated
+ /// by a set of uses or only possibly live (Maybe) only on some but not all
+ /// control flow paths.
+ std::vector<std::pair<OriginID, Confidence>>
+ getLiveOriginsAtPoint(ProgramPoint PP) const;
/// Finds the OriginID for a given declaration.
/// Returns a null optional if not found.
@@ -138,7 +148,7 @@ class LifetimeSafetyAnalysis {
std::unique_ptr<LifetimeFactory> Factory;
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 14fb945382e65..7d880ea26833b 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -22,6 +22,7 @@
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/TimeProfiler.h"
#include <cstdint>
#include <memory>
@@ -865,29 +866,30 @@ class DataflowAnalysis {
std::conditional_t<Dir == Direction::Forward, ForwardDataflowWorklist,
BackwardDataflowWorklist>;
Worklist W(Cfg, AC);
+ llvm::SmallBitVector Seen(Cfg.getNumBlockIDs() + 1);
const CFGBlock *Start = isForward() ? &Cfg.getEntry() : &Cfg.getExit();
InStates[Start] = D.getInitialState();
+ Seen.set(Start->getBlockID());
W.enqueueBlock(Start);
- llvm::SmallBitVector Visited(Cfg.getNumBlockIDs() + 1);
-
while (const CFGBlock *B = W.dequeue()) {
Lattice StateIn = getInState(B);
Lattice StateOut = transferBlock(B, StateIn);
OutStates[B] = StateOut;
- Visited.set(B->getBlockID());
for (const CFGBlock *AdjacentB : isForward() ? B->succs() : B->preds()) {
if (!AdjacentB)
continue;
Lattice OldInState = getInState(AdjacentB);
- Lattice NewInState = D.join(OldInState, StateOut);
+ bool SeeingFirstTime = !Seen.test(AdjacentB->getBlockID());
+ Lattice NewInState =
+ SeeingFirstTime ? StateOut : D.join(OldInState, StateOut);
// Enqueue the adjacent block if its in-state has changed or if we have
- // never visited it.
- if (!Visited.test(AdjacentB->getBlockID()) ||
- NewInState != OldInState) {
+ // never seen it.
+ if (SeeingFirstTime || NewInState != OldInState) {
InStates[AdjacentB] = NewInState;
W.enqueueBlock(AdjacentB);
+ Seen.set(AdjacentB->getBlockID());
}
}
}
@@ -972,42 +974,39 @@ static llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A,
return A;
}
-/// Checks if set A is a subset of set B.
-template <typename T>
-static bool isSubsetOf(const llvm::ImmutableSet<T> &A,
- const llvm::ImmutableSet<T> &B) {
- // Empty set is a subset of all sets.
- if (A.isEmpty())
- return true;
-
- for (const T &Elem : A)
- if (!B.contains(Elem))
- return false;
- return true;
-}
-
/// Computes the key-wise union of two ImmutableMaps.
+/// \param SymmetricJoin If true, the join is symmetric, applying JoinValues to
+/// keys that are unique to either of the input maps. If false, the join is
+/// asymmetric: keys unique to the first map are preserved as-is, while keys
+/// unique to the second map are processed by JoinValues.
// TODO(opt): This key-wise join is a performance bottleneck. A more
// efficient merge could be implemented using a Patricia Trie or HAMT
// instead of the current AVL-tree-based ImmutableMap.
template <typename K, typename V, typename Joiner>
static llvm::ImmutableMap<K, V>
-join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B,
- typename llvm::ImmutableMap<K, V>::Factory &F, Joiner JoinValues) {
+join(const llvm::ImmutableMap<K, V> &A, const llvm::ImmutableMap<K, V> &B,
+ typename llvm::ImmutableMap<K, V>::Factory &F, Joiner JoinValues,
+ bool SymmetricJoin) {
if (A.getHeight() < B.getHeight())
- std::swap(A, B);
+ return join(B, A, F, JoinValues, SymmetricJoin);
// For each element in B, join it with the corresponding element in A
// (or with an empty value if it doesn't exist in A).
+ llvm::ImmutableMap<K, V> Res = A;
for (const auto &Entry : B) {
const K &Key = Entry.first;
const V &ValB = Entry.second;
- if (const V *ValA = A.lookup(Key))
- A = F.add(A, Key, JoinValues(*ValA, ValB));
- else
- A = F.add(A, Key, ValB);
+ Res = F.add(Res, Key, JoinValues(A.lookup(Key), &ValB));
+ }
+ if (SymmetricJoin) {
+ for (const auto &Entry : A) {
+ const K &Key = Entry.first;
+ const V &ValA = Entry.second;
+ if (!B.contains(Key))
+ Res = F.add(Res, Key, JoinValues(&ValA, nullptr));
+ }
}
- return A;
+ return Res;
}
} // namespace utils
@@ -1015,19 +1014,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
-/// that all created states share the same underlying memory management.
-struct LifetimeFactory {
- llvm::BumpPtrAllocator Allocator;
- OriginLoanMap::Factory OriginMapFactory{Allocator, /*canonicalize=*/false};
- LoanSet::Factory LoanSetFactory{Allocator, /*canonicalize=*/false};
- ExpiredLoanMap::Factory ExpiredLoanMapFactory{Allocator,
- /*canonicalize=*/false};
-};
-
/// Represents the dataflow lattice for loan propagation.
///
/// This lattice tracks which loans each origin may hold at a given program
@@ -1071,10 +1057,10 @@ class LoanPropagationAnalysis
public:
LoanPropagationAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager
&F,
- LifetimeFactory &LFactory)
- : DataflowAnalysis(C, AC, F),
- OriginLoanMapFactory(LFactory.OriginMapFactory),
- LoanSetFactory(LFactory.LoanSetFactory) {}
+ OriginLoanMap::Factory &OriginLoanMapFactory,
+ LoanSet::Factory &LoanSetFactory)
+ : DataflowAnalysis(C, AC, F), OriginLoanMapFactory(OriginLoanMapFactory),
+ LoanSetFactory(LoanSetFactory) {}
using Base::transfer;
@@ -1085,11 +1071,19 @@ class LoanPropagationAnalysis
/// Merges two lattices by taking the union of loans for each origin.
// TODO(opt): Keep the state small by removing origins which become dead.
Lattice join(Lattice A, Lattice B) {
- OriginLoanMap JoinedOrigins =
- utils::join(A.Origins, B.Origins, OriginLoanMapFactory,
- [&](LoanSet S1, LoanSet S2) {
- return utils::join(S1, S2, LoanSetFactory);
- });
+ OriginLoanMap JoinedOrigins = utils::join(
+ A.Origins, B.Origins, OriginLoanMapFactory,
+ [&](const LoanSet *S1, const LoanSet *S2) {
+ assert((S1 || S2) && "unexpectedly merging 2 empty sets");
+ if (!S1)
+ return *S2;
+ if (!S2)
+ return *S1;
+ return utils::join(*S1, *S2, LoanSetFactory);
+ },
+ // Asymmetric join is a performance win. For origins present only on
one
+ // branch, the loan set can be carried over as-is.
+ /*SymmetricJoin=*/false);
return Lattice(JoinedOrigins);
}
@@ -1118,12 +1112,12 @@ class LoanPropagationAnalysis
OriginLoanMapFactory.add(In.Origins, DestOID, MergedLoans));
}
- LoanSet getLoans(OriginID OID, ProgramPoint P) {
+ LoanSet getLoans(OriginID OID, ProgramPoint P) const {
return getLoans(getState(P), OID);
}
private:
- LoanSet getLoans(Lattice L, OriginID OID) {
+ LoanSet getLoans(Lattice L, OriginID OID) const {
if (auto *Loans = L.Origins.lookup(OID))
return *Loans;
return LoanSetFactory.getEmptySet();
@@ -1131,96 +1125,181 @@ class LoanPropagationAnalysis
};
// ========================================================================= //
-// Expired Loans Analysis
+// Live Origins Analysis
// ========================================================================= //
-/// The dataflow lattice for tracking the set of expired loans.
-struct ExpiredLattice {
- /// Map from an expired `LoanID` to the `ExpireFact` that made it expire.
- ExpiredLoanMap Expired;
+/// Information about why an origin is live at a program point.
+struct LivenessInfo {
+ /// The use that makes the origin live. If liveness is propagated from
+ /// multiple uses along different paths, this will point to the use appearing
+ /// before in the translation unit.
+ const UseFact *CausingUseFact;
+ /// The confidence in the liveness of the origin.
+ /// `Definite`: The origin is live on all control-flow paths from the current
+ /// point to the function's exit (i.e. the current point is dominated by a
set
+ /// of uses).
+ /// `Maybe`: indicates it is live on some but not all paths.
+ Confidence ConfidenceLevel;
- ExpiredLattice() : Expired(nullptr) {};
- explicit ExpiredLattice(ExpiredLoanMap M) : Expired(M) {}
+ LivenessInfo() : CausingUseFact(nullptr), ConfidenceLevel(Confidence::None)
{}
+ LivenessInfo(const UseFact *UF, Confidence C)
+ : CausingUseFact(UF), ConfidenceLevel(C) {}
- bool operator==(const ExpiredLattice &Other) const {
- return Expired == Other.Expired;
+ bool operator==(const LivenessInfo &Other) const {
+ return CausingUseFact == Other.CausingUseFact &&
+ ConfidenceLevel == Other.ConfidenceLevel;
}
- bool operator!=(const ExpiredLattice &Other) const {
+ bool operator!=(const LivenessInfo &Other) const { return !(*this == Other);
}
+
+ void Profile(llvm::FoldingSetNodeID &IDBuilder) const {
+ IDBuilder.AddPointer(CausingUseFact);
+ IDBuilder.Add(ConfidenceLevel);
+ }
+};
+
+using LivenessMap = llvm::ImmutableMap<OriginID, LivenessInfo>;
+
+/// The dataflow lattice for origin liveness analysis.
+/// It tracks which origins are live, why they're live (which UseFact),
+/// and the confidence level of that liveness.
+struct LivenessLattice {
+ LivenessMap LiveOrigins;
+
+ LivenessLattice() : LiveOrigins(nullptr) {};
+
+ explicit LivenessLattice(LivenessMap L) : LiveOrigins(L) {}
+
+ 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 << "ExpiredLattice State:\n";
- if (Expired.isEmpty())
+ void dump(llvm::raw_ostream &OS, const OriginManager &OM) const {
+ if (LiveOrigins.isEmpty())
OS << " <empty>\n";
- for (const auto &[ID, _] : Expired)
- OS << " Loan " << ID << " is expired\n";
+ for (const auto &Entry : LiveOrigins) {
+ OriginID OID = Entry.first;
+ const LivenessInfo &Info = Entry.second;
+ OS << " ";
+ OM.dump(OID, OS);
+ OS << " is ";
+ switch (Info.ConfidenceLevel) {
+ case Confidence::Definite:
+ OS << "definitely";
+ break;
+ case Confidence::Maybe:
+ OS << "maybe";
+ break;
+ case Confidence::None:
+ llvm_unreachable("liveness condidence should not be none.");
+ }
+ OS << " live at this point\n";
+ }
}
};
-/// The analysis that tracks which loans have expired.
-class ExpiredLoansAnalysis
- : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice,
- Direction::Forward> {
-
- ExpiredLoanMap::Factory &Factory;
+/// The analysis that tracks which origins are live, with granular information
+/// about the causing use fact and confidence level. This is a backward
+/// analysis.
+class LiveOriginAnalysis
+ : public DataflowAnalysis<LiveOriginAnalysis, LivenessLattice,
+ Direction::Backward> {
+ FactManager &FactMgr;
+ LivenessMap::Factory &Factory;
public:
- ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
- LifetimeFactory &Factory)
- : DataflowAnalysis(C, AC, F), Factory(Factory.ExpiredLoanMapFactory) {}
-
- using Base::transfer;
+ LiveOriginAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
+ LivenessMap::Factory &SF)
+ : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF) {}
+ using DataflowAnalysis<LiveOriginAnalysis, Lattice,
+ Direction::Backward>::transfer;
- StringRef getAnalysisName() const { return "ExpiredLoans"; }
+ StringRef getAnalysisName() const { return "LiveOrigins"; }
Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }
- /// Merges two lattices by taking the union of the two expired loans.
- Lattice join(Lattice L1, Lattice L2) {
- return Lattice(
- utils::join(L1.Expired, L2.Expired, Factory,
- // Take the last expiry fact to make this hermetic.
- [](const ExpireFact *F1, const ExpireFact *F2) {
- return F1->getExpiryLoc() > F2->getExpiryLoc() ? F1 : F2;
- }));
- }
-
- Lattice transfer(Lattice In, const ExpireFact &F) {
- return Lattice(Factory.add(In.Expired, F.getLoanID(), &F));
- }
-
- // Removes the loan from the set of expired loans.
- //
- // When a loan is re-issued (e.g., in a loop), it is no longer considered
- // expired. A loan can be in the expired set at the point of issue due to
- // the dataflow state from a previous loop iteration being propagated along
- // a backedge in the CFG.
- //
- // Note: This has a subtle false-negative though where a loan from previous
- // iteration is not overwritten by a reissue. This needs careful tracking
- // of loans "across iterations" which can be considered for future
- // enhancements.
- //
- // void foo(int safe) {
- // int* p = &safe;
- // int* q = &safe;
- // while (condition()) {
- // int x = 1;
- // p = &x; // A loan to 'x' is issued to 'p' in every iteration.
- // if (condition()) {
- // q = p;
- // }
- // (void)*p; // OK — 'p' points to 'x' from new iteration.
- // (void)*q; // UaF - 'q' still points to 'x' from previous iteration
- // // which is now destroyed.
- // }
- // }
- Lattice transfer(Lattice In, const IssueFact &F) {
- return Lattice(Factory.remove(In.Expired, F.getLoanID()));
+ /// Merges two lattices by combining liveness information.
+ /// When the same origin has different confidence levels, we take the lower
+ /// one.
+ Lattice join(Lattice L1, Lattice L2) const {
+ LivenessMap Merged = L1.LiveOrigins;
+ // Take the earliest UseFact to make the join hermetic.
+ auto CombineUseFact = [](const UseFact *A,
+ const UseFact *B) -> const UseFact * {
+ return A->getUseExpr()->getExprLoc() < B->getUseExpr()->getExprLoc() ? A
+ : B;
+ };
+ auto CombineConfidence = [](Confidence C1, Confidence C2) -> Confidence {
+ assert(C1 != Confidence::None &&
+ "liveness confidence should not be none.");
+ assert(C2 != Confidence::None &&
+ "liveness confidence should not be none.");
+ // Only return Definite if both paths are Definite, otherwise Maybe.
+ if (C1 == Confidence::Definite && C2 == Confidence::Definite)
+ return Confidence::Definite;
+ return Confidence::Maybe;
+ };
+ auto CombineLivenessInfo = [&](const LivenessInfo *L1,
+ const LivenessInfo *L2) -> LivenessInfo {
+ assert((L1 || L2) && "unexpectedly merging 2 empty sets");
+ if (!L1)
+ return LivenessInfo(L2->CausingUseFact, Confidence::Maybe);
+ if (!L2)
+ return LivenessInfo(L1->CausingUseFact, Confidence::Maybe);
+ return LivenessInfo(
+ CombineUseFact(L1->CausingUseFact, L2->CausingUseFact),
+ CombineConfidence(L1->ConfidenceLevel, L2->ConfidenceLevel));
+ };
+ return Lattice(utils::join(
+ L1.LiveOrigins, L2.LiveOrigins, Factory, CombineLivenessInfo,
+ // A symmetric join is required here. If an origin is live on one
+ // branch but not the other, its confidence must be demoted to `Maybe`.
+ /*SymmetricJoin=*/true));
+ }
+
+ /// A read operation makes the origin live with definite confidence, as it
+ /// dominates this program point. A write operation kills the liveness of
+ /// the origin since it overwrites the value.
+ Lattice transfer(Lattice In, const UseFact &UF) {
+ OriginID OID = UF.getUsedOrigin(FactMgr.getOriginMgr());
+ // Write kills liveness.
+ if (UF.isWritten())
+ return Lattice(Factory.remove(In.LiveOrigins, OID));
+ // Read makes origin live with definite confidence (dominates this point).
+ return Lattice(Factory.add(In.LiveOrigins, OID,
+ LivenessInfo(&UF, Confidence::Definite)));
+ }
+
+ /// Issuing a new loan to an origin kills its liveness.
+ Lattice transfer(Lattice In, const IssueFact &IF) {
+ return Lattice(Factory.remove(In.LiveOrigins, IF.getOriginID()));
}
- ExpiredLoanMap getExpiredLoans(ProgramPoint P) { return getState(P).Expired;
}
+ /// An OriginFlow kills the liveness of the destination origin if `KillDest`
+ /// is true. Otherwise, it propagates liveness from destination to source.
+ Lattice transfer(Lattice In, const OriginFlowFact &OF) {
+ if (!OF.getKillDest())
+ return In;
+ return Lattice(Factory.remove(In.LiveOrigins, OF.getDestOriginID()));
+ }
+
+ LivenessMap getLiveOrigins(ProgramPoint P) const {
+ return getState(P).LiveOrigins;
+ }
+
+ // Dump liveness values on all test points in the program.
+ void dump(llvm::raw_ostream &OS, const LifetimeSafetyAnalysis &LSA) const {
+ llvm::dbgs() << "==========================================\n";
+ llvm::dbgs() << getAnalysisName() << " results:\n";
+ llvm::dbgs() << "==========================================\n";
+ for (const auto &Entry : LSA.getTestPoints()) {
+ OS << "TestPoint: " << Entry.getKey() << "\n";
+ getState(Entry.getValue()).dump(OS, FactMgr.getOriginMgr());
+ }
+ }
};
// ========================================================================= //
@@ -1238,84 +1317,62 @@ 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<UseFact>())
- checkUse(UF);
+ if (const auto *EF = F->getAs<ExpireFact>())
+ checkExpiry(EF);
issuePendingWarnings();
}
- /// Checks for use-after-free errors for a given use of an Origin.
+ /// Checks for use-after-free errors when a loan expires.
///
- /// 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)
+ /// This method examines all live origins at the expiry point and determines
+ /// if any of them hold the expiring loan. If so, it creates a pending
+ /// warning with the appropriate confidence level based on the liveness
+ /// information. The confidence reflects whether the origin is definitely
+ /// or maybe live at this point.
+ ///
+ /// Note: This implementation considers only the confidence of origin
+ /// liveness. Future enhancements could also consider the confidence of loan
+ /// propagation (e.g., a loan may only be held on some execution paths).
+ void checkExpiry(const ExpireFact *EF) {
+ LoanID ExpiredLoan = EF->getLoanID();
+ LivenessMap Origins = LiveOrigins.getLiveOrigins(EF);
+ Confidence CurConfidence = Confidence::None;
+ const UseFact *BadUse = nullptr;
+ for (auto &[OID, Info] : Origins) {
+ LoanSet HeldLoans = LoanPropagation.getLoans(OID, EF);
+ if (!HeldLoans.contains(ExpiredLoan))
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};
+ // Loan is defaulted.
+ if (CurConfidence < Info.ConfidenceLevel) {
+ CurConfidence = Info.ConfidenceLevel;
+ BadUse = Info.CausingUseFact;
+ }
}
+ if (!BadUse)
+ return;
+ // We have a use-after-free.
+ Confidence LastConf = FinalWarningsMap.lookup(ExpiredLoan).ConfidenceLevel;
+ if (LastConf >= CurConfidence)
+ return;
+ FinalWarningsMap[ExpiredLoan] = {/*ExpiryLoc=*/EF->getExpiryLoc(),
+ /*UseExpr=*/BadUse->getUseExpr(),
+ /*ConfidenceLevel=*/CurConfidence};
}
void issuePendingWarnings() {
@@ -1334,6 +1391,15 @@ class LifetimeChecker {
// LifetimeSafetyAnalysis Class Implementation
// ========================================================================= //
+/// An object to hold the factories for immutable collections, ensuring
+/// that all created states share the same underlying memory management.
+struct LifetimeFactory {
+ llvm::BumpPtrAllocator Allocator;
+ OriginLoanMap::Factory OriginMapFactory{Allocator, /*canonicalize=*/false};
+ LoanSet::Factory LoanSetFactory{Allocator, /*canonicalize=*/false};
+ LivenessMap::Factory LivenessMapFactory{Allocator, /*canonicalize=*/false};
+};
+
// We need this here for unique_ptr with forward declared class.
LifetimeSafetyAnalysis::~LifetimeSafetyAnalysis() = default;
@@ -1364,15 +1430,16 @@ void LifetimeSafetyAnalysis::run() {
/// the analysis.
/// 3. Collapse ExpireFacts belonging to same source location into a single
/// Fact.
- LoanPropagation =
- std::make_unique<LoanPropagationAnalysis>(Cfg, AC, *FactMgr, *Factory);
+ LoanPropagation = std::make_unique<LoanPropagationAnalysis>(
+ Cfg, AC, *FactMgr, Factory->OriginMapFactory, Factory->LoanSetFactory);
LoanPropagation->run();
- ExpiredLoans =
- std::make_unique<ExpiredLoansAnalysis>(Cfg, AC, *FactMgr, *Factory);
- ExpiredLoans->run();
+ LiveOrigins = std::make_unique<LiveOriginAnalysis>(
+ Cfg, AC, *FactMgr, Factory->LivenessMapFactory);
+ LiveOrigins->run();
+ DEBUG_WITH_TYPE("LiveOrigins", LiveOrigins->dump(llvm::dbgs(), *this));
- LifetimeChecker Checker(*LoanPropagation, *ExpiredLoans, *FactMgr, AC,
+ LifetimeChecker Checker(*LoanPropagation, *LiveOrigins, *FactMgr, AC,
Reporter);
Checker.run();
}
@@ -1383,15 +1450,6 @@ LoanSet LifetimeSafetyAnalysis::getLoansAtPoint(OriginID
OID,
return LoanPropagation->getLoans(OID, PP);
}
-std::vector<LoanID>
-LifetimeSafetyAnalysis::getExpiredLoansAtPoint(ProgramPoint PP) const {
- assert(ExpiredLoans && "ExpiredLoansAnalysis has not been run.");
- std::vector<LoanID> Result;
- for (const auto &pair : ExpiredLoans->getExpiredLoans(PP))
- Result.push_back(pair.first);
- return Result;
-}
-
std::optional<OriginID>
LifetimeSafetyAnalysis::getOriginIDForDecl(const ValueDecl *D) const {
assert(FactMgr && "FactManager not initialized");
@@ -1411,6 +1469,15 @@ LifetimeSafetyAnalysis::getLoanIDForVar(const VarDecl
*VD) const {
return Result;
}
+std::vector<std::pair<OriginID, Confidence>>
+LifetimeSafetyAnalysis::getLiveOriginsAtPoint(ProgramPoint PP) const {
+ assert(LiveOrigins && "LiveOriginAnalysis has not been run.");
+ std::vector<std::pair<OriginID, Confidence>> Result;
+ for (auto &[OID, Info] : LiveOrigins->getLiveOrigins(PP))
+ Result.push_back({OID, Info.ConfidenceLevel});
+ return Result;
+}
+
llvm::StringMap<ProgramPoint> LifetimeSafetyAnalysis::getTestPoints() const {
assert(FactMgr && "FactManager not initialized");
llvm::StringMap<ProgramPoint> AnnotationToPointMap;
diff --git a/clang/test/Analysis/LifetimeSafety/benchmark.py
b/clang/test/Analysis/LifetimeSafety/benchmark.py
index d2e5f0b2122a3..cd5b30818a4a8 100644
--- a/clang/test/Analysis/LifetimeSafety/benchmark.py
+++ b/clang/test/Analysis/LifetimeSafety/benchmark.py
@@ -145,6 +145,60 @@ def generate_cpp_nested_loop_test(n: int) -> str:
return cpp_code
+def generate_cpp_switch_fan_out_test(n: int) -> str:
+ """
+ Generates C++ code with a switch statement with N branches.
+ Each branch 'i' 'uses' (reads) a single, unique pointer 'pi'.
+ This pattern creates a "fan-in" join point for the backward
+ liveness analysis, stressing the LivenessMap::join operation
+ by forcing it to merge N disjoint, single-element sets of live origins.
+ The resulting complexity for LiveOrigins should be O(n log n) or higher.
+
+ Example (n=3):
+ struct MyObj { int id; ~MyObj() {} };
+
+ void switch_fan_out_3(int condition) {
+ MyObj v1{1}; MyObj v2{1}; MyObj v3{1};
+ MyObj* p1 = &v1; MyObj* p2 = &v2; MyObj* p3 = &v3;
+
+ switch (condition % 3) {
+ case 0:
+ p1->id = 1;
+ break;
+ case 1:
+ p2->id = 1;
+ break;
+ case 2:
+ p3->id = 1;
+ break;
+ }
+ }
+ """
+ if n <= 0:
+ return "// Number of variables must be positive."
+
+ cpp_code = "struct MyObj { int id; ~MyObj() {} };\n\n"
+ cpp_code += f"void switch_fan_out{n}(int condition) {{\n"
+ # Generate N distinct objects
+ for i in range(1, n + 1):
+ cpp_code += f" MyObj v{i}{{1}};\n"
+ cpp_code += "\n"
+ # Generate N distinct pointers, each as a separate variable
+ for i in range(1, n + 1):
+ cpp_code += f" MyObj* p{i} = &v{i};\n"
+ cpp_code += "\n"
+
+ cpp_code += f" switch (condition % {n}) {{\n"
+ for case_num in range(n):
+ cpp_code += f" case {case_num}:\n"
+ cpp_code += f" p{case_num + 1}->id = 1;\n"
+ cpp_code += " break;\n"
+
+ cpp_code += " }\n}\n"
+ cpp_code += f"\nint main() {{ switch_fan_out{n}(0); return 0; }}\n"
+ return cpp_code
+
+
def analyze_trace_file(trace_path: str) -> dict:
"""
Parses the -ftime-trace JSON output to find durations for the lifetime
@@ -156,14 +210,14 @@ def analyze_trace_file(trace_path: str) -> dict:
"total_us": 0.0,
"fact_gen_us": 0.0,
"loan_prop_us": 0.0,
- "expired_loans_us": 0.0,
+ "live_origins_us": 0.0,
}
event_name_map = {
"LifetimeSafetyAnalysis": "lifetime_us",
"ExecuteCompiler": "total_us",
"FactGenerator": "fact_gen_us",
"LoanPropagation": "loan_prop_us",
- "ExpiredLoans": "expired_loans_us",
+ "LiveOrigins": "live_origins_us",
}
try:
with open(trace_path, "r") as f:
@@ -227,7 +281,7 @@ def generate_markdown_report(results: dict) -> str:
# Table header
report.append(
- "| N (Input Size) | Total Time | Analysis Time (%) | Fact
Generator (%) | Loan Propagation (%) | Expired Loans (%) |"
+ "| N (Input Size) | Total Time | Analysis Time (%) | Fact
Generator (%) | Loan Propagation (%) | Live Origins (%) |"
)
report.append(
"|:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:|"
@@ -247,7 +301,7 @@ def generate_markdown_report(results: dict) -> str:
f"{data['lifetime_ms'][i] / total_t * 100:>17.2f}% |",
f"{data['fact_gen_ms'][i] / total_t * 100:>18.2f}% |",
f"{data['loan_prop_ms'][i] / total_t * 100:>20.2f}% |",
- f"{data['expired_loans_ms'][i] / total_t * 100:>17.2f}% |",
+ f"{data['live_origins_ms'][i] / total_t * 100:>17.2f}% |",
]
report.append(" ".join(row))
@@ -259,7 +313,7 @@ def generate_markdown_report(results: dict) -> str:
"Total Analysis": data["lifetime_ms"],
"FactGenerator": data["fact_gen_ms"],
"LoanPropagation": data["loan_prop_ms"],
- "ExpiredLoans": data["expired_loans_ms"],
+ "LiveOrigins": data["live_origins_ms"],
}
for phase_name, y_data in analysis_phases.items():
@@ -302,7 +356,13 @@ def run_single_test(
source_file,
]
- result = subprocess.run(clang_command, capture_output=True, text=True,
timeout=60)
+ try:
+ result = subprocess.run(
+ clang_command, capture_output=True, text=True, timeout=60
+ )
+ except subprocess.TimeoutExpired:
+ print(f"Compilation timed out for N={n}!", file=sys.stderr)
+ return {}
if result.returncode != 0:
print(f"Compilation failed for N={n}!", file=sys.stderr)
@@ -354,6 +414,12 @@ def run_single_test(
"generator_func": generate_cpp_nested_loop_test,
"n_values": [50, 100, 150, 200],
},
+ {
+ "name": "switch_fan_out",
+ "title": "Switch Fan-out",
+ "generator_func": generate_cpp_switch_fan_out_test,
+ "n_values": [500, 1000, 2000, 4000],
+ },
]
results = {}
@@ -368,7 +434,7 @@ def run_single_test(
"total_ms": [],
"fact_gen_ms": [],
"loan_prop_ms": [],
- "expired_loans_ms": [],
+ "live_origins_ms": [],
}
for n in config["n_values"]:
durations_ms = run_single_test(
@@ -387,7 +453,7 @@ def run_single_test(
f" Total Analysis:
{human_readable_time(durations_ms['lifetime_ms'])} | "
f"FactGen:
{human_readable_time(durations_ms['fact_gen_ms'])} | "
f"LoanProp:
{human_readable_time(durations_ms['loan_prop_ms'])} | "
- f"ExpiredLoans:
{human_readable_time(durations_ms['expired_loans_ms'])}"
+ f"LiveOrigins:
{human_readable_time(durations_ms['live_origins_ms'])}"
)
print("\n\n" + "=" * 80)
diff --git a/clang/test/Sema/warn-lifetime-safety.cpp
b/clang/test/Sema/warn-lifetime-safety.cpp
index f6bec6e66c365..4f234f0ac6e2d 100644
--- a/clang/test/Sema/warn-lifetime-safety.cpp
+++ b/clang/test/Sema/warn-lifetime-safety.cpp
@@ -126,11 +126,15 @@ void definite_single_pointer_multiple_loans_gsl(bool
cond) {
v.use(); // expected-note 2 {{later used here}}
}
-
-//===----------------------------------------------------------------------===//
-// Potential (Maybe) Use-After-Free (-W...strict)
-// These are cases where the pointer *may* become dangling, depending on the
path taken.
-//===----------------------------------------------------------------------===//
+void definite_if_branch(bool cond) {
+ MyObj safe;
+ MyObj* p = &safe;
+ if (cond) {
+ MyObj temp;
+ p = &temp; // expected-warning {{object whose reference is captured does
not live long enough}}
+ } // expected-note {{destroyed here}}
+ (void)*p; // expected-note {{later used here}}
+}
void potential_if_branch(bool cond) {
MyObj safe;
@@ -139,15 +143,18 @@ void potential_if_branch(bool cond) {
MyObj temp;
p = &temp; // expected-warning {{object whose reference is captured may
not live long enough}}
} // expected-note {{destroyed here}}
- (void)*p; // expected-note {{later used here}}
+ if (!cond)
+ (void)*p; // expected-note {{later used here}}
+ else
+ p = &safe;
}
-void potential_if_branch_gsl(bool cond) {
+void definite_if_branch_gsl(bool cond) {
MyObj safe;
View v = safe;
if (cond) {
MyObj temp;
- v = temp; // expected-warning {{object whose reference is captured may
not live long enough}}
+ v = temp; // expected-warning {{object whose reference is captured does
not live long enough}}
} // expected-note {{destroyed here}}
v.use(); // expected-note {{later used here}}
}
@@ -159,13 +166,14 @@ void definite_potential_together(bool cond) {
{
MyObj s;
- p_definite = &s; // expected-warning {{does not live long enough}}
- if (cond) {
- p_maybe = &s; // expected-warning {{may not live long enough}}
- }
- } // expected-note 2 {{destroyed here}}
- (void)*p_definite; // expected-note {{later used here}}
- (void)*p_maybe; // expected-note {{later used here}}
+ if (cond)
+ p_definite = &s; // expected-warning {{does not live long enough}}
+ if (cond)
+ p_maybe = &s; // expected-warning {{may not live long enough}}
+ } // expected-note 2 {{destroyed here}}
+ (void)*p_definite; // expected-note {{later used here}}
+ if (!cond)
+ (void)*p_maybe; // expected-note {{later used here}}
}
void definite_overrides_potential(bool cond) {
@@ -189,10 +197,19 @@ void definite_overrides_potential(bool cond) {
(void)*q;
}
-
-//===----------------------------------------------------------------------===//
-// Control Flow Tests
-//===----------------------------------------------------------------------===//
+void potential_due_to_conditional_killing(bool cond) {
+ MyObj safe;
+ MyObj* q;
+ {
+ MyObj s;
+ q = &s; // expected-warning {{may not live long enough}}
+ } // expected-note {{destroyed here}}
+ if (cond) {
+ // 'q' is conditionally "rescued". 'p' is not.
+ q = &safe;
+ }
+ (void)*q; // expected-note {{later used here}}
+}
void potential_for_loop_use_after_loop_body(MyObj safe) {
MyObj* p = &safe;
@@ -215,34 +232,35 @@ void potential_for_loop_gsl() {
void potential_for_loop_use_before_loop_body(MyObj safe) {
MyObj* p = &safe;
+ // Prefer the earlier use for diagnsotics.
for (int i = 0; i < 1; ++i) {
(void)*p; // expected-note {{later used here}}
MyObj s;
- p = &s; // expected-warning {{may not live long enough}}
+ p = &s; // expected-warning {{does not live long enough}}
} // expected-note {{destroyed here}}
(void)*p;
}
-void potential_loop_with_break(bool cond) {
+void definite_loop_with_break(bool cond) {
MyObj safe;
MyObj* p = &safe;
for (int i = 0; i < 10; ++i) {
if (cond) {
MyObj temp;
- p = &temp; // expected-warning {{may not live long enough}}
+ p = &temp; // expected-warning {{does not live long enough}}
break; // expected-note {{destroyed here}}
}
}
(void)*p; // expected-note {{later used here}}
}
-void potential_loop_with_break_gsl(bool cond) {
+void definite_loop_with_break_gsl(bool cond) {
MyObj safe;
View v = safe;
for (int i = 0; i < 10; ++i) {
if (cond) {
MyObj temp;
- v = temp; // expected-warning {{object whose reference is captured may
not live long enough}}
+ v = temp; // expected-warning {{object whose reference is captured
does not live long enough}}
break; // expected-note {{destroyed here}}
}
}
@@ -250,37 +268,52 @@ void potential_loop_with_break_gsl(bool cond) {
}
void potential_multiple_expiry_of_same_loan(bool cond) {
- // Choose the last expiry location for the loan.
+ // Choose the last expiry location for the loan (e.g., through scope-ends
and break statements).
MyObj safe;
MyObj* p = &safe;
for (int i = 0; i < 10; ++i) {
MyObj unsafe;
if (cond) {
- p = &unsafe; // expected-warning {{may not live long enough}}
- break;
+ p = &unsafe; // expected-warning {{does not live long enough}}
+ break; // expected-note {{destroyed here}}
}
- } // expected-note {{destroyed here}}
+ }
(void)*p; // expected-note {{later used here}}
p = &safe;
for (int i = 0; i < 10; ++i) {
MyObj unsafe;
if (cond) {
- p = &unsafe; // expected-warning {{may not live long enough}}
+ p = &unsafe; // expected-warning {{does not live long enough}}
if (cond)
- break;
+ break; // expected-note {{destroyed here}}
}
- } // expected-note {{destroyed here}}
+ }
(void)*p; // expected-note {{later used here}}
p = &safe;
for (int i = 0; i < 10; ++i) {
if (cond) {
MyObj unsafe2;
- p = &unsafe2; // expected-warning {{may not live long enough}}
+ p = &unsafe2; // expected-warning {{does not live long enough}}
break; // expected-note {{destroyed here}}
}
}
+
+ // TODO: This can be argued to be a "maybe" warning. This is because
+ // we only check for confidence of liveness and not the confidence of
+ // the loan contained in an origin. To deal with this, we can introduce
+ // a confidence in loan propagation analysis as well like liveness.
+ (void)*p; // expected-note {{later used here}}
+
+ p = &safe;
+ for (int i = 0; i < 10; ++i) {
+ MyObj unsafe;
+ if (cond)
+ p = &unsafe; // expected-warning {{does not live long enough}}
+ if (cond)
+ break; // expected-note {{destroyed here}}
+ }
(void)*p; // expected-note {{later used here}}
}
@@ -298,13 +331,14 @@ void potential_switch(int mode) {
break;
}
}
- (void)*p; // expected-note {{later used here}}
+ if (mode == 2)
+ (void)*p; // expected-note {{later used here}}
}
void definite_switch(int mode) {
MyObj safe;
MyObj* p = &safe;
- // All cases are UaF --> Definite error.
+ // A use domintates all the loan expires --> all definite error.
switch (mode) {
case 1: {
MyObj temp1;
@@ -347,6 +381,21 @@ void definite_switch_gsl(int mode) {
v.use(); // expected-note 3 {{later used here}}
}
+void loan_from_previous_iteration(MyObj safe, bool condition) {
+ MyObj* p = &safe;
+ MyObj* q = &safe;
+
+ while (condition) {
+ MyObj x;
+ p = &x; // expected-warning {{may not live long enough}}
+
+ if (condition)
+ q = p;
+ (void)*p;
+ (void)*q; // expected-note {{later used here}}
+ } // expected-note {{destroyed here}}
+}
+
//===----------------------------------------------------------------------===//
// No-Error Cases
//===----------------------------------------------------------------------===//
@@ -372,6 +421,19 @@ void no_error_if_dangle_then_rescue_gsl() {
v.use(); // This is safe.
}
+void no_error_loan_from_current_iteration(bool cond) {
+ // See https://github.com/llvm/llvm-project/issues/156959.
+ MyObj b;
+ while (cond) {
+ MyObj a;
+ View p = b;
+ if (cond) {
+ p = a;
+ }
+ (void)p;
+ }
+}
+
//===----------------------------------------------------------------------===//
// Lifetimebound Attribute Tests
@@ -415,9 +477,9 @@ void lifetimebound_multiple_args_potential(bool cond) {
MyObj obj1;
if (cond) {
MyObj obj2;
- v = Choose(true,
- obj1, // expected-warning {{object whose
reference is captured may not live long enough}}
- obj2); // expected-warning {{object whose
reference is captured may not live long enough}}
+ v = Choose(true,
+ obj1, // expected-warning {{object whose
reference is captured does not live long enough}}
+ obj2); // expected-warning {{object whose
reference is captured does not live long enough}}
} // expected-note {{destroyed here}}
} // expected-note {{destroyed here}}
v.use(); // expected-note 2 {{later used here}}
@@ -488,7 +550,7 @@ void lifetimebound_partial_safety(bool cond) {
MyObj temp_obj;
v = Choose(true,
safe_obj,
- temp_obj); // expected-warning {{object whose reference is
captured may not live long enough}}
+ temp_obj); // expected-warning {{object whose reference is
captured does not live long enough}}
} // expected-note {{destroyed here}}
v.use(); // expected-note {{later used here}}
}
diff --git a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
index 3821015f07fb1..41783f7c99352 100644
--- a/clang/unittests/Analysis/LifetimeSafetyTest.cpp
+++ b/clang/unittests/Analysis/LifetimeSafetyTest.cpp
@@ -126,12 +126,12 @@ class LifetimeTestHelper {
return Analysis.getLoansAtPoint(OID, PP);
}
- std::optional<std::vector<LoanID>>
- getExpiredLoansAtPoint(llvm::StringRef Annotation) {
+ std::optional<std::vector<std::pair<OriginID, Confidence>>>
+ getLiveOriginsAtPoint(llvm::StringRef Annotation) {
ProgramPoint PP = Runner.getProgramPoint(Annotation);
if (!PP)
return std::nullopt;
- return Analysis.getExpiredLoansAtPoint(PP);
+ return Analysis.getLiveOriginsAtPoint(PP);
}
private:
@@ -180,6 +180,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.
///
@@ -221,14 +230,15 @@ MATCHER_P2(HasLoansToImpl, LoanVars, Annotation, "") {
std::sort(ExpectedLoans.begin(), ExpectedLoans.end());
std::sort(ActualLoans.begin(), ActualLoans.end());
if (ExpectedLoans != ActualLoans) {
- *result_listener << "Expected: ";
+ *result_listener << "Expected: {";
for (const auto &LoanID : ExpectedLoans) {
*result_listener << LoanID.Value << ", ";
}
- *result_listener << "Actual: ";
+ *result_listener << "} Actual: {";
for (const auto &LoanID : ActualLoans) {
*result_listener << LoanID.Value << ", ";
}
+ *result_listener << "}";
return false;
}
@@ -236,32 +246,71 @@ 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;
+enum class ConfidenceFilter { Maybe, Definite, All };
- auto ActualExpiredSetOpt = Helper.getExpiredLoansAtPoint(Annotation);
- if (!ActualExpiredSetOpt) {
- *result_listener << "could not get a valid expired loan set at point '"
+/// Matcher to verify the complete set of live origins at a program point.
+MATCHER_P2(AreLiveAtImpl, Annotation, ConfFilter, "") {
+ 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<LoanID> ActualExpiredLoans = *ActualExpiredSetOpt;
- std::vector<LoanID> ExpectedExpiredLoans;
- for (const auto &VarName : Info.LoanVars) {
- auto LoanIDs = Helper.getLoansForVar(VarName);
- if (LoanIDs.empty()) {
- *result_listener << "could not find a loan for variable '" << VarName
+ std::vector<OriginID> ActualLiveOrigins;
+ for (const auto [OID, ActualConfidence] : ActualLiveSetOpt.value()) {
+ if (ConfFilter == ConfidenceFilter::All)
+ ActualLiveOrigins.push_back(OID);
+ if (ActualConfidence == Confidence::Maybe &&
+ ConfFilter == ConfidenceFilter::Maybe)
+ ActualLiveOrigins.push_back(OID);
+ if (ActualConfidence == Confidence::Definite &&
+ ConfFilter == ConfidenceFilter::Definite)
+ ActualLiveOrigins.push_back(OID);
+ }
+
+ 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;
}
- ExpectedExpiredLoans.insert(ExpectedExpiredLoans.end(), LoanIDs.begin(),
- LoanIDs.end());
+ ExpectedLiveOrigins.push_back(*OriginIDOpt);
}
- return ExplainMatchResult(UnorderedElementsAreArray(ExpectedExpiredLoans),
- ActualExpiredLoans, result_listener);
+ std::sort(ExpectedLiveOrigins.begin(), ExpectedLiveOrigins.end());
+ std::sort(ActualLiveOrigins.begin(), ActualLiveOrigins.end());
+ if (ExpectedLiveOrigins != ActualLiveOrigins) {
+ *result_listener << "Expected: {";
+ for (const auto &OriginID : ExpectedLiveOrigins) {
+ *result_listener << OriginID.Value << ", ";
+ }
+ *result_listener << "} Actual: {";
+ for (const auto &OriginID : ActualLiveOrigins) {
+ *result_listener << OriginID.Value << ", ";
+ }
+ *result_listener << "}";
+ return false;
+ }
+ return true;
+}
+
+MATCHER_P(AreDefinitelyLiveAt, Annotation, "") {
+ return ExplainMatchResult(
+ AreLiveAtImpl(Annotation, ConfidenceFilter::Definite), arg,
+ result_listener);
+}
+
+MATCHER_P(AreMaybeLiveAt, Annotation, "") {
+ return ExplainMatchResult(AreLiveAtImpl(Annotation, ConfidenceFilter::Maybe),
+ arg, result_listener);
+}
+
+MATCHER_P(AreLiveAt, Annotation, "") {
+ return ExplainMatchResult(AreLiveAtImpl(Annotation, ConfidenceFilter::All),
+ arg, result_listener);
}
// Base test fixture to manage the runner and helper.
@@ -276,6 +325,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);
@@ -428,29 +484,6 @@ TEST_F(LifetimeAnalysisTest, AssignInSwitch) {
EXPECT_THAT(Origin("p"), HasLoansTo({"s1", "s2", "s3"}, "after_switch"));
}
-TEST_F(LifetimeAnalysisTest, LoanInLoop) {
- SetupTest(R"(
- void target(bool condition) {
- MyObj* p = nullptr;
- while (condition) {
- POINT(start_loop);
- MyObj inner;
- p = &inner;
- POINT(end_loop);
- }
- POINT(after_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) {
SetupTest(R"(
void target(int count) {
@@ -528,20 +561,16 @@ TEST_F(LifetimeAnalysisTest,
PointersAndExpirationInACycle) {
)");
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, InfiniteLoopPrunesEdges) {
@@ -585,178 +614,6 @@ 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"));
-}
-
TEST_F(LifetimeAnalysisTest, NoDuplicateLoansForImplicitCastToConst) {
SetupTest(R"(
void target() {
@@ -880,23 +737,6 @@ TEST_F(LifetimeAnalysisTest, GslPointerPropagation) {
EXPECT_THAT(Origin("z"), HasLoansTo({"a"}, "p3"));
}
-TEST_F(LifetimeAnalysisTest, GslPointerLoanExpiration) {
- SetupTest(R"(
- void target() {
- View x;
- {
- MyObj a;
- x = a;
- POINT(before_expiry);
- } // `a` is destroyed here.
- POINT(after_expiry);
- }
- )");
-
- EXPECT_THAT(NoLoans(), AreExpiredAt("before_expiry"));
- EXPECT_THAT(LoansTo({"a"}), AreExpiredAt("after_expiry"));
-}
-
TEST_F(LifetimeAnalysisTest, GslPointerReassignment) {
SetupTest(R"(
void target() {
@@ -916,7 +756,6 @@ TEST_F(LifetimeAnalysisTest, GslPointerReassignment) {
EXPECT_THAT(Origin("v"), HasLoansTo({"safe"}, "p1"));
EXPECT_THAT(Origin("v"), HasLoansTo({"unsafe"}, "p2"));
EXPECT_THAT(Origin("v"), HasLoansTo({"unsafe"}, "p3"));
- EXPECT_THAT(LoansTo({"unsafe"}), AreExpiredAt("p3"));
}
TEST_F(LifetimeAnalysisTest, GslPointerConversionOperator) {
@@ -1174,5 +1013,187 @@ 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"}), AreDefinitelyLiveAt("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"}), AreDefinitelyLiveAt("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"}), AreDefinitelyLiveAt("p2"));
+ EXPECT_THAT(Origins({"p"}), AreDefinitelyLiveAt("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"}), AreDefinitelyLiveAt("p4"));
+ EXPECT_THAT(NoOrigins(), AreMaybeLiveAt("p4"));
+
+ EXPECT_THAT(Origins({"p", "q"}), AreMaybeLiveAt("p3"));
+
+ EXPECT_THAT(Origins({"q"}), AreDefinitelyLiveAt("p2"));
+ EXPECT_THAT(NoOrigins(), AreMaybeLiveAt("p2"));
+
+ EXPECT_THAT(Origins({"p", "q"}), AreMaybeLiveAt("p1"));
+}
+
+TEST_F(LifetimeAnalysisTest, LivenessInLoopAndIf) {
+ // See https://github.com/llvm/llvm-project/issues/156959.
+ SetupTest(R"(
+ void target(bool cond) {
+ MyObj b;
+ while (cond) {
+ POINT(p1);
+
+ MyObj a;
+ View p = b;
+
+ POINT(p2);
+
+ if (cond) {
+ POINT(p3);
+ p = a;
+ }
+ POINT(p4);
+ (void)p;
+ POINT(p5);
+ }
+ }
+ )");
+ EXPECT_THAT(NoOrigins(), AreLiveAt("p5"));
+ EXPECT_THAT(Origins({"p"}), AreDefinitelyLiveAt("p4"));
+ EXPECT_THAT(NoOrigins(), AreLiveAt("p3"));
+ EXPECT_THAT(Origins({"p"}), AreMaybeLiveAt("p2"));
+ EXPECT_THAT(NoOrigins(), AreLiveAt("p1"));
+}
+
+TEST_F(LifetimeAnalysisTest, LivenessInLoopAndIf2) {
+ SetupTest(R"(
+ void target(MyObj safe, bool condition) {
+ MyObj* p = &safe;
+ MyObj* q = &safe;
+ POINT(p6);
+
+ while (condition) {
+ POINT(p5);
+ MyObj x;
+ p = &x;
+
+ POINT(p4);
+
+ if (condition) {
+ q = p;
+ POINT(p3);
+ }
+
+ POINT(p2);
+ (void)*p;
+ (void)*q;
+ POINT(p1);
+ }
+ }
+ )");
+ EXPECT_THAT(Origins({"q"}), AreMaybeLiveAt("p1"));
+ EXPECT_THAT(NoOrigins(), AreDefinitelyLiveAt("p1"));
+
+ EXPECT_THAT(Origins({"p", "q"}), AreDefinitelyLiveAt("p2"));
+
+ EXPECT_THAT(Origins({"p", "q"}), AreDefinitelyLiveAt("p3"));
+
+ EXPECT_THAT(Origins({"p"}), AreDefinitelyLiveAt("p4"));
+ EXPECT_THAT(Origins({"q"}), AreMaybeLiveAt("p4"));
+
+ EXPECT_THAT(Origins({"q"}), AreMaybeLiveAt("p5"));
+ EXPECT_THAT(NoOrigins(), AreDefinitelyLiveAt("p5"));
+
+ EXPECT_THAT(Origins({"q"}), AreMaybeLiveAt("p6"));
+ EXPECT_THAT(NoOrigins(), AreDefinitelyLiveAt("p6"));
+}
+
+TEST_F(LifetimeAnalysisTest, LivenessOutsideLoop) {
+ SetupTest(R"(
+ void target(MyObj safe) {
+ MyObj* p = &safe;
+ for (int i = 0; i < 1; ++i) {
+ MyObj s;
+ p = &s;
+ POINT(p2);
+ }
+ POINT(p1);
+ (void)*p;
+ }
+ )");
+ EXPECT_THAT(Origins({"p"}), AreDefinitelyLiveAt("p1"));
+ EXPECT_THAT(Origins({"p"}), AreMaybeLiveAt("p2"));
+}
+
} // 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
