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: Context sensitive type inheritance graph walking


Hi,
it took me a while to get back to this patch (especially because I wanted to understand
the issues with virtual inheritance first).  Here is updated version that should reflect
your comments.
I will do some extra testing tomorrow and plan to commit it.

Bootstrapped/regtested x86_64-linux.

Honza

        * cgraph.c (cgraph_create_indirect_edge): Use get_polymorphic_call_info.
        * cgraph.h (cgraph_indirect_call_info): Add outer_type, maybe_in_construction
        and maybe_derived_type.
        * ipa-utils.h (ipa_polymorphic_call_context): New structure.
        (ipa_dummy_polymorphic_call_context): New global var.
        (possible_polymorphic_call_targets): Add context paramter.
        (dump_possible_polymorphic_call_targets): Likewise; update
        wrappers.
        (possible_polymorphic_call_target_p): Likewise.
        (get_polymorphic_call_info): New function.
        * ipa-devirt.c (ipa_dummy_polymorphic_call_context): New function.
        (add_type_duplicate): Remove forgotten debug output.
        (method_class_type): Add sanity check.
        (maybe_record_node): Add FINALP parameter.
        (record_binfo): Add OUTER_TYPE and OFFSET; walk the inner
        by info by get_binfo_at_offset.
        (possible_polymorphic_call_targets_1): Add OUTER_TYPE/OFFSET parameters;
        pass them to record-binfo.
        (polymorphic_call_target_d): Add context and FINAL.
        (polymorphic_call_target_hasher::hash): Hash context.
        (polymorphic_call_target_hasher::equal): Compare context.
        (free_polymorphic_call_targets_hash):
        (get_class_context): New function.
        (contains_type_p): New function.
        (get_polymorphic_call_info): New function.
        (walk_bases): New function.
        (possible_polymorphic_call_targets): Add context parameter; honnor it.
        (dump_possible_polymorphic_call_targets): Dump context.
        (possible_polymorphic_call_target_p): Add context.
        (update_type_inheritance_graph): Update comment.s
        (ipa_set_jf_known_type): Assert that compoentn type is known.
        (ipa_note_param_call): Do not tamper with offsets.
        (ipa_analyze_indirect_call_uses): When offset is being changed; clear
        outer type.
        (update_indirect_edges_after_inlining): Likewise.
        (ipa_write_indirect_edge_info): Stream new fields.
        (ipa_read_indirect_edge_info): Stream in new fields.

        * ipa/devirt9.C: Verify that the optimization happens already before.
        whole-program.

Index: cgraph.c
===================================================================
--- cgraph.c	(revision 204996)
+++ cgraph.c	(working copy)
@@ -959,16 +959,26 @@ cgraph_create_indirect_edge (struct cgra
       && (target = gimple_call_fn (call_stmt))
       && virtual_method_call_p (target))
     {
-      tree type = obj_type_ref_class (target);
+      tree otr_type;
+      HOST_WIDE_INT otr_token;
+      ipa_polymorphic_call_context context;
 
+      get_polymorphic_call_info (caller->decl,
+				 target,
+				 &otr_type, &otr_token,
+				 &context);
 
       /* Only record types can have virtual calls.  */
-      gcc_assert (TREE_CODE (type) == RECORD_TYPE);
+      gcc_assert (TREE_CODE (otr_type) == RECORD_TYPE);
+      edge->indirect_info->polymorphic = true;
       edge->indirect_info->param_index = -1;
-      edge->indirect_info->otr_token
-	 = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (target));
-      edge->indirect_info->otr_type = type;
-      edge->indirect_info->polymorphic = 1;
+      edge->indirect_info->otr_token = otr_token;
+      edge->indirect_info->otr_type = otr_type;
+      edge->indirect_info->outer_type = context.outer_type;
+      edge->indirect_info->offset = context.offset;
+      edge->indirect_info->maybe_in_construction
+	 = context.maybe_in_construction;
+      edge->indirect_info->maybe_derived_type = context.maybe_derived_type;
     }
 
   edge->next_callee = caller->indirect_calls;
Index: cgraph.h
===================================================================
--- cgraph.h	(revision 204996)
+++ cgraph.h	(working copy)
@@ -434,7 +434,7 @@ struct GTY(()) cgraph_indirect_call_info
   /* OBJ_TYPE_REF_TOKEN of a polymorphic call (if polymorphic is set).  */
   HOST_WIDE_INT otr_token;
   /* Type of the object from OBJ_TYPE_REF_OBJECT. */
-  tree otr_type;
+  tree otr_type, outer_type;
   /* Index of the parameter that is called.  */
   int param_index;
   /* ECF flags determined from the caller.  */
@@ -455,6 +455,8 @@ struct GTY(()) cgraph_indirect_call_info
   /* When the previous bit is set, this one determines whether the destination
      is loaded from a parameter passed by reference. */
   unsigned by_ref : 1;
