llvm dev - Jun 2021 - [RFC] Introducing a byte type to LLVM

Hi,
Sorry for my late reply, and thank you for sharing great summaries & ideas.
I'll leave my thoughts below.

On Wed, Jun 16, 2021 at 8:56 AM John McCall <rjmccall at apple.com> wrote:
> Okay, so let me try to restate and summarize all this. I’ve CC’ed
>
> a bunch of people back into this part of the thread.
>
> C is moving towards a provenance model; you can find the details in
> this committee TR that Joshua Cranmer linked:
> http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2676.pdf
>
> This TR is very clearly a work in progress and contains many
> digressions and several possible sets of rules with different
> implications. I will try to briefly summarize.
>
> <snip>
>
> Now, that rule as I’ve stated it would be really bad. Allowing a
> lucky guess to resolve to absolutely anything would almost
> completely block the optimizer from optimizing memory. For example,
> if a local variable came into scope, and then we called a function
> that returned a different pointer, we’d have to conservatively
> assume that that pointer might alias the local, even if the address
> of the local was never even taken, much less escaped:
>
>   int x = 0;
>   int *p = guess_address_of_x();
>   *p = 15;
>   printf(“%d\n”, x); // provably 0?
>
> So the currently favored proposal adds a really important caveat:
> this blessing of provenance only works when a pointer with the
> correct provenance has been “exposed”. There are several ways to
> expose a pointer, including I/O, but the most important is casting
> it to an integer.
>
This is a valid point. If one wants to formally show the correctness of
this kind of memory optimization this problem should be tackled.
I think n2676's 'Allocation-address nondeterminism' (p. 27)
paragraph
addresses this issue.
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.
> Again, there’s no requirement of a data dependence between the
> exposure and the int-to-pointer cast. If the program casts a
> pointer to an integer, and an independently-produced integer
> that happens to be the same value is later cast to a pointer,
> and the storage hasn’t been reallocated in the meantime, the
> resulting pointer will have the right provenance for the memory
> and will be valid to use. This implies that pointer-to-int casts
> (and other exposures) are semantically significant events in the
> program. They don’t have side effects in the normal sense, but
> they must be treated by the compiler just like things that do have
> side effects: e.g. unless I’m missing something in the TR,
> eliminating a completely unused pointer-to-int cast may make
> later code UB.
>
> And in fact, it turns out that this is crucially important for
> optimization. If the optimizer wants to allow arbitrary
> replacement of integers based on conditional equality, like
> in GVN, then replacement totally breaks direct data dependence,
> and you can easily be left with no remaining uses of a pointer-to-int
> cast when the original code would have had a data dependence. So
> you cannot reason about provenance through int-to-pointer casts:
> the pointer can alias any storage whose provenance has potentially
> been exposed, and the optimizer must be conservative about optimizing
> memory that has potentially been exposed.
>
+1, due to this reason the casting semantics cannot be directly used for
LLVM's ptrtoint/inttoptr.
> <snip>
>
> Everything I’ve been talking about so far is a C-level concept:
> an int-to-pointer cast is e.g. (float*) myInt, not inttoptr
> in LLVM IR. But I think people have an expectation of what these
> things mean in LLVM IR, and I haven’t seen it written out explicitly,
> so let’s do that now.
>
> The first assumption here is that int-to-pointer and pointer-to-int
> casts in C will translate to inttoptr and ptrtoint operations
> in IR. Now, this is already problematic, because those operations
> do not currently have the semantics they need to have to make the
> proposed optimization model sound. In particular:
>
>    -
>
>    ptrtoint does not have side-effects and can be dead-stripped
>    when unused, which as discussed above is not okay.
>    -
>
>    ptrtoint on a constant is folded to a constant expression,
>    not an instruction, which is therefore no longer anchored in the
>    code and does not reliably record that the global may have escaped.
>    (Unused constant expressions do not really exist, and we absolutely
>    cannot allow them to affect the semantics of the IR.)
>
>    Of course, this is only significant for globals that don’t already
>    have to be treated conservatively because they might have other
>    uses. That is, it only really matters for globals with, say,
>    internal or private linkage.
>    -
>
>    inttoptr can be reordered with other instructions, which is
>    not allowed because different points in a function may have
>    different sets of storage with escaped provenance.
>    -
>
>    inttoptr(ptrtoint) can be peepholed; ignoring the dead-stripping
>    aspects of removing the inttoptr, this also potentially
>    introduces UB because the original inttoptr “launders” the
>    provenance of the pointer to the current provenance of the
>    storage, whereas the original pointer may have stale provenance.
>
> All of these concerns are valid.
(I'm not sure whether this is a good place to introduce this, but) we
actually have semantics for pointer castings tailored to LLVM (link
<https://sf.snu.ac.kr/publications/llvmtwin.pdf>).
In this proposal, ptrtoint does not have an escaping side effect; ptrtoint
and inttoptr are scalar operations.
inttoptr simply returns a pointer which can access any object.
Combined with the address nondeterminism that is described above, unescaped
objects can be effectively left untouched from other memory accesses.

Also, the following optimizations can be explained:
- 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)
- 'gep (inttoptr i), idx' is equivalent to 'i + idx' (same value
and same
level of undefinedness)
- gep and gep inbounds is a scalar operation (can be freely reordered w.r.t
ptrtoint/inttoptr/lifetime/free/...)
- gep's natural properties are supported: stripping off inbounds tag,
'gep
(gep (inttoptr i), i1), i2' -> 'gep (inttoptr i), i1+i2'

There are a few transformations that become hard to explain, but perhaps
the biggest one is 'inttoptr(ptrtoint p)' -> p.
> <snip>
>
> I don’t find either side of this argument very convincing.
>
> First, the compiler already has to be very conservative about
> memory. If a pointer is stored into memory, we generally have
> to treat it as having fully escaped: unless we can prove that the
> memory isn’t loaded by other code, we have to assume that it is,
> and that the loading code will do arbitrary other stuff. That
> could include doing a pointer-to-int cast and sharing the pointer
> back to us as an integer. Therefore, in the general case, our
> ability to optimize when a pointer has escaped into memory is at
> least as bad as if it had escaped via an int-to-pointer cast. If
> we *can* nonetheless optimize, because we can reason about some of
> the uses together or prove that there aren’t any other uses,
> then okay, maybe we see that there’s an int<->pointer conversion.
> But translating this to ptrtoint/inttoptr should be, at
> worst, overly conservative; it’s not unsound, for reasons I’m
> about to get into.
>
> Second, adding casts through an integer type is always valid.
> Doing so might block the optimizer, but it doesn’t break semantics.
> If I have a program that does e.g *px = 15, and I change it to
> do *(int*)(intptr_t)px = 15, my program has become well-defined
> in strictly more situations: in any case, there must be valid
> storage at px for this not to be UB, but previously px might
> have had the wrong provenance, and now it never does as long as
> the provenance for that storage has previously escaped.
>
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.
> If we find that we’re generating too many unnecessary casts
> through integer types and it’s really blocking the optimizer too
> much, then we should consider the best solutions to those problems
> as they arise. It may be the case that we need a better solution
> for type conversions introduced through manual memcpy-like code
> so that we maintain the original provenance instead of adding
> explicit int<->pointer conversions that launder provenance.
> I don’t know that byte types are the best solution to that, but
> we can consider them.
>
> But this whole conversation about byte types seems to be coming
> at it the wrong way around. We need to be centering the first
> set of problems around int<->pointer casts.
>
John.
>
As the first step, I made a patch to LangRef for differentiation of int and
ptr: https://reviews.llvm.org/D104013 . It is currently under review.
Maybe we can pursue two-track:
(1) gradually disabling the 'inttoptr(ptrtoint p) -> p' folding.
- For example, to fix https://bugs.llvm.org/show_bug.cgi?id=34548,
disabling it when p's underlying object is alloca would be enough (I guess).
(2) inspecting how byte types can help revive optimizations.
- For example, loop idiom recognition on memcpy-like loops should be
removed otherwise. Its performance impact should be checked.
>
>
>
Thanks,
Juneyoung
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210621/91a8e7be/attachment.html>

Hi,
>     Now, that rule as I’ve stated it would be really bad. Allowing a
>     lucky guess to resolve to absolutely anything would almost
>     completely block the optimizer from optimizing memory. For example,
>     if a local variable came into scope, and then we called a function
>     that returned a different pointer, we’d have to conservatively
>     assume that that pointer might alias the local, even if the address
>     of the local was never even taken, much less escaped:
> 
>     |int x = 0; int *p = guess_address_of_x(); *p = 15; printf(“%d\n”, x);
//
>     provably 0? |
> 
>     So the currently favored proposal adds a really important caveat:
>     this blessing of provenance only works when a pointer with the
>     correct provenance has been “exposed”. There are several ways to
>     expose a pointer, including I/O, but the most important is casting
>     it to an integer.
> 
> This is a valid point. If one wants to formally show the correctness of
this
> kind of memory optimization this problem should be tackled.
> I think n2676's 'Allocation-address nondeterminism' (p. 27)
paragraph addresses
> this issue.
> 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.
I am confused -- that optimization is allowed without any reasoning about 
non-determinism, because the address of x has never been exposed, right?

There are some optimizations that still require reasoning about non-determinism,
namely cases where the address *has* been exposed. This was recently discussed 
on <https://lists.cam.ac.uk/mailman/listinfo/cl-c-memory-object-model> and
at
least one WG14 member expressed the opinion that in this case, the optimization 
is actually not allowed.
FWIW, I personally prefer a model that always uses non-determinism to justify 
such optimizations, avoiding the need for any kind of "exposed" flag
(such as
the paper Juneyoung referenced -- unsurprisingly so, since I am a coauthor of 
that paper ;).

However, I should also add that the trade-offs in language design are different 
for a surface language such as C and for an optimized IR such as LLVM's.
>     Again, there’s no requirement of a data dependence between the
>     exposure and the int-to-pointer cast. If the program casts a
>     pointer to an integer, and an independently-produced integer
>     that happens to be the same value is later cast to a pointer,
>     and the storage hasn’t been reallocated in the meantime, the
>     resulting pointer will have the right provenance for the memory
>     and will be valid to use. This implies that pointer-to-int casts
>     (and other exposures) are semantically significant events in the
>     program. They don’t have side effects in the normal sense, but
>     they must be treated by the compiler just like things that do have
>     side effects: e.g. unless I’m missing something in the TR,
>     eliminating a completely unused pointer-to-int cast may make
>     later code UB.
> 
>     And in fact, it turns out that this is crucially important for
>     optimization. If the optimizer wants to allow arbitrary
>     replacement of integers based on conditional equality, like
>     in GVN, then replacement totally breaks direct data dependence,
>     and you can easily be left with no remaining uses of a pointer-to-int
>     cast when the original code would have had a data dependence. So
>     you cannot reason about provenance through int-to-pointer casts:
>     the pointer can alias any storage whose provenance has potentially
>     been exposed, and the optimizer must be conservative about optimizing
>     memory that has potentially been exposed.
> 
> +1, due to this reason the casting semantics cannot be directly used for
LLVM's
> ptrtoint/inttoptr.
However, note that GVN integer replacement is a problem even without the 
"exposed" flag, as demonstrated by the long-standing issues 
https://bugs.llvm.org/show_bug.cgi?id=34548 and 
https://bugs.llvm.org/show_bug.cgi?id=35229.

Kind regards,
Ralf

On 21 Jun 2021, at 2:15, Juneyoung Lee wrote:
> Hi,
> Sorry for my late reply, and thank you for sharing great summaries &
ideas.
> I'll leave my thoughts below.
>
> On Wed, Jun 16, 2021 at 8:56 AM John McCall <rjmccall at apple.com>
wrote:
>> Now, that rule as I’ve stated it would be really bad. Allowing a
>> lucky guess to resolve to absolutely anything would almost
>> completely block the optimizer from optimizing memory. For example,
>> if a local variable came into scope, and then we called a function
>> that returned a different pointer, we’d have to conservatively
>> assume that that pointer might alias the local, even if the address
>> of the local was never even taken, much less escaped:
>>
>>   int x = 0;
>>   int *p = guess_address_of_x();
>>   *p = 15;
>>   printf(“%d\n”, x); // provably 0?
>>
>> So the currently favored proposal adds a really important caveat:
>> this blessing of provenance only works when a pointer with the
>> correct provenance has been “exposed”. There are several ways to
>> expose a pointer, including I/O, but the most important is casting
>> it to an integer.
>>
> This is a valid point. If one wants to formally show the correctness of
> this kind of memory optimization this problem should be tackled.
> I think n2676's 'Allocation-address nondeterminism' (p. 27)
paragraph
> addresses this issue.
> 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.
Ah, that’s an interesting idea.  I must have missed that section; I’m
afraid I only skimmed N2676 looking for the key points, because it’s
quite a long document.

To be clear, under the `PVNI-ae` family of semantics, that rule would
not be necessary to optimize `x` in my example because int-to-pointer
casts are not allowed to recreate provenance for `x` because it has
not been exposed.  That rule does theoretically allow optimization of
some related examples where the address of `x` *has* been exposed,
because it lets the compiler try to reason about what happens after
exposure; it’s no longer true that exposure implies guessing are okay.

Unfortunately, though, I this non-determinism still doesn’t allow LLVM
to be anywhere near as naive about pointer-to-int casts as it is today.
The rule is intended to allow the compiler to start doing use-analysis
of exposures; let’s assume that this analysis doesn’t see any
un-analyzable uses, since of course it would need to conservatively
treat them as escapes.  But if we can optimize uses of integers as if
they didn’t carry pointer data — say, in a function that takes integer
parameters — and then we can apply those optimized uses to integers
that concretely result from pointer-to-int casts — say, by inlining
that function into one of its callers — can’t we end up with a use
pattern for one or more of those pointer-to-int casts that no longer
reflects the fact that it’s been exposed?  It seems to me that either
(1) we cannot do those optimizations on opaque integers or (2) we
need to record that we did them in a way that, if it turns out that
they were created by a pointer-to-int casts, forces other code to
treat that pointer as opaquely exposed.
>> <snip>
>>
>> Everything I’ve been talking about so far is a C-level concept:
>> an int-to-pointer cast is e.g. (float*) myInt, not inttoptr
>> in LLVM IR. But I think people have an expectation of what these
>> things mean in LLVM IR, and I haven’t seen it written out explicitly,
>> so let’s do that now.
>>
>> The first assumption here is that int-to-pointer and pointer-to-int
>> casts in C will translate to inttoptr and ptrtoint operations
>> in IR. Now, this is already problematic, because those operations
>> do not currently have the semantics they need to have to make the
>> proposed optimization model sound. In particular:
>>
>>    -
>>
>>    ptrtoint does not have side-effects and can be dead-stripped
>>    when unused, which as discussed above is not okay.
>>    -
>>
>>    ptrtoint on a constant is folded to a constant expression,
>>    not an instruction, which is therefore no longer anchored in the
>>    code and does not reliably record that the global may have escaped.
>>    (Unused constant expressions do not really exist, and we absolutely
>>    cannot allow them to affect the semantics of the IR.)
>>
>>    Of course, this is only significant for globals that don’t already
>>    have to be treated conservatively because they might have other
>>    uses. That is, it only really matters for globals with, say,
>>    internal or private linkage.
>>    -
>>
>>    inttoptr can be reordered with other instructions, which is
>>    not allowed because different points in a function may have
>>    different sets of storage with escaped provenance.
>>    -
>>
>>    inttoptr(ptrtoint) can be peepholed; ignoring the dead-stripping
>>    aspects of removing the inttoptr, this also potentially
>>    introduces UB because the original inttoptr “launders” the
>>    provenance of the pointer to the current provenance of the
>>    storage, whereas the original pointer may have stale provenance.
>>
>> All of these concerns are valid.
>
> (I'm not sure whether this is a good place to introduce this, but) we
> actually have semantics for pointer castings tailored to LLVM (link
> <https://sf.snu.ac.kr/publications/llvmtwin.pdf>).
> In this proposal, ptrtoint does not have an escaping side effect; ptrtoint
> and inttoptr are scalar operations.
> inttoptr simply returns a pointer which can access any object.
Skimming your paper, I can see how this works *except* that I don’t
see any way not to treat `ptrtoint` as an escape.  And really I think
you’re already partially acknowledging that, because that’s the only
real sense of saying that `inttoptr(ptrtoint p)` can’t be reduced to
`p`.  If those are really just scalar operations that don’t expose
`p` in ways that might be disconnected from the uses of the `inttoptr`
then that reduction ought to be safe.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210621/5ce12b62/attachment.html>