Patchwork [RFC] Bare bones of virtual call tracking

login
register
mail settings
Submitter Jan Hubicka
Date Aug. 15, 2013, 4:17 p.m.
Message ID <20130815161710.GA26705@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/267403/
State New
Headers show

Comments

Jan Hubicka - Aug. 15, 2013, 4:17 p.m.
> On 08/14/2013 02:14 AM, Jan Hubicka wrote:
> >As a temporary hack I suppose I can rely on assembler name of virtual table
> >to be unique for each templated class?
> 
> Actually, that seems like a fine solution for devirtualization; just
> compare the mangled name of the vtable to establish type identity.
OK,
does this seem to make sense?  I checked that it gets rid of my
false ODR violation warnings (I disabled the code for types not
having virtual tables).

So if it looks OK, I would like to go ahead with this patch.
(I am testing it now in isolation at x86_64-linux).

Honza
Xinliang David Li - Aug. 15, 2013, 4:34 p.m.
Some suggestions for the future:

1) add summary info in the odr dump -- i.e. for each node, dump the
number of direct bases, direct subtypes, number of all bases, all
subtypes;
2) add statistics dump -- average size of  a hierarchy subgraph

3) Dump the graph using top-order -- starting from roots of each sub-graph;
4) Add VCG dump per-hierarchy.

thanks,

David


On Thu, Aug 15, 2013 at 9:17 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On 08/14/2013 02:14 AM, Jan Hubicka wrote:
>> >As a temporary hack I suppose I can rely on assembler name of virtual table
>> >to be unique for each templated class?
>>
>> Actually, that seems like a fine solution for devirtualization; just
>> compare the mangled name of the vtable to establish type identity.
> OK,
> does this seem to make sense?  I checked that it gets rid of my
> false ODR violation warnings (I disabled the code for types not
> having virtual tables).
>
> So if it looks OK, I would like to go ahead with this patch.
> (I am testing it now in isolation at x86_64-linux).
>
> Honza
>
> Index: tree.c
> ===================================================================
> --- tree.c      (revision 201764)
> +++ tree.c      (working copy)
> @@ -11833,15 +11833,15 @@ types_same_for_odr (tree type1, tree typ
>    if (type1 == type2)
>      return true;
>
> -  /* If types are not structuraly same, do not bother to contnue.
> -     Match in the remainder of code would mean ODR violation.  */
> -  if (!types_compatible_p (type1, type2))
> -    return false;
> -
> +  /* Without LTO main variants of types are unique.  */
>  #ifndef ENABLE_CHECKING
>    if (!in_lto_p)
>      return false;
>  #endif
> +   /* If types are not structuraly same, do not bother to contnue.
> +      Match in the remainder of code would mean ODR violation.  */
> +   if (!types_compatible_p (type1, type2))
> +     return false;
>
>    /* Check for anonymous namespaces. Those have !TREE_PUBLIC
>       on the corresponding TYPE_STUB_DECL.  */
> @@ -11852,6 +11852,34 @@ types_same_for_odr (tree type1, tree typ
>           || !TREE_PUBLIC (TYPE_STUB_DECL (type2))))
>      return false;
>
> +  /* When assembler name of virtual table is available, it is
> +     easy to compare types for equivalence.
> +     FIXME: the code bellow consider all instantiations of the same
> +     template to have same name.  This is because we have no access
> +     to template parameters.
> +     To avoid false positives that may lead to wrong devirtualizations,
> +     compoare also representative virtual tables.
> +     We can still return false positive positives for types without
> +     virtual tables, but for the moment we do not care.  */
> +  if (TYPE_BINFO (type1) && TYPE_BINFO (type2)
> +      && BINFO_VTABLE (TYPE_BINFO (type1))
> +      && BINFO_VTABLE (TYPE_BINFO (type2)))
> +    {
> +      tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
> +      tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
> +
> +      if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
> +       {
> +         if (TREE_CODE (v2) != POINTER_PLUS_EXPR
> +             || !operand_equal_p (TREE_OPERAND (v1, 1),
> +                                  TREE_OPERAND (v2, 1), 0))
> +           return false;
> +         v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
> +         v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
> +       }
> +      return DECL_ASSEMBLER_NAME (v1) == DECL_ASSEMBLER_NAME (v2);
> +    }
> +
>    if (!TYPE_NAME (type1))
>      return false;
>    if (!decls_same_for_odr (TYPE_NAME (type1), TYPE_NAME (type2)))
Jan Hubicka - Aug. 15, 2013, 4:46 p.m.
> Some suggestions for the future:
> 
> 1) add summary info in the odr dump -- i.e. for each node, dump the
> number of direct bases, direct subtypes, number of all bases, all
> subtypes;

OK, can add that.
> 2) add statistics dump -- average size of  a hierarchy subgraph
> 
> 3) Dump the graph using top-order -- starting from roots of each sub-graph;

This is already done - dumping recursively dumps subtypes and we dump only
types without bases.  Problem is that with multiple inheritance types appear twice.

> 4) Add VCG dump per-hierarchy.

Hmm, may be nice - firefox definitely has huge graph.

Currently my type graph is very partial - I have no nodes for types without
virtual methods at all.  This is because types_same_for_odr is not able to give
exact answer (it gives false positives for templates).  Hope to solve it
incrementaly.

I found many bugs at random places, so will push those out first and send
updated patch.

