| commit | e4866f916a76b3dff4ffceca57a56f9dbac29a40 | [log] [tgz] |
|---|---|---|
| author | Utkarsh Saxena <usx@google.com> | Fri Sep 19 18:40:05 2025 +0200 |
| committer | Copybara-Service <copybara-worker@google.com> | Fri Sep 19 09:43:04 2025 -0700 |
| tree | 1a3a102a2d2ba33b0de17a1c6810a3ad3114f2d0 | |
| parent | 041bb1eb2ac0b7102542d431f8a2d936d95da050 [diff] |
[LifetimeSafety] Avoid adding already present items in sets/maps (#159582) Optimize lifetime safety analysis performance - Added early return optimization in `join` function for ImmutableSet when sets are identical - Improved ImmutableMap join logic to avoid unnecessary operations when values are equal I was under the impression that ImmutableSets/Maps would not modify the underlying if already existing elements are added to the container (and was hoping for structural equality in this aspect). It looks like the current implementation of `ImmutableSet` would perform addition nevertheless thereby creating (presumably `O(log(N))` tree nodes. This change considerably brings down compile times for some edge cases which happened to be present in the LLVM codebase. Now it is actually possible to compile LLVM in under 20 min with the lifetime analysis. The compile time hit is still significant but not as bad as before this change where it was not possible to compile LLVM without severely limiting analysis' scope (giving up on CFG with > 3000 blocks). Fixes https://github.com/llvm/llvm-project/issues/157420 <details> <summary>Report (Before)</summary> </details> <details> <summary>Report (After)</summary> # Lifetime Analysis Performance Report > Generated on: 2025-09-18 14:28:00 --- ## Test Case: Pointer Cycle in Loop **Timing Results:** | N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) | Loan Propagation (%) | Expired Loans (%) | |:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:| | 25 | 53.76 ms | 85.58% | 0.00% | 85.46% | 0.00% | | 50 | 605.35 ms | 98.39% | 0.00% | 98.37% | 0.00% | | 75 | 2.89 s | 99.62% | 0.00% | 99.61% | 0.00% | | 100 | 8.62 s | 99.80% | 0.00% | 99.80% | 0.00% | **Complexity Analysis:** | Analysis Phase | Complexity O(n<sup>k</sup>) | |:------------------|:--------------------------| | Total Analysis | O(n<sup>3.82</sup> ± 0.01) | | FactGenerator | (Negligible) | | LoanPropagation | O(n<sup>3.82</sup> ± 0.01) | | ExpiredLoans | (Negligible) | --- ## Test Case: CFG Merges **Timing Results:** | N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) | Loan Propagation (%) | Expired Loans (%) | |:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:| | 400 | 66.02 ms | 58.61% | 1.04% | 56.53% | 1.02% | | 1000 | 319.24 ms | 81.31% | 0.63% | 80.04% | 0.64% | | 2000 | 1.43 s | 92.00% | 0.40% | 91.32% | 0.28% | | 5000 | 9.35 s | 97.01% | 0.25% | 96.63% | 0.12% | **Complexity Analysis:** | Analysis Phase | Complexity O(n<sup>k</sup>) | |:------------------|:--------------------------| | Total Analysis | O(n<sup>2.12</sup> ± 0.02) | | FactGenerator | O(n<sup>1.54</sup> ± 0.02) | | LoanPropagation | O(n<sup>2.12</sup> ± 0.03) | | ExpiredLoans | O(n<sup>1.13</sup> ± 0.03) | --- ## Test Case: Deeply Nested Loops **Timing Results:** | N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) | Loan Propagation (%) | Expired Loans (%) | |:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:| | 50 | 137.30 ms | 90.72% | 0.00% | 90.42% | 0.00% | | 100 | 1.09 s | 98.13% | 0.00% | 98.02% | 0.09% | | 150 | 4.06 s | 99.24% | 0.00% | 99.18% | 0.05% | | 200 | 10.44 s | 99.66% | 0.00% | 99.63% | 0.03% | **Complexity Analysis:** | Analysis Phase | Complexity O(n<sup>k</sup>) | |:------------------|:--------------------------| | Total Analysis | O(n<sup>3.29</sup> ± 0.01) | | FactGenerator | (Negligible) | | LoanPropagation | O(n<sup>3.29</sup> ± 0.01) | | ExpiredLoans | O(n<sup>1.42</sup> ± 0.19) | --- </details> GitOrigin-RevId: 250a92fca5148414845bc50a0e1883f250891a39
Welcome to Clang.
This is a compiler front-end for the C family of languages (C, C++ and Objective-C) which is built as part of the LLVM compiler infrastructure project.
Unlike many other compiler frontends, Clang is useful for a number of things beyond just compiling code: we intend for Clang to be host to a number of different source-level tools. One example of this is the Clang Static Analyzer.
If you're interested in more (including how to build Clang) it is best to read the relevant websites. Here are some pointers:
Information on Clang: http://clang.llvm.org/
Building and using Clang: http://clang.llvm.org/get_started.html
Clang Static Analyzer: http://clang-analyzer.llvm.org/
Information on the LLVM project: http://llvm.org/
If you have questions or comments about Clang, a great place to discuss them is on the Clang forums:
If you find a bug in Clang, please file it in the LLVM bug tracker: