Restrict pointers

Restrict pointers

[Jan Hoogerbrugge]

Hi,

As far as I know, memory references via two pointers where one of them is a 
restrict pointer and the other pointer is not restricted and is not derived 
from the first one are independent. GCC sees it differently: both pointers 
have to be restricted. I can demonstrate it by means of the following code:

int restrict_test0(int *p, int *q) /* no restrict pointers */
{
        *p = 0;
        return *q;
}

int restrict_test1a(int *restrict p, int *q) /* first pointer is restricted 
*/
{
        *p = 0;
        return *q;
}

int restrict_test1b(int *p, int *restrict q) /* second pointer is restricted 
*/
{
        *p = 0;
        return *q;
}

int restrict_test2(int *restrict p, int *restrict q) /* both pointers are 
restricted */
{
        *p = 0;
        return *q;
}

The scheduler would like the schedule the long latency load of *p before the 
store of *q. Dependences allow this only in the case of restrict_test2() 
where two restrict pointers are involved. This is the resulting Alpha code 
for 3.4.0 20040303:

$restrict_test0..ng:
restrict_test0:
        .frame $30,0,$26,0
        .prologue 0
        stl $31,0($16)
        ldl $0,0($17)
        ret $31,($26),1
        .end restrict_test0
        .align 2
        .align 4
        .globl restrict_test1a
        .ent restrict_test1a
$restrict_test1a..ng:
restrict_test1a:
        .frame $30,0,$26,0
        .prologue 0
        stl $31,0($16)
        ldl $0,0($17)
        ret $31,($26),1
        .end restrict_test1a
        .align 2
        .align 4
        .globl restrict_test1b
        .ent restrict_test1b
$restrict_test1b..ng:
restrict_test1b:
        .frame $30,0,$26,0
        .prologue 0
        stl $31,0($16)
        ldl $0,0($17)
        ret $31,($26),1
        .end restrict_test1b
        .align 2
        .align 4
        .globl restrict_test2
        .ent restrict_test2
$restrict_test2..ng:
restrict_test2:
        .frame $30,0,$26,0
        .prologue 0
        ldl $0,0($17)
        stl $31,0($16)
        ret $31,($26),1
        .end restrict_test2
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.4.0 20040303 (prerelease)"

As you can see, only in the case of restrict_rest2, the load is scheduled 
above the store. GCC should also do this in the case of restrict_test1a and 
restrict_test1b.

I already filed this as a bug (14192) but the status remains unconfirmed for 
several weeks. Could somebody tell whether this is ideed a performance bug?

Regards,
Jan

_________________________________________________________________
Talk with your online friends with MSN Messenger http://messenger.msn.nl/

Re: Restrict pointers

[Jim Wilson]

Jan Hoogerbrugge wrote:
> As far as I know, memory references via two pointers where one of them 
> is a restrict pointer and the other pointer is not restricted and is not 
> derived from the first one are independent.

I believe the problem here is "derived from".  If two pointers are both 
restricted, then clearly they don't alias.

If one pointer is restricted, then you have to perform tests to 
determine if the second pointer might be derived from the first.  These 
tests have not been implemented yet, and may be infeasible to implement 
in the current alias analysis code.  This is because the current code is 
based on RTL, and RTL is so low level that it is very hard to track 
pointer relationships.

It is probably more feasible to implement this in tree-ssa, where we 
have more info about declarations and assignments.  The derived from 
test should be much more feasible there.

Compilers are allowed to ignore restrict, so there is no bug here.  The 
only problem is that we have a missed optimization, because we don't 
have the infrastructure needed to implement the missed optimization. 
tree-ssa probably helps with the infrastructure problem.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: Restrict pointers

[Diego Novillo]

On Fri, 2004-03-12 at 13:15, Dan Nicolaescu wrote:
> Diego Novillo <dnovillo@redhat.com> writes:
> 
>   > On Fri, 2004-03-12 at 12:17, Dan Nicolaescu wrote:
>   > 
>   > > Dan, could you please take a look at why the code below is not
>   > > optimized?
>   > > 
>   > Have you tried -ftree-points-to=andersen?  The non-andersen parts of the
>   > aliasing pass do not handle restrict.
> 
> Yep, I did, it does not help. 
>
OK, thanks, so much for that.  I've taken the PR and will look at it
soonish.


Diego.

Re: Restrict pointers

[Dan Nicolaescu]

