<div dir="ltr"><div dir="ltr">Hi,<div>Sorry for my late reply, and thank you for sharing great summaries & ideas. I'll leave my thoughts below.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jun 16, 2021 at 8:56 AM John McCall <<a href="mailto:rjmccall@apple.com" target="_blank">rjmccall@apple.com</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"><u></u>
<div>
<div style="font-family:sans-serif"><div style="white-space:normal">
<p dir="auto">Okay, so let me try to restate and summarize all this. I’ve CC’ed<br></p></div><div style="white-space:normal"><p dir="auto">
a bunch of people back into this part of the thread.</p>
<p dir="auto">C is moving towards a provenance model; you can find the details in<br>
this committee TR that Joshua Cranmer linked:<br>
<a href="http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2676.pdf" target="_blank">http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2676.pdf</a></p>
<p dir="auto">This TR is very clearly a work in progress and contains many<br>
digressions and several possible sets of rules with different<br>
implications. I will try to briefly summarize.</p>
<p><snip></p>
<p dir="auto">Now, that rule as I’ve stated it would be really bad. Allowing a<br>
lucky guess to resolve to absolutely anything would almost<br>
completely block the optimizer from optimizing memory. For example,<br>
if a local variable came into scope, and then we called a function<br>
that returned a different pointer, we’d have to conservatively<br>
assume that that pointer might alias the local, even if the address<br>
of the local was never even taken, much less escaped:</p>
<pre style="border:thin solid gray;margin-left:15px;margin-right:15px;max-width:90vw;overflow-x:auto;padding:5px"><code> int x = 0;
int *p = guess_address_of_x();
*p = 15;
printf(“%d\n”, x); // provably 0?
</code></pre>
<p dir="auto">So the currently favored proposal adds a really important caveat:<br>
this blessing of provenance only works when a pointer with the<br>
correct provenance has been “exposed”. There are several ways to<br>
expose a pointer, including I/O, but the most important is casting<br>
it to an integer.</p></div></div></div></blockquote><div>This is a valid point. If one wants to formally show the correctness of this kind of memory optimization this problem should be tackled.</div><div>I think n2676's 'Allocation-address nondeterminism' (p. 27) paragraph addresses this issue.</div><div>The underlying idea is that the address of an allocated object is assumed to be non-deterministically chosen, causing any guessed accesses to raise undefined behavior in at least one execution.</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">
<p dir="auto">Again, there’s no requirement of a data dependence between the<br>
exposure and the int-to-pointer cast. If the program casts a<br>
pointer to an integer, and an independently-produced integer<br>
that happens to be the same value is later cast to a pointer,<br>
and the storage hasn’t been reallocated in the meantime, the<br>
resulting pointer will have the right provenance for the memory<br>
and will be valid to use. This implies that pointer-to-int casts<br>
(and other exposures) are semantically significant events in the<br>
program. They don’t have side effects in the normal sense, but<br>
they must be treated by the compiler just like things that do have<br>
side effects: e.g. unless I’m missing something in the TR,<br>
eliminating a completely unused pointer-to-int cast may make<br>
later code UB.</p>
<p dir="auto">And in fact, it turns out that this is crucially important for<br>
optimization. If the optimizer wants to allow arbitrary<br>
replacement of integers based on conditional equality, like<br>
in GVN, then replacement totally breaks direct data dependence,<br>
and you can easily be left with no remaining uses of a pointer-to-int<br>
cast when the original code would have had a data dependence. So<br>
you cannot reason about provenance through int-to-pointer casts:<br>
the pointer can alias any storage whose provenance has potentially<br>
been exposed, and the optimizer must be conservative about optimizing<br>
memory that has potentially been exposed.</p></div></div></div></blockquote><div>+1, due to this reason the casting semantics cannot be directly used for LLVM's ptrtoint/inttoptr. </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"><p><snip></p>
<p dir="auto">Everything I’ve been talking about so far is a C-level concept:<br>
an int-to-pointer cast is e.g. <code>(float*) myInt</code>, not <code>inttoptr</code><br>
in LLVM IR. But I think people have an expectation of what these<br>
things mean in LLVM IR, and I haven’t seen it written out explicitly,<br>
so let’s do that now.</p>
<p dir="auto">The first assumption here is that int-to-pointer and pointer-to-int<br>
casts in C will translate to <code>inttoptr</code> and <code>ptrtoint</code> operations<br>
in IR. Now, this is already problematic, because those operations<br>
do not currently have the semantics they need to have to make the<br>
proposed optimization model sound. In particular:</p>
<ul>
<li><p dir="auto"><code>ptrtoint</code> does not have side-effects and can be dead-stripped<br>
when unused, which as discussed above is not okay.</p></li>
<li><p dir="auto"><code>ptrtoint</code> on a constant is folded to a constant expression,<br>
not an instruction, which is therefore no longer anchored in the<br>
code and does not reliably record that the global may have escaped.<br>
(Unused constant expressions do not really exist, and we absolutely<br>
cannot allow them to affect the semantics of the IR.)</p>
<p dir="auto">Of course, this is only significant for globals that don’t already<br>
have to be treated conservatively because they might have other<br>
uses. That is, it only really matters for globals with, say,<br>
internal or private linkage.</p></li>
<li><p dir="auto"><code>inttoptr</code> can be reordered with other instructions, which is<br>
not allowed because different points in a function may have<br>
different sets of storage with escaped provenance.</p></li>
<li><p dir="auto"><code>inttoptr(ptrtoint)</code> can be peepholed; ignoring the dead-stripping<br>
aspects of removing the <code>inttoptr</code>, this also potentially<br>
introduces UB because the original <code>inttoptr</code> “launders” the<br>
provenance of the pointer to the current provenance of the<br>
storage, whereas the original pointer may have stale provenance.</p></li></ul></div></div></div></blockquote><div>All of these concerns are valid.</div><div><div><br></div><div>(I'm not sure whether this is a good place to introduce this, but) we actually have semantics for pointer castings tailored to LLVM (<a href="https://sf.snu.ac.kr/publications/llvmtwin.pdf" target="_blank">link</a>).</div><div>In this proposal, ptrtoint does not have an escaping side effect; ptrtoint and inttoptr are scalar operations.</div><div>inttoptr simply returns a pointer which can access any object.</div><div>Combined with the address nondeterminism that is described above, unescaped objects can be effectively left untouched from other memory accesses.</div><div><br></div><div></div></div><div>Also, the following optimizations can be explained:</div><div>- The aliasing property of 'gep inbounds p' is supported: dereferencing 'gep inbounds p, 1' must raise UB if either p or p+1 isn't in bounds of p's object (provenance)</div><div>- 'gep (inttoptr i), idx' is equivalent to 'i + idx' (same value and same level of undefinedness)</div><div>- gep and gep inbounds is a scalar operation (can be freely reordered w.r.t ptrtoint/inttoptr/lifetime/free/...)</div><div>- gep's natural properties are supported: stripping off inbounds tag, 'gep (gep (inttoptr i), i1), i2' -> 'gep (inttoptr i), i1+i2'</div><div><br></div><div>There are a few transformations that become hard to explain, but perhaps the biggest one is 'inttoptr(ptrtoint p)' -> p.</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"><p dir="auto"><snip><br></p>
<p dir="auto">I don’t find either side of this argument very convincing.</p>
<p dir="auto">First, the compiler already has to be very conservative about<br>
memory. If a pointer is stored into memory, we generally have<br>
to treat it as having fully escaped: unless we can prove that the<br>
memory isn’t loaded by other code, we have to assume that it is,<br>
and that the loading code will do arbitrary other stuff. That<br>
could include doing a pointer-to-int cast and sharing the pointer<br>
back to us as an integer. Therefore, in the general case, our<br>
ability to optimize when a pointer has escaped into memory is at<br>
least as bad as if it had escaped via an int-to-pointer cast. If<br>
we <em>can</em> nonetheless optimize, because we can reason about some of<br>
the uses together or prove that there aren’t any other uses,<br>
then okay, maybe we see that there’s an int<->pointer conversion.<br>
But translating this to <code>ptrtoint</code>/<code>inttoptr</code> should be, at<br>
worst, overly conservative; it’s not unsound, for reasons I’m<br>
about to get into.</p>
<p dir="auto">Second, adding casts through an integer type is always valid.<br>
Doing so might block the optimizer, but it doesn’t break semantics.<br>
If I have a program that does e.g <code>*px = 15</code>, and I change it to<br>
do <code>*(int*)(intptr_t)px = 15</code>, my program has become well-defined<br>
in strictly more situations: in any case, there must be valid<br>
storage at <code>px</code> for this not to be UB, but previously <code>px</code> might<br>
have had the wrong provenance, and now it never does as long as<br>
the provenance for that storage has previously escaped.</p></div></div></div></blockquote><div>I agree. Transforming 'p' into 'inttoptr(ptrtoint p)' should not make the program undefined, and it can be used to address the correctness issue of these kinds of problems.</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><div style="font-family:sans-serif"><div style="white-space:normal">
<p dir="auto">If we find that we’re generating too many unnecessary casts<br>
through integer types and it’s really blocking the optimizer too<br>
much, then we should consider the best solutions to those problems<br>
as they arise. It may be the case that we need a better solution<br>
for type conversions introduced through manual memcpy-like code<br>
so that we maintain the original provenance instead of adding<br>
explicit int<->pointer conversions that launder provenance.<br>
I don’t know that byte types are the best solution to that, but<br>
we can consider them.</p>
<p dir="auto">But this whole conversation about byte types seems to be coming<br>
at it the wrong way around. We need to be centering the first<br>
set of problems around int<->pointer casts.<span style="font-family:Arial,Helvetica,sans-serif"> </span></p></div></div></div></blockquote><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"><p dir="auto">John.</p></div></div></div></blockquote></div><div>As the first step, I made a patch to LangRef for differentiation of int and ptr: <a href="https://reviews.llvm.org/D104013">https://reviews.llvm.org/D104013</a> . It is currently under review.</div><div><div>Maybe we can pursue two-track:</div><div>(1) gradually disabling the 'inttoptr(ptrtoint p) -> p' folding.</div><div>- For example, to fix <a href="https://bugs.llvm.org/show_bug.cgi?id=34548">https://bugs.llvm.org/show_bug.cgi?id=34548</a>, disabling it when p's underlying object is alloca would be enough (I guess).</div><div>(2) inspecting how byte types can help revive optimizations.</div><div>- For example, loop idiom recognition on memcpy-like loops should be removed otherwise. Its performance impact should be checked.</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><ul>
</ul>
<p dir="auto"></p></div></div></div></blockquote></div><div><br></div><div>Thanks,</div><div>Juneyoung</div><br></div>