ipa-devirt TLC 8 - break out polymorphic context code

Jan Hubicka hubicka@ucw.cz
Thu Sep 25 19:55:00 GMT 2014


Hi,
this patch moves all code dealing with polymorphic_call_context to
ipa-polymorphic-call.c in hope that things are more manageable this way.
This code contains most of the magic of analyzing GIMPLE and determining
contextes.

ipa-devirt.c still contains several essentially independent things - the ODR
logic, the type inheritance graph, the code for determining possible targets,
and, the ipa_devirt pass itself.  Perhaps it would make sense to break out
ODR and type inheritance too, but first I want to revisit the APIs.

Honza

	* ipa-utils.h (subbinfo_with_vtable_at_offset, type_all_derivations_known_p,
	type_known_to_have_no_deriavations_p, types_must_be_same_for_odr,
	types_odr_comparable): Declare.
	(polymorphic_type_binfo_p): Move here from ipa-devirt.c
	* ipa-polymorphic-call.c: New file.
	(contains_polymorphic_type_p, possible_placement_new,
	ipa_polymorphic_call_context::restrict_to_inner_class,
	contains_type_p, decl_maybe_in_construction_p,
	ipa_polymorphic_call_context::stream_out,
	ipa_polymorphic_call_context::debug,
	ipa_polymorphic_call_context::stream_in,
	ipa_polymorphic_call_context::set_by_decl,
	ipa_polymorphic_call_context::set_by_invariant,
	walk_ssa_copies,
	ipa_polymorphic_call_context::ipa_polymorphic_call_context,
	type_change_info, noncall_stmt_may_be_vtbl_ptr_store,
	extr_type_from_vtbl_ptr_store, record_known_type
	check_stmt_for_type_change,
	ipa_polymorphic_call_context::get_dynamic_type): Move here from
	ipa-devirt.c
	* ipa-devirt.c: No longer include data-streamer.h, lto-streamer.h
	and streamer-hooks.h
	(contains_polymorphic_type_p, possible_placement_new,
	ipa_polymorphic_call_context::restrict_to_inner_class,
	contains_type_p, decl_maybe_in_construction_p,
	ipa_polymorphic_call_context::stream_out,
	ipa_polymorphic_call_context::debug,
	ipa_polymorphic_call_context::stream_in,
	ipa_polymorphic_call_context::set_by_decl,
	ipa_polymorphic_call_context::set_by_invariant,
	walk_ssa_copies,
	ipa_polymorphic_call_context::ipa_polymorphic_call_context,
	type_change_info, noncall_stmt_may_be_vtbl_ptr_store,
	extr_type_from_vtbl_ptr_store, record_known_type
	check_stmt_for_type_change,
	ipa_polymorphic_call_context::get_dynamic_type): Move to
	ipa-polymorphic-call.c
	(type_all_derivations_known_p, types_odr_comparable,
	types_must_be_same_for_odr): Export.
	(type_known_to_have_no_deriavations_p): New function.
	* Makefile.in: Add ipa-polymorphic-call.c
	
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 215614)
+++ ipa-utils.h	(working copy)
@@ -74,9 +74,14 @@ tree method_class_type (const_tree);
 bool decl_maybe_in_construction_p (tree, tree, gimple, tree);
 tree vtable_pointer_value_to_binfo (const_tree);
 bool vtable_pointer_value_to_vtable (const_tree, tree *, unsigned HOST_WIDE_INT *);
+tree subbinfo_with_vtable_at_offset (tree, unsigned HOST_WIDE_INT, tree);
 void compare_virtual_tables (varpool_node *, varpool_node *);
+bool type_all_derivations_known_p (const_tree);
+bool type_known_to_have_no_deriavations_p (tree);
 bool contains_polymorphic_type_p (const_tree);
 void register_odr_type (tree);
+bool types_must_be_same_for_odr (tree, tree);
+bool types_odr_comparable (tree, tree);
 
 /* Return vector containing possible targets of polymorphic call E.
    If COMPLETEP is non-NULL, store true if the list is complette. 
@@ -162,6 +167,21 @@ odr_type_p (const_tree t)
   return (TYPE_NAME (t)
           && (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t))));
 }
+
+/* Return true if BINFO corresponds to a type with virtual methods. 
+
+   Every type has several BINFOs.  One is the BINFO associated by the type
+   while other represents bases of derived types.  The BINFOs representing
+   bases do not have BINFO_VTABLE pointer set when this is the single
+   inheritance (because vtables are shared).  Look up the BINFO of type
+   and check presence of its vtable.  */
+
+inline bool
+polymorphic_type_binfo_p (const_tree binfo)
+{
+  /* See if BINFO's type has an virtual table associtated with it.  */
+  return BINFO_VTABLE (TYPE_BINFO (BINFO_TYPE (binfo)));
+}
 #endif  /* GCC_IPA_UTILS_H  */
 
 
