[Bug tree-optimization/62171] New: restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[Bug tree-optimization/62171] New: restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

            Bug ID: 62171
           Summary: restrict pointer to struct with restrict pointers parm
                    doesn't prevent aliases
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vries at gcc dot gnu.org

Created attachment 33351
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=33351&action=edit
test-case, derived from testcase for PR46032

The test-case (attached) contains a function parameter with type restrict
pointer to struct with restrict pointers:
...
struct omp_data_i
{
  double *__restrict__ results;
  double *__restrict__ pData;
  double *__restrict__ coeff;
};

static double __attribute__((noinline, noclone))
f (struct omp_data_i *__restrict__ p, int argc)
{

  int idx;

  for (idx = 0; idx < nEvents; idx++)
    ((p->results))[idx] = (*(p->coeff)) * ((p->pData))[idx];

  return ((p->results))[argc];
}
...

Despite using restrict, we don't manage to get rid of the aliases:
...
$ gcc test.c -O2 -ftree-vectorize -fdump-tree-vect-all
$ egrep 'note: vectorized|version' test.c.*.vect
test.c:15:3: note: versioning for alias required: can't determine dependence
between *pretmp_35 and *_8
test.c:15:3: note: versioning for alias required: can't determine dependence
between *_12 and *_8
cost model: Adding cost of checks for loop versioning aliasing.
test.c:15:3: note: created 2 versioning for alias checks.
test.c:15:3: note: loop versioned for vectorization because of possible
aliasing
test.c:11:1: note: vectorized 1 loops in function.
...

Rewriting the example such that it has seperate function parameters with type
restrict pointer fixes the problem. 

Rewriting the example such that it has seperate function parameters with type
restrict pointer to restrict pointer fixes the problem. 

Rewriting the example such that it has as parameter a single struct with
restrict pointers fixes the problem.

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Our restrict support doesn't handle this case.

Note that I don't think the C standard defines what happens with restrict
qualified data members.  What is the "pointer" that is used for all the
"based-on" wording?  What is the "scope" of it?

Special-casing this very special case in points-to is possible, we already
have code to do that but it is "restricted" (heh).

