Re: RFC: Add ADD_RESTRICT tree code

[Richard Guenther <richard dot guenther at gmail dot com>]

On Thu, Oct 13, 2011 at 10:41 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> 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.).

I suggested that for a final patch we only add ADD_RESTRICT in the
gimplifier for restrict qualified parameters, to make the inlining case
work again.  ADD_RESTRICTs for casts to restrict qualified pointers
I would add at parsing time, exactly when a literal cast to a
restrict qualified pointer from a non-restrict qualified pointer happens
in the source.  Everything else sounds too fragile IMHO.

We'd continue to handle restrict on globals from inside points-to analysis.

Thanks,
Richard.

> ? ? ? ?Jakub
>