Hi,
this patch implements basic support for speculation within polymorphic call
contextes. As we are still having heated discussion how much types in memory
can change, this allows us to deal with these cases speculatively - that is,
anticipate that placement news are not present.
This patch also makes get_polymorphic_call_info to derive speculative guess
from the last pointer type it walks into (that is usually load or parameter).
So for example we now speculatively devirtualize:
struct A {virtual int t(){return 42;}};
struct B:A {virtual int t(){return 1;}};
int
t(struct B *b)
{
struct A *a=b;
a->t();
}
Originally we considered both A::t and B::t as equally likely targets. Now we
conclud that since user typed the parameter struct B *, he is likely holding
pointer to instance of B or its derived type and since B has no visible
derivations, we speculate that destination is B::t.
There are similar testcases in bugzilla where we do not devirtualize because we
lost track of type promises C++ language makes on memory accesses. This may
give us a clue how common these are.
The basic idea is to sort of double outer type information within polymorphic
call type. Now we have outer_type/offset and
speculative_outer_type/speculative_offset. The second is supposed to be
strictly
more restrictive than the first (that is the best known information).
For this reason I did not implement it as two independent contextes - the
handling
is bit interwinded (in get_class_context) where we need to validate speculative
context using the non-speculative context knowledge.
I hope the ugly reshuffling of data into cgraph edges will go away soon with
ipa-prop reorg.
Bootstrapped/regtested x86_64-linux, I will cleanup naming and dumping
incrementally
and add testcases.
Honza
* cgraph.c (cgraph_node::create_indirect_edge): Copy speculative data.
* cgraph.h (cgraph_indirect_call_info): Add speculative data.
* gimple-fold.c (fold_gimple_assign): Fix check for virtual
call.
* ipa-devirt.c (ipa_dummy_polymorphic_call_context): Update
(contains_type_p): Forward declare.
(polymorphic_call_target_hasher::hash): Hash speculative info.
(polymorphic_call_target_hasher::equal): Compare speculative info.
(get_class_context): Handle speuclation.
(contains_type_p): Update.
(get_polymorphic_call_info_for_decl): Update.
(walk_ssa_copies): Break out from ...
(get_polymorphic_call_info): ... here; set speculative context
before giving up.
* ipa-prop.c (ipa_write_indirect_edge_info,
ipa_read_indirect_edge_info):
Stream speculative context.
* ipa-utils.h (ipa_polymorphic_call_context): Add speculative info
(SPECULATIVE_OFFSET, SPECULATIVE_OUTER_TYPE,
SPECULATIVE_MAYBE_DERIVED_TYPE).
(possible_polymorphic_call_targets overriders): Update.
(dump_possible_polymorphic_call_targets overriders): Update.
(dump_possible_polymorphic_call_target_p overriders): Update.
Index: cgraph.c
===================================================================
--- cgraph.c (revision 213123)
+++ cgraph.c (working copy)
@@ -973,10 +973,15 @@
edge->indirect_info->otr_token = otr_token;
edge->indirect_info->otr_type = otr_type;
edge->indirect_info->outer_type = context.outer_type;
+ edge->indirect_info->speculative_outer_type
+ = context.speculative_outer_type;
edge->indirect_info->offset = context.offset;
+ edge->indirect_info->speculative_offset = context.speculative_offset;
edge->indirect_info->maybe_in_construction
= context.maybe_in_construction;
edge->indirect_info->maybe_derived_type = context.maybe_derived_type;
+ edge->indirect_info->speculative_maybe_derived_type
+ = context.speculative_maybe_derived_type;
}
edge->next_callee = indirect_calls;
@@ -3043,12 +3048,9 @@
data = lto_get_section_data (file_data, LTO_section_function_body,
name, &len);
if (!data)
- {
- debug ();
fatal_error ("%s: section %s is missing",
file_data->file_name,
name);
- }
gcc_assert (DECL_STRUCT_FUNCTION (decl) == NULL);
Index: cgraph.h
===================================================================
--- cgraph.h (revision 213123)
+++ cgraph.h (working copy)
@@ -1243,11 +1243,11 @@
was actually used in the polymorphic resides within a larger structure.
If agg_contents is set, the field contains the offset within the aggregate
from which the address to call was loaded. */
- HOST_WIDE_INT offset;
+ HOST_WIDE_INT offset, speculative_offset;
/* OBJ_TYPE_REF_TOKEN of a polymorphic call (if polymorphic is set). */
HOST_WIDE_INT otr_token;
/* Type of the object from OBJ_TYPE_REF_OBJECT. */
- tree otr_type, outer_type;
+ tree otr_type, outer_type, speculative_outer_type;
/* Index of the parameter that is called. */
int param_index;
/* ECF flags determined from the caller. */
@@ -1270,6 +1270,7 @@
unsigned by_ref : 1;
unsigned int maybe_in_construction : 1;
unsigned int maybe_derived_type : 1;
+ unsigned int speculative_maybe_derived_type : 1;
};
struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller")))
cgraph_edge {
Index: gimple-fold.c
===================================================================
--- gimple-fold.c (revision 213123)
+++ gimple-fold.c (working copy)
@@ -372,11 +372,11 @@
tree val = OBJ_TYPE_REF_EXPR (rhs);
if (is_gimple_min_invariant (val))
return val;
- else if (flag_devirtualize && virtual_method_call_p (val))
+ else if (flag_devirtualize && virtual_method_call_p (rhs))
{
bool final;
vec <cgraph_node *>targets
- = possible_polymorphic_call_targets (val, stmt, &final);
+ = possible_polymorphic_call_targets (rhs, stmt, &final);
if (final && targets.length () <= 1 && dbg_cnt (devirt))
{
tree fndecl;
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c (revision 213123)
+++ ipa-devirt.c (working copy)
@@ -141,7 +141,7 @@
/* Dummy polymorphic call context. */
const ipa_polymorphic_call_context ipa_dummy_polymorphic_call_context
- = {0, NULL, false, true};
+ = {0, 0, NULL, NULL, false, true, true};
/* Pointer set of all call targets appearing in the cache. */
static pointer_set_t *cached_polymorphic_call_targets;
@@ -175,7 +175,9 @@
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
@@ -1641,8 +1643,16 @@
hash = iterative_hash_hashval_t (TYPE_UID (odr_query->context.outer_type),
hash);
hash = iterative_hash_host_wide_int (odr_query->context.offset, hash);
+ if (odr_query->context.speculative_outer_type)
+ {
+ hash = iterative_hash_hashval_t
+ (TYPE_UID (odr_query->context.speculative_outer_type), hash);
+ hash = iterative_hash_host_wide_int
(odr_query->context.speculative_offset,
+ hash);
+ }
return iterative_hash_hashval_t
- (((int)odr_query->context.maybe_in_construction << 1)
+ (((int)odr_query->context.maybe_in_construction << 2)
+ | ((int)odr_query->context.speculative_maybe_derived_type << 1)
| (int)odr_query->context.maybe_derived_type, hash);
}
@@ -1654,10 +1664,14 @@
{
return (t1->type == t2->type && t1->otr_token == t2->otr_token
&& t1->context.offset == t2->context.offset
+ && t1->context.speculative_offset == t2->context.speculative_offset
&& t1->context.outer_type == t2->context.outer_type
+ && t1->context.speculative_outer_type ==
t2->context.speculative_outer_type
&& t1->context.maybe_in_construction
== t2->context.maybe_in_construction
- && t1->context.maybe_derived_type == t2->context.maybe_derived_type);
+ && t1->context.maybe_derived_type == t2->context.maybe_derived_type
+ && (t1->context.speculative_maybe_derived_type
+ == t2->context.speculative_maybe_derived_type));
}
/* Remove entry in polymorphic call target cache hash. */
@@ -1750,24 +1764,99 @@
{
tree type = context->outer_type;
HOST_WIDE_INT offset = context->offset;
+ bool speculative = false;
+ bool speculation_valid = false;
+ bool valid = false;
+ if (!context->outer_type)
+ {
+ context->outer_type = expected_type;
+ context->offset = offset;
+ }
+ /* See if speculative type seem to be derrived from outer_type.
+ Then speculation is valid only if it really is a derivate and 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. */
+ if (context->speculative_outer_type
+ && context->speculative_offset >= context->offset
+ && contains_type_p (context->speculative_outer_type,
+ context->offset - context->speculative_offset,
+ context->outer_type))
+ speculation_valid = context->maybe_derived_type;
+
/* Find the sub-object the constant actually refers to and mark whether it is
- an artificial one (as opposed to a user-defined one). */
+ 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 iteration has SPECULATIVE set. */
while (true)
{
HOST_WIDE_INT pos, size;
tree fld;
+ /* Speculative type is assumed to be more specific then outer type. If
outer
+ type contains speculative type at a given position, consider
+ speculation valid. */
+ if (!speculative && !speculation_valid
+ && context->speculative_outer_type
+ && offset == context->speculative_offset
+ && types_same_for_odr (type, context->speculative_outer_type))
+ speculation_valid = true;
+
/* On a match, just return what we found. */
if (TREE_CODE (type) == TREE_CODE (expected_type)
&& types_same_for_odr (type, expected_type))
{
- /* Type can not contain itself on an non-zero offset. In that case
- just give up. */
- if (offset != 0)
- goto give_up;
- gcc_assert (offset == 0);
- return true;
+ if (speculative)
+ {
+ gcc_assert (speculation_valid);
+ gcc_assert (valid);
+
+ /* If we did not match the offset, just give up on speculation.
*/
+ if (offset != 0
+ || (types_same_for_odr (context->speculative_outer_type,
+ context->outer_type)
+ && (context->maybe_derived_type
+ == context->speculative_maybe_derived_type)))
+ {
+ context->speculative_outer_type = NULL;
+ context->speculative_offset = 0;
+ }
+ return true;
+ }
+ else
+ {
+ /* Type can not contain itself on an non-zero offset. In that
case
+ just give up. */
+ if (offset != 0)
+ {
+ valid = false;
+ goto give_up;
+ }
+ valid = true;
+ /* If speculation is not valid or we determined type precisely,
+ we are done. */
+ if (!speculation_valid
+ || !context->maybe_derived_type)
+ {
+ context->speculative_outer_type = NULL;
+ context->speculative_offset = 0;
+ return true;
+ }
+ /* Otherwise look into speculation now. */
+ else
+ {
+ speculative = true;
+ type = context->speculative_outer_type;
+ offset = context->speculative_offset;
+ continue;
+ }
+ }
}
/* Walk fields and find corresponding on at OFFSET. */
@@ -1792,11 +1881,20 @@
/* DECL_ARTIFICIAL represents a basetype. */
if (!DECL_ARTIFICIAL (fld))
{
- context->outer_type = type;
- context->offset = offset;
- /* As soon as we se an field containing the type,
- we know we are not looking for derivations. */
- context->maybe_derived_type = false;
+ if (!speculative)
+ {
+ context->outer_type = type;
+ context->offset = offset;
+ /* As soon as we se an field containing the type,
+ we know we are not looking for derivations. */
+ context->maybe_derived_type = false;
+ }
+ else
+ {
+ context->speculative_outer_type = type;
+ context->speculative_offset = offset;
+ context->speculative_maybe_derived_type = false;
+ }
}
}
else if (TREE_CODE (type) == ARRAY_TYPE)
@@ -1809,9 +1907,18 @@
goto give_up;
offset = offset % tree_to_shwi (TYPE_SIZE (subtype));
type = subtype;
- context->outer_type = type;
- context->offset = offset;
- context->maybe_derived_type = false;
+ if (!speculative)
+ {
+ context->outer_type = type;
+ context->offset = offset;
+ context->maybe_derived_type = false;
+ }
+ else
+ {
+ context->speculative_outer_type = type;
+ context->speculative_offset = offset;
+ context->speculative_maybe_derived_type = false;
+ }
}
/* Give up on anything else. */
else
@@ -1821,6 +1928,10 @@
/* If we failed to find subtype we look for, give up and fall back to the
most generic query. */
give_up:
+ context->speculative_outer_type = NULL;
+ context->speculative_offset = 0;
+ if (valid)
+ return true;
context->outer_type = expected_type;
context->offset = 0;
context->maybe_derived_type = true;
@@ -1831,7 +1942,8 @@
if ((TREE_CODE (type) != RECORD_TYPE
|| !TYPE_BINFO (type)
|| !polymorphic_type_binfo_p (TYPE_BINFO (type)))
- && (TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
+ && (!TYPE_SIZE (type)
+ || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
|| (offset + tree_to_uhwi (TYPE_SIZE (expected_type)) <=
tree_to_uhwi (TYPE_SIZE (type)))))
return true;
@@ -1844,9 +1956,9 @@
contains_type_p (tree outer_type, HOST_WIDE_INT offset,
tree otr_type)
{
- ipa_polymorphic_call_context context = {offset,
+ ipa_polymorphic_call_context context = {offset, 0,
TYPE_MAIN_VARIANT (outer_type),
- false, true};
+ NULL, false, true, false};
return get_class_context (&context, otr_type);
}
@@ -2054,6 +2166,9 @@
context->outer_type = TYPE_MAIN_VARIANT (TREE_TYPE (base));
context->offset = offset;
+ context->speculative_outer_type = NULL;
+ context->speculative_offset = 0;
+ context->speculative_maybe_derived_type = true;
/* Make very conservative assumption that all objects
may be in construction.
TODO: ipa-prop already contains code to tell better.
@@ -2093,6 +2208,26 @@
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;
+}
+
/* Given REF call in FNDECL, determine class of the polymorphic
call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT.
CALL is optional argument giving the actual statement (usually call) where
@@ -2112,6 +2247,9 @@
*otr_token = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (ref));
/* Set up basic info in case we find nothing interesting in the analysis. */
+ context->speculative_outer_type = NULL;
+ context->speculative_offset = 0;
+ context->speculative_maybe_derived_type = true;
context->outer_type = TYPE_MAIN_VARIANT (*otr_type);
context->offset = 0;
base_pointer = OBJ_TYPE_REF_OBJECT (ref);
@@ -2121,16 +2259,9 @@
/* Walk SSA for outer object. */
do
{
- if (TREE_CODE (base_pointer) == SSA_NAME
- && !SSA_NAME_IS_DEFAULT_DEF (base_pointer)
- && SSA_NAME_DEF_STMT (base_pointer)
- && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
+ base_pointer = walk_ssa_copies (base_pointer);
+ if (TREE_CODE (base_pointer) == ADDR_EXPR)
{
- base_pointer = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (base_pointer));
- STRIP_NOPS (base_pointer);
- }
- else if (TREE_CODE (base_pointer) == ADDR_EXPR)
- {
HOST_WIDE_INT size, max_size;
HOST_WIDE_INT offset2;
tree base = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0),
@@ -2175,7 +2306,7 @@
context->outer_type,
call,
current_function_decl);
- return NULL;
+ return base_pointer;
}
else
break;
@@ -2259,6 +2390,35 @@
return base_pointer;
}
}
+
+ 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)
+ {
+ /* Use OTR_TOKEN = INT_MAX as a marker of probably type inconsistent
+ code sequences; we arrange the calls to be builtin_unreachable
+ later. */
+ *otr_token = INT_MAX;
+ return base_pointer;
+ }
+ 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)
+ && contains_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (base_type)),
+ context->offset,
+ *otr_type))
+ {
+ context->speculative_outer_type = TYPE_MAIN_VARIANT
+ (TREE_TYPE (base_type));
+ context->speculative_offset = context->offset;
+ context->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. */
Index: ipa-prop.c
===================================================================
--- ipa-prop.c (revision 213123)
+++ ipa-prop.c (working copy)
@@ -4693,6 +4693,7 @@
bp_pack_value (&bp, ii->by_ref, 1);
bp_pack_value (&bp, ii->maybe_in_construction, 1);
bp_pack_value (&bp, ii->maybe_derived_type, 1);
+ bp_pack_value (&bp, ii->speculative_maybe_derived_type, 1);
streamer_write_bitpack (&bp);
if (ii->polymorphic)
@@ -4700,6 +4701,9 @@
streamer_write_hwi (ob, ii->otr_token);
stream_write_tree (ob, ii->otr_type, true);
stream_write_tree (ob, ii->outer_type, true);
+ stream_write_tree (ob, ii->speculative_outer_type, true);
+ if (ii->speculative_outer_type)
+ streamer_write_hwi (ob, ii->speculative_offset);
}
}
@@ -4723,11 +4727,15 @@
ii->by_ref = bp_unpack_value (&bp, 1);
ii->maybe_in_construction = bp_unpack_value (&bp, 1);
ii->maybe_derived_type = bp_unpack_value (&bp, 1);
+ ii->speculative_maybe_derived_type = bp_unpack_value (&bp, 1);
if (ii->polymorphic)
{
ii->otr_token = (HOST_WIDE_INT) streamer_read_hwi (ib);
ii->otr_type = stream_read_tree (ib, data_in);
ii->outer_type = stream_read_tree (ib, data_in);
+ ii->speculative_outer_type = stream_read_tree (ib, data_in);
+ if (ii->speculative_outer_type)
+ ii->speculative_offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
}
}
Index: ipa-utils.h
===================================================================
--- ipa-utils.h (revision 213123)
+++ ipa-utils.h (working copy)
@@ -38,13 +38,19 @@
type inheritance graph. */
struct ipa_polymorphic_call_context {
/* The called object appears in an object of type OUTER_TYPE
- at offset OFFSET. */
+ at offset OFFSET. When information is not 100% reliable, we
+ use SPECULATIVE_OUTER_TYPE and SPECULATIVE_OFFSET. */
HOST_WIDE_INT offset;
+ HOST_WIDE_INT speculative_offset;
tree outer_type;
+ tree speculative_outer_type;
/* True if outer object may be in construction or destruction. */
bool maybe_in_construction;
/* True if outer object may be of derived type. */
bool maybe_derived_type;
+ /* True if speculative outer object may be of derived type. We always
+ speculate that construction does not happen. */
+ bool speculative_maybe_derived_type;
};
/* Context representing "I know nothing". */
@@ -114,9 +121,12 @@
{
gcc_checking_assert (e->indirect_info->polymorphic);
ipa_polymorphic_call_context context = {e->indirect_info->offset,
+ e->indirect_info->speculative_offset,
e->indirect_info->outer_type,
+
e->indirect_info->speculative_outer_type,
e->indirect_info->maybe_in_construction,
- e->indirect_info->maybe_derived_type};
+ e->indirect_info->maybe_derived_type,
+
e->indirect_info->speculative_maybe_derived_type};
return possible_polymorphic_call_targets (e->indirect_info->otr_type,
e->indirect_info->otr_token,
context,
@@ -153,9 +163,12 @@
{
gcc_checking_assert (e->indirect_info->polymorphic);
ipa_polymorphic_call_context context = {e->indirect_info->offset,
+ e->indirect_info->speculative_offset,
e->indirect_info->outer_type,
+
e->indirect_info->speculative_outer_type,
e->indirect_info->maybe_in_construction,
- e->indirect_info->maybe_derived_type};
+ e->indirect_info->maybe_derived_type,
+
e->indirect_info->speculative_maybe_derived_type};
dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type,
e->indirect_info->otr_token,
context);
@@ -168,10 +181,11 @@
possible_polymorphic_call_target_p (struct cgraph_edge *e,
struct cgraph_node *n)
{
- ipa_polymorphic_call_context context = {e->indirect_info->offset,
- e->indirect_info->outer_type,
+ ipa_polymorphic_call_context context = {e->indirect_info->offset, 0,
+ e->indirect_info->outer_type, NULL,
e->indirect_info->maybe_in_construction,
- e->indirect_info->maybe_derived_type};
+ e->indirect_info->maybe_derived_type,
+ false};
return possible_polymorphic_call_target_p (e->indirect_info->otr_type,
e->indirect_info->otr_token,
context, n);
