| Issue |
75666
|
| Summary |
JumpThreading blows up LLVM IR size by a factor of N^2 with @llvm.lifetime.end instrinsic
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
terrelln
|
# Repro
This issues causes compiling a file with `-O3 -fsanitize=fuzzer` to take hours and exhibit N^3 behavior or worse.
1. Download the file [TimeZoneDatabase.cpp](https://github.com/facebookincubator/velox/blob/3bb636b4d97b9b661a94804c0007752aa3edade3/velox/type/tz/TimeZoneDatabase.cpp)
2. `clang++ -O3 -fsanitize=fuzzer TimeZoneDatabase.cpp` and see that it runs for hours
3. Disable the `JumpThreadingPass` and re-run the compilation, and see that it finishes in ~5 minutes
# Debugging
@apolloww profiled and saw that a lot of time was being spent inside of DCE, specifically eliminating dead lifetime intrinsics here:
https://github.com/llvm/llvm-project/blob/d6f772074c48cf9bb57191cb065b5ce60012ed74/llvm/lib/Transforms/Utils/Local.cpp#L486-L491
That led me to find out that the `JumpThreadingPass` was blowing up the code size by a factor of N^2 in the size of the map.
If I truncate the map to the first 3 elements and print the IR before/after the first `JumpThreadingPass` I see this:
https://gist.github.com/terrelln/f8ac8f1b8caf83590a829c5d9d88e471
Specifically before `JumpThreadingPass` the cleanup blocks look like this:
```ll
35: ; preds = %13
%36 = landingpad { ptr, i32 }
cleanup
br label %60
37: ; preds = %14
%38 = landingpad { ptr, i32 }
cleanup
br label %56
39: ; preds = %16
%40 = landingpad { ptr, i32 }
cleanup
br label %53
```
After the `JumpThreadingPass` they look like this:
```
34: ; preds = %13
%35 = landingpad { ptr, i32 }
cleanup
call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %2) #13
br label %67
36: ; preds = %14
%37 = landingpad { ptr, i32 }
cleanup
call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %3) #13
call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %2) #13
br label %54
38: ; preds = %16
%39 = landingpad { ptr, i32 }
cleanup
call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %4) #13
call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %3) #13
call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %2) #13
br label %54
```
You can see the first block has one `@llvm.lifetime.end` intrinsics, the second has two, and the third has three. This extends all the way to the 2234 entries that the original file has, leading to (2234 * 2235) / 2 = 2,496,495 `@llvm.lifetime.end` intrinsics.
Normally, the `JumpThreadingPass` has a limit in how many instructions it will duplicate controlled by [BBDuplicateThreshold](https://github.com/llvm/llvm-project/blob/aaa3f72c1ce6e1757df79c0d02e0675201ee07a3/llvm/lib/Transforms/Scalar/JumpThreading.cpp#L88-L91). However, [lifetime annotation intrinsics have a cost of 0](https://github.com/llvm/llvm-project/blob/aaa3f72c1ce6e1757df79c0d02e0675201ee07a3/llvm/include/llvm/Analysis/TargetTransformInfoImpl.h#L719), so it is allowed to blow up the LLVM IR temporarily, since it will eventually be cleaned up.
This is all fine when the number of intrinsics added is sane, but when adding 2 million extra intrinsics, that ends up slowing down later passes quadratically. Specifically, now each of the N `%2 = alloca i32, align 4` has up to N `@llvm.lifetime.end` uses, which really slows down [wouldInstructionBeTriviallyDead](https://github.com/llvm/llvm-project/blob/d6f772074c48cf9bb57191cb065b5ce60012ed74/llvm/lib/Transforms/Utils/Local.cpp#L486-L491) because it iterates over all of them.
# Fix
Ultimately, I think `JumpThreadingPass` should refuse to duplicate blocks with too many instructions, including intrinsics. Or stop if it has grown the total IR size by a certain factor. However, I don't know what would be the most sane way to approach this, since I'm not familiar with the code.
If someone has a pointer to how they would like it fixed, I'd be interested in putting up a PR.
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
