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: Infrastructure for forward propagation of polymorphic call contexts


Hi,
this is version of patch I comitted after testing at firefox and libreoffice.
It fixes some issues with mixing in non-C++ types and upper-casting.
The number of devirtualizations is now down to 5000 for Firefox, but that
seems more realistic.

Bootstrapped/regtested x86_64-linux, comitted.

Honza

	* ipa-polymorphic-call.c
	(ipa_polymorphic_call_context::restrict_to_inner_class):
	Rename EXPECTED_TYPE to OTR_TYPE; Validate speculation late;
	use speculation_consistent_p to do so; Add CONSDER_BASES
	and CONSIDER_PLACEMENT_NEW parameters.
	(contains_type_p): Add CONSDER_PLACEMENT_NEW and CONSIDER_BASES;
	short circuit obvious cases.
	(ipa_polymorphic_call_context::dump): Improve formatting.
	(ipa_polymorphic_call_context::ipa_polymorphic_call_context): Use
	combine_speculation_with to record speculations; Do not ICE when
	object is located in pointer type decl; do not ICE for methods
	of UNION_TYPE; do not record nonpolymorphic types.
	(ipa_polymorphic_call_context::speculation_consistent_p): New method.
	(ipa_polymorphic_call_context::combine_speculation_with): New method.
	(ipa_polymorphic_call_context::combine_with): New method.
	(ipa_polymorphic_call_context::make_speculative): Move here; use
	combine speculation.
	* cgraph.h (ipa_polymorphic_call_context): Update
	restrict_to_inner_class prototype; add offset_by, make_speculative, 
	combine_with, useless_p, combine_speculation_with and
	speculation_consistent_p methods.
	(ipa_polymorphic_call_context::offset_by): New method.
	(ipa_polymorphic_call_context::useless_p): New method.
Index: cgraph.h
===================================================================
--- cgraph.h	(revision 215658)
+++ cgraph.h	(working copy)
@@ -1314,8 +1314,35 @@ public:
   void clear_speculation ();
 
   /* Walk container types and modify context to point to actual class
-     containing EXPECTED_TYPE as base class.  */
-  bool restrict_to_inner_class (tree expected_type);
+     containing OTR_TYPE (if non-NULL) as base class.
+     Return true if resulting context is valid.
+
+     When CONSIDER_PLACEMENT_NEW is false, reject contexts that may be made
+     valid only via alocation of new polymorphic type inside by means
+     of placement new.
+
+     When CONSIDER_BASES is false, only look for actual fields, not base types
+     of TYPE.  */
+  bool restrict_to_inner_class (tree otr_type,
+				bool consider_placement_new = true,
+				bool consider_bases = true);
+
+  /* Adjust all offsets in contexts by given number of bits.  */
+  void offset_by (HOST_WIDE_INT);
+  /* Take non-speculative info, merge it with speculative and clear speculatoin.
+     Used when we no longer manage to keep track of actual outer type, but we
+     think it is still there. 
+     If OTR_TYPE is set, the transformation can be done more effectively assuming
+     that context is going to be used only that way.  */
+  void make_speculative (tree otr_type = NULL);
+  /* Assume that both THIS and a given context is valid and strenghten THIS
+     if possible.  Return true if any strenghtening was made.
+     If actual type the context is being used in is known, OTR_TYPE should be
+     set accordingly. This improves quality of combined result.  */
+  bool combine_with (ipa_polymorphic_call_context, tree otr_type = NULL);
+
+  /* Return TRUE if context is fully useless.  */
+  bool useless_p () const;
 
   /* Dump human readable context to F.  */
   void dump (FILE *f) const;
@@ -1326,9 +1353,11 @@ public:
   void stream_in (struct lto_input_block *, struct data_in *data_in);
 
 private:
+  bool combine_speculation_with (tree, HOST_WIDE_INT, bool, tree);
   void set_by_decl (tree, HOST_WIDE_INT);
   bool set_by_invariant (tree, tree, HOST_WIDE_INT);
   void clear_outer_type (tree otr_type = NULL);
+  bool speculation_consistent_p (tree, HOST_WIDE_INT, bool, tree);
 };
 
 /* Structure containing additional information about an indirect call.  */
@@ -2634,4 +2663,23 @@ ipa_polymorphic_call_context::clear_oute
   maybe_derived_type = true;
   maybe_in_construction = true;
 }
