Full restrict support - status update

Hi all,

## Status:

During the past weeks I have updated the restrict patches with various improvements:
- the ScopedNoAliasAA now also works together with the new pass manager
- the SLPVectorizer now works nice with the noalias support.
- there were some issues with some of the options enabling/disabling full restrict. These have been fixed.
- various smaller enhancements.

Today, I rebased the patches. [1]
Based on the feedback at the 'full restrict' roundtable, I also created a single patch containing all changes. [2]

## Request for testing and feedback:

Extra help with the code review would be great [1].
This includes feedback on the design decisions and naming.

It would also be great if you could just try it out and check the effect on your benchmarks and testcases.
The single patch[2] should make it more convenient to try it out:
- If the full restrict support triggers a problem, I would like to hear about it.
- But, if it works and improves your benchmarks, I also would like to hear about it, either through
  phabricator, the llvm mailing list or in private.

## Known issues:

- For now, there is still no llvm-ir bitcode support for the load/store noalias_sidechannel argument.
- the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
-- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
    restrict pointers which have been declared in the same scope.

## Future changes
- Another request that came up during the round table, is to split up the documentation in two parts:
   a separate document describing the noalias architecture, and the LangRef, describing the intrinsics.
  I'll be working on that in the coming days.

Thanks,

Jeroen Dobbelaere

[1] https://reviews.llvm.org/D68484 [PATCH 01/38] [noalias] LangRef: noalias intrinsics and noalias_sidechannel documentation.
[2] https://reviews.llvm.org/D69542 Full Restrict Support - single patch

Hi all,

## Status:

During the past weeks I have updated the restrict patches with various improvements:
- the ScopedNoAliasAA now also works together with the new pass manager
- the SLPVectorizer now works nice with the noalias support.
- there were some issues with some of the options enabling/disabling full restrict. These have been fixed.
- various smaller enhancements.

Today, I rebased the patches. [1]
Based on the feedback at the 'full restrict' roundtable, I also created a single patch containing all changes. [2]

## Request for testing and feedback:

Extra help with the code review would be great [1].
This includes feedback on the design decisions and naming.

It would also be great if you could just try it out and check the effect on your benchmarks and testcases.
The single patch[2] should make it more convenient to try it out:
- If the full restrict support triggers a problem, I would like to hear about it.
- But, if it works and improves your benchmarks, I also would like to hear about it, either through
   phabricator, the llvm mailing list or in private.

## Known issues:

- For now, there is still no llvm-ir bitcode support for the load/store noalias_sidechannel argument.
- the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
-- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
     restrict pointers which have been declared in the same scope.

This, we can fix now independent of anything else. We should either fix
the test, if there's a reasonable way to fix it, or we should remove it.
If you can post a patch with an explanation of the problem, that would
be great.

Thanks again,

Hal

I’m wary of updating the test itself, as someone may re-vendor the GCC C torture suite, undoing those edits. However, we already exclude some tests in the GCC torture suite because they rely on UB. Having inspected pr38212.c, I am happy to add this test to the list of excluded tests with the explanation provided. I’ll commit that change today.

Sam

Jeroen Dobbelaere via llvm-dev <llvm-dev@lists.llvm.org> writes:

- the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
-- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
    restrict pointers which have been declared in the same scope.

What's the failure mode? Wrong answers or compiler abort? If the
latter, it would be nice if LLVM could emit a warning about illegal use
of restrict. Longer term, a RestrictSanitizer would be really helpful.

                      -David

Jeroen Dobbelaere via llvm-dev <llvm-dev@lists.llvm.org> writes:

> - the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
> -- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
> restrict pointers which have been declared in the same scope.

What's the failure mode? Wrong answers or compiler abort? If the
latter,

it would be nice if LLVM could emit a warning about illegal use
of restrict. Longer term, a RestrictSanitizer would be really helpful.

Yes :slight_smile:
I would think it would not require any runtime (think - asan/msan) support,
so i'm not sure why it could not be a part of UBSan proper.
In other words i'd like to *tentatively* claim this,
i may be interested to look into it, after the restrict support lands :slight_smile:

                      -David

Roman

Jeroen Dobbelaere via llvm-dev <llvm-dev@lists.llvm.org> writes:

- the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
-- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
     restrict pointers which have been declared in the same scope.

What's the failure mode? Wrong answers or compiler abort? If the
latter,
it would be nice if LLVM could emit a warning about illegal use
of restrict. Longer term, a RestrictSanitizer would be really helpful.

