[Bug c++/60965] New: IPA: Devirtualization versus placement new

[Bug c++/60965] New: IPA: Devirtualization versus placement new

[aph at gcc dot gnu.org]

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

            Bug ID: 60965
           Summary: IPA: Devirtualization versus placement new
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: aph at gcc dot gnu.org

Created attachment 32683
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32683&action=edit
Reproducer here:

Summary: Devirtualization uses type information to determine if a
virtual method is reachable from a call site.  If type information
indicates that it is not, devirt marks the site as unreachable.  I
think this is wrong, and it breaks some programs.

Consider this class:

class Container {
  void *buffer[5];
public:
  EmbeddedObject *obj() { return (EmbeddedObject*)buffer; }
  Container() { new (buffer) EmbeddedObject(); }
};

Placement new is used to embed an object in a buffer inside another
object.  Its address can be retrieved.  This usage of placement new is
common, and it even appears as the canonical use of placement new in
the in the C++ FAQ at
http://www.parashift.com/c++-faq/placement-new.html.  (I am aware that
this may not be strictly legal.  For one thing, the memory at buffer
may not be suitably aligned.  Please bear with me.)

The embedded object is an instance of:

class EmbeddedObject {
public:
  virtual int val() { return 2; }
};

And it is called like this:

extern Container o;
int main() {

  cout << o.obj()->val() << endl;
}

The devirtualization pass looks into the call to val() and the type of
o, decides that there is no type inside o that is compatible with
EmbeddedObject, and inserts a call to __builtin_unreachanble().  As a
result, instead of printing 2, the program does nothing.

[Bug ipa/60965] IPA: Devirtualization versus placement new

[aph at gcc dot gnu.org]

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

Andrew Haley <aph at gcc dot gnu.org> changed:

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

--- Comment #1 from Andrew Haley <aph at gcc dot gnu.org> ---
*** Bug 60963 has been marked as a duplicate of this bug. ***

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-04-25
      Known to work|                            |4.8.2, 4.9.0
            Summary|IPA: Devirtualization       |[4.10 Regression] IPA:
                   |versus placement new        |Devirtualization versus
                   |                            |placement new
     Ever confirmed|0                           |1

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Self-contained reproducer, using -std=c++11 -O2

#include <new>

class EmbeddedObject {
public:
  virtual int val() { return 2; }
};

class Container {
  alignas(EmbeddedObject) char buffer[sizeof(EmbeddedObject)];
public:
  EmbeddedObject *obj() { return (EmbeddedObject*)buffer; }
  Container() { new (buffer) EmbeddedObject(); }
};

Container o;

int main()
{
  __builtin_printf("%d\n", o.obj()->val());
}

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[jamborm at gcc dot gnu.org]

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

Martin Jambor <jamborm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu.org,
                   |                            |jamborm at gcc dot gnu.org

--- Comment #3 from Martin Jambor <jamborm at gcc dot gnu.org> ---
http://gcc.gnu.org/ml/gcc-patches/2014-04/msg01684.html might make
eventual testcase creation slightly easier.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[hubicka at gcc dot gnu.org]

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

Jan Hubicka <hubicka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |hubicka at gcc dot gnu.org

--- Comment #4 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Mine, probably 4.9 regression, too.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.10.0

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[aph at gcc dot gnu.org]

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

--- Comment #5 from Andrew Haley <aph at gcc dot gnu.org> ---
Jan, can we please have an ETA to fix this?  It is a very importantant problem
for Java because it breaks OpenJDK.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[hubicka at gcc dot gnu.org]

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

--- Comment #6 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
I am testing the attached patch.
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c        (revision 209913)
+++ ipa-devirt.c        (working copy)
@@ -1137,6 +1159,17 @@
   context->outer_type = expected_type;
   context->offset = 0;
   context->maybe_derived_type = true;
+  context->maybe_in_construction = true;
+  /* Non-POD can be changed to instance of polymorphic type by
+     placement new.  Here we play safe and assume that any
+     non-polymorphic type is non-POD.  */
+  if ((TREE_CODE (type) != RECORD_TYPE
+       || !TYPE_BINFO (type)
+       || !polymorphic_type_binfo_p (TYPE_BINFO (type)))
+      && (TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
+         || (offset + tree_to_uhwi (TYPE_SIZE (expected_type)) <=
+             tree_to_uhwi (TYPE_SIZE (type)))))
+    return true;
   return false;
 }