Index: ipa-polymorphic-call.c
===================================================================
--- ipa-polymorphic-call.c	(revision 0)
+++ ipa-polymorphic-call.c	(revision 0)
@@ -0,0 +1,1518 @@
+/* Analysis of polymorphic call context.
+   Copyright (C) 2013-2014 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/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "print-tree.h"
+#include "calls.h"
+#include "expr.h"
+#include "tree-pass.h"
+#include "hash-set.h"
+#include "target.h"
+#include "hash-table.h"
+#include "inchash.h"
+#include "tree-pretty-print.h"
+#include "ipa-utils.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-fold.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "ipa-inline.h"
+#include "diagnostic.h"
+#include "tree-dfa.h"
+#include "demangle.h"
+#include "dbgcnt.h"
+#include "gimple-pretty-print.h"
+#include "stor-layout.h"
+#include "intl.h"
+#include "data-streamer.h"
+#include "lto-streamer.h"
+#include "streamer-hooks.h"
+
+/* 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);
+
+bool
+contains_polymorphic_type_p (const_tree type)
+{
+  type = TYPE_MAIN_VARIANT (type);
+
+  if (RECORD_OR_UNION_TYPE_P (type))
+    {
+      if (TYPE_BINFO (type)
+          && polymorphic_type_binfo_p (TYPE_BINFO (type)))
+	return true;
+      for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
+	if (TREE_CODE (fld) == FIELD_DECL
+	    && !DECL_ARTIFICIAL (fld)
+	    && contains_polymorphic_type_p (TREE_TYPE (fld)))
+	  return true;
+      return false;
+    }
+  if (TREE_CODE (type) == ARRAY_TYPE)
+    return contains_polymorphic_type_p (TREE_TYPE (type));
+  return false;
+}
+
+/* Return true if it seems valid to use placement new to build EXPECTED_TYPE
+   at possition CUR_OFFSET within TYPE.  
+
+   POD can be changed to an instance of a polymorphic type by
+   placement new.  Here we play safe and assume that any
+   non-polymorphic type is POD.  */
+bool
+possible_placement_new (tree type, tree expected_type,
+			HOST_WIDE_INT cur_offset)
+{
+  return ((TREE_CODE (type) != RECORD_TYPE
+	   || !TYPE_BINFO (type)
+	   || cur_offset >= BITS_PER_WORD
+	   || !polymorphic_type_binfo_p (TYPE_BINFO (type)))
+	  && (!TYPE_SIZE (type)
+	      || !tree_fits_shwi_p (TYPE_SIZE (type))
+	      || (cur_offset
+		  + (expected_type ? tree_to_uhwi (TYPE_SIZE (expected_type))
+		     : 1)
+		  <= tree_to_uhwi (TYPE_SIZE (type)))));
+}
+
+/* THIS->OUTER_TYPE is a type of memory object where object of EXPECTED_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
+   to represent it.
+
+   If EXPECTED_TYPE is NULL, just find outermost polymorphic type with
+   virtual table present at possition OFFSET.
+
+   For example when THIS 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
+   THIS->OUTER_TYPE to EXPECTED_TYPE and THIS->OFFSET to NULL. 
+   Return true when lookup was sucesful.  */
+
+bool
+ipa_polymorphic_call_context::restrict_to_inner_class (tree expected_type)
+{
+  tree type = outer_type;
+  HOST_WIDE_INT cur_offset = offset;
+  bool speculative = false;
+  bool size_unknown = false;
+
+  /* Update OUTER_TYPE to match EXPECTED_TYPE if it is not set.  */
+  if (!outer_type)
+    {
+      clear_outer_type (expected_type);
+      type = expected_type;
+      cur_offset = 0;
+    }
+ /* See if OFFSET points inside OUTER_TYPE.  If it does not, we know
+    that the context is either invalid, or the instance type must be
+    derived from OUTER_TYPE.
+
+    Because the instance type may contain field whose type is of OUTER_TYPE,
+    we can not derive any effective information about it.
+
+    TODO: In the case we know all derrived types, we can definitely do better
+    here.  */
+  else if (TYPE_SIZE (outer_type)
+	   && tree_fits_shwi_p (TYPE_SIZE (outer_type))
+	   && tree_to_shwi (TYPE_SIZE (outer_type)) >= 0
+	   && tree_to_shwi (TYPE_SIZE (outer_type)) <= offset)
+   {
+     clear_outer_type (expected_type);
+     type = expected_type;
+     cur_offset = 0;
+
+     /* If derived type is not allowed, we know that the context is invalid.  */
+     if (!maybe_derived_type)
+       {
+	 clear_speculation ();
+	 invalid = true;
+	 return false;
+       }
+   }
+
+  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 (!type)
+    goto no_useful_type_info;
+
+  /* Find the sub-object the constant actually refers to and mark whether it is
+     an artificial one (as opposed to a user-defined one).
+
+     This loop is performed twice; first time for outer_type and second time
+     for speculative_outer_type.  The second run has SPECULATIVE set.  */
+  while (true)
+    {
+      HOST_WIDE_INT pos, size;
+      tree fld;
+
+      /* If we do not know size of TYPE, we need to be more conservative
+         about accepting cases where we can not find EXPECTED_TYPE.
+	 Generally the types that do matter here are of constant size.
+	 Size_unknown case should be very rare.  */
+      if (TYPE_SIZE (type)
+	  && tree_fits_shwi_p (TYPE_SIZE (type))
+	  && tree_to_shwi (TYPE_SIZE (type)) >= 0)
+	size_unknown = false;
+      else
+	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
+	      && TREE_CODE (type) == RECORD_TYPE
+	      && TYPE_BINFO (type)
+	      && polymorphic_type_binfo_p (TYPE_BINFO (type))))
+	{
+	  if (speculative)
+	    {
+	      /* If we did not match the offset, just give up on speculation.  */
+	      if (cur_offset != 0
+		  /* Also check if speculation did not end up being same as
+		     non-speculation.  */
+		  || (types_must_be_same_for_odr (speculative_outer_type,
+						  outer_type)
+		      && (maybe_derived_type
+			  == speculative_maybe_derived_type)))
+		clear_speculation ();
+	      return true;
+	    }
+	  else
+	    {
+	      /* 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))
+		maybe_derived_type = false;
+
+	      /* Type can not contain itself on an non-zero offset.  In that case
+		 just give up.  Still accept the case where size is now known.
+		 Either the second copy may appear past the end of type or within
+		 the non-POD buffer located inside the variably sized type
+		 itself.  */
+	      if (cur_offset != 0)
+		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)
+		{
+		  clear_speculation ();
+	          return true;
+		}
+	      /* Otherwise look into speculation now.  */
+	      else
+		{
+		  speculative = true;
+		  type = speculative_outer_type;
+		  cur_offset = speculative_offset;
+		  continue;
+		}
+	    }
+	}
+
+      /* 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 <= cur_offset && (pos + size) > cur_offset)
+		break;
+	    }
+
+	  if (!fld)
+	    goto no_useful_type_info;
+
+	  type = TYPE_MAIN_VARIANT (TREE_TYPE (fld));
+	  cur_offset -= pos;
+	  /* DECL_ARTIFICIAL represents a basetype.  */
+	  if (!DECL_ARTIFICIAL (fld))
+	    {
+	      if (!speculative)
+		{
+		  outer_type = type;
+		  offset = cur_offset;
+		  /* As soon as we se an field containing the type,
+		     we know we are not looking for derivations.  */
+		  maybe_derived_type = false;
+		}
+	      else
+		{
+		  speculative_outer_type = type;
+		  speculative_offset = cur_offset;
+		  speculative_maybe_derived_type = false;
+		}
+	    }
+	}
+      else if (TREE_CODE (type) == ARRAY_TYPE)
+	{
+	  tree subtype = TYPE_MAIN_VARIANT (TREE_TYPE (type));
+
+	  /* Give up if we don't know array size.  */
+	  if (!TYPE_SIZE (subtype)
+	      || !tree_fits_shwi_p (TYPE_SIZE (subtype))
+	      || tree_to_shwi (TYPE_SIZE (subtype)) <= 0
+	      || !contains_polymorphic_type_p (subtype))
+	    goto no_useful_type_info;
+
+	  HOST_WIDE_INT new_offset = cur_offset % tree_to_shwi (TYPE_SIZE (subtype));
+
+	  /* 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)
+		  > tree_to_uhwi (TYPE_SIZE (type))))
+	    goto no_useful_type_info;
+
+	  cur_offset = new_offset;
+	  type = subtype;
+	  if (!speculative)
+	    {
+	      outer_type = type;
+	      offset = cur_offset;
+	      maybe_derived_type = false;
+	    }
+	  else
+	    {
+	      speculative_outer_type = type;
+	      speculative_offset = cur_offset;
+	      speculative_maybe_derived_type = false;
+	    }
+	}
+      /* Give up on anything else.  */
+      else
+	{
+no_useful_type_info:
+	  /* 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)))
+	    {
+	      /* In these weird cases we want to accept the context.
+		 In non-speculative run we have no useful outer_type info
+		 (TODO: we may eventually want to record upper bound on the
+		  type size that can be used to prune the walk),
+		 but we still want to consider speculation that may
+		 give useful info.  */
+	      if (!speculative)
+		{
+		  clear_outer_type (expected_type);
+		  if (speculative_outer_type)
+		    {
+		      speculative = true;
+		      type = speculative_outer_type;
+		      cur_offset = speculative_offset;
+		    }
+		  else
+		    return true;
+		}
+	      else
+		clear_speculation ();
+	      return true;
+	    }
+	  else
+	    {
+	      clear_speculation ();
+	      if (speculative)
+		return true;
+	      clear_outer_type (expected_type);
+	      invalid = 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;
+  context.offset = offset;
+  context.outer_type = TYPE_MAIN_VARIANT (outer_type);
+  context.maybe_derived_type = false;
+  return context.restrict_to_inner_class (otr_type);
+}
+
+
+/* We know that the instance is stored in variable or parameter
+   (not dynamically allocated) and we want to disprove the fact
+   that it may be in construction at invocation of CALL.
+
+   For the variable to be in construction we actually need to
+   be in constructor of corresponding global variable or
+   the inline stack of CALL must contain the constructor.
+   Check this condition.  This check works safely only before
+   IPA passes, because inline stacks may become out of date
+   later.  */
+
+bool
+decl_maybe_in_construction_p (tree base, tree outer_type,
+			      gimple call, tree function)
+{
+  outer_type = TYPE_MAIN_VARIANT (outer_type);
+  gcc_assert (DECL_P (base));
+
+  /* After inlining the code unification optimizations may invalidate
+     inline stacks.  Also we need to give up on global variables after
+     IPA, because addresses of these may have been propagated to their
+     constructors.  */
+  if (DECL_STRUCT_FUNCTION (function)->after_inlining)
+    return true;
+
+  /* Pure functions can not do any changes on the dynamic type;
+     that require writting to memory.  */
+  if (!auto_var_in_fn_p (base, function)
+      && flags_from_decl_or_type (function) & (ECF_PURE | ECF_CONST))
+    return false;
+
+  for (tree block = gimple_block (call); block && TREE_CODE (block) == BLOCK;
+       block = BLOCK_SUPERCONTEXT (block))
+    if (BLOCK_ABSTRACT_ORIGIN (block)
+	&& TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
+      {
+	tree fn = BLOCK_ABSTRACT_ORIGIN (block);
+
+	if (TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
+	    || (!DECL_CXX_CONSTRUCTOR_P (fn)
+		&& !DECL_CXX_DESTRUCTOR_P (fn)))
+	  {
+	    /* Watch for clones where we constant propagated the first
+	       argument (pointer to the instance).  */
+	    fn = DECL_ABSTRACT_ORIGIN (fn);
+	    if (!fn
+		|| !is_global_var (base)
+	        || TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
+		|| (!DECL_CXX_CONSTRUCTOR_P (fn)
+		    && !DECL_CXX_DESTRUCTOR_P (fn)))
+	      continue;
+	  }
+	if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
+	  continue;
+
+	/* FIXME: this can go away once we have ODR types equivalency on
+	   LTO level.  */
+	if (in_lto_p && !polymorphic_type_binfo_p (TYPE_BINFO (outer_type)))
+	  return true;
+	tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (fn)));
+	if (types_same_for_odr (type, outer_type))
+	  return true;
+      }
+
+  if (TREE_CODE (base) == VAR_DECL
+      && is_global_var (base))
+    {
+      if (TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
+	  || (!DECL_CXX_CONSTRUCTOR_P (function)
+	      && !DECL_CXX_DESTRUCTOR_P (function)))
+	{
+	  if (!DECL_ABSTRACT_ORIGIN (function))
+	    return false;
+	  /* Watch for clones where we constant propagated the first
+	     argument (pointer to the instance).  */
+	  function = DECL_ABSTRACT_ORIGIN (function);
+	  if (!function
+	      || TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
+	      || (!DECL_CXX_CONSTRUCTOR_P (function)
+		  && !DECL_CXX_DESTRUCTOR_P (function)))
+	    return false;
+	}
+      /* FIXME: this can go away once we have ODR types equivalency on
+	 LTO level.  */
+      if (in_lto_p && !polymorphic_type_binfo_p (TYPE_BINFO (outer_type)))
+	return true;
+      tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (function)));
+      if (types_same_for_odr (type, outer_type))
+	return true;
+    }
+  return false;
+}
+
+/* Dump human readable context to F.  */
+
+void
+ipa_polymorphic_call_context::dump (FILE *f) const
+{
+  fprintf (f, "    ");
+  if (invalid)
+    fprintf (f, "Call is known to be undefined\n");
+  else
+    {
+      if (!outer_type && !offset && !speculative_outer_type)
+	fprintf (f, "Empty context\n");
+      if (outer_type || offset)
+	{
+	  fprintf (f, "Outer type:");
+	  print_generic_expr (f, outer_type, TDF_SLIM);
+	  if (maybe_derived_type)
+	    fprintf (f, " (or a derived type)");
+	  if (maybe_in_construction)
+	    fprintf (f, " (maybe in construction)");
+	  fprintf (f, " offset "HOST_WIDE_INT_PRINT_DEC,
+		   offset);
+	}
+      if (speculative_outer_type)
+	{
+	  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)");
+	  fprintf (f, " at offset "HOST_WIDE_INT_PRINT_DEC,
+		   speculative_offset);
+	}
+    }
+  fprintf(f, "\n");
+}
+
+/* Print context to stderr.  */
+
+void
+ipa_polymorphic_call_context::debug () const
+{
+  dump (stderr);
+}
+
+/* Stream out the context to OB.  */
+
+void
+ipa_polymorphic_call_context::stream_out (struct output_block *ob) const
+{
+  struct bitpack_d bp = bitpack_create (ob->main_stream);
+
+  bp_pack_value (&bp, invalid, 1);
+  bp_pack_value (&bp, maybe_in_construction, 1);
+  bp_pack_value (&bp, maybe_derived_type, 1);
+  bp_pack_value (&bp, speculative_maybe_derived_type, 1);
+  bp_pack_value (&bp, outer_type != NULL, 1);
+  bp_pack_value (&bp, offset != 0, 1);
+  bp_pack_value (&bp, speculative_outer_type != NULL, 1);
+  streamer_write_bitpack (&bp);
+
+  if (outer_type != NULL)
+    stream_write_tree (ob, outer_type, true);
+  if (offset)
+    streamer_write_hwi (ob, offset);
+  if (speculative_outer_type != NULL)
+    {
+      stream_write_tree (ob, speculative_outer_type, true);
+      streamer_write_hwi (ob, speculative_offset);
+    }
+  else
+    gcc_assert (!speculative_offset);
+}
+
+/* Stream in the context from IB and DATA_IN.  */
+
+void
+ipa_polymorphic_call_context::stream_in (struct lto_input_block *ib,
+					 struct data_in *data_in)
+{
+  struct bitpack_d bp = streamer_read_bitpack (ib);
+
+  invalid = bp_unpack_value (&bp, 1);
+  maybe_in_construction = bp_unpack_value (&bp, 1);
+  maybe_derived_type = bp_unpack_value (&bp, 1);
+  speculative_maybe_derived_type = bp_unpack_value (&bp, 1);
+  bool outer_type_p = bp_unpack_value (&bp, 1);
+  bool offset_p = bp_unpack_value (&bp, 1);
+  bool speculative_outer_type_p = bp_unpack_value (&bp, 1);
+
+  if (outer_type_p)
+    outer_type = stream_read_tree (ib, data_in);
+  else
+    outer_type = NULL;
+  if (offset_p)
+    offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
+  else
+    offset = 0;
+  if (speculative_outer_type_p)
+    {
+      speculative_outer_type = stream_read_tree (ib, data_in);
+      speculative_offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
+    }
+  else
+    {
+      speculative_outer_type = NULL;
+      speculative_offset = 0;
+    }
+}
+
+/* Proudce polymorphic call context for call method of instance
+   that is located within BASE (that is assumed to be a decl) at offset OFF. */
+
+void
+ipa_polymorphic_call_context::set_by_decl (tree base, HOST_WIDE_INT off)
+{
+  gcc_assert (DECL_P (base));
+
+  outer_type = TYPE_MAIN_VARIANT (TREE_TYPE (base));
+  offset = off;
+  clear_speculation ();
+  /* Make very conservative assumption that all objects
+     may be in construction. 
+ 
+     It is up to caller to revisit this via
+     get_dynamic_type or decl_maybe_in_construction_p.  */
+  maybe_in_construction = true;
+  maybe_derived_type = false;
+}
+
+/* CST is an invariant (address of decl), try to get meaningful
+   polymorphic call context for polymorphic call of method 
+   if instance of OTR_TYPE that is located at offset OFF of this invariant.
+   Return FALSE if nothing meaningful can be found.  */
+
+bool
+ipa_polymorphic_call_context::set_by_invariant (tree cst,
+						tree otr_type,
+						HOST_WIDE_INT off)
+{
+  HOST_WIDE_INT offset2, size, max_size;
+  tree base;
+
+  invalid = false;
+  off = 0;
+  clear_outer_type (otr_type);
+
+  if (TREE_CODE (cst) != ADDR_EXPR)
+    return false;
+
+  cst = TREE_OPERAND (cst, 0);
+  base = get_ref_base_and_extent (cst, &offset2, &size, &max_size);
+  if (!DECL_P (base) || max_size == -1 || max_size != size)
+    return false;
+
+  /* Only type inconsistent programs can have otr_type that is
+     not part of outer type.  */
+  if (otr_type && !contains_type_p (TREE_TYPE (base), off, otr_type))
+    return false;
+
+  set_by_decl (base, off);
+  return true;
+}
+
+/* See if OP is SSA name initialized as a copy or by single assignment.
+   If so, walk the SSA graph up.  */
+
+static tree
+walk_ssa_copies (tree op)
+{
+  STRIP_NOPS (op);
+  while (TREE_CODE (op) == SSA_NAME
+	 && !SSA_NAME_IS_DEFAULT_DEF (op)
+	 && SSA_NAME_DEF_STMT (op)
+	 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
+    {
+      if (gimple_assign_load_p (SSA_NAME_DEF_STMT (op)))
+	return op;
+      op = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op));
+      STRIP_NOPS (op);
+    }
+  return op;
+}
+
+/* Create polymorphic call context from IP invariant CST.
+   This is typically &global_var.
+   OTR_TYPE specify type of polymorphic call or NULL if unknown, OFF
+   is offset of call.  */
+
+ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree cst,
+							    tree otr_type,
+							    HOST_WIDE_INT off)
+{
+  clear_speculation ();
+  set_by_invariant (cst, otr_type, off);
+}
+
+/* Build context for pointer REF contained in FNDECL at statement STMT.
+   if INSTANCE is non-NULL, return pointer to the object described by
+   the context or DECL where context is contained in.  */
+
+ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree fndecl,
+							    tree ref,
+							    gimple stmt,
+							    tree *instance)
+{
+  tree otr_type = NULL;
+  tree base_pointer;
+
+  if (TREE_CODE (ref) == OBJ_TYPE_REF)
+    {
+      otr_type = obj_type_ref_class (ref);
+      base_pointer = OBJ_TYPE_REF_OBJECT (ref);
+    }
+  else
+    base_pointer = ref;
+
+  /* Set up basic info in case we find nothing interesting in the analysis.  */
+  clear_speculation ();
+  clear_outer_type (otr_type);
+  invalid = false;
+
+  /* Walk SSA for outer object.  */
+  do 
+    {
+      base_pointer = walk_ssa_copies (base_pointer);
+      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);
+		  offset
+		    += offset2 + mem_ref_offset (base).to_short_addr () * BITS_PER_UNIT;
+		  outer_type = NULL;
+		}
+	      /* We found base object.  In this case the outer_type
+		 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
+		      && !contains_type_p (TREE_TYPE (base),
+					   offset + offset2, otr_type))
+		    {
+		      invalid = true;
+		      if (instance)
+			*instance = base_pointer;
+		      return;
+		    }
+		  set_by_decl (base, offset + offset2);
+		  if (maybe_in_construction && stmt)
+		    maybe_in_construction
+		     = decl_maybe_in_construction_p (base,
+						     outer_type,
+						     stmt,
+						     fndecl);
+		  if (instance)
+		    *instance = base;
+		  return;
+		}
+	      else
+		break;
+	    }
+	  else
+	    break;
+	}
+      else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR
+	       && tree_fits_uhwi_p (TREE_OPERAND (base_pointer, 1)))
+	{
+	  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))
+	{
+	  outer_type
+	     = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
+	  gcc_assert (TREE_CODE (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 (otr_type
+	      && !contains_type_p (outer_type, offset,
+				   otr_type))
+	    {
+	      outer_type = NULL;
+	      if (instance)
+		*instance = base_pointer;
+	      return;
+	    }
+
+	  /* If the function is constructor or destructor, then
+	     the type is possibly in construction, but we know
+	     it is not derived type.  */
+	  if (DECL_CXX_CONSTRUCTOR_P (fndecl)
+	      || DECL_CXX_DESTRUCTOR_P (fndecl))
+	    {
+	      maybe_in_construction = true;
+	      maybe_derived_type = false;
+	    }
+	  else
+	    {
+	      maybe_derived_type = true;
+	      maybe_in_construction = false;
+	    }
+	  if (instance)
+	    *instance = base_pointer;
+	  return;
+	}
+      /* 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)))
+	{
+	  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))
+	    { 
+	      invalid = true;
+	      if (instance)
+		*instance = base_pointer;
+	      return;
+	    }
+	  maybe_derived_type = false;
+	  maybe_in_construction = false;
+	  if (instance)
+	    *instance = base_pointer;
+	  return;
+	}
+    }
+
+  tree base_type = TREE_TYPE (base_pointer);
+
+  if (TREE_CODE (base_pointer) == SSA_NAME
+      && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
+      && TREE_CODE (SSA_NAME_VAR (base_pointer)) != PARM_DECL)
+    {
+      invalid = true;
+      if (instance)
+	*instance = base_pointer;
+      return;
+    }
+  if (TREE_CODE (base_pointer) == SSA_NAME
+      && SSA_NAME_DEF_STMT (base_pointer)
+      && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
+    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;
+    }
+  /* 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.  */
+  if (instance)
+    *instance = base_pointer;
+  return;
+}
+
+/* Structure to be passed in between detect_type_change and
+   check_stmt_for_type_change.  */
+
+struct type_change_info
+{
+  /* Offset into the object where there is the virtual method pointer we are
+     looking for.  */
+  HOST_WIDE_INT offset;
+  /* The declaration or SSA_NAME pointer of the base that we are checking for
+     type change.  */
+  tree instance;
+  /* The reference to virtual table pointer used.  */
+  tree vtbl_ptr_ref;
+  tree otr_type;
+  /* If we actually can tell the type that the object has changed to, it is
+     stored in this field.  Otherwise it remains NULL_TREE.  */
+  tree known_current_type;
+  HOST_WIDE_INT known_current_offset;
+
+  /* Set to true if dynamic type change has been detected.  */
+  bool type_maybe_changed;
+  /* Set to true if multiple types have been encountered.  known_current_type
+     must be disregarded in that case.  */
+  bool multiple_types_encountered;
+  /* Set to true if we possibly missed some dynamic type changes and we should
+     consider the set to be speculative.  */
+  bool speculative;
+  bool seen_unanalyzed_store;
+};
+
+/* Return true if STMT is not call and can modify a virtual method table pointer.
+   We take advantage of fact that vtable stores must appear within constructor
+   and destructor functions.  */
+
+static bool
+noncall_stmt_may_be_vtbl_ptr_store (gimple stmt)
+{
+  if (is_gimple_assign (stmt))
+    {
+      tree lhs = gimple_assign_lhs (stmt);
+
+      if (gimple_clobber_p (stmt))
+	return false;
+      if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
+	{
+	  if (flag_strict_aliasing
+	      && !POINTER_TYPE_P (TREE_TYPE (lhs)))
+	    return false;
+
+	  if (TREE_CODE (lhs) == COMPONENT_REF
+	      && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
+	    return false;
+	  /* In the future we might want to use get_base_ref_and_offset to find
+	     if there is a field corresponding to the offset and if so, proceed
+	     almost like if it was a component ref.  */
+	}
+    }
+
+  /* Code unification may mess with inline stacks.  */
+  if (cfun->after_inlining)
+    return true;
+
+  /* Walk the inline stack and watch out for ctors/dtors.
+     TODO: Maybe we can require the store to appear in toplevel
+     block of CTOR/DTOR.  */
+  for (tree block = gimple_block (stmt); block && TREE_CODE (block) == BLOCK;
+       block = BLOCK_SUPERCONTEXT (block))
+    if (BLOCK_ABSTRACT_ORIGIN (block)
+	&& TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
+      {
+	tree fn = BLOCK_ABSTRACT_ORIGIN (block);
+
+	if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
+	  return false;
+	return (TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
+		&& (DECL_CXX_CONSTRUCTOR_P (fn)
+		    || DECL_CXX_DESTRUCTOR_P (fn)));
+      }
+  return (TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
+	  && (DECL_CXX_CONSTRUCTOR_P (current_function_decl)
+	      || DECL_CXX_DESTRUCTOR_P (current_function_decl)));
+}
+
+/* If STMT can be proved to be an assignment to the virtual method table
+   pointer of ANALYZED_OBJ and the type associated with the new table
+   identified, return the type.  Otherwise return NULL_TREE.  */
+
+static tree
+extr_type_from_vtbl_ptr_store (gimple stmt, struct type_change_info *tci,
+			       HOST_WIDE_INT *type_offset)
+{
+  HOST_WIDE_INT offset, size, max_size;
+  tree lhs, rhs, base;
+
+  if (!gimple_assign_single_p (stmt))
+    return NULL_TREE;
+
+  lhs = gimple_assign_lhs (stmt);
+  rhs = gimple_assign_rhs1 (stmt);
+  if (TREE_CODE (lhs) != COMPONENT_REF
+      || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
+     {
+	if (dump_file)
+	  fprintf (dump_file, "  LHS is not virtual table.\n");
+	return NULL_TREE;
+     }
+
+  if (tci->vtbl_ptr_ref && operand_equal_p (lhs, tci->vtbl_ptr_ref, 0))
+    ;
+  else
+    {
+      base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
+      if (offset != tci->offset
+	  || size != POINTER_SIZE
+	  || max_size != POINTER_SIZE)
+	{
+	  if (dump_file)
+	    fprintf (dump_file, "    wrong offset %i!=%i or size %i\n",
+		     (int)offset, (int)tci->offset, (int)size);
+	  return NULL_TREE;
+	}
+      if (DECL_P (tci->instance))
+	{
+	  if (base != tci->instance)
+	    {
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "    base:");
+		  print_generic_expr (dump_file, base, TDF_SLIM);
+		  fprintf (dump_file, " does not match instance:");
+		  print_generic_expr (dump_file, tci->instance, TDF_SLIM);
+		  fprintf (dump_file, "\n");
+		}
+	      return NULL_TREE;
+	    }
+	}
+      else if (TREE_CODE (base) == MEM_REF)
+	{
+	  if (!operand_equal_p (tci->instance, TREE_OPERAND (base, 0), 0)
+	      || !integer_zerop (TREE_OPERAND (base, 1)))
+	    {
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "    base mem ref:");
+		  print_generic_expr (dump_file, base, TDF_SLIM);
+		  fprintf (dump_file, " has nonzero offset or does not match instance:");
+		  print_generic_expr (dump_file, tci->instance, TDF_SLIM);
+		  fprintf (dump_file, "\n");
+		}
+	      return NULL_TREE;
+	    }
+	}
+      else if (!operand_equal_p (tci->instance, base, 0)
+	       || tci->offset)
+	{
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "    base:");
+	      print_generic_expr (dump_file, base, TDF_SLIM);
+	      fprintf (dump_file, " does not match instance:");
+	      print_generic_expr (dump_file, tci->instance, TDF_SLIM);
+	      fprintf (dump_file, " with offset %i\n", (int)tci->offset);
+	    }
+	  return NULL_TREE;
+	}
+    }
+
+  tree vtable;
+  unsigned HOST_WIDE_INT offset2;
+
+  if (!vtable_pointer_value_to_vtable (rhs, &vtable, &offset2))
+    {
+      if (dump_file)
+	fprintf (dump_file, "    Failed to lookup binfo\n");
+      return NULL;
+    }
+
+  tree binfo = subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
+					       offset2, vtable);
+  if (!binfo)
+    {
+      if (dump_file)
+	fprintf (dump_file, "    Construction vtable used\n");
+      /* FIXME: We should suport construction contextes.  */
+      return NULL;
+    }
+ 
+  *type_offset = tree_to_shwi (BINFO_OFFSET (binfo)) * BITS_PER_UNIT;
+  return DECL_CONTEXT (vtable);
+}
+
+/* Record dynamic type change of TCI to TYPE.  */
+
+static void
+record_known_type (struct type_change_info *tci, tree type, HOST_WIDE_INT offset)
+{
+  if (dump_file)
+    {
+      if (type)
+	{
+          fprintf (dump_file, "  Recording type: ");
+	  print_generic_expr (dump_file, type, TDF_SLIM);
+          fprintf (dump_file, " at offset %i\n", (int)offset);
+	}
+     else
+       fprintf (dump_file, "  Recording unknown type\n");
+    }
+
+  /* If we found a constructor of type that is not polymorphic or
+     that may contain the type in question as a field (not as base),
+     restrict to the inner class first to make type matching bellow
+     happier.  */
+  if (type
+      && (offset
+          || (TREE_CODE (type) != RECORD_TYPE
+	      || !polymorphic_type_binfo_p (TYPE_BINFO (type)))))
+    {
+      ipa_polymorphic_call_context context;
+
+      context.offset = offset;
+      context.outer_type = type;
+      context.maybe_in_construction = false;
+      context.maybe_derived_type = false;
+      /* If we failed to find the inner type, we know that the call
+	 would be undefined for type produced here.  */
+      if (!context.restrict_to_inner_class (tci->otr_type))
+	{
+	  if (dump_file)
+	    fprintf (dump_file, "  Ignoring; does not contain otr_type\n");
+	  return;
+	}
+      /* Watch for case we reached an POD type and anticipate placement
+	 new.  */
+      if (!context.maybe_derived_type)
+	{
+          type = context.outer_type;
+          offset = context.offset;
+	}
+    }
+  if (tci->type_maybe_changed
+      && (!types_same_for_odr (type, tci->known_current_type)
+	  || offset != tci->known_current_offset))
+    tci->multiple_types_encountered = true;
+  tci->known_current_type = TYPE_MAIN_VARIANT (type);
+  tci->known_current_offset = offset;
+  tci->type_maybe_changed = true;
+}
+
+/* Callback of walk_aliased_vdefs and a helper function for
+   detect_type_change to check whether a particular statement may modify
+   the virtual table pointer, and if possible also determine the new type of
+   the (sub-)object.  It stores its result into DATA, which points to a
+   type_change_info structure.  */
+
+static bool
+check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
+{
+  gimple stmt = SSA_NAME_DEF_STMT (vdef);
+  struct type_change_info *tci = (struct type_change_info *) data;
+  tree fn;
+
+  /* If we already gave up, just terminate the rest of walk.  */
+  if (tci->multiple_types_encountered)
+    return true;
+
+  if (is_gimple_call (stmt))
+    {
+      if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
+	return false;
+
+      /* Check for a constructor call.  */
+      if ((fn = gimple_call_fndecl (stmt)) != NULL_TREE
+	  && DECL_CXX_CONSTRUCTOR_P (fn)
+	  && TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
+	  && gimple_call_num_args (stmt))
+      {
+	tree op = walk_ssa_copies (gimple_call_arg (stmt, 0));
+	tree type = method_class_type (TREE_TYPE (fn));
+	HOST_WIDE_INT offset = 0, size, max_size;
+
+	if (dump_file)
+	  {
+	    fprintf (dump_file, "  Checking constructor call: ");
+	    print_gimple_stmt (dump_file, stmt, 0, 0);
+	  }
+
+	/* See if THIS parameter seems like instance pointer.  */
+	if (TREE_CODE (op) == ADDR_EXPR)
+	  {
+	    op = get_ref_base_and_extent (TREE_OPERAND (op, 0),
+					  &offset, &size, &max_size);
+	    if (size != max_size || max_size == -1)
+	      {
+                tci->speculative = true;
+	        return false;
+	      }
+	    if (op && TREE_CODE (op) == MEM_REF)
+	      {
+		if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
+		  {
+                    tci->speculative = true;
+		    return false;
+		  }
+		offset += tree_to_shwi (TREE_OPERAND (op, 1))
+			  * BITS_PER_UNIT;
+		op = TREE_OPERAND (op, 0);
+	      }
+	    else if (DECL_P (op))
+	      ;
+	    else
+	      {
+                tci->speculative = true;
+	        return false;
+	      }
+	    op = walk_ssa_copies (op);
+	  }
+	if (operand_equal_p (op, tci->instance, 0)
+	    && TYPE_SIZE (type)
+	    && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST
+	    && tree_fits_shwi_p (TYPE_SIZE (type))
+	    && tree_to_shwi (TYPE_SIZE (type)) + offset > tci->offset)
+	  {
+	    record_known_type (tci, type, tci->offset - offset);
+	    return true;
+	  }
+      }
+     /* Calls may possibly change dynamic type by placement new. Assume
+        it will not happen, but make result speculative only.  */
+     if (dump_file)
+	{
+          fprintf (dump_file, "  Function call may change dynamic type:");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+     tci->speculative = true;
+     return false;
+   }
+  /* Check for inlined virtual table store.  */
+  else if (noncall_stmt_may_be_vtbl_ptr_store (stmt))
+    {
+      tree type;
+      HOST_WIDE_INT offset = 0;
+      if (dump_file)
+	{
+	  fprintf (dump_file, "  Checking vtbl store: ");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	}
+
+      type = extr_type_from_vtbl_ptr_store (stmt, tci, &offset);
+      gcc_assert (!type || TYPE_MAIN_VARIANT (type) == type);
+      if (!type)
+	{
+	  if (dump_file)
+	    fprintf (dump_file, "  Unanalyzed store may change type.\n");
+	  tci->seen_unanalyzed_store = true;
+	  tci->speculative = true;
+	}
+      else
+        record_known_type (tci, type, offset);
+      return true;
+    }
+  else
+    return false;
+}
+
+/* THIS is polymorphic call context obtained from get_polymorphic_context.
+   OTR_OBJECT is pointer to the instance returned by OBJ_TYPE_REF_OBJECT.
+   INSTANCE is pointer to the outer instance as returned by
+   get_polymorphic_context.  To avoid creation of temporary expressions,
+   INSTANCE may also be an declaration of get_polymorphic_context found the
+   value to be in static storage.
+
+   If the type of instance is not fully determined
+   (either OUTER_TYPE is unknown or MAYBE_IN_CONSTRUCTION/INCLUDE_DERIVED_TYPES
+   is set), try to walk memory writes and find the actual construction of the
+   instance.
+
+   We do not include this analysis in the context analysis itself, because
+   it needs memory SSA to be fully built and the walk may be expensive.
+   So it is not suitable for use withing fold_stmt and similar uses.  */
+
+bool
+ipa_polymorphic_call_context::get_dynamic_type (tree instance,
+						tree otr_object,
+						tree otr_type,
+						gimple call)
+{
+  struct type_change_info tci;
+  ao_ref ao;
+  bool function_entry_reached = false;
+  tree instance_ref = NULL;
+  gimple stmt = call;
+  /* Remember OFFSET before it is modified by restrict_to_inner_class.
+     This is because we do not update INSTANCE when walking inwards.  */
+  HOST_WIDE_INT instance_offset = offset;
+
+  otr_type = TYPE_MAIN_VARIANT (otr_type);
+
+  /* Walk into inner type. This may clear maybe_derived_type and save us
+     from useless work.  It also makes later comparsions with static type
+     easier.  */
+  if (outer_type)
+    {
+      if (!restrict_to_inner_class (otr_type))
+        return false;
+    }
+
+  if (!maybe_in_construction && !maybe_derived_type)
+    return false;
+
+  /* We need to obtain refernce to virtual table pointer.  It is better
+     to look it up in the code rather than build our own.  This require bit
+     of pattern matching, but we end up verifying that what we found is
+     correct. 
+
+     What we pattern match is:
+
+       tmp = instance->_vptr.A;   // vtbl ptr load
+       tmp2 = tmp[otr_token];	  // vtable lookup
+       OBJ_TYPE_REF(tmp2;instance->0) (instance);
+ 
+     We want to start alias oracle walk from vtbl pointer load,
+     but we may not be able to identify it, for example, when PRE moved the
+     load around.  */
+
+  if (gimple_code (call) == GIMPLE_CALL)
+    {
+      tree ref = gimple_call_fn (call);
+      HOST_WIDE_INT offset2, size, max_size;
+
+      if (TREE_CODE (ref) == OBJ_TYPE_REF)
+	{
+	  ref = OBJ_TYPE_REF_EXPR (ref);
+	  ref = walk_ssa_copies (ref);
+
+	  /* Check if definition looks like vtable lookup.  */
+	  if (TREE_CODE (ref) == SSA_NAME
+	      && !SSA_NAME_IS_DEFAULT_DEF (ref)
+	      && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref))
+	      && TREE_CODE (gimple_assign_rhs1
+			     (SSA_NAME_DEF_STMT (ref))) == MEM_REF)
+	    {
+	      ref = get_base_address
+		     (TREE_OPERAND (gimple_assign_rhs1
+				     (SSA_NAME_DEF_STMT (ref)), 0));
+	      ref = walk_ssa_copies (ref);
+	      /* Find base address of the lookup and see if it looks like
+		 vptr load.  */
+	      if (TREE_CODE (ref) == SSA_NAME
+		  && !SSA_NAME_IS_DEFAULT_DEF (ref)
+		  && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref)))
+		{
+		  tree ref_exp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ref));
+		  tree base_ref = get_ref_base_and_extent
+				   (ref_exp, &offset2, &size, &max_size);
+
+		  /* Finally verify that what we found looks like read from OTR_OBJECT
+		     or from INSTANCE with offset OFFSET.  */
+		  if (base_ref
+		      && ((TREE_CODE (base_ref) == MEM_REF
+		           && ((offset2 == instance_offset
+		                && TREE_OPERAND (base_ref, 0) == instance)
+			       || (!offset2 && TREE_OPERAND (base_ref, 0) == otr_object)))
+			  || (DECL_P (instance) && base_ref == instance
+			      && offset2 == instance_offset)))
+		    {
+		      stmt = SSA_NAME_DEF_STMT (ref);
+		      instance_ref = ref_exp;
+		    }
+		}
+	    }
+	}
+    }
+ 
+  /* If we failed to look up the refernece in code, build our own.  */
+  if (!instance_ref)
+    {
+      /* If the statement in question does not use memory, we can't tell
+	 anything.  */
+      if (!gimple_vuse (stmt))
+	return false;
+      ao_ref_init_from_ptr_and_size (&ao, otr_object, NULL);
+    }
+  else
+  /* Otherwise use the real reference.  */
+    ao_ref_init (&ao, instance_ref);
+
+  /* We look for vtbl pointer read.  */
+  ao.size = POINTER_SIZE;
+  ao.max_size = ao.size;
+  ao.ref_alias_set
+    = get_deref_alias_set (TREE_TYPE (BINFO_VTABLE (TYPE_BINFO (otr_type))));
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "Determining dynamic type for call: ");
+      print_gimple_stmt (dump_file, call, 0, 0);
+      fprintf (dump_file, "  Starting walk at: ");
+      print_gimple_stmt (dump_file, stmt, 0, 0);
+      fprintf (dump_file, "  instance pointer: ");
+      print_generic_expr (dump_file, otr_object, TDF_SLIM);
+      fprintf (dump_file, "  Outer instance pointer: ");
+      print_generic_expr (dump_file, instance, TDF_SLIM);
+      fprintf (dump_file, " offset: %i (bits)", (int)offset);
+      fprintf (dump_file, " vtbl reference: ");
+      print_generic_expr (dump_file, instance_ref, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  tci.offset = offset;
+  tci.instance = instance;
+  tci.vtbl_ptr_ref = instance_ref;
+  gcc_assert (TREE_CODE (instance) != MEM_REF);
+  tci.known_current_type = NULL_TREE;
+  tci.known_current_offset = 0;
+  tci.otr_type = otr_type;
+  tci.type_maybe_changed = false;
+  tci.multiple_types_encountered = false;
+  tci.speculative = false;
+  tci.seen_unanalyzed_store = false;
+
+  walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
+		      &tci, NULL, &function_entry_reached);
+
+  /* If we did not find any type changing statements, we may still drop
+     maybe_in_construction flag if the context already have outer type. 
+
+     Here we make special assumptions about both constructors and
+     destructors which are all the functions that are allowed to alter the
+     VMT pointers.  It assumes that destructors begin with assignment into
+     all VMT pointers and that constructors essentially look in the
+     following way:
+
+     1) The very first thing they do is that they call constructors of
+     ancestor sub-objects that have them.
+
+     2) Then VMT pointers of this and all its ancestors is set to new
+     values corresponding to the type corresponding to the constructor.
+
+     3) Only afterwards, other stuff such as constructor of member
+     sub-objects and the code written by the user is run.  Only this may
+     include calling virtual functions, directly or indirectly.
+
+     4) placement new can not be used to change type of non-POD statically
+     allocated variables.
+
+     There is no way to call a constructor of an ancestor sub-object in any
+     other way.
+
+     This means that we do not have to care whether constructors get the
+     correct type information because they will always change it (in fact,
+     if we define the type to be given by the VMT pointer, it is undefined).
+
+     The most important fact to derive from the above is that if, for some
+     statement in the section 3, we try to detect whether the dynamic type
+     has changed, we can safely ignore all calls as we examine the function
+     body backwards until we reach statements in section 2 because these
+     calls cannot be ancestor constructors or destructors (if the input is
+     not bogus) and so do not change the dynamic type (this holds true only
+     for automatically allocated objects but at the moment we devirtualize
+     only these).  We then must detect that statements in section 2 change
+     the dynamic type and can try to derive the new type.  That is enough
+     and we can stop, we will never see the calls into constructors of
+     sub-objects in this code. 
+
+     Therefore if the static outer type was found (outer_type)
+     we can safely ignore tci.speculative that is set on calls and give up
+     only if there was dyanmic type store that may affect given variable
+     (seen_unanalyzed_store)  */
+
+  if (!tci.type_maybe_changed
+      || (outer_type
+	  && !tci.seen_unanalyzed_store
+	  && !tci.multiple_types_encountered
+	  && offset == tci.offset
+	  && types_same_for_odr (tci.known_current_type,
+				 outer_type)))
+    {
+      if (!outer_type || tci.seen_unanalyzed_store)
+	return false;
+      if (maybe_in_construction)
+        maybe_in_construction = false;
+      if (dump_file)
+	fprintf (dump_file, "  No dynamic type change found.\n");
+      return true;
+    }
+
+  if (tci.known_current_type
+      && !function_entry_reached
+      && !tci.multiple_types_encountered)
+    {
+      if (!tci.speculative)
+	{
+	  outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
+	  offset = tci.known_current_offset;
+	  maybe_in_construction = false;
+	  maybe_derived_type = false;
+	  if (dump_file)
+	    fprintf (dump_file, "  Determined dynamic type.\n");
+	}
+      else if (!speculative_outer_type
+	       || speculative_maybe_derived_type)
+	{
+	  speculative_outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
+	  speculative_offset = tci.known_current_offset;
+	  speculative_maybe_derived_type = false;
+	  if (dump_file)
+	    fprintf (dump_file, "  Determined speculative dynamic type.\n");
+	}
+    }
+  else if (dump_file)
+    {
+      fprintf (dump_file, "  Found multiple types%s%s\n",
+	       function_entry_reached ? " (function entry reached)" : "",
+	       function_entry_reached ? " (multiple types encountered)" : "");
+    }
+
+  return true;
+}
+
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 215614)
+++ ipa-devirt.c	(working copy)
@@ -135,9 +135,6 @@ along with GCC; see the file COPYING3.
 #include "stor-layout.h"
 #include "intl.h"
 #include "hash-map.h"
