RFA: New ipa-devirt PATCH for c++/58678 (devirt vs. KDE)

This patch fixes the latest 58678 testcase by avoiding speculative 
devirtualization to the destructor of an abstract class, which can never 
succeed: you can't create an object of an abstract class, so the pointer 
must point to an object of a derived class, and the derived class 
necessarily has its own destructor.  Other virtual member functions of 
an abstract class are OK for devirtualization: the destructor is the 
only virtual function that is always overridden in every class.

We could also detect an abstract class by searching through the vtable 
for __cxa_pure_virtual, but I figured it was easy enough for the front 
end to set a flag on the BINFO.

Tested x86_64-pc-linux-gnu.  OK for trunk?

> This patch fixes the latest 58678 testcase by avoiding speculative
> devirtualization to the destructor of an abstract class, which can
> never succeed: you can't create an object of an abstract class, so
> the pointer must point to an object of a derived class, and the
> derived class necessarily has its own destructor.  Other virtual
> member functions of an abstract class are OK for devirtualization:
> the destructor is the only virtual function that is always
> overridden in every class.]
> 
> We could also detect an abstract class by searching through the
> vtable for __cxa_pure_virtual, but I figured it was easy enough for
> the front end to set a flag on the BINFO.
> 
> Tested x86_64-pc-linux-gnu.  OK for trunk?

> commit b64f52066f3f4cdc9d5a30e2d48aaf6dd5efd3d4
> Author: Jason Merrill <jason@redhat.com>
> Date:   Wed Mar 5 11:35:07 2014 -0500
> 
>     	PR c++/58678
>     gcc/
>     	* tree.h (BINFO_ABSTRACT_P): New.
>     	* ipa-devirt.c (abstract_class_dtor_p): New.
>     	(likely_target_p): Check it.

I think the abstract classes probably shuld never be considered in the type
inheritance graph walk as possible instances. That is we probably want to test
them in record_targets_from_bases, possible_polymorphic_call_targets and
record_target_from_binfo and simply never call maybe_record_node when the type
considered is abstract without concluding that list is incomplete as we do when
method can not be referred.  If the type has derivations that do not override
something, we will record the methods when walking derrived type, so i do not
think we need to make difference in between destructor and other type.

We also want to sanity check that after get_class_context the outer_type
is not abstract or maybe_derived_type is set. 
>     gcc/cp/
>     	* search.c (get_pure_virtuals): Set BINFO_ABSTRACT_P.
>     	* tree.c (copy_binfo): Copy it.

You need to also save and restre the flag in LTO streaming.

