PR ipa/59831 (ipa-cp devirt issues)
Jan Hubicka
hubicka@ucw.cz
Fri Jan 31 08:32:00 GMT 2014
Hi,
PR ipa/59831 has testcase with one virtual call that shows really interesting
sequence of events. First we speculatively identify the target of call. Next
ipa-cp correctly works out the target and decides to clone. While creating a
clone it however no longer identifies the direct edge. It is because in
meantime it worked out the exact value of the pointer (&globalvar) and thrown
away the binfo information we used previously. ipa-cp tries to look up the
binfo again, but it uses gimple_extract_devirt_binfo_from_cst that is not as
good at doing the same work as ipa-devirt is. For bogus reason (empty base
class) it gives up. Consequently we create the clone and propagate value, then
we hit recursive inlining and it tries to save the function body. While doing
so, it calls fold on the (now substituted) function body and it works out the
virtual call target. This leads to ICE since it tries to resolve the call and
remove the speculation before the body is fully copied.
This patch sanitizes behaviour of ipa-cp. I decided to remove
gimple_extract_devirt_binfo_from_cst since ipa-devirt already has all logic in
it, it was just not available to ipa-cp (it was on my TODO for a while).
To however prevent consistently the deivrutalization, we I added code to use
aggregate value info. It is quite easy to do: when we know the virtual table
pointer, we can lookup the BINFO same was as extr_type_from_vtbl_ptr_store
already does - by checking DECL_CONTEXT of the vtable. I borrowed the logic and
hardened it a bit by extra sanity checking in vtable_pointer_value_to_binfo.
Since I asked about it, I discovered bug in that logic: in the case of multiple
inheritance, we may end up having one vtable nested in another and vtable
initialization like &vtable+120, instead of default 16. In this case we
definitely can not conclude that the dynamic type is the object is the CONTEXT
of vtable, since the it is the dynamic type of the object with some non-zero
offset.
I added code to vtable_pointer_value_to_binfo to lookup the proper binfo of
base with vtable at given offset, but sadly I can't hook it easily to
extr_type_from_vtbl_ptr_store, so I made it to give up in that case for now.
Bootstrapped/regtested x86_64-linux, tested on firefox LTO where it adds
10 new devirtualizations (out of 1200). Will commit it tomorrow if there are
no complains. There is one devirtualization fewer on javascript that is
due to extra checking I added to the instance type lookup.
Honza
PR ipa/59831
* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): Remove.
* ipa-devirt.c (get_poymorphic_call_info_for_decl): Break out from ...
(get_polymorphic_call_info): ... here.
(get_polymorphic_call_info_from_invariant): New function based on
gimple_extract_devirt_binfo_from_cst.
(try_make_edge_direct_virtual_call): Update to use ipa-devirt.
(ipa_get_indirect_edge_target_1): Likewise.
(get_polymorphic_call_info_from_invariant): New function.
(vtable_pointer_value_to_binfo): New function.
* ipa-utils.h (get_polymorphic_call_info_from_invariant): Declare.
(vtable_pointer_value_to_binfo): Declare.
* ipa-prop.c (extr_type_from_vtbl_ptr_store): Use it.
(try_make_edge_direct_virtual_call): Use aggregate propagation;
rewrite handling of constants.
* ipa-cp.c (ipa_get_indirect_edge_target_1): Likewise.
* testsuite/g++.dg/ipa/devirt-21.C: New testcase.
* testsuite/g++.dg/ipa/devirt-20.C: Fix template.
Index: gimple-fold.c
===================================================================
--- gimple-fold.c (revision 207287)
+++ gimple-fold.c (working copy)
@@ -1071,74 +1071,6 @@ gimple_fold_builtin (gimple stmt)
}
-/* Return a binfo to be used for devirtualization of calls based on an object
- represented by a declaration (i.e. a global or automatically allocated one)
- or NULL if it cannot be found or is not safe. CST is expected to be an
- ADDR_EXPR of such object or the function will return NULL. Currently it is
- safe to use such binfo only if it has no base binfo (i.e. no ancestors)
- EXPECTED_TYPE is type of the class virtual belongs to. */
-
-tree
-gimple_extract_devirt_binfo_from_cst (tree cst, tree expected_type)
-{
- HOST_WIDE_INT offset, size, max_size;
- tree base, type, binfo;
- bool last_artificial = false;
-
- if (!flag_devirtualize
- || TREE_CODE (cst) != ADDR_EXPR
- || TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) != RECORD_TYPE)
- return NULL_TREE;
-
- cst = TREE_OPERAND (cst, 0);
- base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
- type = TREE_TYPE (base);
- if (!DECL_P (base)
- || max_size == -1
- || max_size != size
- || TREE_CODE (type) != RECORD_TYPE)
- return NULL_TREE;
-
- /* Find the sub-object the constant actually refers to and mark whether it is
- an artificial one (as opposed to a user-defined one). */
- while (true)
- {
- HOST_WIDE_INT pos, size;
- tree fld;
-
- if (types_same_for_odr (type, expected_type))
- break;
- if (offset < 0)
- return NULL_TREE;
-
- for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
- {
- if (TREE_CODE (fld) != FIELD_DECL)
- continue;
-
- pos = int_bit_position (fld);
- size = tree_to_uhwi (DECL_SIZE (fld));
- if (pos <= offset && (pos + size) > offset)
- break;
- }
- if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
- return NULL_TREE;
-
- last_artificial = DECL_ARTIFICIAL (fld);
- type = TREE_TYPE (fld);
- offset -= pos;
- }
- /* Artificial sub-objects are ancestors, we do not want to use them for
- devirtualization, at least not here. */
- if (last_artificial)
- return NULL_TREE;
- binfo = TYPE_BINFO (type);
- if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
- return NULL_TREE;
- else
- return binfo;
-}
-
/* Attempt to fold a call statement referenced by the statement iterator GSI.
The statement may be replaced by another statement, e.g., if the call
simplifies to a constant value. Return true if any changes were made.
Index: gimple-fold.h
===================================================================
--- gimple-fold.h (revision 207287)
+++ gimple-fold.h (working copy)
@@ -26,7 +26,6 @@ extern tree canonicalize_constructor_val
extern tree get_symbol_constant_value (tree);
extern void gimplify_and_update_call_from_tree (gimple_stmt_iterator *, tree);
extern tree gimple_fold_builtin (gimple);
-extern tree gimple_extract_devirt_binfo_from_cst (tree, tree);
extern bool fold_stmt (gimple_stmt_iterator *);
extern bool fold_stmt_inplace (gimple_stmt_iterator *);
extern tree maybe_fold_and_comparisons (enum tree_code, tree, tree,
Index: ipa-utils.h
===================================================================
--- ipa-utils.h (revision 207287)
+++ ipa-utils.h (working copy)
@@ -87,6 +87,9 @@ tree method_class_type (tree);
tree get_polymorphic_call_info (tree, tree, tree *,
HOST_WIDE_INT *,
ipa_polymorphic_call_context *);
+bool get_polymorphic_call_info_from_invariant (ipa_polymorphic_call_context *,
+ tree, tree, HOST_WIDE_INT);
+tree vtable_pointer_value_to_binfo (tree t);
/* Return vector containing possible targets of polymorphic call E.
If FINALP is non-NULL, store true if the list is complette.
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c (revision 207287)
+++ ipa-devirt.c (working copy)
@@ -972,6 +972,120 @@ contains_type_p (tree outer_type, HOST_W
return get_class_context (&context, otr_type);
}
+/* Proudce polymorphic call context for call method of instance
+ that is located within BASE (that is assumed to be a decl) at OFFSET. */
+
+static void
+get_poymorphic_call_info_for_decl (ipa_polymorphic_call_context *context,
+ tree base, HOST_WIDE_INT offset)
+{
+ gcc_assert (DECL_P (base));
+
+ context->outer_type = TREE_TYPE (base);
+ context->offset = offset;
+ /* Make very conservative assumption that all objects
+ may be in construction.
+ TODO: ipa-prop already contains code to tell better.
+ merge it later. */
+ context->maybe_in_construction = true;
+ context->maybe_derived_type = false;
+}
+
+/* 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 of this invariant.
+ Return FALSE if nothing meaningful can be found. */
+
+bool
+get_polymorphic_call_info_from_invariant (ipa_polymorphic_call_context *context,
+ tree cst,
+ tree otr_type,
+ HOST_WIDE_INT offset)
+{
+ HOST_WIDE_INT offset2, size, max_size;
+ tree base;
+
+ if (TREE_CODE (cst) != ADDR_EXPR)
+ return NULL_TREE;
+
+ 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 NULL_TREE;
+
+ /* Only type inconsistent programs can have otr_type that is
+ not part of outer type. */
+ if (!contains_type_p (TREE_TYPE (base),
+ offset, otr_type))
+ return NULL_TREE;
+
+ get_poymorphic_call_info_for_decl (context,
+ base, offset);
+ return true;
+}
+
+/* Lookup base of BINFO that has virtual table VTABLE with OFFSET. */
+
+static tree
+subbinfo_with_vtable_at_offset (tree binfo, tree offset, tree vtable)
+{
+ tree v = BINFO_VTABLE (binfo);
+ int i;
+ tree base_binfo;
+
+ gcc_assert (!v || TREE_CODE (v) == POINTER_PLUS_EXPR);
+
+ if (v && tree_int_cst_equal (TREE_OPERAND (v, 1), offset)
+ && TREE_OPERAND (TREE_OPERAND (v, 0), 0) == vtable)
+ return binfo;
+ for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
+ if (polymorphic_type_binfo_p (base_binfo))
+ {
+ base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
+ if (base_binfo)
+ return base_binfo;
+ }
+ return NULL;
+}
+
+/* T is known constant value of virtual table pointer. Return BINFO of the
+ instance type. */
+
+tree
+vtable_pointer_value_to_binfo (tree t)
+{
+ /* We expect &MEM[(void *)&virtual_table + 16B].
+ We obtain object's BINFO from the context of the virtual table.
+ This one contains pointer to virtual table represented via
+ POINTER_PLUS_EXPR. Verify that this pointer match to what
+ we propagated through.
+
+ In the case of virtual inheritance, the virtual tables may
+ be nested, i.e. the offset may be different from 16 and we may
+ need to dive into the type representation. */
+ if (t && TREE_CODE (t) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
+ && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
+ == VAR_DECL)
+ && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
+ (TREE_OPERAND (t, 0), 0), 0)))
+ {
+ tree vtable = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
+ tree offset = TREE_OPERAND (TREE_OPERAND (t, 0), 1);
+ tree binfo = TYPE_BINFO (DECL_CONTEXT (vtable));
+
+ binfo = subbinfo_with_vtable_at_offset (binfo, offset, vtable);
+ gcc_assert (binfo);
+ return binfo;
+ }
+ return NULL;
+}
+
+
/* Given REF call in FNDECL, determine class of the polymorphic
call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT.
Return pointer to object described by the context */
@@ -1030,21 +1144,13 @@ get_polymorphic_call_info (tree fndecl,
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 (!contains_type_p (TREE_TYPE (base),
context->offset + offset2, *otr_type))
return base_pointer;
- context->outer_type = TREE_TYPE (base);
- context->offset += offset2;
- /* Make very conservative assumption that all objects
- may be in construction.
- TODO: ipa-prop already contains code to tell better.
- merge it later. */
- context->maybe_in_construction = true;
- context->maybe_derived_type = false;
+ get_poymorphic_call_info_for_decl (context, base,
+ context->offset + offset2);
return NULL;
}
else
Index: ipa-prop.c
===================================================================
--- ipa-prop.c (revision 207287)
+++ ipa-prop.c (working copy)
@@ -592,6 +592,7 @@ extr_type_from_vtbl_ptr_store (gimple st
{
HOST_WIDE_INT offset, size, max_size;
tree lhs, rhs, base;
+ tree binfo;
if (!gimple_assign_single_p (stmt))
return NULL_TREE;
@@ -602,10 +603,12 @@ extr_type_from_vtbl_ptr_store (gimple st
|| !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
|| TREE_CODE (rhs) != ADDR_EXPR)
return NULL_TREE;
- rhs = get_base_address (TREE_OPERAND (rhs, 0));
- if (!rhs
- || TREE_CODE (rhs) != VAR_DECL
- || !DECL_VIRTUAL_P (rhs))
+ binfo = vtable_pointer_value_to_binfo (rhs);
+
+ /* FIXME: We may end up looking up an binfo that is not
+ a base type, since the instance is part of a bigger one.
+ We should handle this in future by working out proper offset. */
+ if (!binfo || TYPE_BINFO (BINFO_TYPE (binfo)) != binfo)
return NULL_TREE;
base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
@@ -624,7 +627,7 @@ extr_type_from_vtbl_ptr_store (gimple st
else if (tci->object != base)
return NULL_TREE;
- return DECL_CONTEXT (rhs);
+ return BINFO_TYPE (binfo);
}
/* Callback of walk_aliased_vdefs and a helper function for
@@ -2670,28 +2673,58 @@ try_make_edge_direct_virtual_call (struc
struct ipa_jump_func *jfunc,
struct ipa_node_params *new_root_info)
{
- tree binfo, target;
+ tree binfo = NULL, target;
+
+ if (!flag_devirtualize)
+ return NULL;
- binfo = ipa_value_from_jfunc (new_root_info, jfunc);
+ /* First try to work out binfo from the knowledge of virtual
+ table pointer. This is always safe. */
+ if (!ie->indirect_info->by_ref)
+ {
+ tree t = ipa_find_agg_cst_for_param (&jfunc->agg,
+ ie->indirect_info->offset,
+ true);
+ binfo = vtable_pointer_value_to_binfo (t);
+ }
+ /* See if we propagated value or binfo. */
+ if (!binfo)
+ binfo = ipa_value_from_jfunc (new_root_info, jfunc);
if (!binfo)
return NULL;
if (TREE_CODE (binfo) != TREE_BINFO)
{
- binfo = gimple_extract_devirt_binfo_from_cst
- (binfo, ie->indirect_info->otr_type);
- if (!binfo)
- return NULL;
+ ipa_polymorphic_call_context context;
+ vec <cgraph_node *>targets;
+ bool final;
+
+ if (!get_polymorphic_call_info_from_invariant
+ (&context, binfo, ie->indirect_info->otr_type,
+ ie->indirect_info->offset))
+ return NULL;
+ targets = possible_polymorphic_call_targets
+ (ie->indirect_info->otr_type,
+ ie->indirect_info->otr_token,
+ context, &final);
+ if (!final || targets.length () > 1)
+ return NULL;
+ if (targets.length () == 1)
+ target = targets[0]->decl;
+ else
+ target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
}
-
- binfo = get_binfo_at_offset (binfo, ie->indirect_info->offset,
- ie->indirect_info->otr_type);
- if (binfo)
- target = gimple_get_virt_method_for_binfo (ie->indirect_info->otr_token,
- binfo);
else
- return NULL;
+ {
+ binfo = get_binfo_at_offset (binfo, ie->indirect_info->offset,
+ ie->indirect_info->otr_type);
+ if (binfo)
+ target = gimple_get_virt_method_for_binfo (ie->indirect_info->otr_token,
+ binfo);
+ else
+ return NULL;
+ }
if (target)
{
Index: ipa-cp.c
===================================================================
--- ipa-cp.c (revision 207287)
+++ ipa-cp.c (working copy)
@@ -117,6 +117,7 @@ along with GCC; see the file COPYING3.
#include "params.h"
#include "ipa-inline.h"
#include "ipa-utils.h"
+#include "print-tree.h"
struct ipcp_value;
@@ -1479,9 +1480,9 @@ ipa_get_indirect_edge_target_1 (struct c
HOST_WIDE_INT token, anc_offset;
tree otr_type;
tree t;
- tree target;
+ tree target = NULL;
- if (param_index == -1
+ if (!flag_devirtualize || param_index == -1
|| known_vals.length () <= (unsigned int) param_index)
return NULL_TREE;
@@ -1532,25 +1533,76 @@ ipa_get_indirect_edge_target_1 (struct c
anc_offset = ie->indirect_info->offset;
otr_type = ie->indirect_info->otr_type;
- t = known_vals[param_index];
+ t = NULL;
+
+ /* Do we know BINFO? */
if (!t && known_binfos.length () > (unsigned int) param_index)
t = known_binfos[param_index];
- if (!t)
- return NULL_TREE;
+ /* FIXME: ipcp_discover_new_direct_edges makes no difference between
+ constants and binfos. This is because ipa-cp currently assumes that known
+ value is always better than binfo. Hopefully this will be fixed when
+ ipa-cp is turned to propagate polymorphic call contextes. */
+ if (known_vals[param_index] && TREE_CODE (known_vals[param_index]) == TREE_BINFO)
+ t = known_vals[param_index];
- if (TREE_CODE (t) != TREE_BINFO)
+ /* Try to work out BINFO from virtual table pointer value in replacements. */
+ if (!t && agg_reps && !ie->indirect_info->by_ref)
{
- tree binfo;
- binfo = gimple_extract_devirt_binfo_from_cst
- (t, ie->indirect_info->otr_type);
- if (!binfo)
+ while (agg_reps)
+ {
+ if (agg_reps->index == param_index
+ && agg_reps->offset == ie->indirect_info->offset
+ && agg_reps->by_ref)
+ {
+ debug_tree (t);
+ t = agg_reps->value;
+ t = vtable_pointer_value_to_binfo (t);
+ break;
+ }
+ agg_reps = agg_reps->next;
+ }
+ }
+
+ /* Try to work out BINFO from virtual table pointer value in known
+ known aggregate values. */
+ if (!t && known_aggs.length () > (unsigned int) param_index
+ && !ie->indirect_info->by_ref)
+ {
+ struct ipa_agg_jump_function *agg;
+ agg = known_aggs[param_index];
+ t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset,
+ true);
+ if (t)
+ t = vtable_pointer_value_to_binfo (t);
+ }
+
+ /* Try to work out value of the pointer. This comes last since not all
+ values leads to devirtualization. */
+ if (!t)
+ {
+ ipa_polymorphic_call_context context;
+ vec <cgraph_node *>targets;
+ bool final;
+
+ t = known_vals[param_index];
+ if (!t)
+ return NULL_TREE;
+
+ if (!get_polymorphic_call_info_from_invariant
+ (&context, t, ie->indirect_info->otr_type,
+ anc_offset))
return NULL_TREE;
- binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
- if (!binfo)
+ targets = possible_polymorphic_call_targets
+ (ie->indirect_info->otr_type,
+ ie->indirect_info->otr_token,
+ context, &final);
+ if (!final || targets.length () > 1)
return NULL_TREE;
- target = gimple_get_virt_method_for_binfo (token, binfo);
+ if (targets.length () == 1)
+ return targets[0]->decl;
+ return builtin_decl_implicit (BUILT_IN_UNREACHABLE);
}
- else
+ if (t)
{
tree binfo;
More information about the Gcc-patches
mailing list