From 8d326f11c5c81d58bd54d155a13a4eba96b75df1 Mon Sep 17 00:00:00 2001 From: hubicka Date: Thu, 25 Sep 2014 19:52:20 +0000 Subject: [PATCH] * 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 git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@215615 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 44 ++ gcc/Makefile.in | 1 + gcc/ipa-devirt.c | 1508 +------------------------------------------ gcc/ipa-polymorphic-call.c | 1518 ++++++++++++++++++++++++++++++++++++++++++++ gcc/ipa-utils.h | 20 + 5 files changed, 1599 insertions(+), 1492 deletions(-) create mode 100644 gcc/ipa-polymorphic-call.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cfc1120..85dd750 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,49 @@ 2014-09-25 Jan Hubicka + * 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 + +2014-09-25 Jan Hubicka + * ipa-devirt.c (polymorphic_call_target_d): Add SPECULATIVE; reorder for better storage. (polymorphic_call_target_hasher::hash): Hash SPECULATIVE. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 97b439a..3dd9d8f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -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 \ diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c index 357a506..cbc9dd5 100644 --- a/gcc/ipa-devirt.c +++ b/gcc/ipa-devirt.c @@ -135,9 +135,6 @@ along with GCC; see the file COPYING3. If not see #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, const_tree type2) 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_node *n, void *d ATTRIBUTE_UNUSED) 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_tree t) 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. diff --git a/gcc/ipa-polymorphic-call.c b/gcc/ipa-polymorphic-call.c new file mode 100644 index 0000000..23f14ac60 --- /dev/null +++ b/gcc/ipa-polymorphic-call.c @@ -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 +. */ + +#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; +} + diff --git a/gcc/ipa-utils.h b/gcc/ipa-utils.h index 494397b..029f39a 100644 --- a/gcc/ipa-utils.h +++ b/gcc/ipa-utils.h @@ -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 */ -- 2.7.4