[LLVMdev] Loop unswitching creates dead code

[Jonas Wagner]

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
On Apr 8, 2014 7:02 PM, "Will Dietz" <willdtz at gmail.com> wrote:

> 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
>
> On Mon, Apr 7, 2014 at 11:24 AM, Jonas Wagner <jonas.wagner at epfl.ch>
> wrote:
> > 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
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140409/2033a682/attachment.html>