+  unsigned int maybe_in_construction : 1;
+  unsigned int maybe_derived_type : 1;
 };
 
 struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) cgraph_edge {
Index: testsuite/g++.dg/ipa/devirt-9.C
===================================================================
--- testsuite/g++.dg/ipa/devirt-9.C	(revision 204996)
+++ testsuite/g++.dg/ipa/devirt-9.C	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-ipa-inline"  } */
+/* { dg-options "-O2 -fdump-ipa-whole-program"  } */
 double foo ();
 struct B
 {
@@ -27,5 +27,7 @@ bar ()
   static C c;
   c.c1 (60, (int) foo ());
 }
-/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target"  "inline"  } } */
-/* { dg-final { cleanup-ipa-dump "inline" } } */
+/* We optimize out this call just after early passes.  Unfortunately
+   this unreachable removal is not logged in dump file.  */
+/* { dg-final { scan-ipa-dump 1 "OBJ_TYPE_REF"  "whole-program"  } } */
+/* { dg-final { cleanup-ipa-dump "whole-program" } } */
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 204996)
+++ ipa-utils.h	(working copy)
@@ -34,6 +34,21 @@ struct ipa_dfs_info {
   PTR aux;
 };
 
+/* Context of polymorphic call.  This is used by ipa-devirt walkers of the
+   type inheritance graph.  */
+struct ipa_polymorphic_call_context {
+  /* The called object appears in an object of type OUTER_TYPE
+     at offset OFFSET.  */
+  HOST_WIDE_INT offset;
+  tree outer_type;
+  /* True if outer object may be in construction or destruction.  */
+  bool maybe_in_construction;
+  /* True if outer object may be of derived type.  */
+  bool maybe_derived_type;
+};
+
+/* Context representing "I know nothing".  */
+extern const ipa_polymorphic_call_context ipa_dummy_polymorphic_call_context;
 
 /* In ipa-utils.c  */
 void ipa_print_order (FILE*, const char *, struct cgraph_node**, int);
@@ -59,13 +74,19 @@ void build_type_inheritance_graph (void)
 void update_type_inheritance_graph (void);
 vec <cgraph_node *>
 possible_polymorphic_call_targets (tree, HOST_WIDE_INT,
+				   ipa_polymorphic_call_context,
 				   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);
+void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT,
+					     const ipa_polymorphic_call_context &);
 bool possible_polymorphic_call_target_p (tree, HOST_WIDE_INT,
+				         const ipa_polymorphic_call_context &,
 					 struct cgraph_node *n);
 tree method_class_type (tree);
+tree get_polymorphic_call_info (tree, tree, tree *,
+				HOST_WIDE_INT *,
+				ipa_polymorphic_call_context *);
 
 /* Return vector containing possible targets of polymorphic call E.
    If FINALP is non-NULL, store true if the list is complette. 
@@ -83,8 +104,27 @@ possible_polymorphic_call_targets (struc
 				   void **cache_token = NULL)
 {
   gcc_checking_assert (e->indirect_info->polymorphic);
+  ipa_polymorphic_call_context context = {e->indirect_info->offset,
+					  e->indirect_info->outer_type,
+					  e->indirect_info->maybe_in_construction,
+					  e->indirect_info->maybe_derived_type};
   return possible_polymorphic_call_targets (e->indirect_info->otr_type,
 					    e->indirect_info->otr_token,
+					    context,
+					    final, cache_token);
+}
+
+/* Same as above but taking OBJ_TYPE_REF as an parameter.  */
+
+inline vec <cgraph_node *>
+possible_polymorphic_call_targets (tree call,
+				   bool *final = NULL,
+				   void **cache_token = NULL)
+{
+  return possible_polymorphic_call_targets (obj_type_ref_class (call),
+					    tree_to_uhwi
+					      (OBJ_TYPE_REF_TOKEN (call)),
+					    ipa_dummy_polymorphic_call_context,
 					    final, cache_token);
 }
 
@@ -94,8 +134,13 @@ inline void
 dump_possible_polymorphic_call_targets (FILE *f, struct cgraph_edge *e)
 {
   gcc_checking_assert (e->indirect_info->polymorphic);
+  ipa_polymorphic_call_context context = {e->indirect_info->offset,
+					  e->indirect_info->outer_type,
+					  e->indirect_info->maybe_in_construction,
+					  e->indirect_info->maybe_derived_type};
   dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type,
-					  e->indirect_info->otr_token);
+					  e->indirect_info->otr_token,
+					  context);
 }
 
 /* Return true if N can be possibly target of a polymorphic call of
@@ -105,8 +150,13 @@ inline bool
 possible_polymorphic_call_target_p (struct cgraph_edge *e,
 				    struct cgraph_node *n)
 {
+  ipa_polymorphic_call_context context = {e->indirect_info->offset,
+					  e->indirect_info->outer_type,
+					  e->indirect_info->maybe_in_construction,
+					  e->indirect_info->maybe_derived_type};
   return possible_polymorphic_call_target_p (e->indirect_info->otr_type,
-					     e->indirect_info->otr_token, n);
+					     e->indirect_info->otr_token,
+					     context, n);
 }
 
 /* Return true if N can be possibly target of a polymorphic call of
@@ -118,7 +168,8 @@ possible_polymorphic_call_target_p (tree
 {
   return possible_polymorphic_call_target_p (obj_type_ref_class (call),
 					     tree_to_uhwi
-						(OBJ_TYPE_REF_TOKEN (call)),
+					       (OBJ_TYPE_REF_TOKEN (call)),
+					     ipa_dummy_polymorphic_call_context,
 					     n);
 }
 #endif  /* GCC_IPA_UTILS_H  */
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 204996)
+++ ipa-devirt.c	(working copy)
@@ -121,6 +121,12 @@ along with GCC; see the file COPYING3.
 #include "gimple.h"
 #include "ipa-inline.h"
 #include "diagnostic.h"
