https://github.com/Xazax-hun created https://github.com/llvm/llvm-project/pull/208908
The dataflow join unions two ImmutableSets / ImmutableMaps key-wise by re-inserting every entry of one into the other. At confluence points the two operands are frequently the same tree -- state carried through a branch that did not touch it -- and the union is then that tree. Return it directly when the roots are pointer-equal: O(1) instead of O(n log n). A dataflow join is idempotent, so the result is exact. benchmark.py, LoanPropagation phase: | Test | Before | After | Speedup | |-----------------------|---------:|---------:|:-------:| | Switch fan-out N=1000 | 71.3 ms | 1.7 ms | ~41x | | Switch fan-out N=2000 | 329.9 ms | 3.9 ms | ~85x | | Switch fan-out N=4000 | 1440 ms | 8.6 ms | ~168x | | Merge N=2000 | 297.0 ms | 236.8 ms | 1.25x | | Merge N=5000 | 2110 ms | 1680 ms | 1.26x | | Cycle N=300 | 1740 ms | 1670 ms | 1.04x | The speedup tracks how much branches perturb pointer state: switch fan-out merges identical maps (whole-map short-circuit), merge carries most origins unchanged (per-value short-circuit), and the cycle reseats every pointer each iteration so little is shared. Assisted by: Claude Opus 4.8 From 2d445037e5bb28e1ac538dbad132e1996655e5a2 Mon Sep 17 00:00:00 2001 From: Gabor Horvath <[email protected]> Date: Sat, 11 Jul 2026 12:47:19 +0100 Subject: [PATCH] [clang][LifetimeSafety] Short-circuit joins of identical immutable containers The dataflow join unions two ImmutableSets / ImmutableMaps key-wise by re-inserting every entry of one into the other. At confluence points the two operands are frequently the same tree -- state carried through a branch that did not touch it -- and the union is then that tree. Return it directly when the roots are pointer-equal: O(1) instead of O(n log n). A dataflow join is idempotent, so the result is exact. benchmark.py, LoanPropagation phase: | Test | Before | After | Speedup | |-----------------------|---------:|---------:|:-------:| | Switch fan-out N=1000 | 71.3 ms | 1.7 ms | ~41x | | Switch fan-out N=2000 | 329.9 ms | 3.9 ms | ~85x | | Switch fan-out N=4000 | 1440 ms | 8.6 ms | ~168x | | Merge N=2000 | 297.0 ms | 236.8 ms | 1.25x | | Merge N=5000 | 2110 ms | 1680 ms | 1.26x | | Cycle N=300 | 1740 ms | 1670 ms | 1.04x | The speedup tracks how much branches perturb pointer state: switch fan-out merges identical maps (whole-map short-circuit), merge carries most origins unchanged (per-value short-circuit), and the cycle reseats every pointer each iteration so little is shared. Assisted by: Claude Opus 4.8 --- clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h index 101ee083f0d95..543bbd045593c 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h @@ -38,6 +38,8 @@ template <typename Tag> struct ID { template <typename T> llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A, llvm::ImmutableSet<T> B, typename llvm::ImmutableSet<T>::Factory &F) { + if (A.getRootWithoutRetain() == B.getRootWithoutRetain()) + return A; if (A.getHeight() < B.getHeight()) std::swap(A, B); for (const T &E : B) @@ -70,6 +72,8 @@ llvm::ImmutableMap<K, V> join(const llvm::ImmutableMap<K, V> &A, const llvm::ImmutableMap<K, V> &B, typename llvm::ImmutableMap<K, V>::Factory &F, Joiner JoinValues, JoinKind Kind) { + if (A.getRootWithoutRetain() == B.getRootWithoutRetain()) + return A; if (A.getHeight() < B.getHeight()) return join(B, A, F, JoinValues, Kind); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
