llvm dev - Jun 2021 - pointer provenance introduction to load/store instructions

Hi all,

as some of you already know, the full restrict patches[0] introduce an optional
'ptr_provenance' operand
to LoadInst/StoreInst. In the context of full restrict support, this operand is
used to separate the
computation of the pointer operand from the possible restrict provenance of that
operand. This was necessary
so that we could keep all the optimizations working on those pointers, without
being blocked by the noalias intrinsics.
At the same time we avoided the risk to lose the noalias provenance of the
instruction.

As that separation can also be useful in other situations, there was a request
in the past LLVM Alias Analysis Tech calls[1],
to split out the pointer provenance changes and propose them as a next step for
inclusion.

Fast forward to today. A lot more discussions about pointer provenance and
related problems are ongoing.

Maybe the provided set of patches[2] and the experience with tracking the
provenance in the full restrict patches can
be a first step to help solving some of those problems ?

Any feedback is welcome, also during tomorrows AA TechCall[1]

Greetings,

Jeroen Dobbelaere

[0] https://reviews.llvm.org/D68484 [PATCH 01/27] [noalias] LangRef: noalias
intrinsics and ptr_provenance documentation.
[1]
https://docs.google.com/document/d/17U-WvX8qyKc3S36YUKr3xfF-GHunWyYowXbxEdpHscw/edit?usp=sharing
LLVM AA TechCall
[2] https://reviews.llvm.org/D104268 [ptr_provenance] Introduce optional
ptr_provenance operand to load/store

As far as I understand, your goal is to declare what's the set of objects a
pointer may alias with at a memory dereference operation.
For example, you may want to say that the following load can only dereference
objects pointed-to by %p and %q:
%v = load i8, * %r

If %r alias with some object other than %p/%q, the load triggers UB. This allows
you to do better AA.

This is useful when you have the restrict keyword in a function argument and you
inline that function. LLVM right now has no way to restrict aliasing per scope
or operation, just per function.
(this story has been seen by every other attribute..)

The goal sounds useful. Though it would be nice to see some performance numbers
as this is a complex feature and we need to understand if it's worth it.

Nevertheless, I would not claim this feature to be related with the discussion
around the byte type. There are only 2 solutions that avoid introducing the byte
type: 1) disable integer optimizations that are wrong for pointers, so that
integers can carry provenance information. This has been tried by another
compiler, CompCert, and didn't go very well.
Solution 2) is to lose provenance with integers and weaken AA substantially.
While your proposal could help recovering precision a bit, it would never
recover much, as it's a very syntactic approach. The compiler needs to find
the memory dereference operations and associate them with the right provenance
shrinking operations syntactically. Doesn't sound very promising, and it
would only act as a cache, essentially. It's not that the front-end could
give you much information. And we can prove this approach it's theoretical
inferior to the byte type, as some escaping scenarios are not possible to
recover from unless we disable type punning through memory (i.e., make the
round-trip of store/load a value a NOP).
Of course, the practicality of the by type is yet to be proven, though work is
undergoing.

Regardless, I'm happy to review your proposal if useful.

Nuno


-----Original Message-----
From: Jeroen Dobbelaere
Sent: 14 June 2021 23:57
To: llvm-dev at lists.llvm.org
Subject: [llvm-dev] pointer provenance introduction to load/store instructions

Hi all,

as some of you already know, the full restrict patches[0] introduce an optional
'ptr_provenance' operand to LoadInst/StoreInst. In the context of full
restrict support, this operand is used to separate the computation of the
pointer operand from the possible restrict provenance of that operand. This was
necessary so that we could keep all the optimizations working on those pointers,
without being blocked by the noalias intrinsics.
At the same time we avoided the risk to lose the noalias provenance of the
instruction.

As that separation can also be useful in other situations, there was a request
in the past LLVM Alias Analysis Tech calls[1], to split out the pointer
provenance changes and propose them as a next step for inclusion.

Fast forward to today. A lot more discussions about pointer provenance and
related problems are ongoing.

Maybe the provided set of patches[2] and the experience with tracking the
provenance in the full restrict patches can be a first step to help solving some
of those problems ?

Any feedback is welcome, also during tomorrows AA TechCall[1]

Greetings,

Jeroen Dobbelaere

[0] https://reviews.llvm.org/D68484 [PATCH 01/27] [noalias] LangRef: noalias
intrinsics and ptr_provenance documentation.
[1]
https://docs.google.com/document/d/17U-WvX8qyKc3S36YUKr3xfF-GHunWyYowXbxEdpHscw/edit?usp=sharing
LLVM AA TechCall
[2] https://reviews.llvm.org/D104268 [ptr_provenance] Introduce optional
ptr_provenance operand to load/store

On Mon, Jun 14, 2021 at 6:57 PM Jeroen Dobbelaere via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Hi all,
>
> as some of you already know, the full restrict patches[0] introduce an
optional 'ptr_provenance' operand
> to LoadInst/StoreInst. In the context of full restrict support, this
operand is used to separate the
> computation of the pointer operand from the possible restrict provenance of
that operand. This was necessary
> so that we could keep all the optimizations working on those pointers,
without being blocked by the noalias intrinsics.
> At the same time we avoided the risk to lose the noalias provenance of the
instruction.
>
> As that separation can also be useful in other situations, there was a
request in the past LLVM Alias Analysis Tech calls[1],
> to split out the pointer provenance changes and propose them as a next step
for inclusion.
>
> Fast forward to today. A lot more discussions about pointer provenance and
related problems are ongoing.
>
> Maybe the provided set of patches[2] and the experience with tracking the
provenance in the full restrict patches can
> be a first step to help solving some of those problems ?
>
> Any feedback is welcome, also during tomorrows AA TechCall[1]
I may not be able to make the call (the call starts as WG14 meetings
are ending), but I wanted to ask whether discussions of pointer
provenance are tracking the draft TS from WG14 on the subject
(http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2676.pdf)? This is a
work item from the C committee's Memory Object Model study group, and
any feedback we can provide to the SG on the TS would be greatly
appreciated as the committee's expectation is to someday roll this TS
into the C standard (with adjustments from whatever implementation
feedback is generated).

Thanks!

~Aaron
>
> Greetings,
>
> Jeroen Dobbelaere
>
> [0] https://reviews.llvm.org/D68484 [PATCH 01/27] [noalias] LangRef:
noalias intrinsics and ptr_provenance documentation.
> [1]
https://docs.google.com/document/d/17U-WvX8qyKc3S36YUKr3xfF-GHunWyYowXbxEdpHscw/edit?usp=sharing
LLVM AA TechCall
> [2] https://reviews.llvm.org/D104268 [ptr_provenance] Introduce optional
ptr_provenance operand to load/store
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev