<div dir="ltr"><div>I was just able to determine the offending IR code before and after the transformation. I'm now almost certain it's a bug in LLVM.</div><div><br></div><div>Before transformation, we have the following IR (I renamed all %xxx for brevity):</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><span style="font-family:monospace">%1 = load i8, i8* %0, align 1<br>%2 = add i8 %1, -1<br>store i8 %2, i8* %0, align 1</span></div></blockquote><div>The above IR is inside a loop, so the value in %0 can be different in each run.<br></div><div><br></div><div>The optimization pass changed the IR above to the following:</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><span style="font-family:monospace">store i8 %3, i8* %0, align 1</span></div></blockquote><div>where %3 is defined by</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><span style="font-family:monospace">%4 = load i8, i8* %0, align 1<br>%3 = add i8 %4, -1</span></div></blockquote><div>in an earlier piece of IR.</div><div><br></div><div>Apparently the pass treated %3 the same thing as %2 and it fired CSE, without realizing that the content in %0 may have been changed by the loop.<br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">David Blaikie <<a href="mailto:dblaikie@gmail.com">dblaikie@gmail.com</a>> 于2020年10月21日周三 下午10:18写道：<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Might be worth running the c source file through creduce or similar to narrow it down a bit that way too.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Oct 21, 2020 at 9:12 PM Haoran Xu via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>A further bisect using opt's <span style="font-family:monospace">-opt-bisect-limit</span> option shows that the following pass is causing the issue:</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>BISECT: running pass (39) Early CSE w/ MemorySSA on function (main)<br></div></blockquote><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Haoran Xu <<a href="mailto:haoranxu510@gmail.com" target="_blank">haoranxu510@gmail.com</a>> 于2020年10月21日周三 下午9:00写道：<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>I did a simple bisect on clang version, and it seems like clang 8.0.0 works correctly, but clang 9.0.0 failed to compile the code correctly.</div><div><a href="https://godbolt.org/z/676Grr" target="_blank">https://godbolt.org/z/676Grr</a> <- if you change the clang version to 8.0.0, you will see the expected output in 'output' section.</div><div>I don't have the ability to bisect on clang git history. I would greatly appreciate it if any one is willing to do that.<br></div><div><br></div><div>Thanks!<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Haoran Xu <<a href="mailto:haoranxu510@gmail.com" target="_blank">haoranxu510@gmail.com</a>> 于2020年10月21日周三 下午8:47写道：<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hello,</div><div><br></div><div>I'm really amazed to find out that
under -O3, a simple piece of C code generated from a brainfxxk-to-C
transpiler is miscompiled. <br></div><div>As one probably know, the C code transpiled from brainfxxk only contains 3 kind of statements: <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>(1) ++(*ptr) / --(*ptr) <br></div><div>(2) ++ptr / --ptr <br></div><div>(3) while (*ptr) { ... }</div></blockquote><div> where ptr is a uint8_t*. <br></div><div>So
it seems very clear to me that the code contains no undefined behavior
(the pointer is uint8_t* and unsigned integer overflow is not UD). <br></div><div><br> </div><div>After further investigation, it seems like clang compiled this loop:</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div> <span style="font-family:monospace">while (*ptr) {<br> --(*ptr);<br> ++ptr;<br> ++(*ptr);<br> --ptr;<br> }</span></div></blockquote><div> to an unconditional infinite loop under -O3, resulting in the bug. The code snippet above seems completely benign to me. <br></div><div><br></div><div>I attached the offending program. With <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>clang a.c -O0</div></blockquote><div>it
worked fine (it should print out an ASCII-art picture of mandelbrot
fracture). However, with -O1 or -O3, it goes into a dead loop (in the
code snippet above) after printing out a few characters.</div><div><br></div><div>I also tried UndefinedBehaviorSanitizer. Strangely, when compiling using <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>clang a.c -O3 -fsanitize=undefined</div></blockquote><div>the code worked again, with no infinite loop, and no undefined behavior reported.</div><div><br></div><div>So it seems to me a LLVM optimizer bug. I would greatly appreciate if any one is willing to investigate.</div><div><br></div><div>Best,</div><div>Haoran<div><br><br></div></div></div>
</blockquote></div>
</blockquote></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</blockquote></div>