Re: [RFC] Bare bones of virtual call tracking

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
I guess I understand you now about the offsets.  I do not need to update token,
right?  Here is updated and somewhat more complette patch (now I can get list
of possible targets and use it to prune the callgraph)
I also added sanity check that ipa-cp devirtualization actually picks one
of targets from my list.

Honza

Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 0)
+++ ipa-devirt.c	(revision 0)
@@ -0,0 +1,359 @@
+/* Basic IPA optimizations and utilities.
+   Copyright (C) 2003-2013 Free Software Foundation, Inc.
+
+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/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "cgraph.h"
+#include "tree-pass.h"
+#include "gimple.h"
+#include "ggc.h"
+#include "flags.h"
+#include "pointer-set.h"
+#include "target.h"
+#include "tree-iterator.h"
+#include "pointer-set.h"
+#include "hash-table.h"
+#include "params.h"
+#include "tree-pretty-print.h"
+#include "diagnostic.h"
+
+struct odr_type_d
+{
+  int id;
+  vec<tree> types;
+  pointer_set_t *types_set;
+  vec<struct odr_type_d *> bases;
+  vec<struct odr_type_d *> derived_types;
+  vec<struct cgraph_node *> methods;
+};
+
+typedef odr_type_d *odr_type;
+
+/* One Definition Rule hashtable helpers.  */
+
+struct odr_hasher 
+{
+  typedef odr_type_d value_type;
+  typedef odr_type_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_TYPE.  */
+
+inline hashval_t
+odr_hasher::hash (const value_type *odr_type)
+{
+  hashval_t hash = 0;
+  tree t = odr_type->types[0];
+  while (t)
+    {
+      gcc_assert (TREE_CODE (t) != TYPE_DECL);
+
+      /* Hash the names.  */
+      if (TREE_CODE (t) == IDENTIFIER_NODE)
+	hash = iterative_hash_hashval_t (hash, htab_hash_pointer (t));
+      else if (DECL_P (t))
+        {
+	  gcc_checking_assert (TREE_CODE (DECL_NAME (t)) == IDENTIFIER_NODE);
+	  hash = iterative_hash_hashval_t (hash, htab_hash_pointer (DECL_NAME (t)));
+	  t = DECL_CONTEXT (t);
+        }
+
+      /* Look into type names.  */
+      else if (TYPE_P (t))
+	{
+	  t = TYPE_MAIN_VARIANT (t);
+
+	  /* Anonymous namespaces must be unique.  */
+	  if (TYPE_STUB_DECL (t) && !!TREE_PUBLIC (TYPE_STUB_DECL (t)))
+	    return iterative_hash_hashval_t (hash, htab_hash_pointer (TYPE_STUB_DECL (t)));
+	  /* Skip internal types.  */
+	  gcc_assert (TYPE_NAME (t));
+	  if (TYPE_NAME (t))
+	    {
+	      gcc_assert (TREE_CODE (DECL_NAME (TYPE_NAME (t))) == IDENTIFIER_NODE);
+	      hash = iterative_hash_hashval_t (hash, htab_hash_pointer (DECL_NAME (TYPE_NAME (t))));
+	    }
+	  t = TYPE_CONTEXT (t);
+	}
+    }
+  return hash;
+}
+
+/* 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 *t2)
+{
+  bool same;
+  if (t1->types[0] == t2->types[0])
+    return true;
+  same = types_same_for_odr (t1->types[0], t2->types[0]);
+#if 0
+  if (!same
+      && odr_hasher::hash (t1) == odr_hasher::hash (t2))
+    {
+      TREE_NO_WARNING (t2->types[0]) = 1;
+      if (TYPE_CANONICAL (t1->types[0]) == TYPE_CANONICAL (t2->types[0]))
+	fprintf (stderr, "Mismatch\n");
+      else
+	fprintf (stderr, "Canonical Mismatch\n");
+      debug_tree (t1->types[0]);
+      debug_tree (t2->types[0]);
+    }
+#endif
+  return same;
+}
+
+/* Free a phi operation structure VP.  */
+
+inline void
+odr_hasher::remove (value_type *v)
+{
+  v->types.release ();
+  v->bases.release ();
+  v->methods.release ();
+  free (v);
+}
+
+/* ODR type hash.  */
+typedef hash_table <odr_hasher> odr_hash_type;
+odr_hash_type odr_hash;
+vec <odr_type> odr_types;
+
+/* Get ODR type hash entry for TYPE.  */
+odr_type
+get_odr_type (tree type)
+{
+  odr_type_d key;
+  odr_type_d **slot;
+  odr_type val;
+  hashval_t hash;
+
+  type = TYPE_MAIN_VARIANT (type);
+  key.types = vNULL;
+  key.types.safe_push (type);
+  hash = odr_hasher::hash (&key);
+  slot = odr_hash.find_slot_with_hash (&key, hash, INSERT);
+  if (*slot)
+    {
+      val = *slot;
+      key.types.release ();
+      if (!pointer_set_insert (val->types_set, type))
+	{
+	  gcc_assert (in_lto_p);
+	  val->types.safe_push (type);
+	  if (!types_compatible_p (val->types[0], type)
+	      && warning_at (DECL_SOURCE_LOCATION (type), 0,
+			     "type %qD violate one definition rule  ",
+			     type))
+	    inform (DECL_SOURCE_LOCATION (val->types[0]),
+		    "the inconsistent declaration of same name");
+	}
+    }
+  else
+    {
+      tree binfo = TYPE_BINFO (type);
+      unsigned int i;
+
+      val = XCNEW (odr_type_d);
+      val->types = key.types;
+      val->types_set = pointer_set_create ();
+      val->bases = vNULL;
+      val->derived_types = vNULL;
+      val->methods = vNULL;
+      pointer_set_insert (val->types_set, type);
+      *slot = val;
+      for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
+	{
+	  odr_type base = get_odr_type (BINFO_TYPE (BINFO_BASE_BINFO (binfo, i)));
+	  base->derived_types.safe_push (val);
+	  val->bases.safe_push (base);
+	}
+      /* First record bases, then add into array so ids are increasing.  */
+      val->id = odr_types.length();
+      odr_types.safe_push (val);
+    }
+  return val;
+}
+
+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->types[0], TDF_SLIM);
+  fprintf (f, " hash: %li canonical: %i\n", (long)odr_hasher::hash (t), TYPE_UID (TYPE_CANONICAL (t->types[0])));
+  if (TYPE_NAME (t->types[0]))
+    {
+      fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
+	       DECL_SOURCE_FILE (TYPE_NAME (t->types[0])),
+	       DECL_SOURCE_LINE (TYPE_NAME (t->types[0])));
+    }
+  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->methods.length())
+    {
+      fprintf (f, "%*s methods:\n", indent * 2, "");
+      for (i = 0; i < t->methods.length(); i++)
+	fprintf (f, "  %*s %s/%i\n", indent * 2, "",
+		 cgraph_node_name (t->methods[i]),
+		 t->methods[i]->symbol.order);
+    }
+  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");
+}
+
+void
+dump_odrs (FILE *f)
+{
+  unsigned int i;
+  for (i = 0; i < odr_types.length(); i++)
+    {
+      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.length() > 1)
+	{
+	  unsigned int j;
+	  fprintf (f, "Duplicate tree types for odr type %i\n", i);
+	  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.
+   Lookup this pointer and get its type.    */
+tree
+method_class_type (tree t)
+{
+  tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t));
+  return TREE_TYPE (first_parm_type);
+}
+
+void
+possible_virtual_call_targets_1 (vec <cgraph_node *> &nodes,
+				 pointer_set_t *inserted,
+				 tree otr_type,
+				 odr_type type,
+			         HOST_WIDE_INT offset,
+			         HOST_WIDE_INT otr_token)
+{
+  tree binfo = get_binfo_at_offset (TYPE_BINFO (type->types[0]),
+				    offset, otr_type);
+  tree target;
+  struct cgraph_node *target_node;
+  unsigned int i;
+
+  gcc_assert (binfo);
+  target = gimple_get_virt_method_for_binfo (otr_token, binfo);
+  if (target
+      && (target_node = cgraph_get_node (target)) != NULL
+      && symtab_real_symbol_p ((symtab_node)target_node)
+      && !pointer_set_insert (inserted, target_node))
+    {
+      nodes.safe_push (target_node);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  %s/%i\n",
+		 cgraph_node_name (target_node),
+		 target_node->symbol.order);
+    }
+  for (i = 0; i < type->derived_types.length(); i++)
+    possible_virtual_call_targets_1 (nodes, inserted,
+				     otr_type,
+				     type->derived_types[i],
+				     offset, otr_token);
+}
+
+vec <cgraph_node *>
+possible_virtual_call_targets (tree otr_type,
+			       HOST_WIDE_INT offset,
+			       HOST_WIDE_INT otr_token)
+{
+  pointer_set_t *inserted = pointer_set_create ();
+  odr_type type = get_odr_type (otr_type);
+  vec <cgraph_node *> nodes=vNULL;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Targets for virtual call of type id %i:", type->id);
+      print_generic_expr (dump_file, otr_type, TDF_SLIM);
+      fprintf (dump_file, " with offset %i and token %i\n", (int)offset, (int)otr_token);
+    }
+  possible_virtual_call_targets_1 (nodes, inserted, otr_type, type, offset, otr_token);
+
+  pointer_set_destroy (inserted);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\n");
+  return nodes;
+}
+
+void
+ipa_devirt_init (void)
+{
+  struct cgraph_node *n;
+
+  if (odr_hash.is_created ())
+    return;
+  odr_hash.create (23);
+  odr_types = vNULL;
+  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)))->methods.safe_push (n);
+#if 0
+  FOR_EACH_FUNCTION (n)
+    for (e = n->indirect_calls; e; e = e->next_callee)
+      if (e->indirect_info->polymorphic)
+        possible_virtual_call_targets (e->indirect_info->otr_type,
+				       e->indirect_info->offset,
+				       e->indirect_info->otr_token);
+#endif
+  if (cgraph_dump_file)
+    dump_odrs (cgraph_dump_file);
+}
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 201640)
+++ ipa-utils.h	(working copy)
@@ -45,6 +45,9 @@
 vec<cgraph_node_ptr> ipa_get_nodes_in_cycle (struct cgraph_node *);
 int ipa_reverse_postorder (struct cgraph_node **);
 tree get_base_var (tree);
