restrict and char pointers

restrict and char pointers

[Jeroen Dobbelaere]

Hi,

I have a question concerning '__restrict__' :

With gcc-4.0.0 (-O3 -fomit-frame-pointer, on i686), following piece of code :


void test_1(unsigned long* __restrict__ bar, unsigned long* __restrict__ bas)
{
  unsigned long tmp = *bar;
  *bas = 0;
  *bar = tmp;
}

void test_2(unsigned long* __restrict__ bar, char* __restrict__ bas)
{
  unsigned long tmp = *bar;
  *bas = 0;
  *bar = tmp;
}


compiles to :

_Z6test_1PmS_:
	movl	8(%esp), %edx
	movl	$0, (%edx)
	ret


_Z6test_2PmPc:
	movl	4(%esp), %eax
	movl	8(%esp), %edx
	movl	(%eax), %ecx
	movb	$0, (%edx)
	movl	%ecx, (%eax)
	ret



I would expect that the second case compiles to :
	movl	8(%esp), %edx
	movb	$0, (%edx)
	ret


Greetings,
-- 
Jeroen Dobbelaere

Re: restrict and char pointers

[James E Wilson]

Jeroen Dobbelaere wrote:
> void test_2(unsigned long* __restrict__ bar, char* __restrict__ bas)
> {
>   unsigned long tmp = *bar;
>   *bas = 0;
>   *bar = tmp;
> }

The optimization in the first example happens in the postreload cse 
pass, and is relying on RTL alias analysis info.

The optimization does not happen for this example because we apparently 
have no way to represent an alias set for a restricted char pointer. 
char * and void * are allowed to alias anything.  That is alias set 0 
internally.  A restricted char pointer can alias anything except another 
restricted pointer, which would require making a subset of alias set 0, 
but that is invalid.  So we give up and just ignore the use of restrict 
here.

See in alias.c, where it does
             if (pointed_to_alias_set == 0)
               /* It's not legal to make a subset of alias set zero.  */
               DECL_POINTER_ALIAS_SET (decl) = 0;

We also don't handle restricted pointers to aggregate types.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: restrict and char pointers

[Jeroen Dobbelaere]

On 5/4/05, James E Wilson <wilson@specifixinc.com> wrote:
[..]
> The optimization does not happen for this example because we apparently
> have no way to represent an alias set for a restricted char pointer.
> char * and void * are allowed to alias anything.  That is alias set 0
> internally.  A restricted char pointer can alias anything except another
> restricted pointer, which would require making a subset of alias set 0,
> but that is invalid.  So we give up and just ignore the use of restrict
> here.
> 
[..]

Is this correct ? I don't have a version of the C99 standard, but
looking at explanations of the 'restrict' keyword, I see in
<http://docs.sun.com/source/819-0494/c99.app.html> and in
<http://www.devx.com/tips/Tip/13825>,
it seems that the definition of a restricted pointer is, that it does
not alias with anything else (for the time it is being used), and that
all accesses to the object it points to, should go through this
restricted pointer only.

This would mean that a restricted char pointer should not alias
something else. (no other restricted pointers, but also no
non-restricted pointers).

Does this 'definition' conflict with the standards definition ??

Greetings,
-- 
Jeroen Dobbelaere

Re: restrict and char pointers

[James E Wilson]

On Wed, 2005-05-04 at 14:27, Jeroen Dobbelaere wrote:
> Is this correct ?

I was only trying to explain how gcc works for the one example that you
posted.  I was not trying to explain precise semantics of how restrict
works according to the ISO C standard, and my message should not be
construed as such.  I didn't think you were asking that question.  I
probably can't answer that question very well.

The standard says "A translator is free to ignore any or all aliasing
implications of restrict".  So there is no conflict with the standard
here.  We are free to do as little optimization as we want, and in the
case of a restricted char pointer, we do none.

Just above the section of code I pointed at earlier is this comment
which explains how we handle restrict in the gcc RTL aliasing code:
          /* No two restricted pointers can point at the same thing.
             However, a restricted pointer can point at the same thing
             as an unrestricted pointer, if that unrestricted pointer
             is based on the restricted pointer.  So, we make the
             alias set for the restricted pointer a subset of the
             alias set for the type pointed to by the type of the
             decl.  */
Perhaps more advanced alias analysis code can do better, but this is
what we do for now in the RTL aliasing code, and it is known to be safe.

There is also tree aliasing code, which is more advanced than the RTL
aliasing code, but I don't think it has any support for restrict yet. 
So effectively we are ignoring restrict there, which is allowed by the
standard.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: restrict and char pointers

[Jeroen Dobbelaere]

On 5/4/05, James E Wilson wrote:
[..]
> The standard says "A translator is free to ignore any or all aliasing
> implications of restrict".  So there is no conflict with the standard
> here.  We are free to do as little optimization as we want, and in the
> case of a restricted char pointer, we do none.

I'm aware of that. The reason are asked for more clarity is that I
think gcc should
do better (as in the example I gave), but I want to be sure that this
is still allowed
by the standard.

[..]
>           /* No two restricted pointers can point at the same thing.
>              However, a restricted pointer can point at the same thing
>              as an unrestricted pointer, if that unrestricted pointer
>              is based on the restricted pointer.  So, we make the
>              alias set for the restricted pointer a subset of the
>              alias set for the type pointed to by the type of the
>              decl.  */
[..]