I can prepare patch tomorrow if you preffer, thanks for looking into this!
Honza
> 
> diff --git a/gcc/cp/search.c b/gcc/cp/search.c
> index c3eed90..7a3ea4b 100644
> --- a/gcc/cp/search.c
> +++ b/gcc/cp/search.c
> @@ -2115,6 +2115,8 @@ get_pure_virtuals (tree type)
>       which it is a primary base will contain vtable entries for the
>       pure virtuals in the base class.  */
>    dfs_walk_once (TYPE_BINFO (type), NULL, dfs_get_pure_virtuals, type);
> +  if (CLASSTYPE_PURE_VIRTUALS (type))
> +    BINFO_ABSTRACT_P (TYPE_BINFO (type)) = true;
>  }
>  
>  /* Debug info for C++ classes can get very large; try to avoid
> diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c
> index 5567253..3836e16 100644
> --- a/gcc/cp/tree.c
> +++ b/gcc/cp/tree.c
> @@ -1554,6 +1554,7 @@ copy_binfo (tree binfo, tree type, tree t, tree *igo_prev, int virt)
>  
>        BINFO_OFFSET (new_binfo) = BINFO_OFFSET (binfo);
>        BINFO_VIRTUALS (new_binfo) = BINFO_VIRTUALS (binfo);
> +      BINFO_ABSTRACT_P (new_binfo) = BINFO_ABSTRACT_P (binfo);
>  
>        /* We do not need to copy the accesses, as they are read only.  */
>        BINFO_BASE_ACCESSES (new_binfo) = BINFO_BASE_ACCESSES (binfo);
> diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c
> index 2f84f17..3f4a1d5 100644
> --- a/gcc/ipa-devirt.c
> +++ b/gcc/ipa-devirt.c
> @@ -1674,6 +1674,19 @@ update_type_inheritance_graph (void)
>    timevar_pop (TV_IPA_INHERITANCE);
>  }
>  
> +/* A destructor for an abstract class is not likely because it can never be
> +   called through the vtable; any actual object will have a derived type,
> +   which will have its own destructor.  */
> +
> +static bool
> +abstract_class_dtor_p (tree fn)
> +{
> +  if (!DECL_CXX_DESTRUCTOR_P (fn))
> +    return false;
> +  tree type = DECL_CONTEXT (fn);
> +  tree binfo = TYPE_BINFO (type);
> +  return BINFO_ABSTRACT_P (binfo);
> +}
>  
>  /* Return true if N looks like likely target of a polymorphic call.
>     Rule out cxa_pure_virtual, noreturns, function declared cold and
> @@ -1694,6 +1707,8 @@ likely_target_p (struct cgraph_node *n)
>      return false;
>    if (n->frequency < NODE_FREQUENCY_NORMAL)
>      return false;
> +  if (abstract_class_dtor_p (n->decl))
> +    return false;
>    return true;
>  }
>  
> diff --git a/gcc/testsuite/g++.dg/ipa/devirt-30.C b/gcc/testsuite/g++.dg/ipa/devirt-30.C
> new file mode 100644
> index 0000000..c4ac694
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/ipa/devirt-30.C
> @@ -0,0 +1,25 @@
> +// PR c++/58678
> +// { dg-options "-O3 -fdump-ipa-devirt" }
> +
> +// We shouldn't speculatively devirtualize to ~B because B is an abstract
> +// class; any actual object passed to f will be of some derived class which
> +// has its own destructor.
> +
> +struct A
> +{
> +  virtual void f() = 0;
> +  virtual ~A();
> +};
> +
> +struct B : A
> +{
> +  virtual ~B() {}
> +};
> +
> +void f(B* b)
> +{
> +  delete b;
> +}
> +
> +// { dg-final { scan-ipa-dump-not "Speculatively devirtualizing" "devirt" } }
> +// { dg-final { cleanup-ipa-dump "devirt" } }
> diff --git a/gcc/tree-core.h b/gcc/tree-core.h
> index e548a0d..708a8ab 100644
> --- a/gcc/tree-core.h
> +++ b/gcc/tree-core.h
> @@ -786,6 +786,9 @@ struct GTY(()) tree_base {
>         PREDICT_EXPR_OUTCOME in
>  	   PREDICT_EXPR
>  
> +       BINFO_ABSTRACT_P in
> +           TREE_BINFO
> +
>     static_flag:
>  
>         TREE_STATIC in
> diff --git a/gcc/tree.h b/gcc/tree.h
> index 0dc8d0d..01e23ec 100644
> --- a/gcc/tree.h
> +++ b/gcc/tree.h
> @@ -1804,6 +1804,9 @@ extern void protected_set_expr_location (tree, location_t);
>  /* Nonzero means that the derivation chain is via a `virtual' declaration.  */
>  #define BINFO_VIRTUAL_P(NODE) (TREE_BINFO_CHECK (NODE)->base.static_flag)
>  
> +/* Nonzero means that the base is an abstract class.  */
> +#define BINFO_ABSTRACT_P(NODE) (TREE_BINFO_CHECK (NODE)->base.addressable_flag)
> +
>  /* Flags for language dependent use.  */
>  #define BINFO_MARKED(NODE) TREE_LANG_FLAG_0 (TREE_BINFO_CHECK (NODE))
>  #define BINFO_FLAG_1(NODE) TREE_LANG_FLAG_1 (TREE_BINFO_CHECK (NODE))

