This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC] Bare bones of virtual call tracking


Hi,
here is current patch that implements the inheritance graph construction and
reachable function lookup.  I think I now understand binfos right.  I added
record_binfo that basically does what get_binfo_at_offset does without
considering the offset (i.e. sort of get_binfo_at_any_offset) and I can sanity
check that ipa-cp never does transformation that I do not anticipate.

I also now cache the result, so the lookup is not compile time hog.  The patch
looks promising, pushing down memory use of firefox LTO build from 10GB to
3.4GB(!) and time from 680seconds to 380 seconds producing somewhat better
binary.  This is because unreachable virtual methods are eliminated early (at
compile time) reducing need for a lot of streaming.   I will produce some
stats.

The template problem is important though. First I think get_binfo_at_any_offset
in mainline will lead to wrong code confusing templates.

Second it makes different types to coincide in my graph.  While it makes my
analysis just more conservative, it is not good.  For start, to fix the
get_binfo_at_any_offset wrong code issues, how can I figure out if give
type is template instantiation?  
As a temporary hack I usppose I can rely on assembler name of virtual table
to be unique for each templated class?

Honza

Index: cgraph.c
===================================================================
--- cgraph.c	(revision 201708)
+++ cgraph.c	(working copy)
@@ -925,12 +925,24 @@
 {
   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
 						   count, freq);
+  tree target;
 
   edge->indirect_unknown_callee = 1;
   initialize_inline_failed (edge);
 
   edge->indirect_info = cgraph_allocate_init_indirect_info ();
   edge->indirect_info->ecf_flags = ecf_flags;
+  if (call_stmt
+      && (target = gimple_call_fn (call_stmt))
+      && TREE_CODE (target) == OBJ_TYPE_REF)
+    {
+      edge->indirect_info->param_index = -1;
+      edge->indirect_info->otr_token
+	 = tree_low_cst (OBJ_TYPE_REF_TOKEN (target), 1);
+      edge->indirect_info->otr_type
+	 = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (target)));
+      edge->indirect_info->polymorphic = 1;
+    }
 
   edge->next_callee = caller->indirect_calls;
   if (caller->indirect_calls)
Index: tree.c
===================================================================
--- tree.c	(revision 201708)
+++ tree.c	(working copy)
@@ -11835,7 +11835,7 @@
 
   /* 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))
+  if (!in_lto_p && !types_compatible_p (type1, type2))
     return false;
 
 #ifndef ENABLE_CHECKING
Index: ipa-cp.c
===================================================================
--- ipa-cp.c	(revision 201708)
+++ ipa-cp.c	(working copy)
@@ -734,7 +734,8 @@
     }
 
   for (ie = node->indirect_calls; ie; ie = ie->next_callee)
-    if (ie->indirect_info->polymorphic)
+    if (ie->indirect_info->polymorphic
+        && ie->indirect_info->param_index >= 0)
       {
 	gcc_checking_assert (ie->indirect_info->param_index >= 0);
 	ipa_get_parm_lattices (info,
Index: cgraphunit.c
===================================================================
--- cgraphunit.c	(revision 201708)
+++ cgraphunit.c	(working copy)
@@ -236,7 +236,7 @@
     return false;
 
   /* Devirtualization may access these.  */
-  if (DECL_VIRTUAL_P (decl) && optimize)
+  if (DECL_VIRTUAL_P (decl) && optimize && flag_devirtualize)
     return true;
 
   if (DECL_EXTERNAL (decl))
dndex: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 201708)
+++ ipa-utils.h	(working copy)
@@ -36,7 +36,6 @@
 };
 
 