+#include "tree-dfa.h"
+
+/* Dummy polymorphic call context.  */
+
+const ipa_polymorphic_call_context ipa_dummy_polymorphic_call_context
+   = {0, NULL, false, true};
 
 /* Pointer set of all call targets appearing in the cache.  */
 static pointer_set_t *cached_polymorphic_call_targets;
@@ -292,8 +298,6 @@ add_type_duplicate (odr_type val, tree t
 	    inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
 		    "a type with the same name but different layout is "
 		    "defined in another translation unit");
-	    debug_tree (BINFO_VTABLE (TYPE_BINFO (type)));
-	    debug_tree (BINFO_VTABLE (TYPE_BINFO (val->type)));
 	  if (cgraph_dump_file)
 	    {
 	      fprintf (cgraph_dump_file, "ODR violation or merging or ODR type bug?\n");
@@ -522,6 +526,7 @@ tree
 method_class_type (tree t)
 {
   tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t));
+  gcc_assert (TREE_CODE (t) == METHOD_TYPE);
 
   return TREE_TYPE (first_parm_type);
 }
@@ -555,34 +560,50 @@ build_type_inheritance_graph (void)
   timevar_pop (TV_IPA_INHERITANCE);
 }
 
-/* If TARGET has associated node, record it in the NODES array.  */
+/* If TARGET has associated node, record it in the NODES array.
+   if TARGET can not be inserted (for example because its body was
+   already removed and there is no way to refer to it), clear COMPLETEP.  */
 
 static void
 maybe_record_node (vec <cgraph_node *> &nodes,
-		   tree target, pointer_set_t *inserted)
+		   tree target, pointer_set_t *inserted,
+		   bool *completep)
 {
   struct cgraph_node *target_node;
   enum built_in_function fcode;
 
-  if (target
+  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
+      || (fcode = DECL_FUNCTION_CODE (target))
+	  == BUILT_IN_UNREACHABLE
+      || fcode == BUILT_IN_TRAP)
+    return;
+
+  target_node = cgraph_get_node (target);
+
+  if (target_node != NULL
       && (TREE_PUBLIC (target)
 	  || target_node->definition)
       && symtab_real_symbol_p (target_node))
     {
-      pointer_set_insert (cached_polymorphic_call_targets,
-			  target_node);
-      nodes.safe_push (target_node);
+      gcc_assert (!target_node->global.inlined_to);
+      gcc_assert (symtab_real_symbol_p (target_node));
+      if (!pointer_set_insert (inserted, target))
+	{
+	  pointer_set_insert (cached_polymorphic_call_targets,
+			      target_node);
+	  nodes.safe_push (target_node);
+	}
     }
+  else if (completep
+	   && !type_in_anonymous_namespace_p
+		 (method_class_type (TREE_TYPE (target))))
+    *completep = true;
 }
 
-/* See if BINFO's type match OTR_TYPE.  If so, lookup method
-   in vtable of TYPE_BINFO and insert method to NODES array.
+/* 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.
    Otherwise recurse to base BINFOs.
    This match what get_binfo_at_offset does, but with offset
    being unknown.
@@ -593,20 +614,23 @@ maybe_record_node (vec <cgraph_node *> &
    otherwise it is binfo of BINFO's type.
 
    MATCHED_VTABLES tracks virtual tables we already did lookup
-   for virtual function in.
+   for virtual function in. INSERTED tracks nodes we already
+   inserted.
 
    ANONYMOUS is true if BINFO is part of anonymous namespace.
   */
 
 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,
