[Bug c/48885] New: missed optimization with restrict qualifier?

[Bug c/48885] New: missed optimization with restrict qualifier?

[jerome.frgacic at yahoo dot fr]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

           Summary: missed optimization with restrict qualifier?
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: trivial
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: jerome.frgacic@yahoo.fr


Hello,

I recently experiment the optimizations obtained by using the restrict
qualifier introduced by the C99 standard. In this purpose, I used this trivial
exemple:

#include <stdio.h>
#include <stdlib.h>


void
test (int *a, int *b, int * restrict v)
{
    *a = *v;
    *b = *v;
}


int
main (void)
{
    int a;
    int b;
    int v = 10;

    test (&a, &b, &v);
    return EXIT_SUCCESS;
}

If i compiled it with the -S and -O2 options, I obtained for the "test"
function:

movl    (%rdx), %eax
movl    %eax, (%rdi)
movl    (%rdx), %eax
movl    %eax, (%rsi)

However, if I had correctly understand the meaning of a restrict pointer, we
can normally expect in the "test" function that the object pointed to by "v"
cannot be changed through "a" or "b"; and therefore perform only one load, like
this:

movl    (%rdx), %eax
movl    %eax, (%rdi)
movl    %eax, (%rsi)

But, the optimization only operate if all the pointers are restrict qualified.
Why?


PS: I compile with GCC 4.6 (Debian amd64 unstable package).

[Bug c/48885] missed optimization with restrict qualifier?

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-05 14:50:48 UTC ---
Because the standard was interpreted that way when implementing restrict
support.
And also because otherwise pointers based on a restrict pointer cannot be
reliably tracked.

[Bug c/48885] missed optimization with restrict qualifier?

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

Marc Glisse <marc.glisse at normalesup dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marc.glisse at normalesup
                   |                            |dot org

--- Comment #2 from Marc Glisse <marc.glisse at normalesup dot org> 2011-05-05 21:20:29 UTC ---
Note for comparison that suncc and icc both perform the optimization as soon as
'a' or 'v' is restrict.

[Bug c/48885] missed optimization with restrict qualifier?

