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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140407/9d48be17/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: weird_loop.c
Type: text/x-csrc
Size: 311 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140407/9d48be17/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: weird_loop.o.ll
Type: application/octet-stream
Size: 12089 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140407/9d48be17/attachment.obj>
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 >
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>