+void ipa_devirt_init (void);
+vec <cgraph_node *>
+possible_virtual_call_targets (tree, HOST_WIDE_INT, HOST_WIDE_INT);
 
 
 #endif  /* GCC_IPA_UTILS_H  */
Index: ipa.c
===================================================================
--- ipa.c	(revision 201640)
+++ ipa.c	(working copy)
@@ -225,6 +225,8 @@
 #endif
   if (file)
     fprintf (file, "\nReclaiming functions:");
+  if (optimize && flag_devirtualize)
+    ipa_devirt_init ();
 #ifdef ENABLE_CHECKING
   FOR_EACH_FUNCTION (node)
     gcc_assert (!node->symbol.aux);
@@ -243,8 +245,8 @@
 	  && !node->symbol.in_other_partition
 	  && (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node)
 	      /* Keep around virtual functions for possible devirtualization.  */
-	      || (before_inlining_p
-		  && DECL_VIRTUAL_P (node->symbol.decl))))
+	      /*|| (before_inlining_p
+		  && DECL_VIRTUAL_P (node->symbol.decl))*/))
 	{
 	  gcc_assert (!node->global.inlined_to);
 	  pointer_set_insert (reachable, node);
@@ -318,7 +320,32 @@
 		    pointer_set_insert (reachable, e->callee);
 		  enqueue_node ((symtab_node) e->callee, &first, reachable);
 		}
