Full Restrict Support - single patch

[jeroen.dobbelaere]

Summary

This is a convenience patch that covers all 27 patches starting from D68484 through D68523. It implements the support for full C99 restrict in clang/llvm.

Any feedback about how it behaves on your benchmarks and testcases is welcome !

Any help with code review is also welcome. That should happen on the separate patches.
(The part that is currently up for review is on D111159, introducing unknown_provenance and ptr_provenance)

The base version is dd2e681612f1f09d92abc9e16f5f65293e3fe725 (May 27, 2023)

NOTE: (January 9, 2023) - added xfail clang/test/CodeGen/restrict/capture_checks_01.c testcase to track missing pointer escape analysis.

NOTE: (June 21, 2021) - full restrict is now again enabled by default - this update also contains a number of bugfixes (triggered by csmith) - llvm.noalias.copy.guard now uses a representation based on offsets for knowing where in memory noalias pointers are stored (documentation is not yet updated) - the separate patches are not yet in sync with this version

Note: (November 17,2021)

• Moved NoAliasProvenance out of AAMetadata. Added PtrProvenance to MemoryLocation
• Introduced UnknownProvenance constant
• Added support for (some) atomic instructions.

Note: (July 29, 2022)

• Track ptr_provenance again during selectiondag lowering

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.

[jeroen.dobbelaere]

NOTE: the latest update missed two mandatory changes: - in clang/include/clang/Driver/Options.td : the DefaultFalse should become a DefaultTrue in order to enable the full restrict by default. - in clang/lib/Driver/ToolChains/Clang.cpp, '"-use-noalias-intrinsic-during-inlining=0"' must become '"-use-noalias-intrinsic-during-inlining=scopes"'

[jeroen.dobbelaere]

NOTE: (June 21, 2021) - full restrict is now again enabled by default - this update also contains a number of bugfixes (triggered by csmith) - llvm.noalias.copy.guard now uses a representation based on offsets for knowing where in memory noalias pointers are stored - the separate patches are not yet in sync with this version

[jeroen.dobbelaere]

Rebased to 3c4fad6a69887311f4e9feeca28126a89f314d45 (August 17, 2021)

[jeroen.dobbelaere]

Compile time impact: https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps%2Fperf%2Ffull_restrict-20210817-01

[gyiu]

llvm/lib/Transforms/Scalar/SROA.cpp

3954

Missing this line to make sure NoAlias Instruction doesn't self-reference.

NoAlias->setOperand(0, Load);

[jeroen.dobbelaere]

Rebased to 8924ba3bf8c6b0e8d14dff455e4e449a426a2700 (November 17, 2021)

Note: (November 17,2021)

• Moved NoAliasProvenance out of AAMetadata. Added PtrProvenance to MemoryLocation
• Introduced UnknownProvenance constant
• Added support for (some) atomic instructions.

[hkao13]

llvm/lib/IR/IRBuilder.cpp

579

This is a case when clang codegen creates a bitcast for NoAliasLoad, causing the TBAA issue mentioned above.

Is it possible to remove this code entirely? Looking into getMangledTypeStr(), it seems like literal structs will be prefixed with "sl_".

Thank you.

[hkao13]

clang/lib/CodeGen/CGExpr.cpp

1759

Metadata copied over from Load to NoAliasLoad may include TBAA. NoAliasLoad may be a bitcast instruction which will cause IR verifier to assert if TBAA metadata is attached.

[jeroen.dobbelaere]

Hi @hkao13 You happen to have some reduced testcases that show the problem ? Thanks !

[hkao13]

Hi @jeroen.dobbelaere, the above two comments of mine are in the wrong order, sorry.

I have attached a C test case, and the problem I'm seeing related to the above comments can be replicated using:

clang -flegacy-pass-manager -ffull-restrict -fstrict-aliasing -O1 test-verify.c

test-verify.c122 BDownload

The output error I see is on a bitcast instruction:
This instruction shall not have a TBAA access tag!

Thanks.

[D.Kharlamov]

Hi. I tried to use your patch for my project. My main concern is AA in MachineScheduler.
I noticed what ptr_provenance info is not passed to CodeGen.
It could be fixed by adding it to MemoryMachineOperand constructor in SelectionDAGBuilder::visitLoad and SelectionDAGBuilder::visitStore.
Also invocation of AAResults::alias in Codegen lacks of PtrProvenance argument in MemoryLocation constructors.
After this fixes AA in MachineScheduler is working fine.

[jeroen.dobbelaere]

In D69542#3465162, @D.Kharlamov wrote:

Hi. I tried to use your patch for my project. My main concern is AA in MachineScheduler.
I noticed what ptr_provenance info is not passed to CodeGen.
It could be fixed by adding it to MemoryMachineOperand constructor in SelectionDAGBuilder::visitLoad and SelectionDAGBuilder::visitStore.

