Skip to content
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 #49129

Closed
haoxintu opened this issue Mar 31, 2021 · 5 comments
Closed

[LoopUnroll] compile-time explosion with assumes at -O3 #49129

haoxintu opened this issue Mar 31, 2021 · 5 comments
Labels
bugzilla Issues migrated from bugzilla

Comments

@haoxintu
Copy link

Bugzilla Link 49785
Resolution FIXED
Resolved on Apr 16, 2021 07:08
Version trunk
OS Linux
CC @rotateright,@oToToT
Fixed by commit(s) bb907b2

Extended Description

Hi all.

$cat small.c
#include <stdint.h>
int a, b, c, d;
uint16_t e;
void f() {
uint16_t *g = &e;
int8_t *i = &a;
for (c = 5; c <= 63; c++)
for (*g = 9; *g <= 60; *g += 1)
if ((e ^ b) != d) {
int8_t *j = a;
for (*j = 3; *j <= 32; *j += 1)
if (*j)
for (*i = 1; *i <= 30;)
*i &= 0 == c;
}
}

$clang -w -O3 small.c
//endless compiling

$clang -v
clang version 13.0.0 (https://github.com/llvm/llvm-project 850fced)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/haoxin/haoxin-data/dut-research/compilers/llvm-project/build-20210330/bin
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/6
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/6.5.0
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/7
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/7.5.0
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

@rotateright
Copy link
Contributor

Unlike some of the other bugs, this one might not be an infinite loop, but a compile-time explosion from assumes. :)

The IR coming out of the loop vectorizer has a lot of assumes like this:
%3 = icmp eq <16 x i32> %2, %broadcast.splat20
%4 = extractelement <16 x i1> %3, i32 0
call void @​llvm.assume(i1 %4)
%5 = extractelement <16 x i1> %3, i32 1
call void @​llvm.assume(i1 %5)

It's then stuck at loop-unroll. That might be why we only notice the problem at -O3 and not -O2.

@rotateright
Copy link
Contributor

I reduced to this:

define void @​#49785 (i32 %d) {
entry:
br label %vector.ph

vector.ph: ; preds = %for.body4, %entry
%0 = phi i32 [ 5, %entry ], [ %inc, %for.body4 ]
%broadcast.splatinsert19 = insertelement <16 x i32> poison, i32 %d, i32 0
%broadcast.splat20 = shufflevector <16 x i32> %broadcast.splatinsert19, <16 x i32> poison, <16 x i32> zeroinitializer
br label %vector.body

vector.body: ; preds = %vector.body, %vector.ph
%index = phi i32 [ 0, %vector.ph ], [ %index.next, %vector.body ]
%1 = icmp eq <16 x i32> zeroinitializer, %broadcast.splat20
%2 = extractelement <16 x i1> %1, i32 4
call void @​llvm.assume(i1 undef)
%index.next = add i32 %index, 16
%3 = icmp eq i32 %index.next, 48
br i1 %3, label %for.body4, label %vector.body

for.body4: ; preds = %vector.body
%xor = xor i32 undef, undef
%cmp6.not = icmp eq i32 %xor, %d
call void @​llvm.assume(i1 %cmp6.not)
%inc = add nuw nsw i32 %0, 1
%cmp = icmp ult i32 %0, 63
br i1 %cmp, label %vector.ph, label %for.end34

for.end34: ; preds = %for.body4
ret void
}

declare void @​llvm.assume(i1 noundef) #​1


And it is taking a seemingly infinite time to compile with:

opt -S 49785min.ll -loop-unroll -unroll-threshold=239

But changing the unroll-threshold lower appears to make this compile instantly, so maybe it is an infinite loop...

@rotateright
Copy link
Contributor

We could blame/change a number of different passes in this example.

The initial assume is created by SimplifyCFG. But we decided that was ok in https://reviews.llvm.org/D97306 (although we suggested using https://llvm.org/docs/LangRef.html#assume-operand-bundles - although I'm not sure how to do that for branch conditions).

There may be a way to limit the damage that the LoopVectorizer is causing by duplicating the initial assume.

If not, I think we will have to look at not duplicating assumes within LoopUnroll.

@rotateright
Copy link
Contributor

If not, I think we will have to look at not duplicating assumes within
LoopUnroll.

Proposal:
https://reviews.llvm.org/D99759

@rotateright
Copy link
Contributor

We took a different approach in:
https://reviews.llvm.org/D100573

Committed at:
https://reviews.llvm.org/rGbb907b26e2bf

IR test case derived from the source in this report added with:
https://reviews.llvm.org/rG437fb4281787

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 11, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla
Projects
None yet
Development

No branches or pull requests

2 participants