Yes :slight_smile:
I would think it would not require any runtime (think - asan/msan) support,
so i'm not sure why it could not be a part of UBSan proper.
In other words i'd like to *tentatively* claim this,
i may be interested to look into it, after the restrict support lands :slight_smile:

Great.

I'm not sure, however, how you do this without a runtime and shadow
memory. You need to add some dynamic data-flow analysis to determine
which pointers are based on which restrict-qualified pointers. This, in
addition to in-function instrumentation, needs some side channel to deal
with function calls (because you need to pass this information across
the function-call interface and it's not clear to me that changing the
ABI is generally practical) and values stored in memory (which likely
need shadow member). Then, for each byte of memory, you need to keep
track of which have been accessed by pointers based on
restrict-qualified pointers, which restrict-qualified pointers, and
appropriately clear out that data when the associated restrict-qualified
pointer goes out of scope.

-Hal

From: David Greene <greened@obbligato.org>

[...]

What's the failure mode? Wrong answers or compiler abort? If the
latter, it would be nice if LLVM could emit a warning about illegal use
of restrict. Longer term, a RestrictSanitizer would be really helpful.

                      -David

The compiler produces code that does not do what the testcase expects it to do.
This particular case could be detected and warned for at compile time (after inlining and constant propagation).

Greetings,

Jeroen

From: David Greene <greened@obbligato.org>

[...]

What's the failure mode? Wrong answers or compiler abort? If the
latter, it would be nice if LLVM could emit a warning about illegal use
of restrict. Longer term, a RestrictSanitizer would be really helpful.

                       -David

The compiler produces code that does not do what the testcase expects it to do.
This particular case could be detected and warned for at compile time (after inlining and constant propagation).

We can also certainly consider adding optimization remarks in to
generate this kind of information as well.

-Hal

Hi Jeroen,

Thank you very much for the great work, it is much appreciated.

  • For now, there is still no llvm-ir bitcode support for the load/store noalias_sidechannel argument.

Do you have plans to work on this in the near future? Do you know how much work it is and if there are significant hurdles?

Thanks,
Alexey

Hi Alexey,

Adding llvm-ir bitcode support means adding/adapting the tags for LOAD/STORE instructions and adding

the support for the noalias_sidechannel at the right places.

I had a short attempt to implement it when preparing the public patches, but I am not familiar with that

part of the llvm code. When I noticed that it would take a lot longer than anticipated, I postponed it.

Also because it is likely that the way how the noalias_sidechannel was added to LoadInst/StoreInst might

change.

At this moment, I am not planning to work on this. For the current implementation, there might be

a number of possibilities for adding support :

  • maybe 2 new tags are needed (FUNC_CODE_INST_{LOAD_NOALIAS,STORE_NOALIAS})

  • or maybe it is sufficient to add the noalias_sidechannels as extra operands and look at the number of

operands to see if they are present or not

  • or maybe it is sufficient to look at the number of operands, and the noalias_sidechannel operand should

be added with an extra bit, indicating if it is really there or not…

Greetings,

Jeroen Dobbelaere

Thanks, Jeroen.

We would love to see your patches merged as soon as possible, so I was wondering: do you think the lack of bitcode support will prevent that from happening?

Best,
Alexey

Hi Alexey,

From: Alexey Zhikhartsev

[..]

We would love to see your patches merged as soon as possible, so I was wondering: do you think the lack of bitcode support will prevent that from happening?

Yes, I think that the lack of bitcode support will prevent it.

During the Developers meeting, I also talked with Hal and Johannes.
They had some extra remarks:
- (1) the restrict implementation deserves a separate document. (I am working on that one)
- (2) they don't like the naming of 'noalias_sidechannel'.
- (3) they also have some other mechanisms in mind to add the 'sidechannel' to the load/store instructions
       (and maybe to function calls, intrinsics; currently that is handled through llvm.noalias.arg.guard)

For (2) and (3), I am waiting for a proposal from them :wink:

Greetings,

Jeroen Dobbelaere

Apologies for the delay.

>From: Alexey Zhikhartsev
[..]
> We would love to see your patches merged as soon as possible, so I was wondering: do you think the lack of bitcode support will prevent that from happening?

Yes, I think that the lack of bitcode support will prevent it.