Hi @D.Kharlamov, thanks for notifying this. Originally, the ptr_provenance was part of the AAMDNodes, so it would be automatically part of those places.
When extracting the ptr_provenance support, I moved it out of AAMDNodes, as that was not the logical place for it to reside. This explicit passing should indeed be
added in the SelectionDAGBuilder::visitLoad/visitStore. (Note that MachinePointerInfo already supports the optional ptr_provenance argument).

Any help with reviewing the ptr_provenance patches (See D107354 and related) is appreciated. Getting these reviewed and accepted is the next step in adding full restrict support.

Also invocation of AAResults::alias in Codegen lacks of PtrProvenance argument in MemoryLocation constructors.
After this fixes AA in MachineScheduler is working fine.

Also here, we will need to pass the ptr_provenance explicitely. Could you point me to a file and location for this case ?

Thanks,

Jeroen Dobbelaere

[jeroen.dobbelaere]

• Rebased
• Track ptr_provenance also during lowering (this was not working any more when ptr_provenance got moved outside of AAMetaData)

[vzakhari]

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

[jeroen.dobbelaere]

In D69542#3932775, @vzakhari wrote:

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

Hi @vzakhari , I'll give it another respin, but it will likely take a week or 2-3.

[vzakhari]

In D69542#3933523, @jeroen.dobbelaere wrote:

In D69542#3932775, @vzakhari wrote:

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

Hi @vzakhari , I'll give it another respin, but it will likely take a week or 2-3.

I see. It will still be great to try it with the latest Flang, but I can try the patch on top of ffe262a198a9f9030991df6d3ddd812e74fa3523 in the meantime. Thank you!

[RalfJung]

llvm/docs/LangRef.rst

9966–9971

Rust and C also have a notion of "pointer provenance", but it is subtly difference: provenance in those languages is something that flows with pointer values. IOW, a value of pointer type consists of some address in memory, plus some "provenance" metadata. LLVM also has that kind of provenance, it is needed e.g. to explain some of the behavior of getelementptr. (A pointer returned by getelementptr without inbounds can go out-of-bounds but must not be used to access memory outside the bounds of the allocation it started with. In other words, the pointer "remembers" the allocation it is associated with in some way that is separate from the integer address it points to.)

Is it a good idea to use the same term for this slightly different concept? A load operation already receives provenance from its pointer argument, and now with this patchset it *also* receives something else, but also called provenance, via a separate argument.

23372

From what I was able to see (but maybe I missed something), the docs do not say what exactly happens when these aliasing requirements are violated. I would expect that this results in immediate UB. During some recent discussion, it was suggested that noalias-violating loads might return poison instead of causing UB, but I think that proposal has problems. Either way though the docs should clearly state what the behavior is in that case.

23401

should probably be: how "they" work

[jeroen.dobbelaere]

Hi Ralf, thanks for your feedback !

This convenience patch is made available to show what the total picture looks like. The current set of extracted patches (ptr_provenance and unknown_provenance) that is available for review can be found here: D104268 (and in the 'stack')

Any help in reviewing and feedback is appreciated !

Thanks,

Jeroen Dobbelaere

llvm/docs/LangRef.rst

9966–9971

