[Bug tree-optimization/29145] New: unsafe use of restrict qualifier

[Bug tree-optimization/29145] New: unsafe use of restrict qualifier

[djg at cray dot com]

In the test case below, GCC doesn't observe a non-restrict-qualified
pointer being "based on" a restrict-qualified pointer. On i686-pc-linux-gnu, 
this program aborts when compiled with
-O2 -msse -ftree-vectorize
because the loop in function with_restrict is vectorized based on an unsafe
alias assumption.

void abort(void);
void exit(int);

void with_restrict(int * __restrict p)
{
  int i;
  int *q = p - 2;

  for (i = 0; i < 1000; ++i) {
    p[i] = q[i];
  }
}

void without_restrict(int * p)
{
  int i;
  int *q = p - 2;

  for (i = 0; i < 1000; ++i) {
    p[i] = q[i];
  }
}

int main(void)
{
  int i;
  int a[1002];
  int b[1002];

  for (i = 0; i < 1002; ++i) {
    a[i] = b[i] = i;
  }

  with_restrict(a + 2);
  without_restrict(b + 2);

  for (i = 0; i < 1002; ++i) {
    if (a[i] != b[i])
      abort();
  }
  exit(0);
}


-- 
           Summary: unsafe use of restrict qualifier
           Product: gcc
           Version: 4.1.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: djg at cray dot com
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-09-19 16:43 -------
Actually restrict is weird and you might be violating one of the rules for
restrict, I always forget those rules and don't really understand them that
well.


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[djg at cray dot com]

------- Comment #2 from djg at cray dot com  2006-09-20 23:49 -------
The definition of restrict in C99 6.7.3.1 doesn't say that only the original
restrict-qualified pointer can be used to access the object it points to; it
says that any pointer "based on" the original restrict-qualified pointer may
access the object.

Following paragraph #3, q is "based on" p.

The code in question in GCC seems to be the code by this comment, in
tree-data-ref.c:

   /* An instruction writing through a restricted pointer is "independent" of
any
      instruction reading or writing through a different pointer, in the same
      block/scope.  */


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[ian at airs dot com]

------- Comment #3 from ian at airs dot com  2006-11-02 16:07 -------
This looks like a compiler bug to me.  The code in base_addr_differ_p seems
dubious anyhow: in principle,may_alias_p should handle restrict, it shouldn't
be handled by the caller.

It looks like this code has been there since tree-vect-analyze.c was added in
2005-02-17.


-- 

ian at airs dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dorit at il dot ibm dot com


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2006-11-02 16:10 -------
Confirmed.  (this is also why effective restrict is hard to do without better
PTA)


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2006-11-02 16:10:22
               date|                            |


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[dberlin at gcc dot gnu dot org]

------- Comment #5 from dberlin at gcc dot gnu dot org  2006-11-04 04:15 -------
This was something that slipped in, IIRC. I was of Ian's viewpoint, that
may_alias_p should handle it, and it shouldn't be special to data-references.
But it can't, at least in it's current state, because it somehow gets stripped.

I forget the exact details, but diego has explained this to me before :).

Diego, what was the deal with restrict and stripping qualifications that caused
us to not see restrict when it comes time for may_alias_p? 

Anyway, what exactly does "based on" mean?

is the following legal?

int *whee(int *__restrict a)
{
return a - 2;
}
void with_restrict(int * __restrict p)
{
  int i;
  int *q = whee(p);

  for (i = 0; i < 1000; ++i) {
    p[i] = q[i];
  }


If so, we'll never be able to get restrict right on a intraprocedural basis,
and it makes restrict completely useless for almost all cases that restricted
pointers escape :)


-- 

dberlin at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dnovillo at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[dorit at il dot ibm dot com]

