- Notifications
You must be signed in to change notification settings - Fork14.5k
[LifetimeSafety] Add per-program-point lattice tracking#149199
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Open
usx95 wants to merge1 commit intomainChoose a base branch
base:main
Could not load branches
Branch not found:{{ refName }}
Loading
Could not load tags
Nothing to show
Loading
Are you sure you want to change the base?
Some commits from the old base branch may be removed from the timeline, and old review comments may become outdated.
Uh oh!
There was an error while loading.Please reload this page.
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
ContributorAuthor
usx95 commentedJul 16, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
This stack of pull requests is managed byGraphite. Learn more aboutstacking. |
4f11ea0 toa0b1ef0Compare@llvm/pr-subscribers-clang Author: Utkarsh Saxena (usx95) ChangesAdd per-program-point state tracking to the dataflow analysis framework.
This change enables more precise analysis by tracking program state at each individual program point rather than just at block boundaries. This is necessary for answering queries about the state of loans, origins, and other properties at specific points in the program, which is required for error reporting in the lifetime safety analysis. Full diff:https://github.com/llvm/llvm-project/pull/149199.diff 1 Files Affected:
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp b/clang/lib/Analysis/LifetimeSafety.cppindex e3a03cf93880e..3bf3b0d344cfa 100644--- a/clang/lib/Analysis/LifetimeSafety.cpp+++ b/clang/lib/Analysis/LifetimeSafety.cpp@@ -502,6 +502,12 @@ class FactGenerator : public ConstStmtVisitor<FactGenerator> { enum class Direction { Forward, Backward };+/// A program point is a pair of a CFGBlock and a Fact within that block.+///+/// This is used to represent the state of the program *after* the Fact is+/// executed.+using ProgramPoint = std::pair<const CFGBlock *, const Fact *>;+ /// A generic, policy-based driver for dataflow analyses. It combines /// the dataflow runner and the transferer logic into a single class hierarchy. ///@@ -530,8 +536,14 @@ class DataflowAnalysis { const CFG &Cfg; AnalysisDeclContext &AC;+ /// The dataflow state before a basic block is processed. llvm::DenseMap<const CFGBlock *, Lattice> InStates;+ /// The dataflow state after a basic block is processed. llvm::DenseMap<const CFGBlock *, Lattice> OutStates;+ /// The dataflow state at a Program Point.+ /// In a forward analysis, this is the state after the Fact at that point has+ /// been applied, while in a backward analysis, it is the state before.+ llvm::DenseMap<ProgramPoint, Lattice> PerPointStates; static constexpr bool isForward() { return Dir == Direction::Forward; }@@ -577,6 +589,8 @@ class DataflowAnalysis { } }+ Lattice getState(ProgramPoint P) const { return PerPointStates.lookup(P); }+ Lattice getInState(const CFGBlock *B) const { return InStates.lookup(B); } Lattice getOutState(const CFGBlock *B) const { return OutStates.lookup(B); }@@ -590,18 +604,23 @@ class DataflowAnalysis { getOutState(&B).dump(llvm::dbgs()); }+private: /// Computes the state at one end of a block by applying all its facts /// sequentially to a given state from the other end.- /// TODO: We might need to store intermediate states per-fact in the block for- /// later analysis. Lattice transferBlock(const CFGBlock *Block, Lattice State) { auto Facts = AllFacts.getFacts(Block);- if constexpr (isForward())- for (const Fact *F : Facts)+ if constexpr (isForward()) {+ for (const Fact *F : Facts) { State = transferFact(State, F);- else- for (const Fact *F : llvm::reverse(Facts))+ PerPointStates[{Block, F}] = State;+ }+ } else {+ for (const Fact *F : llvm::reverse(Facts)) {+ // In backward analysis, capture the state before applying the fact.+ PerPointStates[{Block, F}] = State; State = transferFact(State, F);+ }+ } return State; }@@ -769,6 +788,10 @@ class LoanPropagationAnalysis Factory.OriginMapFactory.add(In.Origins, DestOID, SrcLoans)); }+ LoanSet getLoans(OriginID OID, ProgramPoint P) {+ return getLoans(getState(P), OID);+ }+ private: LoanSet getLoans(Lattice L, OriginID OID) { if (auto *Loans = L.Origins.lookup(OID))@@ -779,7 +802,6 @@ class LoanPropagationAnalysis // ========================================================================= // // TODO:-// - Modifying loan propagation to answer `LoanSet getLoans(Origin O, Point P)` // - Modify loan expiry analysis to answer `bool isExpired(Loan L, Point P)` // - Modify origin liveness analysis to answer `bool isLive(Origin O, Point P)` // - Using the above three to perform the final error reporting. |
@llvm/pr-subscribers-clang-analysis Author: Utkarsh Saxena (usx95) ChangesAdd per-program-point state tracking to the dataflow analysis framework.
This change enables more precise analysis by tracking program state at each individual program point rather than just at block boundaries. This is necessary for answering queries about the state of loans, origins, and other properties at specific points in the program, which is required for error reporting in the lifetime safety analysis. Full diff:https://github.com/llvm/llvm-project/pull/149199.diff 1 Files Affected:
diff --git a/clang/lib/Analysis/LifetimeSafety.cpp b/clang/lib/Analysis/LifetimeSafety.cppindex e3a03cf93880e..3bf3b0d344cfa 100644--- a/clang/lib/Analysis/LifetimeSafety.cpp+++ b/clang/lib/Analysis/LifetimeSafety.cpp@@ -502,6 +502,12 @@ class FactGenerator : public ConstStmtVisitor<FactGenerator> { enum class Direction { Forward, Backward };+/// A program point is a pair of a CFGBlock and a Fact within that block.+///+/// This is used to represent the state of the program *after* the Fact is+/// executed.+using ProgramPoint = std::pair<const CFGBlock *, const Fact *>;+ /// A generic, policy-based driver for dataflow analyses. It combines /// the dataflow runner and the transferer logic into a single class hierarchy. ///@@ -530,8 +536,14 @@ class DataflowAnalysis { const CFG &Cfg; AnalysisDeclContext &AC;+ /// The dataflow state before a basic block is processed. llvm::DenseMap<const CFGBlock *, Lattice> InStates;+ /// The dataflow state after a basic block is processed. llvm::DenseMap<const CFGBlock *, Lattice> OutStates;+ /// The dataflow state at a Program Point.+ /// In a forward analysis, this is the state after the Fact at that point has+ /// been applied, while in a backward analysis, it is the state before.+ llvm::DenseMap<ProgramPoint, Lattice> PerPointStates; static constexpr bool isForward() { return Dir == Direction::Forward; }@@ -577,6 +589,8 @@ class DataflowAnalysis { } }+ Lattice getState(ProgramPoint P) const { return PerPointStates.lookup(P); }+ Lattice getInState(const CFGBlock *B) const { return InStates.lookup(B); } Lattice getOutState(const CFGBlock *B) const { return OutStates.lookup(B); }@@ -590,18 +604,23 @@ class DataflowAnalysis { getOutState(&B).dump(llvm::dbgs()); }+private: /// Computes the state at one end of a block by applying all its facts /// sequentially to a given state from the other end.- /// TODO: We might need to store intermediate states per-fact in the block for- /// later analysis. Lattice transferBlock(const CFGBlock *Block, Lattice State) { auto Facts = AllFacts.getFacts(Block);- if constexpr (isForward())- for (const Fact *F : Facts)+ if constexpr (isForward()) {+ for (const Fact *F : Facts) { State = transferFact(State, F);- else- for (const Fact *F : llvm::reverse(Facts))+ PerPointStates[{Block, F}] = State;+ }+ } else {+ for (const Fact *F : llvm::reverse(Facts)) {+ // In backward analysis, capture the state before applying the fact.+ PerPointStates[{Block, F}] = State; State = transferFact(State, F);+ }+ } return State; }@@ -769,6 +788,10 @@ class LoanPropagationAnalysis Factory.OriginMapFactory.add(In.Origins, DestOID, SrcLoans)); }+ LoanSet getLoans(OriginID OID, ProgramPoint P) {+ return getLoans(getState(P), OID);+ }+ private: LoanSet getLoans(Lattice L, OriginID OID) { if (auto *Loans = L.Origins.lookup(OID))@@ -779,7 +802,6 @@ class LoanPropagationAnalysis // ========================================================================= // // TODO:-// - Modifying loan propagation to answer `LoanSet getLoans(Origin O, Point P)` // - Modify loan expiry analysis to answer `bool isExpired(Loan L, Point P)` // - Modify origin liveness analysis to answer `bool isLive(Origin O, Point P)` // - Using the above three to perform the final error reporting. |
Uh oh!
There was an error while loading.Please reload this page.
a0b1ef0 to3e67c98Compare| /// The dataflow state at a Program Point. | ||
| /// In a forward analysis, this is the state after the Fact at that point has | ||
| /// been applied, while in a backward analysis, it is the state before. | ||
| llvm::DenseMap<ProgramPoint, Lattice> PerPointStates; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Do you think all of the analyses needPerPointStates? E.g., what about theExpiredLoansAnalysis? I wonder if we should have a boolean policy here.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Ah never mind. Now I remember you want to keep these states instead of replaying the analysis for the blocks.
Xazax-hun approved these changesJul 17, 2025
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
LG, thanks!
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Uh oh!
There was an error while loading.Please reload this page.
Add per-program-point state tracking to the dataflow analysis framework.
ProgramPointtype representing a pair of a CFGBlock and a Fact within that blockPerPointStatesmap to store lattice states at each program pointtransferBlockmethod to store intermediate states after each fact is processedgetLoansmethod to theLoanPropagationAnalysisclass that uses program pointsThis change enables more precise analysis by tracking program state at each individual program point rather than just at block boundaries. This is necessary for answering queries about the state of loans, origins, and other properties at specific points in the program, which is required for error reporting in the lifetime safety analysis.