[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
diff --git a/lib/Analysis/LifetimeSafety.cpp b/lib/Analysis/LifetimeSafety.cpp
index 0dd5716..d016c6f 100644
--- a/lib/Analysis/LifetimeSafety.cpp
+++ b/lib/Analysis/LifetimeSafety.cpp
@@ -910,10 +910,13 @@
static llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A,
llvm::ImmutableSet<T> B,
typename llvm::ImmutableSet<T>::Factory &F) {
+ if (A == B)
+ return A;
if (A.getHeight() < B.getHeight())
std::swap(A, B);
for (const T &E : B)
- A = F.add(A, E);
+ if (!A.contains(E))
+ A = F.add(A, E);
return A;
}
@@ -947,10 +950,11 @@
for (const auto &Entry : B) {
const K &Key = Entry.first;
const V &ValB = Entry.second;
- if (const V *ValA = A.lookup(Key))
- A = F.add(A, Key, JoinValues(*ValA, ValB));
- else
+ const V *ValA = A.lookup(Key);
+ if (!ValA)
A = F.add(A, Key, ValB);
+ else if (*ValA != ValB)
+ A = F.add(A, Key, JoinValues(*ValA, ValB));
}
return A;
}
diff --git a/test/Analysis/LifetimeSafety/benchmark.py b/test/Analysis/LifetimeSafety/benchmark.py
index 4421fe9..2373f99 100644
--- a/test/Analysis/LifetimeSafety/benchmark.py
+++ b/test/Analysis/LifetimeSafety/benchmark.py
@@ -252,7 +252,7 @@
report.append(" ".join(row))
report.append("\n**Complexity Analysis:**\n")
- report.append("| Analysis Phase | Complexity O(n<sup>k</sup>) |")
+ report.append("| Analysis Phase | Complexity O(n<sup>k</sup>) | ")
report.append("|:------------------|:--------------------------|")
analysis_phases = {
@@ -302,7 +302,7 @@
source_file,
]
- result = subprocess.run(clang_command, capture_output=True, text=True)
+ result = subprocess.run(clang_command, capture_output=True, text=True, timeout=60)
if result.returncode != 0:
print(f"Compilation failed for N={n}!", file=sys.stderr)
@@ -334,24 +334,25 @@
os.makedirs(args.output_dir, exist_ok=True)
print(f"Benchmark files will be saved in: {os.path.abspath(args.output_dir)}\n")
+ # Maximize 'n' values while keeping execution time under 10s.
test_configurations = [
{
"name": "cycle",
"title": "Pointer Cycle in Loop",
"generator_func": generate_cpp_cycle_test,
- "n_values": [10, 25, 50, 75, 100, 150],
+ "n_values": [25, 50, 75, 100],
},
{
"name": "merge",
"title": "CFG Merges",
"generator_func": generate_cpp_merge_test,
- "n_values": [10, 50, 100, 200, 400, 800],
+ "n_values": [400, 1000, 2000, 5000],
},
{
"name": "nested_loops",
"title": "Deeply Nested Loops",
"generator_func": generate_cpp_nested_loop_test,
- "n_values": [10, 50, 100, 200, 400, 800],
+ "n_values": [50, 100, 150, 200],
},
]
