diff options
| author | Utkarsh Saxena <usx@google.com> | 2025-10-07 19:46:04 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2025-10-07 17:46:04 +0000 |
| commit | 6bbd7eaf0aa0b75b73d843d9f56ab6d7226018ef (patch) | |
| tree | 7e56d73dcefe6cbe3bf3a26ba7639f96c03ed2e6 /llvm/lib/CodeGen/CodeGen.cpp | |
| parent | 675be0df29d305edd6137de7efcb85035028f731 (diff) | |
| download | llvm-6bbd7eaf0aa0b75b73d843d9f56ab6d7226018ef.zip llvm-6bbd7eaf0aa0b75b73d843d9f56ab6d7226018ef.tar.gz llvm-6bbd7eaf0aa0b75b73d843d9f56ab6d7226018ef.tar.bz2 | |
[LifetimeSafety] Introduce a liveness-based lifetime policy (#159991)
This PR replaces the forward `ExpiredLoansAnalysis` with a backward
`LiveOriginAnalysis` that tracks which origins are live at each program
point, along with confidence levels (Definite or Maybe). The new
approach:
- Tracks liveness of origins rather than expiration of loans
- Uses a backward dataflow analysis to determine which origins are live
at each point.
- Provides more precise confidence levels for use-after-free warnings
and avoids previous false-positives
The `LifetimeChecker` now checks for use-after-free by examining if an
origin is live when a loan expires, rather than checking if a loan is
expired when an origin is used.
More details describing the design flaw in using `ExpiredLoans` is
mentioned in
https://github.com/llvm/llvm-project/issues/156959#issuecomment-3281917701
Fixes: https://github.com/llvm/llvm-project/issues/156959
(With this, we can build LLVM with no false-positives 🎉 )
<details>
<summary>
Benchmark report
</summary>
# Lifetime Analysis Performance Report
> Generated on: 2025-09-24 13:08:03
---
## Test Case: Pointer Cycle in Loop
**Timing Results:**
| N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) |
Loan Propagation (%) | Live Origins (%) |
|:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:|
| 50 | 54.12 ms | 80.80% | 0.00% | 80.42% | 0.00% |
| 75 | 150.22 ms | 91.54% | 0.00% | 91.19% | 0.00% |
| 100 | 317.12 ms | 94.90% | 0.00% | 94.77% | 0.00% |
| 200 | 2.40 s | 98.58% | 0.00% | 98.54% | 0.03% |
| 300 | 9.85 s | 99.25% | 0.00% | 99.24% | 0.01% |
**Complexity Analysis:**
| Analysis Phase | Complexity O(n<sup>k</sup>) |
|:------------------|:--------------------------|
| Total Analysis | O(n<sup>3.47</sup> ± 0.06) |
| FactGenerator | (Negligible) |
| LoanPropagation | O(n<sup>3.47</sup> ± 0.06) |
| LiveOrigins | (Negligible) |
---
## Test Case: CFG Merges
**Timing Results:**
| N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) |
Loan Propagation (%) | Live Origins (%) |
|:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:|
| 400 | 105.22 ms | 72.61% | 0.68% | 71.38% | 0.52% |
| 1000 | 610.74 ms | 88.88% | 0.33% | 88.32% | 0.23% |
| 2000 | 2.50 s | 95.32% | 0.21% | 94.99% | 0.11% |
| 5000 | 17.20 s | 98.20% | 0.14% | 98.01% | 0.05% |
**Complexity Analysis:**
| Analysis Phase | Complexity O(n<sup>k</sup>) |
|:------------------|:--------------------------|
| Total Analysis | O(n<sup>2.14</sup> ± 0.00) |
| FactGenerator | O(n<sup>1.59</sup> ± 0.05) |
| LoanPropagation | O(n<sup>2.14</sup> ± 0.00) |
| LiveOrigins | O(n<sup>1.19</sup> ± 0.04) |
---
## Test Case: Deeply Nested Loops
**Timing Results:**
| N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) |
Loan Propagation (%) | Live Origins (%) |
|:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:|
| 50 | 141.95 ms | 91.14% | 0.00% | 90.99% | 0.00% |
| 100 | 1.09 s | 98.17% | 0.00% | 98.13% | 0.00% |
| 150 | 3.87 s | 99.28% | 0.00% | 99.27% | 0.00% |
| 200 | 9.81 s | 99.61% | 0.00% | 99.60% | 0.00% |
**Complexity Analysis:**
| Analysis Phase | Complexity O(n<sup>k</sup>) |
|:------------------|:--------------------------|
| Total Analysis | O(n<sup>3.23</sup> ± 0.02) |
| FactGenerator | (Negligible) |
| LoanPropagation | O(n<sup>3.23</sup> ± 0.02) |
| LiveOrigins | (Negligible) |
---
## Test Case: Switch Fan-out
**Timing Results:**
| N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) |
Loan Propagation (%) | Live Origins (%) |
|:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:|
| 500 | 155.10 ms | 72.03% | 0.47% | 67.49% | 4.06% |
| 1000 | 568.40 ms | 85.60% | 0.24% | 80.53% | 4.83% |
| 2000 | 2.25 s | 93.00% | 0.13% | 86.99% | 5.88% |
| 4000 | 9.06 s | 96.62% | 0.10% | 89.68% | 6.84% |
**Complexity Analysis:**
| Analysis Phase | Complexity O(n<sup>k</sup>) |
|:------------------|:--------------------------|
| Total Analysis | O(n<sup>2.07</sup> ± 0.01) |
| FactGenerator | O(n<sup>1.52</sup> ± 0.13) |
| LoanPropagation | O(n<sup>2.06</sup> ± 0.01) |
| LiveOrigins | O(n<sup>2.23</sup> ± 0.00) |
---
<details>
Diffstat (limited to 'llvm/lib/CodeGen/CodeGen.cpp')
0 files changed, 0 insertions, 0 deletions