This is an archive of the discontinued LLVM Phabricator instance.

Full Restrict Support - single patch
Needs ReviewPublic

Authored by jeroen.dobbelaere on Oct 28 2019, 6:02 PM.

Details

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

Diff Detail

Event Timeline

jeroen.dobbelaere edited the summary of this revision. (Show Details)Oct 28 2019, 6:05 PM

What revision is the base for this change?

What revision is the base for this change?

The is a rebase based on 82d3ba87d06f9e2abc6e27d8799587d433c56630

Is this work stalled?

Is this work stalled?

Partly:

  • I still need to do the documentation work, creating a separate document for restrict/noalias.
  • Johannes wondered if we need to use operand bundles: http://lists.llvm.org/pipermail/llvm-dev/2019-November/136705.html
    • There is no resolution for this yet. If we decide that this is the way to go, I can migrate the full restrict support patch, once the load/store instructions support operand bundles.
MSxDOS added a subscriber: MSxDOS.Mar 2 2020, 7:36 AM
JOE1994 added a subscriber: JOE1994.Jun 7 2020, 9:56 AM
jeroen.dobbelaere edited the summary of this revision. (Show Details)
jeroen.dobbelaere edited the summary of this revision. (Show Details)Jun 15 2020, 12:38 AM
bmahjour removed a subscriber: bmahjour.Jun 15 2020, 6:41 AM
kkwli0 added a subscriber: kkwli0.Jun 15 2020, 7:11 AM
jeroen.dobbelaere edited the summary of this revision. (Show Details)

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

jeroen.dobbelaere edited the summary of this revision. (Show Details)
jeroen.dobbelaere added a subscriber: hfinkel.

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

D68509: Updated to correctly handle inlining when callee == caller. (Triggered by doing a stage2 compile)
D68515: Fixed build warning and testcase failure in Release mode.

Following changes were done:

  • use 'variant 1' approach for ptr_provenance argument, getting rid of 'NumUserOperandsDelta' (See D68488)
  • fix issue with new pass manager (See D68507)
  • fix testcase issue (See D68512)
mdchen added a subscriber: mdchen.Oct 7 2020, 12:50 AM
barannikov88 added inline comments.
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1770–1771

Suppose we have V2 with valid noalias provenance, and V1 without it.
V1 is a long chain of GEPs (longer than MaxLookupSearchDepth), finished with noalias.arg.guard.

When aliasCheck is called the first time, we get into the "then" branch of the "if", strip nothing, and getUnderlyingObject finds some base for V1 at the depth MaxLookupSearchDepth. This object will be passed to a recursive call of aliasCheck later as O1.

After that, aliasCheck is called recursively from aliasGEP, this time with O1 != nullptr and empty V2AAInfo. We get into the else branch of the if and strip out noalias.arg.guard from V1 chain. This effectively decreases depth of the expression, and DecomposeGEP called later from aliasGEP will return _different_ base object from O1.

This leads to failed assertion in aliasGEP which checks that DecomposeGEP found the same base as getUnderlyingObject.

Thanks for the detailed analysis !

