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 base version is f8dbd61074176bae92ec360a093ac7bc498c9321 (May 18, 2021)

[jrmuizel]

What revision is the base for this change?

[jeroen.dobbelaere]

In D69542#1727793, @jrmuizel wrote:

What revision is the base for this change?

The is a rebase based on 82d3ba87d06f9e2abc6e27d8799587d433c56630

[jrmuizel]

Is this work stalled?

[jeroen.dobbelaere]

In D69542#1836340, @jrmuizel wrote:

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.

[jeroen.dobbelaere]

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

[jeroen.dobbelaere]

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

[jeroen.dobbelaere]

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.

[jeroen.dobbelaere]

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)

[barannikov88]

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.

[jeroen.dobbelaere]

Thanks for the detailed analysis !

[barannikov88]

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?

[jeroen.dobbelaere]

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]

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]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

494

Here you go:

test.ll3 KBDownload

$ 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]

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]

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

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.