https://github.com/usx95 updated
https://github.com/llvm/llvm-project/pull/148222
>From eb33d75e1ad1faf621f90d0b8f6ac3deab267084 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/3] [LifetimeSafety] Add expired loans analysis
---
clang/lib/Analysis/LifetimeSafety.cpp | 140 ++++++++++++++++++++++++++
1 file changed, 140 insertions(+)
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp
b/clang/lib/Analysis/LifetimeSafety.cpp
index 20f3285249ac2..a6de79cffb371 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -729,6 +729,142 @@ class LifetimeDataflow {
}
};
+// ========================================================================= //
+// Expired Loans Analysis
+// ========================================================================= //
+
+/// The lattice for tracking expired loans. It is a set of loan IDs.
+struct ExpiredLattice {
+ LoanSet Expired;
+
+ ExpiredLattice() = default;
+ 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);
+ }
+
+ /// Computes the union of two lattices.
+ ExpiredLattice join(const ExpiredLattice &Other,
+ LoanSet::Factory &Factory) const {
+ LoanSet JoinedSet = Expired;
+ for (LoanID LID : Other.Expired)
+ JoinedSet = Factory.add(JoinedSet, LID);
+ return ExpiredLattice(JoinedSet);
+ }
+
+ 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 ExpiredLoansTransferer {
+ FactManager &AllFacts;
+ LoanSet::Factory &SetFactory;
+
+public:
+ explicit ExpiredLoansTransferer(FactManager &F, LoanSet::Factory &SF)
+ : AllFacts(F), SetFactory(SF) {}
+
+ /// Computes the exit state of a block by applying all its facts sequentially
+ /// to a given entry state.
+ ExpiredLattice transferBlock(const CFGBlock *Block,
+ ExpiredLattice EntryState) {
+ ExpiredLattice BlockState = EntryState;
+ llvm::ArrayRef<const Fact *> Facts = AllFacts.getFacts(Block);
+
+ for (const Fact *F : Facts) {
+ BlockState = transferFact(BlockState, F);
+ }
+ return BlockState;
+ }
+
+private:
+ ExpiredLattice transferFact(ExpiredLattice In, const Fact *F) {
+ if (const auto *EF = F->getAs<ExpireFact>())
+ return ExpiredLattice(SetFactory.add(In.Expired, EF->getLoanID()));
+
+ if (const auto *IF = F->getAs<IssueFact>())
+ return ExpiredLattice(SetFactory.remove(In.Expired, IF->getLoanID()));
+
+ return In;
+ }
+};
+
+/// Dataflow analysis driver for tracking expired loans.
+class ExpiredLoansAnalysis {
+ const CFG &Cfg;
+ AnalysisDeclContext &AC;
+ LoanSet::Factory SetFactory;
+ ExpiredLoansTransferer Xfer;
+
+ llvm::DenseMap<const CFGBlock *, ExpiredLattice> BlockEntryStates;
+ llvm::DenseMap<const CFGBlock *, ExpiredLattice> BlockExitStates;
+
+public:
+ ExpiredLoansAnalysis(const CFG &C, FactManager &FS, AnalysisDeclContext &AC)
+ : Cfg(C), AC(AC), Xfer(FS, SetFactory) {}
+
+ void run() {
+ llvm::TimeTraceScope TimeProfile("Expired Loans Analysis");
+ ForwardDataflowWorklist Worklist(Cfg, AC);
+ const CFGBlock *Entry = &Cfg.getEntry();
+ BlockEntryStates[Entry] = ExpiredLattice(SetFactory.getEmptySet());
+ Worklist.enqueueBlock(Entry);
+ while (const CFGBlock *B = Worklist.dequeue()) {
+ ExpiredLattice EntryState = getEntryState(B);
+ ExpiredLattice ExitState = Xfer.transferBlock(B, EntryState);
+ BlockExitStates[B] = ExitState;
+
+ for (const CFGBlock *Successor : B->succs()) {
+ auto SuccIt = BlockEntryStates.find(Successor);
+ ExpiredLattice OldSuccEntryState = (SuccIt != BlockEntryStates.end())
+ ? SuccIt->second
+ : ExpiredLattice{};
+ ExpiredLattice NewSuccEntryState =
+ OldSuccEntryState.join(ExitState, SetFactory);
+ if (SuccIt == BlockEntryStates.end() ||
+ NewSuccEntryState != OldSuccEntryState) {
+ BlockEntryStates[Successor] = NewSuccEntryState;
+ Worklist.enqueueBlock(Successor);
+ }
+ }
+ }
+ }
+
+ void dump() const {
+ llvm::dbgs() << "==========================================\n";
+ llvm::dbgs() << " Expired Loans Results:\n";
+ llvm::dbgs() << "==========================================\n";
+ const CFGBlock &B = Cfg.getExit();
+ getExitState(&B).dump(llvm::dbgs());
+ }
+
+ ExpiredLattice getEntryState(const CFGBlock *B) const {
+ auto It = BlockEntryStates.find(B);
+ if (It != BlockEntryStates.end()) {
+ return It->second;
+ }
+ return ExpiredLattice(SetFactory.getEmptySet());
+ }
+
+ ExpiredLattice getExitState(const CFGBlock *B) const {
+ auto It = BlockExitStates.find(B);
+ if (It != BlockExitStates.end()) {
+ return It->second;
+ }
+ return ExpiredLattice(SetFactory.getEmptySet());
+ }
+};
+
// ========================================================================= //
// TODO: Analysing dataflow results and error reporting.
// ========================================================================= //
@@ -756,5 +892,9 @@ void runLifetimeSafetyAnalysis(const DeclContext &DC, const
CFG &Cfg,
LifetimeDataflow Dataflow(Cfg, FactMgr, AC);
Dataflow.run();
DEBUG_WITH_TYPE("LifetimeDataflow", Dataflow.dump());
+
+ ExpiredLoansAnalysis ExpiredAnalysis(Cfg, FactMgr, AC);
+ ExpiredAnalysis.run();
+ DEBUG_WITH_TYPE("ExpiredLoans", ExpiredAnalysis.dump());
}
} // namespace clang
>From 47425603375f6fd568da7cec2dbc7073406dbbed Mon Sep 17 00:00:00 2001
From: Utkarsh Saxena <u...@google.com>
Date: Mon, 14 Jul 2025 15:50:10 +0000
Subject: [PATCH 2/3] make the dataflow algorithm generic to avoid duplication
---
clang/lib/Analysis/LifetimeSafety.cpp | 22 +++++++---------------
1 file changed, 7 insertions(+), 15 deletions(-)
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp
b/clang/lib/Analysis/LifetimeSafety.cpp
index a6de79cffb371..cdb3e5e47c90f 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -737,7 +737,7 @@ class LifetimeDataflow {
struct ExpiredLattice {
LoanSet Expired;
- ExpiredLattice() = default;
+ ExpiredLattice() : Expired(nullptr) {};
explicit ExpiredLattice(LoanSet S) : Expired(S) {}
bool operator==(const ExpiredLattice &Other) const {
@@ -814,10 +814,10 @@ class ExpiredLoansAnalysis {
: Cfg(C), AC(AC), Xfer(FS, SetFactory) {}
void run() {
- llvm::TimeTraceScope TimeProfile("Expired Loans Analysis");
+ llvm::TimeTraceScope TimeProfile("ExpiredLoansAnalysis");
ForwardDataflowWorklist Worklist(Cfg, AC);
const CFGBlock *Entry = &Cfg.getEntry();
- BlockEntryStates[Entry] = ExpiredLattice(SetFactory.getEmptySet());
+ BlockEntryStates[Entry] = ExpiredLattice{};
Worklist.enqueueBlock(Entry);
while (const CFGBlock *B = Worklist.dequeue()) {
ExpiredLattice EntryState = getEntryState(B);
@@ -849,24 +849,16 @@ class ExpiredLoansAnalysis {
}
ExpiredLattice getEntryState(const CFGBlock *B) const {
- auto It = BlockEntryStates.find(B);
- if (It != BlockEntryStates.end()) {
- return It->second;
- }
- return ExpiredLattice(SetFactory.getEmptySet());
+ return BlockEntryStates.lookup(B);
}
ExpiredLattice getExitState(const CFGBlock *B) const {
- auto It = BlockExitStates.find(B);
- if (It != BlockExitStates.end()) {
- return It->second;
- }
- return ExpiredLattice(SetFactory.getEmptySet());
+ return BlockExitStates.lookup(B);
}
};
// ========================================================================= //
-// TODO: Analysing dataflow results and error reporting.
+// TODO: Liveness analysis, analysing dataflow results and error reporting.
// ========================================================================= //
} // anonymous namespace
@@ -895,6 +887,6 @@ void runLifetimeSafetyAnalysis(const DeclContext &DC, const
CFG &Cfg,
ExpiredLoansAnalysis ExpiredAnalysis(Cfg, FactMgr, AC);
ExpiredAnalysis.run();
- DEBUG_WITH_TYPE("ExpiredLoans", ExpiredAnalysis.dump());
+ DEBUG_WITH_TYPE("LifetimeExpiredLoans", ExpiredAnalysis.dump());
}
} // namespace clang
>From e90b6151677644856712faa4c3d0127470932788 Mon Sep 17 00:00:00 2001
From: Utkarsh Saxena <u...@google.com>
Date: Mon, 14 Jul 2025 16:45:12 +0000
Subject: [PATCH 3/3] format
---
clang/lib/Analysis/LifetimeSafety.cpp | 445 ++++++++++----------------
1 file changed, 177 insertions(+), 268 deletions(-)
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp
b/clang/lib/Analysis/LifetimeSafety.cpp
index cdb3e5e47c90f..6bd8181ef7989 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
@@ -535,52 +636,6 @@ struct LifetimeLattice {
return !(*this == Other);
}
- LoanSet getLoans(OriginID OID, LifetimeFactory &Factory) const {
- if (auto *Loans = Origins.lookup(OID))
- return *Loans;
- return Factory.LoanSetFact.getEmptySet();
- }
-
- /// 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.OriginMapFact.add(
- JoinedState, OID,
- join(getLoans(OID, Factory), 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())
@@ -594,138 +649,66 @@ 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.OriginMapFact.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(
+ return Lattice(
Factory.OriginMapFact.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, Factory);
- return LifetimeLattice(
- Factory.OriginMapFact.add(InState.Origins, DestOID, SrcLoans));
+ LoanSet SrcLoans = getLoans(In, SrcOID);
+ return Lattice(Factory.OriginMapFact.add(In.Origins, DestOID, SrcLoans));
}
-};
-
-// ========================================================================= //
-// Dataflow 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;
-
- Transferer Xfer;
-
- /// 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;
-
-public:
- LifetimeDataflow(const CFG &C, FactManager &FS, AnalysisDeclContext &AC)
- : Cfg(C), AC(AC), Xfer(FS, LifetimeFact) {}
- 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;
-
- 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);
- }
- }
- }
- }
-
- void dump() const {
- llvm::dbgs() << "==========================================\n";
- llvm::dbgs() << " Dataflow results:\n";
- llvm::dbgs() << "==========================================\n";
- const CFGBlock &B = Cfg.getExit();
- getExitState(&B).dump(llvm::dbgs());
- }
-
- LifetimeLattice getEntryState(const CFGBlock *B) const {
- return BlockEntryStates.lookup(B);
- }
-
- LifetimeLattice getExitState(const CFGBlock *B) const {
- return BlockExitStates.lookup(B);
+private:
+ LoanSet getLoans(Lattice L, OriginID OID) {
+ if (auto *Loans = L.Origins.lookup(OID))
+ return *Loans;
+ return Factory.LoanSetFact.getEmptySet();
}
};
@@ -747,15 +730,6 @@ struct ExpiredLattice {
return !(*this == Other);
}
- /// Computes the union of two lattices.
- ExpiredLattice join(const ExpiredLattice &Other,
- LoanSet::Factory &Factory) const {
- LoanSet JoinedSet = Expired;
- for (LoanID LID : Other.Expired)
- JoinedSet = Factory.add(JoinedSet, LID);
- return ExpiredLattice(JoinedSet);
- }
-
void dump(llvm::raw_ostream &OS) const {
OS << "ExpiredLattice State:\n";
if (Expired.isEmpty())
@@ -766,100 +740,36 @@ struct ExpiredLattice {
};
/// Transfer function for the expired loans analysis.
-class ExpiredLoansTransferer {
- FactManager &AllFacts;
- LoanSet::Factory &SetFactory;
-
-public:
- explicit ExpiredLoansTransferer(FactManager &F, LoanSet::Factory &SF)
- : AllFacts(F), SetFactory(SF) {}
-
- /// Computes the exit state of a block by applying all its facts sequentially
- /// to a given entry state.
- ExpiredLattice transferBlock(const CFGBlock *Block,
- ExpiredLattice EntryState) {
- ExpiredLattice BlockState = EntryState;
- llvm::ArrayRef<const Fact *> Facts = AllFacts.getFacts(Block);
-
- for (const Fact *F : Facts) {
- BlockState = transferFact(BlockState, F);
- }
- return BlockState;
- }
+class ExpiredLoansAnalysis
+ : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice> {
-private:
- ExpiredLattice transferFact(ExpiredLattice In, const Fact *F) {
- if (const auto *EF = F->getAs<ExpireFact>())
- return ExpiredLattice(SetFactory.add(In.Expired, EF->getLoanID()));
-
- if (const auto *IF = F->getAs<IssueFact>())
- return ExpiredLattice(SetFactory.remove(In.Expired, IF->getLoanID()));
-
- return In;
- }
-};
-
-/// Dataflow analysis driver for tracking expired loans.
-class ExpiredLoansAnalysis {
- const CFG &Cfg;
- AnalysisDeclContext &AC;
- LoanSet::Factory SetFactory;
- ExpiredLoansTransferer Xfer;
-
- llvm::DenseMap<const CFGBlock *, ExpiredLattice> BlockEntryStates;
- llvm::DenseMap<const CFGBlock *, ExpiredLattice> BlockExitStates;
+ LoanSet::Factory &SetFactory;
public:
- ExpiredLoansAnalysis(const CFG &C, FactManager &FS, AnalysisDeclContext &AC)
- : Cfg(C), AC(AC), Xfer(FS, SetFactory) {}
+ ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
+ LoanSet::Factory &SF)
+ : DataflowAnalysis(C, AC, F), SetFactory(SF) {}
- void run() {
- llvm::TimeTraceScope TimeProfile("ExpiredLoansAnalysis");
- ForwardDataflowWorklist Worklist(Cfg, AC);
- const CFGBlock *Entry = &Cfg.getEntry();
- BlockEntryStates[Entry] = ExpiredLattice{};
- Worklist.enqueueBlock(Entry);
- while (const CFGBlock *B = Worklist.dequeue()) {
- ExpiredLattice EntryState = getEntryState(B);
- ExpiredLattice ExitState = Xfer.transferBlock(B, EntryState);
- BlockExitStates[B] = ExitState;
+ using DataflowAnalysis<ExpiredLoansAnalysis, Lattice>::transfer;
- for (const CFGBlock *Successor : B->succs()) {
- auto SuccIt = BlockEntryStates.find(Successor);
- ExpiredLattice OldSuccEntryState = (SuccIt != BlockEntryStates.end())
- ? SuccIt->second
- : ExpiredLattice{};
- ExpiredLattice NewSuccEntryState =
- OldSuccEntryState.join(ExitState, SetFactory);
- 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() << " Expired Loans 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);
}
- ExpiredLattice 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()));
}
- ExpiredLattice 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: Liveness analysis, analysing dataflow results and error reporting.
-// ========================================================================= //
} // anonymous namespace
void runLifetimeSafetyAnalysis(const DeclContext &DC, const CFG &Cfg,
@@ -872,21 +782,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());
-
- ExpiredLoansAnalysis ExpiredAnalysis(Cfg, FactMgr, AC);
+ // 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("LifetimeExpiredLoans", ExpiredAnalysis.dump());
+ DEBUG_WITH_TYPE(
+ "ExpiredLoans",
+ ExpiredAnalysis.getExitState(&Cfg.getExit()).dump(llvm::dbgs()));
}
} // namespace clang
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