------- Comment #6 from dorit at il dot ibm dot com  2006-11-05 15:48 -------
(In reply to comment #5)
> This was something that slipped in, IIRC. I was of Ian's viewpoint, that
> may_alias_p should handle it, and it shouldn't be special to data-references.

yes, it was originally added as a temporary hack until alias analysis did
something with restrict


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[djg at cray dot com]

------- Comment #7 from djg at cray dot com  2006-11-05 16:50 -------
(In reply to comment #5)

"based on" basically means copied from, and possibly incremented or
decremented, though not necessarily in obvious ways. Your example is
legal; q is based on p.

BTW, I made a mistake in my earlier suggestion; simply checking that both
pointers are restrict-qualified isn't sufficient if expressions may have
moved across the original C scope boundaries. 


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[dorit at il dot ibm dot com]

------- Comment #8 from dorit at il dot ibm dot com  2007-01-07 20:22 -------
I'm testing this patch, that makes us more conservative, and concludes that two
pointers don't overlap only if both are "based on" restricted pointers, with
"based on" trivially implemented as the pointer used in the reference itself.
In addition, we check that the declarations of both pointers are in the
parameter list of the same function (to be safe w.r.t the scope of the pointer
declarations). Looks like this should be safe enough?

Most of the vectorizer testcases still get vectorized with this patch. Two
testcases that don't, however, are - vect-[74,80].c, for which we need a bit
less trivial implementation of "based on". We can start with this conservative
implementation, switch this PR to a "missed optimization", and gradually work
on relaxing the restrictions as much as we can.


Index: tree-data-ref.c
===================================================================
--- tree-data-ref.c     (revision 120551)
+++ tree-data-ref.c     (working copy)
@@ -490,6 +490,7 @@
   tree addr_a = DR_BASE_ADDRESS (dra);
   tree addr_b = DR_BASE_ADDRESS (drb);
   tree type_a, type_b;
+  tree decl_a, decl_b;
   bool aliased;

   if (!addr_a || !addr_b)
@@ -547,14 +548,25 @@
     }

   /* An instruction writing through a restricted pointer is "independent" of
any
-     instruction reading or writing through a different pointer, in the same 
-     block/scope.  */
-  else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
-      || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
+     instruction reading or writing through a different restricted pointer, 
+     in the same block/scope.  */
+  else if (TYPE_RESTRICT (type_a)
+          &&  TYPE_RESTRICT (type_b) 
+          && (!DR_IS_READ (drb) || !DR_IS_READ (dra))
+          && TREE_CODE (DR_BASE_ADDRESS (dra)) == SSA_NAME
+          && (decl_a = SSA_NAME_VAR (DR_BASE_ADDRESS (dra)))
+          && TREE_CODE (decl_a) == PARM_DECL
+          && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
+          && TREE_CODE (DR_BASE_ADDRESS (drb)) == SSA_NAME
+          && (decl_b = SSA_NAME_VAR (DR_BASE_ADDRESS (drb)))
+          && TREE_CODE (decl_b) == PARM_DECL
+          && TREE_CODE (DECL_CONTEXT (decl_b)) == FUNCTION_DECL
+          && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b)) 
     { 
       *differ_p = true;
       return true;
     }
+
   return false;
 }


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[patchapp at dberlin dot org]

------- Comment #9 from patchapp at dberlin dot org  2007-01-09 09:35 -------
Subject: Bug number PR29145

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2007-01/msg00648.html


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[djg at cray dot com]

------- Comment #10 from djg at cray dot com  2007-01-26 21:09 -------
(In reply to comment #8)
> I'm testing this patch, that makes us more conservative, and concludes that two
> pointers don't overlap only if both are "based on" restricted pointers, with
> "based on" trivially implemented as the pointer used in the reference itself.
> In addition, we check that the declarations of both pointers are in the
> parameter list of the same function (to be safe w.r.t the scope of the pointer
> declarations). Looks like this should be safe enough?

One thing I can think of that this description misses is that the two pointers
must be based-on *different* restrict-qualified pointers, unless that case is
already handled elsewhere.


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[dorit at il dot ibm dot com]

------- Comment #11 from dorit at il dot ibm dot com  2007-02-06 08:18 -------
(In reply to comment #10)
> One thing I can think of that this description misses is that the two 
> pointers must be based-on *different* restrict-qualified pointers, unless 
> that case is already handled elsewhere.

yes, at the beginning of this function we check if the two pointers are the
same, and if so - we don't reach this part of the code. Since our
implementation of "based on" is the pointer itself (i.e. "is ptr_a based on
some restricted pointer ptr_b" is implemented as "is ptr_a a restricted
pointer", we are safe. You're right though that when the implementation of
"based on" is extended, we'd need to compare the two restricted pointers (we
now compare the two ptr_a's, we'd need to compare the two ptr_b's). 


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[dorit at gcc dot gnu dot org]

------- Comment #12 from dorit at gcc dot gnu dot org  2007-02-12 13:15 -------
Subject: Bug 29145

Author: dorit
Date: Mon Feb 12 13:14:52 2007
New Revision: 121844

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=121844
Log:
        PR tree-optimization/29145
        * tree-data-ref.c (base_addr_differ_p): Make us more conservative
        in our handling of restrict qualified pointers.


Added:
    trunk/gcc/testsuite/gcc.dg/vect/pr29145.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/vect/vect-74.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-80.c
    trunk/gcc/tree-data-ref.c


-- 


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

[Bug tree-optimization/29145] unsafe use of restrict qualifier

[dorit at gcc dot gnu dot org]

------- Comment #13 from dorit at gcc dot gnu dot org  2007-07-01 08:32 -------
Fix committed, PR can be closed.


-- 

dorit at gcc dot gnu dot org changed:

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


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