Revisit of pr38212 regarding restrict definition

Revisit of pr38212 regarding restrict definition

[Bingfeng Mei]

Hi,
I am working on how to improve "restrict". I noticed 
that my changes lead to failure of pr38212. After looking
at its code, I think the test may not be valid according
to c99 standard.

C99 standard 6.7.3.1: 

EXAMPLE 4 The rule limiting assignments between restricted pointers does not distinguish between a
function call and an equivalent nested block. With one exception, only ''outer-to-inner'' assignments
between restricted pointers declared in nested blocks have defined behavior.
{
  int * restrict p1;
  int * restrict q1;
  p1 = q1; // undefined behavior
  {
    int * restrict p2 = p1; // valid
    int * restrict q2 = q1; // valid
    p1 = q2; // undefined behavior
    p2 = q2; // undefined behavior
  }
}

pr38212.c
int __attribute__((noinline))
foo (int *__restrict p, int i)
{
  int *__restrict q;
  int *__restrict r;
  int v, w;
  q = p + 1;
  r = q - i;
  v = *r;
  *p = 1;
  w = *r;
  return v + w;
}
extern void abort (void);
int main()
{
  int i = 0;
  if (foo (&i, 1) != 1)
    abort ();
  return 0;
}

Isn't that "r = q - i" undefined?  "q = p + 1" may be also undefined,
depending whether we regard parameter p from outer or inner block. 

Cheers,
Bingfeng

Re: Revisit of pr38212 regarding restrict definition

[Richard Guenther]

On Tue, Nov 30, 2010 at 2:07 PM, Bingfeng Mei <bmei@broadcom.com> wrote:
> Hi,
> I am working on how to improve "restrict". I noticed
> that my changes lead to failure of pr38212. After looking
> at its code, I think the test may not be valid according
> to c99 standard.
>
> C99 standard 6.7.3.1:
>
> EXAMPLE 4 The rule limiting assignments between restricted pointers does not distinguish between a
> function call and an equivalent nested block. With one exception, only ''outer-to-inner'' assignments
> between restricted pointers declared in nested blocks have defined behavior.
> {
>  int * restrict p1;
>  int * restrict q1;
>  p1 = q1; // undefined behavior
>  {
>    int * restrict p2 = p1; // valid
>    int * restrict q2 = q1; // valid
>    p1 = q2; // undefined behavior
>    p2 = q2; // undefined behavior
>  }
> }
>
> pr38212.c
> int __attribute__((noinline))
> foo (int *__restrict p, int i)
> {
>  int *__restrict q;
>  int *__restrict r;
>  int v, w;
>  q = p + 1;
>  r = q - i;
>  v = *r;
>  *p = 1;
>  w = *r;
>  return v + w;
> }
> extern void abort (void);
> int main()
> {
>  int i = 0;
>  if (foo (&i, 1) != 1)
>    abort ();
>  return 0;
> }
>
> Isn't that "r = q - i" undefined?

Why?  r is based on q which is based on p.  If you write the source
as r = p + 1 - i; it'll have the same effect (and then it's clearly based on p).

  "q = p + 1" may be also undefined,
> depending whether we regard parameter p from outer or inner block.

you can avoid all the named temporaries by substituting the
pointer arithmetic into the dereferences.

Of course the middle-end may not do optimizations based on what
C thinks are "blocks".

Richard.

> Cheers,
> Bingfeng
>
>

RE: Revisit of pr38212 regarding restrict definition

[Bingfeng Mei]

> -----Original Message-----
> From: Richard Guenther [mailto:richard.guenther@gmail.com]
> Sent: 30 November 2010 13:53
> To: Bingfeng Mei
> Cc: gcc@gcc.gnu.org
> Subject: Re: Revisit of pr38212 regarding restrict definition
> 
> On Tue, Nov 30, 2010 at 2:07 PM, Bingfeng Mei <bmei@broadcom.com> wrote:
> > Hi,
> > I am working on how to improve "restrict". I noticed
> > that my changes lead to failure of pr38212. After looking
> > at its code, I think the test may not be valid according
> > to c99 standard.
> >
> > C99 standard 6.7.3.1:
> >
> > EXAMPLE 4 The rule limiting assignments between restricted pointers
> does not distinguish between a
> > function call and an equivalent nested block. With one exception,
> only ''outer-to-inner'' assignments
> > between restricted pointers declared in nested blocks have defined
> behavior.
> > {
> >  int * restrict p1;
> >  int * restrict q1;
> >  p1 = q1; // undefined behavior
> >  {
> >    int * restrict p2 = p1; // valid
> >    int * restrict q2 = q1; // valid
> >    p1 = q2; // undefined behavior
> >    p2 = q2; // undefined behavior
> >  }
> > }
> >
> > pr38212.c
> > int __attribute__((noinline))
> > foo (int *__restrict p, int i)
> > {
> >  int *__restrict q;
> >  int *__restrict r;
> >  int v, w;
> >  q = p + 1;
> >  r = q - i;
> >  v = *r;
> >  *p = 1;
> >  w = *r;
> >  return v + w;
> > }
> > extern void abort (void);
> > int main()
> > {
> >  int i = 0;
> >  if (foo (&i, 1) != 1)
> >    abort ();
> >  return 0;
> > }
> >
> > Isn't that "r = q - i" undefined?
> 
> Why?  r is based on q which is based on p.  If you write the source
> as r = p + 1 - i; it'll have the same effect (and then it's clearly
> based on p).
> 

