Re: RFC: Add ADD_RESTRICT tree code

[Jakub Jelinek <jakub at redhat dot com>]

On Thu, Oct 13, 2011 at 01:38:44AM +0200, Michael Matz wrote:
> IMO reading the standard to allow an access to be 
> based "on s.p _as well as_ t->p" and that this should result in any 
> sensible behaviour regarding restrict is interpreting too much into it.  

No.  Because s.p and t->p designates (if the wrapper function returns
the address it was passed as the first argument, otherwise may designate)
the same object.  And the based on P relation is basing on objects,
not expressions - "expression E based on object P" in the standard.

> Let's do away with the fields, trying to capture the core of the 
> disagreement.  What you seem to be saying is that this code is 
> well-defined and shouldn't return 1:
> 
> int foo (int * _a, int * _b)
> {
>   int * restrict a = _a;
>   int * restrict b = _b;
>   int * restrict *pa = wrap (&a);                                       
>   *pa = _b;         // 1
>   *a = 0;
>   **pa = 1;
>   return *a;
> }

This is valid.  *pa and a expressions designate (if wrap returns the passed
in pointer) the same object, pa itself is not restrict, thus it is fine
if both of those expressions are used to access the object a.
The store to the restrict object (// 1) is fine, the standard has only
restrictions when you assign to the restrict pointer object a value based
on another restrict pointer (then the inner block resp. return from block
rules apply), in the above case _b is either not based on any restrict
pointer, or could be based on a restrict pointer associated with some outer
block (caller).  Both *a and **pa lvalues have (or may have) address based
on the same restricted pointer object (a).

Of course if you change the above to
int * restrict * restrict pa = wrap (&a);
the testcase would be invalid, because then accesses to a would be done
through both expression based on the restricted pointer pa and through a
directly in the same block.  So, you can disambiguate based on
int *restrict*pa or field restrict, but only if you can first disambiguate
that *pa and a is not actually the same object.  That disambiguation can
be through restrict pa or some other means (PTA/IPA-PTA usual job).

> I think that would go straight against the intent of restrict.  I'd read 
> the standard as making the above trick undefined.

Where exactly?

> > Because, if you change t->p (or s.p) at some point in between t->p = q; 
> > and s.p[0]; (i.e. prior to the access) to point to a copy of the array, 
> > both s.p and t->p change.
> 
> Yes, but the question is, if the very modification of t->p was valid to 
> start with.  In my example above insn 1 is a funny way to write "a = _b", 
> i.e. reassigning the already set restrict pointer a to the one that also 
> is already in b.  Simplifying the above then leads to:
> 
> int foo (int * _a, int * _b)
> {
>   int * restrict a = _a;
>   int * restrict b = _b;
>   a = _b;
>   *a = 0;
>   *b = 1;
>   return *a;
> }
> 
> which I think is undefined because of the fourth clause (multiple 
> modifying accesses to the same underlying object X need to go through one 
> particular restrict chain).

Yes, this one is undefined, *_b object is modified
and accessed here through lvalues based on different restrict pointer
objects (a and b).  Note that in the earlier testcase, although
you have int * restrict b = _b; there, nothing is accessed through lvalue
based on b, unlike here.

> Seen from another perspective your reading would introduce an 
> inconsistency with composition.  Let's assume we have this function 
> available:
> 
> int tail (int * restrict a, int * restrict b) {
>   *a = 0;
>   *b = 1;
>   return *a;
> }
> 
> Clearly we can optimize this into { *a=0;*b=1;return 0; } without 
> looking at the context.  Now write the testcase or my example above in 

Sure.

> terms of that function:
> 
> int goo (int *p, int *q)
> {
>   struct S s, *t;
>   s.a = 1;
>   s.p = p;       // 1
>   t = wrap(&s);  // 2 t=&s in effect, but GCC doesn't see this
>   t->p = q;      // 3
>   return tail (s.p, t->p);
> }
> 
> Now we get the same behaviour of returning a zero.  Something must be 
> undefined here, and it's not in tail itself.  It's either the call of 
> tail, the implicit modification of s.p with writes to t->p or the 
> existence of two separate restrict pointers of the same value.  I think 
> the production of two separate equal-value restrict pointers via 
> indirect modification is the undefinedness, and _if_ the standard can be 
> read in a way that this is supposed to be valid then it needs to be 
> clarified to not allow that anymore.

This is undefined, the undefined behavior happens when running the tail.
The same object X (*q) is modified and accessed through lvalue based on
restricted pointer object a as well as through lvalue based on restricted
pointer b.

> I believe the standard should say something to the effect of disallowing 
> modifying restrict pointers after they are initialized/assigned to once.

The standard doesn't say anything like that, and it would e.g. break all the
code that does:
void foo (int *restrict a, int *restrict b)
{
  int i;
  for (i = 0; i < 50; i++)
    *a++ = *b++;
}
etc.  Furthermore, field restrict would result in not being able to ever
modify the field, e.g. if you have a global object
struct S { int i; char *restrict p; } s;
then you couldn't ever set it (except for = { 3, &foo } static initializer).

So, to your patch, adding ADD_RESTRICT whenever something not TYPE_RESTRICT
is cast to TYPE_RESTRICT in the gimplifier must not include the extra casts
added in the gimplifier in order to store a pointer into a restrict pointer
memory object (field or *ptr etc.).

	Jakub