-	      bool anonymous)
+record_target_from_binfo (vec <cgraph_node *> &nodes,
+			  tree binfo,
+			  tree otr_type,
+			  tree type_binfo,
+			  HOST_WIDE_INT otr_token,
+			  tree outer_type,
+			  HOST_WIDE_INT offset,
+			  pointer_set_t *inserted,
+			  pointer_set_t *matched_vtables,
+			  bool anonymous)
 {
   tree type = BINFO_TYPE (binfo);
   int i;
@@ -614,14 +638,15 @@ record_binfo (vec <cgraph_node *> &nodes
 
   gcc_checking_assert (BINFO_VTABLE (type_binfo));
 
-  if (types_same_for_odr (type, otr_type)
-      && !pointer_set_insert (matched_vtables, BINFO_VTABLE (type_binfo)))
+  if (types_same_for_odr (type, outer_type))
     {
+      tree inner_binfo = get_binfo_at_offset (type_binfo,
+					      offset, otr_type);
       /* For types in anonymous namespace first check if the respective vtable
 	 is alive. If not, we know the type can't be called.  */
       if (!flag_ltrans && anonymous)
 	{
-	  tree vtable = BINFO_VTABLE (type_binfo);
+	  tree vtable = BINFO_VTABLE (inner_binfo);
 	  struct varpool_node *vnode;
 
 	  if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
@@ -630,9 +655,13 @@ record_binfo (vec <cgraph_node *> &nodes
 	  if (!vnode || !vnode->definition)
 	    return;
 	}
-      tree target = gimple_get_virt_method_for_binfo (otr_token, type_binfo);
-      if (target)
-	maybe_record_node (nodes, target, inserted);
+      gcc_assert (inner_binfo);
+      if (!pointer_set_insert (matched_vtables, BINFO_VTABLE (inner_binfo)))
+	{
+	  tree target = gimple_get_virt_method_for_binfo (otr_token, inner_binfo);
+	  if (target)
+	    maybe_record_node (nodes, target, inserted, NULL);
+	}
       return;
     }
 
@@ -640,12 +669,13 @@ record_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_binfo (nodes, base_binfo, otr_type,
-		    /* In the case of single inheritance, the virtual table
-		       is shared with the outer type.  */
-		    BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo,
-		    otr_token, inserted,
-		    matched_vtables, anonymous);
+      record_target_from_binfo (nodes, base_binfo, otr_type,
+				/* In the case of single inheritance,
+				   the virtual table is shared with
+				   the outer type.  */
+				BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo,
+				otr_token, outer_type, offset, inserted,
+				matched_vtables, anonymous);
 }
      
 /* Lookup virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
@@ -659,19 +689,23 @@ possible_polymorphic_call_targets_1 (vec
 				     pointer_set_t *matched_vtables,
 				     tree otr_type,
 				     odr_type type,
-				     HOST_WIDE_INT otr_token)
+				     HOST_WIDE_INT otr_token,
+				     tree outer_type,
+				     HOST_WIDE_INT offset)
 {
   tree binfo = TYPE_BINFO (type->type);
   unsigned int i;
 
-  record_binfo (nodes, binfo, otr_type, binfo, otr_token, inserted,
-	        matched_vtables, type->anonymous_namespace);
+  record_target_from_binfo (nodes, binfo, otr_type, binfo, otr_token,
+			    outer_type, offset,
+			    inserted, matched_vtables,
+			    type->anonymous_namespace);
   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);
+					 otr_token, outer_type, offset);
 }
 
 /* Cache of queries for polymorphic call targets.
@@ -682,9 +716,11 @@ possible_polymorphic_call_targets_1 (vec
 
 struct polymorphic_call_target_d
 {
-  odr_type type;
   HOST_WIDE_INT otr_token;
+  ipa_polymorphic_call_context context;
+  odr_type type;
   vec <cgraph_node *> targets;
+  bool final;
 };
 
 /* Polymorphic call target cache helpers.  */
@@ -703,8 +739,17 @@ struct polymorphic_call_target_hasher
 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);
+  hashval_t hash;
+
+  hash = iterative_hash_host_wide_int
+	  (odr_query->otr_token,
+	   odr_query->type->id);
+  hash = iterative_hash_hashval_t (TYPE_UID (odr_query->context.outer_type),
+				   hash);
+  hash = iterative_hash_host_wide_int (odr_query->context.offset, hash);
+  return iterative_hash_hashval_t
+	    (((int)odr_query->context.maybe_in_construction << 1)
+	     | (int)odr_query->context.maybe_derived_type, hash);
 }
 
 /* Compare cache entries T1 and T2.  */
@@ -713,7 +758,12 @@ 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;
+  return (t1->type == t2->type && t1->otr_token == t2->otr_token
+	  && t1->context.offset == t2->context.offset
+	  && t1->context.outer_type == t2->context.outer_type
+	  && t1->context.maybe_in_construction
+	      == t2->context.maybe_in_construction
+	  && t1->context.maybe_derived_type == t2->context.maybe_derived_type);
 }
 
 /* Remove entry in polymorphic call target cache hash.  */
@@ -754,6 +804,337 @@ devirt_node_removal_hook (struct cgraph_
     free_polymorphic_call_targets_hash ();
 }
 
