Nested restrict pointers: missed optimization & client with UB?

Nested restrict pointers: missed optimization & client with UB?

[Ties Klappe]

[-- Attachment #1: Type: text/plain, Size: 1741 bytes --]

Hi,

I have two questions related to nested restrict pointers.
GCC 13.02 with optimization level 3 optimizes the function *foo1* to simply
return 10.

int foo1(int *restrict *restrict p, int *restrict *restrict q)
{
    **p = 10;
    **q = 11;
    return **p;
}

I am curious why the function *foo2* is not optimized in the same way (see
https://godbolt.org/z/E4cx1c1GP): the first pointer dereference of p and q
result in the restrict qualified pointer lvalues, which are used to write
to a disjoint (as promised by the restrict qualifier) location storing an
integer object. So this should give enough information to perform the
optimization, i.e. a write via **q cannot change the object **p designates
if the program has defined behavior.

int foo2(int *restrict *p, int *restrict *q)
{
    **p = 10;
    **q = 11;
    return **p;
}

Secondly, if we would have a client *main* invoking *foo1* (see below), the
optimization would be incorrect if the client does not contain undefined
behavior. So I am curious how the standard section 6.7.3.1 actually applies
here: if the program is defined, I would assume both lvalues *p and *q are
said to be based on xp (xp = *p = *q; = object `*P` *where the standard
refers to), but is it actually the case that both the *p and *q expressions
are based on the same object P?

int main() {
    int x = 0;
    int* xp = &x;

    int res = foo1(&xp, &xp);

    return 0;
}

So to wrap up, I have two questions:

1. Should *foo2* be optimized in the same way as *foo1* and is it simply a
missed optimization candidate, or is there another reason GCC does not
optimize it?
2. Does the client *main* contain undefined behavior according to GCC, and
if so, why?

Thank you in advance.

Kind regards,
Ties

Re: Nested restrict pointers: missed optimization & client with UB?

[Richard Biener]

On Tue, Feb 13, 2024 at 2:02 PM Ties Klappe via Gcc <gcc@gcc.gnu.org> wrote:
>
> Hi,
>
> I have two questions related to nested restrict pointers.
> GCC 13.02 with optimization level 3 optimizes the function *foo1* to simply
> return 10.
>
> int foo1(int *restrict *restrict p, int *restrict *restrict q)
> {
>     **p = 10;
>     **q = 11;
>     return **p;
> }
>
> I am curious why the function *foo2* is not optimized in the same way (see
> https://godbolt.org/z/E4cx1c1GP): the first pointer dereference of p and q
> result in the restrict qualified pointer lvalues, which are used to write
> to a disjoint (as promised by the restrict qualifier) location storing an
> integer object. So this should give enough information to perform the
> optimization, i.e. a write via **q cannot change the object **p designates
> if the program has defined behavior.
>
> int foo2(int *restrict *p, int *restrict *q)
> {
>     **p = 10;
>     **q = 11;

this function could do

     int a;
     *p = &a;
     **q = 11;
     **p = 12;
>     return **q;

even when being called as you outline below.

> }
>
> Secondly, if we would have a client *main* invoking *foo1* (see below), the
> optimization would be incorrect if the client does not contain undefined
> behavior. So I am curious how the standard section 6.7.3.1 actually applies
> here: if the program is defined, I would assume both lvalues *p and *q are
> said to be based on xp (xp = *p = *q; = object `*P` *where the standard
> refers to), but is it actually the case that both the *p and *q expressions
> are based on the same object P?
>
> int main() {
>     int x = 0;
>     int* xp = &x;
>
>     int res = foo1(&xp, &xp);
>
>     return 0;
> }
>
> So to wrap up, I have two questions:
>
> 1. Should *foo2* be optimized in the same way as *foo1* and is it simply a
> missed optimization candidate, or is there another reason GCC does not
> optimize it?
> 2. Does the client *main* contain undefined behavior according to GCC, and
> if so, why?
>
> Thank you in advance.

We are optimizing the following which is related at least to the amount
of memory references done.  I'm also curious how the standard reads
here.  Implementation-wise it's a bit difficult to handle the
int ** restrict case, as points-to analysis has to handle *p and *q to
point to an object as if p and q themselves were restrict.  I'm not sure
that doesn't open up things for miscompiles.

int * restrict p;
int * restrict q;
int foo2()
{
    *p = 10;
    *q = 11;
    return *p;
}

int main ()
{
  int x = 0;
  int* xp = &x;
  p = xp;
  q = xp;
  int res = foo1();
  return 0;
}

Richard.

> Kind regards,
> Ties

Re: Nested restrict pointers: missed optimization & client with UB?

[Joseph Myers]

On Tue, 13 Feb 2024, Ties Klappe via Gcc wrote:

> int foo2(int *restrict *p, int *restrict *q)
> {
>     **p = 10;
>     **q = 11;
>     return **p;
> }

In this case, *p and *q might be the same restricted pointer object.  See 
the more detailed explanation at 
<https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192#c8>.

-- 
Joseph S. Myers
josmyers@redhat.com

Re: Nested restrict pointers: missed optimization & client with UB?

[Ties Klappe]

[-- Attachment #1: Type: text/plain, Size: 1532 bytes --]

Thank you both for your quick replies.

@Joseph, thank you for linking me to the other issue. If I understand
correctly what the point is, would you then agree that the program main
when calling foo2 has *defined* behavior?
What surprises me is that *p and *q might be the same restricted pointer:
the *xp* object itself is not declared as *int** *restrict* but as *int**.

By passing *xp* as argument to foo1, is the type of the object *xp* then
implicitly converted to (or merely interpreted as) *int* restrict *(because
of the argument type)*, i.e.* xp corresponds to the object *P *the standard
refers to?

int main() {
    int x = 0;
    int* xp = &x;

    int res = foo2(&xp, &xp);

    return 0;
}

---

@Richard, thank you for the alternative implementation. Is foo3 meant to be
optimized by GCC currently (I didn't manage to get GCC13.2 to do it)? Or is
it a hypothetical example that would allow GCC to optimize it?

int foo3(int *restrict * p, int *restrict * q)
{
    int a;
    *p = &a;
    **q = 11;
    **p = 12;
    return **q;
}

Kind regards,
Ties


Op di 13 feb 2024 om 15:29 schreef Joseph Myers <josmyers@redhat.com>:

> On Tue, 13 Feb 2024, Ties Klappe via Gcc wrote:
>
> > int foo2(int *restrict *p, int *restrict *q)
> > {
> >     **p = 10;
> >     **q = 11;
> >     return **p;
> > }
>
> In this case, *p and *q might be the same restricted pointer object.  See
> the more detailed explanation at
> <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192#c8>.
>
> --
> Joseph S. Myers
> josmyers@redhat.com
>
>

Re: Nested restrict pointers: missed optimization & client with UB?

[Joseph Myers]

On Tue, 13 Feb 2024, Ties Klappe via Gcc wrote:

> Thank you both for your quick replies.
> 
> @Joseph, thank you for linking me to the other issue. If I understand
> correctly what the point is, would you then agree that the program main
> when calling foo2 has *defined* behavior?

I think that's the case, yes.

-- 
Joseph S. Myers
josmyers@redhat.com

Re: Nested restrict pointers: missed optimization & client with UB?

[Richard Biener]

> Am 13.02.2024 um 16:27 schrieb Ties Klappe via Gcc <gcc@gcc.gnu.org>:
> 
> Thank you both for your quick replies.
> 
> @Joseph, thank you for linking me to the other issue. If I understand
> correctly what the point is, would you then agree that the program main
> when calling foo2 has *defined* behavior?
> What surprises me is that *p and *q might be the same restricted pointer:
> the *xp* object itself is not declared as *int** *restrict* but as *int**.
> 
> By passing *xp* as argument to foo1, is the type of the object *xp* then
> implicitly converted to (or merely interpreted as) *int* restrict *(because
> of the argument type)*, i.e.* xp corresponds to the object *P *the standard
> refers to?
> 
> int main() {
>    int x = 0;
>    int* xp = &x;
> 
>    int res = foo2(&xp, &xp);
> 
>    return 0;
> }
> 
> ---
> 
> @Richard, thank you for the alternative implementation. Is foo3 meant to be
> optimized by GCC currently (I didn't manage to get GCC13.2 to do it)? Or is
> it a hypothetical example that would allow GCC to optimize it?

It’s a situation to show handling your two examples the same would be difficult.

> int foo3(int *restrict * p, int *restrict * q)
> {
>    int a;
>    *p = &a;
>    **q = 11;
>    **p = 12;
>    return **q;
> }
> 
> Kind regards,
> Ties
> 
> 
> Op di 13 feb 2024 om 15:29 schreef Joseph Myers <josmyers@redhat.com>:
> 
>>> On Tue, 13 Feb 2024, Ties Klappe via Gcc wrote:
>>> 
>>> int foo2(int *restrict *p, int *restrict *q)
>>> {
>>>    **p = 10;
>>>    **q = 11;
>>>    return **p;
>>> }
>> 
>> In this case, *p and *q might be the same restricted pointer object.  See
>> the more detailed explanation at
>> <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192#c8>.
>> 
>> --
>> Joseph S. Myers
>> josmyers@redhat.com
>> 
>>