diff options
| -rw-r--r-- | gcc/ChangeLog | 20 | ||||
| -rw-r--r-- | gcc/Makefile.in | 8 | ||||
| -rw-r--r-- | gcc/cgraph.c | 12 | ||||
| -rw-r--r-- | gcc/cgraphunit.c | 33 | ||||
| -rw-r--r-- | gcc/dumpfile.c | 2 | ||||
| -rw-r--r-- | gcc/dumpfile.h | 1 | ||||
| -rw-r--r-- | gcc/ipa-devirt.c | 666 | ||||
| -rw-r--r-- | gcc/ipa-utils.h | 42 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/testsuite/g++.dg/ipa/type-inheritance-1.C | 28 | ||||
| -rw-r--r-- | gcc/timevar.def | 2 | ||||
| -rw-r--r-- | gcc/tree.c | 15 | ||||
| -rw-r--r-- | gcc/tree.h | 1 |
13 files changed, 818 insertions, 16 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9fdf2c45931..38216dcbc28 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,23 @@ +2013-08-18 Jan Hubicka <jh@suse.cz> + + * Makeifle-in (ipa-devirt.o): New. + (GTFILES): Add ipa-utils.h and ipa-devirt.c + * cgraphunit.c (decide_is_symbol_needed): Do not care about virtuals. + (analyze_functions): Look into possible targets of polymorphic call. + * dumpfile.c (dump_files): Add type-inheritance dump. + * dumpfile.h (TDI_inheritance): New. + * ipa-devirt.c: New file. + * ipa-utils.h (odr_type_d): Forward declare. + (odr_type): New type. + (build_type_inheritance_graph): Declare. + (possible_polymorphic_call_targets): Declare and introduce inline + variant when only edge is pased. + (dump_possible_polymorphic_call_targets): Likewise. + * timevar.def (TV_IPA_INHERITANCE, TV_IPA_VIRTUAL_CALL): New. + * tree.c (type_in_anonymous_namespace_p): Break out from ... + (types_same_for_odr): ... here. + * tree.h (type_in_anonymous_namespace_p): Declare. + 2013-08-18 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/58006 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 6ddc8534f84..6034046374a 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1275,6 +1275,7 @@ OBJS = \ init-regs.o \ internal-fn.o \ ipa-cp.o \ + ipa-devirt.o \ ipa-split.o \ ipa-inline.o \ ipa-inline-analysis.o \ @@ -2945,6 +2946,9 @@ ipa.o : ipa.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \ $(TREE_PASS_H) $(GIMPLE_H) $(TARGET_H) $(GGC_H) pointer-set.h \ $(IPA_UTILS_H) tree-inline.h $(HASH_TABLE_H) profile.h $(PARAMS_H) \ $(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) \ @@ -3784,7 +3788,7 @@ GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/cselib.h $(srcdir)/basic-block.h $(srcdir)/ipa-ref.h $(srcdir)/cgraph.h \ $(srcdir)/reload.h $(srcdir)/caller-save.c $(srcdir)/symtab.c \ $(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c $(srcdir)/cgraph.c \ - $(srcdir)/ipa-prop.c $(srcdir)/ipa-cp.c \ + $(srcdir)/ipa-prop.c $(srcdir)/ipa-cp.c $(srcdir)/ipa-utils.h \ $(srcdir)/dbxout.c \ $(srcdir)/dwarf2out.h \ $(srcdir)/dwarf2asm.c \ @@ -3826,7 +3830,7 @@ GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/ipa-inline.h \ $(srcdir)/vtable-verify.c \ $(srcdir)/asan.c \ - $(srcdir)/tsan.c \ + $(srcdir)/tsan.c $(srcdir)/ipa-devirt.c \ @all_gtfiles@ # Compute the list of GT header files from the corresponding C sources, diff --git a/gcc/cgraph.c b/gcc/cgraph.c index e2f96d6436d..c6850c60c31 100644 --- a/gcc/cgraph.c +++ b/gcc/cgraph.c @@ -1292,10 +1292,13 @@ cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e) struct ipa_ref *ref; cgraph_speculative_call_info (e, e, e2, ref); - if (gimple_call_fndecl (e->call_stmt)) - e = cgraph_resolve_speculation (e, gimple_call_fndecl (e->call_stmt)); - if (!gimple_check_call_matching_types (e->call_stmt, e->callee->symbol.decl, - true)) + /* If there already is an direct call (i.e. as a result of inliner's substitution), + forget about speculating. */ + if (decl) + e = cgraph_resolve_speculation (e, decl); + /* If types do not match, speculation was likely wrong. */ + else if (!gimple_check_call_matching_types (e->call_stmt, e->callee->symbol.decl, + true)) { e = cgraph_resolve_speculation (e, NULL); if (dump_file) @@ -1304,6 +1307,7 @@ cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e) xstrdup (cgraph_node_name (e->caller)), e->caller->symbol.order, xstrdup (cgraph_node_name (e->callee)), e->callee->symbol.order); } + /* Expand speculation into GIMPLE code. */ else { if (dump_file) diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c index 1a4f99febf9..0aa68c75e80 100644 --- a/gcc/cgraphunit.c +++ b/gcc/cgraphunit.c @@ -235,10 +235,6 @@ decide_is_symbol_needed (symtab_node node) if (!node->symbol.definition) return false; - /* Devirtualization may access these. */ - if (DECL_VIRTUAL_P (decl) && optimize) - return true; - if (DECL_EXTERNAL (decl)) return false; @@ -838,6 +834,7 @@ analyze_functions (void) struct cgraph_node *first_handled = first_analyzed; static struct varpool_node *first_analyzed_var; struct varpool_node *first_handled_var = first_analyzed_var; + struct pointer_set_t *reachable_call_targets = pointer_set_create (); symtab_node node, next; int i; @@ -853,6 +850,8 @@ analyze_functions (void) FOR_EACH_SYMBOL (node) if (node->symbol.cpp_implicit_alias) fixup_same_cpp_alias_visibility (node, symtab_alias_target (node)); + if (optimize && flag_devirtualize) + build_type_inheritance_graph (); /* Analysis adds static variables that in turn adds references to new functions. So we need to iterate the process until it stabilize. */ @@ -875,6 +874,8 @@ analyze_functions (void) changed = true; if (cgraph_dump_file) fprintf (cgraph_dump_file, " %s", symtab_node_asm_name (node)); + if (!changed && cgraph_dump_file) + fprintf (cgraph_dump_file, "\n"); } if (node == (symtab_node)first_analyzed || node == (symtab_node)first_analyzed_var) @@ -919,6 +920,29 @@ analyze_functions (void) for (edge = cnode->callees; edge; edge = edge->next_callee) if (edge->callee->symbol.definition) enqueue_node ((symtab_node)edge->callee); + if (optimize && flag_devirtualize) + { + for (edge = cnode->indirect_calls; edge; edge = edge->next_callee) + if (edge->indirect_info->polymorphic) + { + unsigned int i; + void *cache_token; + vec <cgraph_node *>targets + = possible_polymorphic_call_targets + (edge, NULL, &cache_token); + + if (!pointer_set_insert (reachable_call_targets, + cache_token)) + { + if (cgraph_dump_file) + dump_possible_polymorphic_call_targets + (cgraph_dump_file, edge); + + for (i = 0; i < targets.length(); i++) + enqueue_node ((symtab_node) targets[i]); + } + } + } /* If decl is a clone of an abstract function, mark that abstract function so that we don't release its body. @@ -999,6 +1023,7 @@ analyze_functions (void) dump_symtab (cgraph_dump_file); } bitmap_obstack_release (NULL); + pointer_set_destroy (reachable_call_targets); ggc_collect (); } diff --git a/gcc/dumpfile.c b/gcc/dumpfile.c index 55ad80451d6..9c97512e799 100644 --- a/gcc/dumpfile.c +++ b/gcc/dumpfile.c @@ -52,6 +52,8 @@ static struct dump_file_info dump_files[TDI_end] = {NULL, NULL, NULL, NULL, NULL, NULL, NULL, 0, 0, 0, 0, 0, 0}, {".cgraph", "ipa-cgraph", NULL, NULL, NULL, NULL, NULL, TDF_IPA, 0, 0, 0, 0, 0}, + {".type-inheritance", "ipa-type-inheritance", NULL, NULL, NULL, NULL, NULL, TDF_IPA, + 0, 0, 0, 0, 0}, {".tu", "translation-unit", NULL, NULL, NULL, NULL, NULL, TDF_TREE, 0, 0, 0, 0, 1}, {".class", "class-hierarchy", NULL, NULL, NULL, NULL, NULL, TDF_TREE, diff --git a/gcc/dumpfile.h b/gcc/dumpfile.h index 77f5de68c4d..da079bad748 100644 --- a/gcc/dumpfile.h +++ b/gcc/dumpfile.h @@ -29,6 +29,7 @@ enum tree_dump_index { TDI_none, /* No dump */ TDI_cgraph, /* dump function call graph. */ + TDI_inheritance, /* dump type inheritance graph. */ TDI_tu, /* dump the whole translation unit. */ TDI_class, /* dump class hierarchy. */ TDI_original, /* dump each function before optimizing it */ diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c new file mode 100644 index 00000000000..834cfb01dbb --- /dev/null +++ b/gcc/ipa-devirt.c @@ -0,0 +1,666 @@ +/* Basic IPA utilities for type inheritance graph construction and + devirtualization. + Copyright (C) 2013 Free Software Foundation, Inc. + Contributed by Jan Hubicka + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +/* Brief vocalburary: + ODR = One Definition Rule + In short, the ODR states that: + 1 In any translation unit, a template, type, function, or object can + have no more than one definition. Some of these can have any number + of declarations. A definition provides an instance. + 2 In the entire program, an object or non-inline function cannot have + more than one definition; if an object or function is used, it must + have exactly one definition. You can declare an object or function + that is never used, in which case you don't have to provide + a definition. In no event can there be more than one definition. + 3 Some things, like types, templates, and extern inline functions, can + be defined in more than one translation unit. For a given entity, + each definition must be the same. Non-extern objects and functions + in different translation units are different entities, even if their + names and types are the same. + + OTR = OBJ_TYPE_REF + This is Gimple representation of type information of a polymorphic call. + It contains two parameters: + otr_type is a type of class whose method is called. + otr_token is index into virtual table where address is taken. + + BINFO + This is the type inheritance information attached to each tree + RECORD_TYPE by the C++ frotend. It provides information about base + types and virtual tables. + + BINFO is linked to the RECORD_TYPE by TYPE_BINFO. + BINFO also links to its type by BINFO_TYPE and to the virtual table by + BINFO_VTABLE. + + Base types of a given type are enumerated by BINFO_BASE_BINFO + vector. Members of this vectors are not BINFOs associated + with a base type. Rather they are new copies of BINFOs + (base BINFOs). Their virtual tables may differ from + virtual table of the base type. Also BINFO_OFFSET specify + offset of the base within the type. + + In the case of single inheritance, the virtual table is shared + and BINFO_VTABLE of base BINFO is NULL. In the case of multiple + inheritance the individual virtual tables are pointer to by + BINFO_VTABLE of base binfos (that differs of BINFO_VTABLE of + binfo associated to the base type). + + BINFO lookup for a given base type and offset can be done by + get_binfo_at_offset. It returns proper BINFO whose virtual table + can be used for lookup of virtual methods associated with the + base type. + + token + This is an index of virtual method in virtual table associated + to the type defining it. Token can be looked up from OBJ_TYPE_REF + or from DECL_VINDEX of given virtual table. + + polymorphic (indirect) call + This is callgraph represention of virtual method call. Every + polymorphic call contains otr_type and otr_token taken from + original OBJ_TYPE_REF at callgraph construction time. + + What we do here: + + build_type_inheritance_graph triggers a construction of the type inheritance + graph. + + We reconstruct it based on types of methods we see in the unit. + This means that the graph is not complete. Types with no methods are not + inserted to the graph. Also types without virtual methods are not + represented at all, though it may be easy to add this. + + The inheritance graph is represented as follows: + + Vertices are structures odr_type. Every odr_type may correspond + to one or more tree type nodes that are equivalent by ODR rule. + (the multiple type nodes appear only with linktime optimization) + + Edges are repsented by odr_type->base and odr_type->derived_types. + At the moment we do not track offsets of types for multiple inheritance. + Adding this is easy. + + possible_polymorphic_call_targets returns, given an parameters found in + indirect polymorphic edge all possible polymorphic call targets of the call. +*/ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "cgraph.h" +#include "tree-pass.h" +#include "ggc.h" +#include "pointer-set.h" +#include "target.h" +#include "hash-table.h" +#include "tree-pretty-print.h" +#include "ipa-utils.h" +#include "gimple.h" + +/* The node of type inheritance graph. For each type unique in + One Defintion Rule (ODR) sense, we produce one node linking all + main variants of types equivalent to it, bases and derived types. */ + +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; +}; + + +/* Return true if BINFO corresponds to a type with virtual methods. */ + +static inline bool +polymorphic_type_binfo_p (tree binfo) +{ + /* See if BINFO's type has an virtual table associtated with it. */ + return BINFO_VTABLE (TYPE_BINFO (BINFO_TYPE (binfo))); +} + +/* One Definition Rule hashtable helpers. */ + +struct odr_hasher +{ + typedef odr_type_d value_type; + typedef union tree_node compare_type; + static inline hashval_t hash (const value_type *); + static inline bool equal (const value_type *, const compare_type *); + static inline void remove (value_type *); +}; + +/* Produce hash based on type name. */ + +hashval_t +hash_type_name (tree t) +{ + gcc_checking_assert (TYPE_MAIN_VARIANT (t) == t); + + /* If not in LTO, all main variants are unique, so we can do + pointer hash. */ + if (!in_lto_p) + return htab_hash_pointer (t); + + /* Anonymous types are unique. */ + if (type_in_anonymous_namespace_p (t)) + return htab_hash_pointer (t); + + /* Rest is not implemented yet. */ + gcc_unreachable (); +} + +/* Return the computed hashcode for ODR_TYPE. */ + +inline hashval_t +odr_hasher::hash (const value_type *odr_type) +{ + return hash_type_name (odr_type->type); +} + +/* Compare types operations T1 and T2 and return true if they are + equivalent. */ + +inline bool +odr_hasher::equal (const value_type *t1, const compare_type *ct2) +{ + tree t2 = const_cast <tree> (ct2); + + gcc_checking_assert (TYPE_MAIN_VARIANT (ct2) == ct2); + if (t1->type == t2) + return true; + if (!in_lto_p) + return false; + 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); +} + +/* ODR type hash used to lookup ODR type based on tree type node. */ + +typedef hash_table <odr_hasher> odr_hash_type; +static odr_hash_type odr_hash; + +/* ODR types are also stored into ODR_TYPE vector to allow consistent + walking. Bases appear before derived types. Vector is garbage collected + so we won't end up visiting empty types. */ + +static GTY(()) vec <odr_type, va_gc> *odr_types_ptr; +#define odr_types (*odr_types_ptr) + +/* Get ODR type hash entry for TYPE. If INSERT is true, create + possibly new entry. */ + +odr_type +get_odr_type (tree type, bool insert) +{ + odr_type_d **slot; + odr_type val; + hashval_t hash; + + type = TYPE_MAIN_VARIANT (type); + gcc_checking_assert (TYPE_MAIN_VARIANT (type) == type); + hash = hash_type_name (type); + slot = odr_hash.find_slot_with_hash (type, hash, insert ? INSERT : NO_INSERT); + if (!slot) + return NULL; + + /* See if we already have entry for type. */ + if (*slot) + { + 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 + { + tree binfo = TYPE_BINFO (type); + unsigned int i; + + val = ggc_alloc_cleared_odr_type_d (); + val->type = type; + val->bases = vNULL; + val->derived_types = vNULL; + *slot = val; + for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++) + /* For now record only polymorphic types. other are + pointless for devirtualization and we can not precisely + determine ODR equivalency of these during LTO. */ + if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo, i))) + { + odr_type base = get_odr_type (BINFO_TYPE (BINFO_BASE_BINFO (binfo, + i)), + true); + base->derived_types.safe_push (val); + val->bases.safe_push (base); + } + /* First record bases, then add into array so ids are increasing. */ + if (odr_types_ptr) + val->id = odr_types.length(); + vec_safe_push (odr_types_ptr, val); + } + return val; +} + +/* Dump ODR type T and all its derrived type. INDENT specify indentation for + recusive printing. */ + +static void +dump_odr_type (FILE *f, odr_type t, int indent=0) +{ + unsigned int i; + fprintf (f, "%*s type %i: ", indent * 2, "", t->id); + print_generic_expr (f, t->type, TDF_SLIM); + fprintf (f, "\n"); + if (TYPE_NAME (t->type)) + { + fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "", + DECL_SOURCE_FILE (TYPE_NAME (t->type)), + DECL_SOURCE_LINE (TYPE_NAME (t->type))); + } + if (t->bases.length()) + { + fprintf (f, "%*s base odr type ids: ", indent * 2, ""); + for (i = 0; i < t->bases.length(); i++) + fprintf (f, " %i", t->bases[i]->id); + fprintf (f, "\n"); + } + if (t->derived_types.length()) + { + fprintf (f, "%*s derived types:\n", indent * 2, ""); + for (i = 0; i < t->derived_types.length(); i++) + dump_odr_type (f, t->derived_types[i], indent + 1); + } + fprintf (f, "\n"); +} + +/* Dump the type inheritance graph. */ + +static void +dump_type_inheritance_graph (FILE *f) +{ + unsigned int i; + fprintf (f, "\n\nType inheritance graph:\n"); + for (i = 0; i < odr_types.length(); i++) + { + if (odr_types[i]->bases.length() == 0) + dump_odr_type (f, odr_types[i]); + } +} + +/* Given method type T, return type of class it belongs to. + Lookup this pointer and get its type. */ + +static tree +method_class_type (tree t) +{ + tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t)); + + return TREE_TYPE (first_parm_type); +} + +/* Initialize IPA devirt and build inheritance tree graph. */ + +void +build_type_inheritance_graph (void) +{ + struct cgraph_node *n; + FILE *inheritance_dump_file; + int flags; + + if (odr_hash.is_created ()) + return; + timevar_push (TV_IPA_INHERITANCE); + inheritance_dump_file = dump_begin (TDI_inheritance, &flags); + odr_hash.create (23); + + /* We reconstruct the graph starting of types of all methods seen in the + the unit. */ + FOR_EACH_FUNCTION (n) + if (DECL_VIRTUAL_P (n->symbol.decl) + && symtab_real_symbol_p ((symtab_node)n)) + get_odr_type (method_class_type (TREE_TYPE (n->symbol.decl)), true); + if (inheritance_dump_file) + { + dump_type_inheritance_graph (inheritance_dump_file); + dump_end (TDI_inheritance, inheritance_dump_file); + } + timevar_pop (TV_IPA_INHERITANCE); +} + +/* If TARGET has associated node, record it in the NODES array. */ + +static void +maybe_record_node (vec <cgraph_node *> &nodes, + tree target, pointer_set_t *inserted) +{ + struct cgraph_node *target_node; + enum built_in_function fcode; + + if (target + /* Those are used to mark impossible scenarios. */ + && (fcode = DECL_FUNCTION_CODE (target)) + != BUILT_IN_UNREACHABLE + && fcode != BUILT_IN_TRAP + && !pointer_set_insert (inserted, target) + && (target_node = cgraph_get_node (target)) != NULL + && symtab_real_symbol_p ((symtab_node)target_node)) + nodes.safe_push (target_node); +} + +/* See if BINFO's type match OTR_TYPE. If so, lookup method + in vtable of TYPE_BINFO and insert method to NODES array. + Otherwise recurse to base BINFOs. + This match what get_binfo_at_offset does, but with offset + being unknown. + + TYPE_BINFO is binfo holding an virtual table matching + BINFO's type. In the case of single inheritance, this + is binfo of BINFO's type ancestor (vtable is shared), + otherwise it is binfo of BINFO's type. + + MATCHED_VTABLES tracks virtual tables we already did lookup + for virtual function in. + */ + +static void +record_binfo (vec <cgraph_node *> &nodes, + tree binfo, + tree otr_type, + tree type_binfo, + HOST_WIDE_INT otr_token, + pointer_set_t *inserted, + pointer_set_t *matched_vtables) +{ + tree type = BINFO_TYPE (binfo); + int i; + tree base_binfo; + + gcc_checking_assert (BINFO_VTABLE (type_binfo)); + + if (types_same_for_odr (type, otr_type) + && !pointer_set_insert (matched_vtables, BINFO_VTABLE (type_binfo))) + { + tree target = gimple_get_virt_method_for_binfo (otr_token, type_binfo); + if (target) + maybe_record_node (nodes, target, inserted); + return; + } + + /* Walk bases. */ + for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) + /* Walking bases that have no virtual method is pointless excercise. */ + if (polymorphic_type_binfo_p (base_binfo)) + record_binfo (nodes, base_binfo, otr_type, + BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo, + otr_token, inserted, + matched_vtables); +} + +/* Lookup virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN) + of TYPE, insert them to NODES, recurse into derived nodes. + INSERTED is used to avoid duplicate insertions of methods into NODES. + MATCHED_VTABLES are used to avoid duplicate walking vtables. */ + +static void +possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes, + pointer_set_t *inserted, + pointer_set_t *matched_vtables, + tree otr_type, + odr_type type, + HOST_WIDE_INT otr_token) +{ + tree binfo = TYPE_BINFO (type->type); + unsigned int i; + + record_binfo (nodes, binfo, otr_type, binfo, otr_token, inserted, + matched_vtables); + for (i = 0; i < type->derived_types.length(); i++) + possible_polymorphic_call_targets_1 (nodes, inserted, + matched_vtables, + otr_type, + type->derived_types[i], + otr_token); +} + +/* Cache of queries for polymorphic call targets. + + Enumerating all call targets may get expensive when there are many + polymorphic calls in the program, so we memoize all the previous + queries and avoid duplicated work. */ + +struct polymorphic_call_target_d +{ + odr_type type; + HOST_WIDE_INT otr_token; + vec <cgraph_node *> targets; +}; + +/* Polymorphic call target cache helpers. */ + +struct polymorphic_call_target_hasher +{ + typedef polymorphic_call_target_d value_type; + typedef polymorphic_call_target_d compare_type; + static inline hashval_t hash (const value_type *); + static inline bool equal (const value_type *, const compare_type *); + static inline void remove (value_type *); +}; + +/* Return the computed hashcode for ODR_QUERY. */ + +inline hashval_t +polymorphic_call_target_hasher::hash (const value_type *odr_query) +{ + return iterative_hash_hashval_t (odr_query->type->id, + odr_query->otr_token); +} + +/* Compare cache entries T1 and T2. */ + +inline bool +polymorphic_call_target_hasher::equal (const value_type *t1, + const compare_type *t2) +{ + return t1->type == t2->type && t1->otr_token == t2->otr_token; +} + +/* Remove entry in polymorphic call target cache hash. */ + +inline void +polymorphic_call_target_hasher::remove (value_type *v) +{ + v->targets.release (); + free (v); +} + +/* Polymorphic call target query cache. */ + +typedef hash_table <polymorphic_call_target_hasher> + polymorphic_call_target_hash_type; +static polymorphic_call_target_hash_type polymorphic_call_target_hash; +pointer_set_t *cached_polymorphic_call_targets; + +/* Destroy polymorphic call target query cache. */ + +static void +free_polymorphic_call_targets_hash () +{ + polymorphic_call_target_hash.dispose (); + pointer_set_destroy (cached_polymorphic_call_targets); + cached_polymorphic_call_targets = NULL; +} + +/* When virtual function is removed, we may need to flush the cache. */ + +static void +devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED) +{ + if (pointer_set_contains (cached_polymorphic_call_targets, n)) + free_polymorphic_call_targets_hash (); +} + +/* Return vector containing possible targets of polymorphic call of type + OTR_TYPE caling method OTR_TOKEN with OFFSET. If FINALp is non-NULL, + store true if the list is complette. + CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry + in the target cache. If user needs to visit every target list + just once, it can memoize them. + + Returned vector is placed into cache. It is NOT caller's responsibility + to free it. The vector can be freed on cgraph_remove_node call if + the particular node is a virtual function present in the cache. */ + +vec <cgraph_node *> +possible_polymorphic_call_targets (tree otr_type, + HOST_WIDE_INT otr_token, + bool *finalp, + void **cache_token) +{ + static struct cgraph_node_hook_list *node_removal_hook_holder; + pointer_set_t *inserted; + pointer_set_t *matched_vtables; + vec <cgraph_node *> nodes=vNULL; + odr_type type; + polymorphic_call_target_d key; + polymorphic_call_target_d **slot; + unsigned int i; + tree binfo, target; + + if (finalp) + *finalp = false; + + type = get_odr_type (otr_type, false); + /* If we do not have type in our hash it means we never seen any method + in it. */ + if (!type) + return nodes; + + /* For anonymous namespace types we can attempt to build full type. + All derivations must be in this unit. */ + if (type->anonymous_namespace && finalp && !flag_ltrans) + *finalp = true; + + /* Initialize query cache. */ + if (!cached_polymorphic_call_targets) + { + cached_polymorphic_call_targets = pointer_set_create (); + polymorphic_call_target_hash.create (23); + if (!node_removal_hook_holder) + node_removal_hook_holder = + cgraph_add_node_removal_hook (&devirt_node_removal_hook, NULL); + } + + /* Lookup cached answer. */ + key.type = type; + key.otr_token = otr_token; + slot = polymorphic_call_target_hash.find_slot (&key, INSERT); + if (cache_token) + *cache_token = (void *)*slot; + if (*slot) + return (*slot)->targets; + + /* Do actual search. */ + timevar_push (TV_IPA_VIRTUAL_CALL); + *slot = XCNEW (polymorphic_call_target_d); + if (cache_token) + *cache_token = (void *)*slot; + (*slot)->type = type; + (*slot)->otr_token = otr_token; + + inserted = pointer_set_create (); + matched_vtables = pointer_set_create (); + + /* First see virtual method of type itself. */ + + binfo = TYPE_BINFO (type->type); + target = gimple_get_virt_method_for_binfo (otr_token, binfo); + if (target) + maybe_record_node (nodes, target, inserted); + pointer_set_insert (matched_vtables, BINFO_VTABLE (binfo)); + + /* TODO: If method is final, we can stop here and signaize that + list is final. We need C++ FE to pass our info about final + methods and classes. */ + + /* Walk recursively all derived types. Here we need to lookup proper basetype + via their BINFO walk that is done by record_binfo */ + for (i = 0; i < type->derived_types.length(); i++) + possible_polymorphic_call_targets_1 (nodes, inserted, + matched_vtables, + otr_type, type->derived_types[i], + otr_token); + (*slot)->targets = nodes; + + pointer_set_destroy (inserted); + pointer_set_destroy (matched_vtables); + timevar_pop (TV_IPA_VIRTUAL_CALL); + return nodes; +} + +/* Dump all possible targets of a polymorphic call. */ + +void +dump_possible_polymorphic_call_targets (FILE *f, + tree otr_type, + HOST_WIDE_INT otr_token) +{ + vec <cgraph_node *> targets; + bool final; + odr_type type = get_odr_type (otr_type, false); + unsigned int i; + + if (!type) + return; + targets = possible_polymorphic_call_targets (otr_type, otr_token, + &final); + fprintf (f, "Targets of polymorphic call of type %i ", type->id); + print_generic_expr (f, type->type, TDF_SLIM); + fprintf (f, " token %i%s:", + (int)otr_token, + final ? " (full list)" : " (partial list, may call to other unit)"); + for (i = 0; i < targets.length (); i++) + fprintf (f, " %s/%i", cgraph_node_name (targets[i]), + targets[i]->symbol.order); + fprintf (f, "\n"); +} + +#include "gt-ipa-devirt.h" diff --git a/gcc/ipa-utils.h b/gcc/ipa-utils.h index f388598eafb..f35ddb5dc54 100644 --- a/gcc/ipa-utils.h +++ b/gcc/ipa-utils.h @@ -36,7 +36,6 @@ struct ipa_dfs_info { }; - /* In ipa-utils.c */ void ipa_print_order (FILE*, const char *, struct cgraph_node**, int); int ipa_reduced_postorder (struct cgraph_node **, bool, bool, @@ -46,7 +45,48 @@ vec<cgraph_node_ptr> ipa_get_nodes_in_cycle (struct cgraph_node *); int ipa_reverse_postorder (struct cgraph_node **); tree get_base_var (tree); +/* In ipa-devirt.c */ + +struct odr_type_d; +typedef odr_type_d *odr_type; +void build_type_inheritance_graph (void); +vec <cgraph_node *> +possible_polymorphic_call_targets (tree, HOST_WIDE_INT, + bool *final = NULL, + void **cache_token = NULL); +odr_type get_odr_type (tree, bool insert = false); +void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT); + +/* Return vector containing possible targets of polymorphic call E. + If FINALP is non-NULL, store true if the list is complette. + CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry + in the target cache. If user needs to visit every target list + just once, it can memoize them. + + Returned vector is placed into cache. It is NOT caller's responsibility + to free it. The vector can be freed on cgraph_remove_node call if + the particular node is a virtual function present in the cache. */ + +inline vec <cgraph_node *> +possible_polymorphic_call_targets (struct cgraph_edge *e, + bool *final = NULL, + void **cache_token = NULL) +{ + gcc_checking_assert (e->indirect_info->polymorphic); + return possible_polymorphic_call_targets (e->indirect_info->otr_type, + e->indirect_info->otr_token, + final, cache_token); +} + +/* Dump possible targets of a polymorphic call E into F. */ +inline void +dump_possible_polymorphic_call_targets (FILE *f, struct cgraph_edge *e) +{ + gcc_checking_assert (e->indirect_info->polymorphic); + dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type, + e->indirect_info->otr_token); +} #endif /* GCC_IPA_UTILS_H */ diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index d0eee3f8fc4..bbe5c1d87d2 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2013-08-18 Jan Hubicka <jh@suse.cz> + + * g++.dg/ipa/type-inheritance-1.C: New testcase. + 2013-08-19 Janus Weil <janus@gcc.gnu.org> PR fortran/46271 diff --git a/gcc/testsuite/g++.dg/ipa/type-inheritance-1.C b/gcc/testsuite/g++.dg/ipa/type-inheritance-1.C new file mode 100644 index 00000000000..818002ec1d5 --- /dev/null +++ b/gcc/testsuite/g++.dg/ipa/type-inheritance-1.C @@ -0,0 +1,28 @@ +/* Verify that callgraph construction keeps FOO for possible devirtualization + and removes BAR. */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-ipa-visibility" } */ + +extern "C" void abort (void); + +class A +{ +public: + virtual int foo (void) + { + return 4; + } + virtual int bar (void) + { + return 5; + } +}; + + +int t(class A *a) +{ + return a->foo(); +} +/* { dg-final { scan-ipa-dump "A::foo" "visibility" } } */ +/* { dg-final { scan-ipa-dump-not "A::bar" "visibility" } } */ +/* { dg-final { cleanup-ipa-dump "visibility" } } */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 8ab9b99eadf..bd1ee7612dc 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -64,6 +64,8 @@ DEFTIMEVAR (TV_PCH_CPP_RESTORE , "PCH preprocessor state restore") DEFTIMEVAR (TV_CGRAPH , "callgraph construction") DEFTIMEVAR (TV_CGRAPHOPT , "callgraph optimization") +DEFTIMEVAR (TV_IPA_INHERITANCE , "ipa inheritance graph") +DEFTIMEVAR (TV_IPA_VIRTUAL_CALL , "ipa virtual call target") DEFTIMEVAR (TV_IPA_CONSTANT_PROP , "ipa cp") DEFTIMEVAR (TV_IPA_INLINING , "ipa inlining heuristics") DEFTIMEVAR (TV_IPA_FNSPLIT , "ipa function splitting") diff --git a/gcc/tree.c b/gcc/tree.c index 9d4bc7f9fc8..194710564a9 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -11845,11 +11845,8 @@ types_same_for_odr (tree type1, tree type2) /* Check for anonymous namespaces. Those have !TREE_PUBLIC on the corresponding TYPE_STUB_DECL. */ - if (TYPE_STUB_DECL (type1) != TYPE_STUB_DECL (type2) - && (!TYPE_STUB_DECL (type1) - || !TYPE_STUB_DECL (type2) - || !TREE_PUBLIC (TYPE_STUB_DECL (type1)) - || !TREE_PUBLIC (TYPE_STUB_DECL (type2)))) + if (type_in_anonymous_namespace_p (type1) + || type_in_anonymous_namespace_p (type2)) return false; if (!TYPE_NAME (type1)) @@ -11904,6 +11901,14 @@ obj_type_ref_class (tree ref) return TREE_TYPE (ref); } +/* Return true if T is in anonymous namespace. */ + +bool +type_in_anonymous_namespace_p (tree t) +{ + return (TYPE_STUB_DECL (t) && !TREE_PUBLIC (TYPE_STUB_DECL (t))); +} + /* Try to find a base info of BINFO that would have its field decl at offset OFFSET within the BINFO type and which is of EXPECTED_TYPE. If it can be found, return, otherwise return NULL_TREE. */ diff --git a/gcc/tree.h b/gcc/tree.h index 4dbff212b97..84bd69932d2 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -5980,6 +5980,7 @@ extern bool types_same_for_odr (tree type1, tree type2); extern tree get_ref_base_and_extent (tree, HOST_WIDE_INT *, HOST_WIDE_INT *, HOST_WIDE_INT *); extern bool contains_bitfld_component_ref_p (const_tree); +extern bool type_in_anonymous_namespace_p (tree); /* In tree-nested.c */ extern tree build_addr (tree, tree); |