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; }
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.
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.
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.
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.
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; }
Created attachment 15588 [details] 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.
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.
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
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
Committed.
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) > 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.