[Bug middle-end/36013] New: Wrong code involving restricted pointers to non-restricted pointers

[Bug middle-end/36013] New: Wrong code involving restricted pointers to non-restricted pointers

[rainy6144 at gmail dot com]

The program below aborts at runtime when compiled by gcc 4.3.0 with option "-O2
-std=c99" (it runs correctly without optimization or when compiled with "icc
-std=c99 -restrict").  I believe it should have defined behavior according to
the standard (see e.g. PR14192), for p[0] and q[0] are not restricted pointers,
and p[0][0] is based on p[0] but not p.  Intuitively, p and q should behave
like two different arrays of pointers, and we may well want to store aliasing
pointers into them.

This is apparently due to the simplistic find_base_decl() in 4.3.0, which is
quite different the standard's definition of "based on".  If I understand
correctly, for two pointers p and q, only when p is provably based on some
restricted pointer p0 (along all control paths), and q is provably not based on
it, can we be sure that a modification to *q can never change *p.

>From a casual glance of the 4.3.0 source, it seems that "restrict" is not well
supported by the tree passes, but the alias sets in the generated RTL make some
use of it.  Proper support, either at RTL or tree level, may mean a lot of
work, but in the meantime we had better agree on the meaning of the standard
and avoid generating wrong code :)

==============================================
#include <stdlib.h>

/* fail by gcc-4.3.0 */
void f(int **restrict p, int **restrict q)
{
  p[0][0] = 1;
  q[0][0] = 2;
  if (p[0][0] != 2) abort();
}

int main(void)
{
  int a;
  int *p1 = &a, *p2 = &a;
  f(&p1, &p2);
  return 0;
}


-- 
           Summary: Wrong code involving restricted pointers to non-
                    restricted pointers
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rainy6144 at gmail 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=36013

[Bug middle-end/36013] [4.1/4.3 Regression] Wrong code involving restricted pointers to non-restricted pointers

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2008-04-22 22:17 -------
Confirmed.  The tree level gets this right and we expand from

  # VUSE <SMT.4_7(D)>
  D.1761 = *p;
  # SMT.5_9 = VDEF <SMT.5_8(D)>
  *D.1761 = 1;
  # SMT.5_10 = VDEF <SMT.5_9>
  **q = 2;
  if (*D.1761 != 2)

and cse1 removes the comparison.


-- 

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
      Known to fail|                            |4.1.3 4.3.0
      Known to work|                            |4.0.4 4.2.3
   Last reconfirmed|0000-00-00 00:00:00         |2008-04-22 22:17:50
               date|                            |
            Summary|Wrong code involving        |[4.1/4.3 Regression] Wrong
                   |restricted pointers to non- |code involving restricted
                   |restricted pointers         |pointers to non-restricted
                   |                            |pointers
   Target Milestone|---                         |4.1.3


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[jakub at gcc dot gnu dot org]

------- Comment #2 from jakub at gcc dot gnu dot org  2008-04-25 09:21 -------
The alias sets seem to be wrong already in the *.expand dump:
(insn 7 6 8 3 pr36013.c:6 (set (reg/f:DI 58 [ D.1430 ])
        (mem/f:DI (reg/v/f:DI 59 [ p ]) [4 S8 A64])) -1 (nil))

(insn 8 7 9 3 pr36013.c:6 (set (mem:SI (reg/f:DI 58 [ D.1430 ]) [4 S4 A32])
        (const_int 1 [0x1])) -1 (nil))

(insn 9 8 10 3 pr36013.c:7 (set (reg/f:DI 61)
        (mem/f:DI (reg/v/f:DI 60 [ q ]) [5 S8 A64])) -1 (nil))

(insn 10 9 11 3 pr36013.c:7 (set (mem:SI (reg/f:DI 61) [3 S4 A32])
        (const_int 2 [0x2])) -1 (nil))

(insn 11 10 12 3 pr36013.c:8 (set (reg:CCZ 17 flags)
        (compare:CCZ (mem:SI (reg/f:DI 58 [ D.1430 ]) [4 S4 A32])
            (const_int 2 [0x2]))) -1 (nil))

(jump_insn 12 11 13 3 pr36013.c:8 (set (pc)
        (if_then_else (eq (reg:CCZ 17 flags)
                (const_int 0 [0x0]))
            (label_ref 16)
            (pc))) -1 (expr_list:REG_BR_PROB (const_int 9900 [0x26ac])
        (nil)))