This is rather an extension of this concept than a different concept: the patches extend the notion of a pointer that represents a value + provenance. For the load/store instructions, when no ptr_provenance is present, the single pointer represents both the value and provenance (and getPtrProvenance() will return this value). When the ptr_provenance` argument has been set it means that for these instructions, the getPointerOperand now only points to the value. The getPtrPtrProvenance() and getOptionalPtrProvenance() will now return the separate ptr_provenance.

It is still assumed that a single pointer contains both value and provenance.

23372

This explanation is indeed missing. In practice, noalias-violating loads must be kept as ok. noalias-violating loads in combination with a noalias-violating store results in undefined behavior. The background for this is that: reorderings of a noalias-violating load/load should not harm. Reorderings of a noalias-violating store/store, load/store or store/load might result in unwanted results.

23401

Indeed

[RalfJung]

Okay I will try to post the same comments there.

[RalfJung]

Hm I cannot find the diff that the 2nd and 3rd comment refer to in https://reviews.llvm.org/D104268? Am I looking at the wrong thing? It refers to the new "Scoped NoAlias Related Intrinsics" section of the LangRef.
Sorry for the noise. This patchset stuff is really confusing, I have no clue how to navigate them.

[jeroen.dobbelaere]

In D69542#4010990, @RalfJung wrote:

Hm I cannot find the diff that the 2nd and 3rd comment refer to in https://reviews.llvm.org/D104268? Am I looking at the wrong thing? It refers to the new "Scoped NoAlias Related Intrinsics" section of the LangRef.

Hi Ralf, the ptr_provenance patches do not contain the description of the various noalias intrinsics. I will create separate patches for this once the ptr_provenance set of changes have been reviewed and committed.

Sorry for the noise. This patchset stuff is really confusing, I have no clue how to navigate them.

I tried to provide the real dependencies in the 'stack'. Maybe it is better to just go for a fake linear dependency chain.

[RalfJung]

I see, thanks. I guess this summary patch is then the best place for those comments still.

[nikic]

In D69542#3933523, @jeroen.dobbelaere wrote:

In D69542#3932775, @vzakhari wrote:

Hi @jeroen.dobbelaere, can you please rebase the patch? I would like to try @llvm.noalias for Flang generated IR, but the patch would not apply cleanly. Thank you!

Hi @vzakhari , I'll give it another respin, but it will likely take a week or 2-3.

If there's a version of the patch that applies to either release/15.x or current main, I'd like to test this against Rust. The last time I tried this I didn't get far due to the type mangling issues, but those have been fixed, so I think it would be worthwhile to try again, both from a correctness and compile-time perspective.

Especially the ptr_provenance change seems like it could have many silent failure points. I know we have a lot of code that assumes that a pointer used by a load is the loaded pointer, which is true right now, but does not hold with ptr_provenance.

[nikic]

Thanks for the rebase!

I tested the updated patch with rustc, but unfortunately didn't get very far again. The proc_macro build fails with verifier errors:

llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %22 = call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %8, ptr %19, ptr null, ptr undef, i64 0, metadata !4794), !noalias !4796
llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %23 = tail call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %11, ptr %20, ptr null, ptr undef, i64 0, metadata !4798), !noalias !4796
llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %44 = call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %8, ptr %42, ptr null, ptr undef, i64 0, metadata !4808), !noalias !4810
llvm.provenance.noalias scope arg must match with llvm.noalias.decl
  %45 = tail call ptr @llvm.provenance.noalias.p0.p0.p0.p0.i64(ptr nonnull %11, ptr %41, ptr null, ptr undef, i64 0, metadata !4812), !noalias !4810
LLVM ERROR: Broken module found, compilation aborted!

Here is the input IR (run under e.g. opt -O2): https://gist.github.com/nikic/fb9701235151e199fff0a23530808539

[jeroen.dobbelaere]

In D69542#4046725, @nikic wrote:

Thanks for the rebase!

I tested the updated patch with rustc, but unfortunately didn't get very far again. The proc_macro build fails with verifier errors:
...
Here is the input IR (run under e.g. opt -O2): https://gist.github.com/nikic/fb9701235151e199fff0a23530808539

Hi @nikic, thanks for trying it out. I am able to reproduce the problem and was also able to produce a reduced version. I'll provide an update once I have a fix.

[ram-NK]

llvm/lib/Transforms/Scalar/LICM.cpp

2097

Rodinia/backprop benchmark of llvm-test-suite is failed, When I test with this patch.
My analysis points to a restrict argument ( %hidden_units in bpnn_train_kernel()), Which is promoted by LICM.

[jeroen.dobbelaere]

llvm/lib/Transforms/Scalar/LICM.cpp

2097

Thanks for the report. I am currently working on a rebase. Once that is available (and published) I'll be working on this and some other issues that were reported.

[jeroen.dobbelaere]

This is a rebase, based on dd2e681612f1f09d92abc9e16f5f65293e3fe725 (May 27, 2023). It fully incorporates the ptr_provenance patches (D111159)

There are a number of known issues that have not yet been resolved. Those are available in testcases and have been marked with XFAIL
(a grep for XFAIL in this patch should show them) :

• wrong (too optimistic) assumption when mixing restrict and non-restrict based pointers:
  • with a global variable as restrict pointer
  • escape analysis misses cases where a noalias pointer (restrict annotated pointer) escapes through a double (or more) indirection
• LICM introduces inconsistencies in noalias.scope metadata (through phi nodes).
• LICM exposes an issue with AliasSet where ptr_provenance data is missed.

In the most recent rebase (between May 13 and may 27), I also noticed a change in behavior for an OpenMP testcase. That testcase has also been changed to XFAIL.

During June, I should be able to come up with an update that fixes those known issues.

As usual, any feedback is welcome. If you want to help out or discuss, you can always join the 4-weekly LLVM AA Technical calls.

[nikic]

For the record, I tested the new rebase and the "llvm.provenance.noalias scope arg must match with llvm.noalias.decl" issue still exists. I wasn't sure whether it was supposed to be fixed or not.

[jeroen.dobbelaere]

In D69542#4380832, @nikic wrote:

For the record, I tested the new rebase and the "llvm.provenance.noalias scope arg must match with llvm.noalias.decl" issue still exists. I wasn't sure whether it was supposed to be fixed or not.

That problem is indeed not fixed. It is also related to a new check with PHI nodes that already triggers in the .ll file that you provided earlier.

Thanks for testing !

[ram-NK]

Hi @jeroen.dobbelaere,
Following issue is identified during my testing.
GVN Pass is not copying ptr_provenance to new Load. due to this test-suite/MicroBenchmarks/LCALS/SubsetCRawLoops benchmark is giving noalias to same pointer( one is with provenance details and other without).
But unfortunately benchmark is not failing.

Always there is possibility of wrong AA analysis result, if ptr_provenance propagation is not done in any of the passes/new passes.
Adding an assertion to prevent these cases will be helpful.