-#include "data-streamer.h"
-#include "lto-streamer.h"
-#include "streamer-hooks.h"
 
 /* Hash based set of pairs of types.  */
 typedef struct
@@ -213,24 +210,6 @@ struct GTY(()) odr_type_d
   bool odr_violated;
 };
 
-static bool contains_type_p (tree, HOST_WIDE_INT, tree);
-
-
-/* Return true if BINFO corresponds to a type with virtual methods. 
-
-   Every type has several BINFOs.  One is the BINFO associated by the type
-   while other represents bases of derived types.  The BINFOs representing
-   bases do not have BINFO_VTABLE pointer set when this is the single
-   inheritance (because vtables are shared).  Look up the BINFO of type
-   and check presence of its vtable.  */
-
-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)));
-}
-
 /* Return TRUE if all derived types of T are known and thus
    we may consider the walk of derived type complete.
 
@@ -238,8 +217,8 @@ polymorphic_type_binfo_p (tree binfo)
    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)
+bool
+type_all_derivations_known_p (const_tree t)
 {
   if (TYPE_FINAL_P (t))
     return true;
@@ -460,7 +439,7 @@ types_same_for_odr (const_tree type1, co
    In non-LTO it is always decide, in LTO however it depends in the type has
    ODR info attached.  */
 
