llvm / llvm/llvm-project

Lifetime safety can timeout on cyclic substitution in a loop

Open
#161,333 4 comments 0 reactions 0 assignees View on GitHub
clang:temporal-safety slow-compile
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```cpp
struct MyObj { int id; ~MyObj() {} };

void long_cycle_4(bool condition) {
MyObj v1{1};
MyObj* p1 = &v1;
{
MyObj v2{1};
MyObj v3{1};
MyObj v4{1};

MyObj* p2 = &v2;
MyObj* p3 = &v3;
MyObj* p4 = &v4;

while (condition) {
MyObj* temp = p1;
p1 = p2;
p2 = p3;
p3 = p4;
p4 = temp;
}
}
(void)*p1;
}
```
https://godbolt.org/z/7hnvbnx5W

Current benchmark results:

Test Case: Pointer Cycle in Loop

**Timing Results:**

| N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) | Loan Propagation (%) | Live Origins (%) |
|:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:|
| 50 | 56.10 ms | 79.14% | 0.00% | 78.77% | 0.00% |
| 75 | 156.51 ms | 91.45% | 0.00% | 91.24% | 0.00% |
| 100 | 344.89 ms | 94.44% | 0.00% | 94.32% | 0.00% |
| 200 | 2.47 s | 98.46% | 0.00% | 98.42% | 0.03% |
| 300 | 8.85 s | 99.16% | 0.00% | 99.14% | 0.01% |

This is also found to be a scaling issue for Polonius: https://github.com/rust-lang/rust/issues/140454

Since we do not aim for rigorous memory safety for C++ using Lifetime Safety, we can afford to cut off the fixed point iteration after some iterations. (See https://github.com/llvm/llvm-project/issues/154509)

Contributor guide

Open the contributing guide

Research direction

The issue provides a C++ cyclic-substitution example and benchmark results for the Lifetime Safety analysis, with loan propagation dominating runtime. Start by reproducing the “Pointer Cycle in Loop” case and tracing the fixed-point iteration; done means cyclic inputs no longer scale toward a timeout while preserving the intended analysis behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.