https://github.com/Xazax-hun created https://github.com/llvm/llvm-project/pull/213530
Block-local origins were only discarded in `join`, which the dataflow driver skips when a successor's in-state is seen for the first time, and therefore always skips for a block with a single predecessor. In straight-line code the block-local map was inherited down the whole chain and never cleared, so it accumulated every expression origin in the region. Drop them in a new `exitBlock` hook instead, which runs on every edge. This also keeps in-states canonical, so state comparison no longer sees a spurious difference between a first-visit in-state and a joined one. The per-program-point states the checker queries are unaffected; only the state propagated across block boundaries changes. LoanPropagation time below, median of 5-7 interleaved runs of a baseline and a patched binary. Synthetic cases are from clang/test/Analysis/LifetimeSafety/benchmark.py: | case | before | after | delta | |-------------------------|--------|--------|--------| | switch_fan_out (N=4000) | 7.62 | 5.35 | -29.8% | | nested_loops (N=200) | 0.78 | 0.55 | -28.9% | | merge (N=5000) | 8.58 | 8.21 | -4.3% | | cycle (N=200) | 164.19 | 162.95 | -0.8% | Real-world translation units: | translation unit | before | after | delta | |---------------------------|--------|--------|--------| | ByteCode/Disasm.cpp | 22.34 | 18.21 | -18.5% | | X86/X86ISelLowering.cpp | 49.31 | 42.19 | -14.5% | | Sema/SemaExprCXX.cpp | 40.01 | 36.78 | -8.1% | | TargetBuiltins/ARM.cpp | 45.68 | 43.24 | -5.3% | Gains are concentrated in blocks with a single predecessor, where `join` never ran. Other phases are unchanged within run-to-run noise, and peak RSS is unchanged. LoanPropagation is 5-14% of the whole analysis, so its total effect there is -0.8% to -1.4%. Assisted-by: Opus 5.0 From 97d922a321aa33158d15be9b12916ddac274e09e Mon Sep 17 00:00:00 2001 From: Gabor Horvath <[email protected]> Date: Sun, 2 Aug 2026 12:13:49 +0100 Subject: [PATCH] [clang][LifetimeSafety] Drop block-local origins at block exit Block-local origins were only discarded in `join`, which the dataflow driver skips when a successor's in-state is seen for the first time, and therefore always skips for a block with a single predecessor. In straight-line code the block-local map was inherited down the whole chain and never cleared, so it accumulated every expression origin in the region. Drop them in a new `exitBlock` hook instead, which runs on every edge. This also keeps in-states canonical, so state comparison no longer sees a spurious difference between a first-visit in-state and a joined one. The per-program-point states the checker queries are unaffected; only the state propagated across block boundaries changes. LoanPropagation time below, median of 5-7 interleaved runs of a baseline and a patched binary. Synthetic cases are from clang/test/Analysis/LifetimeSafety/benchmark.py: | case | before | after | delta | |-------------------------|--------|--------|--------| | switch_fan_out (N=4000) | 7.62 | 5.35 | -29.8% | | nested_loops (N=200) | 0.78 | 0.55 | -28.9% | | merge (N=5000) | 8.58 | 8.21 | -4.3% | | cycle (N=200) | 164.19 | 162.95 | -0.8% | Real-world translation units: | translation unit | before | after | delta | |---------------------------|--------|--------|--------| | ByteCode/Disasm.cpp | 22.34 | 18.21 | -18.5% | | X86/X86ISelLowering.cpp | 49.31 | 42.19 | -14.5% | | Sema/SemaExprCXX.cpp | 40.01 | 36.78 | -8.1% | | TargetBuiltins/ARM.cpp | 45.68 | 43.24 | -5.3% | Gains are concentrated in blocks with a single predecessor, where `join` never ran. Other phases are unchanged within run-to-run noise, and peak RSS is unchanged. LoanPropagation is 5-14% of the whole analysis, so its total effect there is -0.8% to -1.4%. Assisted-by: Opus 5.0 --- clang/lib/Analysis/LifetimeSafety/Dataflow.h | 7 ++++++- clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp | 11 ++++++++++- 2 files changed, 16 insertions(+), 2 deletions(-) diff --git a/clang/lib/Analysis/LifetimeSafety/Dataflow.h b/clang/lib/Analysis/LifetimeSafety/Dataflow.h index fc3049c8bec84..aaa2c32c400c3 100644 --- a/clang/lib/Analysis/LifetimeSafety/Dataflow.h +++ b/clang/lib/Analysis/LifetimeSafety/Dataflow.h @@ -47,6 +47,9 @@ using ProgramPoint = const Fact *; /// lifetime-relevant `Fact` transforms the lattice state. Only overloads /// for facts relevant to the analysis need to be implemented. /// +/// It may additionally override `Lattice exitBlock(Lattice);` to drop state +/// that is not visible outside the block it was computed in. +/// /// \tparam Derived The CRTP derived class that implements the specific /// analysis. /// \tparam LatticeType The dataflow lattice used by the analysis. @@ -157,7 +160,7 @@ class DataflowAnalysis { State = transferFact(State, F); } } - return State; + return static_cast<Derived *>(this)->exitBlock(State); } Lattice transferFact(Lattice In, const Fact *F) { @@ -187,6 +190,8 @@ class DataflowAnalysis { } public: + Lattice exitBlock(Lattice In) { return In; } + Lattice transfer(Lattice In, const IssueFact &) { return In; } Lattice transfer(Lattice In, const ExpireFact &) { return In; } Lattice transfer(Lattice In, const OriginFlowFact &) { return In; } diff --git a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp index 078892bd48c10..f028e0f06ae29 100644 --- a/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp +++ b/clang/lib/Analysis/LifetimeSafety/LoanPropagation.cpp @@ -148,8 +148,9 @@ class AnalysisImpl Lattice getInitialState() { return Lattice{}; } /// Merges two lattices by taking the union of loans for each origin. - /// Only persistent origins are joined; block-local origins are discarded. Lattice join(Lattice A, Lattice B) { + assert(A.BlockLocalOrigins.isEmpty() && B.BlockLocalOrigins.isEmpty() && + "block-local origins must not reach a block boundary"); OriginLoanMap JoinedOrigins = utils::join( A.PersistentOrigins, B.PersistentOrigins, OriginLoanMapFactory, [&](const LoanSet *S1, const LoanSet *S2) { @@ -166,6 +167,14 @@ class AnalysisImpl return Lattice(JoinedOrigins, OriginLoanMapFactory.getEmptyMap()); } + /// Block-local origins are not referenced outside the block that computed + /// them, so they are dropped here rather than propagated to adjacent blocks. + /// Dropping them at the boundary (instead of in `join`) also covers edges + /// where `join` is never called, such as blocks with a single predecessor. + Lattice exitBlock(Lattice L) { + return Lattice(L.PersistentOrigins, OriginLoanMapFactory.getEmptyMap()); + } + /// A new loan is issued to the origin. Old loans are erased. Lattice transfer(Lattice In, const IssueFact &F) { OriginID OID = F.getOriginID(); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