+	      /* Keep alive possible targets for devirtualization.
+		 Even after inlining we want to keep the possible targets in the boundary,
+		 so late passes can still produce direct call even if chance for inlining
+		 is lost.  We however remove the actual function bodies.  */
+	      if (optimize && flag_devirtualize)
+		for (e = cnode->indirect_calls; e; e = e->next_callee)
+		  if (e->indirect_info->polymorphic)
+		    {
+		       unsigned int i;
+		       vec <cgraph_node *>targets = possible_virtual_call_targets (e->indirect_info->otr_type,
+										   e->indirect_info->offset,
+										   e->indirect_info->otr_token);
+		       for (i = 0; i < targets.length(); i++)
+			 {
+			    struct cgraph_node *n = targets[i];
 
+			    if (n->symbol.definition
+				&& before_inlining_p
+				&& (!DECL_EXTERNAL (n->symbol.decl)
+				    || n->symbol.alias))
+			      pointer_set_insert (reachable, n);
+			    enqueue_node ((symtab_node) n, &first, reachable);
+			 }
+		       targets.release ();
+		    }
+
 	      /* When inline clone exists, mark body to be preserved so when removing
 		 offline copy of the function we don't kill it.  */
 	      if (cnode->global.inlined_to)
@@ -1407,54 +1430,10 @@
   bool something_changed = false;
   int i;
   gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
