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

Diff Detail

Unit TestsFailed

TimeTest
120 msx64 debian > Polly.Support::pipelineposition.ll
Script: -- : 'RUN: at line 2'; opt -polly-process-unprofitable -polly-remarks-minimal -polly-use-llvm-names -polly-import-jscop-dir=/var/lib/buildkite-agent/builds/llvm-project/polly/test/Support -polly-codegen-verify -O3 -enable-new-pm=0 -polly -polly-position=early -disable-output -debug-only=polly-scops < /var/lib/buildkite-agent/builds/llvm-project/polly/test/Support/pipelineposition.ll 2>&1 | FileCheck /var/lib/buildkite-agent/builds/llvm-project/polly/test/Support/pipelineposition.ll --check-prefix=NOINLINE

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

@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