llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-analysis Author: Gábor Horváth (Xazax-hun) <details> <summary>Changes</summary> 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 --- Full diff: https://github.com/llvm/llvm-project/pull/208908.diff 1 Files Affected: - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety/Utils.h (+4) ``````````diff 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); `````````` </details> https://github.com/llvm/llvm-project/pull/208908 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