+
+/* Adjust all offsets in contexts by OFF bits.  */
+
+inline void
+ipa_polymorphic_call_context::offset_by (HOST_WIDE_INT off)
+{
+  if (outer_type)
+    offset += off;
+  if (speculative_outer_type)
+    speculative_offset += off;
+}
+
+/* Return TRUE if context is fully useless.  */
+
+inline bool
+ipa_polymorphic_call_context::useless_p () const
+{
+  return (!outer_type && !speculative_outer_type);
+}
 #endif  /* GCC_CGRAPH_H  */
Index: ipa-polymorphic-call.c
===================================================================
--- ipa-polymorphic-call.c	(revision 215658)
+++ ipa-polymorphic-call.c	(working copy)
@@ -53,7 +53,9 @@ along with GCC; see the file COPYING3.
 /* Return true when TYPE contains an polymorphic type and thus is interesting
    for devirtualization machinery.  */
 
-static bool contains_type_p (tree, HOST_WIDE_INT, tree);
+static bool contains_type_p (tree, HOST_WIDE_INT, tree,
+			     bool consider_placement_new = true,
+			     bool consider_bases = true);
 
 bool
 contains_polymorphic_type_p (const_tree type)
@@ -99,13 +101,13 @@ possible_placement_new (tree type, tree
 		  <= tree_to_uhwi (TYPE_SIZE (type)))));
 }
 
-/* THIS->OUTER_TYPE is a type of memory object where object of EXPECTED_TYPE
+/* THIS->OUTER_TYPE is a type of memory object where object of OTR_TYPE
    is contained at THIS->OFFSET.  Walk the memory representation of
    THIS->OUTER_TYPE and find the outermost class type that match
-   EXPECTED_TYPE or contain EXPECTED_TYPE as a base.  Update THIS
+   OTR_TYPE or contain OTR_TYPE as a base.  Update THIS
    to represent it.
 
-   If EXPECTED_TYPE is NULL, just find outermost polymorphic type with
+   If OTR_TYPE is NULL, just find outermost polymorphic type with
    virtual table present at possition OFFSET.
 
    For example when THIS represents type
@@ -119,22 +121,32 @@ possible_placement_new (tree type, tree
    sizeof(int). 
 
    If we can not find corresponding class, give up by setting
-   THIS->OUTER_TYPE to EXPECTED_TYPE and THIS->OFFSET to NULL. 
-   Return true when lookup was sucesful.  */
+   THIS->OUTER_TYPE to OTR_TYPE and THIS->OFFSET to NULL. 
+   Return true when lookup was sucesful.
+
+   When CONSIDER_PLACEMENT_NEW is false, reject contexts that may be made
+   valid only via alocation of new polymorphic type inside by means
+   of placement new.
+
+   When CONSIDER_BASES is false, only look for actual fields, not base types
+   of TYPE.  */
 
 bool
-ipa_polymorphic_call_context::restrict_to_inner_class (tree expected_type)
+ipa_polymorphic_call_context::restrict_to_inner_class (tree otr_type,
+						       bool consider_placement_new,
+						       bool consider_bases)
 {
   tree type = outer_type;
   HOST_WIDE_INT cur_offset = offset;
   bool speculative = false;
   bool size_unknown = false;
+  unsigned HOST_WIDE_INT otr_type_size = GET_MODE_BITSIZE (Pmode);
 
   /* Update OUTER_TYPE to match EXPECTED_TYPE if it is not set.  */
   if (!outer_type)
     {
-      clear_outer_type (expected_type);
-      type = expected_type;
+      clear_outer_type (otr_type);
+      type = otr_type;
       cur_offset = 0;
     }
  /* See if OFFSET points inside OUTER_TYPE.  If it does not, we know
@@ -151,8 +163,8 @@ ipa_polymorphic_call_context::restrict_t
 	   && tree_to_shwi (TYPE_SIZE (outer_type)) >= 0
 	   && tree_to_shwi (TYPE_SIZE (outer_type)) <= offset)
    {
-     clear_outer_type (expected_type);
-     type = expected_type;
+     clear_outer_type (otr_type);
+     type = otr_type;
      cur_offset = 0;
 
      /* If derived type is not allowed, we know that the context is invalid.  */
@@ -164,36 +176,11 @@ ipa_polymorphic_call_context::restrict_t
        }
    }
 
