| Message ID | 20130815161710.GA26705@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
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)))
> 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
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
> 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
> > 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
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)))