Diego Novillo <dnovillo@redhat.com> writes:

  > On Fri, 2004-03-12 at 12:17, Dan Nicolaescu wrote:
  > 
  > > Dan, could you please take a look at why the code below is not
  > > optimized?
  > > 
  > Have you tried -ftree-points-to=andersen?  The non-andersen parts of the
  > aliasing pass do not handle restrict.

Yep, I did, it does not help. 

Re: Restrict pointers

[Diego Novillo]

On Fri, 2004-03-12 at 12:17, Dan Nicolaescu wrote:

> Dan, could you please take a look at why the code below is not
> optimized?
> 
Have you tried -ftree-points-to=andersen?  The non-andersen parts of the
aliasing pass do not handle restrict.


Diego.

Re: Restrict pointers

[Dan Nicolaescu]

Daniel Berlin <dberlin@dberlin.org> writes:

>> Currently there is no special handling for restrict pointers (unless
>> the
>> generic alias set routines in alias.c support it).
>>
>
  > This isn't quite right.
  > I implemented handling of restrict pointers in the flow insensitive
  > aliasing part (through probably not as fully as it could be, i'm not
  > sure).


Dan, could you please take a look at why the code below is not
optimized?

void bar0 (int * __restrict__ arr1, int * __restrict__ arr2)
{
  arr1[0] = 1;
  arr2[0] = 1;
  if (arr1[0] != 1)
    link_error ();
}

This is PR14187.

Re: Restrict pointers

[Diego Novillo]

On Fri, 2004-03-12 at 10:58, Daniel Berlin wrote:

> I implemented handling of restrict pointers in the flow insensitive 
> aliasing part (through probably not as fully as it could be, i'm not 
> sure).
> 
Even better.  Thanks.


Diego.

Re: Restrict pointers

[Daniel Berlin]

> Currently there is no special handling for restrict pointers (unless 
> the
> generic alias set routines in alias.c support it).
>

This isn't quite right.
I implemented handling of restrict pointers in the flow insensitive 
aliasing part (through probably not as fully as it could be, i'm not 
sure).


>
> Diego.
>

Re: Restrict pointers

[Diego Novillo]

On Fri, 2004-03-12 at 10:27, Jan Hoogerbrugge wrote:

> What can we / I do to improve the handling of restrict pointers? Any idea
> of the difficulty and where to start?
> 
Could you take a look at tree-ssa?  We implement 3 alias analyses: flow
insensitive points-to, flow sensitive points-to and type based aliasing.

All these are implemented in tree-ssa-alias.c and tree-alias-*.c.  The
main driver for the alias pass is in
tree-ssa-alias.c:compute_may_aliases.  You will also find documentation
in doc/tree-ssa.texi.

Currently there is no special handling for restrict pointers (unless the
generic alias set routines in alias.c support it).


Diego.

Re: Restrict pointers

[Jan Hoogerbrugge]

>From: Jim Wilson <wilson@specifixinc.com>
>
>Jan Hoogerbrugge wrote:
>>As far as I know, memory references via two pointers where one of them is 
>>a restrict pointer and the other pointer is not restricted and is not 
>>derived from the first one are independent.
>
>I believe the problem here is "derived from".  If two pointers are both 
>restricted, then clearly they don't alias.
>
>If one pointer is restricted, then you have to perform tests to determine 
>if the second pointer might be derived from the first.  These tests have 
>not been implemented yet, and may be infeasible to implement in the current 
>alias analysis code.  This is because the current code is based on RTL, and 
>RTL is so low level that it is very hard to track pointer relationships.
>
>It is probably more feasible to implement this in tree-ssa, where we have 
>more info about declarations and assignments.  The derived from test should 
>be much more feasible there.
>
>Compilers are allowed to ignore restrict, so there is no bug here.  The 
>only problem is that we have a missed optimization, because we don't have 
>the infrastructure needed to implement the missed optimization. tree-ssa 
>probably helps with the infrastructure problem.

It's a pitty that GCC does not exploit all power of restrict pointers. I am
working on a port of GCC to the TriMedia VLIW processor and many
of the applications that are available for this processor use restrict 
pointers
extensively. Many compute kernels run a few times faster when restrict
pointers are present and fully exploited. I guess that this will be true for
many other instruction-level parallel processors for which applications have
been tuned.

What can we / I do to improve the handling of restrict pointers? Any idea
of the difficulty and where to start?

Jan

_________________________________________________________________
Play online games with your friends with MSN Messenger 
http://messenger.msn.nl/