> > This patch fixes the latest 58678 testcase by avoiding speculative
> > devirtualization to the destructor of an abstract class, which can
> > never succeed: you can't create an object of an abstract class, so
> > the pointer must point to an object of a derived class, and the
> > derived class necessarily has its own destructor.  Other virtual
> > member functions of an abstract class are OK for devirtualization:
> > the destructor is the only virtual function that is always
> > overridden in every class.]
> > 
> > We could also detect an abstract class by searching through the
> > vtable for __cxa_pure_virtual, but I figured it was easy enough for
> > the front end to set a flag on the BINFO.
> > 
> > Tested x86_64-pc-linux-gnu.  OK for trunk?
> 
> > commit b64f52066f3f4cdc9d5a30e2d48aaf6dd5efd3d4
> > Author: Jason Merrill <jason@redhat.com>
> > Date:   Wed Mar 5 11:35:07 2014 -0500
> > 
> >     	PR c++/58678
> >     gcc/
> >     	* tree.h (BINFO_ABSTRACT_P): New.
> >     	* ipa-devirt.c (abstract_class_dtor_p): New.
> >     	(likely_target_p): Check it.
> 
> I think the abstract classes probably shuld never be considered in the type
> inheritance graph walk as possible instances. That is we probably want to test
> them in record_targets_from_bases, possible_polymorphic_call_targets and
> record_target_from_binfo and simply never call maybe_record_node when the type
> considered is abstract without concluding that list is incomplete as we do when
> method can not be referred.  If the type has derivations that do not override
> something, we will record the methods when walking derrived type, so i do not
> think we need to make difference in between destructor and other type.
> 
> We also want to sanity check that after get_class_context the outer_type
> is not abstract or maybe_derived_type is set. 
> >     gcc/cp/
> >     	* search.c (get_pure_virtuals): Set BINFO_ABSTRACT_P.
> >     	* tree.c (copy_binfo): Copy it.
> 
> You need to also save and restre the flag in LTO streaming.
> 
> I can prepare patch tomorrow if you preffer, thanks for looking into this!

BTW it would conserve little bit of memory & streaming if we also stripped DECL_INITIAL
of those vtables. They should never be needed. (We still need DECL_VTABLE to be able to
work out ODR equivalence, since the types must be in type inheritance tree)

Honza

On Wed, Mar 05, 2014 at 07:40:06PM +0100, Jan Hubicka wrote:
> >     gcc/cp/
> >     	* search.c (get_pure_virtuals): Set BINFO_ABSTRACT_P.
> >     	* tree.c (copy_binfo): Copy it.
> 
> You need to also save and restre the flag in LTO streaming.
> I can prepare patch tomorrow if you preffer, thanks for looking into this!

It is TREE_ADDRESSABLE, isn't it streamed already?

> > --- a/gcc/tree.h
> > +++ b/gcc/tree.h
> > @@ -1804,6 +1804,9 @@ extern void protected_set_expr_location (tree, location_t);
> >  /* Nonzero means that the derivation chain is via a `virtual' declaration.  */
> >  #define BINFO_VIRTUAL_P(NODE) (TREE_BINFO_CHECK (NODE)->base.static_flag)
> >  
> > +/* Nonzero means that the base is an abstract class.  */
> > +#define BINFO_ABSTRACT_P(NODE) (TREE_BINFO_CHECK (NODE)->base.addressable_flag)
> > +
> >  /* Flags for language dependent use.  */
> >  #define BINFO_MARKED(NODE) TREE_LANG_FLAG_0 (TREE_BINFO_CHECK (NODE))
> >  #define BINFO_FLAG_1(NODE) TREE_LANG_FLAG_1 (TREE_BINFO_CHECK (NODE))

	Jakub