+/* CONTEXT->OUTER_TYPE is a type of memory object where object of EXPECTED_TYPE
+   is contained at CONTEXT->OFFSET.  Walk the memory representation of
+   CONTEXT->OUTER_TYPE and find the outermost class type that match
+   EXPECTED_TYPE or contain EXPECTED_TYPE as a base.  Update CONTEXT
+   to represent it.
+
+   For example when CONTEXT represents type
+   class A
+     {
+       int a;
+       class B b;
+     }
+   and we look for type at offset sizeof(int), we end up with B and offset 0.
+   If the same is produced by multiple inheritance, we end up with A and offset
+   sizeof(int). 
+
+   If we can not find corresponding class, give up by setting
+   CONTEXT->OUTER_TYPE to EXPECTED_TYPE and CONTEXT->OFFSET to NULL. 
+   Return true when lookup was sucesful.  */
+
+static bool
+get_class_context (ipa_polymorphic_call_context *context,
+		   tree expected_type)
+{
+  tree type = context->outer_type;
+  HOST_WIDE_INT offset = context->offset;
+
+  /* Find the sub-object the constant actually refers to and mark whether it is
+     an artificial one (as opposed to a user-defined one).  */
+  while (true)
+    {
+      HOST_WIDE_INT pos, size;
+      tree fld;
+
+      /* On a match, just return what we found.  */
+      if (TREE_CODE (type) == TREE_CODE (expected_type)
+	  && types_same_for_odr (type, expected_type))
+	{
+	  gcc_assert (offset == 0);
+	  return true;
+	}
+
+      /* Walk fields and find corresponding on at OFFSET.  */
+      if (TREE_CODE (type) == RECORD_TYPE)
+	{
+	  for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
+	    {
+	      if (TREE_CODE (fld) != FIELD_DECL)
+		continue;
+
+	      pos = int_bit_position (fld);
+	      size = tree_to_uhwi (DECL_SIZE (fld));
+	      if (pos <= offset && (pos + size) > offset)
+		break;
+	    }
+
+	  if (!fld)
+	    goto give_up;
+
+	  type = TREE_TYPE (fld);
+	  offset -= pos;
+	  /* DECL_ARTIFICIAL represents a basetype.  */
+	  if (!DECL_ARTIFICIAL (fld))
+	    {
+	      context->outer_type = type;
+	      context->offset = offset;
+	      /* As soon as we se an field containing the type,
+		 we know we are not looking for derivations.  */
+	      context->maybe_derived_type = false;
+	    }
+	}
+      else if (TREE_CODE (type) == ARRAY_TYPE)
+	{
+	  tree subtype = TREE_TYPE (type);
+
+	  /* Give up if we don't know array size.  */
+	  if (!tree_fits_shwi_p (TYPE_SIZE (subtype))
+	      || !tree_to_shwi (TYPE_SIZE (subtype)) <= 0)
+	    goto give_up;
+	  offset = offset % tree_to_shwi (TYPE_SIZE (subtype));
+	  type = subtype;
+	  context->outer_type = type;
+	  context->offset = offset;
+	  context->maybe_derived_type = false;
+	}
+      /* Give up on anything else.  */
+      else
+	goto give_up;
+    }
+
+  /* If we failed to find subtype we look for, give up and fall back to the
+     most generic query.  */
+give_up:
+  context->outer_type = expected_type;
+  context->offset = 0;
+  context->maybe_derived_type = true;
+  return false;
+}
+
+/* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET.  */
+
+static bool
+contains_type_p (tree outer_type, HOST_WIDE_INT offset,
+		 tree otr_type)
+{
+  ipa_polymorphic_call_context context = {offset, outer_type,
+					  false, true};
+  return get_class_context (&context, otr_type);
+}
+
+/* Given REF call in FNDECL, determine class of the polymorphic
+   call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT.
+   Return pointer to object described by the context  */
+
+tree
+get_polymorphic_call_info (tree fndecl,
+			   tree ref,
+			   tree *otr_type,
+			   HOST_WIDE_INT *otr_token,
+			   ipa_polymorphic_call_context *context)
+{
+  tree base_pointer;
+  *otr_type = obj_type_ref_class (ref);
+  *otr_token = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (ref));
+
+  /* Set up basic info in case we find nothing interesting in the analysis.  */
+  context->outer_type = *otr_type;
+  context->offset = 0;
+  base_pointer = OBJ_TYPE_REF_OBJECT (ref);
+  context->maybe_derived_type = true;
+  context->maybe_in_construction = false;
+
+  /* Walk SSA for outer object.  */
+  do 
+    {
+      if (TREE_CODE (base_pointer) == SSA_NAME
+	  && !SSA_NAME_IS_DEFAULT_DEF (base_pointer)
+	  && SSA_NAME_DEF_STMT (base_pointer)
+	  && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
+	{
+	  base_pointer = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (base_pointer));
+	  STRIP_NOPS (base_pointer);
+	}
+      else if (TREE_CODE (base_pointer) == ADDR_EXPR)
+	{
+	  HOST_WIDE_INT size, max_size;
+	  HOST_WIDE_INT offset2;
+	  tree base = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0),
+					       &offset2, &size, &max_size);
+
+	  /* If this is a varying address, punt.  */
+	  if ((TREE_CODE (base) == MEM_REF || DECL_P (base))
+	      && max_size != -1
+	      && max_size == size)
+	    {
+	      /* We found dereference of a pointer.  Type of the pointer
+		 and MEM_REF is meaningless, but we can look futher.  */
+	      if (TREE_CODE (base) == MEM_REF)
+		{
+		  base_pointer = TREE_OPERAND (base, 0);
+		  context->offset
+		     += offset2 + mem_ref_offset (base).low * BITS_PER_UNIT;
+		  context->outer_type = NULL;
+		}
+	      /* We found base object.  In this case the outer_type
+		 is known.  */
+	      else if (DECL_P (base))
+		{
+		  context->outer_type = TREE_TYPE (base);
+		  gcc_assert (!POINTER_TYPE_P (context->outer_type));
+
+		  /* Only type inconsistent programs can have otr_type that is
+		     not part of outer type.  */
+		  if (!contains_type_p (context->outer_type,
+					context->offset, *otr_type))
+		    return base_pointer;
+		  context->offset += offset2;
+		  base_pointer = NULL;
+		  /* Make very conservative assumption that all objects
+		     may be in construction. 
+		     TODO: ipa-prop already contains code to tell better. 
+		     merge it later.  */
+		  context->maybe_in_construction = true;
+		  context->maybe_derived_type = false;
+		  return base_pointer;
+		}
+	      else
+		break;
+	    }
+	  else
+	    break;
+	}
+      else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR
+	       && tree_fits_uhwi_p (TREE_OPERAND (base_pointer, 1)))
+	{
+	  context->offset += tree_to_shwi (TREE_OPERAND (base_pointer, 1))
+		    * BITS_PER_UNIT;
+	  base_pointer = TREE_OPERAND (base_pointer, 0);
+	}
+      else
+	break;
+    }
+  while (true);
+
+  /* Try to determine type of the outer object.  */
+  if (TREE_CODE (base_pointer) == SSA_NAME
+      && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
+      && TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL)
+    {
+      /* See if parameter is THIS pointer of a method.  */
+      if (TREE_CODE (TREE_TYPE (fndecl)) == METHOD_TYPE
+	  && SSA_NAME_VAR (base_pointer) == DECL_ARGUMENTS (fndecl))
+	{
+	  context->outer_type = TREE_TYPE (TREE_TYPE (base_pointer));
+	  gcc_assert (TREE_CODE (context->outer_type) == RECORD_TYPE);
+
+	  /* Dynamic casting has possibly upcasted the type
+	     in the hiearchy.  In this case outer type is less
+	     informative than inner type and we should forget
+	     about it.  */
+	  if (!contains_type_p (context->outer_type, context->offset,
+				*otr_type))
+	    {
+	      context->outer_type = NULL;
+	      return base_pointer;
+	    }
+
+	  /* If the function is constructor or destructor, then
+	     the type is possibly in consturction, but we know
+	     it is not derived type.  */
+	  if (DECL_CXX_CONSTRUCTOR_P (fndecl)
+	      || DECL_CXX_DESTRUCTOR_P (fndecl))
+	    {
+	      context->maybe_in_construction = true;
+	      context->maybe_derived_type = false;
+	    }
+	  else
+	    {
+	      context->maybe_derived_type = true;
+	      context->maybe_in_construction = false;
+	    }
+	  return base_pointer;
+	}
+      /* Non-PODs passed by value are really passed by invisible
+	 reference.  In this case we also know the type of the
+	 object.  */
+      if (DECL_BY_REFERENCE (SSA_NAME_VAR (base_pointer)))
+	{
+	  context->outer_type = TREE_TYPE (TREE_TYPE (base_pointer));
+	  gcc_assert (!POINTER_TYPE_P (context->outer_type));
+	  /* Only type inconsistent programs can have otr_type that is
+	     not part of outer type.  */
+	  if (!contains_type_p (context->outer_type, context->offset,
+			        *otr_type))
+	    { 
+	      context->outer_type = NULL;
+	      gcc_unreachable ();
+	      return base_pointer;
+	    }
+	  context->maybe_derived_type = false;
+	  context->maybe_in_construction = false;
+          return base_pointer;
+	}
+    }
+  /* TODO: There are multiple ways to derive a type.  For instance
+     if BASE_POINTER is passed to an constructor call prior our refernece.
+     We do not make this type of flow sensitive analysis yet.  */
+  return base_pointer;
+}
+
+/* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
+   Lookup their respecitve virtual methods for OTR_TOKEN and OTR_TYPE
+   and insert them to NODES.
+
+   MATCHED_VTABLES and INSERTED is used to avoid duplicated work.  */
+
+static void
+record_targets_from_bases (tree otr_type,
+			   HOST_WIDE_INT otr_token,
+			   tree outer_type,
+			   HOST_WIDE_INT offset,
+			   vec <cgraph_node *> nodes,
+			   pointer_set_t *inserted,
+			   pointer_set_t *matched_vtables,
+			   bool *completep)
+{
+  while (true)
+    {
+      HOST_WIDE_INT pos, size;
+      tree base_binfo;
+      tree fld;
+
+      if (types_same_for_odr (outer_type, otr_type))
+	return;
+
+      for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld))
+	{
+	  if (TREE_CODE (fld) != FIELD_DECL)
+	    continue;
+
+	  pos = int_bit_position (fld);
+	  size = tree_to_shwi (DECL_SIZE (fld));
+	  if (pos <= offset && (pos + size) > offset)
+	    break;
+	}
+      /* Within a class type we should always find correcponding fields.  */
+      gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE);
+
+      /* Nonbasetypes should have been stripped by outer_class_type.  */
+      gcc_assert (DECL_ARTIFICIAL (fld));
+
+      outer_type = TREE_TYPE (fld);
+      offset -= pos;
+
+      base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type),
+					offset, otr_type);
+      gcc_assert (base_binfo);
+      if (!pointer_set_insert (matched_vtables, BINFO_VTABLE (base_binfo)))
+	{
+	  tree target = gimple_get_virt_method_for_binfo (otr_token, base_binfo);
+	  if (target)
+	    maybe_record_node (nodes, target, inserted, completep);
+	  /* The only way method in anonymous namespace can become unreferable
+	     is that it has been fully optimized out.  */
+	  else if (flag_ltrans || !type_in_anonymous_namespace_p (outer_type))
+	    *completep = false;
+	  pointer_set_insert (matched_vtables, BINFO_VTABLE (base_binfo));
+	}
+    }
+}
+
 /* When virtual table is removed, we may need to flush the cache.  */
 
 static void