-  if (speculative_outer_type)
-    {
-      /* Short cirucit the busy work bellow and give up on case when speculation
-	 is obviously the same as outer_type.  */
-      if ((!maybe_derived_type
-	   || speculative_maybe_derived_type)
-	  && types_must_be_same_for_odr (speculative_outer_type, outer_type))
-	clear_speculation ();
-
-      /* See if SPECULATIVE_OUTER_TYPE is contained in or derived from OUTER_TYPE.
-	 In this case speculation is valid only if derived types are allowed. 
-
-	 The test does not really look for derivate, but also accepts the case where
-	 outer_type is a field of speculative_outer_type.  In this case eiter
-	 MAYBE_DERIVED_TYPE is false and we have full non-speculative information or
-	 the loop bellow will correctly update SPECULATIVE_OUTER_TYPE
-	 and SPECULATIVE_MAYBE_DERIVED_TYPE.  */
-      else if (speculative_offset < offset
-	       || !contains_type_p (speculative_outer_type,
-				    speculative_offset - offset,
-				    outer_type)
-	       || !maybe_derived_type)
-	clear_speculation ();
-    }
-  else
-    /* Regularize things little bit and clear all the fields when no useful
-       speculatin is known.  */
-    clear_speculation ();
+  if (otr_type && TYPE_SIZE (otr_type)
+      && tree_fits_shwi_p (TYPE_SIZE (otr_type)))
+    otr_type_size = tree_to_uhwi (TYPE_SIZE (otr_type));
 
-  if (!type)
+  if (!type || offset < 0)
     goto no_useful_type_info;
 
   /* Find the sub-object the constant actually refers to and mark whether it is
@@ -203,7 +190,7 @@ ipa_polymorphic_call_context::restrict_t
      for speculative_outer_type.  The second run has SPECULATIVE set.  */
   while (true)
     {
-      HOST_WIDE_INT pos, size;
+      unsigned HOST_WIDE_INT pos, size;
       tree fld;
 
       /* If we do not know size of TYPE, we need to be more conservative
@@ -218,9 +205,10 @@ ipa_polymorphic_call_context::restrict_t
 	size_unknown = true;
 
       /* On a match, just return what we found.  */
-      if ((types_odr_comparable (type, expected_type)
-	   && types_same_for_odr (type, expected_type))
-	  || (!expected_type
+      if ((otr_type
+	   && types_odr_comparable (type, otr_type)
+	   && types_same_for_odr (type, otr_type))
+	  || (!otr_type
 	      && TREE_CODE (type) == RECORD_TYPE
 	      && TYPE_BINFO (type)
 	      && polymorphic_type_binfo_p (TYPE_BINFO (type))))
@@ -242,7 +230,9 @@ ipa_polymorphic_call_context::restrict_t
 	    {
 	      /* If type is known to be final, do not worry about derived
 		 types.  Testing it here may help us to avoid speculation.  */
-	      if (type_known_to_have_no_deriavations_p (outer_type))
+	      if (otr_type && TREE_CODE (outer_type) == RECORD_TYPE
+		  && (!in_lto_p || odr_type_p (outer_type))
+		  && type_known_to_have_no_deriavations_p (outer_type))
 		maybe_derived_type = false;
 
 	      /* Type can not contain itself on an non-zero offset.  In that case
@@ -254,7 +244,11 @@ ipa_polymorphic_call_context::restrict_t
 		goto no_useful_type_info;
 	      /* If we determined type precisely or we have no clue on
  		 speuclation, we are done.  */
-	      if (!maybe_derived_type || !speculative_outer_type)
+	      if (!maybe_derived_type || !speculative_outer_type
+		  || !speculation_consistent_p (speculative_outer_type,
+					        speculative_offset,
+					        speculative_maybe_derived_type,
+						otr_type))
 		{
 		  clear_speculation ();
 	          return true;
@@ -279,8 +273,29 @@ ipa_polymorphic_call_context::restrict_t
 		continue;
 
 	      pos = int_bit_position (fld);
+	      if (pos > (unsigned HOST_WIDE_INT)cur_offset)
+		continue;
+	      if (!DECL_SIZE (fld) || !tree_fits_uhwi_p (DECL_SIZE (fld)))
+		goto no_useful_type_info;
 	      size = tree_to_uhwi (DECL_SIZE (fld));
-	      if (pos <= cur_offset && (pos + size) > cur_offset)
+
+	      /* We can always skip types smaller than pointer size:
+		 those can not contain a virtual table pointer.
+
+		 Disqualifying fields that are too small to fit OTR_TYPE
+		 saves work needed to walk them for no benefit.
+		 Because of the way the bases are packed into a class, the
+		 field's size may be smaller than type size, so it needs
+		 to be done with a care.  */
+		
+	      if (pos <= (unsigned HOST_WIDE_INT)cur_offset
+		  && (pos + size) >= (unsigned HOST_WIDE_INT)cur_offset
+				     + GET_MODE_BITSIZE (Pmode)
+		  && (!otr_type
+		      || !TYPE_SIZE (TREE_TYPE (fld))
+		      || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (fld)))
+		      || (pos + tree_to_uhwi (TYPE_SIZE (TREE_TYPE (fld))))
+			  >= cur_offset + otr_type_size))
 		break;
 	    }
 
@@ -307,12 +322,16 @@ ipa_polymorphic_call_context::restrict_t
 		  speculative_maybe_derived_type = false;
 		}
 	    }
