Hi, this patch makes inheritance graph builder to work on LTO. Nothing but ODR violation warnings and dump file is produced, yet.
The main change is to make types_same_for_odr and ODR hasher to use assembler name of virtual tables of the type (if present) to establish type equality. This is result of discussion with Jason at http://gcc.gnu.org/ml/gcc-patches/2013-08/msg00826.html Jason, does the implemenetation seem sane? Multiple tree types can now be representations of single ODR type. There is new add_type_duplicate that output warnings on obvious mismatches and records variant in odr_type->types array. Those are used for debug output (it may be interesting to get more of the unified by Richard's merging). Trickier part is the code that merges BINFOs of ODR equivalent types. This is important since we do not want to keep external vtables around when internal exists (external version may refer to external static methods that are internal to our LTO unit). With ODR violations it may lead to wrong devirtualization, but that is the case previously anyway. Bootstrapped/regtested x86_64-linux, OK? Honza * Makefile.in (ipa-devirt.o): Add dependency on diagnostic.h * ipa-devirt.c: Include diganostic.h (odr_type_d): Add types and types_set. (hash_type_name): Work for types with vtables during LTO. (odr_hasher::remove): Fix comment; destroy types_set. (add_type_duplicate): New function, (get_odr_type): Use it. (dump_type_inheritance_graph): Dump type duplicates. * ipa.c (symtab_remove_unreachable_nodes): Build type inheritance graph. * tree.c (types_same_for_odr): Give exact answers on types with virtual tables. Index: Makefile.in =================================================================== *** Makefile.in (revision 201836) --- Makefile.in (working copy) *************** ipa.o : ipa.c $(CONFIG_H) $(SYSTEM_H) co *** 2948,2954 **** $(LTO_STREAMER_H) $(DATA_STREAMER_H) ipa-devirt.o : ipa-devirt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \ $(GIMPLE_H) $(TARGET_H) $(GGC_H) pointer-set.h \ ! $(IPA_UTILS_H) $(HASH_TABLE_H) ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \ $(TREE_FLOW_H) $(TM_H) $(TREE_PASS_H) $(FLAGS_H) $(TREE_H) \ --- 2948,2954 ---- $(LTO_STREAMER_H) $(DATA_STREAMER_H) ipa-devirt.o : ipa-devirt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \ $(GIMPLE_H) $(TARGET_H) $(GGC_H) pointer-set.h \ ! $(IPA_UTILS_H) $(HASH_TABLE_H) $(DIAGNOSTIC_H) ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \ $(TREE_FLOW_H) $(TM_H) $(TREE_PASS_H) $(FLAGS_H) $(TREE_H) \ Index: ipa-devirt.c =================================================================== *** ipa-devirt.c (revision 201836) --- ipa-devirt.c (working copy) *************** along with GCC; see the file COPYING3. *** 116,121 **** --- 116,122 ---- #include "tree-pretty-print.h" #include "ipa-utils.h" #include "gimple.h" + #include "diagnostic.h" /* The node of type inheritance graph. For each type unique in One Defintion Rule (ODR) sense, we produce one node linking all *************** along with GCC; see the file COPYING3. *** 123,136 **** struct GTY(()) odr_type_d { - /* Unique ID indexing the type in odr_types array. */ - int id; /* leader type. */ tree type; /* All bases. */ vec<odr_type> GTY((skip)) bases; /* All derrived types with virtual methods seen in unit. */ vec<odr_type> GTY((skip)) derived_types; /* Is it in anonymous namespace? */ bool anonymous_namespace; }; --- 124,143 ---- struct GTY(()) odr_type_d { /* leader type. */ tree type; /* All bases. */ vec<odr_type> GTY((skip)) bases; /* All derrived types with virtual methods seen in unit. */ vec<odr_type> GTY((skip)) derived_types; + + /* All equivalent types, if more than one. */ + vec<tree, va_gc> *types; + /* Set of all equivalent types, if NON-NULL. */ + pointer_set_t * GTY((skip)) types_set; + + /* Unique ID indexing the type in odr_types array. */ + int id; /* Is it in anonymous namespace? */ bool anonymous_namespace; }; *************** hash_type_name (tree t) *** 172,177 **** --- 179,204 ---- if (type_in_anonymous_namespace_p (t)) return htab_hash_pointer (t); + /* For polymorphic types, we can simply hash the virtual table. */ + if (TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t))) + { + tree v = BINFO_VTABLE (TYPE_BINFO (t)); + hashval_t hash = 0; + + if (TREE_CODE (v) == POINTER_PLUS_EXPR) + { + hash = TREE_INT_CST_LOW (TREE_OPERAND (v, 1)); + v = TREE_OPERAND (TREE_OPERAND (v, 0), 0); + } + + v = DECL_ASSEMBLER_NAME (v); + #ifdef ENABLE_CHECKING + gcc_assert (!strchr (IDENTIFIER_POINTER (v), '.')); + #endif + hash = iterative_hash_hashval_t (hash, htab_hash_pointer (v)); + return hash; + } + /* Rest is not implemented yet. */ gcc_unreachable (); } *************** odr_hasher::hash (const value_type *odr_ *** 184,190 **** return hash_type_name (odr_type->type); } ! /* Compare types operations T1 and T2 and return true if they are equivalent. */ inline bool --- 211,217 ---- return hash_type_name (odr_type->type); } ! /* Compare types T1 and T2 and return true if they are equivalent. */ inline bool *************** odr_hasher::equal (const value_type *t1, *** 200,212 **** return types_same_for_odr (t1->type, t2); } ! /* Free a phi operation structure VP. */ inline void odr_hasher::remove (value_type *v) { v->bases.release (); v->derived_types.release (); ggc_free (v); } --- 227,241 ---- return types_same_for_odr (t1->type, t2); } ! /* Free ODR type V. */ inline void odr_hasher::remove (value_type *v) { v->bases.release (); v->derived_types.release (); + if (v->types_set) + pointer_set_destroy (v->types_set); ggc_free (v); } *************** static odr_hash_type odr_hash; *** 222,227 **** --- 251,382 ---- static GTY(()) vec <odr_type, va_gc> *odr_types_ptr; #define odr_types (*odr_types_ptr) + /* TYPE is equivalent to VAL by ODR, but its tree representation differs + from VAL->type. This may happen in LTO where tree merging did not merge + all variants of the same type. It may or may not mean the ODR violation. + Add it to the list of duplicates and warn on some violations. */ + + void + add_type_duplicate (odr_type val, tree type) + { + if (!val->types_set) + val->types_set = pointer_set_create (); + + /* See if this duplicate is new. */ + if (!pointer_set_insert (val->types_set, type)) + { + bool merge = true; + bool base_mismatch = false; + gcc_assert (in_lto_p); + vec_safe_push (val->types, type); + unsigned int i,j; + + /* First we compare memory layout. */ + if (!types_compatible_p (val->type, type)) + { + merge = false; + if (BINFO_VTABLE (TYPE_BINFO (val->type)) + && warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (type)), 0, + "type %qD violate one definition rule ", + type)) + inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)), + "the type of same name with different memory layout " + "defined in other compilation unit"); + debug_tree (BINFO_VTABLE (TYPE_BINFO (type))); + debug_tree (BINFO_VTABLE (TYPE_BINFO (val->type))); + if (cgraph_dump_file) + { + fprintf (cgraph_dump_file, "ODR violation or merging or ODR type bug?\n"); + + print_node (cgraph_dump_file, "", val->type, 0); + putc ('\n',cgraph_dump_file); + print_node (cgraph_dump_file, "", type, 0); + putc ('\n',cgraph_dump_file); + } + } + + /* Next sanity check that bases are the same. If not, we will end + up producing wrong answers. */ + for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++) + if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (TYPE_BINFO (type), i))) + { + odr_type base = get_odr_type + (BINFO_TYPE + (BINFO_BASE_BINFO (TYPE_BINFO (type), + i)), + true); + if (val->bases.length () <= j || val->bases[j] != base) + base_mismatch = true; + j++; + } + if (base_mismatch) + { + merge = false; + + if (warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (type)), 0, + "type %qD violate one definition rule ", + type)) + inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)), + "the inconsistent type of same name with different bases" + " (defined in other compilation unit)"); + if (cgraph_dump_file) + { + fprintf (cgraph_dump_file, "ODR bse violation or merging bug?\n"); + + print_node (cgraph_dump_file, "", val->type, 0); + putc ('\n',cgraph_dump_file); + print_node (cgraph_dump_file, "", type, 0); + putc ('\n',cgraph_dump_file); + } + } + + /* Regularize things a little. During LTO same types may come with + different BINFOs. Either because their virtual table was + not merged by tree merging and only later at decl merging or + because one type comes with external vtable, while other + with internal. We want to merge equivalent binfos to conserve + memory and streaming overhead. + + The external vtables are more harmful: they contain references + to external declarations of methods that may be defined in the + merged LTO unit. For this reason we absolutely need to remove + them and replace by internal variants. Not doing so will lead + to incomplete answers from possible_polymorphic_call_targets. */ + if (!flag_ltrans && merge) + { + tree master_binfo = TYPE_BINFO (val->type); + tree v1 = BINFO_VTABLE (master_binfo); + tree v2 = BINFO_VTABLE (TYPE_BINFO (type)); + + if (TREE_CODE (v1) == POINTER_PLUS_EXPR) + { + gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR + && operand_equal_p (TREE_OPERAND (v1, 1), + TREE_OPERAND (v2, 1), 0)); + v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0); + v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0); + } + gcc_assert (DECL_ASSEMBLER_NAME (v1) + == DECL_ASSEMBLER_NAME (v2)); + + if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2)) + { + unsigned int i; + + TYPE_BINFO (val->type) = TYPE_BINFO (type); + for (i = 0; i < val->types->length(); i++) + { + if (TYPE_BINFO ((*val->types)[i]) + == master_binfo) + TYPE_BINFO ((*val->types)[i]) = TYPE_BINFO (type); + } + } + else + TYPE_BINFO (type) = master_binfo; + } + } + } + /* Get ODR type hash entry for TYPE. If INSERT is true, create possibly new entry. */ *************** get_odr_type (tree type, bool insert) *** 244,254 **** { val = *slot; ! /* With LTO we will need to support multiple tree representation of ! the same ODR type. For now we ignore this. */ ! if (val->type == type) ! return val; ! gcc_unreachable (); } else { --- 399,408 ---- { val = *slot; ! /* With LTO we need to support multiple tree representation of ! the same ODR type. */ ! if (val->type != type) ! add_type_duplicate (val, type); } else { *************** dump_type_inheritance_graph (FILE *f) *** 324,329 **** --- 478,505 ---- if (odr_types[i]->bases.length() == 0) dump_odr_type (f, odr_types[i]); } + for (i = 0; i < odr_types.length(); i++) + { + if (odr_types[i]->types && odr_types[i]->types->length()) + { + unsigned int j; + fprintf (f, "Duplicate tree types for odr type %i\n", i); + print_node (f, "", odr_types[i]->type, 0); + for (j = 0; j < odr_types[i]->types->length(); j++) + { + tree t; + fprintf (f, "duplicate #%i\n", j); + print_node (f, "", (*odr_types[i]->types)[j], 0); + t = (*odr_types[i]->types)[j]; + while (TYPE_P (t) && TYPE_CONTEXT (t)) + { + t = TYPE_CONTEXT (t); + print_node (f, "", t, 0); + } + putc ('\n',f); + } + } + } } /* Given method type T, return type of class it belongs to. Index: ipa.c =================================================================== *** ipa.c (revision 201835) --- ipa.c (working copy) *************** symtab_remove_unreachable_nodes (bool be *** 223,228 **** --- 223,230 ---- #ifdef ENABLE_CHECKING verify_symtab (); #endif + if (optimize && flag_devirtualize) + build_type_inheritance_graph (); if (file) fprintf (file, "\nReclaiming functions:"); #ifdef ENABLE_CHECKING Index: tree.c =================================================================== *** tree.c (revision 201836) --- tree.c (working copy) *************** types_same_for_odr (tree type1, tree typ *** 11833,11843 **** 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; - #ifndef ENABLE_CHECKING if (!in_lto_p) return false; --- 11833,11838 ---- *************** types_same_for_odr (tree type1, tree typ *** 11848,11854 **** --- 11843,11887 ---- if (type_in_anonymous_namespace_p (type1) || type_in_anonymous_namespace_p (type2)) return false; + /* When assembler name of virtual table is available, it is + easy to compare types for equivalence. + FIXME: the code comparing type names consider all instantiations of the + same template to have same name. This is because we have no access + to template parameters. For types with no virtual method tables + we thus can return false positives. At the moment we do not need + to compare types in other scenarios than devirtualization. */ + 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); + } + v1 = DECL_ASSEMBLER_NAME (v1); + v2 = DECL_ASSEMBLER_NAME (v2); + /* If we ever start adding random .blah suffixes after + assembler names, we need to compare for match ignoring + these (and update odr_type_hash, too). */ + #ifdef ENABLE_CHECKING + gcc_assert (!strchr (IDENTIFIER_POINTER (v1), '.') + && !strchr (IDENTIFIER_POINTER (v2), '.')); + #endif + return (v1 == v2); + } + + /* 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; if (!TYPE_NAME (type1)) return false; if (!decls_same_for_odr (TYPE_NAME (type1), TYPE_NAME (type2)))
