-
Notifications
You must be signed in to change notification settings - Fork 12.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[LoopUnroll] compile-time explosion with assumes at -O3 #48515
Comments
The bug seems to be in either LoopUnroll or ValueTracking's isKnownNonEqual() and has something to do with @llvm.assume() replication/analysis. Also, this is not actually an infinite loop. If you adjust the for-loop constants down from 78/73, you can see the compile-time explosion in progress before it becomes intolerable: time with "21, 16": user 0m3.467s That's why the bug only becomes noticeable at -O3 rather than -O2. We use more aggressive unrolling parameters at O3. cc'ing @nikic and @jdoerfert in case this might be related to https://reviews.llvm.org/D96208 ? |
We generate a total of #144 assumptions which should not be enough to cause a problem by itself. From a quick look at this I see: I imagine we look at a decent chunk of the 144 assumes for every if(b) branch in the unrolled loop, probably in a non-linear way? |
IR test case: @a = dso_local global i32 0, align 4 define dso_local void @e() local_unnamed_addr #0 { for.cond1.preheader: ; preds = %entry, %for.cond1.preheader for.end11: ; preds = %for.cond1.preheader declare void @llvm.assume(i1) Run with -loop-unroll -unroll-threshold=300. |
A bit smaller: define void @test(i32 %arg) { loop: exit: declare void @llvm.assume(i1) I think that at least a large part of the problem is that we allow an unbounded scan to find non-dominating but guaranteed-to-execute assumes. We should limit that. |
Yes, that seems to work. This makes the example compile fast: diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
|
Note that there's an instcombine test for that chunk of code added with: I don't know if that test had any intent of checking the actual distance between assume and its context inst, but if we want to preserve it, we'd make the ScanLimit = 15 in my draft patch. Let me know if I should post that on Phab and/or we want to do any compile-time-tracking experiments to find a better limit. |
+1 for distance checks If we are looking at this, we should add early exit various places or to look at |
@spatel Your patch with a limit of 15 looks fine to me. I don't think we need to do further experiments, as this is a question of worst-case complexity rather than average-case performance. |
Thanks! Committed the quick fix here - https://reviews.llvm.org/rG378941f611ab I think that's enough to say this bug is fixed, but reopen if I got that wrong. I haven't been following the details of guaranteed progress discussions, so not sure how to test this...does this correctly implement the suggested check for function attributes? diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
|
Thanks for the quick fixing! Cheers, |
Extended Description
Hi, all.
This code, s.c, is a valid program but makes Clang hung on with -O3 at compile time.
$cat s.c
int a, b, c, d;
void e() {
a = 7;
for (; a <= 78; a++) {
d = 3;
for (; d <= 73; d++) {
int f = 0;
b += c;
if (b) {
int g = 0;
for (f = 5; f; g)
;
}
}
}
}
$clang -c -w -O3 s.c
//endless compiling
This problem only occurs in clang-trunk with -O3, and other released versions or optimization flags seem well while dealing with this case.
$clang -v
clang version 13.0.0 (https://github.com/llvm/llvm-project 48bdd67)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/haoxin/haoxin-data/dut-research/compilers/llvm-project/build-20210127/bin
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/8
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7.5.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/8
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/8
Candidate multilib: .;@m64
Selected multilib: .;@m64
Thanks.
Haoxin
The text was updated successfully, but these errors were encountered: