[llvm-dev] pointer provenance introduction to load/store instructions

Tue Jun 15 01:53:01 PDT 2021

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