<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Okay, it's just not immediately undefined behaviour. The C model has more issues because of the problem with how "trap representation" is defined (which precludes trap representations for unsigned char, two's complement signed char, etc.). </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">This interpretation is further stressed because C only explicitly ascribes undefined behaviour to trap representations on loads and stores.</blockquote><div dir="ltr"><br></div><div>In this case, freeze(poison) can be used to represent an uninitialized value, because using freeze(poison) never raises UB.</div><div>However, I couldn't find relevant statements from C standard about these two. Could you elaborate a bit more please?</div><div><br></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Thanks for raising this. So, it can be that there are:<br>- values that induce broader undefined behaviour (with certain operations),<br>- values that may change on their own, and<br>- values that become defined to an unspecified value (not of the first category) at some point in time. </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"> </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">The unspecified values put into padding in C appear to be in the last category. Is that how LLVM treats them?</blockquote></div><div><br></div><div>With the current version of LLVM, there is slightly a gap, and with our suggestion this becomes correct.</div><div><a href="https://godbolt.org/z/nxhnTK">https://godbolt.org/z/nxhnTK</a><br></div><div>Reading padding is optimized to undef, but according to the previous link (<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1787">http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1787</a>), this isn't valid because unspecified value is a 'stable' value.</div><div>In our suggestion, well-defined bits are stored into padding at object creation, so it becomes okay.</div><div><br></div><div>Juneyoung</div><div><br></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Oct 9, 2020 at 11:58 PM Hubert Tong <<a href="mailto:hubert.reinterpretcast@gmail.com">hubert.reinterpretcast@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 8, 2020 at 11:54 PM Juneyoung Lee <<a href="mailto:juneyoung.lee@sf.snu.ac.kr" target="_blank">juneyoung.lee@sf.snu.ac.kr</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><blockquote class="gmail_quote" style="color:rgb(0,0,0);margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><font face="monospace">// Members are initialized to poison at object creation.<br></font><font face="monospace">p = alloca {i8, i32} // p[0], p[4~7] are poison<br></font>p[0] is an i8, so it shouldn't be poison?</blockquote></div></div></div></blockquote></div><div dir="ltr"><br></div><div>My interpretation of standard is that reading uninitialized char can also yield trap representation.</div><div>If uninitialized, char variable has indeterminate value, and C/C++ does not seem to forbid reading trap representation from it.</div></div></div></div></div></div></blockquote><div>Okay, it's just not immediately undefined behaviour. The C model has more issues because of the problem with how "trap representation" is defined (which precludes trap representations for unsigned char, two's complement signed char, etc.). This interpretation is further stressed because C only explicitly ascribes undefined behaviour to trap representations on loads and stores.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>C++14 explicitly has an example that shows it is indeterminate value at 3.3.2.1 :</div><div>```</div><div><div>The point of declaration for a name is immediately after its complete declarator (Clause 8) and before its initializer (if any), except as noted below. [Example:</div><div> unsigned char x = 12;</div><div> { unsigned char x = x; }</div><div>Here the second x is initialized with its own (<u>indeterminate</u>) value. —end example]</div></div><div>```</div><div><br></div><div>It seems there was a phrase saying that reading indeterminate value as an unsigned char should yield unspecified value in the C++14 draft in the past, but it is removed: <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1787" target="_blank">http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1787</a></div><div>The removed phrase did not exist in C++11, so I believe it is fine to use poison for uninitialized char types.</div></div></div></div></div></div></blockquote>Thanks for raising this. So, it can be that there are:</div><div class="gmail_quote">- values that induce broader undefined behaviour (with certain operations),</div><div class="gmail_quote">- values that may change on their own, and<br></div><div class="gmail_quote">- values that become defined to an unspecified value (not of the first category) at some point in time.</div><div class="gmail_quote"><br></div><div class="gmail_quote">The unspecified values put into padding in C appear to be in the last category. Is that how LLVM treats them?<br><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><br></div><div>Juneyoung</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Oct 9, 2020 at 12:19 PM Hubert Tong <<a href="mailto:hubert.reinterpretcast@gmail.com" target="_blank">hubert.reinterpretcast@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 8, 2020 at 11:09 PM Juneyoung Lee <<a href="mailto:juneyoung.lee@sf.snu.ac.kr" target="_blank">juneyoung.lee@sf.snu.ac.kr</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>It is UB when a poison is passed to certain operations that raise UB on poison, such as division by poison/dereferencing poison pointer/branching on poison condition/etc.</div></div></div></div></blockquote><div>Got it. Thanks.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>Otherwise, poison is simply propagated, but it does not raise UB<br></div><div>Copying poison bytes is okay:<br><div><br></div><div><font face="monospace">// Members are initialized to poison at object creation.</font></div><div><font face="monospace">p = alloca {i8, i32} // p[0], p[4~7] are poison</font></div></div></div></div></div></blockquote><div>p[0] is an i8, so it shouldn't be poison?<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><font face="monospace">q = alloca {i8, i32} // we want to copy p to q</font></div><div><font face="monospace">v = load i8* p[0] // v is poison</font></div><div><font face="monospace">store i8 v, i8* q[0] // poison is simply copied; no UB happened</font></div></div><div><br></div><div>Similarly, passing/returning poison is allowed as well.</div><div><br></div><div>Juneyoung</div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Oct 9, 2020 at 10:45 AM Hubert Tong <<a href="mailto:hubert.reinterpretcast@gmail.com" target="_blank">hubert.reinterpretcast@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 8, 2020 at 7:13 PM Juneyoung Lee <<a href="mailto:juneyoung.lee@sf.snu.ac.kr" target="_blank">juneyoung.lee@sf.snu.ac.kr</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr">> 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.</div><div>Yes, nondeterministic bits would work for padding of struct/union, as described in (3) The third case is the value of struct/union padding.</div><div>For the members of struct/union, it is allowed to have trap representation, so poison can be used.</div></div></div></blockquote><div>At what point are the members considered poison? For copying/passing/returning a struct or union, there is no UB even if some members are uninitialized.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><br></div><div>Juneyoung</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Oct 9, 2020 at 5:37 AM Hubert Tong <<a href="mailto:hubert.reinterpretcast@gmail.com" target="_blank">hubert.reinterpretcast@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><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" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color: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-width:1px;border-left-style:solid;border-left-color: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-width:1px;border-left-style:solid;border-left-color: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>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div>
</blockquote></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div>
</blockquote></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div></div></div></div></div></div></div></div></div>