-
 /* 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,16 @@
 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 ipa_devirt_init (void);
+vec <cgraph_node *>
+possible_virtual_call_targets (tree, HOST_WIDE_INT, HOST_WIDE_INT, bool *final = false);
+odr_type get_odr_type (tree, bool insert = false);
+
+
 #endif  /* GCC_IPA_UTILS_H  */
 
 
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 0)
+++ ipa-devirt.c	(revision 0)
@@ -0,0 +1,666 @@
+/* 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"
+#include "ipa-utils.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, derived types
+   and methods.  */
+
+struct GTY(()) odr_type_d
+{
+  /* Unique ID indexing the type in odr_types array.  */
+  int id;
+  /* leader type.  */
+  tree type;
+  /* 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;
+  /* 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 methods of tyhis type seen in unit.  */
+  vec<cgraph_node_ptr> GTY((skip)) methods;
+  /* Is it in anonymous namespace? */
+  bool anonymous_namespace;
+};
+
+
+/* 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 *);
+};
+
+/* Return true if T is in anonymous namespace.  */
+
+static inline bool
+type_in_anonymous_namespace (tree t)
+{
+  return (TYPE_STUB_DECL (t) && !TREE_PUBLIC (TYPE_STUB_DECL (t)));
+}
+
+/* Produce hash based on type name.  */
+
+hashval_t
+hash_type_name (tree t)
+{
+  hashval_t hash = 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_in_anonymous_namespace (t))
+	    return iterative_hash_hashval_t (hash, htab_hash_pointer (TYPE_STUB_DECL (t)));
+	  /* Check that all types are named.  */
+	  gcc_assert (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;
+}
+
+/* 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);
+  if (t1->type == t2)
+    return true;
+  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->methods.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_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;
+  if (*slot)
+    {
+      val = *slot;
+      if (val->type == type)
+	return val;
+      if (!val->types_set)
+        val->types_set = pointer_set_create ();
+      if (!pointer_set_insert (val->types_set, type))
+	{
+	  gcc_assert (in_lto_p);
+	  vec_safe_push (val->types, type);
+	  if (!types_compatible_p (val->type, type)
+	      /* FIXME: template instantiations are not same.  */
+	      && (!DECL_ABSTRACT_ORIGIN (TYPE_NAME (type))
+		  || !DECL_ABSTRACT_ORIGIN (TYPE_NAME (val->type))
+		  || !types_same_for_odr (TYPE_NAME (type),
+					  TYPE_NAME (val->type))))
+	    {
+	      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");
+	      if (cgraph_dump_file)
+		{
+#if 0
+		  fprintf (cgraph_dump_file, "ODR violation? hash %i %i\n",
+			   (int)gimple_canonical_type_hash (val->type),
+			   (int)type);
+#endif
+		  fprintf (cgraph_dump_file, "ODR 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);
+		}
+	    }
+	}
+    }
+  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;
+      val->methods = vNULL;
+      *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)), 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, " %shash: %li canonical: %i\n",
+	   t->anonymous_namespace ? "anonymous_namespace " : "",
+	   (long)odr_hasher::hash (t),
+	   TYPE_UID (TYPE_CANONICAL (t->type)));
+  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->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");
+}
+
+/* Dump all types found in unit.  */
+
+static void
+dump_odrs (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]);
+    }
+  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.
+   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);
+}
+
+/* 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);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  %s/%i\n",
+		 cgraph_node_name (target_node),
+		 target_node->symbol.order);
+    }
+}
+
+/* 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.
+
+   VISITED_BINFOs tracks BINFOS we walked recursively, so
+   we do not need to re-do work on duplicated types.
+   MATCHED_BINFOs tracks BINFOS 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 *visited_binfos,
+	      pointer_set_t *matched_binfos)
+{
+  tree type = BINFO_TYPE (binfo);
+  int i;
+  tree base_binfo;
+
+  /* Avoid too much of duplicate work.  If we already
+     seen this binfo, do nothing.  */
+  if (binfo == type_binfo
+      && pointer_set_insert (visited_binfos, binfo))
+    return;
+
+  gcc_checking_assert (BINFO_VTABLE (type_binfo));
+
+  /* If we already found match in this binfo, we no longer
+     need to look into it.  */
+  if (pointer_set_contains (matched_binfos, BINFO_VTABLE (type_binfo)))
+    return;
+
+  if (types_same_for_odr (type, otr_type)
+      && !pointer_set_insert (matched_binfos, 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;
+    }
+
+  /* Offset 0 indicates the primary base, whose vtable contents are
+     represented in the binfo for the derived class.  */
+  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
+    record_binfo (nodes, base_binfo, otr_type,
+		  BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo,
+		  otr_token, inserted,
+		  visited_binfos, matched_binfos);
+}
+     
+/* 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.
+   VISITED_BINFOS and MATCHED_BINFOS are used to avoid duplicate walking of
+   BINFO base types.  */
+
+static void
+possible_virtual_call_targets_1 (vec <cgraph_node *> &nodes,
+				 pointer_set_t *inserted,
+			         pointer_set_t *visited_binfos,
+			         pointer_set_t *matched_binfos,
+				 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,
+	        visited_binfos, matched_binfos);
+  /* BINFO of individual copies of types do not need to necesarily match.
+     Be sure to walk them all.  */
+  if (type->types)
+    for (i = 0; i < type->types->length(); i++)
+      {
+	tree binfo2 = TYPE_BINFO ((*type->types)[i]);
+	if (binfo2 != binfo)
+	  record_binfo (nodes, binfo2, otr_type, binfo2, otr_token,
+			inserted, visited_binfos, matched_binfos);
+      }
+  for (i = 0; i < type->derived_types.length(); i++)
+    possible_virtual_call_targets_1 (nodes, inserted, visited_binfos,
+				     matched_binfos,
+				     otr_type,
+				     type->derived_types[i],
+				     otr_token);
+}
+
+/* Cache used to match duplicated devirtualization queries.  */
+
+struct virtual_call_target_d
+{
+  odr_type type;
+  HOST_WIDE_INT otr_token;
+  vec <cgraph_node *> targets;
+};
+
+/* Virtual call target cache helpers.  */
+
+struct virtual_call_target_hasher 
+{
+  typedef virtual_call_target_d value_type;
+  typedef virtual_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_TYPE.  */
+
+inline hashval_t
+virtual_call_target_hasher::hash (const value_type *odr_query)
+{
+  return iterative_hash_hashval_t (odr_query->type->id,
+				   odr_query->otr_token);
+}
+
+/* Compare types operations T1 and T2 and return true if they are
+   equivalent.  */
+
+inline bool
+virtual_call_target_hasher::equal (const value_type *t1,
+				   const compare_type *t2)
+{
+  return t1->type == t2->type && t1->otr_token == t2->otr_token;
+}
+
+/* Free a phi operation structure VP.  */
+
+inline void
+virtual_call_target_hasher::remove (value_type *v)
+{
+  v->targets.release ();
+  free (v);
+}
+
+/* ODR query cache.  */
+
+typedef hash_table <virtual_call_target_hasher> virtual_call_target_hash_type;
+static virtual_call_target_hash_type virtual_call_target_hash;
+pointer_set_t *cached_virtual_call_targets;
+
+/* Destroy ODR query cache.  */
+
+static void
+free_virtual_call_targets_hash ()
+{
+  virtual_call_target_hash.dispose ();
+  pointer_set_destroy (cached_virtual_call_targets);
+  cached_virtual_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_virtual_call_targets, n))
+    free_virtual_call_targets_hash ();
+}
+
+/* Return vector containing possible calls of virtual call of type
+   OTR_TYPE caling method OTR_TOKEN with OFFSET.  If FINALp is non-NULL,
+   store true if the list is complette.  */
+
+vec <cgraph_node *>
+possible_virtual_call_targets (tree otr_type,
+			       HOST_WIDE_INT offset,
+			       HOST_WIDE_INT otr_token,
+			       bool *finalp)
+{
+  static struct cgraph_node_hook_list *node_removal_hook_holder;
+  pointer_set_t *inserted;
+  pointer_set_t *visited_binfos;
+  pointer_set_t *matched_binfos;
+  vec <cgraph_node *> nodes=vNULL;
+  odr_type type;
+  virtual_call_target_d key;
+  virtual_call_target_d **slot;
+  unsigned int i;
+  tree binfo, target;
+
+  if (finalp)
+    *finalp = false;
+
+  /* FIXME: For some reason there are types w/o binfo on libxul build.
+     How those can appear in an polymorphic edge?   */
+  if (!TYPE_BINFO (otr_type))
+    return nodes;
+  type = get_odr_type (otr_type, false);
+  if (!type)
+    return nodes;
+
+  if (type->anonymous_namespace && finalp)
+    *finalp = true;
+
+  if (!cached_virtual_call_targets)
+    {
+      cached_virtual_call_targets = pointer_set_create ();
+      virtual_call_target_hash.create (23);
+      if (!node_removal_hook_holder)
+	node_removal_hook_holder =
+	  cgraph_add_node_removal_hook (&devirt_node_removal_hook, NULL);
+    }
+  key.type = type;
+  key.otr_token = otr_token;
+  slot = virtual_call_target_hash.find_slot (&key, INSERT);
+  if (*slot)
+    return (*slot)->targets;
+  *slot = XCNEW (virtual_call_target_d);
+  (*slot)->type = type;
+  (*slot)->otr_token = otr_token;
+
+  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);
+    }
+
+  inserted = pointer_set_create ();
+  visited_binfos = pointer_set_create ();
+  matched_binfos = 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 (visited_binfos, binfo);
+  pointer_set_insert (matched_binfos, binfo);
+  if (type->types)
+    for (i = 0; i < type->types->length(); i++)
+      {
+	tree binfo2 = TYPE_BINFO ((*type->types)[i]);
+	if (binfo2 != binfo)
+	  {
+	    pointer_set_insert (visited_binfos, binfo2);
+	    pointer_set_insert (matched_binfos, binfo2);
+	    target = gimple_get_virt_method_for_binfo (otr_token, binfo2);
+	    if (target)
+	       maybe_record_node (nodes, target, inserted);
+	  }
+      }
+
+  /* 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.  */
+
+  for (i = 0; i < type->derived_types.length(); i++)
+    possible_virtual_call_targets_1 (nodes, inserted, visited_binfos,
+				     matched_binfos,
+				     otr_type, type->derived_types[i], otr_token);
+  (*slot)->targets = nodes;
+
+  pointer_set_destroy (inserted);
+  pointer_set_destroy (visited_binfos);
+  pointer_set_destroy (matched_binfos);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\n");
+  return nodes;
+}
+
+/* Initialize IPA devirt and build inheritance tree graph.  */
+
+void
+ipa_devirt_init (void)
+{
+  struct cgraph_node *n;
+  struct cgraph_edge *e;
+
+  if (odr_hash.is_created ())
+    return;
+  odr_hash.create (23);
+  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)
+	  ->methods.safe_push (n);
+      /* LTO type merging may result in different binfos for same type.
+	 (i.e. one with external vtable, one with internal).  Be sure
+	 to record them all and also diagnoze mismatches.  */
+      if (in_lto_p)
+	for (e = n->indirect_calls; e; e = e->next_callee)
+	  if (e->indirect_info->polymorphic
+	      && e->indirect_info->otr_type
+	      && TYPE_BINFO (e->indirect_info->otr_type))
+	    get_odr_type (e->indirect_info->otr_type, true);
+    }
+  if (cgraph_dump_file)
+    dump_odrs (cgraph_dump_file);
+}
+#include "gt-ipa-devirt.h"
Index: ipa.c
===================================================================
--- ipa.c	(revision 201708)
+++ 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,31 @@
 		    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);