barannikov88 added inline comments.Dec 17 2020, 1:38 PM
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
494 ↗(On Diff #292770)

@jeroen.dobbelaere
In case the instruction is Load or Store, its provenance operand is set UndefValue upon cloning. Is this behavior appropriate here?

elindsey removed a subscriber: elindsey.Dec 17 2020, 1:39 PM
jeroen.dobbelaere marked an inline comment as not done.Dec 18 2020, 1:07 AM
jeroen.dobbelaere added inline comments.
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
494 ↗(On Diff #292770)

@barannikov88
Good question. The restrict patches have had already a number of iterations. In the earlier versions, ptr_provenance information was dropped when cloning. The main reason was for safety: In a restrict world, you need to think what to do when cloning an instruction wrt the restrict validity: do we need to keep the same scopes/restrict variable or do we need to work on a copy. Dropping the info was a safety guard. But, we needed to keep the same number of arguments, so I used UndefValue to indicate a dropped ptr_provenance.

At that time, a missing ptr_provenance would result in 'safe analysis', as, both a ptr_provenance and a !noalias metadata were required to perform ScopeNoAliasAA. Later on, it became clear that we should also do analysis if no ptr_provenance was explicitly present (which meant the same as ptr == ptr_provenance) and the rules changed.

This probably means that just dropping the ptr_provenance when cloning is probably not the right thing to do any more.
And passes that use clone() on a load/store instruction should become aware of the potential extra dependency introduced by the ptr_provenance. Dropping it (in a restrict) world should only be done if also the !noalias metadata is removed. In a world where ptr_provenance is also used for tracking actual ptr_provenance, this might also not be true.

So no, this behavior is probably not appropriate here. Do you happen to have a testcase that confirms this ?

barannikov88 added inline comments.Dec 18 2020, 1:20 AM
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
494 ↗(On Diff #292770)

Thank you for the quick and detailed answer!
I have a testcase, but right now it contains some bits of proprietary information. I'll strip them off and post the test here later.

barannikov88 added inline comments.Dec 18 2020, 5:18 AM
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
494 ↗(On Diff #292770)

Here you go:

$ opt test.ll -loop-rotate -S -o -

You should be able to find the following line in the output:
%x.01 = load i8, i8* %src_ptr, ptr_provenance i8* undef, align 1, !tbaa !10, !noalias !9

The patch was aplied to the same base, the project is configured as:

-DBUILD_SHARED_LIBS=ON
-DLLVM_CCACHE_BUILD=ON
-DLLVM_TARGETS_TO_BUILD="X86"
-DLLVM_ENABLE_PROJECTS="clang"
-DLLVM_USE_LINKER=lld

PS
I believe I've seen similar behavior of the SimplifyCFG pass, I'll try to prepare a test for that, too.

barannikov88 added inline comments.Dec 18 2020, 6:26 AM
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
494 ↗(On Diff #292770)

I believe I've seen similar behavior of the SimplifyCFG pass, I'll try to prepare a test for that, too.

It appeared to be the same pass (LoopRotate). The dump just did not show the change with -print-after-all.

jeroen.dobbelaere marked an inline comment as not done.Dec 18 2020, 7:24 AM

@barannikov88
Thanks ! I have vacation the next two weeks, so things will be slow. But I'll take it into account for the next revision on which I am working.
If you have time you can always join the LLVM Alias Analysis Technical Call. The next one should be on January 5,2021; 12pm central time.

penzn added a subscriber: penzn.Jan 5 2021, 10:25 AM
jansvoboda11 resigned from this revision.Feb 19 2021, 5:17 AM
Matt added a subscriber: Matt.May 12 2021, 9:08 AM
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 edited the summary of this revision. (Show Details)
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 edited the summary of this revision. (Show Details)

Rebased to 3c4fad6a69887311f4e9feeca28126a89f314d45 (August 17, 2021)

gyiu added a subscriber: gyiu.Aug 26 2021, 1:45 PM
gyiu added inline comments.
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 marked an inline comment as done.
jeroen.dobbelaere edited the summary of this revision. (Show Details)

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.
anemet added a subscriber: anemet.Jan 21 2022, 9:40 PM
hkao13 added a subscriber: hkao13.Feb 1 2022, 2:01 PM
hkao13 added inline comments.
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 added inline comments.Feb 1 2022, 2:09 PM
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.

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

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

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

Thanks.

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.

Herald added a project: Restricted Project. · View Herald TranscriptApr 21 2022, 10:27 AM
Herald added subscribers: mattd, MaskRay. · View Herald Transcript

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 edited the summary of this revision. (Show Details)
  • Rebased
  • Track ptr_provenance also during lowering (this was not working any more when ptr_provenance got moved outside of AAMetaData)
mgabka added a subscriber: mgabka.Jun 29 2022, 5:50 AM

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 @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.

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 added inline comments.
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

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

Okay I will try to post the same comments there.

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.

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.

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

nikic added a comment.Dec 24 2022, 1:48 AM

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.

jeroen.dobbelaere edited the summary of this revision. (Show Details)
nikic added a comment.Jan 12 2023, 2:34 AM

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

dang removed a subscriber: dang.Jan 12 2023, 3:51 AM

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.

alefel added a subscriber: alefel.Feb 15 2023, 3:32 AM
ojeda added a subscriber: ojeda.Feb 19 2023, 4:52 AM
ram-NK added a subscriber: ram-NK.Apr 27 2023, 8:11 AM
ram-NK added inline comments.Apr 27 2023, 8:26 AM
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.

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.

khei4 added a subscriber: khei4.May 15 2023, 2:16 AM
jeroen.dobbelaere edited the summary of this revision. (Show Details)

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 added a comment.May 30 2023, 7:39 AM

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.

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 !

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.

Hello! I'm wondering what the plan is for this work given the ongoing switch to GitHub PRs and the closing of Phabricator? I believe this is work the community is still very interested in seeing landed (I certainly am!), but I'm skeptical of our ability to do that by the deadline and figure we should start talking about how to handle this sooner rather than later. Thanks!

CC @rnk for awareness on outstanding Phab reviews

Hello! I'm wondering what the plan is for this work given the ongoing switch to GitHub PRs and the closing of Phabricator? I believe this is work the community is still very interested in seeing landed (I certainly am!), but I'm skeptical of our ability to do that by the deadline and figure we should start talking about how to handle this sooner rather than later. Thanks!

CC @rnk for awareness on outstanding Phab reviews

Hi Aaron, I has some discussion about this in the last US LLVM conference. Consensus is to keep using phabricator for now (github does not work well with stacked reviews), but also to speed up the committing of changes that have already been accepted and preparation of remaining changes.
I am currently working on a rebase.

Thanks,

Jeroen Dobbelaere

Hello! I'm wondering what the plan is for this work given the ongoing switch to GitHub PRs and the closing of Phabricator? I believe this is work the community is still very interested in seeing landed (I certainly am!), but I'm skeptical of our ability to do that by the deadline and figure we should start talking about how to handle this sooner rather than later. Thanks!

CC @rnk for awareness on outstanding Phab reviews

Hi Aaron, I has some discussion about this in the last US LLVM conference. Consensus is to keep using phabricator for now (github does not work well with stacked reviews), but also to speed up the committing of changes that have already been accepted and preparation of remaining changes.
I am currently working on a rebase.

Excellent, that sounds like a great path forward. Thank you!