<div dir="ltr"><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 8, 2020 at 12:12 PM Juneyoung Lee via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">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 dir="ltr"><div>Hello all,<br></div><div><br></div><div>Thank everyone who participated in the (impromptu) round table discussion on Tuesday.</div><div>For those who are interested, I share the summary of the discussion.</div><div>Also, I share a short-term plan regarding this issue and relevant patches.</div><div><br></div><div><br></div><div><b>Fixing Miscompilations using Freeze</b></div><div>-----------------------------------</div><div><br></div><div>To reduce the cost of fixing miscompilations using freeze instruction, we need to</div><div>optimize freeze away whenever possible.</div><div>Using the no-undef/poison assumption from the source language (C/C++ in</div><div>this context) can play a significant role.</div><div>To make use the assumptions, here are short-term goals:</div><div><br></div><div><b>1. Preserve no-undef/poison assumption of function arguments from C/C++ when valid.</b></div><div><br></div><div>There is an ongoing relevant patch (that is written by others):</div><div><a href="https://reviews.llvm.org/D81678" target="_blank">https://reviews.llvm.org/D81678</a></div><div><br></div><div><b>2. Preserve no-undef/poison assumption of lvalue reads in C/C++ when valid.</b></div><div><br></div><div>Reading an indeterminate value from an lvalue that does not have char or</div><div>std::byte type is UB [1].</div><div>Since reading an lvalue is lowered to `load` in IR, we suggest attaching a new</div><div>!noundef metadata to such `load`s.</div><div>The IR-side change is here: <a href="https://reviews.llvm.org/D89050" target="_blank">https://reviews.llvm.org/D89050</a></div><div>The clang-side change is going to be made after D81678 is reviewed, because it is likely</div><div>that this patch will have a lot of changes in clang tests.</div><div><br></div><div><br></div><div><b>Replacing Undef with Poison</b></div><div>---------------------------</div><div><br></div><div>Since undef is known to be the source of many optimizations due to its complexity,</div><div>we'd like to suggest gradually moving towards using poison only.</div><div>To make it, (1) `poison` constant should be introduced into LLVM IR first, and (2)</div><div>transformations that introduce `undef` should be updated to introduce `poison` instead.</div><div><br></div><div>For the step (2), we need an experimental result showing that it does not cause</div><div>performance degradation. This relies on better support for freeze (the</div><div>no-undef/poison analysis patches).</div><div><br></div><div><b>1. Introduce a new `poison` constant into IR</b>: <a href="https://reviews.llvm.org/D71126" target="_blank">https://reviews.llvm.org/D71126</a></div><div><br></div><div>Note that `poison` constant can be used as a true placeholder value as well.</div><div>Undef cannot be used in general because it is less undefined than poison.</div><div><br></div><div><b>2. Update transformations that introduce `undef` to introduce `poison` instead</b></div><div><br></div><div>(1) There are transformations that introduce `undef` as a placeholder (e.g. phi operand</div><div>from an unreachable block).</div><div>For these, `poison` can be used instead.</div><div><br></div><div>(2) The value of an uninitialized object (automatic or dynamic).<br></div><div>They are indeterminate values in C/C++, so okay to use poison instead.</div><div>A tricky case is a bitfield access, and we have two possible solutions:</div><div><br></div><div>- i. Introduce a very-packed struct type</div><div>```</div><div><font face="monospace"><C></font></div><div><font face="monospace">struct {</font></div><div><font face="monospace"> int a:2, b:6;</font></div><div><font face="monospace">} s;</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">v = s.a;</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">=></font></div><div><font face="monospace"><br></font></div><div><font face="monospace"><IR></font></div><div><font face="monospace"><br></font></div><div><font face="monospace">s = alloca</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">tmp = load <b><u>{{i2, i6}}</u></b>* s ; load as a very packed struct type</font></div><div><font face="monospace">v = extractvalue tmp, 0</font></div><div>```</div><div> * Pros: Can be used to precisely lower C/C++'s struct typed function argument into IR </div><div>(currently clang coerces a struct into int if small enough; I'll explain about this detail if anyone requests)</div><div> * Cons: Since optimizations aren’t aware of the new type, they should be updated</div><div><br></div><div>- ii. Use load-freeze</div><div>```</div><div><font face="monospace"><C></font></div><div><font face="monospace">struct {</font></div><div><font face="monospace"> int a:2, b:6;</font></div><div><font face="monospace">} s;</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">v = s.a;</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">=></font></div><div><font face="monospace"><br></font></div><div><font face="monospace"><IR></font></div><div><font face="monospace">s = alloca</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">// Poison bits are frozen and returned</font></div><div><font face="monospace">tmp = <b><u>load freeze</u></b> i8* s</font></div><div><font face="monospace">v = tmp & 3</font></div><div>```</div><div> * Pros: The change is simpler</div><div> * Cons: Store forwarding isn’t free; needs insertion of freeze</div><div> (store x, p; v = load freeze p => store x, p; v = freeze x)</div><div><br></div><div><br></div><div>(3) The third case is the value of struct/union padding.</div><div>Padding is filled with unspecified value in C, so it is too undefined to use poison.</div><div>We can fill it with defined bits nondeterministically chosen at allocation time (freeze poison).</div><div><br></div><div>```</div><div><font face="monospace"><C></font></div><div><font face="monospace">struct {</font></div><div><font face="monospace"> char a; // 3 bytes padding</font></div><div><font face="monospace"> int b;</font></div><div><font face="monospace">} s;</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">v = s.b;</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">=></font></div><div><font face="monospace"><br></font></div><div><font face="monospace"><IR></font></div><div><font face="monospace">s = alloca {i8, i32} // alloca initializes bytes in a type-dependent manner</font></div><div><font face="monospace">// s[0], s[4~7]: poison</font></div><div><font face="monospace">// s[1~3]: let's fill these bytes with nondet. bits</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">s2 = gep (bitcast s to i8*), 4</font></div><div><font face="monospace">v = load i32 s2</font></div><div>```</div><div><br></div><div><br></div><div>Thanks,</div><div>Juneyoung</div><div><br></div><div><br></div><div><br></div><div>[1]</div><div>C11 6.2.6.1.5: If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined.</div><div>(Similarly, C17 6.2.6.1.5)</div></div></div></blockquote><div>It is important to note that this applies to trap representations and not to unspecified values. A structure or union never has a trap representation.<br></div><div> </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 dir="ltr"><div>C++14 8.5.12: If an indeterminate value is produced by an evaluation, the behavior is undefined except in the following cases: If an indeterminate value of unsigned narrow character type ...</div><div>(Similarly, C++17 11.6.12 , C++11 4.1.1)</div></div></div></blockquote><div>While loading undef for the unsigned character type case merely produces undef, for C++, operations such as sign-extend or zero-extend on an undef i8 is also undefined behaviour.<br></div><div> </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 dir="ltr"><div><br></div></div></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></div>