<div dir="ltr"><div dir="ltr"><div>Hi Nicolai,</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">I feel like the entire discussion is extremely confused and confusing because there is lack of clarity about what values are in fact carried by the types i<N>, ptr (assuming untyped pointers already), and the proposed b<N>. There are statements about "whether a b<N> contains a pointer or an integer" without a clear definition of what any of that really means.</blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">By the way: the discussion of GVN states that i<N> do not carry provenance information, but LangRef appears to contradict this, because it states (in the Pointer Aliasing section) that "A pointer value formed by an <code>inttoptr</code> is <em>based</em> on all pointer
values that contribute (directly or indirectly) to the computation of
the pointer’s value." The only way to make this statement operational is for the operand of the inttoptr to carry provenance information; this definitely needs to be addressed by this proposal.</blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">My educated guess is that what the proposal really wants to say is that an i<N> value is poison or an integer without pointer provenance (i.e., an i<N> value is never "based on" a pointer) while a b<N> value is poison or an integer that may have provenance (i.e., it may be "based on" one or more pointers). Everything else should follow from this core definition. With this phrasing, I can see a coherent picture emerging that can be discussed without a lot of the confusion in this thread (though still _some_ confusion, as the topic is inherently subtle).</blockquote></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">@George, Nuno, and Juneyoung: is that a good lens through which to see the proposal?</blockquote></div><div><br></div><div>Yes, our understanding is that only values of pointer types carry provenance whereas non-pointer types (i<N>, float, ...) don't carry provenance.</div><div>We believe that when people were writing optimizations on non-pointer types (instcombine, reassociate, gvn, etc) they did not assume the existence of provenance in such types.</div><div>As mentioned, it contradicts with LangRef's wording about inttoptr though.</div><div><br></div><div>I agree that clarifying these is a good first step to avoid confusion. Specifically, via pinning down what people agree on in LangRef.</div><div><div>I think it is good to start with removing the inttoptr case from LangRef's based-on part and adding relevant texts.</div><div></div></div><div>IMO, existing alias analysis and optimizations were already avoiding uses of inttoptr's based-on information (experts' comments needed to double check).</div><div>Also, to provide alternatives for ptrtoint/inttoptr round trip with better analysis, llvm.ptrmask and clang-tidy's performance-no-int-to-ptr were added as well.</div><div><br></div><div>If people agree, I'll write a draft for this and share it via phabricator.</div><div><br></div><div>Thanks,</div><div>Juneyoung</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jun 9, 2021 at 8:02 AM Nicolai Hähnle 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>Hi,</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jun 7, 2021 at 7:40 PM Harald van Dijk 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>On 04/06/2021 16:24, George Mitenkov
via llvm-dev wrote:<br>
<blockquote type="cite">
<div dir="ltr">
<div dir="ltr"><span id="gmail-m_-5865386445399705736gmail-m_-3069621638968785232gmail-docs-internal-guid-ec050142-7fff-10f3-b533-a9ba2e107dc6" style="color:rgb(0,0,0)">
<ol style="margin-top:0px;margin-bottom:0px" start="2">
<li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;font-variant-ligatures:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-variant-ligatures:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">When copying pointers as bytes implicit pointer-to-integer casts are avoided.The current setting of performing a memcpy using i8s leads to miscompilations (example: bug report </span><a href="https://bugs.llvm.org/show_bug.cgi?id=37469" style="text-decoration:none" target="_blank"><span style="font-size:11pt;font-variant-ligatures:normal;font-variant-east-asian:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap">37469</span></a><span style="font-size:11pt;font-variant-ligatures:normal;font-variant-east-asian:normal;white-space:pre-wrap">) and is bad for alias analysis.</span></p></li>
</ol>
</span></div>
</div>
</blockquote>
<p>While trying to understand what exactly is going wrong in this
bug I think I stumbled upon incomplete documentation. At
<a href="https://llvm.org/docs/LangRef.html#pointeraliasing" target="_blank">https://llvm.org/docs/LangRef.html#pointeraliasing</a> it is
documented that</p>
<ul>
<li>A memory access must be done through a pointer associated with
the address range.</li>
<li>A pointer value is associated with the addresses associated
with any
value it is based on.</li>
<li>A pointer value formed by an instruction is based on another
pointer value the instruction is getelementptr, bitcast, or
inttoptr.</li>
</ul>
<p>What is not mentioned is what a pointer value formed by a load
instruction is based on. If a pointer value formed by a load
instruction is not associated with any address range, then it
cannot be used to load or store <i>any</i> value. Clearly that is
not wanted.</p>
<p>If memory is completely untyped, then a load of a pointer value
needs to be equivalent to a load of an integer value followed by
inttoptr. In that model, it is not possible to replace a load of a
pointer value by a previously stored value, it is only possible to
replace it by inttoptr(ptrtoint(previously stored value)). In that
model, the problem is that LLVM does replace a load of a pointer
value by a previously stored value, and the bug can be fixed (at a
cost of reduced optimisations of other code) by making sure to
insert ptrtoint and inttoptr as needed, including for any pointer
members of structs etc.</p>
<p>Your proposal is based on an interpretation of the problem using
a memory model where memory is not completely untyped. In your
memory model, what address range is a pointer value that came from
a load instruction associated with?</p></div></blockquote><div><br></div><div>I second this.</div><div><br></div><div>I feel like the entire discussion is extremely confused and confusing because there is lack of clarity about what values are in fact carried by the types i<N>, ptr (assuming untyped pointers already), and the proposed b<N>. There are statements about "whether a b<N> contains a pointer or an integer" without a clear definition of what any of that really means.</div><div><br></div><div>By the way: the discussion of GVN states that i<N> do not carry provenance information, but LangRef appears to contradict this, because it states (in the Pointer Aliasing section) that "A pointer value formed by an <code><span>inttoptr</span></code> is <em>based</em> on all pointer
values that contribute (directly or indirectly) to the computation of
the pointer’s value." The only way to make this statement operational is for the operand of the inttoptr to carry provenance information; this definitely needs to be addressed by this proposal.<br></div><div><br></div><div>My educated guess is that what the proposal really wants to say is that an i<N> value is poison or an integer without pointer provenance (i.e., an i<N> value is never "based on" a pointer) while a b<N> value is poison or an integer that may have provenance (i.e., it may be "based on" one or more pointers). Everything else should follow from this core definition. With this phrasing, I can see a coherent picture emerging that can be discussed without a lot of the confusion in this thread (though still _some_ confusion, as the topic is inherently subtle).</div><div><br></div><div>@George, Nuno, and Juneyoung: is that a good lens through which to see the proposal? If no, why not? If yes, I believe there are some immediate implications and questions, such as:</div><div><br></div><div>1. Forbidding arithmetic and bitwise operations in b<N> seems pointless. Just define them as the corresponding i<N> op plus the union of provenance of the operands. This allows consistent implementation of char/unsigned char as b8, without having to jump back and forth between b8 and i8 all the time.<br></div><div><br></div><div>2. What's the provenance of a b<N> `select`?</div><div><br></div><div>3. A b<N>-to-i<N> conversion necessarily loses all provenance information.</div><div><br></div><div>4. What's the provenance of the result of an i<N>-to-b<N> conversion? The only possible choices are "empty" or "full" provenance, where "full" provenance means that the value is "based on" _all_ pointers. Depending on the details of allowed instruction signatures, we may want to allow both choices. "Full" provenance gives us something that's useful as a step towards inttoptr. "Empty" provenance allows us to lift i<N> to b<N> for arithmetic operations without being overly conservative (e.g., consider the somewhat hypothetical problem of lowering a GEP to a sequence of arithmetic on b<N> types in IR -- we want the result to have the provenance of the base pointer, which enters the arithmetic as a b<N> with provenance; adding the various i<N> offset operands should have no effect on provenance).<br></div><div><br></div><div>5. Memory is untyped but can carry provenance; i.e., it consists of b8. Load/store of i<N> performs implicit i-to-b/b-to-i conversions, respectively. Which kind of i-to-b conversion is used during a store? The "empty" one or the "full" one? There are several reasonable options for how to address this, and a choice must be made.<br></div><div><br> </div><div>6. (How) are pointer types fundamentally different from b<N> types of the correct size? (By this I mean: is there any interesting difference in the values that these types can carry? Ignore surface differences like the fact that GEP traditionally goes with pointers while `add` goes with integer types -- we could have a GEP instruction on a correctly sized b<N>)<br></div><div><br></div><div>It seems pretty clear that there is still a lot of work to be done on this proposal before we can be sufficiently confident that it won't just add new correctness problems elsewhere. Besides, the cost of adding a new family of types is very high, and I am not (yet?) convinced that it pays for itself. But with the above I can at least see better where you're coming from.</div><div><br></div><div>Cheers,</div><div>Nicolai<br></div><br><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>
<p>Cheers,<br>
Harald van Dijk<br>
</p>
</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><br clear="all"><br>-- <br><div dir="ltr">Lerne, wie die Welt wirklich ist,<br>aber vergiss niemals, wie sie sein sollte.</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><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>