[LifetimeSafety] Avoid adding already present items in sets/maps #159582

usx95 · 2025-09-18T14:28:47Z

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 #157420

Report (Before)

Report (After)

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^k)
Total Analysis	O(n^3.82 ± 0.01)
FactGenerator	(Negligible)
LoanPropagation	O(n^3.82 ± 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^k)
Total Analysis	O(n^2.12 ± 0.02)
FactGenerator	O(n^1.54 ± 0.02)
LoanPropagation	O(n^2.12 ± 0.03)
ExpiredLoans	O(n^1.13 ± 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^k)
Total Analysis	O(n^3.29 ± 0.01)
FactGenerator	(Negligible)
LoanPropagation	O(n^3.29 ± 0.01)
ExpiredLoans	O(n^1.42 ± 0.19)

usx95 · 2025-09-18T14:29:04Z

[LifetimeSafety] Avoid adding already present items in sets/maps #159582 👈 (View in Graphite)
main

This stack of pull requests is managed by Graphite. Learn more about stacking.

llvmbot · 2025-09-18T14:38:46Z

@llvm/pr-subscribers-clang-analysis
@llvm/pr-subscribers-clang
@llvm/pr-subscribers-clang-static-analyzer-1

@llvm/pr-subscribers-clang-temporal-safety

Author: Utkarsh Saxena (usx95)

Changes

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 #157420

Full diff: https://github.com/llvm/llvm-project/pull/159582.diff

2 Files Affected:

(modified) clang/lib/Analysis/LifetimeSafety.cpp (+6-3)
(modified) clang/test/Analysis/LifetimeSafety/benchmark.py (+6-5)

diff --git a/clang/lib/Analysis/LifetimeSafety.cpp b/clang/lib/Analysis/LifetimeSafety.cpp
index 0dd5716d93fb6..ddcdd0e72a723 100644
--- a/clang/lib/Analysis/LifetimeSafety.cpp
+++ b/clang/lib/Analysis/LifetimeSafety.cpp
@@ -910,6 +910,8 @@ template <typename T>
 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)
@@ -947,10 +949,11 @@ join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B,
   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/clang/test/Analysis/LifetimeSafety/benchmark.py b/clang/test/Analysis/LifetimeSafety/benchmark.py
index 4421fe9a81e21..2373f9984eecd 100644
--- a/clang/test/Analysis/LifetimeSafety/benchmark.py
+++ b/clang/test/Analysis/LifetimeSafety/benchmark.py
@@ -252,7 +252,7 @@ def generate_markdown_report(results: dict) -> str:
             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 @@ def run_single_test(
         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 @@ def run_single_test(
     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],
         },
     ]

Xazax-hun · 2025-09-19T07:33:22Z

Ugh, I wonder if this is unintentional and we should change the implementation of these data structures. I also find this behavior very surprising.

jvoung

Oof nice find!

jvoung · 2025-09-19T12:29:03Z

