Jan Hubicka <hubi...@ucw.cz> wrote:
>Hi,
>this patch fixes some issues with ipa-devirt I noticed since the
>initial
>commit.
>
> 1) I added fixes and comments Doji suggested (thanks!)
>
>2) During the callgraph construction new external nodes may be created
>that
>needs to be added into the inheritance graph get more complette andwers
> from possible_polymorphic_call_targets.
>
>While the answer is never complette for external functions, it is
>better
> to have more of them than fewer so speculation is not trying to work
> too hard.
>
> I added function that collects all new nodes into the graph.
>
>3) I merged in flag for anonymous_namespace types, but forgot to
>initialize
> it (it is used to decide if set of targets is complette and I am not
> using that flag in mainline ATM)
>
>4) Added possible_polymorphic_call_target_p that can be used for sanity
>checking
>of devirtualization machinery. The testing now passes firefox and
>couple
>other testcases, but I will submit the verification bits separately of
>this
> change.
>
>5) -fdump-ipa-type-inheritance ICEs when there are no polynmorphic
>types.
>
>6) I managed to get call target cache wrong in a way that is is never
>freed
> on node removal as it is supposed to.
>
>Bootstrapped/regtested ppc64-linux, will commit it tomorrow if there
>are no
>complains and x86_64-linux testing completes.
Btw, how does this all scale with the worst testcase? That is, a very deep
inheritance hierarchy with each level virtually overriding all methods and very
many duplicate input files? Is that really the worst case? We should make sure
not to introduce quadratic or worse algorithms. (I didn't see you limiting the
number of possible call targets)
Richard.
>Honza
>
> * cgraphunit.c (analyze_functions) Use update_type_inheritance_graph.
> * ipa-utils.h (update_type_inheritance_graph): Declare.
> (possible_polymorphic_call_target_p): Declare.
> (possible_polymorphic_call_target_p): New.
> * ipa-devirt.c: Update toplevel comments.
> (cached_polymorphic_call_targets): Move up.
> (odr_type_d): Move ID down.
> (polymorphic_type_binfo_p): Update comment.
> (odr_hasher::remove): Likewise;
> (get_odr_type): Set anonymous_namespace.
> (dump_odr_type): Dump it.
> (dump_type_inheritance_graph): Do not ICE when there are no ODR types.
> (maybe_record_node): Record node in cached_polymorphic_call_targets.
> (record_binfo): Add comment.
> (free_polymorphic_call_targets_hash): Do not ICE when cache is not
>built.
> (devirt_node_removal_hook): Do not iCE when cache is freed.
> (possible_polymorphic_call_target_p): New predicate.
> (update_type_inheritance_graph): New function.
>Index: cgraphunit.c
>===================================================================
>--- cgraphunit.c (revision 201899)
>+++ cgraphunit.c (working copy)
>@@ -976,6 +976,8 @@ analyze_functions (void)
> cgraph_process_new_functions ();
> }
> }
>+ if (optimize && flag_devirtualize)
>+ update_type_inheritance_graph ();
>
> /* Collect entry points to the unit. */
> if (cgraph_dump_file)
>Index: ipa-utils.h
>===================================================================
>--- ipa-utils.h (revision 201899)
>+++ ipa-utils.h (working copy)
>@@ -50,12 +50,15 @@ tree get_base_var (tree);
> struct odr_type_d;
> typedef odr_type_d *odr_type;
> void build_type_inheritance_graph (void);
>+void update_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);
>+bool possible_polymorphic_call_target_p (tree, HOST_WIDE_INT,
>+ struct cgraph_node *n);
>
> /* Return vector containing possible targets of polymorphic call E.
> If FINALP is non-NULL, store true if the list is complette.
>@@ -87,6 +90,17 @@ dump_possible_polymorphic_call_targets (
> dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type,
> e->indirect_info->otr_token);
> }
>+
>+/* Return true if N can be possibly target of a polymorphic call of
>+ E. */
>+
>+inline bool
>+possible_polymorphic_call_target_p (struct cgraph_edge *e,
>+ struct cgraph_node *n)
>+{
>+ return possible_polymorphic_call_target_p
>(e->indirect_info->otr_type,
>+ e->indirect_info->otr_token, n);
>+}
> #endif /* GCC_IPA_UTILS_H */
>
>
>Index: ipa-devirt.c
>===================================================================
>--- ipa-devirt.c (revision 201899)
>+++ ipa-devirt.c (working copy)
>@@ -37,10 +37,10 @@ along with GCC; see the file COPYING3.
> names and types are the same.
>
> OTR = OBJ_TYPE_REF
>- This is Gimple representation of type information of a
>polymorphic call.
>+ This is the 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.
>+ otr_token is the index into virtual table where address is taken.
>
> BINFO
> This is the type inheritance information attached to each tree
>@@ -55,7 +55,7 @@ along with GCC; see the file COPYING3.
> 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
>+ virtual table of the base type. Also BINFO_OFFSET specifies
> offset of the base within the type.
>
> In the case of single inheritance, the virtual table is shared
>@@ -72,7 +72,7 @@ along with GCC; see the file COPYING3.
> 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.
>+ or from DECL_VINDEX of a given virtual table.
>
> polymorphic (indirect) call
> This is callgraph represention of virtual method call. Every
>@@ -86,7 +86,7 @@ along with GCC; see the file COPYING3.
>
> 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
>+ inserted into 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:
>@@ -95,7 +95,7 @@ along with GCC; see the file COPYING3.
> 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.
>+ Edges are represented 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.
>
>@@ -117,26 +117,36 @@ along with GCC; see the file COPYING3.
> #include "ipa-utils.h"
> #include "gimple.h"
>
>+/* Pointer set of all call targets appearing in the cache. */
>+static pointer_set_t *cached_polymorphic_call_targets;
>+
> /* 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;
>+
>+ /* Unique ID indexing the type in odr_types array. */
>+ int id;
> /* Is it in anonymous namespace? */
> bool anonymous_namespace;
> };
>
>
>-/* Return true if BINFO corresponds to a type with virtual methods.
>*/
>+/* Return true if BINFO corresponds to a type with virtual methods.
>+
>+ Every type has several BINFOs. One is the BINFO associated by the
>type
>+ while other represents bases of derived types. The BINFOs
>representing
>+ bases do not have BINFO_VTABLE pointer set when this is the single
>+ inheritance (because vtables are shared). Look up the BINFO of
>type
>+ and check presence of its vtable. */
>
> static inline bool
> polymorphic_type_binfo_p (tree binfo)
>@@ -184,7 +194,7 @@ odr_hasher::hash (const value_type *odr_
> return hash_type_name (odr_type->type);
> }
>
>-/* Compare types operations T1 and T2 and return true if they are
>+/* Compare types T1 and T2 and return true if they are
> equivalent. */
>
> inline bool
>@@ -200,13 +210,13 @@ odr_hasher::equal (const value_type *t1,
> return types_same_for_odr (t1->type, t2);
> }
>
>-/* Free a phi operation structure VP. */
>+/* Free ODR type V. */
>
> inline void
> odr_hasher::remove (value_type *v)
> {
> v->bases.release ();
> v->derived_types.release ();
> ggc_free (v);
> }
>
>@@ -259,6 +271,7 @@ get_odr_type (tree type, bool insert)
> val->type = type;
> val->bases = vNULL;
> val->derived_types = vNULL;
>+ val->anonymous_namespace = type_in_anonymous_namespace_p (type);
> *slot = val;
> for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
> /* For now record only polymorphic types. other are
>@@ -289,7 +302,7 @@ dump_odr_type (FILE *f, odr_type t, int
> unsigned int i;
> fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
> print_generic_expr (f, t->type, TDF_SLIM);
>- fprintf (f, "\n");
>+ fprintf (f, "%s\n", t->anonymous_namespace ? " (anonymous
>namespace)":"");
> if (TYPE_NAME (t->type))
> {
> fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
>@@ -318,6 +331,8 @@ static void
> dump_type_inheritance_graph (FILE *f)
> {
> unsigned int i;
>+ if (!odr_types_ptr)
>+ return;
> fprintf (f, "\n\nType inheritance graph:\n");
> for (i = 0; i < odr_types.length(); i++)
> {
>@@ -383,7 +398,11 @@ maybe_record_node (vec <cgraph_node *> &
> && !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);
>+ {
>+ pointer_set_insert (cached_polymorphic_call_targets,
>+ target_node);
>+ nodes.safe_push (target_node);
>+ }
> }
>
> /* See if BINFO's type match OTR_TYPE. If so, lookup method
>@@ -430,6 +449,8 @@ record_binfo (vec <cgraph_node *> &nodes
>/* Walking bases that have no virtual method is pointless excercise.
>*/
> if (polymorphic_type_binfo_p (base_binfo))
> record_binfo (nodes, base_binfo, otr_type,
>+ /* In the case of single inheritance, the virtual table
>+ is shared with the outer type. */
> BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo,
> otr_token, inserted,
> matched_vtables);
>@@ -517,16 +538,18 @@ polymorphic_call_target_hasher::remove (
> 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;
>+ if (cached_polymorphic_call_targets)
>+ {
>+ 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.
>*/
>@@ -534,7 +557,8 @@ free_polymorphic_call_targets_hash ()
> static void
>devirt_node_removal_hook (struct cgraph_node *n, void *d
>ATTRIBUTE_UNUSED)
> {
>- if (pointer_set_contains (cached_polymorphic_call_targets, n))
>+ if (cached_polymorphic_call_targets
>+ && pointer_set_contains (cached_polymorphic_call_targets, n))
> free_polymorphic_call_targets_hash ();
> }
>
>@@ -663,4 +687,47 @@ dump_possible_polymorphic_call_targets (
> fprintf (f, "\n");
> }
>
>+
>+/* Return true if N can be possibly target of a polymorphic call of
>+ OTR_TYPE/OTR_TOKEN. */
>+
>+bool
>+possible_polymorphic_call_target_p (tree otr_type,
>+ HOST_WIDE_INT otr_token,
>+ struct cgraph_node *n)
>+{
>+ vec <cgraph_node *> targets;
>+ unsigned int i;
>+
>+ if (!odr_hash.is_created ())
>+ return true;
>+ targets = possible_polymorphic_call_targets (otr_type, otr_token);
>+ for (i = 0; i < targets.length (); i++)
>+ if (n == targets[i])
>+ return true;
>+ return false;
>+}
>+
>+
>+/* After callgraph construction new external nodes may appear.
>+ Add them into the graph. */
>+
>+void
>+update_type_inheritance_graph (void)
>+{
>+ struct cgraph_node *n;
>+
>+ if (!odr_hash.is_created ())
>+ return;
>+ free_polymorphic_call_targets_hash ();
>+ timevar_push (TV_IPA_INHERITANCE);
>+ /* 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)
>+ && !n->symbol.definition
>+ && symtab_real_symbol_p ((symtab_node)n))
>+ get_odr_type (method_class_type (TREE_TYPE (n->symbol.decl)),
>true);
>+ timevar_pop (TV_IPA_INHERITANCE);
>+}
> #include "gt-ipa-devirt.h"
