User account creation filtered due to spam.

Bug 29272 - [4.2 Regression] memcpy optimization causes wrong-code
Summary: [4.2 Regression] memcpy optimization causes wrong-code
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: 4.2.0
: P1 blocker
Target Milestone: 4.2.0
Assignee: Not yet assigned to anyone
URL:
Keywords: alias, wrong-code
Depends on:
Blocks:
 
Reported: 2006-09-28 16:03 UTC by Richard Biener
Modified: 2007-06-26 18:09 UTC (History)
7 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2006-09-29 04:40:41


Attachments
gcc42-pr29272.patch (781 bytes, patch)
2006-09-28 18:17 UTC, Jakub Jelinek
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2006-09-28 16:03:25 UTC
With the following testcase lowering memcpy to pointer assignment causes
wrong alias information to be generated.

struct Foo {
  int a;
  int b;
};
struct Node;
struct Node {
  struct Node *next;
};
struct Node *pool;
void grow (void)
{
  char *mem = __builtin_malloc (4096);
  struct Node *node = (struct Node *)mem;
  struct Foo *foo;
  __builtin_memcpy (&node->next, &pool, sizeof(struct Node*));
  pool = node;
} 
static inline void *alloc_one (void)
{ 
  struct Node *node = pool;
  __builtin_memcpy (&pool, &node->next, sizeof(struct Node*));
  return node;
}
static inline void dealloc_one (void *p)
{
  struct Node *node = p;
  __builtin_memcpy (&node->next, &pool, sizeof(struct Node*));
  pool = node;
}
int bar(void)
{
  grow();
  struct Foo* foo = alloc_one();
  foo->a = 0;
  foo->b = -1;
  dealloc_one (foo);
  return foo->a;
}

while we have in .optimized

<bb 2>:
  grow ();
  node = pool;
  D.1928 = node->next;
  pool = D.1928;
  foo = (struct Foo *) node;
  foo->a = 0;
  foo->b = -1;
  node = (struct Node *) foo;
  node->next = D.1928;
  pool = node;
  return foo->a;

asm generates:

bar:
.LFB5:
        subq    $8, %rsp
.LCFI1:
        call    grow
        movq    pool(%rip), %rax
        movl    $0, (%rax)
        movl    $-1, 4(%rax)
        xorl    %eax, %eax
        addq    $8, %rsp
        ret

which is wrong.
Comment 1 Jakub Jelinek 2006-09-28 17:57:37 UTC
I think after we want to look through handled_component_p's of destvar/srcvar
(in fold_builtin_memory_op) resp. var (in fold_builtin_memset) and see if
inside is a VAR_DECL or not.  If it is a VAR_DECL, then I believe the optimization is always safe, if it is INDIRECT_REF of a pointer, then it would
be only safe if we can make the read resp. write use forcibly alias set 0.
If we e.g. made a copy of the pointer and set DECL_POINTER_ALIAS_SET on it,
would that work and not be optimized out?
Comment 2 Jakub Jelinek 2006-09-28 18:17:56 UTC
Created attachment 12352 [details]
gcc42-pr29272.patch

Untested patch to just bail for non-vars.
Comment 3 Diego Novillo 2006-09-28 18:32:23 UTC
Excerpts from IRC session with jakub discussing this:

13:28 <dnovillo>      1    grow ();
13:28 <dnovillo>      2    node = pool;
13:28 <dnovillo>      3    D.1928 = node->next;
13:28 <dnovillo>      4    pool = D.1928;
13:28 <dnovillo>      5    foo = (struct Foo *) node;
13:28 <dnovillo>      6    foo->a = 0;
13:28 <dnovillo>      7    foo->b = -1;
13:28 <dnovillo>      8    node = (struct Node *) foo;   <- redundant. node == foo already.
13:28 <dnovillo>      9    node->next = D.1928;          <- redundant. node->next == D.1928 already
13:28 <dnovillo>     10    pool = node;                  <- redundant. node == pool already.
13:28 <dnovillo>     11    return foo->a;
13:33 <jakub> line 9 is not redundant, because node->next occupies the same memory as foo->a and foo->b
13:34 <jakub> I think we have 2 options with this optimization
13:35 <jakub> 1) for each memcpy etc. operand, look through all handled components and if it is an actual VAR_DECL, we can surely optimize it, with the native alias set
13:36 <jakub> but if it is a pointer, we can't be sure
13:37 <jakub> now, either we figure out some way how to express that operation in an alias friendly way if it is a pointer, or we just bail and don't optimize
13:37 <dnovillo> but, my point was that i don't see where the RTL optimizers may be screwing up.  what's the exact operation that they remove that they shouldn't have?
13:37 <dnovillo> it all looks removable to me.
13:39 <jakub> RTL optimizers remove the node->next = D.1928 line
13:40 <jakub> which means 1) pool->next is in the end 0 rather than old pool->next
13:40 <jakub> and 2) 0 is returned rather than (int) pool->next
13:40 <dnovillo> but D.1928 and node->next have the same value according to the tree dump.  or am i misreading something?
14:03 <jakub> foo == node, so foo->a and node->next occupy the same memory
14:03 <dnovillo> oh, crap.
14:03 <jakub> and eventhough those 2 have aliasing incompatible types, the use of memcpy makes it ok
14:03 <dnovillo> i had missed that.
14:04 <jakub> guess I'll now write just a quick patch to only do it for VAR_DECLs and components thereof
14:05 <jakub> so that the bug is fixed and we can then keep discussing how even pointers can be safely optimized
14:05 <dnovillo> so, going back to not apply this on pointers then?
14:05 <dnovillo> yeah, for now that would be the safe approach.
14:10 <jakub>   /* If var is a VAR_DECL or a component thereof,
14:10 <jakub>      we can use its alias set, otherwise we'd need to make
14:10 <jakub>      sure we go through alias set 0.  */
14:10 <jakub>   inner = srcvar;
14:10 <jakub>   while (handled_component_p (inner))
14:10 <jakub>     inner = TREE_OPERAND (inner, 0);
14:10 <jakub>   if (TREE_CODE (inner) != VAR_DECL)
14:10 <jakub>     return 0;
14:11 <jakub> or should I use SSA_VAR_P (inner) instead?
14:12 <jakub> I guess at least PARM_DECL or RESULT_DECL would be ok, not sure about SSA names
14:22 <dnovillo> the reason we don't screw up in the trees is the presence of points-to information, most likely.  i got tricked because i wasn't following who was pointing to who.
14:22 <dnovillo> the store foo->a changes node->next.
14:23 <dnovillo> bah.
14:23 <dnovillo> RTL misses that because the stores have different alias sets.
14:23 <dnovillo> the transformation we do on trees is invalid for RTL because we don't keep points-to info in RTL, only type info.
14:23 <dnovillo> the Real Fix would tag the stores so that gimple->RTL changes the alias sets.
14:24 <dnovillo> something along the lines of what you suggest may work.
14:26 <jakub> yeah, now to find a way to force the alias set...
Comment 4 Richard Biener 2006-09-29 09:14:45 UTC
Here's an executable testcase which is miscompiled at the tree-level.

extern void abort(void);
struct Foo {
  int a;
  int b;
};
struct Node;
struct Node {
  struct Node *next;
};
struct Node *pool;
void grow (void)
{
  char *mem = __builtin_malloc (4096);
  struct Node *node = (struct Node *)mem;
  struct Foo *foo;
  __builtin_memcpy (&node->next, &pool, sizeof(struct Node*));
  pool = node;
}
static inline void *alloc_one (void)
{
  struct Node *node = pool;
  __builtin_memcpy (&pool, &node->next, sizeof(struct Node*));
  return node;
}
static inline void dealloc_one (void *p)
{
  struct Node *node = p;
  __builtin_memcpy (&node->next, &pool, sizeof(struct Node*));
  pool = node;
}
int main()
{
  grow();
  struct Foo* foo = alloc_one();
  foo->a = 0;
  foo->b = -1;
  dealloc_one (foo);
  if (foo->b == -1)
    abort ();
  return 0;
}
Comment 5 Andrew Pinski 2006-09-29 17:30:12 UTC
I think we can declare this as invalid code for C and unkown for C++.

For C++, inplacement new is supposed to "fix" the problem with different types as C++ defines aliasing based on the dynamic type but we get a different bug with that being PR 29286.
Comment 6 Jakub Jelinek 2006-09-29 22:04:37 UTC
Is:
extern void abort (void);