@@ -767,8 +1148,14 @@ devirt_variable_node_removal_hook (struc
 }
 
 /* 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. 
+   OTR_TYPE caling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET.
+   If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containig
+   OTR_TYPE and include their virtual method.  This is useful for types
+   possibly in construction or destruction where the virtual table may
+   temporarily change to one of base types.  INCLUDE_DERIVER_TYPES make
+   us to walk the inheritance graph for all derivations.
+
+   If COMPLETEP 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.
@@ -780,32 +1167,44 @@ devirt_variable_node_removal_hook (struc
 vec <cgraph_node *>
 possible_polymorphic_call_targets (tree otr_type,
 			           HOST_WIDE_INT otr_token,
-			           bool *finalp,
+				   ipa_polymorphic_call_context context,
+			           bool *completep,
 			           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;
+  odr_type type, outer_type;
   polymorphic_call_target_d key;
   polymorphic_call_target_d **slot;
   unsigned int i;
   tree binfo, target;
+  bool final;
 
-  if (finalp)
-    *finalp = false;
+  type = get_odr_type (otr_type, true);
 
-  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;
+  /* Lookup the outer class type we want to walk.  */
+  if (context.outer_type)
+    get_class_context (&context, otr_type);
 
-  /* 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;
+  /* We now canonicalize our query, so we do not need extra hashtable entries.  */
+
+  /* Without outer type, we have no use for offset.  Just do the
+     basic search from innter type  */
+  if (!context.outer_type)
+    {
+      context.outer_type = otr_type;
+      context.offset = 0;
+    }
+  /* 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 final, there are no derivations.  */
+  if (TYPE_FINAL_P (outer_type->type))
+    context.maybe_derived_type = false;
 
   /* Initialize query cache.  */
   if (!cached_polymorphic_call_targets)