static void
intra_create_variable_infos (struct function *fn)
{
  tree t;

  /* For each incoming pointer argument arg, create the constraint ARG
     = NONLOCAL or a dummy variable if it is a restrict qualified
     passed-by-reference argument.  */
  for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
    {
      varinfo_t p = get_vi_for_tree (t);

      /* For restrict qualified pointers to objects passed by
         reference build a real representative for the pointed-to object.
         Treat restrict qualified references the same.  */
      if (TYPE_RESTRICT (TREE_TYPE (t))
          && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
              || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
          && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
        {
...

which was implemented to support Fortran array descriptors with
restrict qualified data pointer.

So if you say we can treat any T * restrict parameter in that way
(no other global(!) or function parameter pointer may be used to
access the memory the fields in the struct pointed to by the
parameter), then fine.  Note that we restrict this to REFERENCEs
as pointers may point to an array of objects which I think we
don't treat correctly here (we need to know the size of the
object - with a pointer you can even access sth before what we point to).

This means supporting this may be difficult.  It may already work
if you use C++ and

static double __attribute__((noinline, noclone))
f (struct omp_data_i &__restrict__ p, int argc)
{

?  That is, if the middle-end uses a REFERENCE_TYPE?

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
And maybe set DECL_BY_REFERENCE, a mere REFERENCE_TYPE doesn't prevent
you from doing (&param)[2] which we'd miscompile.  Not sure who added
that REFERENCE_TYPE code.

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

--- Comment #3 from vries at gcc dot gnu.org ---
(In reply to Richard Biener from comment #2)
> And maybe set DECL_BY_REFERENCE, a mere REFERENCE_TYPE doesn't prevent
> you from doing (&param)[2] which we'd miscompile.  Not sure who added
> that REFERENCE_TYPE code.

Submitted here: https://gcc.gnu.org/ml/gcc-patches/2011-09/msg01489.html
OK-ed here: https://gcc.gnu.org/ml/gcc-patches/2011-09/msg01489.html

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

--- Comment #4 from vries at gcc dot gnu.org ---
(In reply to vries from comment #3)
> (In reply to Richard Biener from comment #2)
> > And maybe set DECL_BY_REFERENCE, a mere REFERENCE_TYPE doesn't prevent
> > you from doing (&param)[2] which we'd miscompile.  Not sure who added
> > that REFERENCE_TYPE code.
>

[correcting copy/past-o]

Submitted here: https://gcc.gnu.org/ml/gcc-patches/2011-09/msg01426.html
OK-ed here: https://gcc.gnu.org/ml/gcc-patches/2011-09/msg01489.html

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

--- Comment #5 from vries at gcc dot gnu.org ---
(In reply to Richard Biener from comment #1)
> It may already work
> if you use C++ and
> 
> static double __attribute__((noinline, noclone))
> f (struct omp_data_i &__restrict__ p, int argc)
> {
> 
> ?  That is, if the middle-end uses a REFERENCE_TYPE?

Confirmed, rewriting the example with 'struct omp_data_i &' and compiling with
g++ solves the aliasing problem.

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

--- Comment #6 from vries at gcc dot gnu.org ---
(In reply to Richard Biener from comment #2)
> And maybe set DECL_BY_REFERENCE, a mere REFERENCE_TYPE doesn't prevent
> you from doing (&param)[2] which we'd miscompile.  Not sure who added
> that REFERENCE_TYPE code.

Richard,

can you give a complete example of what you think we'd miscompile?

Thanks,
- Tom

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
I was thinking about sth like

struct X { int i; int * __restrict__ q; };

int foo (X& __restrict__ x, X *p)
{
  *x.q = 1;
  p->i = 0;
  return *x.q;
}

int main()
{
  X x;
  x.q = &x.i;
  return foo (x, &x);
}

but I see we're still conservatively requiring decls in visit_loadstore:

      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;

Of course this kind of testcase would also break if X were passed by
value (and changed by the frontend to DECL_BY_REFERENCE).  That is,
using the 2nd level restrict sounds bogus iff there can be a testcase
that can be created by the user (thus is not under strict control by
the compiler).


That said, generally the tree-ssa-structalias.c:visit_loadstore needs
some more sophistication as well.

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

--- Comment #8 from vries at gcc dot gnu.org ---
(In reply to Richard Biener from comment #7)
> I was thinking about sth like
> 
> struct X { int i; int * __restrict__ q; };
> 
> int foo (X& __restrict__ x, X *p)
> {
>   *x.q = 1;
>   p->i = 0;
>   return *x.q;
> }
> 
> int main()
> {
>   X x;
>   x.q = &x.i;
>   return foo (x, &x);
> }
> 

I think this example's an invalid use of restrict.

By using restrict in the 'X& __restrict__ x' parameter of foo, we promise that
if the object x points to is modified during foo execution (and it is, by both
assignments) we only access the object using pointers based on x during foo
execution.

p is pointing to the same object, and we access the object via p. But p is not
based on x.

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[rguenther at suse dot de]

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

--- Comment #9 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 22 Sep 2015, vries at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62171
> 
> --- Comment #8 from vries at gcc dot gnu.org ---
> (In reply to Richard Biener from comment #7)
> > I was thinking about sth like
> > 
> > struct X { int i; int * __restrict__ q; };
> > 
> > int foo (X& __restrict__ x, X *p)
> > {
> >   *x.q = 1;
> >   p->i = 0;
> >   return *x.q;
> > }
> > 
> > int main()
> > {
> >   X x;
> >   x.q = &x.i;
> >   return foo (x, &x);
> > }
> > 
> 
> I think this example's an invalid use of restrict.
> 
> By using restrict in the 'X& __restrict__ x' parameter of foo, we promise that
> if the object x points to is modified during foo execution (and it is, by both
> assignments) we only access the object using pointers based on x during foo
> execution.
> 
> p is pointing to the same object, and we access the object via p. But p is not
> based on x.

Sorry, I modified it bogously, just move int i; out of the struct and
somewhere else.  My concerns boil down to X being passed twice,
once as reference and once as pointer.  The PTA machinery will
then use restrict for X.q for the reference case but not for
the pointer case.  I believe C doesn't specify what happens for
these "indirect" cases (nor for what happens for global restricts).

To behave "correctly" PTA would need to correlate q from both
parameters.

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

--- Comment #10 from vries at gcc dot gnu.org ---
(In reply to rguenther@suse.de from comment #9)
> On Tue, 22 Sep 2015, vries at gcc dot gnu.org wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62171
> > 
> > --- Comment #8 from vries at gcc dot gnu.org ---
> > (In reply to Richard Biener from comment #7)
> > > I was thinking about sth like
> > > 
> > > struct X { int i; int * __restrict__ q; };
> > > 
> > > int foo (X& __restrict__ x, X *p)
> > > {
> > >   *x.q = 1;
> > >   p->i = 0;
> > >   return *x.q;
> > > }
> > > 
> > > int main()
> > > {
> > >   X x;
> > >   x.q = &x.i;
> > >   return foo (x, &x);
> > > }
> > > 
> > 
> > I think this example's an invalid use of restrict.
> > 
> > By using restrict in the 'X& __restrict__ x' parameter of foo, we promise that
> > if the object x points to is modified during foo execution (and it is, by both
> > assignments) we only access the object using pointers based on x during foo
> > execution.
> > 
> > p is pointing to the same object, and we access the object via p. But p is not
> > based on x.
> 
> Sorry, I modified it bogously, just move int i; out of the struct and
> somewhere else.

I don't understand. My reasoning above has nothing to do with 'int i'.

> My concerns boil down to X being passed twice,
> once as reference and once as pointer.

That's exactly the thing I was trying to point out as illegal use of restrict.
Let me try again, with variables renamed for clarity:

struct X { int i; int * __restrict__ q; };

int foo (X& __restrict__ foox, X *foop)
{
   *foox.q = 1;
   foop->i = 0;
   return *foox.q;
}

int main()
{
  X mainx;
  mainx.q = &mainx.i;
  return foo (mainx, &mainx);
}

By:
- using restrict for the foox parameter of foo, and
- modifing object mainx during foo execution
we promise that we only access the object mainx using pointers based on foox
during foo execution.

However, we access mainx via foop in foo, and foop is not based on foox.

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[rguenther at suse dot de]

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

--- Comment #11 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 22 Sep 2015, vries at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62171
> 
> --- Comment #10 from vries at gcc dot gnu.org ---
> (In reply to rguenther@suse.de from comment #9)
> > On Tue, 22 Sep 2015, vries at gcc dot gnu.org wrote:
> > 
> > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62171
> > > 
> > > --- Comment #8 from vries at gcc dot gnu.org ---
> > > (In reply to Richard Biener from comment #7)
> > > > I was thinking about sth like
> > > > 
> > > > struct X { int i; int * __restrict__ q; };
> > > > 
> > > > int foo (X& __restrict__ x, X *p)
> > > > {
> > > >   *x.q = 1;
> > > >   p->i = 0;
> > > >   return *x.q;
> > > > }
> > > > 
> > > > int main()
> > > > {
> > > >   X x;
> > > >   x.q = &x.i;
> > > >   return foo (x, &x);
> > > > }
> > > > 
> > > 
> > > I think this example's an invalid use of restrict.
> > > 
> > > By using restrict in the 'X& __restrict__ x' parameter of foo, we promise that
> > > if the object x points to is modified during foo execution (and it is, by both
> > > assignments) we only access the object using pointers based on x during foo
> > > execution.
> > > 
> > > p is pointing to the same object, and we access the object via p. But p is not
> > > based on x.
> > 
> > Sorry, I modified it bogously, just move int i; out of the struct and
> > somewhere else.
> 
> I don't understand. My reasoning above has nothing to do with 'int i'.
> 
> > My concerns boil down to X being passed twice,
> > once as reference and once as pointer.
> 
> That's exactly the thing I was trying to point out as illegal use of restrict.
> Let me try again, with variables renamed for clarity:
> 
> struct X { int i; int * __restrict__ q; };
> 
> int foo (X& __restrict__ foox, X *foop)
> {
>    *foox.q = 1;
>    foop->i = 0;
>    return *foox.q;
> }
> 
> int main()
> {
>   X mainx;
>   mainx.q = &mainx.i;
>   return foo (mainx, &mainx);
> }
> 
> By:
> - using restrict for the foox parameter of foo, and
> - modifing object mainx during foo execution
> we promise that we only access the object mainx using pointers based on foox
> during foo execution.
> 
> However, we access mainx via foop in foo, and foop is not based on foox.

Hmm, indeed.  I guess we're fine then and could lift the restriction
even more via

Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c  (revision 228010)
+++ gcc/tree-ssa-structalias.c  (working copy)
@@ -5857,9 +5953,8 @@ intra_create_variable_infos (struct func
       /* For restrict qualified pointers to objects passed by
          reference build a real representative for the pointed-to object.
         Treat restrict qualified references the same.  */
-      if (TYPE_RESTRICT (TREE_TYPE (t))
-         && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
-             || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
+      if (POINTER_TYPE_P (TREE_TYPE (t))
+         && TYPE_RESTRICT (TREE_TYPE (t))
          && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
        {
          struct constraint_expr lhsc, rhsc;

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

--- Comment #12 from vries at gcc dot gnu.org ---
Committed test-case: https://gcc.gnu.org/ml/gcc-cvs/2015-09/msg01335.html :

Author: vries
Date: Mon Sep 28 08:19:42 2015
New Revision: 228193

URL: https://gcc.gnu.org/viewcvs?rev=228193&root=gcc&view=rev
Log:
Add gcc.dg/vect/pr62171.c

2015-09-28  Tom de Vries  <tom@codesourcery.com>

        * gcc.dg/vect/pr62171.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/vect/pr62171.c
Modified:
    trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/62171] restrict pointer to struct with restrict pointers parm doesn't prevent aliases

[vries at gcc dot gnu.org]

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

vries at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |FIXED

--- Comment #13 from vries at gcc dot gnu.org ---
Patch from comment 11 was committed (noted at PR67673).

Test-case has been committed.

marking resolved-fixed.