https://github.com/usx95 updated
https://github.com/llvm/llvm-project/pull/148222
>From 927f92a13bfe02ca3e458723a0e74fe0b7f53d18 Mon Sep 17 00:00:00 2001
From: Utkarsh Saxena <u...@google.com>
Date: Fri, 11 Jul 2025 11:11:47 +0000
Subject: [PATCH 1/2] [LifetimeSafety] Add expired loans analysis
---
clang/lib/Analysis/LifetimeSafety.cpp | 363 ++++++++++++++------------
1 file changed, 203 insertions(+), 160 deletions(-)
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp
b/clang/lib/Analysis/LifetimeSafety.cpp
index bf67bea6c9933..fe6ccf2a33c49 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -496,7 +496,108 @@ class FactGenerator : public
ConstStmtVisitor<FactGenerator> {
};
// ========================================================================= //
-// The Dataflow Lattice
+// Generic Dataflow Framework
+// ========================================================================= //
+/// A generic, policy-based driver for forward dataflow analyses. It combines
+/// the dataflow runner and the transferer logic into a single class hierarchy.
+///
+/// The derived class is expected to provide:
+/// - A `Lattice` type.
+/// - `Lattice getInitialState()`
+/// - `Lattice join(Lattice, Lattice)`
+/// - `Lattice transfer(Lattice, const FactType&)` for relevant fact types.
+///
+/// \tparam Derived The CRTP derived class that implements the specific
+/// analysis.
+/// \tparam LatticeType The lattice type used by the analysis.
+template <typename Derived, typename LatticeType> class DataflowAnalysis {
+public:
+ using Lattice = LatticeType;
+
+private:
+ const CFG &Cfg;
+ AnalysisDeclContext &AC;
+
+ llvm::DenseMap<const CFGBlock *, Lattice> BlockEntryStates;
+ llvm::DenseMap<const CFGBlock *, Lattice> BlockExitStates;
+
+protected:
+ FactManager &AllFacts;
+
+ explicit DataflowAnalysis(const CFG &C, AnalysisDeclContext &AC,
+ FactManager &F)
+ : Cfg(C), AC(AC), AllFacts(F) {}
+
+public:
+ void run() {
+ Derived &d = static_cast<Derived &>(*this);
+ ForwardDataflowWorklist Worklist(Cfg, AC);
+ const CFGBlock *Entry = &Cfg.getEntry();
+ BlockEntryStates[Entry] = d.getInitialState();
+ Worklist.enqueueBlock(Entry);
+
+ while (const CFGBlock *B = Worklist.dequeue()) {
+ Lattice EntryState = getEntryState(B);
+ Lattice ExitState = transferBlock(B, EntryState);
+ BlockExitStates[B] = ExitState;
+
+ for (const CFGBlock *Successor : B->succs()) {
+ auto SuccIt = BlockEntryStates.find(Successor);
+ Lattice OldSuccEntryState = (SuccIt != BlockEntryStates.end())
+ ? SuccIt->second
+ : d.getInitialState();
+ Lattice NewSuccEntryState = d.join(OldSuccEntryState, ExitState);
+
+ if (SuccIt == BlockEntryStates.end() ||
+ NewSuccEntryState != OldSuccEntryState) {
+ BlockEntryStates[Successor] = NewSuccEntryState;
+ Worklist.enqueueBlock(Successor);
+ }
+ }
+ }
+ }
+
+ Lattice getEntryState(const CFGBlock *B) const {
+ return BlockEntryStates.lookup(B);
+ }
+
+ Lattice getExitState(const CFGBlock *B) const {
+ return BlockExitStates.lookup(B);
+ }
+
+private:
+ Lattice transferBlock(const CFGBlock *Block, Lattice EntryState) {
+ Lattice BlockState = EntryState;
+ for (const Fact *F : AllFacts.getFacts(Block)) {
+ BlockState = transferFact(BlockState, F);
+ }
+ return BlockState;
+ }
+
+ Lattice transferFact(Lattice In, const Fact *F) {
+ Derived *d = static_cast<Derived *>(this);
+ switch (F->getKind()) {
+ case Fact::Kind::Issue:
+ return d->transfer(In, *F->getAs<IssueFact>());
+ case Fact::Kind::Expire:
+ return d->transfer(In, *F->getAs<ExpireFact>());
+ case Fact::Kind::AssignOrigin:
+ return d->transfer(In, *F->getAs<AssignOriginFact>());
+ case Fact::Kind::ReturnOfOrigin:
+ return d->transfer(In, *F->getAs<ReturnOfOriginFact>());
+ }
+ llvm_unreachable("Unknown fact kind");
+ }
+
+public:
+ Lattice transfer(Lattice In, const IssueFact &) { return In; }
+ Lattice transfer(Lattice In, const ExpireFact &) { return In; }
+ Lattice transfer(Lattice In, const AssignOriginFact &) { return In; }
+ Lattice transfer(Lattice In, const ReturnOfOriginFact &) { return In; }
+};
+
+// ========================================================================= //
+// Loan Propagation Analysis
// ========================================================================= //
// Using LLVM's immutable collections is efficient for dataflow analysis
@@ -538,51 +639,6 @@ struct LifetimeLattice {
return !(*this == Other);
}
- LoanSet getLoans(OriginID OID) const {
- if (auto *Loans = Origins.lookup(OID))
- return *Loans;
- return LoanSet(nullptr);
- }
-
- /// Computes the union of two lattices by performing a key-wise join of
- /// their OriginLoanMaps.
- // 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.
- // TODO(opt): Keep the state small by removing origins which become dead.
- LifetimeLattice join(const LifetimeLattice &Other,
- LifetimeFactory &Factory) const {
- /// Merge the smaller map into the larger one ensuring we iterate over the
- /// smaller map.
- if (Origins.getHeight() < Other.Origins.getHeight())
- return Other.join(*this, Factory);
-
- OriginLoanMap JoinedState = Origins;
- // For each origin in the other map, union its loan set with ours.
- for (const auto &Entry : Other.Origins) {
- OriginID OID = Entry.first;
- LoanSet OtherLoanSet = Entry.second;
- JoinedState = Factory.OriginMapFactory.add(
- JoinedState, OID, join(getLoans(OID), OtherLoanSet, Factory));
- }
- return LifetimeLattice(JoinedState);
- }
-
- LoanSet join(LoanSet a, LoanSet b, LifetimeFactory &Factory) const {
- /// Merge the smaller set into the larger one ensuring we iterate over the
- /// smaller set.
- if (a.getHeight() < b.getHeight())
- std::swap(a, b);
- LoanSet Result = a;
- for (LoanID LID : b) {
- /// TODO(opt): Profiling shows that this loop is a major performance
- /// bottleneck. Investigate using a BitVector to represent the set of
- /// loans for improved join performance.
- Result = Factory.LoanSetFact.add(Result, LID);
- }
- return Result;
- }
-
void dump(llvm::raw_ostream &OS) const {
OS << "LifetimeLattice State:\n";
if (Origins.isEmpty())
@@ -596,144 +652,128 @@ struct LifetimeLattice {
}
};
-// ========================================================================= //
-// The Transfer Function
-// ========================================================================= //
-class Transferer {
- FactManager &AllFacts;
+class LoanPropagationAnalysis
+ : public DataflowAnalysis<LoanPropagationAnalysis, LifetimeLattice> {
+
LifetimeFactory &Factory;
public:
- explicit Transferer(FactManager &F, LifetimeFactory &Factory)
- : AllFacts(F), Factory(Factory) {}
-
- /// Computes the exit state of a block by applying all its facts sequentially
- /// to a given entry state.
- /// TODO: We might need to store intermediate states per-fact in the block
for
- /// later analysis.
- LifetimeLattice transferBlock(const CFGBlock *Block,
- LifetimeLattice EntryState) {
- LifetimeLattice BlockState = EntryState;
- llvm::ArrayRef<const Fact *> Facts = AllFacts.getFacts(Block);
-
- for (const Fact *F : Facts) {
- BlockState = transferFact(BlockState, F);
+ LoanPropagationAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager
&F,
+ LifetimeFactory &Factory)
+ : DataflowAnalysis(C, AC, F), Factory(Factory) {}
+
+ // Make the base class's transfer overloads visible.
+ using DataflowAnalysis<LoanPropagationAnalysis, Lattice>::transfer;
+
+ Lattice getInitialState() { return Lattice{}; }
+
+ Lattice join(Lattice L1, Lattice L2) {
+ /// Merge the smaller map into the larger one ensuring we iterate over the
+ /// smaller map.
+ if (L1.Origins.getHeight() < L2.Origins.getHeight())
+ std::swap(L1, L2);
+
+ OriginLoanMap JoinedState = L1.Origins;
+ // For each origin in the other map, union its loan set with ours.
+ for (const auto &Entry : L2.Origins) {
+ OriginID OID = Entry.first;
+ LoanSet OtherLoanSet = Entry.second;
+ JoinedState = Factory.OriginMapFactory.add(
+ JoinedState, OID, join(getLoans(L1, OID), OtherLoanSet));
}
- return BlockState;
+ return Lattice(JoinedState);
}
-private:
- LifetimeLattice transferFact(LifetimeLattice In, const Fact *F) {
- switch (F->getKind()) {
- case Fact::Kind::Issue:
- return transfer(In, *F->getAs<IssueFact>());
- case Fact::Kind::AssignOrigin:
- return transfer(In, *F->getAs<AssignOriginFact>());
- // Expire and ReturnOfOrigin facts don't modify the Origins and the State.
- case Fact::Kind::Expire:
- case Fact::Kind::ReturnOfOrigin:
- return In;
- }
- llvm_unreachable("Unknown fact kind");
+ LoanSet join(LoanSet S1, LoanSet S2) {
+ if (S1.getHeight() < S2.getHeight())
+ std::swap(S1, S2);
+ for (LoanID L : S2)
+ S1 = Factory.LoanSetFact.add(S1, L);
+ return S1;
}
- /// A new loan is issued to the origin. Old loans are erased.
- LifetimeLattice transfer(LifetimeLattice In, const IssueFact &F) {
+ // Overloads for specific fact types this transferer cares about.
+ Lattice transfer(Lattice In, const IssueFact &F) {
OriginID OID = F.getOriginID();
LoanID LID = F.getLoanID();
return LifetimeLattice(Factory.OriginMapFactory.add(
In.Origins, OID, Factory.createLoanSet(LID)));
}
- /// The destination origin's loan set is replaced by the source's.
- /// This implicitly "resets" the old loans of the destination.
- LifetimeLattice transfer(LifetimeLattice InState, const AssignOriginFact &F)
{
+ Lattice transfer(Lattice In, const AssignOriginFact &F) {
OriginID DestOID = F.getDestOriginID();
OriginID SrcOID = F.getSrcOriginID();
- LoanSet SrcLoans = InState.getLoans(SrcOID);
+ LoanSet SrcLoans = getLoans(In, SrcOID);
return LifetimeLattice(
- Factory.OriginMapFactory.add(InState.Origins, DestOID, SrcLoans));
+ Factory.OriginMapFactory.add(In.Origins, DestOID, SrcLoans));
+ }
+
+private:
+ LoanSet getLoans(Lattice L, OriginID OID) {
+ if (auto *Loans = L.Origins.lookup(OID))
+ return *Loans;
+ return Factory.LoanSetFact.getEmptySet();
}
};
// ========================================================================= //
-// Dataflow analysis
+// Expired Loans Analysis
// ========================================================================= //
-/// Drives the intra-procedural dataflow analysis.
-///
-/// Orchestrates the analysis by iterating over the CFG using a worklist
-/// algorithm. It computes a fixed point by propagating the LifetimeLattice
-/// state through each block until the state no longer changes.
-/// TODO: Maybe use the dataflow framework! The framework might need changes
-/// to support the current comparison done at block-entry.
-class LifetimeDataflow {
- const CFG &Cfg;
- AnalysisDeclContext &AC;
- LifetimeFactory LifetimeFact;
+/// The lattice for tracking expired loans. It is a set of loan IDs.
+struct ExpiredLattice {
+ LoanSet Expired;
+
+ ExpiredLattice() : Expired(nullptr) {};
+ explicit ExpiredLattice(LoanSet S) : Expired(S) {}
+
+ bool operator==(const ExpiredLattice &Other) const {
+ return Expired == Other.Expired;
+ }
+ bool operator!=(const ExpiredLattice &Other) const {
+ return !(*this == Other);
+ }
+
+ void dump(llvm::raw_ostream &OS) const {
+ OS << "ExpiredLattice State:\n";
+ if (Expired.isEmpty())
+ OS << " <empty>\n";
+ for (const LoanID &LID : Expired)
+ OS << " Loan " << LID << " is expired\n";
+ }
+};
- Transferer Xfer;
+/// Transfer function for the expired loans analysis.
+class ExpiredLoansAnalysis
+ : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice> {
- /// Stores the merged analysis state at the entry of each CFG block.
- llvm::DenseMap<const CFGBlock *, LifetimeLattice> BlockEntryStates;
- /// Stores the analysis state at the exit of each CFG block, after the
- /// transfer function has been applied.
- llvm::DenseMap<const CFGBlock *, LifetimeLattice> BlockExitStates;
+ LoanSet::Factory &SetFactory;
public:
- LifetimeDataflow(const CFG &C, FactManager &FS, AnalysisDeclContext &AC)
- : Cfg(C), AC(AC), Xfer(FS, LifetimeFact) {}
+ ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
+ LoanSet::Factory &SF)
+ : DataflowAnalysis(C, AC, F), SetFactory(SF) {}
- void run() {
- llvm::TimeTraceScope TimeProfile("Lifetime Dataflow");
- ForwardDataflowWorklist Worklist(Cfg, AC);
- const CFGBlock *Entry = &Cfg.getEntry();
- BlockEntryStates[Entry] = LifetimeLattice{};
- Worklist.enqueueBlock(Entry);
- while (const CFGBlock *B = Worklist.dequeue()) {
- LifetimeLattice EntryState = getEntryState(B);
- LifetimeLattice ExitState = Xfer.transferBlock(B, EntryState);
- BlockExitStates[B] = ExitState;
+ using DataflowAnalysis<ExpiredLoansAnalysis, Lattice>::transfer;
- for (const CFGBlock *Successor : B->succs()) {
- auto SuccIt = BlockEntryStates.find(Successor);
- LifetimeLattice OldSuccEntryState = (SuccIt != BlockEntryStates.end())
- ? SuccIt->second
- : LifetimeLattice{};
- LifetimeLattice NewSuccEntryState =
- OldSuccEntryState.join(ExitState, LifetimeFact);
- // Enqueue the successor if its entry state has changed.
- // TODO(opt): Consider changing 'join' to report a change if !=
- // comparison is found expensive.
- if (SuccIt == BlockEntryStates.end() ||
- NewSuccEntryState != OldSuccEntryState) {
- BlockEntryStates[Successor] = NewSuccEntryState;
- Worklist.enqueueBlock(Successor);
- }
- }
- }
- }
+ Lattice getInitialState() { return Lattice(SetFactory.getEmptySet()); }
- void dump() const {
- llvm::dbgs() << "==========================================\n";
- llvm::dbgs() << " Dataflow results:\n";
- llvm::dbgs() << "==========================================\n";
- const CFGBlock &B = Cfg.getExit();
- getExitState(&B).dump(llvm::dbgs());
+ Lattice join(Lattice L1, Lattice L2) const {
+ LoanSet JoinedSet = L1.Expired;
+ for (LoanID LID : L2.Expired)
+ JoinedSet = SetFactory.add(JoinedSet, LID);
+ return Lattice(JoinedSet);
}
- LifetimeLattice getEntryState(const CFGBlock *B) const {
- return BlockEntryStates.lookup(B);
+ // Overloads for specific fact types this transferer cares about.
+ Lattice transfer(Lattice In, const ExpireFact &F) {
+ return Lattice(SetFactory.add(In.Expired, F.getLoanID()));
}
- LifetimeLattice getExitState(const CFGBlock *B) const {
- return BlockExitStates.lookup(B);
+ Lattice transfer(Lattice In, const IssueFact &F) {
+ return Lattice(SetFactory.remove(In.Expired, F.getLoanID()));
}
};
-
-// ========================================================================= //
-// TODO: Analysing dataflow results and error reporting.
-// ========================================================================= //
} // anonymous namespace
void runLifetimeSafetyAnalysis(const DeclContext &DC, const CFG &Cfg,
@@ -746,17 +786,20 @@ void runLifetimeSafetyAnalysis(const DeclContext &DC,
const CFG &Cfg,
FactGen.run();
DEBUG_WITH_TYPE("LifetimeFacts", FactMgr.dump(Cfg, AC));
- /// TODO(opt): Consider optimizing individual blocks before running the
- /// dataflow analysis.
- /// 1. Expression Origins: These are assigned once and read at most once,
- /// forming simple chains. These chains can be compressed into a single
- /// assignment.
- /// 2. Block-Local Loans: Origins of expressions are never read by other
- /// blocks; only Decls are visible. Therefore, loans in a block that
- /// never reach an Origin associated with a Decl can be safely dropped by
- /// the analysis.
- LifetimeDataflow Dataflow(Cfg, FactMgr, AC);
- Dataflow.run();
- DEBUG_WITH_TYPE("LifetimeDataflow", Dataflow.dump());
+ // Run Loan Propagation Analysis
+ LifetimeFactory LifetimeFact;
+ LoanPropagationAnalysis LoanPropagation(Cfg, AC, FactMgr, LifetimeFact);
+ LoanPropagation.run();
+ DEBUG_WITH_TYPE(
+ "LifetimeDataflow",
+ LoanPropagation.getExitState(&Cfg.getExit()).dump(llvm::dbgs()));
+
+ // Run Expired Loans Analysis
+ ExpiredLoansAnalysis ExpiredAnalysis(Cfg, AC, FactMgr,
+ LifetimeFact.LoanSetFact);
+ ExpiredAnalysis.run();
+ DEBUG_WITH_TYPE(
+ "ExpiredLoans",
+ ExpiredAnalysis.getExitState(&Cfg.getExit()).dump(llvm::dbgs()));
}
} // namespace clang
>From 702d2559f7f7fafbbc4deefe86d8cea2b9460fea Mon Sep 17 00:00:00 2001
From: Utkarsh Saxena <u...@google.com>
Date: Mon, 14 Jul 2025 18:51:17 +0000
Subject: [PATCH 2/2] bring back comments
---
clang/lib/Analysis/LifetimeSafety.cpp | 179 ++++++++----------
.../Sema/warn-lifetime-safety-dataflow.cpp | 30 +--
2 files changed, 93 insertions(+), 116 deletions(-)
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp
b/clang/lib/Analysis/LifetimeSafety.cpp
index fe6ccf2a33c49..c1bd4e82f4327 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -503,13 +503,18 @@ class FactGenerator : public
ConstStmtVisitor<FactGenerator> {
///
/// The derived class is expected to provide:
/// - A `Lattice` type.
-/// - `Lattice getInitialState()`
-/// - `Lattice join(Lattice, Lattice)`
-/// - `Lattice transfer(Lattice, const FactType&)` for relevant fact types.
+/// - `const char *getAnalysisName() const`
+/// - `Lattice getInitialState();` The initial state at the function entry.
+/// - `Lattice join(Lattice, Lattice);` Merges states from multiple CFG paths.
+/// - `Lattice transfer(Lattice, const FactType&);` Defines how a single
+/// lifetime-relevant `Fact` transforms the lattice state. Only overloads
+/// for facts relevant to the analysis need to be implemented.
///
/// \tparam Derived The CRTP derived class that implements the specific
/// analysis.
/// \tparam LatticeType The lattice type used by the analysis.
+/// TODO: Maybe use the dataflow framework! The framework might need changes
+/// to support the current comparison done at block-entry.
template <typename Derived, typename LatticeType> class DataflowAnalysis {
public:
using Lattice = LatticeType;
@@ -530,10 +535,12 @@ template <typename Derived, typename LatticeType> class
DataflowAnalysis {
public:
void run() {
- Derived &d = static_cast<Derived &>(*this);
+ Derived &D = static_cast<Derived &>(*this);
+ llvm::TimeTraceScope Time(D.getAnalysisName());
+
ForwardDataflowWorklist Worklist(Cfg, AC);
const CFGBlock *Entry = &Cfg.getEntry();
- BlockEntryStates[Entry] = d.getInitialState();
+ BlockEntryStates[Entry] = D.getInitialState();
Worklist.enqueueBlock(Entry);
while (const CFGBlock *B = Worklist.dequeue()) {
@@ -545,9 +552,11 @@ template <typename Derived, typename LatticeType> class
DataflowAnalysis {
auto SuccIt = BlockEntryStates.find(Successor);
Lattice OldSuccEntryState = (SuccIt != BlockEntryStates.end())
? SuccIt->second
- : d.getInitialState();
- Lattice NewSuccEntryState = d.join(OldSuccEntryState, ExitState);
-
+ : D.getInitialState();
+ Lattice NewSuccEntryState = D.join(OldSuccEntryState, ExitState);
+ // Enqueue the successor if its entry state has changed.
+ // TODO(opt): Consider changing 'join' to report a change if !=
+ // comparison is found expensive.
if (SuccIt == BlockEntryStates.end() ||
NewSuccEntryState != OldSuccEntryState) {
BlockEntryStates[Successor] = NewSuccEntryState;
@@ -565,7 +574,20 @@ template <typename Derived, typename LatticeType> class
DataflowAnalysis {
return BlockExitStates.lookup(B);
}
+ void dump() const {
+ const Derived *D = static_cast<const Derived *>(this);
+ llvm::dbgs() << "==========================================\n";
+ llvm::dbgs() << " " << D->getAnalysisName() << " results:\n";
+ llvm::dbgs() << "==========================================\n";
+ const CFGBlock &B = Cfg.getExit();
+ getExitState(&B).dump(llvm::dbgs());
+ }
+
private:
+ /// Computes the exit state of a block by applying all its facts sequentially
+ /// to a given entry state.
+ /// TODO: We might need to store intermediate states per-fact in the block
for
+ /// later analysis.
Lattice transferBlock(const CFGBlock *Block, Lattice EntryState) {
Lattice BlockState = EntryState;
for (const Fact *F : AllFacts.getFacts(Block)) {
@@ -618,10 +640,10 @@ struct LifetimeFactory {
}
};
-/// LifetimeLattice represents the state of our analysis at a given program
-/// point. It is an immutable object, and all operations produce a new
+/// LoanPropagationLattice represents the state of our analysis at a given
+/// program point. It is an immutable object, and all operations produce a new
/// instance rather than modifying the existing one.
-struct LifetimeLattice {
+struct LoanPropagationLattice {
/// The map from an origin to the set of loans it contains.
/// The lattice has a finite height: An origin's loan set is bounded by the
/// total number of loans in the function.
@@ -629,13 +651,13 @@ struct LifetimeLattice {
/// not expressions, because expressions are not visible across blocks.
OriginLoanMap Origins = OriginLoanMap(nullptr);
- explicit LifetimeLattice(const OriginLoanMap &S) : Origins(S) {}
- LifetimeLattice() = default;
+ explicit LoanPropagationLattice(const OriginLoanMap &S) : Origins(S) {}
+ LoanPropagationLattice() = default;
- bool operator==(const LifetimeLattice &Other) const {
+ bool operator==(const LoanPropagationLattice &Other) const {
return Origins == Other.Origins;
}
- bool operator!=(const LifetimeLattice &Other) const {
+ bool operator!=(const LoanPropagationLattice &Other) const {
return !(*this == Other);
}
@@ -653,7 +675,7 @@ struct LifetimeLattice {
};
class LoanPropagationAnalysis
- : public DataflowAnalysis<LoanPropagationAnalysis, LifetimeLattice> {
+ : public DataflowAnalysis<LoanPropagationAnalysis, LoanPropagationLattice>
{
LifetimeFactory &Factory;
@@ -662,49 +684,58 @@ class LoanPropagationAnalysis
LifetimeFactory &Factory)
: DataflowAnalysis(C, AC, F), Factory(Factory) {}
- // Make the base class's transfer overloads visible.
using DataflowAnalysis<LoanPropagationAnalysis, Lattice>::transfer;
+ const char *getAnalysisName() const { return "LoanPropagation"; }
+
Lattice getInitialState() { return Lattice{}; }
- Lattice join(Lattice L1, Lattice L2) {
+ /// Computes the union of two lattices by performing a key-wise join of
+ /// their OriginLoanMaps.
+ // 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.
+ // TODO(opt): Keep the state small by removing origins which become dead.
+ Lattice join(Lattice A, Lattice B) {
/// Merge the smaller map into the larger one ensuring we iterate over the
/// smaller map.
- if (L1.Origins.getHeight() < L2.Origins.getHeight())
- std::swap(L1, L2);
+ if (A.Origins.getHeight() < B.Origins.getHeight())
+ std::swap(A, B);
- OriginLoanMap JoinedState = L1.Origins;
+ OriginLoanMap JoinedState = A.Origins;
// For each origin in the other map, union its loan set with ours.
- for (const auto &Entry : L2.Origins) {
+ for (const auto &Entry : B.Origins) {
OriginID OID = Entry.first;
LoanSet OtherLoanSet = Entry.second;
JoinedState = Factory.OriginMapFactory.add(
- JoinedState, OID, join(getLoans(L1, OID), OtherLoanSet));
+ JoinedState, OID, join(getLoans(A, OID), OtherLoanSet));
}
return Lattice(JoinedState);
}
- LoanSet join(LoanSet S1, LoanSet S2) {
- if (S1.getHeight() < S2.getHeight())
- std::swap(S1, S2);
- for (LoanID L : S2)
- S1 = Factory.LoanSetFact.add(S1, L);
- return S1;
+ LoanSet join(LoanSet A, LoanSet B) {
+ if (A.getHeight() < B.getHeight())
+ std::swap(A, B);
+ for (LoanID L : B)
+ A = Factory.LoanSetFact.add(A, L);
+ return A;
}
- // Overloads for specific fact types this transferer cares about.
+ /// A new loan is issued to the origin. Old loans are erased.
Lattice transfer(Lattice In, const IssueFact &F) {
OriginID OID = F.getOriginID();
LoanID LID = F.getLoanID();
- return LifetimeLattice(Factory.OriginMapFactory.add(
+ return LoanPropagationLattice(Factory.OriginMapFactory.add(
In.Origins, OID, Factory.createLoanSet(LID)));
}
+ /// The destination origin's loan set is replaced by the source's.
+ /// This implicitly "resets" the old loans of the destination.
Lattice transfer(Lattice In, const AssignOriginFact &F) {
OriginID DestOID = F.getDestOriginID();
OriginID SrcOID = F.getSrcOriginID();
LoanSet SrcLoans = getLoans(In, SrcOID);
- return LifetimeLattice(
+ return LoanPropagationLattice(
Factory.OriginMapFactory.add(In.Origins, DestOID, SrcLoans));
}
@@ -715,65 +746,13 @@ class LoanPropagationAnalysis
return Factory.LoanSetFact.getEmptySet();
}
};
-
// ========================================================================= //
-// Expired Loans Analysis
+// TODO:
+// - Modifying loan propagation to answer `LoanSet getLoans(Origin O, Point P)`
+// - Adding loan expiry analysis to answer `bool isExpired(Loan L, Point P)`
+// - Adding origin liveness analysis to answer `bool isLive(Origin O, Point P)`
+// - Using the above three to perform the final error reporting.
// ========================================================================= //
-
-/// The lattice for tracking expired loans. It is a set of loan IDs.
-struct ExpiredLattice {
- LoanSet Expired;
-
- ExpiredLattice() : Expired(nullptr) {};
- explicit ExpiredLattice(LoanSet S) : Expired(S) {}
-
- bool operator==(const ExpiredLattice &Other) const {
- return Expired == Other.Expired;
- }
- bool operator!=(const ExpiredLattice &Other) const {
- return !(*this == Other);
- }
-
- void dump(llvm::raw_ostream &OS) const {
- OS << "ExpiredLattice State:\n";
- if (Expired.isEmpty())
- OS << " <empty>\n";
- for (const LoanID &LID : Expired)
- OS << " Loan " << LID << " is expired\n";
- }
-};
-
-/// Transfer function for the expired loans analysis.
-class ExpiredLoansAnalysis
- : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice> {
-
- LoanSet::Factory &SetFactory;
-
-public:
- ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
- LoanSet::Factory &SF)
- : DataflowAnalysis(C, AC, F), SetFactory(SF) {}
-
- using DataflowAnalysis<ExpiredLoansAnalysis, Lattice>::transfer;
-
- Lattice getInitialState() { return Lattice(SetFactory.getEmptySet()); }
-
- Lattice join(Lattice L1, Lattice L2) const {
- LoanSet JoinedSet = L1.Expired;
- for (LoanID LID : L2.Expired)
- JoinedSet = SetFactory.add(JoinedSet, LID);
- return Lattice(JoinedSet);
- }
-
- // Overloads for specific fact types this transferer cares about.
- Lattice transfer(Lattice In, const ExpireFact &F) {
- return Lattice(SetFactory.add(In.Expired, F.getLoanID()));
- }
-
- Lattice transfer(Lattice In, const IssueFact &F) {
- return Lattice(SetFactory.remove(In.Expired, F.getLoanID()));
- }
-};
} // anonymous namespace
void runLifetimeSafetyAnalysis(const DeclContext &DC, const CFG &Cfg,
@@ -786,20 +765,18 @@ void runLifetimeSafetyAnalysis(const DeclContext &DC,
const CFG &Cfg,
FactGen.run();
DEBUG_WITH_TYPE("LifetimeFacts", FactMgr.dump(Cfg, AC));
- // Run Loan Propagation Analysis
+ /// TODO(opt): Consider optimizing individual blocks before running the
+ /// dataflow analysis.
+ /// 1. Expression Origins: These are assigned once and read at most once,
+ /// forming simple chains. These chains can be compressed into a single
+ /// assignment.
+ /// 2. Block-Local Loans: Origins of expressions are never read by other
+ /// blocks; only Decls are visible. Therefore, loans in a block that
+ /// never reach an Origin associated with a Decl can be safely dropped by
+ /// the analysis.
LifetimeFactory LifetimeFact;
LoanPropagationAnalysis LoanPropagation(Cfg, AC, FactMgr, LifetimeFact);
LoanPropagation.run();
- DEBUG_WITH_TYPE(
- "LifetimeDataflow",
- LoanPropagation.getExitState(&Cfg.getExit()).dump(llvm::dbgs()));
-
- // Run Expired Loans Analysis
- ExpiredLoansAnalysis ExpiredAnalysis(Cfg, AC, FactMgr,
- LifetimeFact.LoanSetFact);
- ExpiredAnalysis.run();
- DEBUG_WITH_TYPE(
- "ExpiredLoans",
- ExpiredAnalysis.getExitState(&Cfg.getExit()).dump(llvm::dbgs()));
+ DEBUG_WITH_TYPE("LifetimeLoanPropagation", LoanPropagation.dump());
}
} // namespace clang
diff --git a/clang/test/Sema/warn-lifetime-safety-dataflow.cpp
b/clang/test/Sema/warn-lifetime-safety-dataflow.cpp
index 38dfdb98f08fc..0e98904ade86a 100644
--- a/clang/test/Sema/warn-lifetime-safety-dataflow.cpp
+++ b/clang/test/Sema/warn-lifetime-safety-dataflow.cpp
@@ -1,4 +1,4 @@
-// RUN: %clang_cc1 -mllvm -debug-only=LifetimeFacts,LifetimeDataflow
-Wexperimental-lifetime-safety %s 2>&1 | FileCheck %s
+// RUN: %clang_cc1 -mllvm -debug-only=LifetimeFacts,LifetimeLoanPropagation
-Wexperimental-lifetime-safety %s 2>&1 | FileCheck %s
// REQUIRES: asserts
struct MyObj {
@@ -19,7 +19,7 @@ MyObj* return_local_addr() {
// CHECK: ReturnOfOrigin (OriginID: [[O_RET_VAL]])
// CHECK: Expire (LoanID: [[L_X]])
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_ADDR_X]] contains Loan [[L_X]]
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_X]]
// CHECK-DAG: Origin [[O_RET_VAL]] contains Loan [[L_X]]
@@ -47,7 +47,7 @@ MyObj* assign_and_return_local_addr() {
// CHECK: ReturnOfOrigin (OriginID: [[O_PTR2_RVAL_2]])
// CHECK: Expire (LoanID: [[L_Y]])
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_ADDR_Y]] contains Loan [[L_Y]]
// CHECK-DAG: Origin [[O_PTR1]] contains Loan [[L_Y]]
// CHECK-DAG: Origin [[O_PTR2]] contains Loan [[L_Y]]
@@ -65,7 +65,7 @@ int return_int_val() {
return x;
}
// CHECK-NEXT: End of Block
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK: <empty>
@@ -79,7 +79,7 @@ void loan_expires_cpp() {
// CHECK: AssignOrigin (DestID: [[O_POBJ:[0-9]+]], SrcID: [[O_ADDR_OBJ]])
// CHECK: Expire (LoanID: [[L_OBJ]])
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_ADDR_OBJ]] contains Loan [[L_OBJ]]
// CHECK-DAG: Origin [[O_POBJ]] contains Loan [[L_OBJ]]
@@ -96,7 +96,7 @@ void loan_expires_trivial() {
// CHECK-NEXT: End of Block
// FIXME: Add check for Expire once trivial destructors are handled for
expiration.
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_ADDR_TRIVIAL_OBJ]] contains Loan [[L_TRIVIAL_OBJ]]
// CHECK-DAG: Origin [[O_PTOBJ]] contains Loan [[L_TRIVIAL_OBJ]]
@@ -119,7 +119,7 @@ void conditional(bool condition) {
// CHECK: AssignOrigin (DestID: [[O_P_RVAL:[0-9]+]], SrcID: [[O_P]])
// CHECK: AssignOrigin (DestID: [[O_Q:[0-9]+]], SrcID: [[O_P_RVAL]])
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_ADDR_A]] contains Loan [[L_A]]
// CHECK-DAG: Origin [[O_ADDR_B]] contains Loan [[L_B]]
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_A]]
@@ -163,7 +163,7 @@ void pointers_in_a_cycle(bool condition) {
}
// At the end of the analysis, the origins for the pointers involved in the
cycle
// (p1, p2, p3, temp) should all contain the loans from v1, v2, and v3 at the
fixed point.
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_P1]] contains Loan [[L_V1]]
// CHECK-DAG: Origin [[O_P1]] contains Loan [[L_V2]]
// CHECK-DAG: Origin [[O_P1]] contains Loan [[L_V3]]
@@ -195,7 +195,7 @@ void overwrite_origin() {
// CHECK: Expire (LoanID: [[L_S2]])
// CHECK: Expire (LoanID: [[L_S1]])
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK: Origin [[O_P]] contains Loan [[L_S2]]
// CHECK-NOT: Origin [[O_P]] contains Loan [[L_S1]]
@@ -213,7 +213,7 @@ void reassign_to_null() {
}
// FIXME: Have a better representation for nullptr than just an empty origin.
// It should be a separate loan and origin kind.
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK: Origin [[O_P]] contains no loans
@@ -235,7 +235,7 @@ void reassign_in_if(bool condition) {
// CHECK: Expire (LoanID: [[L_S2]])
// CHECK: Expire (LoanID: [[L_S1]])
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_S1]]
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_S2]]
// CHECK-DAG: Origin [[O_ADDR_S1]] contains Loan [[L_S1]]
@@ -276,7 +276,7 @@ void assign_in_switch(int mode) {
// CHECK-DAG: Expire (LoanID: [[L_S2]])
// CHECK-DAG: Expire (LoanID: [[L_S1]])
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_S1]]
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_S2]]
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_S3]]
@@ -299,7 +299,7 @@ void loan_in_loop(bool condition) {
// CHECK: Expire (LoanID: [[L_INNER]])
}
}
-// CHECK: Dataflow results:
+// CHECK: LoanPropagation results:
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_INNER]]
// CHECK-DAG: Origin [[O_ADDR_INNER]] contains Loan [[L_INNER]]
@@ -326,7 +326,7 @@ void loop_with_break(int count) {
// CHECK: Expire (LoanID: [[L_S1]])
}
-// CHECK-LABEL: Dataflow results:
+// CHECK-LABEL: LoanPropagation results:
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_S1]]
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_S2]]
// CHECK-DAG: Origin [[O_ADDR_S1]] contains Loan [[L_S1]]
@@ -355,7 +355,7 @@ void nested_scopes() {
// CHECK: Expire (LoanID: [[L_OUTER]])
}
-// CHECK-LABEL: Dataflow results:
+// CHECK-LABEL: LoanPropagation results:
// CHECK-DAG: Origin [[O_P]] contains Loan [[L_INNER]]
// CHECK-DAG: Origin [[O_ADDR_INNER]] contains Loan [[L_INNER]]
// CHECK-DAG: Origin [[O_ADDR_OUTER]] contains Loan [[L_OUTER]]
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
