Page MenuHomePhabricator

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 ffe262a198a9f9030991df6d3ddd812e74fa3523 (July 29, 2022)

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

There are a very large number of changes, so older changes are hidden. Show Older Changes
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

@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

@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

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

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

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.Wed, Jun 29, 5:50 AM