+	  else if (!consider_bases)
+	    goto no_useful_type_info;
 	}
       else if (TREE_CODE (type) == ARRAY_TYPE)
 	{
 	  tree subtype = TYPE_MAIN_VARIANT (TREE_TYPE (type));
 
-	  /* Give up if we don't know array size.  */
+	  /* Give up if we don't know array field size.
+	     Also give up on non-polymorphic types as they are used
+	     as buffers for placement new.  */
 	  if (!TYPE_SIZE (subtype)
 	      || !tree_fits_shwi_p (TYPE_SIZE (subtype))
 	      || tree_to_shwi (TYPE_SIZE (subtype)) <= 0
@@ -324,9 +343,7 @@ ipa_polymorphic_call_context::restrict_t
 	  /* We may see buffer for placement new.  In this case the expected type
 	     can be bigger than the subtype.  */
 	  if (TYPE_SIZE (subtype)
-	      && (cur_offset
-		  + (expected_type ? tree_to_uhwi (TYPE_SIZE (expected_type))
-		     : 0)
+	      && (cur_offset + otr_type_size
 		  > tree_to_uhwi (TYPE_SIZE (subtype))))
 	    goto no_useful_type_info;
 
@@ -349,12 +366,36 @@ ipa_polymorphic_call_context::restrict_t
       else
 	{
 no_useful_type_info:
+	  if (maybe_derived_type && !speculative
+	      && TREE_CODE (outer_type) == RECORD_TYPE
+	      && TREE_CODE (otr_type) == RECORD_TYPE
+	      && TYPE_BINFO (otr_type)
+	      && !offset
+	      && get_binfo_at_offset (TYPE_BINFO (otr_type), 0, outer_type))
+	    {
+	      clear_outer_type (otr_type);
+	      if (!speculative_outer_type
+		  || !speculation_consistent_p (speculative_outer_type,
+						speculative_offset,
+					        speculative_maybe_derived_type,
+						otr_type))
+		clear_speculation ();
+	      if (speculative_outer_type)
+		{
+		  speculative = true;
+		  type = speculative_outer_type;
+		  cur_offset = speculative_offset;
+		}
+	      else
+		return true;
+	    }
 	  /* We found no way to embedd EXPECTED_TYPE in TYPE.
 	     We still permit two special cases - placement new and
 	     the case of variadic types containing themselves.  */
 	  if (!speculative
-	      && (size_unknown || !type
-		  || possible_placement_new (type, expected_type, cur_offset)))
+	      && consider_placement_new
+	      && (size_unknown || !type || maybe_derived_type
+		  || possible_placement_new (type, otr_type, cur_offset)))
 	    {
 	      /* In these weird cases we want to accept the context.
 		 In non-speculative run we have no useful outer_type info
@@ -364,7 +405,13 @@ no_useful_type_info:
 		 give useful info.  */
 	      if (!speculative)
 		{
-		  clear_outer_type (expected_type);
+		  clear_outer_type (otr_type);
+		  if (!speculative_outer_type
+		      || !speculation_consistent_p (speculative_outer_type,
+						    speculative_offset,
+						    speculative_maybe_derived_type,
+						    otr_type))
+		    clear_speculation ();
 		  if (speculative_outer_type)
 		    {
 		      speculative = true;
@@ -383,7 +430,7 @@ no_useful_type_info:
 	      clear_speculation ();
 	      if (speculative)
 		return true;
-	      clear_outer_type (expected_type);
+	      clear_outer_type (otr_type);
 	      invalid = true; 
 	      return false;
 	    }
@@ -391,17 +438,33 @@ no_useful_type_info:
     }
 }
 
-/* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET.  */
+/* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET.
+   CONSIDER_PLACEMENT_NEW makes function to accept cases where OTR_TYPE can
+   be built within OUTER_TYPE by means of placement new.  CONSIDER_BASES makes
+   function to accept cases where OTR_TYPE appears as base of OUTER_TYPE or as
+   base of one of fields of OUTER_TYPE.  */
 
 static bool
 contains_type_p (tree outer_type, HOST_WIDE_INT offset,
-		 tree otr_type)
+		 tree otr_type,
+		 bool consider_placement_new,
+		 bool consider_bases)
 {
   ipa_polymorphic_call_context context;
+
+  /* Check that type is within range.  */
+  if (offset < 0)
+    return false;
+  if (TYPE_SIZE (outer_type) && TYPE_SIZE (otr_type)
+      && TREE_CODE (outer_type) == INTEGER_CST
+      && TREE_CODE (otr_type) == INTEGER_CST
+      && wi::ltu_p (wi::to_offset (outer_type), (wi::to_offset (otr_type) + offset)))
+    return false;
+
   context.offset = offset;
   context.outer_type = TYPE_MAIN_VARIANT (outer_type);
   context.maybe_derived_type = false;
-  return context.restrict_to_inner_class (otr_type);
+  return context.restrict_to_inner_class (otr_type, consider_placement_new, consider_bases);
 }
 
 
@@ -508,8 +571,8 @@ ipa_polymorphic_call_context::dump (FILE
     fprintf (f, "Call is known to be undefined\n");
   else
     {
-      if (!outer_type && !offset && !speculative_outer_type)
-	fprintf (f, "Empty context\n");
+      if (useless_p ())
+	fprintf (f, "nothing known");
       if (outer_type || offset)
 	{
 	  fprintf (f, "Outer type:");
@@ -523,7 +586,9 @@ ipa_polymorphic_call_context::dump (FILE
 	}
       if (speculative_outer_type)
 	{
-	  fprintf (f, " speculative outer type:");
+	  if (outer_type || offset)
+	    fprintf (f, " ");
+	  fprintf (f, "Speculative outer type:");
 	  print_generic_expr (f, speculative_outer_type, TDF_SLIM);
 	  if (speculative_maybe_derived_type)
 	    fprintf (f, " (or a derived type)");
@@ -730,6 +795,13 @@ ipa_polymorphic_call_context::ipa_polymo
 	  tree base = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0),
 					       &offset2, &size, &max_size);
 
+	  if (max_size != -1 && max_size == size)
+	    combine_speculation_with (TYPE_MAIN_VARIANT
+					(TREE_TYPE (TREE_TYPE (base_pointer))),
+				      offset + offset2,
+				      true,
+				      NULL /* Do not change outer type.  */);
+
 	  /* If this is a varying address, punt.  */
 	  if ((TREE_CODE (base) == MEM_REF || DECL_P (base))
 	      && max_size != -1
@@ -748,8 +820,6 @@ ipa_polymorphic_call_context::ipa_polymo
 		 is known.  */
 	      else if (DECL_P (base))
 		{
-		  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (base)));
-
 		  /* Only type inconsistent programs can have otr_type that is
 		     not part of outer type.  */
 		  if (otr_type
@@ -801,15 +871,17 @@ ipa_polymorphic_call_context::ipa_polymo
 	{
 	  outer_type
 	     = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
-	  gcc_assert (TREE_CODE (outer_type) == RECORD_TYPE);
+	  gcc_assert (TREE_CODE (outer_type) == RECORD_TYPE
+		      || TREE_CODE (outer_type) == UNION_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 (otr_type
-	      && !contains_type_p (outer_type, offset,
-				   otr_type))
+	  if ((otr_type
+	       && !contains_type_p (outer_type, offset,
+				    otr_type))
+	      || !contains_polymorphic_type_p (outer_type))
 	    {
 	      outer_type = NULL;
 	      if (instance)
@@ -842,17 +914,24 @@ ipa_polymorphic_call_context::ipa_polymo
 	{
 	  outer_type
 	     = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
-	  gcc_assert (!POINTER_TYPE_P (outer_type));
 	  /* Only type inconsistent programs can have otr_type that is
 	     not part of outer type.  */
-	  if (!contains_type_p (outer_type, offset,
-			        otr_type))
+	  if (otr_type && !contains_type_p (outer_type, offset,
+					    otr_type))
 	    { 
 	      invalid = true;
 	      if (instance)
 		*instance = base_pointer;
 	      return;
 	    }
+	  /* Non-polymorphic types have no interest for us.  */
+	  else if (!otr_type && !contains_polymorphic_type_p (outer_type))
+	    {
+	      outer_type = NULL;
+	      if (instance)
+		*instance = base_pointer;
+	      return;
+	    }
 	  maybe_derived_type = false;
 	  maybe_in_construction = false;
 	  if (instance)
@@ -878,17 +957,10 @@ ipa_polymorphic_call_context::ipa_polymo
     base_type = TREE_TYPE (gimple_assign_rhs1
 			    (SSA_NAME_DEF_STMT (base_pointer)));
  
-  if (POINTER_TYPE_P (base_type)
-      && (otr_type
-	  || !contains_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (base_type)),
-			       offset,
-			       otr_type)))
-    {
-      speculative_outer_type = TYPE_MAIN_VARIANT
-					  (TREE_TYPE (base_type));
-      speculative_offset = offset;
-      speculative_maybe_derived_type = true;
-    }
+  if (POINTER_TYPE_P (base_type))
+    combine_speculation_with (TYPE_MAIN_VARIANT (TREE_TYPE (base_type)),
+			      offset,
+			      true, NULL /* Do not change type here */);
   /* 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.  */
@@ -1080,7 +1152,7 @@ extr_type_from_vtbl_ptr_store (gimple st
     {
       if (dump_file)
 	fprintf (dump_file, "    Construction vtable used\n");
-      /* FIXME: We should suport construction contextes.  */
+      /* FIXME: We should suport construction contexts.  */
       return NULL;
     }
  
@@ -1516,3 +1588,390 @@ ipa_polymorphic_call_context::get_dynami
   return true;
 }
 
+/* See if speculation given by SPEC_OUTER_TYPE, SPEC_OFFSET and SPEC_MAYBE_DERIVED_TYPE
+   seems consistent (and useful) with what we already have in the non-speculative context.  */
+
+bool
+ipa_polymorphic_call_context::speculation_consistent_p (tree spec_outer_type,
+							HOST_WIDE_INT spec_offset,
+							bool spec_maybe_derived_type,
+							tree otr_type)
+{
+  if (!flag_devirtualize_speculatively)
+    return false;
+  /* If we know nothing, speculation is always good.  */
+  if (!outer_type)
+    return true;
+
+  /* Speculation is only useful to avoid derived types.
+     This is not 100% true for placement new, where the outer context may
+     turn out to be useless, but ignore these for now.  */
+  if (!maybe_derived_type)
+    return false;
+
+  /* If types agrees, speculation is consistent, but it makes sense only
+     when it says something new.  */
+  if (types_must_be_same_for_odr (spec_outer_type, outer_type))
+    return maybe_derived_type && !spec_maybe_derived_type;
+
+  /* Non-polymorphic types are useless for deriving likely polymorphic
+     call targets.  */
+  if (!contains_polymorphic_type_p (spec_outer_type))
+    return false;
+
+  /* If speculation does not contain the type in question, ignore it.  */
+  if (otr_type
+      && !contains_type_p (spec_outer_type, spec_offset, otr_type, false, true))
+    return false;
+
+  /* If outer type already contains speculation as a filed,
+     it is useless.  We already know from OUTER_TYPE 
+     SPEC_TYPE and that it is not in the construction.  */
+  if (contains_type_p (outer_type, offset - spec_offset,
+		       spec_outer_type, false, false))
+    return false;
+
+  /* If speculative outer type is not more specified than outer
+     type, just give up. 
+     We can only decide this safely if we can compare types with OUTER_TYPE.
+   */
+  if ((!in_lto_p || odr_type_p (outer_type))
+      && !contains_type_p (spec_outer_type,
+			   spec_offset - offset,
+			   outer_type, false))
+    return false;
+  return true;
+}
+
+/* Improve THIS with speculation described by NEW_OUTER_TYPE, NEW_OFFSET,
+   NEW_MAYBE_DERIVED_TYPE 
+   If OTR_TYPE is set, assume the context is used with OTR_TYPE.  */
+
+bool
+ipa_polymorphic_call_context::combine_speculation_with
+   (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type,
+    tree otr_type)
+{
+  if (!new_outer_type)
+    return false;
+
+  /* restrict_to_inner_class may eliminate wrong speculation making our job
+     easeier.  */
+  if (otr_type)
+    restrict_to_inner_class (otr_type);
+
+  if (!speculation_consistent_p (new_outer_type, new_offset,
+				 new_maybe_derived_type, otr_type))
+    return false;
+
+  /* New speculation is a win in case we have no speculation or new
+     speculation does not consider derivations.  */
+  if (!speculative_outer_type
+      || (speculative_maybe_derived_type
+	  && !new_maybe_derived_type))
+    {
+      speculative_outer_type = new_outer_type;
+      speculative_offset = new_offset;
+      speculative_maybe_derived_type = new_maybe_derived_type;
+      return true;
+    }
+  else if (types_must_be_same_for_odr (speculative_outer_type,
+				       new_outer_type))
+    {
+      if (speculative_offset != new_offset)
+	{
+	  /* OK we have two contexts that seems valid but they disagree,
+	     just give up.
+
+	     This is not a lattice operation, so we may want to drop it later.  */
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Speculative outer types match, "
+		     "offset mismatch -> invalid speculation\n");
+	  clear_speculation ();
+	  return true;
+	}
+      else
+	{
+	  if (speculative_maybe_derived_type && !new_maybe_derived_type)
+	    {
+	      speculative_maybe_derived_type = false;
+	      return true;
+	    }
+	  else
+	    return false;
+	}
+    }
+  /* Choose type that contains the other.  This one either contains the outer
+     as a field (thus giving exactly one target) or is deeper in the type
+     hiearchy.  */
+  else if (speculative_outer_type
+	   && speculative_maybe_derived_type
+	   && (new_offset > speculative_offset
+	       || (new_offset == speculative_offset
+		   && contains_type_p (new_outer_type,
+				       0, speculative_outer_type, false))))
+    {
+      tree old_outer_type = speculative_outer_type;
+      HOST_WIDE_INT old_offset = speculative_offset;
+      bool old_maybe_derived_type = speculative_maybe_derived_type;
+
+      speculative_outer_type = new_outer_type;
+      speculative_offset = new_offset;
+      speculative_maybe_derived_type = new_maybe_derived_type;
+
+      if (otr_type)
+	restrict_to_inner_class (otr_type);
+
+      /* If the speculation turned out to make no sense, revert to sensible
+	 one.  */
+      if (!speculative_outer_type)
+	{
+	  speculative_outer_type = old_outer_type;
+	  speculative_offset = old_offset;
+	  speculative_maybe_derived_type = old_maybe_derived_type;
+	  return false;
+	}
+      return (old_offset != speculative_offset
+	      || old_maybe_derived_type != speculative_maybe_derived_type
+	      || types_must_be_same_for_odr (speculative_outer_type,
+					     new_outer_type));
+    }
+  return false;
+}
+
+/* Assume that both THIS and a given context is valid and strenghten THIS
+   if possible.  Return true if any strenghtening was made.
+   If actual type the context is being used in is known, OTR_TYPE should be
+   set accordingly. This improves quality of combined result.  */
+
+bool
+ipa_polymorphic_call_context::combine_with (ipa_polymorphic_call_context ctx,
+					    tree otr_type)
+{
+  bool updated = false;
+
+  if (ctx.useless_p () || invalid)
+    return false;
+
+  /* Restricting context to inner type makes merging easier, however do not
+     do that unless we know how the context is used (OTR_TYPE is non-NULL)  */
+  if (otr_type && !invalid && !ctx.invalid)
+    {
+      restrict_to_inner_class (otr_type);
+      ctx.restrict_to_inner_class (otr_type);
+      if(invalid)
+        return false;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Polymorphic call context combine:");
+      dump (dump_file);
+      fprintf (dump_file, "With context:                    ");
+      ctx.dump (dump_file);
+      if (otr_type)
+	{
+          fprintf (dump_file, "To be used with type:            ");
+	  print_generic_expr (dump_file, otr_type, TDF_SLIM);
+          fprintf (dump_file, "\n");
+	}
+    }
+
+  /* If call is known to be invalid, we are done.  */
+  if (ctx.invalid)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+        fprintf (dump_file, "-> Invalid context\n");
+      goto invalidate;
+    }
+
+  if (!ctx.outer_type)
+    ;
+  else if (!outer_type)
+    {
+      outer_type = ctx.outer_type;
+      offset = ctx.offset;
+      maybe_in_construction = ctx.maybe_in_construction;
+      maybe_derived_type = ctx.maybe_derived_type;
+      updated = true;
+    }
+  /* If types are known to be same, merging is quite easy.  */
+  else if (types_must_be_same_for_odr (outer_type, ctx.outer_type))
+    {
+      if (offset != ctx.offset
+	  && TYPE_SIZE (outer_type)
+	  && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Outer types match, offset mismatch -> invalid\n");
+	  clear_speculation ();
+	  clear_outer_type ();
+	  invalid = true;
+	  return true;
+	}
+      if (dump_file && (dump_flags & TDF_DETAILS))
+        fprintf (dump_file, "Outer types match, merging flags\n");
+      if (maybe_in_construction && !ctx.maybe_in_construction)
+	{
+	  updated = true;
+	  maybe_in_construction = false;
+	}
+      if (maybe_derived_type && !ctx.maybe_derived_type)
+	{
+	  updated = true;
+	  maybe_derived_type = false;
+	}
+    }
+  /* If we know the type precisely, there is not much to improve.  */
+  else if (!maybe_derived_type && !maybe_in_construction
+	   && !ctx.maybe_derived_type && !ctx.maybe_in_construction)
+    {
+      /* It may be easy to check if second context permits the first
+	 and set INVALID otherwise.  This is not easy to do in general;
+	 contains_type_p may return false negatives for non-comparable
+	 types.  
+
+	 If OTR_TYPE is known, we however can expect that
+	 restrict_to_inner_class should have discovered the same base
+	 type.  */
+      if (otr_type && !ctx.maybe_in_construction && !ctx.maybe_derived_type)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "Contextes disagree -> invalid\n");
+	  goto invalidate;
+	}
+    }
+  /* See if one type contains the other as a field (not base).
+     In this case we want to choose the wider type, because it contains
+     more information.  */
+  else if (contains_type_p (ctx.outer_type, ctx.offset - offset,
+			    outer_type, false, false))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Second type contain the first as a field\n");
+
+      if (maybe_derived_type)
+	{
+	  outer_type = ctx.outer_type;
+	  maybe_derived_type = ctx.maybe_derived_type;
+	  offset = ctx.offset;
+	  updated = true;
+	}
+
+      /* If we do not know how the context is being used, we can
+	 not clear MAYBE_IN_CONSTRUCTION because it may be offseted
+	 to other component of OUTER_TYPE later and we know nothing
+	 about it.  */
+      if (otr_type && maybe_in_construction
+	  && !ctx.maybe_in_construction)
+	{
+          maybe_in_construction = false;
+	  updated = true;
+	}
+    }
+  else if (contains_type_p (outer_type, offset - ctx.offset,
+			    ctx.outer_type, false, false))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "First type contain the second as a field\n");
+
+      if (otr_type && maybe_in_construction
+	  && !ctx.maybe_in_construction)
+	{
+          maybe_in_construction = false;
+	  updated = true;
+	}
+    }
+  /* See if OUTER_TYPE is base of CTX.OUTER_TYPE.  */
+  else if (contains_type_p (ctx.outer_type,
+			    ctx.offset - offset, outer_type, false, true))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "First type is base of second\n");
+      if (!maybe_derived_type)
+	{
+	  if (!ctx.maybe_in_construction
+	      && types_odr_comparable (outer_type, ctx.outer_type))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "Second context does not permit base -> invalid\n");
+	      goto invalidate;
+	    }
+	}
+      /* Pick variant deeper in the hiearchy.  */
+      else
+	{
+	  outer_type = ctx.outer_type;
+	  maybe_in_construction = ctx.maybe_in_construction;
+	  maybe_derived_type = ctx.maybe_derived_type;
+	  offset = ctx.offset;
+          updated = true;
+	}
+    }
+  /* See if CTX.OUTER_TYPE is base of OUTER_TYPE.  */
+  else if (contains_type_p (outer_type,
+			    offset - ctx.offset, ctx.outer_type, false, true))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Second type is base of first\n");
+      if (!ctx.maybe_derived_type)
+	{
+	  if (!maybe_in_construction
+	      && types_odr_comparable (outer_type, ctx.outer_type))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "First context does not permit base -> invalid\n");
+	      goto invalidate;
+	    }
+	}
+    }
+  /* TODO handle merging using hiearchy. */
+  else if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Giving up on merge\n");
+
+  updated |= combine_speculation_with (ctx.speculative_outer_type,
+				       ctx.speculative_offset,
+				       ctx.maybe_in_construction,
+				       otr_type);
+
+  if (updated && dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Updated as:                      ");
+      dump (dump_file);
+      fprintf (dump_file, "\n");
+    }
+  return updated;
+
+invalidate:
+  invalid = true;
+  clear_speculation ();
+  clear_outer_type ();
+  return true;
+}
+
+/* Take non-speculative info, merge it with speculative and clear speculation.
+   Used when we no longer manage to keep track of actual outer type, but we
+   think it is still there.  */
+
+void
+ipa_polymorphic_call_context::make_speculative (tree otr_type)
+{
+  tree spec_outer_type = outer_type;
+  HOST_WIDE_INT spec_offset = offset;
+  bool spec_maybe_derived_type = maybe_derived_type;
+
+  if (invalid)
+    {
+      invalid = false;
+      clear_outer_type ();
+      clear_speculation ();
+      return;
+    }
+  if (!outer_type)
+    return;
+  clear_outer_type ();
+  combine_speculation_with (spec_outer_type, spec_offset,
+			    spec_maybe_derived_type,
+			    otr_type);
+}


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