[paulo@matos-sorge.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

Paulo J. Matos <paulo@matos-sorge.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paulo@matos-sorge.com

--- Comment #3 from Paulo J. Matos <paulo@matos-sorge.com> ---
My understanding is that for restrict optimization to take effect, variable a
has also to be restrict. Otherwise in the first assignment *a = *v;, a could
point to the same memory as v and therefore overwrite it, rendering the value
of *v in *b = *v; invalid. I think gcc is now doing the right thing.

[Bug c/48885] missed optimization with restrict qualifier?

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Paulo J. Matos from comment #3)
> My understanding is that for restrict optimization to take effect, variable
> a has also to be restrict. Otherwise in the first assignment *a = *v;, a
> could point to the same memory as v

No, the standard is quite clear that restrict is only needed on one variable to
ensure it doesn't alias the other.

"During each execution of B, let L be any lvalue that has &L based on P. If L
is used to access the value of the object X that it designates, and X is also
modified (by any means), then the following requirements apply: T shall not be
const-qualified. Every other lvalue used to access the value of X shall also
have its address based on P"

v points to X
P is v
L is *v
a is not based on v (if I write v=0, that doesn't change the value of the
pointer a), so the lvalue *a cannot be used to access X.

There is even an example where restrict is not specified on all variables:

"EXAMPLE 1 The file scope declarations
int * restrict a;
int * restrict b;
extern int c[];
assert that if an object is accessed using one of a, b, or c, and that object
is modified anywhere in the program, then it is never accessed using either of
the other two."



A separate remark, for the case with no "restrict" at all:
- if *a and *v are disjoint, we don't need the second load;
- if a == v, we don't need the second load either;
- the only case where we could need a reload is if *a and *v partially overlap,
I don't know if that's ever legal.

[Bug c/48885] missed optimization with restrict qualifier?

[paulo@matos-sorge.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #5 from Paulo J. Matos <paulo@matos-sorge.com> ---
(In reply to Marc Glisse from comment #4)
> (In reply to Paulo J. Matos from comment #3)
> > My understanding is that for restrict optimization to take effect, variable
> > a has also to be restrict. Otherwise in the first assignment *a = *v;, a
> > could point to the same memory as v
> 
> No, the standard is quite clear that restrict is only needed on one variable
> to ensure it doesn't alias the other.
> 
> "During each execution of B, let L be any lvalue that has &L based on P. If
> L is used to access the value of the object X that it designates, and X is
> also modified (by any means), then the following requirements apply: T shall
> not be const-qualified. Every other lvalue used to access the value of X
> shall also have its address based on P"
> 
> v points to X
> P is v
> L is *v
> a is not based on v (if I write v=0, that doesn't change the value of the
> pointer a), so the lvalue *a cannot be used to access X.
> 
> There is even an example where restrict is not specified on all variables:
> 
> "EXAMPLE 1 The file scope declarations
> int * restrict a;
> int * restrict b;
> extern int c[];
> assert that if an object is accessed using one of a, b, or c, and that
> object is modified anywhere in the program, then it is never accessed using
> either of the other two."
> 
> 
> 
> A separate remark, for the case with no "restrict" at all:
> - if *a and *v are disjoint, we don't need the second load;
> - if a == v, we don't need the second load either;
> - the only case where we could need a reload is if *a and *v partially
> overlap, I don't know if that's ever legal.

I would love to say I am convinced but I am not [yet]. In the example c is
extern so it's not really defining an object. All other examples in the
standard have restrict being applied to all the pointers.

But I am not terribly convinced I am right either. Extern seems to have special
meaning given the sentence from the standard:
"2 If D appears inside a block and does not have storage class extern, let B
 denote the block. If D appears in the list of parameter declarations of a 
function definition, let B denote the associated block. Otherwise, let B denote 
the block of main (or the block of whatever function is called at program 
startup in a freestanding environment)."

My initial comments were based on this explanation:
http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

First I do understand this is not the standard but it sounded much clear:
"In this case, I promise that the pointer declared along with the restrict
qualifier is not aliased. I certify that writes through this pointer will not
effect the values read through any other pointer available in the same context
which is also declared as restricted."

[Bug c/48885] missed optimization with restrict qualifier?

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #6 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Paulo J. Matos from comment #5)
> I would love to say I am convinced but I am not [yet].

Note that interpreting the standard and deciding what to implement in gcc are
very different and almost independent problems. The "one restrict is enough"
version seems harder to implement: you need to prove that a pointer is not
based on another one, whereas with "all pointers restrict" you can just check
that they come from different declarations.

> Extern seems to have
> special meaning given the sentence from the standard:
> "2 If D appears inside a block and does not have storage class extern, let B
>  denote the block. If D appears in the list of parameter declarations of a 
> function definition, let B denote the associated block. Otherwise, let B
> denote 
> the block of main (or the block of whatever function is called at program 
> startup in a freestanding environment)."

That's just trying to define the scope where the non-aliasing rule applies, but
the rule itself remains the same.

> My initial comments were based on this explanation:
> http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-
> restrict-keyword.html
> 
> First I do understand this is not the standard but it sounded much clear:
> "In this case, I promise that the pointer declared along with the restrict
> qualifier is not aliased. I certify that writes through this pointer will
> not effect the values read through any other pointer available in the same
> context which is also declared as restricted."

The "which is also declared as restricted" part is an invention. See my quote
from the C99/C11 standard: "Every other lvalue", not just those based on a
restrict pointer.

See also the early statement of intent: "An object that is accessed through a
restrict-qualified pointer has a special association with that pointer. This
association, defined in 6.7.3.1 below, requires that all accesses to that
object use, directly or indirectly, the value of that particular pointer." and
associated footnote: "For example, a statement that assigns a value returned by
malloc to a single pointer establishes this association between the allocated
object and the pointer."

When you call malloc, you know this memory aliases nothing, so you can mark it
so, you don't have to (and it would obviously be wrong) mark all the other
pointers as restrict to say so.

[Bug c/48885] missed optimization with restrict qualifier?

[paulo@matos-sorge.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #7 from Paulo J. Matos <paulo@matos-sorge.com> ---
(In reply to Marc Glisse from comment #6)
> 
> Note that interpreting the standard and deciding what to implement in gcc
> are very different and almost independent problems. The "one restrict is
> enough" version seems harder to implement: you need to prove that a pointer
> is not based on another one, whereas with "all pointers restrict" you can
> just check that they come from different declarations.
> 

I am not sure what the GCC community wants but I would expect that if the task
is not impossible, then implementing the standard should be the way to go. I do
understand that we are all 'volunteers' though and someone would need to take
the time to do it.

> That's just trying to define the scope where the non-aliasing rule applies,
> but the rule itself remains the same.
> 
> > My initial comments were based on this explanation:
> > http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-
> > restrict-keyword.html
> > 
> > First I do understand this is not the standard but it sounded much clear:
> > "In this case, I promise that the pointer declared along with the restrict
> > qualifier is not aliased. I certify that writes through this pointer will
> > not effect the values read through any other pointer available in the same
> > context which is also declared as restricted."
> 
> The "which is also declared as restricted" part is an invention. See my
> quote from the C99/C11 standard: "Every other lvalue", not just those based
> on a restrict pointer.
> 
> See also the early statement of intent: "An object that is accessed through
> a restrict-qualified pointer has a special association with that pointer.
> This association, defined in 6.7.3.1 below, requires that all accesses to
> that object use, directly or indirectly, the value of that particular
> pointer." and associated footnote: "For example, a statement that assigns a
> value returned by
> malloc to a single pointer establishes this association between the
> allocated object and the pointer."
> 
> When you call malloc, you know this memory aliases nothing, so you can mark
> it so, you don't have to (and it would obviously be wrong) mark all the
> other pointers as restrict to say so.

Re-reading the standard after your comments makes more sense. Your malloc
example got me convinced though.

There are still a few questions. One is why the standard only uses examples
where all the pointers are restricted (with the exception example of the one
you post where the 'c' was extern). The other is why was GCC working according
to standard (or apparently so in 4.5) and changed in 4.6. Was it on purpose or
was it on by accident? If on purpose then this decision to deviate from the
standard should be documented and this bug can be marked as INVALID.

[Bug c/48885] missed optimization with restrict qualifier?

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #8 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Paulo J. Matos from comment #7)
> There are still a few questions. One is why the standard only uses examples
> where all the pointers are restricted (with the exception example of the one
> you post where the 'c' was extern).

Feel free to contact WG14 to try and get them to add another example, I'd
certainly welcome even a sentence clarifying that one "restrict" is sufficient
in one of the examples.

> The other is why was GCC working
> according to standard (or apparently so in 4.5) and changed in 4.6. Was it
> on purpose or was it on by accident?

I wasn't there, you'd have to check the logs and read the ML archives from that
time.

> If on purpose then this decision to
> deviate from the standard should be documented and this bug can be marked as
> INVALID.

WONTFIX at most, not INVALID.

[Bug c/48885] missed optimization with restrict qualifier?

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #9 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #2)
> Note for comparison that suncc and icc both perform the optimization as soon
> as 'a' or 'v' is restrict.

And clang as well, for the record.

[Bug c/48885] missed optimization with restrict qualifier?

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

vries at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org,
                   |                            |vries at gcc dot gnu.org

--- Comment #10 from vries at gcc dot gnu.org ---
The current implementation of restrict is based on clique/base pairs.

For the example
...
void
test (int *a, int *b, int * restrict v)
{
  *a = *v;
  *b = *v;
}
...
we get *v annotated with clique/base 1/1.

I wonder if we can reserve a base in each clique as non-restrict base, and
annotate like this:
- *a : 1/non-restrict
- *b : 1/non-restrict
- *v : 1/1

This way:
- *a and *b would still potentially alias
- *a and *v would be disambiguated, and
- not annotated memory references would not be impacted


This would only work with top-level restrict though. We would have to take care
in an example like this:
...
void
f (int *__restrict__ &__restrict__ p, int *p2)
{
  *p = 1;
  *p2 = 2;
}

void
g (int *__restrict__ gp)
{
  f (gp, gp);
}
...

Currently we annotate this as:
...
void f(int* __restrict__&, int*) (intD.9 * restrict & restrict pD.2252, intD.9
* p2D.2253)
{
  intD.9 * _3;

  # VUSE <.MEM_1(D)>
  # PT = { D.2265 } (nonlocal)
  _3 = MEM[(intD.9 * restrict &)p_2(D) clique 1 base 1];

  # .MEM_4 = VDEF <.MEM_1(D)>
  MEM[(intD.9 *)_3 clique 1 base 2] = 1;

  # .MEM_6 = VDEF <.MEM_4>
  *p2_5(D) = 2;
...

In this case, p2 cannot alias with clique 1/base 1, since it's a toplevel
restrict. But p2 can alias with clique 1/base 2, because it's not a toplevel
restrict.

So, if we f.i. register MR_DEPENDENCE_TOPLEVEL (in addition to
MR_DEPENDENCE_CLIQUE and MR_DEPENDENCE_BASE), we can disambiguate:
- normal bases within the same clique if they're different, and
- a non-restrict base vs a toplevel base.

[Bug c/48885] missed optimization with restrict qualifier?

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-09-23
     Ever confirmed|0                           |1

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
It's just a matter of implementing the missing ???

/* Mark "other" loads and stores as belonging to CLIQUE and with
   base zero.  */

static bool
visit_loadstore (gimple *, tree base, tree ref, void *clique_)
{
  unsigned short clique = (uintptr_t)clique_;
  if (TREE_CODE (base) == MEM_REF
      || TREE_CODE (base) == TARGET_MEM_REF)
    {
      tree ptr = TREE_OPERAND (base, 0);
      if (TREE_CODE (ptr) == SSA_NAME)
        {
          /* ???  We need to make sure 'ptr' doesn't include any of
             the restrict tags in its points-to set.  */
          return false;

(well, we could handle default-defs without adding that).  Thus for the
particular testcase:

@@ -6952,7 +7047,8 @@ visit_loadstore (gimple *, tree base, tr
       || TREE_CODE (base) == TARGET_MEM_REF)
     {
       tree ptr = TREE_OPERAND (base, 0);
-      if (TREE_CODE (ptr) == SSA_NAME)
+      if (TREE_CODE (ptr) == SSA_NAME
+         && ! SSA_NAME_IS_DEFAULT_DEF (ptr))
        {
          /* ???  We need to make sure 'ptr' doesn't include any of
             the restrict tags in its points-to set.  */

but we can of course do better.  Remember all 'restrict_var' we added
bases for and above lookup the points-to solution for 'ptr' and intersect
it with the restrict_var set.  If that's empty - fine - if not, we have
to continue failing.

I'm testing the above simple fix and amend the comment.

[Bug c/48885] missed optimization with restrict qualifier?

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #12 from vries at gcc dot gnu.org ---
(In reply to Richard Biener from comment #11)
> I'm testing the above simple fix and amend the comment.

Consider the example with functions f and g I gave in comment 10. Using the
patch from comment 11, I get at ealias:
...
void f(int* __restrict__&, int*) (intD.9 * restrict & restrict pD.2252, intD.9
* p2D.2253)
{
  intD.9 * _3;

  # VUSE <.MEM_1(D)>
  # PT = { D.2265 } (nonlocal)
  _3 = MEM[(intD.9 * restrict &)p_2(D) clique 1 base 1];

  # .MEM_4 = VDEF <.MEM_1(D)>
  MEM[(intD.9 *)_3 clique 1 base 2] = 1;

  # .MEM_6 = VDEF <.MEM_4>
  MEM[(intD.9 *)p2_5(D) clique 1 base 0] = 2;
...

AFAIU, this is incorrect. The two stores can be now disambiguated based on same
clique/different base, but in fact the stores can alias (in fact they do, in
the  "f (gp, gp)" call from g).

[Bug c/48885] missed optimization with restrict qualifier?

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #13 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 23 Sep 2015, vries at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885
> 
> --- Comment #12 from vries at gcc dot gnu.org ---
> (In reply to Richard Biener from comment #11)
> > I'm testing the above simple fix and amend the comment.
> 
> Consider the example with functions f and g I gave in comment 10. Using the
> patch from comment 11, I get at ealias:
> ...
> void f(int* __restrict__&, int*) (intD.9 * restrict & restrict pD.2252, intD.9
> * p2D.2253)
> {
>   intD.9 * _3;
> 
>   # VUSE <.MEM_1(D)>
>   # PT = { D.2265 } (nonlocal)
>   _3 = MEM[(intD.9 * restrict &)p_2(D) clique 1 base 1];
> 
>   # .MEM_4 = VDEF <.MEM_1(D)>
>   MEM[(intD.9 *)_3 clique 1 base 2] = 1;
> 
>   # .MEM_6 = VDEF <.MEM_4>
>   MEM[(intD.9 *)p2_5(D) clique 1 base 0] = 2;
> ...
> 
> AFAIU, this is incorrect. The two stores can be now disambiguated based on same
> clique/different base, but in fact the stores can alias (in fact they do, in
> the  "f (gp, gp)" call from g).

How is this a valid testcase?  You are accessing g()s *gp through
p and p2 even though p is marked as restrict.  Did you mean to write

void
f (int *&__restrict__ p, int *p2)

?

[Bug c/48885] missed optimization with restrict qualifier?

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #14 from vries at gcc dot gnu.org ---
(In reply to rguenther@suse.de from comment #13)
> On Wed, 23 Sep 2015, vries at gcc dot gnu.org wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885
> > 
> > --- Comment #12 from vries at gcc dot gnu.org ---
> > (In reply to Richard Biener from comment #11)
> > > I'm testing the above simple fix and amend the comment.
> > 
> > Consider the example with functions f and g I gave in comment 10. Using the
> > patch from comment 11, I get at ealias:
> > ...
> > void f(int* __restrict__&, int*) (intD.9 * restrict & restrict pD.2252, intD.9
> > * p2D.2253)
> > {
> >   intD.9 * _3;
> > 
> >   # VUSE <.MEM_1(D)>
> >   # PT = { D.2265 } (nonlocal)
> >   _3 = MEM[(intD.9 * restrict &)p_2(D) clique 1 base 1];
> > 
> >   # .MEM_4 = VDEF <.MEM_1(D)>
> >   MEM[(intD.9 *)_3 clique 1 base 2] = 1;
> > 
> >   # .MEM_6 = VDEF <.MEM_4>
> >   MEM[(intD.9 *)p2_5(D) clique 1 base 0] = 2;
> > ...
> > 
> > AFAIU, this is incorrect. The two stores can be now disambiguated based on same
> > clique/different base, but in fact the stores can alias (in fact they do, in
> > the  "f (gp, gp)" call from g).
> 
> How is this a valid testcase?
> You are accessing g()s *gp through
> p and p2 even though p is marked as restrict.

To be exact, p is a restrict reference to a restrict pointer.
And AFAIU it's a valid test-case.

>  Did you mean to write
> 
> void
> f (int *&__restrict__ p, int *p2)
> 
> ?

No. I'll try explain, renaming variables to help clarification, and adding a
call to g for completeness:
...
void
f (int *__restrict__ &__restrict__ fp, int *fp2)
{
  *fp = 1;
  *fp2 = 2;
}

void
g (int *__restrict__ gp)
{
  f (gp, gp);
}

void
h (void)
{
  int ha;
  g (&ha);
}
...

Let's look at the three restricts in the example.

First, there's the second restrict in "int *__restrict &__restrict fp", which
is a reference to object gp. Since object gp is not modified during f, the
restrict has no consequence.

Then there's the restrict in "int *__restrict__ gp". The object pointed to is
ha, and it's modified during g. So all accesses to ha during g need to be based
on gp. And that is the case. The '*fp2 = 1' is based on gp. And the '*fp2 = 2'
is based on gp.

Finally, there's the first restrict in "int *__restrict &__restrict fp". That's
a copy of the type of gp.

[Bug c/48885] missed optimization with restrict qualifier?

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to vries from comment #14)
> (In reply to rguenther@suse.de from comment #13)
> > On Wed, 23 Sep 2015, vries at gcc dot gnu.org wrote:
> > 
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885
> > > 
> > > --- Comment #12 from vries at gcc dot gnu.org ---
> > > (In reply to Richard Biener from comment #11)
> > > > I'm testing the above simple fix and amend the comment.
> > > 
> > > Consider the example with functions f and g I gave in comment 10. Using the
> > > patch from comment 11, I get at ealias:
> > > ...
> > > void f(int* __restrict__&, int*) (intD.9 * restrict & restrict pD.2252, intD.9
> > > * p2D.2253)
> > > {
> > >   intD.9 * _3;
> > > 
> > >   # VUSE <.MEM_1(D)>
> > >   # PT = { D.2265 } (nonlocal)
> > >   _3 = MEM[(intD.9 * restrict &)p_2(D) clique 1 base 1];
> > > 
> > >   # .MEM_4 = VDEF <.MEM_1(D)>
> > >   MEM[(intD.9 *)_3 clique 1 base 2] = 1;
> > > 
> > >   # .MEM_6 = VDEF <.MEM_4>
> > >   MEM[(intD.9 *)p2_5(D) clique 1 base 0] = 2;
> > > ...
> > > 
> > > AFAIU, this is incorrect. The two stores can be now disambiguated based on same
> > > clique/different base, but in fact the stores can alias (in fact they do, in
> > > the  "f (gp, gp)" call from g).
> > 
> > How is this a valid testcase?
> > You are accessing g()s *gp through
> > p and p2 even though p is marked as restrict.
> 
> To be exact, p is a restrict reference to a restrict pointer.
> And AFAIU it's a valid test-case.
> 
> >  Did you mean to write
> > 
> > void
> > f (int *&__restrict__ p, int *p2)
> > 
> > ?
> 
> No. I'll try explain, renaming variables to help clarification, and adding a
> call to g for completeness:
> ...
> void
> f (int *__restrict__ &__restrict__ fp, int *fp2)
> {
>   *fp = 1;
>   *fp2 = 2;
> }
> 
> void
> g (int *__restrict__ gp)
> {
>   f (gp, gp);
> }
> 
> void
> h (void)
> {
>   int ha;
>   g (&ha);
> }
> ...
> 
> Let's look at the three restricts in the example.
> 
> First, there's the second restrict in "int *__restrict &__restrict fp",
> which is a reference to object gp. Since object gp is not modified during f,
> the restrict has no consequence.
> 
> Then there's the restrict in "int *__restrict__ gp". The object pointed to
> is ha, and it's modified during g. So all accesses to ha during g need to be
> based on gp. And that is the case. The '*fp2 = 1' is based on gp. And the
> '*fp2 = 2' is based on gp.

No, *fp2 is _not_ based on gp.  Otherwise even simple cases like

int foo (int * __restrict p, int * __restrict q)
{
  *p = 1;
  *q = 0;
  return *p;
}

could not be optimized because calling foo like

int bar ()
{
  int i;
  int *r = &i;
  foo (r, r);
  return i;
}

would make that invalid.  With your reading both p and q are based on r
(in the context of bar).

The standard has some interesting wording to define "based-on".  IIRC
it goes like a pointer is based on 'p' if the value of the pointer
changes when you modify 'p'.  I think that only allows for expressions
based on p, like (p + 1) or &p[2].  It does _not_ allow for new
temporaries, like q = p + 1; as if you modify p q doesn't change.

IMHO the restrict qualifications on a function signature are to be
seen as constraints on the set of valid parameters it can be called
with and f (gp, gp) is not amongst that set.

> Finally, there's the first restrict in "int *__restrict &__restrict fp".
> That's a copy of the type of gp.

[Bug c/48885] missed optimization with restrict qualifier?

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Sep 24 07:34:47 2015
New Revision: 228073

URL: https://gcc.gnu.org/viewcvs?rev=228073&root=gcc&view=rev
Log:
2015-09-24  Richard Biener  <rguenther@suse.de>

        PR tree-optimization/48885
        * tree-ssa-structalias.c (visit_loadstore): Handle default defs
        as not including any restrict tags from other pointers.

        * gcc.dg/tree-ssa/restrict-6.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/restrict-6.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-structalias.c

[Bug c/48885] missed optimization with restrict qualifier?

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to work|                            |6.0
         Resolution|---                         |FIXED

--- Comment #17 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for GCC 6.

[Bug c/48885] missed optimization with restrict qualifier?

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

vries at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jsm28 at gcc dot gnu.org

--- Comment #18 from vries at gcc dot gnu.org ---
Let's rewrite the example from comment 14 to plain C (as we did in PR67705):

void
f (int *__restrict__ *__restrict__ fpp, int *fp2)
{
  int *fp = *fpp;
  *fp = 1;
  *fp2 = 2;
}

void
g (int *__restrict__ gp)
{
  f (&gp, gp);
}

void
h (void)
{
  int ha;
  g (&ha);
}

My interpretation of the restricts in the example (given what I've learned in
PR67705):

Restrict declaration D: "int *__restrict__ gp"
Type T: int
Object P: gp
Block B: g function block
Lvalues: *fp and *fp2
Objects designated by lvalues: ha in both cases.
Object ha modified during execution of B: yes
Object gp considered modified during execution of B: yes
&Lvalues: pointer expressions fp and fp2
&Lvalues based on object P: yes
Conclusion: Valid example.  Since both lvalues have their address based on
            the same restrict pointer, there are no disambiguation
            consequences.

Restrict declaration D: "int *__restrict__ *__restrict__ fpp"
Type T: int *__restrict__
Object P: fpp
Block B: f function block
Lvalues: *fpp
Objects designated by lvalues: gp
Object gp modified during execution of B: considered modified, yes
Object fpp considered modified during execution of B: yes
&Lvalues: pointer expression fpp
&Lvalues based on object P: yes
Conclusion: Valid example. Since there's only one lvalue accessing gp there
            are no disambiguation consequences.

Joseph, can you confirm that:
- this is a valid example, and
- there are no disambiguation consequences.

If that is indeed the case, then the committed patch is invalid.

[Bug c/48885] missed optimization with restrict qualifier?

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #19 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 25 Sep 2015, vries at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885
> 
> vries at gcc dot gnu.org changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |jsm28 at gcc dot gnu.org
> 
> --- Comment #18 from vries at gcc dot gnu.org ---
> Let's rewrite the example from comment 14 to plain C (as we did in PR67705):
> 
> void
> f (int *__restrict__ *__restrict__ fpp, int *fp2)
> {
>   int *fp = *fpp;
>   *fp = 1;
>   *fp2 = 2;
> }
> 
> void
> g (int *__restrict__ gp)
> {
>   f (&gp, gp);
> }
> 
> void
> h (void)
> {
>   int ha;
>   g (&ha);
> }
> 
> My interpretation of the restricts in the example (given what I've learned in
> PR67705):
> 
> Restrict declaration D: "int *__restrict__ gp"
> Type T: int
> Object P: gp
> Block B: g function block
> Lvalues: *fp and *fp2
> Objects designated by lvalues: ha in both cases.
> Object ha modified during execution of B: yes
> Object gp considered modified during execution of B: yes
> &Lvalues: pointer expressions fp and fp2
> &Lvalues based on object P: yes
> Conclusion: Valid example.  Since both lvalues have their address based on
>             the same restrict pointer, there are no disambiguation
>             consequences.
> 
> Restrict declaration D: "int *__restrict__ *__restrict__ fpp"
> Type T: int *__restrict__
> Object P: fpp
> Block B: f function block
> Lvalues: *fpp
> Objects designated by lvalues: gp
> Object gp modified during execution of B: considered modified, yes
> Object fpp considered modified during execution of B: yes
> &Lvalues: pointer expression fpp
> &Lvalues based on object P: yes
> Conclusion: Valid example. Since there's only one lvalue accessing gp there
>             are no disambiguation consequences.
> 
> Joseph, can you confirm that:
> - this is a valid example, and
> - there are no disambiguation consequences.
> 
> If that is indeed the case, then the committed patch is invalid.

I don't see how one needs to consider fp2 based on fp (*fpp).  If
we need to consider that then what's the difference to

int foo (int * __restrict__ p, int *q)
{
  *p = 1;
  *q = 2;
  return *p;
}

int main ()
{
  int i;
  if (foo (&i, &i) != 2)
    abort ();
}

here q is based on p if you take into account the caller.

But IIRC what matters here is that the BLOCK with the restrict
declaration of 'p' starts at the beginning of foo and does not
include the initialization at the call site.  Thus any
"based-on" properties that are formed before the execution of
BLOCK begins are irrelevant to the standards wording.

Thus it's like

int main()
{
  int i;
  int *pcaller = &i;
  int *qcaller = &i;
  int ret;
  {
    int * __restrict__ p = pcaller;
    int * q = qcaller;
    *p = 1;
    *q = 2;
    ret = *p;
  }
  if (ret != 2)
    abort ();
}

(where GCC doesn't handle restrict as it can only guarantee to
follow the scoping rule on a whole function basis).

[Bug c/48885] missed optimization with restrict qualifier?

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #20 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to vries from comment #18)

Aren't you supposed to also look at:
D: declaration of fpp
B: block of f
P: *fpp
accesses: *fp and *fp2
etc ?

[Bug c/48885] missed optimization with restrict qualifier?

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #21 from vries at gcc dot gnu.org ---
(In reply to Marc Glisse from comment #20)
> (In reply to vries from comment #18)
> 
> Aren't you supposed to also look at:
> D: declaration of fpp
> B: block of f
> P: *fpp
> accesses: *fp and *fp2
> etc ?

Hmm, I think this may indeed be the difference in interpretation.

Standard: "Let D be a declaration of an ordinary identifier that provides a
means of designating an object P as a restrict-qualified pointer to type T."

Say D is "int *__restrict__ *__restrict__ fpp"

Does this designate as a restrict-qualified pointer":
1. both objects fpp and *fpp, or
2. only object fpp
   (and the first restrict is just an obligate copy of the type qualifier of
the
   restrict pointer declaration fpp points to)
?

I'd say the standard is not clear on this point.

[Bug c/48885] missed optimization with restrict qualifier?

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #22 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Fri, 25 Sep 2015, vries at gcc dot gnu.org wrote:

> Standard: "Let D be a declaration of an ordinary identifier that provides a
> means of designating an object P as a restrict-qualified pointer to type T."
> 
> Say D is "int *__restrict__ *__restrict__ fpp"
> 
> Does this designate as a restrict-qualified pointer":
> 1. both objects fpp and *fpp, or

Both objects.  And also objects fpp[1], fpp[-1], etc., if they exist.

[Bug c/48885] missed optimization with restrict qualifier?

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=48885

--- Comment #23 from vries at gcc dot gnu.org ---
(In reply to joseph@codesourcery.com from comment #22)
> On Fri, 25 Sep 2015, vries at gcc dot gnu.org wrote:
> 
> > Standard: "Let D be a declaration of an ordinary identifier that provides a
> > means of designating an object P as a restrict-qualified pointer to type T."
> > 
> > Say D is "int *__restrict__ *__restrict__ fpp"
> > 
> > Does this designate as a restrict-qualified pointer":
> > 1. both objects fpp and *fpp, or
> 
> Both objects.  And also objects fpp[1], fpp[-1], etc., if they exist.

Ok, understood.

Then indeed this bit of the analysis was missing:

Restrict declaration D: "int *__restrict__ *__restrict__ fpp"
Type T: int
Object P: *fpp (in other words, gp)
Block B: f function block
Lvalues: *fp and *fp2
Object designated by lvalues: ha
Object ha modified during execution of B: yes
Object *fpp considered modified during execution of B: yes
&Lvalues: pointer expression fp and fp2
&Lvalues based on object P: fp yes, fp2 no. Modifying the value of *fpp during
                            B has no effect on the value of fp2.
Conclusion: Invalid example.