During the Developers meeting, I also talked with Hal and Johannes.
They had some extra remarks:
- (1) the restrict implementation deserves a separate document. (I am working on that one)
- (2) they don't like the naming of 'noalias_sidechannel'.
- (3) they also have some other mechanisms in mind to add the 'sidechannel' to the load/store instructions
       (and maybe to function calls, intrinsics; currently that is handled through llvm.noalias.arg.guard)

For (2) and (3), I am waiting for a proposal from them :wink:

I would like to see the restrict support be merged but, as Jeroen
mentions above, I feel there are two design choices we have to
overthink. Here are short descriptions to get some feedback from the
community:

(A) Naming and restriction

The name "sidechannel" is unfortunate, it has various negative
connotations, e.g., the release notes that read:
"LLVM 10.0 now has sidechannel support for your restrict pointer"
will raise a lot of follow up questions.

What I think we actually do, and what we should call it, is "provenance"
tracking.

Now beyond the pure renaming of "sidechannel" into "provenance" (or sth.
similar) I want us to decouple provenance tracking from the noalias
logic. Noalias/restrict is one use case in which (pointer) provenance
information is useful but not the only one. If we add some mechanism to
track provenance, let's make it generic and reusable. Note that the
basic ideas are not much different to what the noalias RFC proposed.
The major difference would be that we have provenance information and if
that originates in an `llvm.restrict.decl` call we can use it for
(no)alias queries.

(B) Using operand bundles

Right now, loads and stores are treated differently and given a new
operand. Then there are intrinsics to decode other kinds of information.
As an alternative, we could allow operand bundles on all instructions
and use them to tie information to an instruction. The "sidechannel"
operand of a load would then look something like:
  load i32* %p [ "ptr_provenance"(%p_decl) ]
and for a store we could have
  store i32** %p.addr, i32* %p [ "ptr_provenance"(%p_decl) ]

The benefit is that we do not change the operand count (which causes a
lot of noise) but we still have to make sure ptr/value uses are not
confused with operand bundle uses. We can attach the information to more
than load/store instructions, also to remove the need for some of the
intrinsics.

Please let me know what you think!

Cheers,
  Johannes

Hi Johannes et al,

From: Doerfert, Johannes <jdoerfert@anl.gov>

[..]

> >From: Alexey Zhikhartsev
> [..]
> > We would love to see your patches merged as soon as possible, so I was
wondering: do you think the lack of bitcode support will prevent that from
happening?
>
> Yes, I think that the lack of bitcode support will prevent it.
>
> During the Developers meeting, I also talked with Hal and Johannes.
> They had some extra remarks:
> - (1) the restrict implementation deserves a separate document. (I am
working on that one)
> - (2) they don't like the naming of 'noalias_sidechannel'.
> - (3) they also have some other mechanisms in mind to add the 'sidechannel'
to the load/store instructions
> (and maybe to function calls, intrinsics; currently that is handled through
llvm.noalias.arg.guard)
>
> For (2) and (3), I am waiting for a proposal from them :wink:

I would like to see the restrict support be merged but, as Jeroen
mentions above, I feel there are two design choices we have to
overthink. Here are short descriptions to get some feedback from the
community:

(A) Naming and restriction

The name "sidechannel" is unfortunate, it has various negative
connotations, e.g., the release notes that read:
"LLVM 10.0 now has sidechannel support for your restrict pointer"
will raise a lot of follow up questions.

What I think we actually do, and what we should call it, is "provenance"
tracking.

Now beyond the pure renaming of "sidechannel" into "provenance" (or sth.
similar) I want us to decouple provenance tracking from the noalias
logic. Noalias/restrict is one use case in which (pointer) provenance
information is useful but not the only one. If we add some mechanism to
track provenance, let's make it generic and reusable. Note that the
basic ideas are not much different to what the noalias RFC proposed.
The major difference would be that we have provenance information and if
that originates in an `llvm.restrict.decl` call we can use it for
(no)alias queries.

"provenance" might indeed be a good name.

There is a big difference between a restrict declaration, and a restrict usage:
- the declaration intrinsic (llvm.noalias.decl) is used to track in the cfg the location
   where the restrict variable was declared. This is important to handle code motion,
   merging, duplication in a correct way (inlining, loop unrolling, ...)
- the restrict usage intrinsics (llvm.noalias and llvm.side.noalias) are used to indicate
   that from that point on, restrict (noalias) properties are introduced for that pointer.
  They can exist without an associated 'llvm.noalias.decl' (when the declaration is outside
   the function.)
