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

[haoxintu]

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]

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]

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]

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]

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

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

[rotateright]

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