Honza
Xinliang David Li - Aug. 15, 2013, 5:07 p.m.
On Thu, Aug 15, 2013 at 9:46 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Some suggestions for the future:
>>
>> 1) add summary info in the odr dump -- i.e. for each node, dump the
>> number of direct bases, direct subtypes, number of all bases, all
>> subtypes;
>
> OK, can add that.
>> 2) add statistics dump -- average size of  a hierarchy subgraph
>>
>> 3) Dump the graph using top-order -- starting from roots of each sub-graph;
>
> This is already done - dumping recursively dumps subtypes and we dump only
> types without bases.  Problem is that with multiple inheritance types appear twice.
>
>> 4) Add VCG dump per-hierarchy.
>
> Hmm, may be nice - firefox definitely has huge graph.

That is why the graph should be split up and dumped independently. If
the design is such that all types are derived from one common root
class we have a problem here :)

>
> Currently my type graph is very partial - I have no nodes for types without
> virtual methods at all.

Those are not probably interesting anyways.

David

> This is because types_same_for_odr is not able to give
> exact answer (it gives false positives for templates).  Hope to solve it
> incrementaly.
>
> I found many bugs at random places, so will push those out first and send
> updated patch.
>
> Honza
Jan Hubicka - Aug. 15, 2013, 5:15 p.m.
> On Thu, Aug 15, 2013 at 9:46 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> Some suggestions for the future:
> >>
> >> 1) add summary info in the odr dump -- i.e. for each node, dump the
> >> number of direct bases, direct subtypes, number of all bases, all
> >> subtypes;
> >
> > OK, can add that.
> >> 2) add statistics dump -- average size of  a hierarchy subgraph
> >>
> >> 3) Dump the graph using top-order -- starting from roots of each sub-graph;
> >
> > This is already done - dumping recursively dumps subtypes and we dump only
> > types without bases.  Problem is that with multiple inheritance types appear twice.
> >
> >> 4) Add VCG dump per-hierarchy.
> >
> > Hmm, may be nice - firefox definitely has huge graph.
> 
> That is why the graph should be split up and dumped independently. If
> the design is such that all types are derived from one common root
> class we have a problem here :)

Hehe, for now the main problem is to locate the dump itself in hypergigantic
.cgraph dump. I really ought to split that dump into more files...

Honza
Jan Hubicka - Aug. 15, 2013, 5:21 p.m.
> > Currently my type graph is very partial - I have no nodes for types without
> > virtual methods at all.
> 
> Those are not probably interesting anyways.
Forgot to mention, I think in longer term we can use it to maintain more of C++
type based aliasing rules.  Currently we unify canonical types only based on
memory layout, since that is safe.

If we marked types that follows ODR rule by C++ FE, then we can do odr_type
based matching for canonical type unless there is non-ODR type of same layout
originating from other language - then we probably need to make it to alias
with everything...

Because canonical type construction is incremental, I am not really sure
how to decide if there is ODR-non-ODR conflict.  But I did not really look
in detail anyway.

Honza

Patch

Index: tree.c
===================================================================
--- tree.c	(revision 201764)
+++ tree.c	(working copy)
@@ -11833,15 +11833,15 @@  types_same_for_odr (tree type1, tree typ
   if (type1 == type2)
     return true;
 
-  /* If types are not structuraly same, do not bother to contnue.
-     Match in the remainder of code would mean ODR violation.  */
-  if (!types_compatible_p (type1, type2))
-    return false;
-
+  /* Without LTO main variants of types are unique.  */
 #ifndef ENABLE_CHECKING
   if (!in_lto_p)
     return false;
 #endif
+   /* If types are not structuraly same, do not bother to contnue.
+      Match in the remainder of code would mean ODR violation.  */
+   if (!types_compatible_p (type1, type2))
+     return false;
 
   /* Check for anonymous namespaces. Those have !TREE_PUBLIC
      on the corresponding TYPE_STUB_DECL.  */
@@ -11852,6 +11852,34 @@  types_same_for_odr (tree type1, tree typ
 	  || !TREE_PUBLIC (TYPE_STUB_DECL (type2))))
     return false;
 
+  /* When assembler name of virtual table is available, it is
+     easy to compare types for equivalence.
+     FIXME: the code bellow consider all instantiations of the same
+     template to have same name.  This is because we have no access
+     to template parameters.
+     To avoid false positives that may lead to wrong devirtualizations,
+     compoare also representative virtual tables.
+     We can still return false positive positives for types without
+     virtual tables, but for the moment we do not care.  */
+  if (TYPE_BINFO (type1) && TYPE_BINFO (type2)
+      && BINFO_VTABLE (TYPE_BINFO (type1))
+      && BINFO_VTABLE (TYPE_BINFO (type2)))
+    {
+      tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
+      tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
+
+      if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
+	{
+	  if (TREE_CODE (v2) != POINTER_PLUS_EXPR
+	      || !operand_equal_p (TREE_OPERAND (v1, 1),
+				   TREE_OPERAND (v2, 1), 0))
+	    return false;
+	  v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
+	  v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
+	}
+      return DECL_ASSEMBLER_NAME (v1) == DECL_ASSEMBLER_NAME (v2);
+    }
+
   if (!TYPE_NAME (type1))
     return false;
   if (!decls_same_for_odr (TYPE_NAME (type1), TYPE_NAME (type2)))