* ipa-devirt.c (odr_type_d): Add field all_derivations_known.

	(type_all_derivations_known_p): New predicate.
	(type_all_ctors_visible_p): New predicate.
	(type_possibly_instantiated_p): New predicate.
	(get_odr_type): Compute all_derivations_known.
	(dump_odr_type): Dump the flag.
	(maybe_record_type): Cleanup.
	(record_target_from_binfo): Add bases_to_consider array;
	record bases for types w/o instances and skip CXX destructor.
	(possible_polymorphic_call_targets_1): Add bases_to_consider
	and consider_construction parameters; check if type may
	have instance.
	(get_polymorphic_call_info): Set maybe_in_construction to true
	when we know nothing.
	(record_targets_from_bases): Skip CXX destructors; they are
	never called for types in construction.
	(possible_polymorphic_call_targets): Do not record target when
	type may not have instance.

	* g++.dg/ipa/devirt-31.C: New testcase.



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

1 files changed, 146 insertions, 27 deletions

diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c
index ce724a5147a..eab7ecdb8c7 100644
--- a/gcc/ipa-devirt.c
+++ b/gcc/ipa-devirt.c
@@ -162,6 +162,8 @@ struct GTY(()) odr_type_d
   int id;
   /* Is it in anonymous namespace? */
   bool anonymous_namespace;
+  /* Do we know about all derivations of given type?  */
+  bool all_derivations_known;
 };
 
 
@@ -180,6 +182,61 @@ polymorphic_type_binfo_p (tree binfo)
   return BINFO_VTABLE (TYPE_BINFO (BINFO_TYPE (binfo)));
 }
 
+/* Return TRUE if all derived types of T are known and thus
+   we may consider the walk of derived type complete.
+
+   This is typically true only for final anonymous namespace types and types
+   defined within functions (that may be COMDAT and thus shared across units,
+   but with the same set of derived types).  */
+
+static bool
+type_all_derivations_known_p (tree t)
+{
+  if (TYPE_FINAL_P (t))
+    return true;
+  if (flag_ltrans)
+    return false;
+  if (type_in_anonymous_namespace_p (t))
+    return true;
+  return (decl_function_context (TYPE_NAME (t)) != NULL);
+}
+
+/* Return TURE if type's constructors are all visible.  */
+
+static bool
+type_all_ctors_visible_p (tree t)
+{
+  return !flag_ltrans
+	 && cgraph_state >= CGRAPH_STATE_CONSTRUCTION
+	 /* We can not always use type_all_derivations_known_p.
+	    For function local types we must assume case where
+	    the function is COMDAT and shared in between units. 
+
+	    TODO: These cases are quite easy to get, but we need
+	    to keep track of C++ privatizing via -Wno-weak
+	    as well as the  IPA privatizing.  */
+	 && type_in_anonymous_namespace_p (t);
+}
+
+/* Return TRUE if type may have instance.  */
+
+static bool
+type_possibly_instantiated_p (tree t)
+{
+  tree vtable;
+  varpool_node *vnode;
+
+  /* TODO: Add abstract types here.  */
+  if (!type_all_ctors_visible_p (t))
+    return true;
+
+  vtable = BINFO_VTABLE (TYPE_BINFO (t));
+  if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
+    vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
+  vnode = varpool_get_node (vtable);
+  return vnode && vnode->definition;
+}
+
 /* One Definition Rule hashtable helpers.  */
 
 struct odr_hasher 
@@ -439,6 +496,7 @@ get_odr_type (tree type, bool insert)
       val->bases = vNULL;
       val->derived_types = vNULL;
       val->anonymous_namespace = type_in_anonymous_namespace_p (type);
