<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/xhtml; charset=utf-8">
</head>
<body>
<div style="font-family:sans-serif"><div style="white-space:normal">
<p dir="auto">On 22 Jun 2021, at 12:02, Juneyoung Lee wrote:</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #3983C4; color:#3983C4; margin:0 0 5px; padding-left:5px"><p dir="auto">On Tue, Jun 22, 2021 at 4:08 AM John McCall <rjmccall@apple.com> wrote:</p>
<blockquote style="border-left:2px solid #3983C4; color:#7CBF0C; margin:0 0 5px; padding-left:5px; border-left-color:#7CBF0C"><p dir="auto">On 21 Jun 2021, at 2:15, Juneyoung Lee wrote:<br>
<br>
Hi,<br>
Sorry for my late reply, and thank you for sharing great summaries & ideas.<br>
I'll leave my thoughts below.<br>
<br>
On Wed, Jun 16, 2021 at 8:56 AM John McCall <rjmccall@apple.com> wrote:<br>
<br>
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:<br>
<br>
int x = 0;<br>
int *p = guess_address_of_x();<br>
*p = 15;<br>
printf(“%d\n”, x); // provably 0?<br>
<br>
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.<br>
<br>
This is a valid point. If one wants to formally show the correctness of<br>
this kind of memory optimization this problem should be tackled.<br>
I think n2676's 'Allocation-address nondeterminism' (p. 27) paragraph<br>
addresses this issue.<br>
The underlying idea is that the address of an allocated object is assumed<br>
to be non-deterministically chosen, causing any guessed accesses to raise<br>
undefined behavior in at least one execution.<br>
<br>
Ah, that’s an interesting idea. I must have missed that section; I’m<br>
afraid I only skimmed N2676 looking for the key points, because it’s<br>
quite a long document.<br>
<br>
To be clear, under the PVNI-ae family of semantics, that rule would<br>
not be necessary to optimize x in my example because int-to-pointer<br>
casts are not allowed to recreate provenance for x because it has<br>
not been exposed. That rule does theoretically allow optimization of<br>
some related examples where the address of x *has* been exposed,<br>
because it lets the compiler try to reason about what happens after<br>
exposure; it’s no longer true that exposure implies guessing are okay.<br>
<br>
Unfortunately, though, I this non-determinism still doesn’t allow LLVM<br>
to be anywhere near as naive about pointer-to-int casts as it is today.<br>
The rule is intended to allow the compiler to start doing use-analysis<br>
of exposures; let’s assume that this analysis doesn’t see any<br>
un-analyzable uses, since of course it would need to conservatively<br>
treat them as escapes. But if we can optimize uses of integers as if<br>
they didn’t carry pointer data — say, in a function that takes integer<br>
parameters — and then we can apply those optimized uses to integers<br>
that concretely result from pointer-to-int casts — say, by inlining<br>
that function into one of its callers — can’t we end up with a use<br>
pattern for one or more of those pointer-to-int casts that no longer<br>
reflects the fact that it’s been exposed? It seems to me that either<br>
(1) we cannot do those optimizations on opaque integers or (2) we<br>
need to record that we did them in a way that, if it turns out that<br>
they were created by a pointer-to-int casts, forces other code to<br>
treat that pointer as opaquely exposed.<br>
</p>
</blockquote><p dir="auto">IIUC the corresponding example would be:<br>
int p;<br>
intptr_t i = (intptr_t)&p;<br>
f(i);<br>
// Initially f(i) exposes p by storing i into somewhere, but optimization<br>
changed f to not store i anymore (e.g. i was replaced with a constant)<br>
<br>
In this case, p was already exposed by '(intptr_t)p' I guess; the body of<br>
f(i) won't affect the exposedness of p.</p>
</blockquote></div>
<div style="white-space:normal">
<p dir="auto">Right, formally I think that’s true.</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #3983C4; color:#3983C4; margin:0 0 5px; padding-left:5px"><blockquote style="border-left:2px solid #3983C4; color:#7CBF0C; margin:0 0 5px; padding-left:5px; border-left-color:#7CBF0C"><p dir="auto">All of these concerns are valid.<br>
<br>
(I'm not sure whether this is a good place to introduce this, but) we<br>
actually have semantics for pointer castings tailored to LLVM (link<br>
<<a href="https://sf.snu.ac.kr/publications/llvmtwin.pdf">https://sf.snu.ac.kr/publications/llvmtwin.pdf</a>>).<br>
In this proposal, ptrtoint does not have an escaping side effect; ptrtoint<br>
and inttoptr are scalar operations.<br>
inttoptr simply returns a pointer which can access any object.<br>
<br>
Skimming your paper, I can see how this works *except* that I don’t<br>
see any way not to treat ptrtoint as an escape. And really I think<br>
you’re already partially acknowledging that, because that’s the only<br>
real sense of saying that inttoptr(ptrtoint p) can’t be reduced to<br>
p. If those are really just scalar operations that don’t expose<br>
p in ways that might be disconnected from the uses of the inttoptr<br>
then that reduction ought to be safe.<br>
<br>
John.<br>
</p>
</blockquote><p dir="auto">It again relies on nondeterminism of the address of an object.<br>
<br>
For example:<br>
p = call malloc(4) ; p's address is assumed to be nondeterministically<br>
chosen<br>
i = ptrtoint p<br>
; i is never used<br>
ret void<br>
<br>
Since i is never used, this program cannot safely access p via address<br>
guessing + inttoptr.<br>
This allows (more precise) escape analysis to conclude that malloc with one<br>
unused ptrtoint is never escaped.</p>
</blockquote></div>
<div style="white-space:normal">
<p dir="auto">I think this is too local of an analysis.</p>
<p dir="auto">Your proposal generally relies on certain optimizations not applying<br>
to pointers because they mess up provenance as represented in<br>
transitive use-dependencies. If those optimizations can be applied<br>
to integers, you can lose use-dependencies in exactly the same way as<br>
you can with pointers. Not doing the <code>inttoptr(ptrtoint p)) -> p</code><br>
reduction doesn’t matter at all, because in either case that value<br>
has a use-dependency on <code>p</code>, whereas the actual problem is that there<br>
is no longer a use-dependency on some other value.</p>
<p dir="auto">For example, you have compellingly argued that it’s problematic to<br>
do the reduction <code>a == b ? a : b</code> to <code>b</code> for pointer types. Suppose<br>
I instead do this optimization on integers where <code>a = ptrtoint A</code>.<br>
The result is now simply <code>b</code>. If I <code>inttoptr</code> that result and access<br>
the memory, there will be no record that that access may validly<br>
be to <code>A</code>. It does not help that the access may be represented<br>
as <code>inttoptr (ptrtoint B)</code> for some <code>B</code> rather than just directly<br>
to <code>B</code>, because there is no use-dependence on <code>A</code>. All there is<br>
is an apparently unrelated and unused <code>ptrtoint A</code>.</p>
<p dir="auto">Obviously we can avoid doing this optimization locally when we<br>
see that the inputs result from <code>ptrtoint</code>, but that’s no more<br>
than best-effort: we can do this optimization in a function which<br>
we later inline in a caller that performs all the <code>ptrtoint</code> and<br>
<code>inttoptr</code> casts.</p>
<p dir="auto">John.</p>
</div>
</div>
</body>
</html>