struct S { struct S *s; } s;
struct T { struct T *t; } t;

static inline void
foo (void *s)
{
  struct T *p = s;
  __builtin_memcpy (&p->t, &t.t, sizeof (t.t));
}

void *
__attribute__((noinline))
bar (void *p, struct S *q)
{
  q->s = &s;
  foo (p);
  return q->s;
}

int
main (void)
{
  t.t = &t;
  if (bar (&s, &s) != (void *) &t)
    abort ();
  return 0;
}

valid?  I'd say yes, we either access s.s using its declared (== effective) type,
or through memcpy (which is supposed tobe a char array access and therefore
ok wrt. aliasing).
Comment 7 Andrew Pinski 2006-09-29 22:13:33 UTC
Subject: Re:  [4.2 Regression] memcpy optimization causes wrong-code

> 
> 
> 
> ------- Comment #6 from jakub at gcc dot gnu dot org  2006-09-29 22:04 -------
> Is:
> extern void abort (void);
> 
> struct S { struct S *s; } s;
> struct T { struct T *t; } t;
> 
> static inline void
> foo (void *s)
> {
>   struct T *p = s;
>   __builtin_memcpy (&p->t, &t.t, sizeof (t.t));

I think the problem is really is &p->t include an access or not?
I know if p is NULL, this is undefined as &p->t is now have a NULL pointer
access but does that include using memcpy?

-- Pinski
Comment 8 Mike Stump 2006-09-29 23:15:15 UTC
> If it is a VAR_DECL, then I believe the optimization is always safe

Not in C++.
Comment 9 rguenther@suse.de 2006-09-30 11:46:06 UTC
Subject: Re:  [4.2 Regression] memcpy optimization
 causes wrong-code

On Sat, 29 Sep 2006, pinskia at physics dot uc dot edu wrote:

> ------- Comment #7 from pinskia at physics dot uc dot edu  2006-09-29 22:13 -------
> Subject: Re:  [4.2 Regression] memcpy optimization causes wrong-code
> > ------- Comment #6 from jakub at gcc dot gnu dot org  2006-09-29 22:04 -------
> > Is:
> > extern void abort (void);
> > 
> > struct S { struct S *s; } s;
> > struct T { struct T *t; } t;
> > 
> > static inline void
> > foo (void *s)
> > {
> >   struct T *p = s;
> >   __builtin_memcpy (&p->t, &t.t, sizeof (t.t));
> 
> I think the problem is really is &p->t include an access or not?
> I know if p is NULL, this is undefined as &p->t is now have a NULL pointer
> access but does that include using memcpy?

If you write it as memcpy (p, &t, ...) then it is ok.  Now I think
by applying common sense 6.5.3.2/3 can be applied to &p->t, too.
Comment 10 rguenther@suse.de 2006-09-30 11:47:03 UTC
Subject: Re:  [4.2 Regression] memcpy optimization
 causes wrong-code

On Sat, 29 Sep 2006, mrs at apple dot com wrote:

> ------- Comment #8 from mrs at apple dot com  2006-09-29 23:15 -------
> > If it is a VAR_DECL, then I believe the optimization is always safe
> 
> Not in C++.

As safe as using memcpy, which does not add any semantics to an
access using the VAR_DECL.  So I believe this is safe even for C++.

Comment 11 Jakub Jelinek 2006-09-30 11:49:36 UTC
The primary advantage of the single entry optimization is actually that
at tree level we can find out if something is only addressable because of the
memcpy/memset/mempcpy/memmove and not for other reasons.  So, creating
a pointer to the object, adding may_alias attribute to the type and dereferencing
it doesn't buy us much, because it would still be addressable.  So, either
we have a way to mark the VAR_DECL (or component thereof) read resp. write
with alias set 0, or we need the patch I posted, possibly with additional
check for C++/ObjC++ and don't do the optimization at all for C++.
Comment 12 Jakub Jelinek 2006-10-01 22:35:41 UTC
Wrt #8, can you come up with a C++ testcase where
using var = x; is invalid, but using memcpy (&var, &x, sizeof (var)); (where
sizeof (var) == sizeof (x)) makes it valid C++ (from aliasing point of view)?
Comment 13 Jakub Jelinek 2006-10-10 09:47:09 UTC
Subject: Bug 29272

Author: jakub
Date: Tue Oct 10 09:46:59 2006
New Revision: 117599

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117599
Log:
	PR middle-end/29272
	* builtins.c (var_decl_component_p): New function.
	(fold_builtin_memset, fold_builtin_memory_op): Restrict
	single entry optimization to variables and components thereof.

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

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/20060930-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/builtins.c
    trunk/gcc/testsuite/ChangeLog

Comment 14 Richard Biener 2006-10-11 22:04:10 UTC
This is fixed now.  Or was invalid.
Comment 15 cvs-commit@developer.classpath.org 2006-12-06 11:37:36 UTC
Subject: Bug 29272

CVSROOT:	/cvsroot/classpath
Module name:	classpath
Changes by:	Chris Burdess <dog>	06/12/06 11:36:42

Modified files:
	.              : ChangeLog 
	gnu/xml/stream : SAXParser.java 
	javax/xml/parsers: DocumentBuilderFactory.java 

Log message:
	2006-12-06  Chris Burdess  <dog@gnu.org>
	
		Fixes PR 29272.
		* javax/xml/parsers/DocumentBuilderFactory.java: Fix broken Javadoc.
		* gnu/xml/stream/SAXParser.java: Fix file descriptor leak.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/classpath/ChangeLog?cvsroot=classpath&r1=1.8928&r2=1.8929
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/stream/SAXParser.java?cvsroot=classpath&r1=1.21&r2=1.22
http://cvs.savannah.gnu.org/viewcvs/classpath/javax/xml/parsers/DocumentBuilderFactory.java?cvsroot=classpath&r1=1.5&r2=1.6



Comment 16 cvs-commit@developer.classpath.org 2006-12-08 10:30:41 UTC
Subject: Bug 29272

CVSROOT:	/cvsroot/classpath
Module name:	classpath
Branch:		generics-branch
Changes by:	Mark Wielaard <mark>	06/12/08 10:30:10

Modified files:
	.              : ChangeLog 
	gnu/xml/dom    : DomAttr.java DomNode.java 
	gnu/xml/stream : SAXParser.java XMLStreamWriterImpl.java 
	javax/xml/parsers: DocumentBuilderFactory.java 
	javax/xml/validation: SchemaFactory.java 

Log message:
	2006-12-06  Ben Konrath  <bkonrath@redhat.com>
	
	       Fixes PR 29853.
	       * gnu/xml/dom/DomAttr.java: Don't report mutation if oldValue and
	       newValue are the same.
	       * gnu/xml/dom/DomNode.java: Set parent if null during mutation.
	
	2006-12-06  Chris Burdess  <dog@gnu.org>
	
	       Fixes PR 29272.
	       * javax/xml/parsers/DocumentBuilderFactory.java: Fix broken Javadoc.
	       * gnu/xml/stream/SAXParser.java: Fix file descriptor leak.
	
	2006-12-06  Chris Burdess  <dog@gnu.org>
	
	       Fixes PR 29264.
	       * gnu/xml/stream/XMLStreamWriterImpl.java: Allow arbitrary text in
	       writeDTD method.
	
	2006-12-056  Chris Burdess  <dog@gnu.org>
	
	       Fixes PR 28816.
	       * javax/xml/validation/SchemaFactory.java: Use correct algorithm to
	       discover schema factory implementation class.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/classpath/ChangeLog?cvsroot=classpath&only_with_tag=generics-branch&r1=1.2386.2.358&r2=1.2386.2.359
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/dom/DomAttr.java?cvsroot=classpath&only_with_tag=generics-branch&r1=1.1.2.3&r2=1.1.2.4
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/dom/DomNode.java?cvsroot=classpath&only_with_tag=generics-branch&r1=1.1.2.10&r2=1.1.2.11
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/stream/SAXParser.java?cvsroot=classpath&only_with_tag=generics-branch&r1=1.14.2.4&r2=1.14.2.5
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/stream/XMLStreamWriterImpl.java?cvsroot=classpath&only_with_tag=generics-branch&r1=1.1.2.4&r2=1.1.2.5
http://cvs.savannah.gnu.org/viewcvs/classpath/javax/xml/parsers/DocumentBuilderFactory.java?cvsroot=classpath&only_with_tag=generics-branch&r1=1.1.2.5&r2=1.1.2.6
http://cvs.savannah.gnu.org/viewcvs/classpath/javax/xml/validation/SchemaFactory.java?cvsroot=classpath&only_with_tag=generics-branch&r1=1.1.2.5&r2=1.1.2.6



Comment 17 cvs-commit@developer.classpath.org 2006-12-08 10:32:25 UTC
Subject: Bug 29272

CVSROOT:	/cvsroot/classpath
Module name:	classpath
Branch:		classpath-0_93-branch
Changes by:	Mark Wielaard <mark>	06/12/08 10:31:50

Modified files:
	.              : ChangeLog 
	gnu/xml/dom    : DomAttr.java DomNode.java 
	gnu/xml/stream : SAXParser.java XMLStreamWriterImpl.java 
	javax/xml/parsers: DocumentBuilderFactory.java 
	javax/xml/validation: SchemaFactory.java 

Log message:
	2006-12-06  Ben Konrath  <bkonrath@redhat.com>
	
	       Fixes PR 29853.
	       * gnu/xml/dom/DomAttr.java: Don't report mutation if oldValue and
	       newValue are the same.
	       * gnu/xml/dom/DomNode.java: Set parent if null during mutation.
	
	2006-12-06  Chris Burdess  <dog@gnu.org>
	
	       Fixes PR 29272.
	       * javax/xml/parsers/DocumentBuilderFactory.java: Fix broken Javadoc.
	       * gnu/xml/stream/SAXParser.java: Fix file descriptor leak.
	
	2006-12-06  Chris Burdess  <dog@gnu.org>
	
	       Fixes PR 29264.
	       * gnu/xml/stream/XMLStreamWriterImpl.java: Allow arbitrary text in
	       writeDTD method.
	
	2006-12-056  Chris Burdess  <dog@gnu.org>
	
	       Fixes PR 28816.
	       * javax/xml/validation/SchemaFactory.java: Use correct algorithm to
	       discover schema factory implementation class.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/classpath/ChangeLog?cvsroot=classpath&only_with_tag=classpath-0_93-branch&r1=1.8897.2.14&r2=1.8897.2.15
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/dom/DomAttr.java?cvsroot=classpath&only_with_tag=classpath-0_93-branch&r1=1.3&r2=1.3.12.1
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/dom/DomNode.java?cvsroot=classpath&only_with_tag=classpath-0_93-branch&r1=1.16&r2=1.16.2.1
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/stream/SAXParser.java?cvsroot=classpath&only_with_tag=classpath-0_93-branch&r1=1.21&r2=1.21.4.1
http://cvs.savannah.gnu.org/viewcvs/classpath/gnu/xml/stream/XMLStreamWriterImpl.java?cvsroot=classpath&only_with_tag=classpath-0_93-branch&r1=1.5&r2=1.5.12.1
http://cvs.savannah.gnu.org/viewcvs/classpath/javax/xml/parsers/DocumentBuilderFactory.java?cvsroot=classpath&only_with_tag=classpath-0_93-branch&r1=1.5&r2=1.5.10.1
http://cvs.savannah.gnu.org/viewcvs/classpath/javax/xml/validation/SchemaFactory.java?cvsroot=classpath&only_with_tag=classpath-0_93-branch&r1=1.5&r2=1.5.6.1



Comment 18 Jakub Jelinek 2007-06-26 11:47:29 UTC
Subject: Bug 29272

Author: jakub
Date: Tue Jun 26 11:47:19 2007
New Revision: 126023

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=126023
Log:
	PR middle-end/29272
	* builtins.c (fold_builtin_memset, fold_builtin_memory_op): Restrict
	single entry optimization to variables and components thereof.

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

Added:
    branches/redhat/gcc-4_1-branch/gcc/testsuite/gcc.c-torture/execute/20060930-2.c
Modified:
    branches/redhat/gcc-4_1-branch/gcc/ChangeLog
    branches/redhat/gcc-4_1-branch/gcc/builtins.c
    branches/redhat/gcc-4_1-branch/gcc/testsuite/ChangeLog