llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-temporal-safety Author: Utkarsh Saxena (usx95) <details> <summary>Changes</summary> 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 --- 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 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], }, ] `````````` </details> https://github.com/llvm/llvm-project/pull/159582 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
