Author: Gábor Horváth Date: 2026-07-14T12:28:43+01:00 New Revision: ad3c1ef174f9cac5bd0332747226740ce1b16159
URL: https://github.com/llvm/llvm-project/commit/ad3c1ef174f9cac5bd0332747226740ce1b16159 DIFF: https://github.com/llvm/llvm-project/commit/ad3c1ef174f9cac5bd0332747226740ce1b16159.diff LOG: [clang][Analysis] Speed up LiveVariables set merge (#209430) LiveVariables' mergeSets built the union by unconditionally inserting every element of B into A. Apply the two cheap tricks the lifetime-safety analysis uses in its dataflow join: * Return early when both operands are the same tree (an O(1) pointer comparison), skipping the merge entirely. Merged liveness values are canonicalized, so two predecessors with identical liveness share the same tree -- common at confluence points. * Insert the smaller set into the larger one, so the number of O(log n) insertions is min(|A|, |B|) rather than always |B|. The result is unchanged: set union is commutative and order-independent. On a pathological function (1000 simultaneously-live locals across 5000 control-flow merges of identical sets) the liveness computation is ~18% faster, essentially all from the identical-set short circuit. On real translation units the merge is a small fraction of the analysis, so the effect is within noise (measured neutral on DAGCombiner.cpp and X86ISelLowering.cpp); this mainly avoids redundant work at unchanged confluence points and brings the two dataflow analyses' merges into line. Assisted by: Claude Opus 4.8 Co-authored-by: Gabor Horvath <[email protected]> Added: Modified: clang/lib/Analysis/LiveVariables.cpp Removed: ################################################################################ diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp index af3055c3d5f8d..6fdd8e71396da 100644 --- a/clang/lib/Analysis/LiveVariables.cpp +++ b/clang/lib/Analysis/LiveVariables.cpp @@ -88,16 +88,18 @@ bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { } namespace { - template <typename SET> - SET mergeSets(SET A, SET B) { - if (A.isEmpty()) - return B; - - for (const auto *Elem : B) { - A = A.add(Elem); - } +template <typename SET> SET mergeSets(SET A, SET B) { + if (A.getRootWithoutRetain() == B.getRootWithoutRetain()) return A; + + if (A.getHeight() < B.getHeight()) + std::swap(A, B); + + for (const auto *Elem : B) { + A = A.add(Elem); } + return A; +} } // namespace void LiveVariables::Observer::anchor() { } _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