-static bool
+bool
 types_odr_comparable (tree t1, tree t2)
 {
   return (!in_lto_p
@@ -475,7 +454,7 @@ types_odr_comparable (tree t1, tree t2)
 /* Return true if T1 and T2 are ODR equivalent.  If ODR equivalency is not
    known, be conservative and return false.  */
 
-static bool
+bool
 types_must_be_same_for_odr (tree t1, tree t2)
 {
   if (types_odr_comparable (t1, t2))
@@ -1438,6 +1417,17 @@ register_odr_type (tree type)
     get_odr_type (type, true);
 }
 
+/* Return true if type is known to have no derivations.  */
+
+bool
+type_known_to_have_no_deriavations_p (tree t)
+{
+  return (type_all_derivations_known_p (t)
+	  && (TYPE_FINAL_P (t)
+	      || (odr_hash
+		  && !get_odr_type (t, true)->derived_types.length())));
+}
+
 /* Dump ODR type T and all its derrived type.  INDENT specify indentation for
    recusive printing.  */
 
@@ -1983,364 +1973,9 @@ devirt_node_removal_hook (struct cgraph_
     free_polymorphic_call_targets_hash ();
 }
 
-/* Return true when TYPE contains an polymorphic type and thus is interesting
-   for devirtualization machinery.  */
-
-bool
-contains_polymorphic_type_p (const_tree type)
-{
-  type = TYPE_MAIN_VARIANT (type);
-
-  if (RECORD_OR_UNION_TYPE_P (type))
-    {
-      if (TYPE_BINFO (type)
-          && polymorphic_type_binfo_p (TYPE_BINFO (type)))
-	return true;
-      for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
-	if (TREE_CODE (fld) == FIELD_DECL
-	    && !DECL_ARTIFICIAL (fld)
-	    && contains_polymorphic_type_p (TREE_TYPE (fld)))
-	  return true;
-      return false;
-    }
-  if (TREE_CODE (type) == ARRAY_TYPE)
-    return contains_polymorphic_type_p (TREE_TYPE (type));
-  return false;
-}
-
-/* Return true if it seems valid to use placement new to build EXPECTED_TYPE
-   at possition CUR_OFFSET within TYPE.  
-
-   POD can be changed to an instance of a polymorphic type by
-   placement new.  Here we play safe and assume that any
-   non-polymorphic type is POD.  */
-bool
-possible_placement_new (tree type, tree expected_type,
-			HOST_WIDE_INT cur_offset)
-{
-  return ((TREE_CODE (type) != RECORD_TYPE
-	   || !TYPE_BINFO (type)
-	   || cur_offset >= BITS_PER_WORD
-	   || !polymorphic_type_binfo_p (TYPE_BINFO (type)))
-	  && (!TYPE_SIZE (type)
-	      || !tree_fits_shwi_p (TYPE_SIZE (type))
-	      || (cur_offset
-		  + (expected_type ? tree_to_uhwi (TYPE_SIZE (expected_type))
-		     : 1)
-		  <= tree_to_uhwi (TYPE_SIZE (type)))));
-}
-
-/* THIS->OUTER_TYPE is a type of memory object where object of EXPECTED_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
-   to represent it.
-
-   If EXPECTED_TYPE is NULL, just find outermost polymorphic type with
-   virtual table present at possition OFFSET.
-
-   For example when THIS 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
-   THIS->OUTER_TYPE to EXPECTED_TYPE and THIS->OFFSET to NULL. 
-   Return true when lookup was sucesful.  */
-
-bool
-ipa_polymorphic_call_context::restrict_to_inner_class (tree expected_type)
-{
-  tree type = outer_type;
-  HOST_WIDE_INT cur_offset = offset;
-  bool speculative = false;
-  bool size_unknown = false;
-
-  /* Update OUTER_TYPE to match EXPECTED_TYPE if it is not set.  */
-  if (!outer_type)
-    {
-      clear_outer_type (expected_type);
-      type = expected_type;
-      cur_offset = 0;
-    }
- /* See if OFFSET points inside OUTER_TYPE.  If it does not, we know
-    that the context is either invalid, or the instance type must be
-    derived from OUTER_TYPE.
-
-    Because the instance type may contain field whose type is of OUTER_TYPE,
-    we can not derive any effective information about it.
-
-    TODO: In the case we know all derrived types, we can definitely do better
-    here.  */
-  else if (TYPE_SIZE (outer_type)
-	   && tree_fits_shwi_p (TYPE_SIZE (outer_type))
-	   && tree_to_shwi (TYPE_SIZE (outer_type)) >= 0
-	   && tree_to_shwi (TYPE_SIZE (outer_type)) <= offset)
-   {
-     clear_outer_type (expected_type);
-     type = expected_type;
-     cur_offset = 0;
-
-     /* If derived type is not allowed, we know that the context is invalid.  */
-     if (!maybe_derived_type)
-       {
-	 clear_speculation ();
-	 invalid = true;
-	 return false;
-       }
-   }
-
-  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 (!type)
-    goto no_useful_type_info;
-
-  /* Find the sub-object the constant actually refers to and mark whether it is
-     an artificial one (as opposed to a user-defined one).
-
-     This loop is performed twice; first time for outer_type and second time
-     for speculative_outer_type.  The second run has SPECULATIVE set.  */
-  while (true)
-    {
-      HOST_WIDE_INT pos, size;
-      tree fld;
-
-      /* If we do not know size of TYPE, we need to be more conservative
-         about accepting cases where we can not find EXPECTED_TYPE.
-	 Generally the types that do matter here are of constant size.
-	 Size_unknown case should be very rare.  */
-      if (TYPE_SIZE (type)
-	  && tree_fits_shwi_p (TYPE_SIZE (type))
-	  && tree_to_shwi (TYPE_SIZE (type)) >= 0)
-	size_unknown = false;
-      else
-	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
-	      && TREE_CODE (type) == RECORD_TYPE
-	      && TYPE_BINFO (type)
-	      && polymorphic_type_binfo_p (TYPE_BINFO (type))))
-	{
-	  if (speculative)
-	    {
-	      /* If we did not match the offset, just give up on speculation.  */
-	      if (cur_offset != 0
-		  /* Also check if speculation did not end up being same as
-		     non-speculation.  */
-		  || (types_must_be_same_for_odr (speculative_outer_type,
-						  outer_type)
-		      && (maybe_derived_type
-			  == speculative_maybe_derived_type)))
-		clear_speculation ();
-	      return true;
-	    }
-	  else
-	    {
-	      /* If type is known to be final, do not worry about derived
-		 types.  Testing it here may help us to avoid speculation.  */
-	      if (type_all_derivations_known_p (outer_type)
-		  && (TYPE_FINAL_P (outer_type)
-		      || (odr_hash
-			  && !get_odr_type (outer_type, true)->derived_types.length())))
-		maybe_derived_type = false;
-
-	      /* Type can not contain itself on an non-zero offset.  In that case
-		 just give up.  Still accept the case where size is now known.
-		 Either the second copy may appear past the end of type or within
-		 the non-POD buffer located inside the variably sized type
-		 itself.  */
-	      if (cur_offset != 0)
-		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)
-		{
-		  clear_speculation ();
-	          return true;
-		}
-	      /* Otherwise look into speculation now.  */
-	      else
-		{
-		  speculative = true;
-		  type = speculative_outer_type;
-		  cur_offset = speculative_offset;
-		  continue;
-		}
-	    }
-	}
-
-      /* 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 <= cur_offset && (pos + size) > cur_offset)
-		break;
-	    }
-
-	  if (!fld)
-	    goto no_useful_type_info;
-
-	  type = TYPE_MAIN_VARIANT (TREE_TYPE (fld));
-	  cur_offset -= pos;
-	  /* DECL_ARTIFICIAL represents a basetype.  */
-	  if (!DECL_ARTIFICIAL (fld))
-	    {
-	      if (!speculative)
-		{
-		  outer_type = type;
-		  offset = cur_offset;
-		  /* As soon as we se an field containing the type,
-		     we know we are not looking for derivations.  */
-		  maybe_derived_type = false;
-		}
-	      else
-		{
-		  speculative_outer_type = type;
-		  speculative_offset = cur_offset;
-		  speculative_maybe_derived_type = false;
-		}
-	    }
-	}
-      else if (TREE_CODE (type) == ARRAY_TYPE)
-	{
-	  tree subtype = TYPE_MAIN_VARIANT (TREE_TYPE (type));
-
-	  /* Give up if we don't know array size.  */
-	  if (!TYPE_SIZE (subtype)
-	      || !tree_fits_shwi_p (TYPE_SIZE (subtype))
-	      || tree_to_shwi (TYPE_SIZE (subtype)) <= 0
-	      || !contains_polymorphic_type_p (subtype))
-	    goto no_useful_type_info;
-
-	  HOST_WIDE_INT new_offset = cur_offset % tree_to_shwi (TYPE_SIZE (subtype));
-
-	  /* 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)
-		  > tree_to_uhwi (TYPE_SIZE (type))))
-	    goto no_useful_type_info;
-
-	  cur_offset = new_offset;
-	  type = subtype;
-	  if (!speculative)
-	    {
-	      outer_type = type;
-	      offset = cur_offset;
-	      maybe_derived_type = false;
-	    }
-	  else
-	    {
-	      speculative_outer_type = type;
-	      speculative_offset = cur_offset;
-	      speculative_maybe_derived_type = false;
-	    }
-	}
-      /* Give up on anything else.  */
-      else
-	{
-no_useful_type_info:
-	  /* 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)))
-	    {
-	      /* In these weird cases we want to accept the context.
-		 In non-speculative run we have no useful outer_type info
-		 (TODO: we may eventually want to record upper bound on the
-		  type size that can be used to prune the walk),
-		 but we still want to consider speculation that may
-		 give useful info.  */
-	      if (!speculative)
-		{
-		  clear_outer_type (expected_type);
-		  if (speculative_outer_type)
-		    {
-		      speculative = true;
-		      type = speculative_outer_type;
-		      cur_offset = speculative_offset;
-		    }
-		  else
-		    return true;
-		}
-	      else
-		clear_speculation ();
-	      return true;
-	    }
-	  else
-	    {
-	      clear_speculation ();
-	      if (speculative)
-		return true;
-	      clear_outer_type (expected_type);
-	      invalid = 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;
-  context.offset = offset;
-  context.outer_type = TYPE_MAIN_VARIANT (outer_type);
-  context.maybe_derived_type = false;
-  return context.restrict_to_inner_class (otr_type);
-}
-
 /* Lookup base of BINFO that has virtual table VTABLE with OFFSET.  */
 
-static tree
+tree
 subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset,
 				tree vtable)
 {
@@ -2438,1117 +2073,6 @@ vtable_pointer_value_to_binfo (const_tre
 					 offset, vtable);
 }
 
