* 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.

	* g++.dg/ipa/type-inheritance-1.C: New testcase.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@201836 138bc75d-0d04-0410-961f-82ee72b054a4

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