Given that, I assume that you mean 'llvm.provenance.noalias' (~ llvm.side.noalias) instead
of 'llvm.restrict.decl'.

(B) Using operand bundles

Right now, loads and stores are treated differently and given a new
operand. Then there are intrinsics to decode other kinds of information.
As an alternative, we could allow operand bundles on all instructions
and use them to tie information to an instruction. The "sidechannel"
operand of a load would then look something like:
  load i32* %p [ "ptr_provenance"(%p_decl) ]
and for a store we could have
  store i32** %p.addr, i32* %p [ "ptr_provenance"(%p_decl) ]

The benefit is that we do not change the operand count (which causes a
lot of noise) but we still have to make sure ptr/value uses are not
confused with operand bundle uses. We can attach the information to more
than load/store instructions, also to remove the need for some of the
intrinsics.

To me, operand bundles sound to be more or less equivalent to the current
solution. It might also make the 'instruction cloning' easier, if we can omit the
'ptr_provenance' there. The change of the number of operands caused some
noise, but it is the changes in the amount of 'uses' of a pointer that refer to the
same instruction that caused the most problems. Especially when that instruction
was going to be erased. Operand bundles will still need those code changes.
(like in parts of D68516 and D68518)

As the 'Call' instruction already supports operand bundles, it could eliminate the need
for the 'llvm.noalias.arg.guard' intrinsic, which combines the normal pointer with the
side channel (aka provenance). But, after inlining, we still need to put that information
somewhere. Or it should be propagated during inlining.
Care must be taken not to lose that information when the 'call' is changed by optimizations
as, after inlining, that might result in wrong alias analysis conclusions.

Are you thinking of "operand bundles" support for just LoadInst/StoreInst, or for all
instructions ?

Greetings,

Jeroen Dobbelaere

Hi Johannes et al,

Trying to revive this discussion, as the restrict support is relevant for one of our teams.

Thank you,
Alina

Hi, everyone,

We’ve had a number of discussions recently, including on the Flang technical call, about potential improvements to LLVM’s alias analysis to support handling restrict and restrict-like semantics.

We would like to try having a call to discuss these issues further. Please, if you’re interested in joining, indicate your availability (prior to the end of this week):

https://doodle.com/poll/evhwr2eyfvcf8ib3

Thanks again,
Hal

Thanks to everyone who participated in the poll. The time that maximizes availability is:

Thursday, May 28th @ 9-10 AM central time / 2-3 PM UTC.

I’ll send out meeting information shortly.

-Hal

To join our call on Thursday, May 28th @ 9-10 AM central time / 2-3 PM UTC please use this information:

Meeting URL

https://bluejeans.com/643493129?src=join_info

Meeting ID

643 493 129

Want to dial in from a phone?

Dial one of the following numbers:

+1.312.216.0325 (US (Chicago))

+1.408.740.7256 (US (San Jose))

+1.866.226.4650 (US Toll Free)

(see all numbers - https://www.bluejeans.com/premium-numbers)

Enter the meeting ID and passcode followed by #

Connecting from a room system?

Dial: bjn.vc or 199.48.152.152 and enter your meeting ID & passcode

On our agenda, we’ll have:

  1. Scalability challenges and other issues discovered with the current infrastructure (especially, perhaps, with the noalias metadata).
  2. Proposed solutions: progress, outstanding challenges, how to make progress going forward.

We’ll formulate the detailed agenda and take notes from the call using this Google doc: https://docs.google.com/document/d/1ybwEKDVtIbhIhK50qYtwKsL50K-NvB6LfuBsfepBZ9Y/edit?usp=sharing

A summary will then be sent to the mailing list after the call. If you would like to add items to the agenda, please edit the document (or reply to this email).

Thanks again,
Hal

Hi Hal,

Thanks very much for scheduling the LLVM Alias Analysis Technical Call. I have added more details to the Google document.

Regards,
Tarique Islam
XL Fortran Compiler Development
IBM Toronto Software Lab
tislam@ca.ibm.com (905) 413-3190

graycol.gif“Finkel, Hal J. via llvm-dev” —2020-05-18 12:41:56 PM—To join our call on Thursday, May 28th @ 9-10 AM central time / 2-3 PM UTC please use this informati

Great, thanks!

Are you planning on just talking about these things with slides? Do we have other things to which we can link for people to read?

-Hal

Hal Finkel

Lead, Compiler Technology and Programming Languages

Leadership Computing Facility

Argonne National Laboratory

graycol.gif