Agenda:
- Discussion about the next steps for getting the full restrict patches ready for inclusion. This also relates to pointer provenance and general Alias Analysis.
These notes were also added to the LLVM Alias Analysis Tech Call note tracker ( LLVM AA Technical Call - Notes - Google Docs )
Before Start
Started with a quick example about how provenance should be preserved by not removing a pointer comparison when pointers are the same. LLVM does not optimize one pointer away; GCC does (potential problematic), and LLVM used to as well. Important for, for example, the CHERI architecture.
https://godbolt.org/z/9nbYYd6v7
Note: The example does show that, for architectures where the pointer authentication/provenance is not tracked, the produced code by LLVM today is not optimal.
Start Roundtable
-
Recent months have seen more work on implementing local restrict, with goal to upstream.
-
Complex set of patches, close to the C standard. Several LLVM components need adaptation.
-
Currently preparing for a new full restrict RFC (previous RFC was in 2018).
- Initial feedback from limited group; goal is to discuss highlighted issues.
-
Not many people present at the round table are familiar with the restrict proposal.
-
Main topic for today: discussing unknown_provenance constant.
Background: summary of Changes for Restrict
-
Restrictness is introduced when reading a restrict pointer.
-
Every memory access is annotated with noalias metadata indicating active restrict pointers at that location.
-
Basic noalias intrinsic in the pointer path is difficult to optimize (either too opaque or too transparent). Could lead to wrong conclusions and therefore wrong code.
- Requires the introduction of a separate provenance path.
-
Proposed (and prototyped) solution: Memory instructions (load/store) receive an optional additional provenance argument.
-
Maintains compatibility with previous IR.
-
Most optimization passes don’t need to handle the additional argument initially. It should work “as is” (but could perhaps be improved).
-
Feedback on Design (outside of roundtable, discussed at the roundtable)
Background:
-
Cloning of load/store instructions (reason for introducing unknown_provenance):
-
keeps the same number of arguments (optional ptr_provenance argument)
-
If a ptr_provenance argument is present, it is replaced by a unknown_provenance.
-
This prevents problems with unadapted transformation passes (there might be dominance issues if the original value was kept)
-
It is up to If the transformation pass to replace it with a correct value.
-
-
This is introduced for cases where we either can’t preserve the actual provenance, or for cases where a pass is not yet adapted to preserve the correct provenance.
-
E.g., an instruction is moved up, pass doesn’t get fixed initially, so provenance isn’t moved. Safe fallback to UnknownProvenance.
-
When it “learns” about provenance, no longer UnknownProvenance.
-
Feedback:
-
Effect of special UnknownProvenance constant: You can now have a function with two allocas and a store with UnknownProvenance. You’re not sure if you can eliminate the alloca.
-
If you have UnknownProvenance, you can no longer have escape analysis.
-
Memory access with UnknownProvenance can access all memory.
-
You can escape only provenance, but any call can write to it with UnknownProvenance. Original call doesn’t know this.
-
-
No one cares about breaking out-of-tree passes, so that’s not a good reason to keep UnknownProvenance. → We can replace the ‘clone’ behavior with copying the reference of the ptr_provenance operand.
Clarifications about provenance
-
Provenance and pointer can be independent.
-
Originally (in the restrict patches), provenance always merged back with the pointers origin, but this was found to not be needed.
-
Feedback: People agree.
-
Question: Is UnknownProvenance only for passes that don’t yet handle provenance, or also a way out for transformations?
-
Bit of both, but we could block optimization.
-
Discussion on Provenance union/phi ?
-
Not everyone agrees that this will be fully sound/easy/useful.
-
Can have a model where a pointer can have multiple provenances, but it complicates things, such as the “inbounds” flag on GEP.
-
Consensus is that we shouldn’t combine/merge provenance.
-
Note: Current upstream implementation of noalias on argument is a wrong model for restrict pointer arguments:
-
If, in a function, you have a restrict pointer argument rp and a non-restrict pointer argument q, q can still point to the same objects of rp, but you must first assign it to rp and then do the access through rp. With the mapping of restrict pointer arguments onto the noalias attribute, that will not work and you will get wrong code.
void foo(int* restrict rp, int *q, int *r) {
*rp=42; // *rp and *q can alias (but we must not use *q directly)
rp=q;
*rp=43; // current LLVM assumes *rp and *q will never alias,
// even if done in this way
*r = 44; // *r will not alias with *rp (and not with *q)
}
Comment: Impossible to not update all passes; we just have to live with it. We might want to make the provenance argument mandatory at some point in time.
Discussion on fusing the pointer and provenance before a call (ptr.provenance intrinsic)
-
If we use provenance for more than restrict, would adding an intrinsic before each call be too much overhead ?
-
Maybe it should be an argument/attribute/operand bundle, like it is for load/store.
-
Comment: for load/store, the provenance is more important.
-
Comment: maybe start with load/store.
-
Note: you could make BasicAA a lot simpler if the provenance is directly available for a load/store.**
Note:** Previous objection was that separate provenance path might be too expensive
- Consensus now is that maybe it’s worth it.
If we all agree, what are the next steps?
Recommended way discussed in the LLVM AA TechCalls:
-
Start with new RFC
-
Clean up patches
-
Get reviews
-
Review all patches, then add them in a staged way.
The round table participants do not think this is the best order, they propose to upstream ptr provenance before the restrict support.
-
First add as an optional ptr_provenance argument. Fix all passes where issues pop up.
-
Eventually (over time), the ptr_provenance will not be optional any more. (single argument ptr version should be removed). Note: Will affect single-use checks.
-
Consensus: People don’t like making it optional, but counterargument is that this is already taking long, making it mandatory may make things more difficult. We’ll go forward in a pragmatic way.
Conclusions:
-
we will remove UnknownProvenance
-
we will prioritize upstreaming of ptr_provenance argument.
-
IF needed, add ptrtoint to “expose” the pointer
It would be hard to use in full restrict for Rust, but it might be useful for Fortran.
After round-table discussions:
- By thinking about an undefined behavior detection mechanism for LLUBI, we came up with a more formal way of explaining the effects of the intrinsics/meta data. This also exposed places where the current implemented analysis can be improved.
Thank you all for the interesting discussion and the good feedback !