Hi, this is the first half of the original fix to the PR, bit expanded in length. The main change is simple: we now devirtualize when aggregate propagation tells us the virtual table pointer value. This is done to prevent fold() doing it during inliner's function saving that confuses the cgraph on disappearing speculation edges.
The patch has grown in size because I decided to remove some of code duplication. I noticed we have several places where we turn generic or gimple way of representing &vtbl+offset that is now done by vtable_pointer_value_to_vtable. I also decided to avoid the jump through BINFO. I.e. knowing the virtual table pointer, then turning it into BINFO and then using BINFO to lookup the virtual table pointer and do devirtualization. For this reason I broke out gimple_get_virt_method_for_vtable from gimple_get_virt_method_for_binfo. There are no functional changes. This change however produce ICE on gcc.dg/ipa/devirt3.C. This is related to other PR on ICE for type inconsistent program (the testcase is really undefined and we are just overactive on sanity checking). I decided to this do this in incremental patch - I want to figure out how much we want to warn user about inconsistencies and how much of sanity check we can keep in, since it was incredibly useful to hammer out various latent issues in devirt code. Last change is in ipa-prop.c where I noticed that determine_known_aggregate_parts still uses TREE_TYPE (TREE_TYPE (pointer_from_gimple_code)) to determine type of aggregate passed. This is invalid, since we skip pointer type conversions. Last July with Martin we updated ipa-prop to use param_type determined from a declaration. We missed a case here that prevented me from building the testcase attached that tests that we propagate vtbl pointer in object allocated by new. new returns VOID pointer and the function just gave up. (I use new in the testcase to be sure that our current type based machinery won't trigger) Bootstrapped/regtested x86_64-linux, will commit it shortly. PR ipa/59831 * g++.dg/ipa/devirt-24.C: New testcase. * ipa-cp.c (ipa_get_indirect_edge_target_1): Give up on -fno-devirtualize; Try to devirtualize by the knowledge of virtual table pointer given by aggregate propagation. * ipa-prop.c (try_make_edge_direct_virtual_call): Likewise. ipa_print_node_jump_functions): Dump also offset that is relevant for polymorphic calls. (determine_known_aggregate_parts): Add arg_type parameter; use it instead of determining the type from pointer type. (ipa_compute_jump_functions_for_edge): Update call of determine_known_aggregate_parts. * gimple-fold.c (gimple_get_virt_method_for_vtable): Break out from ... (gimple_get_virt_method_for_binfo): ... here; simplify using vtable_pointer_value_to_vtable. * gimple-fold.h (gimple_get_virt_method_for_vtable): Declare. * ipa-devirt.c (subbinfo_with_vtable_at_offset): Turn OFFSET parameter to unsigned HOST_WIDE_INT; Use vtable_pointer_value_to_vtable. (vtable_pointer_value_to_vtable): Break out from ...; handle also POINTER_PLUS_EXPR. (vtable_pointer_value_to_binfo): ... here. * ipa-utils.h (vtable_pointer_value_to_vtable): Declare. Index: testsuite/g++.dg/ipa/devirt-24.C =================================================================== --- testsuite/g++.dg/ipa/devirt-24.C (revision 0) +++ testsuite/g++.dg/ipa/devirt-24.C (revision 0) @@ -0,0 +1,42 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fno-ipa-sra -fdump-ipa-inline -fdump-ipa-cp" } */ +void pad(void); +class A {}; +class B { +public: + A &operator[](int); +}; +class C : B { +public: + virtual int m_fn1() { return 0; } + inline A &operator[](int p1) { + int a; + a = m_fn1(); + static_cast<void>(__builtin_expect(a, 0) ?: 0); + return B::operator[](p1); + } +}; + +int *e; +static void sort(C &p1, C &p2) { + for (int i=0;; i++) { + A c, d = p2[0]; + pad(); + pad(); + pad(); + } +} + +int test (); + +void update_sources() { +while (test()) { + C f; +C *b = new (C); + sort(f, *b); + } +} +/* { dg-final { scan-ipa-dump-times "Discovered a virtual call to a known target" 1 "inline" } } */ +/* { dg-final { cleanup-ipa-dump "inline" } } */ +/* { dg-final { scan-ipa-dump-times "Aggregate passed by reference" 1 "cp" } } */ +/* { dg-final { cleanup-ipa-dump "cp" } } */ Index: ipa-cp.c =================================================================== --- ipa-cp.c (revision 207412) +++ ipa-cp.c (working copy) @@ -1479,7 +1479,7 @@ 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 || known_vals.length () <= (unsigned int) param_index) @@ -1527,14 +1527,53 @@ ipa_get_indirect_edge_target_1 (struct c return NULL_TREE; } + if (!flag_devirtualize) + return NULL_TREE; + gcc_assert (!ie->indirect_info->agg_contents); token = ie->indirect_info->otr_token; anc_offset = ie->indirect_info->offset; otr_type = ie->indirect_info->otr_type; - t = known_vals[param_index]; + t = NULL; + + /* Try to work out value of virtual table pointer value in replacemnets. */ + if (!t && agg_reps && !ie->indirect_info->by_ref) + { + while (agg_reps) + { + if (agg_reps->index == param_index + && agg_reps->offset == ie->indirect_info->offset + && agg_reps->by_ref) + { + t = agg_reps->value; + break; + } + agg_reps = agg_reps->next; + } + } + + /* Try to work out value of virtual table pointer value in 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 we found the virtual table pointer, lookup the binfo. */ + if (t) + t = vtable_pointer_value_to_binfo (t); + + /* Did we work out BINFO via type propagation? */ if (!t && known_binfos.length () > (unsigned int) param_index) t = known_binfos[param_index]; + /* Or do we know the constant value of pointer? */ + if (!t) + t = known_vals[param_index]; if (!t) return NULL_TREE; Index: ipa-prop.c =================================================================== --- ipa-prop.c (revision 207413) +++ ipa-prop.c (working copy) @@ -355,8 +355,10 @@ ipa_print_node_jump_functions (FILE *f, ii->param_index, ii->offset, ii->by_ref ? "by reference" : "by_value"); else - fprintf (f, " indirect %s callsite, calling param %i", - ii->polymorphic ? "polymorphic" : "simple", ii->param_index); + fprintf (f, " indirect %s callsite, calling param %i, " + "offset " HOST_WIDE_INT_PRINT_DEC, + ii->polymorphic ? "polymorphic" : "simple", ii->param_index, + ii->offset); if (cs->call_stmt) { @@ -1332,11 +1334,11 @@ struct ipa_known_agg_contents_list /* Traverse statements from CALL backwards, scanning whether an aggregate given in ARG is filled in with constant values. ARG can either be an aggregate - expression or a pointer to an aggregate. JFUNC is the jump function into - which the constants are subsequently stored. */ + expression or a pointer to an aggregate. ARG_TYPE is the type of the aggregate. + JFUNC is the jump function into which the constants are subsequently stored. */ static void -determine_known_aggregate_parts (gimple call, tree arg, +determine_known_aggregate_parts (gimple call, tree arg, tree arg_type, struct ipa_jump_func *jfunc) { struct ipa_known_agg_contents_list *list = NULL; @@ -1347,22 +1349,23 @@ determine_known_aggregate_parts (gimple bool check_ref, by_ref; ao_ref r; /* The function operates in three stages. First, we prepare check_ref, r, arg_base and arg_offset based on what is actually passed as an actual argument. */ - if (POINTER_TYPE_P (TREE_TYPE (arg))) + if (POINTER_TYPE_P (arg_type)) { by_ref = true; if (TREE_CODE (arg) == SSA_NAME) { tree type_size; - if (!tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (TREE_TYPE (arg))))) + if (!tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (arg_type)))) return; check_ref = true; arg_base = arg; arg_offset = 0; - type_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (arg))); + type_size = TYPE_SIZE (TREE_TYPE (arg_type)); arg_size = tree_to_uhwi (type_size); ao_ref_init_from_ptr_and_size (&r, arg_base, NULL_TREE); } @@ -1645,13 +1648,22 @@ ipa_compute_jump_functions_for_edge (str ? TREE_TYPE (param_type) : NULL); + /* If ARG is pointer, we can not use its type to determine the type of aggregate + passed (because type conversions are ignored in gimple). Usually we can + safely get type from function declaration, but in case of K&R prototypes or + variadic functions we can try our luck with type of the pointer passed. + TODO: Since we look for actual initialization of the memory object, we may better + work out the type based on the memory stores we find. */ + if (!param_type) + param_type = TREE_TYPE (arg); + if ((jfunc->type != IPA_JF_PASS_THROUGH || !ipa_get_jf_pass_through_agg_preserved (jfunc)) && (jfunc->type != IPA_JF_ANCESTOR || !ipa_get_jf_ancestor_agg_preserved (jfunc)) && (AGGREGATE_TYPE_P (TREE_TYPE (arg)) - || (POINTER_TYPE_P (TREE_TYPE (arg))))) - determine_known_aggregate_parts (call, arg, jfunc); + || POINTER_TYPE_P (param_type))) + determine_known_aggregate_parts (call, arg, param_type, jfunc); } } @@ -2676,9 +2688,23 @@ 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 do lookup binfo via known virtual table pointer value. */ + if (!ie->indirect_info->by_ref) + { + tree t = ipa_find_agg_cst_for_param (&jfunc->agg, + ie->indirect_info->offset, + true); + if (t) + binfo = vtable_pointer_value_to_binfo (t); + } + + if (!binfo) + binfo = ipa_value_from_jfunc (new_root_info, jfunc); if (!binfo) return NULL; @@ -2688,7 +2714,7 @@ try_make_edge_direct_virtual_call (struc binfo = gimple_extract_devirt_binfo_from_cst (binfo, ie->indirect_info->otr_type); if (!binfo) - return NULL; + return NULL; } binfo = get_binfo_at_offset (binfo, ie->indirect_info->offset, Index: gimple-fold.c =================================================================== --- gimple-fold.c (revision 207412) +++ gimple-fold.c (working copy) @@ -3236,33 +3236,16 @@ fold_const_aggregate_ref (tree t) return fold_const_aggregate_ref_1 (t, NULL); } -/* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN - is integer form of OBJ_TYPE_REF_TOKEN of the reference expression. - KNOWN_BINFO carries the binfo describing the true type of - OBJ_TYPE_REF_OBJECT(REF). */ +/* Lookup virtual method with index TOKEN in a virtual table V + at OFFSET. */ tree -gimple_get_virt_method_for_binfo (HOST_WIDE_INT token, tree known_binfo) +gimple_get_virt_method_for_vtable (HOST_WIDE_INT token, + tree v, + unsigned HOST_WIDE_INT offset) { - unsigned HOST_WIDE_INT offset, size; - tree v, fn, vtable, init; - - vtable = v = BINFO_VTABLE (known_binfo); - /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone. */ - if (!v) - return NULL_TREE; - - if (TREE_CODE (v) == POINTER_PLUS_EXPR) - { - offset = tree_to_uhwi (TREE_OPERAND (v, 1)) * BITS_PER_UNIT; - v = TREE_OPERAND (v, 0); - } - else - offset = 0; - - if (TREE_CODE (v) != ADDR_EXPR) - return NULL_TREE; - v = TREE_OPERAND (v, 0); + tree vtable = v, init, fn; + unsigned HOST_WIDE_INT size; if (TREE_CODE (v) != VAR_DECL || !DECL_VIRTUAL_P (v)) @@ -3281,6 +3264,7 @@ gimple_get_virt_method_for_binfo (HOST_W } gcc_checking_assert (TREE_CODE (TREE_TYPE (v)) == ARRAY_TYPE); size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (v)))); + offset *= BITS_PER_UNIT; offset += token * size; fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), init, offset, size, v); @@ -3306,6 +3290,28 @@ gimple_get_virt_method_for_binfo (HOST_W return fn; } +/* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN + is integer form of OBJ_TYPE_REF_TOKEN of the reference expression. + KNOWN_BINFO carries the binfo describing the true type of + OBJ_TYPE_REF_OBJECT(REF). */ + +tree +gimple_get_virt_method_for_binfo (HOST_WIDE_INT token, tree known_binfo) +{ + unsigned HOST_WIDE_INT offset; + tree v; + + v = BINFO_VTABLE (known_binfo); + /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone. */ + if (!v) + return NULL_TREE; + + if (!vtable_pointer_value_to_vtable (v, &v, &offset)) + return NULL_TREE; + + return gimple_get_virt_method_for_vtable (token, v, offset); +} + /* Return true iff VAL is a gimple expression that is known to be non-negative. Restricted to floating-point inputs. */ Index: gimple-fold.h =================================================================== --- gimple-fold.h (revision 207412) +++ gimple-fold.h (working copy) @@ -38,6 +38,8 @@ extern tree gimple_fold_stmt_to_constant extern tree fold_const_aggregate_ref_1 (tree, tree (*) (tree)); extern tree fold_const_aggregate_ref (tree); extern tree gimple_get_virt_method_for_binfo (HOST_WIDE_INT, tree); +extern tree gimple_get_virt_method_for_vtable (HOST_WIDE_INT, tree, + unsigned HOST_WIDE_INT); extern bool gimple_val_nonnegative_real_p (tree); extern tree gimple_fold_indirect_ref (tree); extern bool arith_code_with_undefined_signed_overflow (tree_code); Index: ipa-devirt.c =================================================================== --- ipa-devirt.c (revision 207413) +++ ipa-devirt.c (working copy) @@ -975,17 +975,24 @@ contains_type_p (tree outer_type, HOST_W /* Lookup base of BINFO that has virtual table VTABLE with OFFSET. */ static tree -subbinfo_with_vtable_at_offset (tree binfo, tree offset, tree vtable) +subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset, + tree vtable) { tree v = BINFO_VTABLE (binfo); int i; tree base_binfo; + unsigned HOST_WIDE_INT this_offset; - gcc_assert (!v || TREE_CODE (v) == POINTER_PLUS_EXPR); + if (v) + { + if (!vtable_pointer_value_to_vtable (v, &v, &this_offset)) + gcc_unreachable (); + + if (offset == this_offset + && DECL_ASSEMBLER_NAME (v) == DECL_ASSEMBLER_NAME (vtable)) + return binfo; + } - 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)) { @@ -996,11 +1003,12 @@ subbinfo_with_vtable_at_offset (tree bin return NULL; } -/* T is known constant value of virtual table pointer. Return BINFO of the - instance type. */ +/* T is known constant value of virtual table pointer. + Store virtual table to V and its offset to OFFSET. + Return false if T does not look like virtual table reference. */ -tree -vtable_pointer_value_to_binfo (tree t) +bool +vtable_pointer_value_to_vtable (tree t, tree *v, unsigned HOST_WIDE_INT *offset) { /* We expect &MEM[(void *)&virtual_table + 16B]. We obtain object's BINFO from the context of the virtual table. @@ -1011,7 +1019,7 @@ vtable_pointer_value_to_binfo (tree t) 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 + if (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 @@ -1020,20 +1028,47 @@ vtable_pointer_value_to_binfo (tree t) && 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); - - /* FIXME: for stores of construction vtables we return NULL, - because we do not have BINFO for those. Eventually we should fix - our representation to allow this case to be handled, too. - In the case we see store of BINFO we however may assume - that standard folding will be ale to cope with it. */ - return binfo; + *v = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0); + *offset = tree_to_uhwi (TREE_OPERAND (TREE_OPERAND (t, 0), 1)); + return true; } - return NULL; + + /* Alternative representation, used by C++ frontend is POINTER_PLUS_EXPR. + We need to handle it when T comes from static variable initializer or + BINFO. */ + if (TREE_CODE (t) == POINTER_PLUS_EXPR) + { + *offset = tree_to_uhwi (TREE_OPERAND (t, 1)); + t = TREE_OPERAND (t, 0); + } + else + *offset = 0; + + if (TREE_CODE (t) != ADDR_EXPR) + return false; + *v = TREE_OPERAND (t, 0); + return true; +} + +/* T is known constant value of virtual table pointer. Return BINFO of the + instance type. */ + +tree +vtable_pointer_value_to_binfo (tree t) +{ + tree vtable; + unsigned HOST_WIDE_INT offset; + + if (!vtable_pointer_value_to_vtable (t, &vtable, &offset)) + return NULL_TREE; + + /* FIXME: for stores of construction vtables we return NULL, + because we do not have BINFO for those. Eventually we should fix + our representation to allow this case to be handled, too. + In the case we see store of BINFO we however may assume + that standard folding will be ale to cope with it. */ + return subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)), + offset, vtable); } /* Given REF call in FNDECL, determine class of the polymorphic Index: ipa-utils.h =================================================================== --- ipa-utils.h (revision 207413) +++ ipa-utils.h (working copy) @@ -88,6 +88,7 @@ tree get_polymorphic_call_info (tree, tr HOST_WIDE_INT *, ipa_polymorphic_call_context *); tree vtable_pointer_value_to_binfo (tree t); +bool vtable_pointer_value_to_vtable (tree, tree *, unsigned HOST_WIDE_INT *); /* Return vector containing possible targets of polymorphic call E. If FINALP is non-NULL, store true if the list is complette.