On 03/05/2014 01:40 PM, Jan Hubicka wrote:
> I think the abstract classes probably should never be considered in the type
> inheritance graph walk as possible instances. That is we probably want to test
> them in record_targets_from_bases, possible_polymorphic_call_targets and
> record_target_from_binfo and simply never call maybe_record_node when the type
> considered is abstract without concluding that list is incomplete as we do when
> method can not be referred.  If the type has derivations that do not override
> something, we will record the methods when walking derived type, so i do not
> think we need to make difference in between destructor and other type.

Hmm, if we see

struct A
{
   virtual void f() = 0;
   virtual void g() { };
};

void f(A* a)
{
   a->g();
}

and ignore A because it's abstract, then we don't speculatively 
devirtualize the call to g, which we might want to do; it might be the 
case that most derived classes don't override g.  The destructor is 
special because all derived classes must override it.

> I can prepare patch tomorrow if you prefer, thanks for looking into this!

Sounds good, thanks.

Jason

> This patch fixes the latest 58678 testcase by avoiding speculative
> devirtualization to the destructor of an abstract class, which can
> never succeed: you can't create an object of an abstract class, so
> the pointer must point to an object of a derived class, and the
> derived class necessarily has its own destructor.  Other virtual
> member functions of an abstract class are OK for devirtualization:
> the destructor is the only virtual function that is always
> overridden in every class.
> 
> We could also detect an abstract class by searching through the
> vtable for __cxa_pure_virtual, but I figured it was easy enough for
> the front end to set a flag on the BINFO.
> 
> Tested x86_64-pc-linux-gnu.  OK for trunk?

> commit b64f52066f3f4cdc9d5a30e2d48aaf6dd5efd3d4
> Author: Jason Merrill <jason@redhat.com>
> Date:   Wed Mar 5 11:35:07 2014 -0500
> 
>     	PR c++/58678
>     gcc/
>     	* tree.h (BINFO_ABSTRACT_P): New.
>     	* ipa-devirt.c (abstract_class_dtor_p): New.
>     	(likely_target_p): Check it.
>     gcc/cp/
>     	* search.c (get_pure_virtuals): Set BINFO_ABSTRACT_P.
>     	* tree.c (copy_binfo): Copy it.

Jason, I was looking into this and I think I have patch that works.  I would
just like to verify I inderstnad things right.  First thing I implemented is to
consistently skip dtors of abstract classes as per the comment in
abstract_class_dtor_p there is no way to call those by virtual table pointer.
Unlike your patch it will i.e. enable better unreachable code removal since
they will not appear in possible target lists of polymorphic calls.

The second change I did is to move methods that are reachable only
via abstract class into the part of list that is in construction,
since obviously we do not have instances of these classes.
I do not think it is too important (and it needs bit of changes in the
walk), but it is better to be correct here so we avoid further problems
where the ipa-devirt digs out target that is in fact not possible.

What I would like to verify with you shtat I also changed walk when looking
for destructors to not consider types in construction. I believe there is no way
to get destructor call via construction vtable as we always know the type.
Is that right?

Honza

> > This patch fixes the latest 58678 testcase by avoiding speculative
> > devirtualization to the destructor of an abstract class, which can
> > never succeed: you can't create an object of an abstract class, so
> > the pointer must point to an object of a derived class, and the
> > derived class necessarily has its own destructor.  Other virtual
> > member functions of an abstract class are OK for devirtualization:
> > the destructor is the only virtual function that is always
> > overridden in every class.
> > 
> > We could also detect an abstract class by searching through the
> > vtable for __cxa_pure_virtual, but I figured it was easy enough for
> > the front end to set a flag on the BINFO.
> > 
> > Tested x86_64-pc-linux-gnu.  OK for trunk?
> 
> > commit b64f52066f3f4cdc9d5a30e2d48aaf6dd5efd3d4
> > Author: Jason Merrill <jason@redhat.com>
> > Date:   Wed Mar 5 11:35:07 2014 -0500
> > 
> >     	PR c++/58678
> >     gcc/
> >     	* tree.h (BINFO_ABSTRACT_P): New.
> >     	* ipa-devirt.c (abstract_class_dtor_p): New.
> >     	(likely_target_p): Check it.
> >     gcc/cp/
> >     	* search.c (get_pure_virtuals): Set BINFO_ABSTRACT_P.
> >     	* tree.c (copy_binfo): Copy it.