@@ -824,43 +1223,75 @@ possible_polymorphic_call_targets (tree
   /* Lookup cached answer.  */
   key.type = type;
   key.otr_token = otr_token;
+  key.context = context;
   slot = polymorphic_call_target_hash.find_slot (&key, INSERT);
   if (cache_token)
    *cache_token = (void *)*slot;
   if (*slot)
-    return (*slot)->targets;
+    {
+      if (completep)
+	*completep = (*slot)->final;
+      return (*slot)->targets;
+    }
+
+  final = true;
 
   /* Do actual search.  */
   timevar_push (TV_IPA_VIRTUAL_CALL);
   *slot = XCNEW (polymorphic_call_target_d);
   if (cache_token)
-   *cache_token = (void *)*slot;
+    *cache_token = (void *)*slot;
   (*slot)->type = type;
   (*slot)->otr_token = otr_token;
+  (*slot)->context = context;
 
   inserted = pointer_set_create ();
   matched_vtables = pointer_set_create ();
 
   /* First see virtual method of type itself.  */
 
-  binfo = TYPE_BINFO (type->type);
+  binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type),
+			       context.offset, otr_type);
   target = gimple_get_virt_method_for_binfo (otr_token, binfo);
   if (target)
-    maybe_record_node (nodes, target, inserted);
+    {
+      maybe_record_node (nodes, target, inserted, &final);
+
+      /* In the case we get final method, we don't need 
+	 to walk derivations.  */
+      if (DECL_FINAL_P (target))
+	context.maybe_derived_type = false;
+    }
+  /* The only way method in anonymous namespace can become unreferable
+     is that it has been fully optimized out.  */
+  else if (flag_ltrans || !type->anonymous_namespace)
+    final = false;
   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.  */
+  /* Next walk bases, if asked to.  */
+  if (context.maybe_in_construction)
+    record_targets_from_bases (otr_type, otr_token, outer_type->type,
+			       context.offset, nodes, inserted,
+			       matched_vtables, &final);
 
-  /* 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);
+  /* Finally walk recursively all derived types.  */
+  if (context.maybe_derived_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)
+	final = false;
+      for (i = 0; i < outer_type->derived_types.length(); i++)
+	possible_polymorphic_call_targets_1 (nodes, inserted,
+					     matched_vtables,
+					     otr_type, outer_type->derived_types[i],
+					     otr_token, outer_type->type,
+					     context.offset);
+    }
   (*slot)->targets = nodes;
+  (*slot)->final = final;
+  if (completep)
+    *completep = final;
 
   pointer_set_destroy (inserted);
   pointer_set_destroy (matched_vtables);
@@ -872,8 +1303,9 @@ possible_polymorphic_call_targets (tree
 
 void
 dump_possible_polymorphic_call_targets (FILE *f,
-				    tree otr_type,
-				    HOST_WIDE_INT otr_token)
+					tree otr_type,
+					HOST_WIDE_INT otr_token,
+					const ipa_polymorphic_call_context &ctx)
 {
   vec <cgraph_node *> targets;
   bool final;
@@ -883,16 +1315,25 @@ dump_possible_polymorphic_call_targets (
   if (!type)
     return;
   targets = possible_polymorphic_call_targets (otr_type, otr_token,
+					       ctx,
 					       &final);
-  fprintf (f, "Targets of polymorphic call of type %i ", type->id);
+  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)");
+  fprintf (f, " token %i\n"
+	   "    Contained in type:",
+	   (int)otr_token);
+  print_generic_expr (f, ctx.outer_type, TDF_SLIM);
+  fprintf (f, " at offset "HOST_WIDE_INT_PRINT_DEC"\n"
+	   "    %s%s%s\n      ",
+	   ctx.offset,
+	   final ? "This is full list." :
+	   "This is partial list; extra targets may be defined in other units.",
+	   ctx.maybe_in_construction ? " (base types included)" : "",
+	   ctx.maybe_derived_type ? " (derived types included)" : "");
   for (i = 0; i < targets.length (); i++)
     fprintf (f, " %s/%i", targets[i]->name (),
 	     targets[i]->order);
-  fprintf (f, "\n");
+  fprintf (f, "\n\n");
 }
 
 
