Lifetime safety can timeout on cyclic substitution in a loop
- 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
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