+      val->all_derivations_known = type_all_derivations_known_p (type);
       *slot = val;
       for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
 	/* For now record only polymorphic types. other are
@@ -469,7 +527,8 @@ 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, "%s\n", t->anonymous_namespace ? " (anonymous namespace)":"");
+  fprintf (f, "%s", t->anonymous_namespace ? " (anonymous namespace)":"");
+  fprintf (f, "%s\n", t->all_derivations_known ? " (derivations known)":"");
   if (TYPE_NAME (t->type))
     {
       fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
@@ -710,14 +769,16 @@ maybe_record_node (vec <cgraph_node *> &nodes,
 	}
     }
   else if (completep
-	   && !type_in_anonymous_namespace_p
-		 (method_class_type (TREE_TYPE (target))))
+	   && (!type_in_anonymous_namespace_p
+		 (DECL_CONTEXT (target))
+	       || flag_ltrans))
     *completep = false;
 }
 
 /* See if BINFO's type match OUTER_TYPE.  If so, lookup 
    BINFO of subtype of OTR_TYPE at OFFSET and in that BINFO find
-   method in vtable and insert method to NODES array.
+   method in vtable and insert method to NODES array
+   or BASES_TO_CONSIDER if this array is non-NULL.
    Otherwise recurse to base BINFOs.
    This match what get_binfo_at_offset does, but with offset
    being unknown.
@@ -736,6 +797,7 @@ maybe_record_node (vec <cgraph_node *> &nodes,
 
 static void
 record_target_from_binfo (vec <cgraph_node *> &nodes,
+			  vec <tree> *bases_to_consider,
 			  tree binfo,
 			  tree otr_type,
 			  vec <tree> &type_binfos,
@@ -795,13 +857,19 @@ record_target_from_binfo (vec <cgraph_node *> &nodes,
 	    return;
 	}
       gcc_assert (inner_binfo);
-      if (!pointer_set_insert (matched_vtables, BINFO_VTABLE (inner_binfo)))
+      if (bases_to_consider
+	  ? !pointer_set_contains (matched_vtables, BINFO_VTABLE (inner_binfo))
+	  : !pointer_set_insert (matched_vtables, BINFO_VTABLE (inner_binfo)))
 	{
 	  bool can_refer;
 	  tree target = gimple_get_virt_method_for_binfo (otr_token,
 							  inner_binfo,
 							  &can_refer);
-	  maybe_record_node (nodes, target, inserted, can_refer, completep);
+	  if (!bases_to_consider)
+	    maybe_record_node (nodes, target, inserted, can_refer, completep);
+	  /* Destructors are never called via construction vtables.  */
+	  else if (!target || !DECL_CXX_DESTRUCTOR_P (target))
+	    bases_to_consider->safe_push (target);
 	}
       return;
     }
@@ -810,7 +878,7 @@ record_target_from_binfo (vec <cgraph_node *> &nodes,
   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_target_from_binfo (nodes, base_binfo, otr_type,
+      record_target_from_binfo (nodes, bases_to_consider, base_binfo, otr_type,
 				type_binfos, 
 				otr_token, outer_type, offset, inserted,
 				matched_vtables, anonymous, completep);
@@ -822,7 +890,11 @@ record_target_from_binfo (vec <cgraph_node *> &nodes,
    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.
-   Clear COMPLETEP if unreferable target is found.  */
+   Clear COMPLETEP if unreferable target is found.
+ 
+   If CONSIDER_CONSTURCTION is true, record to BASES_TO_CONSDIER
+   all cases where BASE_SKIPPED is true (because the base is abstract
+   class).  */
 
 static void
 possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
@@ -833,23 +905,39 @@ possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
 				     HOST_WIDE_INT otr_token,
 				     tree outer_type,
 				     HOST_WIDE_INT offset,
-				     bool *completep)
+				     bool *completep,
+				     vec <tree> &bases_to_consider,
+				     bool consider_construction)
 {
   tree binfo = TYPE_BINFO (type->type);
   unsigned int i;
   vec <tree> type_binfos = vNULL;
-
-  record_target_from_binfo (nodes, binfo, otr_type, type_binfos, otr_token,
-			    outer_type, offset,
-			    inserted, matched_vtables,
-			    type->anonymous_namespace, completep);
+  bool possibly_instantiated = type_possibly_instantiated_p (type->type);
+
+  /* We may need to consider types w/o instances because of possible derived
+     types using their methods either directly or via construction vtables.
+     We are safe to skip them when all derivations are known, since we will
+     handle them later.
+     This is done by recording them to BASES_TO_CONSIDER array.  */
+  if (possibly_instantiated || consider_construction)
+    {
+      record_target_from_binfo (nodes,
+				(!possibly_instantiated
+				 && type_all_derivations_known_p (type->type))
+				? &bases_to_consider : NULL,
+				binfo, otr_type, type_binfos, otr_token,
+				outer_type, offset,
+				inserted, matched_vtables,
+				type->anonymous_namespace, completep);
+    }
   type_binfos.release ();
   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, outer_type, offset, completep);
+					 otr_token, outer_type, offset, completep,
+					 bases_to_consider, consider_construction);
 }
 
 /* Cache of queries for polymorphic call targets.
@@ -1232,7 +1320,7 @@ get_polymorphic_call_info (tree fndecl,
   context->offset = 0;
   base_pointer = OBJ_TYPE_REF_OBJECT (ref);
   context->maybe_derived_type = true;
-  context->maybe_in_construction = false;
+  context->maybe_in_construction = true;
 
   /* Walk SSA for outer object.  */
   do 
@@ -1433,7 +1521,8 @@ record_targets_from_bases (tree otr_type,
 	  tree target = gimple_get_virt_method_for_binfo (otr_token,
 							  base_binfo,
 							  &can_refer);
-	  maybe_record_node (nodes, target, inserted, can_refer, completep);
+	  if (!target || ! DECL_CXX_DESTRUCTOR_P (target))
+	    maybe_record_node (nodes, target, inserted, can_refer, completep);
 	  pointer_set_insert (matched_vtables, BINFO_VTABLE (base_binfo));
 	}
     }