Note *p and **p uses the same alias set 4 (bad) and *q uses alias set 5 (that's
ok, it should be different from *p as they can't alias) and **q uses 3.


-- 


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[jakub at gcc dot gnu dot org]

------- Comment #3 from jakub at gcc dot gnu dot org  2008-04-25 10:06 -------
      if (u && TREE_CODE (u) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (u))
        u = DECL_GET_RESTRICT_BASE (u);
in internal_get_tmp_var looks wrong to me.  That together with
find_single_pointer_decl not respecting indirection/array_ref barriers means
that
any depth of dereferences as long as they are gimplified one level at a time
are all marked DECL_BASED_ON_RESTRICT_P.

CCing Ian as he introduced that in 2005.


-- 

jakub at gcc dot gnu dot org changed:

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


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[jakub at gcc dot gnu dot org]

------- Comment #4 from jakub at gcc dot gnu dot org  2008-04-25 11:37 -------
The patch didn't come with any testcases, so it is hard to find out what
exactly is supposed to mean DECL_BASED_ON_RESTRICT_P on a decl.  Is that
supposed to
be on the same level of indirection as some TYPE_RESTRICT pointer
(i.e. say for int *** restrict p; formal decl initialized to p + 32 has
DECL_GET_RESTRICT_BASE p), or is it supposed to be one indirection different,
(e.g. formal decl initialized to *p + 32 has DECL_GET_RESTRICT_BASE p)?
>From the use in find_decl_base I'd think that it should be the same level,
as it will share the alias set with the pointer.  ATM gimplify.c sets this
as "somehow related to a restricted pointer".  Wonder if just making sure
that types_compatible_p between the DECL_GET_RESTRICT_BASE and the original
decl
in find_decl_base and only returning the restrict base if they have compatible
types would be sufficient, though that still sounds dangerous. 


-- 


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[ian at airs dot com]

------- Comment #5 from ian at airs dot com  2008-05-06 14:23 -------
I introduced DECL_BASED_ON_RESTRICT_P because the conversion to SSA discarded
almost all information about restrict qualifiers.  The compiler was tracking
restrict qualifiers on the original variable, but not on the GIMPLE variables. 
The main use of restrict qualifiers at the RTL level is in the scheduler, and I
didn't realize that it would be possible to write a machine-independent test
case.

DECL_BASED_ON_RESTRICT_P is meant to indicate that the temporary has the same
restrict qualifiers as the DECL_GET_RESTRICT_BASE.  It's not meant to be a
general implementation of "based on" as defined by the standard.  It's only
meant to say "this GIMPLE temporary has the same restrict qualifiers as this
user variable."

This patch fixes the problem, although I haven't tested it.

Index: gimplify.c
===================================================================
--- gimplify.c  (revision 134283)
+++ gimplify.c  (working copy)
@@ -391,6 +391,13 @@ find_single_pointer_decl_1 (tree *tp, in
 {
   tree *pdecl = (tree *) data;

+  /* We are only looking for pointers at the same level as the
+     original tree; we must not look through any indirections.
+     Returning anything other than NULL_TREE will cause the caller to
+     not find a base.  */
+  if (REFERENCE_CLASS_P (*tp))
+    return *tp;
+
   if (DECL_P (*tp) && POINTER_TYPE_P (TREE_TYPE (*tp)))
     {
       if (*pdecl)
@@ -406,8 +413,9 @@ find_single_pointer_decl_1 (tree *tp, in
   return NULL_TREE;
 }

-/* Find the single DECL of pointer type in the tree T and return it.
-   If there are zero or more than one such DECLs, return NULL.  */
+/* Find the single DECL of pointer type in the tree T, used directly
+   rather than via an indirection, and return it.  If there are zero
+   or more than one such DECLs, return NULL.  */

 static tree
 find_single_pointer_decl (tree t)
@@ -418,7 +426,8 @@ find_single_pointer_decl (tree t)
     {
       /* find_single_pointer_decl_1 returns a nonzero value, causing
         walk_tree to return a nonzero value, to indicate that it
-        found more than one pointer DECL.  */
+        found more than one pointer DECL or that it found an
+        indirection.  */
       return NULL_TREE;
     }



-- 


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[jakub at gcc dot gnu dot org]

------- Comment #6 from jakub at gcc dot gnu dot org  2008-05-06 22:56 -------
Created an attachment (id=15588)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15588&action=view)
gcc44-pr36013.patch

Patch I've bootstrapped/regtested on x86_64-linux.  Will you check this in, or
should I mail it to gcc-patches?

I've played with testcases like:

int
foo (int *__restrict p, int *__restrict q)
{
  int *r, *s, t;
  *p = 1;
  *q = 2;
  p[6] = 3;
  q[6] = 4;
  for (r = p, s = q, t = 0; r < p + 64; r++, s++)
    {
      *r = 7;
      *s = 88;
      t += *r;
    }
  return t;
}

and here neither tree nor RTL aliasing is ATM able to optimize the subsequent
read from *r out - while the accesses before the loop use different alias sets
(3 resp. 4), in the loop everything uses alias set 2, but that isn't a
regression introduced with this patch, so probably DECL_BASED_ON_RESTRICT_P
stuff needs more work, but that is unrelated to this bug.


-- 


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[ian at airs dot com]

------- Comment #7 from ian at airs dot com  2008-05-07 04:39 -------
I'll approve the patch.  I think it's correct.  I'll check it in in a day or
two, or you can go ahead and do it if you are ready.  Thanks for testing it.


-- 


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[jakub at gcc dot gnu dot org]

------- Comment #8 from jakub at gcc dot gnu dot org  2008-05-07 07:46 -------
Subject: Bug 36013

Author: jakub
Date: Wed May  7 07:45:17 2008
New Revision: 135029

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=135029
Log:
        PR middle-end/36013
        * gimplify.c (find_single_pointer_decl_1): Don't look through
        indirections.
        (find_single_pointer_decl): Adjust comments.

        * gcc.c-torture/execute/20080506-2.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/20080506-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimplify.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[jakub at gcc dot gnu dot org]

------- Comment #9 from jakub at gcc dot gnu dot org  2008-05-07 08:01 -------
Subject: Bug 36013

Author: jakub
Date: Wed May  7 08:00:36 2008
New Revision: 135032

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=135032
Log:
        PR middle-end/36013
        * gimplify.c (find_single_pointer_decl_1): Don't look through
        indirections.
        (find_single_pointer_decl): Adjust comments.

        * gcc.c-torture/execute/20080506-2.c: New test.

Added:
    branches/gcc-4_3-branch/gcc/testsuite/gcc.c-torture/execute/20080506-2.c
Modified:
    branches/gcc-4_3-branch/gcc/ChangeLog
    branches/gcc-4_3-branch/gcc/gimplify.c
    branches/gcc-4_3-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[jakub at gcc dot gnu dot org]

------- Comment #10 from jakub at gcc dot gnu dot org  2008-05-07 08:07 -------
Committed.


-- 

jakub at gcc dot gnu dot org changed:

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


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

[Bug middle-end/36013] [4.1/4.3/4.4 Regression] Wrong code involving restricted pointers to non-restricted pointers

[rguenther at suse dot de]

------- Comment #11 from rguenther at suse dot de  2008-05-07 08:21 -------
Subject: Re:  [4.1/4.3/4.4 Regression] Wrong code
 involving restricted pointers to non-restricted pointers

On Tue, 6 May 2008, jakub at gcc dot gnu dot org wrote:

> ------- Comment #6 from jakub at gcc dot gnu dot org  2008-05-06 22:56 -------
> Created an attachment (id=15588)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15588&action=view)
>  --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15588&action=view)
> gcc44-pr36013.patch
> 
> Patch I've bootstrapped/regtested on x86_64-linux.  Will you check this in, or
> should I mail it to gcc-patches?
> 
> I've played with testcases like:
> 
> int
> foo (int *__restrict p, int *__restrict q)
> {
>   int *r, *s, t;
>   *p = 1;
>   *q = 2;
>   p[6] = 3;
>   q[6] = 4;
>   for (r = p, s = q, t = 0; r < p + 64; r++, s++)
>     {
>       *r = 7;
>       *s = 88;
>       t += *r;
>     }
>   return t;
> }
> 
> and here neither tree nor RTL aliasing is ATM able to optimize the subsequent
> read from *r out - while the accesses before the loop use different alias sets
> (3 resp. 4), in the loop everything uses alias set 2, but that isn't a
> regression introduced with this patch, so probably DECL_BASED_ON_RESTRICT_P
> stuff needs more work, but that is unrelated to this bug.

The patch/rfc I posted two days ago optimizes the above case on the tree
level.  I will make sure something like that goes into 4.4.

Richard.


-- 


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