Jason, also if abstract_class_dtor_p functions are never called via vtables, is there
reason for C++ FE to put them there? I understand that there is a slot in vtable initializer
for them, but things would go smoother if it was initialized to NULL or some other marker
different from cxa_pure_virtual.  Then gimple-fold will already substitute it for
builtin_unreachable and they will get ignored during the ipa-devirt's walks.

Honza

On 03/11/2014 05:08 PM, Jan Hubicka wrote:
> Jason, I was looking into this and I think I have patch that works.  I would
> just like to verify I inderstnad things right.  First thing I implemented is to
> consistently skip dtors of abstract classes as per the comment in
> abstract_class_dtor_p there is no way to call those by virtual table pointer.
> Unlike your patch it will i.e. enable better unreachable code removal since
> they will not appear in possible target lists of polymorphic calls.

Makes sense.

> The second change I did is to move methods that are reachable only
> via abstract class into the part of list that is in construction,
> since obviously we do not have instances of these classes.

I'm not sure how you would tell that a method that is reachable only via 
abstract class; a derived class doesn't have to override methods other 
than the destructor, so we could get the abstract class method for an 
object of a derived class.

> What I would like to verify with you shtat I also changed walk when looking
> for destructors to not consider types in construction. I believe there is no way
> to get destructor call via construction vtable as we always know the type.
> Is that right?

I guess it would be possible to get the abstract destructor via 
construction vtable if someone deletes the object while it's being 
constructed.  But surely that's undefined behavior anyway.

> also if abstract_class_dtor_p functions are never called via vtables, is there
> reason for C++ FE to put them there? I understand that there is a slot in vtable initializer
> for them, but things would go smoother if it was initialized to NULL or some other marker
> different from cxa_pure_virtual.  Then gimple-fold will already substitute it for
> builtin_unreachable and they will get ignored during the ipa-devirt's walks.

Hmm, interesting idea.  Shall I implement that?

Jason

> On 03/11/2014 05:08 PM, Jan Hubicka wrote:
> >Jason, I was looking into this and I think I have patch that works.  I would
> >just like to verify I inderstnad things right.  First thing I implemented is to
> >consistently skip dtors of abstract classes as per the comment in
> >abstract_class_dtor_p there is no way to call those by virtual table pointer.
> >Unlike your patch it will i.e. enable better unreachable code removal since
> >they will not appear in possible target lists of polymorphic calls.
> 
> Makes sense.
> 
> >The second change I did is to move methods that are reachable only
> >via abstract class into the part of list that is in construction,
> >since obviously we do not have instances of these classes.
> 
> I'm not sure how you would tell that a method that is reachable only
> via abstract class; a derived class doesn't have to override methods
> other than the destructor, so we could get the abstract class method
> for an object of a derived class.

Yep, this can apply only to anonymous namespace types where we know the
derivations. So it is not a big win.
> 
> >What I would like to verify with you shtat I also changed walk when looking
> >for destructors to not consider types in construction. I believe there is no way
> >to get destructor call via construction vtable as we always know the type.
> >Is that right?
> 
> I guess it would be possible to get the abstract destructor via
> construction vtable if someone deletes the object while it's being
> constructed.  But surely that's undefined behavior anyway.
> 
> >also if abstract_class_dtor_p functions are never called via vtables, is there
> >reason for C++ FE to put them there? I understand that there is a slot in vtable initializer
> >for them, but things would go smoother if it was initialized to NULL or some other marker
> >different from cxa_pure_virtual.  Then gimple-fold will already substitute it for
> >builtin_unreachable and they will get ignored during the ipa-devirt's walks.
> 
> Hmm, interesting idea.  Shall I implement that?

Less we have in the vtables, the better, so if you can implement this, it would be
great.

Honza
> 
> Jason