<div dir="ltr"><div dir="ltr">On Tue, Jun 15, 2021 at 4:07 PM John McCall <<a href="mailto:rjmccall@apple.com" target="_blank">rjmccall@apple.com</a>> wrote:<br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><u></u>




<div>
<div style="font-family:sans-serif"><div style="white-space:normal">
<p dir="auto">On 15 Jun 2021, at 1:49, Juneyoung Lee wrote:</p>

</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid rgb(57,131,196);color:rgb(57,131,196);margin:0px 0px 5px;padding-left:5px"><p dir="auto">On Tue, Jun 15, 2021 at 1:08 AM John McCall via llvm-dev <<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
</p>
<blockquote style="border-left:2px solid rgb(124,191,12);color:rgb(124,191,12);margin:0px 0px 5px;padding-left:5px"><p dir="auto">The semantics you seem to want are that LLVM’s integer types cannot carry<br>
information from pointers. But I can cast a pointer to an integer in C and<br>
vice-versa, and compilers have de facto defined the behavior of subsequent<br>
operations like breaking the integer up (and then putting it back<br>
together), adding numbers to it, and so on. So no, as a C compiler writer,<br>
I do not have a choice; I will have to use a type that can validly carry<br>
pointer information for integers in C.<br>
</p>
</blockquote><p dir="auto">int->ptr cast can reconstruct the pointer information, so making integer<br>
types not carry pointer information does not necessarily mean that<br>
dereferencing a pointer casted from integer is UB.</p>
</blockquote></div>
<div style="white-space:normal">

<p dir="auto">What exactly is the claimed formal property of byte types, then,<br>
that integer types will lack?  Because it seems to me that converting<br>
from an integer gives us valid provenance in strictly more situations<br>
than converting from bytes, since it reconstructs provenance if there’s<br>
any object at that address (under still-debated restrictions),<br>
while converting from bytes always preserves the original provenance<br>
(if any).  I don’t understand how that can possibly give us <em>more</em><br>
flexibility to optimize integers.</p></div></div></div></blockquote><div>When two objects are adjacent, and an integer is exactly pointing to the location between them, its provenance cannot be properly recovered.</div><div><br></div><div>int x[1], y[1];</div><div>llvm.assume((intptr_t)&x[0] == 0x100 && (intptr_t)&y[0] == 0x104);</div><div></div><div>int *p = (int*)(intptr_t)&x[1];</div><div>// Q: Is p's provenance x or y?</div><div><br></div><div>If it is expected that '*(p-1)' is equivalent to *x, p's provenance should be x.</div><div>However, based on llvm.assume, optimizations on integers can replace (intptr_t)&x[1] with (intptr_t)&y[0] (which is what happened in the bug report).</div><div>Then, '*(p-1)' suddenly becomes out-of-bounds access, which is UB.</div><div>So, p's provenance isn't simply x or y; it should be something that can access both x and y.</div><div><br></div><div>This implies that, unless there is a guarantee that all allocated objects are one or more bytes apart, there is no type that can perfectly store a pointer byte.</div><div>memcpy(x, y, 8) isn't equivalent to 'v=load i64 y;store i64 v, x' because v already lost the pointer information.</div><div><br></div><div><br></div><div>The pointer information is perfectly stored in a byte type. But, arithmetic property-based optimizations such as the above one are not correct anymore.</div><div>Here is an example with a byte-type version:</div><div><br></div><div><div>int x[1], y[1];</div><div>// byte_8 is a 64-bits byte type<br></div><div>llvm.assume((byte_8)&x[0] == 0x100 && (byte_8)&y[0] == 0x104);</div><div></div><div>int *p = (int*)(byte_8)&x[1]; </div><div></div></div><div>// p's provenance is alway x.</div><div><br></div><div>For a byte type, equality comparison is true does not mean that the two values are precisely equal.</div><div>Since (byte_8)&x[1] and (byte_8)&y[0] have different provenances, replacing one with another must be avoided.</div><div>Instead, we can guarantee that p is precisely equivalent to &x[1].</div><div>Another benefit is that optimizations on integers do not need to suffer from these pointer thingy anymore;<br></div><div>e.g., the optimization on llvm.assume above can survive and it does not need to check whether an integer variable is derived from a pointer value.</div><div> <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><div style="font-family:sans-serif"><div style="white-space:normal">

</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid rgb(57,131,196);color:rgb(57,131,196);margin:0px 0px 5px;padding-left:5px"><blockquote style="border-left:2px solid rgb(124,191,12);color:rgb(124,191,12);margin:0px 0px 5px;padding-left:5px"><p dir="auto">Since you seem to find this sort of thing compelling, please note that<br>
even a simple assignment like char c2 = c1 technically promotes through<br>
int in C, and so int must be able to carry pointer information if char<br>
can.<br>
</p>
</blockquote><p dir="auto">IIUC integer promotion is done when it is used as an operand of arithmetic<br>
ops or switch's condition, so I think assignment operation is okay.</p>
</blockquote></div>
<div style="white-space:normal">

<p dir="auto">Hmm, I was misremembering the rule, you’re right.</p>

<p dir="auto">John.</p>
</div>
</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>