Can you, please, double check that it fixes the Java issues? It is a bit
questionable on how precisely define what type transitions are allowed by
placement new.  This is quite conservative definition except for the
requirement that type needs to be large enough to contain the newly built type.
This condition may need relaxation for open ended types (ones having arrays at
end, I think that is rule used by aliasing code in simliar case), but I believe
at least for 4.9 this is non-issue: we only care non-heap decls and this is not
a problem here.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[jason at gcc dot gnu.org]

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

Jason Merrill <jason at gcc dot gnu.org> changed:

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

--- Comment #7 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Jan Hubicka from comment #6)
> It is a bit
> questionable on how precisely define what type transitions are allowed by
> placement new.  This is quite conservative definition except for the
> requirement that type needs to be large enough to contain the newly built
> type.

We don't need to handle all non-PODs; arrays of (unsigned) char are special
under the aliasing rules, so that you can construct any type of object in a
char array and access the object representation of any type via a char pointer.
 You can't randomly change the object stored in a buffer of any other type.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[aph at gcc dot gnu.org]

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

--- Comment #8 from Andrew Haley <aph at gcc dot gnu.org> ---
(In reply to Jason Merrill from comment #7)
> (In reply to Jan Hubicka from comment #6)
> > It is a bit
> > questionable on how precisely define what type transitions are allowed by
> > placement new.  This is quite conservative definition except for the
> > requirement that type needs to be large enough to contain the newly built
> > type.
> 
> We don't need to handle all non-PODs; arrays of (unsigned) char are special
> under the aliasing rules, so that you can construct any type of object in a
> char array and access the object representation of any type via a char
> pointer.  You can't randomly change the object stored in a buffer of any
> other type.

While it's true that we can play hardball on this one by insisting that only
char arrays should be used with placement new, it wouldn't really do any good. 
I don't think it would make any real-world code more efficient.  It makes sense
to play safe by assuming that any object of a non-polymorphic type might be
overwritten by placement new.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[jason at gcc dot gnu.org]

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

--- Comment #9 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Andrew Haley from comment #8)
> While it's true that we can play hardball on this one by insisting that only
> char arrays should be used with placement new, it wouldn't really do any
> good.  I don't think it would make any real-world code more efficient.

On the contrary, this bug is an example of making real code more efficient,
just inappropriately because of the special status of char arrays.  We really
don't want to have to assume that any random object can invisibly change type,
as that would make type-based optimizations pretty useless.

As far as I know people always use char arrays for placement new anyway; at
least all the examples I've ever seen do.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[harald at gigawatt dot nl]

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

Harald van Dijk <harald at gigawatt dot nl> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |harald at gigawatt dot nl

--- Comment #10 from Harald van Dijk <harald at gigawatt dot nl> ---
(In reply to Jan Hubicka from comment #4)
> Mine, probably 4.9 regression, too.

It is, and Jonathan Wakely's earlier reduction exposes it on 4.9 too.

(In reply to Jan Hubicka from comment #6)
> Can you, please, double check that it fixes the Java issues?

With 4.9.0, for me, IcedTea reliably hangs during the build process. I hadn't
investigated the problem at all, but with 4.9.0 plus your patch, it builds
successfully.

What I had looked into was a segmentation fault in Qt
(https://bugreports.qt-project.org/browse/QTBUG-38733) and Chromium, both using
WebKit, also because of this. Chromium is still building, but for Qt, I can
confirm it is also fixed by your patch.

(In reply to Jason Merrill from comment #9)
> As far as I know people always use char arrays for placement new anyway; at
> least all the examples I've ever seen do.

Or a structure containing (possibly indirectly) a character array as its first
member, such as aligned_storage. But as long as a pointer to such a structure
is indistinguishable from a pointer to the contained character array, that
should not be a problem.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[aph at gcc dot gnu.org]

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

--- Comment #11 from Andrew Haley <aph at gcc dot gnu.org> ---
(In reply to Jason Merrill from comment #9)
> (In reply to Andrew Haley from comment #8)
> > While it's true that we can play hardball on this one by insisting that only
> > char arrays should be used with placement new, it wouldn't really do any
> > good.  I don't think it would make any real-world code more efficient.
> 
> On the contrary, this bug is an example of making real code more efficient,
> just inappropriately because of the special status of char arrays.  We
> really don't want to have to assume that any random object can invisibly
> change type, as that would make type-based optimizations pretty useless.

In this case?  Really?  What real well-defined code would be pessimized by
disabling this transformation in the case of POD types?

> As far as I know people always use char arrays for placement new anyway; at
> least all the examples I've ever seen do.

I'm not really sure how, given that objects must be aligned.  We don't really
know how much code this transformation breaks, but I do know that it breaks in
ways that are hard to diagnose: in the Java example a function silently falls
through to whatever happens to follow it.

How about a compromise?  Make this optimization respect -fno-strict-aliasing. 
People already expect that option to disable type-based optimizations.

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[hubicka at ucw dot cz]

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

--- Comment #12 from Jan Hubicka <hubicka at ucw dot cz> ---
> (In reply to Jan Hubicka from comment #4)
> > Mine, probably 4.9 regression, too.
> 
> It is, and Jonathan Wakely's earlier reduction exposes it on 4.9 too.
> 
> (In reply to Jan Hubicka from comment #6)
> > Can you, please, double check that it fixes the Java issues?
> 
> With 4.9.0, for me, IcedTea reliably hangs during the build process. I hadn't
> investigated the problem at all, but with 4.9.0 plus your patch, it builds
> successfully.
> 
> What I had looked into was a segmentation fault in Qt
> (https://bugreports.qt-project.org/browse/QTBUG-38733) and Chromium, both using
> WebKit, also because of this. Chromium is still building, but for Qt, I can
> confirm it is also fixed by your patch.

Thank you,
I think the patch (as it is, modulo the reversed comment) is safe -
per Jason's comments we may make it stronger, but it won't win much: we are
only
interested in tracking types with vtable pointer, nothing else at the moment.

Assuming that any type can change at any time would really disable pretty much
all of the type based devirtualization - not just the case we are seeing, as
the
compiler would have to prove that there is no vtable store in between
definition
and apperance of the polymorphic call. We have logic for that, but it is not
particularly strong: alias analysis will always say yes on any external
function call,
for instance.

We make pretty strong assumptions here for years, so I hope there will be no
additional surprises.  I am still travelling, but will go ahead with it on
monday if there are no other problems found.

Honza

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[hubicka at ucw dot cz]

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

--- Comment #13 from Jan Hubicka <hubicka at ucw dot cz> ---
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60965
> 
> --- Comment #11 from Andrew Haley <aph at gcc dot gnu.org> ---
> (In reply to Jason Merrill from comment #9)
> > (In reply to Andrew Haley from comment #8)
> > > While it's true that we can play hardball on this one by insisting that only
> > > char arrays should be used with placement new, it wouldn't really do any
> > > good.  I don't think it would make any real-world code more efficient.
> > 
> > On the contrary, this bug is an example of making real code more efficient,
> > just inappropriately because of the special status of char arrays.  We
> > really don't want to have to assume that any random object can invisibly
> > change type, as that would make type-based optimizations pretty useless.
> 
> In this case?  Really?  What real well-defined code would be pessimized by
> disabling this transformation in the case of POD types?

Note that I do intend to disable it for all POD types for now (both at 4.9 and
4.10, at the proposed patch does).  We may revisit it for 4.10 later, but I do
not expect this is giong to cost too much of optimization; basically it will
only lose in paths where there is call of virtual pointer of one derived type
but we know that the instance is of incompatible derived type.  These cases are
harmful, since inliner & IPA code will agressively inline and optimize along
those provably impossible paths, but it is not _that_ serious.

What matters currently is that types with vtbl pointer are not changing
randomly.

Note that there is -fno-devirtualize as workaround in 4.9

Thank you!
Honza

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[hubicka at gcc dot gnu.org]

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

--- Comment #15 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Author: hubicka
Date: Mon May  5 19:40:34 2014
New Revision: 210079

URL: http://gcc.gnu.org/viewcvs?rev=210079&root=gcc&view=rev
Log:
    PR ipa/60965
    * g++.dg/ipa/devirt-31.C: New testcase.
    * g++.dg/ipa/devirt-11.C: Adjust testcase.
    * ipa-devirt.c (get_class_context): Allow POD to change to non-POD.

Added:
    branches/gcc-4_9-branch/gcc/testsuite/g++.dg/ipa/devirt-31.C
Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/ipa-devirt.c
    branches/gcc-4_9-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_9-branch/gcc/testsuite/g++.dg/ipa/devirt-11.C

[Bug ipa/60965] [4.10 Regression] IPA: Devirtualization versus placement new

[hubicka at gcc dot gnu.org]

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

--- Comment #16 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Author: hubicka
Date: Mon May  5 23:27:40 2014
New Revision: 210086

URL: http://gcc.gnu.org/viewcvs?rev=210086&root=gcc&view=rev
Log:

    PR ipa/60965
    * ipa-devirt.c (get_class_context): Allow POD to change to non-POD.
    * g++.dg/ipa/devirt-32.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/ipa/devirt-32.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ipa-devirt.c
    trunk/gcc/testsuite/ChangeLog