+  struct cgraph_node *n,*n2;
+  int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
+  bool node_map_initialized = false;
 
-  /* Produce speculative calls: we saved common traget from porfiling into
-     e->common_target_id.  Now, at link time, we can look up corresponding
-     function node and produce speculative call.  */
-  if (in_lto_p)
-    {
-      struct cgraph_edge *e;
-      struct cgraph_node *n,*n2;
-
-      init_node_map (false);
-      FOR_EACH_DEFINED_FUNCTION (n)
-	{
-	  bool update = false;
-
-	  for (e = n->indirect_calls; e; e = e->next_callee)
-	    if (e->indirect_info->common_target_id)
-	      {
-		n2 = find_func_by_profile_id (e->indirect_info->common_target_id);
-		if (n2)
-		  {
-		    if (dump_file)
-		      {
-			fprintf (dump_file, "Indirect call -> direct call from"
-				 " other module %s/%i => %s/%i, prob %3.2f\n",
-				 xstrdup (cgraph_node_name (n)), n->symbol.order,
-				 xstrdup (cgraph_node_name (n2)), n2->symbol.order,
-				 e->indirect_info->common_target_probability
-				 / (float)REG_BR_PROB_BASE);
-		      }
-		    cgraph_turn_edge_to_speculative
-		      (e, n2,
-		       apply_scale (e->count,
-				    e->indirect_info->common_target_probability),
-		       apply_scale (e->frequency,
-				    e->indirect_info->common_target_probability));
-		    update = true;
-		  }
-		else
-		  if (dump_file)
-		    fprintf (dump_file, "Function with profile-id %i not found.\n",
-			     e->indirect_info->common_target_id);
-	       }
-	     if (update)
-	       inline_update_overall_summary (n);
-	   }
-	del_node_map ();
-    }
-
   if (dump_file)
     dump_histogram (dump_file, histogram);
   for (i = 0; i < (int)histogram.length (); i++)
Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 201640)
+++ ipa-prop.c	(working copy)
@@ -38,6 +38,7 @@
 #include "data-streamer.h"
 #include "tree-streamer.h"
 #include "params.h"
+#include "ipa-utils.h"
 
 /* Intermediate information about a parameter that is only useful during the
    run of ipa_analyze_node and is not kept afterwards.  */
@@ -2259,6 +2260,21 @@
   struct inline_edge_summary *es = inline_edge_summary (ie);
   bool unreachable = false;
 
+  /* Sanity check that we actually have the virtual call in list of targets.  */
+  if (ie->indirect_info->polymorphic
+      && flag_devirtualize && cgraph_get_node (target))
+    {
+      unsigned int i;
+      vec <cgraph_node *>targets = possible_virtual_call_targets (ie->indirect_info->otr_type,
+								  ie->indirect_info->offset,
+								  ie->indirect_info->otr_token);
+      for (i = 0; i < targets.length(); i++)
+	if (targets[i]->symbol.decl == target)
+	  break;
+      gcc_assert (i != targets.length());
+      targets.release ();
+    }
+
   if (TREE_CODE (target) == ADDR_EXPR)
     target = TREE_OPERAND (target, 0);
   if (TREE_CODE (target) != FUNCTION_DECL)