C++ Logo

std-proposals

Advanced search

Re: RFC: disjoint qualifier

From: Eric Lengyel <lengyel_at_[hidden]>
Date: Wed, 23 Sep 2020 14:40:44 -0700
Hi Jeroen --

Thanks for your input. The main ideas of the disjoint proposal are that (a)
restrict is not a good fit for C++, (b) disjoint makes use of the type
system to prevent at least one class of possible mistakes, and (c) when the
disjoint qualifier is present, the compiler can always assume no aliasing on
the affected storage. The correctness of this last assumption is the
responsibility of the programmer.

   disjoint int* gp6;
   void foo(disjoint int *p1, int *p2, int *p3, int i, int j) {
     int *p4=p1;
     disjoint int *p5=p1; // is this allowed ? --- YES, not UB
     *p1 = 1; // will this alias ? --- Compiler always assumes NO
     *p2 = 2; // may alias with *p3, any other aliases ? --- NO
     *p3 = 3; // may alias with *p2, any other aliases ? --- NO
     *p4 = 4; // will this alias ? --- Compiler must assume YES
     *p5 = 5; // will this alias ? --- Compiler always assumes NO
     *gp6= 6; // will this alias ? --- Compiler always assumes NO
     p1[i] = p1[j]+1; // will the store and the load alias ? --- Compiler
always assumes NO
   }

On the last line above, since *p1 is disjoint storage, the compiler is
allowed to assume no aliasing on all loads and stores without any further
analysis. There is no concept of 'based on'. It is the programmer's
responsibility to ensure that the sets of values attained by the indexes i
and j are themselves disjoint. (In this particular example, it would mean
that i != j when passed to the function, but you can imagine them being
something like loop indexes.) The disjoint keyword is a promise by the
programmer that accesses to the storage do not overlap. This includes any
patterns like strided accesses from n4150.

The disjoint qualifier is intended to be simple to implement and easy to
understand through its absolute effects. The compiler would never need to
figure out that one pointer is based on another, and it is not allowed to
deduce any non-aliasing properties from such a relationship.

The line "int *p4 = p1" would be the preferred way for a programmer to
inform the compiler that it's going to access the storage in a
possibly-aliased manner.

-- Eric




-----Original Message-----
From: Jeroen Dobbelaere <Jeroen.Dobbelaere_at_[hidden]>
Sent: Wednesday, September 23, 2020 9:58 AM
To: Ronan Keryell <rkeryell_at_[hidden]>; std-proposals_at_[hidden]
Cc: Eric Lengyel <lengyel_at_[hidden]>
Subject: RE: [std-proposals] RFC: disjoint qualifier

Hi Eric, Ronan et al,

I am not on the std-proposal mailing list, but I am glad that Ronan added me
to his reply.

Having implemented all of 'restrict' for clang/llvm [1], I can say that the
C restrict specification is dense and terse, but it is also complete. Extra
examples documenting the important consequences of the wording would have
been useful and lack thereof is one (but not the only one) of the things
that IMHO makes restrict hard to understand.

In a c++ world, 'restrict' has its place as a compiler extension, but it is
indeed not a good match.
As such, I can agree with some of the complaints in the
'disjoint_lengyel.pdf' document.

But I do not agree with the proposed solution. IMHO, a single 'disjoint'
qualifier on a type will not do. Also, IMHO, the proposal lacks a decent
description (See 10.1.7.1, para 3 and 7) on what the impact is of the
'disjoint' qualifier wrt to aliasing and 'based on'.

 Like:
   disjoint int* gp6;
   void foo(disjoint int *p1, int *p2, int *p3, int i, int j) {
     int *p4=p1;
     disjoint int *p5=p1; // is this allowed ?
     *p1 = 1; // will this alias ?
     *p2 = 2; // may alias with *p3, any other aliases ?
     *p3 = 3; // may alias with *p2, any other aliases ?
     *p4 = 4; // will this alias ?
     *p5 = 5; // will this alias ?
     *gp6= 6; // will this alias ?
     p1[i] = p1[j]+1; // will the store and the load alias ?
   }


More examples that show how a new feature is supposed to be used and be
useful are always welcome.
In this context, also examples showing what it is not expected to work are
useful, maybe not for the 'standard', but at least for the proposal. (Can we
model strided accesses, like in one of the examples in n4150 ? Next to the
aliasing guarantees, do we get guarantees about pointer comparisons ?
...)

Besides the effect on types and classes, it would also be interesting to
learn how the feature interacts with the standard library (std::vector, ...)
and templates.

With 'restrict', the 'based on' hierarchy is clearly defined, just like the
scope where it is valid.
In combination with c++, you want to be able to specify that a certain
access in a 'leaf function'
will/will not alias an access in another 'leaf function'. That is harder to
model with restrict.
I do think that the alias_set proposal (n4150) or at least, an improved
version of it, can have a role here. At the same time, it has the potential
of 'fixing' the type-safety issue that restrict has.

my 5 cents

Greetings,

Jeroen Dobbelaere
[1] https://reviews.llvm.org/D68484


> -----Original Message-----
> From: Ronan Keryell <rkeryell_at_[hidden]>
> Sent: Tuesday, September 22, 2020 22:52
> To: std-proposals_at_[hidden]
> Cc: Eric Lengyel <lengyel_at_[hidden]>; Jeroen Dobbelaere
> <dobbel_at_[hidden]>
> Subject: Re: [std-proposals] RFC: disjoint qualifier
>
> On 9/17/20 6:37 PM, Eric Lengyel via Std-Proposals wrote:
>
> > Standard C++ does not include the "restrict" qualifier from C, and
> > many serious problems arise when attempting to properly incorporate
> > it into the C++ language. The following proposal introduces a
> > superior alternative in the form of a "disjoint" qualifier that
> > functions differently in several important ways. The disjoint
> > qualifier is a clean and natural fit within the established design
> > of the C++ language, and it adds type-safe aliasing controls in a
backward-compatible manner.
> >
> >
> http://terathon.com/disjoint_lengyel.pdf
> >
> > Please discuss.
>
> That seems useful.
> It would be interesting to do some bibliography study, for example by
> comparing to the references at the end of
> http://lists.llvm.org/pipermail/llvm-dev/2019-October/135672.html
> --
> Ronan KERYELL, Xilinx Research Labs / San Josť, California.

Received on 2020-09-23 16:40:50