clang/lib/Analysis/LifetimeSafety.cpp

                                  llvm::ImmutableSet<T> B,
                                  typename llvm::ImmutableSet<T>::Factory &F) {
+  if (A == B)
+    return A;


would the add() on line 918 also possibly do more allocation than desired (and cost more than checking if contains first), if E was already in A ?

Added this check as well.

usx95 · 2025-09-19T14:42:13Z

Ugh, I wonder if this is unintentional and we should change the implementation of these data structures. I also find this behavior very surprising.

I can try changing the data structure. Let me do that in a separate PR. It would need an extra Value comparison which needs to be done while inserting the element and this could be a slight concern for other users. Let me give it a try.

ymand · 2025-09-19T14:45:29Z

Ugh, I wonder if this is unintentional and we should change the implementation of these data structures. I also find this behavior very surprising.

I can try changing the data structure. Let me do that in a separate PR. It would need an extra Value comparison which needs to be done while inserting the element and this could be a slight concern for other users. Let me give it a try.

Seems like its a bug, based on the comment for add:

    /// add - ...  If
    ///  the original set already included the value, then the original set is
    ///  returned and no memory is allocated. ...

usx95 · 2025-09-19T14:46:04Z

Hmm. Atleast the documentation for add_internal suggests that this might be really unintentional

/// add_internal - Creates a new tree that includes the specified
  ///  data and the data from the original tree.  If the original tree
  ///  already contained the data item, the original tree is returned.

usx95 · 2025-09-19T14:47:12Z

Yitzi beat me to it. Yup this is definitely a bug then.

usx95

Will change the underlying data structure in the next PR. Submitting this to stop the bleeding.

usx95 · 2025-09-19T15:30:16Z

clang/lib/Analysis/LifetimeSafety.cpp

                                  llvm::ImmutableSet<T> B,
                                  typename llvm::ImmutableSet<T>::Factory &F) {
+  if (A == B)
+    return A;


Added this check as well.

usx95 · 2025-09-19T15:59:41Z

Merge activity

Sep 19, 3:59 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:02 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:09 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:12 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:15 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:22 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:25 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:32 PM UTC: Graphite rebased this pull request as part of a merge.
Sep 19, 4:36 PM UTC: Graphite rebased this pull request as part of a merge.

usx95 added the clang:temporal-safety Issue/FR relating to the lifetime analysis in Clang (-Wdangling, -Wreturn-local-addr) label Sep 18, 2025 — with Graphite App

github-project-automation bot added this to Lifetime Safety in Clang Sep 18, 2025

usx95 marked this pull request as ready for review September 18, 2025 14:39

llvmbot added clang Clang issues not falling into any other category clang:static analyzer clang:analysis labels Sep 18, 2025

Xazax-hun approved these changes Sep 19, 2025

View reviewed changes

usx95 requested review from jvoung and ymand September 19, 2025 11:06

jvoung approved these changes Sep 19, 2025

View reviewed changes

ymand approved these changes Sep 19, 2025

View reviewed changes

usx95 force-pushed the users/usx95/09-18-_lifetimesafety_avoid_adding_already_present_items_in_sets_maps branch from 45f4b75 to 533103b Compare September 19, 2025 15:28

usx95 commented Sep 19, 2025

View reviewed changes

usx95 force-pushed the users/usx95/09-18-_lifetimesafety_avoid_adding_already_present_items_in_sets_maps branch from 533103b to 713609d Compare September 19, 2025 15:59

usx95 force-pushed the users/usx95/09-18-_lifetimesafety_avoid_adding_already_present_items_in_sets_maps branch 7 times, most recently from c08ea2d to ddfed4a Compare September 19, 2025 16:32

[LifetimeSafety] Avoid adding already present items in sets/maps

e6a9a57

usx95 force-pushed the users/usx95/09-18-_lifetimesafety_avoid_adding_already_present_items_in_sets_maps branch from ddfed4a to e6a9a57 Compare September 19, 2025 16:35

usx95 merged commit 250a92f into main Sep 19, 2025
7 of 9 checks passed

usx95 deleted the users/usx95/09-18-_lifetimesafety_avoid_adding_already_present_items_in_sets_maps branch September 19, 2025 16:40

github-project-automation bot moved this to Done in Lifetime Safety in Clang Sep 19, 2025

[LifetimeSafety] Avoid adding already present items in sets/maps #159582

[LifetimeSafety] Avoid adding already present items in sets/maps #159582

Uh oh!

Conversation

usx95 commented Sep 18, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Lifetime Analysis Performance Report

Test Case: Pointer Cycle in Loop

Test Case: CFG Merges

Test Case: Deeply Nested Loops

Uh oh!

usx95 commented Sep 18, 2025

Uh oh!

llvmbot commented Sep 18, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Xazax-hun commented Sep 19, 2025

Uh oh!

jvoung left a comment

Choose a reason for hiding this comment

Uh oh!

jvoung Sep 19, 2025

Choose a reason for hiding this comment

Uh oh!

usx95 Sep 19, 2025

Choose a reason for hiding this comment

Uh oh!

usx95 commented Sep 19, 2025

Uh oh!

ymand commented Sep 19, 2025

Uh oh!

usx95 commented Sep 19, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

usx95 commented Sep 19, 2025

Uh oh!

usx95 left a comment

Choose a reason for hiding this comment

Uh oh!

usx95 Sep 19, 2025

Choose a reason for hiding this comment

Uh oh!

usx95 commented Sep 19, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Merge activity

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

usx95 commented Sep 18, 2025 •

edited

Loading

llvmbot commented Sep 18, 2025 •

edited

Loading

usx95 commented Sep 19, 2025 •

edited

Loading

usx95 commented Sep 19, 2025 •

edited

Loading