@@ -902,17 +1343,25 @@ dump_possible_polymorphic_call_targets (
 bool
 possible_polymorphic_call_target_p (tree otr_type,
 				    HOST_WIDE_INT otr_token,
+				    const ipa_polymorphic_call_context &ctx,
 				    struct cgraph_node *n)
 {
   vec <cgraph_node *> targets;
   unsigned int i;
+  enum built_in_function fcode;
   bool final;
 
+  if (TREE_CODE (TREE_TYPE (n->decl)) == FUNCTION_TYPE
+      && ((fcode = DECL_FUNCTION_CODE (n->decl))
+	  == BUILT_IN_UNREACHABLE
+          || fcode == BUILT_IN_TRAP))
+    return true;
+
   if (!odr_hash.is_created ())
     return true;
-  targets = possible_polymorphic_call_targets (otr_type, otr_token, &final);
+  targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx, &final);
   for (i = 0; i < targets.length (); i++)
-    if (n == targets[i])
+    if (symtab_semantically_equivalent_p (n, targets[i]))
       return true;
 
   /* At a moment we allow middle end to dig out new external declarations
@@ -935,7 +1384,7 @@ update_type_inheritance_graph (void)
     return;
   free_polymorphic_call_targets_hash ();
   timevar_push (TV_IPA_INHERITANCE);
-  /* We reconstruct the graph starting of types of all methods seen in the
+  /* We reconstruct the graph starting from types of all methods seen in the
      the unit.  */
   FOR_EACH_FUNCTION (n)
     if (DECL_VIRTUAL_P (n->decl)
Index: ipa-prop.c
===================================================================
--- ipa-prop.c	(revision 204996)
+++ ipa-prop.c	(working copy)
@@ -386,6 +386,7 @@ ipa_set_jf_known_type (struct ipa_jump_f
   jfunc->value.known_type.offset = offset,
   jfunc->value.known_type.base_type = base_type;
   jfunc->value.known_type.component_type = component_type;
+  gcc_assert (component_type);
 }
 
 /* Set JFUNC to be a copy of another jmp (to be used by jump function
@@ -1739,8 +1740,6 @@ ipa_note_param_call (struct cgraph_node
 
   cs = cgraph_edge (node, stmt);
   cs->indirect_info->param_index = param_index;
-  cs->indirect_info->offset = 0;
-  cs->indirect_info->polymorphic = 0;
   cs->indirect_info->agg_contents = 0;
   cs->indirect_info->member_ptr = 0;
   return cs;
@@ -1837,6 +1836,8 @@ ipa_analyze_indirect_call_uses (struct c
 				   NULL, &by_ref))
     {
       struct cgraph_edge *cs = ipa_note_param_call (node, index, call);
+      if (cs->indirect_info->offset != offset)
+	cs->indirect_info->outer_type = NULL;
       cs->indirect_info->offset = offset;
       cs->indirect_info->agg_contents = 1;
       cs->indirect_info->by_ref = by_ref;
@@ -1934,6 +1935,8 @@ ipa_analyze_indirect_call_uses (struct c
       && parm_preserved_before_stmt_p (&parms_ainfo[index], call, rec))
     {
       struct cgraph_edge *cs = ipa_note_param_call (node, index, call);
+      if (cs->indirect_info->offset != offset)
+	cs->indirect_info->outer_type = NULL;
       cs->indirect_info->offset = offset;
       cs->indirect_info->agg_contents = 1;
       cs->indirect_info->member_ptr = 1;
@@ -2770,6 +2773,8 @@ update_indirect_edges_after_inlining (st
 	  else
 	    {
 	      ici->param_index = ipa_get_jf_ancestor_formal_id (jfunc);
+	      if (ipa_get_jf_ancestor_offset (jfunc))
+	        ici->outer_type = NULL;
 	      ici->offset += ipa_get_jf_ancestor_offset (jfunc);
 	    }
 	}
@@ -4084,12 +4089,15 @@ ipa_write_indirect_edge_info (struct out
   bp_pack_value (&bp, ii->agg_contents, 1);
   bp_pack_value (&bp, ii->member_ptr, 1);
   bp_pack_value (&bp, ii->by_ref, 1);
+  bp_pack_value (&bp, ii->maybe_in_construction, 1);
+  bp_pack_value (&bp, ii->maybe_derived_type, 1);
   streamer_write_bitpack (&bp);
 
   if (ii->polymorphic)
     {
       streamer_write_hwi (ob, ii->otr_token);
       stream_write_tree (ob, ii->otr_type, true);
+      stream_write_tree (ob, ii->outer_type, true);
     }
 }
 
@@ -4111,10 +4119,13 @@ ipa_read_indirect_edge_info (struct lto_
   ii->agg_contents = bp_unpack_value (&bp, 1);
   ii->member_ptr = bp_unpack_value (&bp, 1);
   ii->by_ref = bp_unpack_value (&bp, 1);
+  ii->maybe_in_construction = bp_unpack_value (&bp, 1);
+  ii->maybe_derived_type = bp_unpack_value (&bp, 1);
   if (ii->polymorphic)
     {
       ii->otr_token = (HOST_WIDE_INT) streamer_read_hwi (ib);
       ii->otr_type = stream_read_tree (ib, data_in);
+      ii->outer_type = stream_read_tree (ib, data_in);
     }
 }
 


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