ipa-devirt.c TLC

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.

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.

Jan Hubicka <hubicka@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"

> 
> 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)

Very many duplicate input files are not an issue, since I identify the ODR
types and handle them only by leaders.  

To get things working well in practice (not in worst case) I use the query
cache.  The purpose of query cache is to re-use the target lists when same
virutal call appears in program many times.  The cache tokens passed to users
allows them to not walk the same list many times when the work depends only on
callees (as it does for dead code removal).

So to trigger the qudaratic case you need to introduce something like 1000
classes inheriting each other and each overwriting the method and then call
with type of each of them (so you have 1000 different calls). Then the
call target query cache will have 1+2+..1000 entries.
Worse yet, make the first baseclass to have 1000 methods and you can trigger
linear walks in the gimple_get_virt_method_for_binfo linear slowness. Of course
here you will generate quadratically sized vtables into the binary.

I made simple script constructing this and we died in FE (binfos are quadratic
already and we have non-linear walks on them). So I declared it premature
optimization and decided to get things correct first.

The simple way around is to start returning empty list once call target cache
is, say 100*number of virtual methods in unit.

The mainline version with patch enabling it on LTO (I wait for approval of the
ODR patch that makes use of VTABLE manglings) I get the overall overhead of
call target analysis and walks in unreachable code removal on Firefox under 2%.
Vast majority goes to constructor folding that is called from
gimple_get_virt_method_for_binfo.  Sensible speedup would be to reconstruct
vectors of virtual methods from vtables instead of walking the vtables
everywhere, but for that I would like to change all the binfo walks we have in
middle-end, so I would like to cleanup and fix existing code a bit first.

Finally the cache can be made smaller (linear to vtable size in case of single)
inheritance by simply making it to return partial vectors and have list of
outer type to contain the list of inner type.  It means that I will need to
invent my own type for return value of possible_polymorphic_call_targets and
iterators on that + some smarter way to tell passes calling me when they
do redundant work.

If you preffer to have the limit on cache size now, I can push out a patch.

Honza