But standard just plainly says it is undefined when you assign one 
restrict pointer to another restrict pointer in the same block level.

"If P is assigned the value of a pointer expression E that is based 
on another restricted pointer object P2, associated with block B2, 
then either the execution of B2 shall begin before the execution of B, 
or the execution of B2 shall end prior to the assignment. If these
requirements are not met, then the behavior is undefined."

Whether r is based on p is not important, IMO. Suppose p is not
restrict qualified. If we write

int *__restrict r = p + 1 - i;

Programmer just assumes that access through r won't be aliased 
with any other pointer, including p. If it turns out that i = 1
and r is indeed aliased with p. It is not compiler's fault to 
miscompile code, but programmer's fault to write wrong code. 

>   "q = p + 1" may be also undefined,
> > depending whether we regard parameter p from outer or inner block.
> 
> you can avoid all the named temporaries by substituting the
> pointer arithmetic into the dereferences.
> 

If we remove all the restricted temporary pointers, there is nothing
undefined here and is a valid test for sure. 
int __attribute__((noinline))
foo (int *__restrict p, int i)
 {
  int v, w;
  v = *(p + 1 - i);
  *p = 1;
  w = *(p + 1 - i);
  return v + w;
}


Bingfeng

> Of course the middle-end may not do optimizations based on what
> C thinks are "blocks".
> 
> Richard.
> 
> > Cheers,
> > Bingfeng
> >
> >

Re: Revisit of pr38212 regarding restrict definition

[Richard Guenther]

On Tue, Nov 30, 2010 at 3:29 PM, Bingfeng Mei <bmei@broadcom.com> wrote:
>
>
>> -----Original Message-----
>> From: Richard Guenther [mailto:richard.guenther@gmail.com]
>> Sent: 30 November 2010 13:53
>> To: Bingfeng Mei
>> Cc: gcc@gcc.gnu.org
>> Subject: Re: Revisit of pr38212 regarding restrict definition
>>
>> On Tue, Nov 30, 2010 at 2:07 PM, Bingfeng Mei <bmei@broadcom.com> wrote:
>> > Hi,
>> > I am working on how to improve "restrict". I noticed
>> > that my changes lead to failure of pr38212. After looking
>> > at its code, I think the test may not be valid according
>> > to c99 standard.
>> >
>> > C99 standard 6.7.3.1:
>> >
>> > EXAMPLE 4 The rule limiting assignments between restricted pointers
>> does not distinguish between a
>> > function call and an equivalent nested block. With one exception,
>> only ''outer-to-inner'' assignments
>> > between restricted pointers declared in nested blocks have defined
>> behavior.
>> > {
>> >  int * restrict p1;
>> >  int * restrict q1;
>> >  p1 = q1; // undefined behavior
>> >  {
>> >    int * restrict p2 = p1; // valid
>> >    int * restrict q2 = q1; // valid
>> >    p1 = q2; // undefined behavior
>> >    p2 = q2; // undefined behavior
>> >  }
>> > }
>> >
>> > pr38212.c
>> > int __attribute__((noinline))
>> > foo (int *__restrict p, int i)
>> > {
>> >  int *__restrict q;
>> >  int *__restrict r;
>> >  int v, w;
>> >  q = p + 1;
>> >  r = q - i;
>> >  v = *r;
>> >  *p = 1;
>> >  w = *r;
>> >  return v + w;
>> > }
>> > extern void abort (void);
>> > int main()
>> > {
>> >  int i = 0;
>> >  if (foo (&i, 1) != 1)
>> >    abort ();
>> >  return 0;
>> > }
>> >
>> > Isn't that "r = q - i" undefined?
>>
>> Why?  r is based on q which is based on p.  If you write the source
>> as r = p + 1 - i; it'll have the same effect (and then it's clearly
>> based on p).
>>
>
> But standard just plainly says it is undefined when you assign one
> restrict pointer to another restrict pointer in the same block level.
>
> "If P is assigned the value of a pointer expression E that is based
> on another restricted pointer object P2, associated with block B2,
> then either the execution of B2 shall begin before the execution of B,
> or the execution of B2 shall end prior to the assignment. If these
> requirements are not met, then the behavior is undefined."
>
> Whether r is based on p is not important, IMO. Suppose p is not
> restrict qualified. If we write
>
> int *__restrict r = p + 1 - i;
>
> Programmer just assumes that access through r won't be aliased
> with any other pointer, including p. If it turns out that i = 1
> and r is indeed aliased with p. It is not compiler's fault to
> miscompile code, but programmer's fault to write wrong code.
>
>>   "q = p + 1" may be also undefined,
>> > depending whether we regard parameter p from outer or inner block.
>>
>> you can avoid all the named temporaries by substituting the
>> pointer arithmetic into the dereferences.
>>
>
> If we remove all the restricted temporary pointers, there is nothing
> undefined here and is a valid test for sure.
> int __attribute__((noinline))
> foo (int *__restrict p, int i)
>  {
>  int v, w;
>  v = *(p + 1 - i);
>  *p = 1;
>  w = *(p + 1 - i);
>  return v + w;
> }

The middle-end will see exactly the same (temporaries with restrict
qualification being assigned a pointer that is restrict qualified).

The testcase basically models what the middle-end has to expect
and deal with, it doesn't try to be literally compliant with the C
standard.

Richard.

>
> Bingfeng
>
>> Of course the middle-end may not do optimizations based on what
>> C thinks are "blocks".
>>
>> Richard.
>>
>> > Cheers,
>> > Bingfeng
>> >
>> >
>
>
>