clang crashes at -O3 with both newgvn and polly: Instruction does not dominate all uses!

[llvmbot]

Bugzilla Link	34687
Resolution	FIXED
Resolved on	Oct 03, 2017 08:04
Version	unspecified
OS	All
Reporter	LLVM Bugzilla Contributor
CC	@alexey-bataev,@dtemirbulatov,@etherzhhb,@tobiasgrosser

Extended Description

Unlike Bug 32795, the crash happens in 32-bit mode with both newgvn and polly enabled.

$ clang-trunk -v
clang version 6.0.0 (trunk 313740) (llvm/trunk 313739)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/bin

$ clang-trunk -mllvm -polly -mllvm -enable-newgvn -O3 -m32 abc.c
Instruction does not dominate all uses!
%118 = add <16 x i32> %vec.phi, %116
%16 = and <16 x i32> %118, <i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255>
Instruction does not dominate all uses!
%119 = add nuw nsw <16 x i32> %vec.phi94, %117
%17 = and <16 x i32> %119, <i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255, i32 255>
fatal error: error in backend: Broken function found, compilation aborted!
clang-6.0: error: clang frontend command failed with exit code 70 (use -v to see invocation)
clang version 6.0.0 (trunk 313740) (llvm/trunk 313739)
Target: i386-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/bin
clang-6.0: note: diagnostic msg: PLEASE submit a bug report to http://llvm.org/bugs/ and include the crash backtrace, preprocessed source, and associated run script.
clang-6.0: note: diagnostic msg:

---

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-6.0: note: diagnostic msg: /tmp/abc-fa66e6.c
clang-6.0: note: diagnostic msg: /tmp/abc-fa66e6.sh
clang-6.0: note: diagnostic msg:

---

$ cat abc.c
char a, b = 8, i = 0;
long c, g;
short d, h, j;
int e, f;
int *k;
void fn1() {
long l = c;
for (; g;) {
l1:
for (; l;)
;
if (f)
goto l1;
for (; j <= 2; j++) {
e = b;
a += (b = 0) || i ? *k %= h : (f || d / h) & (l = j || j / e);
}
}
}

[etherzhhb]

Maybe polly do not update the dominator correctly.

[tobiasgrosser]

AFAIK Polly does not do something totally stupid. We need to reduce it with bugpoint to a short sequence of bugs.

[llvmbot]

Reproduces with loop vectorize only (just run opt-bisect and stop right before the loop vectorizer):

$ ./opt -loop-vectorize blah.ll

Instruction does not dominate all uses!
%158 = add nuw nsw <16 x i32> %156, %154
%19 = trunc <16 x i32> %158 to <16 x i8>
Instruction does not dominate all uses!
%159 = add nuw nsw <16 x i32> %157, %155
%21 = trunc <16 x i32> %159 to <16 x i8>
LLVM ERROR: Broken function found, compilation aborted!

[llvmbot]

reduced

[llvmbot]

CC:ing people who touched the vectorizer recently.

[tobiasgrosser]

Trying to assign this to the generic LLVM optimizer, as this is not a new bug.

[alexey-bataev]

The problem is in LoopVectorizer, not SLPVectorizer

[llvmbot]

Reduced (opt -loop-vectorize)

target triple = "x86_64-unknown-linux-gnu"

define void @​patatino() {
bb:
br i1 undef, label %bb2, label %bb1

bb1: ; preds = %bb12, %bb1, %bb
br label %bb1

bb2: ; preds = %bb
br label %bb3

bb3: ; preds = %bb7, %bb2
%tmp = phi i32 [ undef, %bb2 ], [ %tmp9, %bb7 ]
%tmp4 = phi i32 [ undef, %bb2 ], [ %tmp10, %bb7 ]
br i1 true, label %bb5, label %bb7

bb5: ; preds = %bb3
%tmp6 = sdiv i32 undef, undef
br label %bb7

bb7: ; preds = %bb5, %bb3
%tmp8 = and i32 %tmp, 255
%tmp9 = add nuw nsw i32 %tmp8, undef
%tmp10 = add nsw i32 %tmp4, 1
%tmp11 = icmp eq i32 %tmp10, 3
br i1 %tmp11, label %bb12, label %bb3

bb12: ; preds = %bb7
%tmp13 = phi i32 [ %tmp9, %bb7 ]
br label %bb1
}

[llvmbot]

The issue seems to be that the loop vectorizer doesn't always take in account dominance when inserting instructions.

The body contains:

vector.body: ; preds =
[....]
%1 = add i32 %offset.idx, 16
%2 = trunc <16 x i32> %72 to <16 x i2>
%3 = zext <16 x i2> %2 to <16 x i32>
%4 = trunc <16 x i32> %73 to <16 x i2>
%5 = zext <16 x i2> %4 to <16 x i32>
br i1 true, label %pred.sdiv.if, label %pred.sdiv.continue
[....]

And pred.sdiv.continue64 contains:

pred.sdiv.continue64: ; preds = %pred.sdiv.if63, %pred.sdiv.continue62
%69 = phi i32 [ undef, %pred.sdiv.continue62 ], [ %68, %pred.sdiv.if63 ]
%70 = and <16 x i32> %vec.phi, <i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3>
%71 = and <16 x i32> %vec.phi1, <i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3, i32 3>
%72 = add nuw nsw <16 x i32> %70, undef
%73 = add nuw nsw <16 x i32> %71, undef
%index.next = add i32 %index, 32
%74 = icmp eq i32 %index.next, undef
br i1 %74, label %middle.block, label %vector.body, !llvm.loop !​0

%72 is used to compute %2, but the block where the DEF of %72 appears doesn't really dominate the vector.body block

[llvmbot]

Thanks for simplifying the bug, Davide! I think we're getting the insertion point wrong when type-shrinking reductions. I'll take look.

[llvmbot]

This fix is fairly simple - when type-shrinking reductions, we truncate (then extend) the incoming value to the reduction phi so that Instcombine will be able to rewrite the expression in the smaller type. We insert these instructions at the end of the loop. The insert point is:

LoopVectorBody->getTerminator()

But in this test case, we had to scalarize and predicate the sdiv instructions. So LoopVectorBody->getTerminator() is no longer the loop latch. We need to change the insert point to:

LI->getLoopFor(LoopVectorBody)->getLoopLatch()->getTerminator()

I'll submit the patch later today after testing.

[llvmbot]

Should be fixed by https://reviews.llvm.org/rL314542.