@@ -1487,6 +1576,7 @@ possible_polymorphic_call_targets (tree otr_type,
   pointer_set_t *inserted;
   pointer_set_t *matched_vtables;
   vec <cgraph_node *> nodes = vNULL;
+  vec <tree> bases_to_consider = vNULL;
   odr_type type, outer_type;
   polymorphic_call_target_d key;
   polymorphic_call_target_d **slot;
@@ -1494,6 +1584,7 @@ possible_polymorphic_call_targets (tree otr_type,
   tree binfo, target;
   bool complete;
   bool can_refer;
+  bool skipped = false;
 
   /* If ODR is not initialized, return empty incomplete list.  */
   if (!odr_hash.is_created ())
@@ -1539,9 +1630,6 @@ possible_polymorphic_call_targets (tree otr_type,
     }
   /* We need to update our hiearchy if the type does not exist.  */
   outer_type = get_odr_type (context.outer_type, true);
-  /* If outer and inner type match, there are no bases to see.  */
-  if (type == outer_type)
-    context.maybe_in_construction = false;
   /* If the type is complete, there are no derivations.  */
   if (TYPE_FINAL_P (outer_type->type))
     context.maybe_derived_type = false;
@@ -1602,7 +1690,10 @@ possible_polymorphic_call_targets (tree otr_type,
       target = NULL;
     }
 
-  maybe_record_node (nodes, target, inserted, can_refer, &complete);
+  /* Destructors are never called through construction virtual tables,
+     because the type is always known.  */
+  if (target && DECL_CXX_DESTRUCTOR_P (target))
+    context.maybe_in_construction = false;
 
   if (target)
     {
@@ -1611,8 +1702,15 @@ possible_polymorphic_call_targets (tree otr_type,
       if (DECL_FINAL_P (target))
 	context.maybe_derived_type = false;
     }
+
+  /* If OUTER_TYPE is abstract, we know we are not seeing its instance.  */
+  if (type_possibly_instantiated_p (outer_type->type))
+    maybe_record_node (nodes, target, inserted, can_refer, &complete);
   else
-    gcc_assert (!complete);
+    {
+      skipped = true;
+      gcc_assert (in_lto_p || context.maybe_derived_type);
+    }
 
   pointer_set_insert (matched_vtables, BINFO_VTABLE (binfo));
 
@@ -1621,7 +1719,7 @@ possible_polymorphic_call_targets (tree otr_type,
     {
       /* For anonymous namespace types we can attempt to build full type.
 	 All derivations must be in this unit (unless we see partial unit).  */
-      if (!type->anonymous_namespace || flag_ltrans)
+      if (!type->all_derivations_known)
 	complete = false;
       for (i = 0; i < outer_type->derived_types.length(); i++)
 	possible_polymorphic_call_targets_1 (nodes, inserted,
@@ -1629,15 +1727,36 @@ possible_polymorphic_call_targets (tree otr_type,
 					     otr_type,
 					     outer_type->derived_types[i],
 					     otr_token, outer_type->type,
-					     context.offset, &complete);
+					     context.offset, &complete,
+					     bases_to_consider,
+					     context.maybe_in_construction);
     }
 
   /* Finally walk bases, if asked to.  */
   (*slot)->nonconstruction_targets = nodes.length();
+
+  /* Destructors are never called through construction virtual tables,
+     because the type is always known.  One of entries may be cxa_pure_virtual
+     so look to at least two of them.  */
+  if (context.maybe_in_construction)
+    for (i =0 ; i < MIN (nodes.length (), 2); i++)
+      if (DECL_CXX_DESTRUCTOR_P (nodes[i]->decl))
+	context.maybe_in_construction = false;
   if (context.maybe_in_construction)
-    record_targets_from_bases (otr_type, otr_token, outer_type->type,
-			       context.offset, nodes, inserted,
-			       matched_vtables, &complete);
+    {
+      if (type != outer_type
+	  && (!skipped
+	      || (context.maybe_derived_type
+	          && !type_all_derivations_known_p (outer_type->type))))
+	record_targets_from_bases (otr_type, otr_token, outer_type->type,
+				   context.offset, nodes, inserted,
+				   matched_vtables, &complete);
+      if (skipped)
+        maybe_record_node (nodes, target, inserted, can_refer, &complete);
+      for (i = 0; i < bases_to_consider.length(); i++)
+        maybe_record_node (nodes, bases_to_consider[i], inserted, can_refer, &complete);
+    }
+  bases_to_consider.release();
 
   (*slot)->targets = nodes;
   (*slot)->complete = complete;