Loop unswitching creates dead code

Project Infrastructure LLVM Dev List Archives
#1

Hi,

I’m surprised by the result of compiling the following lines of code:

for (int i = 0; i < RANDOM_CHUNKS; i++) {
    for (int j = 0; j < RANDOM_CHUNK_SIZE; j++) {
        random_text[i][j] = (int)(ran()*256);
    }
}

The problem happens when -fsanitize=undefined, -fno-sanitize-recover and -O3 are enabled. In this case, UndefinedBehaviorSanitizer inserts check for array index out of bounds, and for cast-to-int overflow. The loop unswitching pass presumably tries to move these out of the loops. Thereby, the loop condition of the outer loop gets duplicated, and one of the copies branches to a dead block.

This is a problem at the interplay between multiple optimization passes. Maybe there isn’t an easy solution. But I thought I’d post it here since people might be interested.

Attached are a complete C file reproducing the problem, as well as the resulting Bitcode. Compilation was done using clang -Wall -g -flto -O3 -fsanitize=undefined -fno-sanitize-recover -c weird_loop.c

Cheers,
Jonas

weird_loop.c (311 Bytes)

weird_loop.o.ll (11.8 KB)

#2

In the future please be a bit more specific about which blocks
correspond to your unexpected behavior, it'd help folks understand
your issue :).

Anyway, looking at the IR for a bit I think I see what might be
confusing (other than sanitizers making control flow extra fun :)):

There are two comparisons similar to the outer loop condition:

  %0 = icmp ult i32 %i.042, 32, !dbg !20

And:

  %cmp = icmp slt i32 %26, 32, !dbg !19

The first check, if it fails, branches to a block that necessarily
calls one of two sanitizer abort functions.

Observations:

1) The first check is an ULT, stronger than the SLT used later and
specified in your source as the outer loop condition. This is
significant, and helps explain why when the check fails the program
will necessarily call one of two abort functions as it's not a loop
condition check but rather a bounds check:

2)If the ULT fails (somehow 'i' is larger than 32 when interpreted as
unsigned!), if the code makes it to the array access it will be an
out-of-bounds access. However, if the code encounters a float-to-int
error before this happens, the float abort handler will be called
instead. This explains the resulting control-flow that is followed
should the first check fail.

3)This code is certainly sub-optimal, unfortunately. It seems LLVM is
unable to reason about the loops effectively when instrumented by the
sanitizers, likely at least partially due to the increment
instructions being replaced with overflow-checking intrinsics.
There's more to it, however, since it seems building with only
-sanitize=bound LLVM is able to optimize away the check on 'i', but
not the check for 'j'.

Anyway, AFAICT nothing is 'dead' and the code is correct if a bit
more complicated than one might like :).
Let me know if anything was unclear or you have any further questions.

Hope this helps,
~Will

#3

Hi,

Thanks a lot for the detailed explanation!

I did not pay attention to the difference between signed and unsigned less-than. Indeed the unsigned check is necessary because the index could be negative (and hence out of bound).

This shows me that I need to be more careful when making assumptions about code… I hope I’ll learn the lesson. Thanks again.

  • Jonas