+			 }
+		    }
+
 	      /* 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)
Index: gimple-fold.c
===================================================================
--- gimple-fold.c	(revision 201708)
+++ gimple-fold.c	(working copy)
@@ -3099,9 +3099,8 @@
   tree v, fn, vtable;
 
   vtable = v = BINFO_VTABLE (known_binfo);
-  /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone.  */
-  if (!v)
-    return NULL_TREE;
+  /* We should have found valid binfo with an virtual table.  */
+  gcc_assert (v);
 
   if (TREE_CODE (v) == POINTER_PLUS_EXPR)
     {
@@ -3126,9 +3125,21 @@
   fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), DECL_INITIAL (v),
 			    offset, size, vtable);
   if (!fn || integer_zerop (fn))
-    return NULL_TREE;
-  gcc_assert (TREE_CODE (fn) == ADDR_EXPR
-	      || TREE_CODE (fn) == FDESC_EXPR);
+    {
+      fn = builtin_decl_implicit (BUILT_IN_TRAP);
+      cgraph_get_create_node (fn);
+      return fn;
+    }
+
+  /* On ODR violation, we may get out of range accesses to the vtable.  */
+  if (TREE_CODE (fn) != ADDR_EXPR
+      && TREE_CODE (fn) != FDESC_EXPR)
+    {
+      /*gcc_assert (in_lto_p);*/
+      fn = builtin_decl_implicit (BUILT_IN_TRAP);
+      cgraph_get_create_node (fn);
+      return fn;
+    }
   fn = TREE_OPERAND (fn, 0);
   gcc_assert (TREE_CODE (fn) == FUNCTION_DECL);
 
Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 201708)
+++ 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,22 @@
   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
+      && DECL_FUNCTION_CODE (target) != BUILT_IN_UNREACHABLE
+      && DECL_FUNCTION_CODE (target) != BUILT_IN_TRAP)
+    {
+      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());
+    }
+
   if (TREE_CODE (target) == ADDR_EXPR)
     target = TREE_OPERAND (target, 0);
   if (TREE_CODE (target) != FUNCTION_DECL)
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 201708)
+++ Makefile.in	(working copy)
@@ -1275,6 +1275,7 @@
 	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,10 @@
    $(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) \
+   $(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-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) \
@@ -3780,6 +3785,7 @@
   $(srcdir)/optabs.h $(srcdir)/tree.h $(srcdir)/libfuncs.h $(SYMTAB_H) \
   $(srcdir)/real.h $(srcdir)/function.h $(srcdir)/insn-addr.h $(srcdir)/hwint.h \
   $(srcdir)/fixed-value.h \
+  $(srcdir)/ipa-utils.h \
   $(srcdir)/output.h $(srcdir)/cfgloop.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 \
@@ -3826,7 +3832,7 @@
   $(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,


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]