From what I found on these pages I refered to, this could be made more strict :
accesses through restricted pointers would not interfere with other accesses,
which would allow some more aggressive optimizations.

Greetings,
-- 
Jeroen Dobbelaere

Re: restrict and char pointers

[James E Wilson]

On Wed, 2005-05-04 at 16:24, Jeroen Dobbelaere wrote:
> I'm aware of that. The reason are asked for more clarity is that I
> think gcc should
> do better (as in the example I gave), but I want to be sure that this
> is still allowed
> by the standard.

Certainly gcc can and should do better, and this is allowed by the
standard, but implementing better support here is definitely
non-trivial.

> >From what I found on these pages I refered to, this could be made more strict :
> accesses through restricted pointers would not interfere with other accesses,
> which would allow some more aggressive optimizations.

I took a look at the standard, and gcc seems to be in line with it.  The
problem is that you can have something like
  int sub (int * __restrict__ a) { int *b = a; ... }
and now a and b alias each other, even though one pointer was declared
restrict.  If you can track these relationships, then this isn't a
problem.  If you can't track these relationships, then you have to use
the semantics that gcc currently uses, which is only that different
restricted pointers don't alias each other.  We can perhaps handle this
well in the tree-aliasing code (if it handled restrict at all), but it
would be difficult to handle this well in the RTL aliasing code.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: restrict and char pointers

[Diego Novillo]

On Wed, May 04, 2005 at 05:08:23PM -0700, James E Wilson wrote:

> We can perhaps handle this well in the tree-aliasing code (if
> it handled restrict at all), but it would be difficult to
> handle this well in the RTL aliasing code.
>
It doesn't.  Mostly for similar reasons.

Perhaps we could be more aggressive with the new aliasing changes
coming down the line, but it's certainly non-trivial to take
advantage of restrict.  A shame, really.


Diego.

Re: restrict and char pointers

[Daniel Berlin]

On Wed, 2005-05-04 at 20:41 -0400, Diego Novillo wrote:
> On Wed, May 04, 2005 at 05:08:23PM -0700, James E Wilson wrote:
> 
> > We can perhaps handle this well in the tree-aliasing code (if
> > it handled restrict at all), but it would be difficult to
> > handle this well in the RTL aliasing code.
> >
> It doesn't.  Mostly for similar reasons.
> 
> Perhaps we could be more aggressive with the new aliasing changes
> coming down the line, but it's certainly no
> trivial to take
> advantage of restrict.  A shame, really.

You can do it, but apparently restrict isn't as simple as "a and b are
both restrict pointers and therefore can never alias", because that's
not the actual definition of restrict.
It says stuff about pointers "based on" restricted objects, etc.

Joseph Myers has shown some very weird but legal things you can do with
restrict that make it all but pointless to try to handle, at least for
the non function argument case.


> 
> 
> Diego.

Re: restrict and char pointers

[Michael Matz]

Hi,

On Thu, 5 May 2005, Daniel Berlin wrote:

> You can do it, but apparently restrict isn't as simple as "a and b are
> both restrict pointers and therefore can never alias", because that's
> not the actual definition of restrict. It says stuff about pointers
> "based on" restricted objects, etc.
> 
> Joseph Myers has shown some very weird but legal things you can do with
> restrict that make it all but pointless to try to handle, at least for
> the non function argument case.

Disagreement here.  Some of Josephs weird examples were things like:
  void f(int* restrict a, int * restrict b) {
    for (i=0; i < N; i+=2) a[i] = 2*b[i];
  }
  int array[N];
  f (&array[0], &array[1]);

I.e. interleaving the pointers in a way that they both point into the 
same object.  This is not forbidden by restrict, but it also poses no 
problem.  The two restrict pointers still may not actually point to the 
same memory objects (individual array elements here), so the compiler can 
still trivially apply the "two restrict pointers don't alias" rule.

Then there is the problem of "based on".  This allows a non-restrict
pointer to sometimes alias a restrict pointer.  One could ignore this
rule at first, for ease of implementation, and say that a unrestricted
pointer can alias everything again.  restricted pointers themself can only
be based on other restricted pointers under very narrow circumstances,
which effectively prevents them again to be aliased at their points of
dereference.

User actually using restrict in their programs will most probably use
restrict for each pointer possible, so just handling that two restrict
pointers can't alias alone would probably catch 90% of all cases. (I've
actually had one user who was very confused that the vectorizer didn't do
anything on his very simple two-line function, although he made all three
pointer arguments be restricted).

As you said the most important would probably be to handle restrict 
pointers in function arguments.  I would add to that also those pointers 
which are not used in any RHS of any statement (except for being 
dereferenced of course).  This would ensure that no other pointer is based 
on them.  And it would allow users to write code like:
  void f(int* a, int *b, int n) {
    if (a > b+n || b > a+n) {  // arrays don't overlap
      int * restrict ar = a;
      int * restrict br = b;
      /* Make this nonaliasing known to the compiler */
      for (int i = 0; i < n; i++) ar[i] += br[i];
    } else {
      /* They overlap, can't optimize as much */
      for (int i = 0; i < n; i++) a[i] += b[i];
    }
  }


Ciao,
Michael.