-/* We know that the instance is stored in variable or parameter
-   (not dynamically allocated) and we want to disprove the fact
-   that it may be in construction at invocation of CALL.
-
-   For the variable to be in construction we actually need to
-   be in constructor of corresponding global variable or
-   the inline stack of CALL must contain the constructor.
-   Check this condition.  This check works safely only before
-   IPA passes, because inline stacks may become out of date
-   later.  */
-
-bool
-decl_maybe_in_construction_p (tree base, tree outer_type,
-			      gimple call, tree function)
-{
-  outer_type = TYPE_MAIN_VARIANT (outer_type);
-  gcc_assert (DECL_P (base));
-
-  /* After inlining the code unification optimizations may invalidate
-     inline stacks.  Also we need to give up on global variables after
-     IPA, because addresses of these may have been propagated to their
-     constructors.  */
-  if (DECL_STRUCT_FUNCTION (function)->after_inlining)
-    return true;
-
-  /* Pure functions can not do any changes on the dynamic type;
-     that require writting to memory.  */
-  if (!auto_var_in_fn_p (base, function)
-      && flags_from_decl_or_type (function) & (ECF_PURE | ECF_CONST))
-    return false;
-
-  for (tree block = gimple_block (call); block && TREE_CODE (block) == BLOCK;
-       block = BLOCK_SUPERCONTEXT (block))
-    if (BLOCK_ABSTRACT_ORIGIN (block)
-	&& TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
-      {
-	tree fn = BLOCK_ABSTRACT_ORIGIN (block);
-
-	if (TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
-	    || (!DECL_CXX_CONSTRUCTOR_P (fn)
-		&& !DECL_CXX_DESTRUCTOR_P (fn)))
-	  {
-	    /* Watch for clones where we constant propagated the first
-	       argument (pointer to the instance).  */
-	    fn = DECL_ABSTRACT_ORIGIN (fn);
-	    if (!fn
-		|| !is_global_var (base)
-	        || TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
-		|| (!DECL_CXX_CONSTRUCTOR_P (fn)
-		    && !DECL_CXX_DESTRUCTOR_P (fn)))
-	      continue;
-	  }
-	if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
-	  continue;
-
-	/* FIXME: this can go away once we have ODR types equivalency on
-	   LTO level.  */
-	if (in_lto_p && !polymorphic_type_binfo_p (TYPE_BINFO (outer_type)))
-	  return true;
-	tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (fn)));
-	if (types_same_for_odr (type, outer_type))
-	  return true;
-      }
-
-  if (TREE_CODE (base) == VAR_DECL
-      && is_global_var (base))
-    {
-      if (TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
-	  || (!DECL_CXX_CONSTRUCTOR_P (function)
-	      && !DECL_CXX_DESTRUCTOR_P (function)))
-	{
-	  if (!DECL_ABSTRACT_ORIGIN (function))
-	    return false;
-	  /* Watch for clones where we constant propagated the first
-	     argument (pointer to the instance).  */
-	  function = DECL_ABSTRACT_ORIGIN (function);
-	  if (!function
-	      || TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
-	      || (!DECL_CXX_CONSTRUCTOR_P (function)
-		  && !DECL_CXX_DESTRUCTOR_P (function)))
-	    return false;
-	}
-      /* FIXME: this can go away once we have ODR types equivalency on
-	 LTO level.  */
-      if (in_lto_p && !polymorphic_type_binfo_p (TYPE_BINFO (outer_type)))
-	return true;
-      tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (function)));
-      if (types_same_for_odr (type, outer_type))
-	return true;
-    }
-  return false;
-}
-
-/* Dump human readable context to F.  */
-
-void
-ipa_polymorphic_call_context::dump (FILE *f) const
-{
-  fprintf (f, "    ");
-  if (invalid)
-    fprintf (f, "Call is known to be undefined\n");
-  else
-    {
-      if (!outer_type && !offset && !speculative_outer_type)
-	fprintf (f, "Empty context\n");
-      if (outer_type || offset)
-	{
-	  fprintf (f, "Outer type:");
-	  print_generic_expr (f, outer_type, TDF_SLIM);
-	  if (maybe_derived_type)
-	    fprintf (f, " (or a derived type)");
-	  if (maybe_in_construction)
-	    fprintf (f, " (maybe in construction)");
-	  fprintf (f, " offset "HOST_WIDE_INT_PRINT_DEC,
-		   offset);
-	}
-      if (speculative_outer_type)
-	{
-	  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)");
-	  fprintf (f, " at offset "HOST_WIDE_INT_PRINT_DEC,
-		   speculative_offset);
-	}
-    }
-  fprintf(f, "\n");
-}
-
-/* Print context to stderr.  */
-
-void
-ipa_polymorphic_call_context::debug () const
-{
-  dump (stderr);
-}
-
-/* Stream out the context to OB.  */
-
-void
-ipa_polymorphic_call_context::stream_out (struct output_block *ob) const
-{
-  struct bitpack_d bp = bitpack_create (ob->main_stream);
-
-  bp_pack_value (&bp, invalid, 1);
-  bp_pack_value (&bp, maybe_in_construction, 1);
-  bp_pack_value (&bp, maybe_derived_type, 1);
-  bp_pack_value (&bp, speculative_maybe_derived_type, 1);
-  bp_pack_value (&bp, outer_type != NULL, 1);
-  bp_pack_value (&bp, offset != 0, 1);
-  bp_pack_value (&bp, speculative_outer_type != NULL, 1);
-  streamer_write_bitpack (&bp);
-
-  if (outer_type != NULL)
-    stream_write_tree (ob, outer_type, true);
-  if (offset)
-    streamer_write_hwi (ob, offset);
-  if (speculative_outer_type != NULL)
-    {
-      stream_write_tree (ob, speculative_outer_type, true);
-      streamer_write_hwi (ob, speculative_offset);
-    }
-  else
-    gcc_assert (!speculative_offset);
-}
-
-/* Stream in the context from IB and DATA_IN.  */
-
-void
-ipa_polymorphic_call_context::stream_in (struct lto_input_block *ib,
-					 struct data_in *data_in)
-{
-  struct bitpack_d bp = streamer_read_bitpack (ib);
-
-  invalid = bp_unpack_value (&bp, 1);
-  maybe_in_construction = bp_unpack_value (&bp, 1);
-  maybe_derived_type = bp_unpack_value (&bp, 1);
-  speculative_maybe_derived_type = bp_unpack_value (&bp, 1);
-  bool outer_type_p = bp_unpack_value (&bp, 1);
-  bool offset_p = bp_unpack_value (&bp, 1);
-  bool speculative_outer_type_p = bp_unpack_value (&bp, 1);
-
-  if (outer_type_p)
-    outer_type = stream_read_tree (ib, data_in);
-  else
-    outer_type = NULL;
-  if (offset_p)
-    offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
-  else
-    offset = 0;
-  if (speculative_outer_type_p)
-    {
-      speculative_outer_type = stream_read_tree (ib, data_in);
-      speculative_offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
-    }
-  else
-    {
-      speculative_outer_type = NULL;
-      speculative_offset = 0;
-    }
-}
-
-/* Proudce polymorphic call context for call method of instance
-   that is located within BASE (that is assumed to be a decl) at offset OFF. */
-
-void
-ipa_polymorphic_call_context::set_by_decl (tree base, HOST_WIDE_INT off)
-{
-  gcc_assert (DECL_P (base));
-
-  outer_type = TYPE_MAIN_VARIANT (TREE_TYPE (base));
-  offset = off;
-  clear_speculation ();
-  /* Make very conservative assumption that all objects
-     may be in construction. 
- 
-     It is up to caller to revisit this via
-     get_dynamic_type or decl_maybe_in_construction_p.  */
-  maybe_in_construction = true;
-  maybe_derived_type = false;
-}
-
-/* CST is an invariant (address of decl), try to get meaningful
-   polymorphic call context for polymorphic call of method 
-   if instance of OTR_TYPE that is located at offset OFF of this invariant.
-   Return FALSE if nothing meaningful can be found.  */
-
-bool
-ipa_polymorphic_call_context::set_by_invariant (tree cst,
-						tree otr_type,
-						HOST_WIDE_INT off)
-{
-  HOST_WIDE_INT offset2, size, max_size;
-  tree base;
-
-  invalid = false;
-  off = 0;
-  clear_outer_type (otr_type);
-
-  if (TREE_CODE (cst) != ADDR_EXPR)
-    return false;
-
-  cst = TREE_OPERAND (cst, 0);
-  base = get_ref_base_and_extent (cst, &offset2, &size, &max_size);
-  if (!DECL_P (base) || max_size == -1 || max_size != size)
-    return false;
-
-  /* Only type inconsistent programs can have otr_type that is
-     not part of outer type.  */
-  if (otr_type && !contains_type_p (TREE_TYPE (base), off, otr_type))
-    return false;
-
-  set_by_decl (base, off);
-  return true;
-}
-
-/* See if OP is SSA name initialized as a copy or by single assignment.
-   If so, walk the SSA graph up.  */
-
-static tree
-walk_ssa_copies (tree op)
-{
-  STRIP_NOPS (op);
-  while (TREE_CODE (op) == SSA_NAME
-	 && !SSA_NAME_IS_DEFAULT_DEF (op)
-	 && SSA_NAME_DEF_STMT (op)
-	 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op)))
-    {
-      if (gimple_assign_load_p (SSA_NAME_DEF_STMT (op)))
-	return op;
-      op = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op));
-      STRIP_NOPS (op);
-    }
-  return op;
-}
-
-/* Create polymorphic call context from IP invariant CST.
-   This is typically &global_var.
-   OTR_TYPE specify type of polymorphic call or NULL if unknown, OFF
-   is offset of call.  */
-
-ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree cst,
-							    tree otr_type,
-							    HOST_WIDE_INT off)
-{
-  clear_speculation ();
-  set_by_invariant (cst, otr_type, off);
-}
-
-/* Build context for pointer REF contained in FNDECL at statement STMT.
-   if INSTANCE is non-NULL, return pointer to the object described by
-   the context or DECL where context is contained in.  */
-
-ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree fndecl,
-							    tree ref,
-							    gimple stmt,
-							    tree *instance)
-{
-  tree otr_type = NULL;
-  tree base_pointer;
-
-  if (TREE_CODE (ref) == OBJ_TYPE_REF)
-    {
-      otr_type = obj_type_ref_class (ref);
-      base_pointer = OBJ_TYPE_REF_OBJECT (ref);
-    }
-  else
-    base_pointer = ref;
-
-  /* Set up basic info in case we find nothing interesting in the analysis.  */
-  clear_speculation ();
-  clear_outer_type (otr_type);
-  invalid = false;
-
-  /* Walk SSA for outer object.  */
-  do 
-    {
-      base_pointer = walk_ssa_copies (base_pointer);
-      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);
-		  offset
-		    += offset2 + mem_ref_offset (base).to_short_addr () * BITS_PER_UNIT;
-		  outer_type = NULL;
-		}
-	      /* We found base object.  In this case the outer_type
-		 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
-		      && !contains_type_p (TREE_TYPE (base),
-					   offset + offset2, otr_type))
-		    {
-		      invalid = true;
-		      if (instance)
-			*instance = base_pointer;
-		      return;
-		    }
-		  set_by_decl (base, offset + offset2);
-		  if (maybe_in_construction && stmt)
-		    maybe_in_construction
-		     = decl_maybe_in_construction_p (base,
-						     outer_type,
-						     stmt,
-						     fndecl);
-		  if (instance)
-		    *instance = base;
-		  return;
-		}
-	      else
-		break;
-	    }
-	  else
-	    break;
-	}
-      else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR
-	       && tree_fits_uhwi_p (TREE_OPERAND (base_pointer, 1)))
-	{
-	  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))
-	{
-	  outer_type
-	     = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
-	  gcc_assert (TREE_CODE (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 (otr_type
-	      && !contains_type_p (outer_type, offset,
-				   otr_type))
-	    {
-	      outer_type = NULL;
-	      if (instance)
-		*instance = base_pointer;
-	      return;
-	    }
-
-	  /* If the function is constructor or destructor, then
-	     the type is possibly in construction, but we know
-	     it is not derived type.  */
-	  if (DECL_CXX_CONSTRUCTOR_P (fndecl)
-	      || DECL_CXX_DESTRUCTOR_P (fndecl))
-	    {
-	      maybe_in_construction = true;
-	      maybe_derived_type = false;
-	    }
-	  else
-	    {
-	      maybe_derived_type = true;
-	      maybe_in_construction = false;
-	    }
-	  if (instance)
-	    *instance = base_pointer;
-	  return;
-	}
-      /* 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)))
-	{
-	  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))
-	    { 
-	      invalid = true;
-	      if (instance)
-		*instance = base_pointer;
-	      return;
-	    }
-	  maybe_derived_type = false;
-	  maybe_in_construction = false;
-	  if (instance)
-	    *instance = base_pointer;
-	  return;
-	}
-    }
-
-  tree base_type = TREE_TYPE (base_pointer);
-
-  if (TREE_CODE (base_pointer) == SSA_NAME
-      && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
-      && TREE_CODE (SSA_NAME_VAR (base_pointer)) != PARM_DECL)
-    {
-      invalid = true;
-      if (instance)
-	*instance = base_pointer;
-      return;
-    }
-  if (TREE_CODE (base_pointer) == SSA_NAME
-      && SSA_NAME_DEF_STMT (base_pointer)
-      && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
-    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;
-    }
-  /* 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.  */
-  if (instance)
-    *instance = base_pointer;
-  return;
-}
-
-/* Structure to be passed in between detect_type_change and
-   check_stmt_for_type_change.  */
-
-struct type_change_info
-{
-  /* Offset into the object where there is the virtual method pointer we are
-     looking for.  */
-  HOST_WIDE_INT offset;
-  /* The declaration or SSA_NAME pointer of the base that we are checking for
-     type change.  */
-  tree instance;
-  /* The reference to virtual table pointer used.  */
-  tree vtbl_ptr_ref;
-  tree otr_type;
-  /* If we actually can tell the type that the object has changed to, it is
-     stored in this field.  Otherwise it remains NULL_TREE.  */
-  tree known_current_type;
-  HOST_WIDE_INT known_current_offset;
-
-  /* Set to true if dynamic type change has been detected.  */
-  bool type_maybe_changed;
-  /* Set to true if multiple types have been encountered.  known_current_type
-     must be disregarded in that case.  */
-  bool multiple_types_encountered;
-  /* Set to true if we possibly missed some dynamic type changes and we should
-     consider the set to be speculative.  */
-  bool speculative;
-  bool seen_unanalyzed_store;
-};
-
-/* Return true if STMT is not call and can modify a virtual method table pointer.
-   We take advantage of fact that vtable stores must appear within constructor
-   and destructor functions.  */
-
-static bool
-noncall_stmt_may_be_vtbl_ptr_store (gimple stmt)
-{
-  if (is_gimple_assign (stmt))
-    {
-      tree lhs = gimple_assign_lhs (stmt);
-
-      if (gimple_clobber_p (stmt))
-	return false;
-      if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
-	{
-	  if (flag_strict_aliasing
-	      && !POINTER_TYPE_P (TREE_TYPE (lhs)))
-	    return false;
-
-	  if (TREE_CODE (lhs) == COMPONENT_REF
-	      && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
-	    return false;
-	  /* In the future we might want to use get_base_ref_and_offset to find
-	     if there is a field corresponding to the offset and if so, proceed
-	     almost like if it was a component ref.  */
-	}
-    }
-
-  /* Code unification may mess with inline stacks.  */
-  if (cfun->after_inlining)
-    return true;
-
-  /* Walk the inline stack and watch out for ctors/dtors.
-     TODO: Maybe we can require the store to appear in toplevel
-     block of CTOR/DTOR.  */
-  for (tree block = gimple_block (stmt); block && TREE_CODE (block) == BLOCK;
-       block = BLOCK_SUPERCONTEXT (block))
-    if (BLOCK_ABSTRACT_ORIGIN (block)
-	&& TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
-      {
-	tree fn = BLOCK_ABSTRACT_ORIGIN (block);
-
-	if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
-	  return false;
-	return (TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
-		&& (DECL_CXX_CONSTRUCTOR_P (fn)
-		    || DECL_CXX_DESTRUCTOR_P (fn)));
-      }
-  return (TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
-	  && (DECL_CXX_CONSTRUCTOR_P (current_function_decl)
-	      || DECL_CXX_DESTRUCTOR_P (current_function_decl)));
-}
-
-/* If STMT can be proved to be an assignment to the virtual method table
-   pointer of ANALYZED_OBJ and the type associated with the new table
-   identified, return the type.  Otherwise return NULL_TREE.  */
-
-static tree
-extr_type_from_vtbl_ptr_store (gimple stmt, struct type_change_info *tci,
-			       HOST_WIDE_INT *type_offset)
-{
-  HOST_WIDE_INT offset, size, max_size;
-  tree lhs, rhs, base;
-
-  if (!gimple_assign_single_p (stmt))
-    return NULL_TREE;
-
-  lhs = gimple_assign_lhs (stmt);
-  rhs = gimple_assign_rhs1 (stmt);
-  if (TREE_CODE (lhs) != COMPONENT_REF
-      || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
-     {
-	if (dump_file)
-	  fprintf (dump_file, "  LHS is not virtual table.\n");
-	return NULL_TREE;
-     }
-
-  if (tci->vtbl_ptr_ref && operand_equal_p (lhs, tci->vtbl_ptr_ref, 0))
-    ;
-  else
-    {
-      base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
-      if (offset != tci->offset
-	  || size != POINTER_SIZE
-	  || max_size != POINTER_SIZE)
-	{
-	  if (dump_file)
-	    fprintf (dump_file, "    wrong offset %i!=%i or size %i\n",
-		     (int)offset, (int)tci->offset, (int)size);
-	  return NULL_TREE;
-	}
-      if (DECL_P (tci->instance))
-	{
-	  if (base != tci->instance)
-	    {
-	      if (dump_file)
-		{
-		  fprintf (dump_file, "    base:");
-		  print_generic_expr (dump_file, base, TDF_SLIM);
-		  fprintf (dump_file, " does not match instance:");
-		  print_generic_expr (dump_file, tci->instance, TDF_SLIM);
-		  fprintf (dump_file, "\n");
-		}
-	      return NULL_TREE;
-	    }
-	}
-      else if (TREE_CODE (base) == MEM_REF)
-	{
-	  if (!operand_equal_p (tci->instance, TREE_OPERAND (base, 0), 0)
-	      || !integer_zerop (TREE_OPERAND (base, 1)))
-	    {
-	      if (dump_file)
-		{
-		  fprintf (dump_file, "    base mem ref:");
-		  print_generic_expr (dump_file, base, TDF_SLIM);
-		  fprintf (dump_file, " has nonzero offset or does not match instance:");
-		  print_generic_expr (dump_file, tci->instance, TDF_SLIM);
-		  fprintf (dump_file, "\n");
-		}
-	      return NULL_TREE;
-	    }
-	}
-      else if (!operand_equal_p (tci->instance, base, 0)
-	       || tci->offset)
-	{
-	  if (dump_file)
-	    {
-	      fprintf (dump_file, "    base:");
-	      print_generic_expr (dump_file, base, TDF_SLIM);
-	      fprintf (dump_file, " does not match instance:");
-	      print_generic_expr (dump_file, tci->instance, TDF_SLIM);
-	      fprintf (dump_file, " with offset %i\n", (int)tci->offset);
-	    }
-	  return NULL_TREE;
-	}
-    }
-
-  tree vtable;
-  unsigned HOST_WIDE_INT offset2;
-
-  if (!vtable_pointer_value_to_vtable (rhs, &vtable, &offset2))
-    {
-      if (dump_file)
-	fprintf (dump_file, "    Failed to lookup binfo\n");
-      return NULL;
-    }
-
-  tree binfo = subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
-					       offset2, vtable);
-  if (!binfo)
-    {
-      if (dump_file)
-	fprintf (dump_file, "    Construction vtable used\n");
-      /* FIXME: We should suport construction contextes.  */
-      return NULL;
-    }
- 
-  *type_offset = tree_to_shwi (BINFO_OFFSET (binfo)) * BITS_PER_UNIT;
-  return DECL_CONTEXT (vtable);
-}
-
-/* Record dynamic type change of TCI to TYPE.  */
-
-void
-record_known_type (struct type_change_info *tci, tree type, HOST_WIDE_INT offset)
-{
-  if (dump_file)
-    {
-      if (type)
-	{
-          fprintf (dump_file, "  Recording type: ");
-	  print_generic_expr (dump_file, type, TDF_SLIM);
-          fprintf (dump_file, " at offset %i\n", (int)offset);
-	}
-     else
-       fprintf (dump_file, "  Recording unknown type\n");
-    }
-
-  /* If we found a constructor of type that is not polymorphic or
-     that may contain the type in question as a field (not as base),
-     restrict to the inner class first to make type matching bellow
-     happier.  */
-  if (type
-      && (offset
-          || (TREE_CODE (type) != RECORD_TYPE
-	      || !polymorphic_type_binfo_p (TYPE_BINFO (type)))))
-    {
-      ipa_polymorphic_call_context context;
-
-      context.offset = offset;
-      context.outer_type = type;
-      context.maybe_in_construction = false;
-      context.maybe_derived_type = false;
-      /* If we failed to find the inner type, we know that the call
-	 would be undefined for type produced here.  */
-      if (!context.restrict_to_inner_class (tci->otr_type))
-	{
-	  if (dump_file)
-	    fprintf (dump_file, "  Ignoring; does not contain otr_type\n");
-	  return;
-	}
-      /* Watch for case we reached an POD type and anticipate placement
-	 new.  */
-      if (!context.maybe_derived_type)
-	{
-          type = context.outer_type;
-          offset = context.offset;
-	}
-    }
-  if (tci->type_maybe_changed
-      && (!types_same_for_odr (type, tci->known_current_type)
-	  || offset != tci->known_current_offset))
-    tci->multiple_types_encountered = true;
-  tci->known_current_type = TYPE_MAIN_VARIANT (type);
-  tci->known_current_offset = offset;
-  tci->type_maybe_changed = true;
-}
-
-/* Callback of walk_aliased_vdefs and a helper function for
-   detect_type_change to check whether a particular statement may modify
-   the virtual table pointer, and if possible also determine the new type of
-   the (sub-)object.  It stores its result into DATA, which points to a
-   type_change_info structure.  */
-
-static bool
-check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
-{
-  gimple stmt = SSA_NAME_DEF_STMT (vdef);
-  struct type_change_info *tci = (struct type_change_info *) data;
-  tree fn;
-
-  /* If we already gave up, just terminate the rest of walk.  */
-  if (tci->multiple_types_encountered)
-    return true;
-
-  if (is_gimple_call (stmt))
-    {
-      if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
-	return false;
-
-      /* Check for a constructor call.  */
-      if ((fn = gimple_call_fndecl (stmt)) != NULL_TREE
-	  && DECL_CXX_CONSTRUCTOR_P (fn)
-	  && TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
-	  && gimple_call_num_args (stmt))
-      {
-	tree op = walk_ssa_copies (gimple_call_arg (stmt, 0));
-	tree type = method_class_type (TREE_TYPE (fn));
-	HOST_WIDE_INT offset = 0, size, max_size;
-
-	if (dump_file)
-	  {
-	    fprintf (dump_file, "  Checking constructor call: ");
-	    print_gimple_stmt (dump_file, stmt, 0, 0);
-	  }
-
-	/* See if THIS parameter seems like instance pointer.  */
-	if (TREE_CODE (op) == ADDR_EXPR)
-	  {
-	    op = get_ref_base_and_extent (TREE_OPERAND (op, 0),
-					  &offset, &size, &max_size);
-	    if (size != max_size || max_size == -1)
-	      {
-                tci->speculative = true;
-	        return false;
-	      }
-	    if (op && TREE_CODE (op) == MEM_REF)
-	      {
-		if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
-		  {
-                    tci->speculative = true;
-		    return false;
-		  }
-		offset += tree_to_shwi (TREE_OPERAND (op, 1))
-			  * BITS_PER_UNIT;
-		op = TREE_OPERAND (op, 0);
-	      }
-	    else if (DECL_P (op))
-	      ;
-	    else
-	      {
-                tci->speculative = true;
-	        return false;
-	      }
-	    op = walk_ssa_copies (op);
-	  }
-	if (operand_equal_p (op, tci->instance, 0)
-	    && TYPE_SIZE (type)
-	    && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST
-	    && tree_fits_shwi_p (TYPE_SIZE (type))
-	    && tree_to_shwi (TYPE_SIZE (type)) + offset > tci->offset)
-	  {
-	    record_known_type (tci, type, tci->offset - offset);
-	    return true;
-	  }
-      }
-     /* Calls may possibly change dynamic type by placement new. Assume
-        it will not happen, but make result speculative only.  */
-     if (dump_file)
-	{
-          fprintf (dump_file, "  Function call may change dynamic type:");
-	  print_gimple_stmt (dump_file, stmt, 0, 0);
-	}
-     tci->speculative = true;
-     return false;
-   }
-  /* Check for inlined virtual table store.  */
-  else if (noncall_stmt_may_be_vtbl_ptr_store (stmt))
-    {
-      tree type;
-      HOST_WIDE_INT offset = 0;
-      if (dump_file)
-	{
-	  fprintf (dump_file, "  Checking vtbl store: ");
-	  print_gimple_stmt (dump_file, stmt, 0, 0);
-	}
-
-      type = extr_type_from_vtbl_ptr_store (stmt, tci, &offset);
-      gcc_assert (!type || TYPE_MAIN_VARIANT (type) == type);
-      if (!type)
-	{
-	  if (dump_file)
-	    fprintf (dump_file, "  Unanalyzed store may change type.\n");
-	  tci->seen_unanalyzed_store = true;
-	  tci->speculative = true;
-	}
-      else
-        record_known_type (tci, type, offset);
-      return true;
-    }
-  else
-    return false;
-}
-
-/* THIS is polymorphic call context obtained from get_polymorphic_context.
-   OTR_OBJECT is pointer to the instance returned by OBJ_TYPE_REF_OBJECT.
-   INSTANCE is pointer to the outer instance as returned by
-   get_polymorphic_context.  To avoid creation of temporary expressions,
-   INSTANCE may also be an declaration of get_polymorphic_context found the
-   value to be in static storage.
-
-   If the type of instance is not fully determined
-   (either OUTER_TYPE is unknown or MAYBE_IN_CONSTRUCTION/INCLUDE_DERIVED_TYPES
-   is set), try to walk memory writes and find the actual construction of the
-   instance.
-
-   We do not include this analysis in the context analysis itself, because
-   it needs memory SSA to be fully built and the walk may be expensive.
-   So it is not suitable for use withing fold_stmt and similar uses.  */
-
-bool
-ipa_polymorphic_call_context::get_dynamic_type (tree instance,
-						tree otr_object,
-						tree otr_type,
-						gimple call)
-{
-  struct type_change_info tci;
-  ao_ref ao;
-  bool function_entry_reached = false;
-  tree instance_ref = NULL;
-  gimple stmt = call;
-  /* Remember OFFSET before it is modified by restrict_to_inner_class.
-     This is because we do not update INSTANCE when walking inwards.  */
-  HOST_WIDE_INT instance_offset = offset;
-
-  otr_type = TYPE_MAIN_VARIANT (otr_type);
-
-  /* Walk into inner type. This may clear maybe_derived_type and save us
-     from useless work.  It also makes later comparsions with static type
-     easier.  */
-  if (outer_type)
-    {
-      if (!restrict_to_inner_class (otr_type))
-        return false;
-    }
-
-  if (!maybe_in_construction && !maybe_derived_type)
-    return false;
-
-  /* We need to obtain refernce to virtual table pointer.  It is better
-     to look it up in the code rather than build our own.  This require bit
-     of pattern matching, but we end up verifying that what we found is
-     correct. 
-
-     What we pattern match is:
-
-       tmp = instance->_vptr.A;   // vtbl ptr load
-       tmp2 = tmp[otr_token];	  // vtable lookup
-       OBJ_TYPE_REF(tmp2;instance->0) (instance);
- 
-     We want to start alias oracle walk from vtbl pointer load,
-     but we may not be able to identify it, for example, when PRE moved the
-     load around.  */
-
-  if (gimple_code (call) == GIMPLE_CALL)
-    {
-      tree ref = gimple_call_fn (call);
-      HOST_WIDE_INT offset2, size, max_size;
-
-      if (TREE_CODE (ref) == OBJ_TYPE_REF)
-	{
-	  ref = OBJ_TYPE_REF_EXPR (ref);
-	  ref = walk_ssa_copies (ref);
-
-	  /* Check if definition looks like vtable lookup.  */
-	  if (TREE_CODE (ref) == SSA_NAME
-	      && !SSA_NAME_IS_DEFAULT_DEF (ref)
-	      && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref))
-	      && TREE_CODE (gimple_assign_rhs1
-			     (SSA_NAME_DEF_STMT (ref))) == MEM_REF)
-	    {
-	      ref = get_base_address
-		     (TREE_OPERAND (gimple_assign_rhs1
-				     (SSA_NAME_DEF_STMT (ref)), 0));
-	      ref = walk_ssa_copies (ref);
-	      /* Find base address of the lookup and see if it looks like
-		 vptr load.  */
-	      if (TREE_CODE (ref) == SSA_NAME
-		  && !SSA_NAME_IS_DEFAULT_DEF (ref)
-		  && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref)))
-		{
-		  tree ref_exp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ref));
-		  tree base_ref = get_ref_base_and_extent
-				   (ref_exp, &offset2, &size, &max_size);
-
-		  /* Finally verify that what we found looks like read from OTR_OBJECT
-		     or from INSTANCE with offset OFFSET.  */
-		  if (base_ref
-		      && ((TREE_CODE (base_ref) == MEM_REF
-		           && ((offset2 == instance_offset
-		                && TREE_OPERAND (base_ref, 0) == instance)
-			       || (!offset2 && TREE_OPERAND (base_ref, 0) == otr_object)))
-			  || (DECL_P (instance) && base_ref == instance
-			      && offset2 == instance_offset)))
-		    {
-		      stmt = SSA_NAME_DEF_STMT (ref);
-		      instance_ref = ref_exp;
-		    }
-		}
-	    }
-	}
-    }
- 
-  /* If we failed to look up the refernece in code, build our own.  */
-  if (!instance_ref)
-    {
-      /* If the statement in question does not use memory, we can't tell
-	 anything.  */
-      if (!gimple_vuse (stmt))
-	return false;
-      ao_ref_init_from_ptr_and_size (&ao, otr_object, NULL);
-    }
-  else
-  /* Otherwise use the real reference.  */
-    ao_ref_init (&ao, instance_ref);
-
-  /* We look for vtbl pointer read.  */
-  ao.size = POINTER_SIZE;
-  ao.max_size = ao.size;
-  ao.ref_alias_set
-    = get_deref_alias_set (TREE_TYPE (BINFO_VTABLE (TYPE_BINFO (otr_type))));
-
-  if (dump_file)
-    {
-      fprintf (dump_file, "Determining dynamic type for call: ");
-      print_gimple_stmt (dump_file, call, 0, 0);
-      fprintf (dump_file, "  Starting walk at: ");
-      print_gimple_stmt (dump_file, stmt, 0, 0);
-      fprintf (dump_file, "  instance pointer: ");
-      print_generic_expr (dump_file, otr_object, TDF_SLIM);
-      fprintf (dump_file, "  Outer instance pointer: ");
-      print_generic_expr (dump_file, instance, TDF_SLIM);
-      fprintf (dump_file, " offset: %i (bits)", (int)offset);
-      fprintf (dump_file, " vtbl reference: ");
-      print_generic_expr (dump_file, instance_ref, TDF_SLIM);
-      fprintf (dump_file, "\n");
-    }
-
-  tci.offset = offset;
-  tci.instance = instance;
-  tci.vtbl_ptr_ref = instance_ref;
-  gcc_assert (TREE_CODE (instance) != MEM_REF);
-  tci.known_current_type = NULL_TREE;
-  tci.known_current_offset = 0;
-  tci.otr_type = otr_type;
-  tci.type_maybe_changed = false;
-  tci.multiple_types_encountered = false;
-  tci.speculative = false;
-  tci.seen_unanalyzed_store = false;
-
-  walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
-		      &tci, NULL, &function_entry_reached);
-
-  /* If we did not find any type changing statements, we may still drop
-     maybe_in_construction flag if the context already have outer type. 
-
-     Here we make special assumptions about both constructors and
-     destructors which are all the functions that are allowed to alter the
-     VMT pointers.  It assumes that destructors begin with assignment into
-     all VMT pointers and that constructors essentially look in the
-     following way:
-
-     1) The very first thing they do is that they call constructors of
-     ancestor sub-objects that have them.
-
-     2) Then VMT pointers of this and all its ancestors is set to new
-     values corresponding to the type corresponding to the constructor.
-
-     3) Only afterwards, other stuff such as constructor of member
-     sub-objects and the code written by the user is run.  Only this may
-     include calling virtual functions, directly or indirectly.
-
-     4) placement new can not be used to change type of non-POD statically
-     allocated variables.
-
-     There is no way to call a constructor of an ancestor sub-object in any
-     other way.
-
-     This means that we do not have to care whether constructors get the
-     correct type information because they will always change it (in fact,
-     if we define the type to be given by the VMT pointer, it is undefined).
-
-     The most important fact to derive from the above is that if, for some
-     statement in the section 3, we try to detect whether the dynamic type
-     has changed, we can safely ignore all calls as we examine the function
-     body backwards until we reach statements in section 2 because these
-     calls cannot be ancestor constructors or destructors (if the input is
-     not bogus) and so do not change the dynamic type (this holds true only
-     for automatically allocated objects but at the moment we devirtualize
-     only these).  We then must detect that statements in section 2 change
-     the dynamic type and can try to derive the new type.  That is enough
-     and we can stop, we will never see the calls into constructors of
-     sub-objects in this code. 
-
-     Therefore if the static outer type was found (outer_type)
-     we can safely ignore tci.speculative that is set on calls and give up
-     only if there was dyanmic type store that may affect given variable
-     (seen_unanalyzed_store)  */
-
-  if (!tci.type_maybe_changed
-      || (outer_type
-	  && !tci.seen_unanalyzed_store
-	  && !tci.multiple_types_encountered
-	  && offset == tci.offset
-	  && types_same_for_odr (tci.known_current_type,
-				 outer_type)))
-    {
-      if (!outer_type || tci.seen_unanalyzed_store)
-	return false;
-      if (maybe_in_construction)
-        maybe_in_construction = false;
-      if (dump_file)
-	fprintf (dump_file, "  No dynamic type change found.\n");
-      return true;
-    }
-
-  if (tci.known_current_type
-      && !function_entry_reached
-      && !tci.multiple_types_encountered)
-    {
-      if (!tci.speculative)
-	{
-	  outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
-	  offset = tci.known_current_offset;
-	  maybe_in_construction = false;
-	  maybe_derived_type = false;
-	  if (dump_file)
-	    fprintf (dump_file, "  Determined dynamic type.\n");
-	}
-      else if (!speculative_outer_type
-	       || speculative_maybe_derived_type)
-	{
-	  speculative_outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
-	  speculative_offset = tci.known_current_offset;
-	  speculative_maybe_derived_type = false;
-	  if (dump_file)
-	    fprintf (dump_file, "  Determined speculative dynamic type.\n");
-	}
-    }
-  else if (dump_file)
-    {
-      fprintf (dump_file, "  Found multiple types%s%s\n",
-	       function_entry_reached ? " (function entry reached)" : "",
-	       function_entry_reached ? " (multiple types encountered)" : "");
-    }
-
-  return true;
-}
-
 /* 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.
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 215614)
+++ Makefile.in	(working copy)
@@ -1255,6 +1255,7 @@ OBJS = \
 	internal-fn.o \
 	ipa-cp.o \
 	ipa-devirt.o \
+	ipa-polymorphic-call.o \
 	ipa-split.o \
 	ipa-inline.o \
 	ipa-comdats.o \



More information about the Gcc-patches mailing list