This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH, devirtualization] Intraprocedural devirtualization pass


On Tue, Nov 1, 2011 at 11:06 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> the patch below is the second (and last) revived type-based
> devirtualization patch that did not make it to 4.6. ?It deals with
> virtual calls from the function in which the there is also the object
> declaration:
>
> void foo()
> {
> ?A a;
>
> ?a.foo ();
> }
>
> Normally, the front-end would do the devirtualization on its own,
> however, early-inlining can create these situations too. ?Since there
> is nothing interprocedural going on, the current inlining and IPA-CP
> devirtualization bits are of no help. ?We do not do type-based
> devirtualization in OBJ_TYPE_REF folding either, because the necessary
> type-changing checks might make it quite expensive.

But in the above case - a is not address-taken - we do not need
type-based devirtualization.  So, can you explain why we do not
forward the proper vtable from the vtable store that would lead to
the known-type info?

Thanks,
Richard.

> ?Thus, this patch
> introduces a new pass to do that.
>
> The patch basically piggy-tails on the intraprocedural
> devirtualization mechanism, trying to construct a known-type jump
> function for all objects in OBJ_TYPE_REF calls and then immediately
> using it like we do in IPA-CP.
>
> The original patch was doing this as a part of
> pass_rebuild_cgraph_edges. ?Honza did not like this idea so I made it
> a separate pass. ?First, I scheduled it after
> pass_rebuild_cgraph_edges and was only traversing indirect edges,
> avoiding a sweep over all of the IL. ?Unfortunately, this does not
> work in one scenario. ?If the newly-known destination of a virtual
> call is known not to throw, we may have to purge some EH CFG edges and
> potentially basic blocks. ?If these basic blocks contain calls
> (typically calls to object destructors), we may end up having stale
> call edges in the call graph... and our current approach to that
> problem is to call pass_rebuild_cgraph_edges. ?I think that I was not
> running into this problem when the mechanism was a part of that pass
> just because of pure luck. ?Anyway, this is why I eventually opted for
> a sweep over the statements.
>
> My best guess is that it is probably worth it, but only because the
> overhead should be still fairly low. ?The pass triggers quite a number
> of times when building libstdc++ and it can speed up an artificial
> testcase which I will attach from over 20 seconds to 7s on my older
> desktop - it is very similar to the one I posted with the previous
> patch but this time the object constructors must not get early inlined
> but the function multiply_matrices has to. ?Currently I have problems
> compiling Firefox even without LTO so I don't have any numbers from it
> either. ?IIRC, Honza did not see this patch trigger there when he
> tried the ancient version almost a year go. ?On the other hand, Maxim
> claimed that the impact can be noticeable on some code base he is
> concerned about.
>
> I have successfully bootstrapped and tested the patch on x86_64-linux.
> What do you think, should we include this in trunk?
>
> Thanks,
>
> Martin
>
>
> 2011-10-31 ?Martin Jambor ?<mjambor@suse.cz>
>
> ? ? ? ?* ipa-cp.c (ipa_value_from_known_type_jfunc): Moved to...
> ? ? ? ?* ipa-prop.c (ipa_binfo_from_known_type_jfunc): ...here, exported and
> ? ? ? ?updated all callers.
> ? ? ? ?(intraprocedural_devirtualization): New function.
> ? ? ? ?(gate_intra_devirtualization): Likewise.
> ? ? ? ?(pass_intra_devirt): New pass.
> ? ? ? ?* ipa-prop.h (ipa_binfo_from_known_type_jfunc): Declared.
> ? ? ? ?* passes.c (init_optimization_passes): Schedule pass_intra_devirt.
> ? ? ? ?* tree-pass.h (pass_intra_devirt): Declare.
>
> ? ? ? ?* testsuite/g++.dg/ipa/imm-devirt-1.C: New test.
> ? ? ? ?* testsuite/g++.dg/ipa/imm-devirt-2.C: Likewise.
>
>
> Index: src/gcc/testsuite/g++.dg/ipa/imm-devirt-1.C
> ===================================================================
> --- /dev/null
> +++ src/gcc/testsuite/g++.dg/ipa/imm-devirt-1.C
> @@ -0,0 +1,62 @@
> +/* Verify that virtual calls are folded even when a typecast to an
> + ? ancestor is involved along the way. ?*/
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-devirt" ?} */
> +
> +extern "C" void abort (void);
> +
> +class A
> +{
> +public:
> + ?int data;
> + ?virtual int foo (int i);
> +};
> +
> +
> +class B : public A
> +{
> +public:
> + ?__attribute__ ((noinline)) B();
> + ?virtual int foo (int i);
> +};
> +
> +int __attribute__ ((noinline)) A::foo (int i)
> +{
> + ?return i + 1;
> +}
> +
> +int __attribute__ ((noinline)) B::foo (int i)
> +{
> + ?return i + 2;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> + ?return 1;
> +}
> +
> +__attribute__ ((noinline)) B::B()
> +{
> +}
> +
> +static inline int middleman_1 (class A *obj, int i)
> +{
> + ?return obj->foo (i);
> +}
> +
> +static inline int middleman_2 (class B *obj, int i)
> +{
> + ?return middleman_1 (obj, i);
> +}
> +
> +int main (int argc, char *argv[])
> +{
> + ?class B b;
> +
> + ?if (middleman_2 (&b, get_input ()) != 3)
> + ? ?abort ();
> + ?return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump "Immediately devirtualizing call.*into.*B::foo" ?"devirt" ?} } */
> +/* { dg-final { cleanup-tree-dump "devirt" } } */
> Index: src/gcc/testsuite/g++.dg/ipa/imm-devirt-2.C
> ===================================================================
> --- /dev/null
> +++ src/gcc/testsuite/g++.dg/ipa/imm-devirt-2.C
> @@ -0,0 +1,95 @@
> +/* Verify that virtual calls are folded even when a typecast to an
> + ? ancestor is involved along the way. ?*/
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-devirt-slim" ?} */
> +
> +extern "C" void abort (void);
> +
> +class Distraction
> +{
> +public:
> + ?float f;
> + ?double d;
> + ?Distraction ()
> + ?{
> + ? ?f = 8.3;
> + ? ?d = 10.2;
> + ?}
> + ?virtual float bar (float z);
> +};
> +
> +class A
> +{
> +public:
> + ?int data;
> + ?virtual int foo (int i);
> +};
> +
> +class B : public A
> +{
> +public:
> + ?int data_2;
> + ?virtual int foo (int i);
> + ?virtual int baz (int i);
> +};
> +
> +
> +class C : public Distraction, public B
> +{
> +public:
> + ?__attribute__ ((noinline)) C();
> + ?virtual int foo (int i);
> +};
> +
> +float __attribute__ ((noinline)) Distraction::bar (float z)
> +{
> + ?f += z;
> + ?return f/2;
> +}
> +
> +int __attribute__ ((noinline)) A::foo (int i)
> +{
> + ?return i + 1;
> +}
> +
> +int __attribute__ ((noinline)) B::foo (int i)
> +{
> + ?return i + 2;
> +}
> +
> +int __attribute__ ((noinline)) B::baz (int i)
> +{
> + ?return i * 15;
> +}
> +
> +int __attribute__ ((noinline)) C::foo (int i)
> +{
> + ?return i + 3;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> + ?return 1;
> +}
> +
> +static inline int middleman (class A *obj, int i)
> +{
> + ?return obj->foo (i);
> +}
> +
> +__attribute__ ((noinline)) C::C()
> +{
> +}
> +
> +int main (int argc, char *argv[])
> +{
> + ?class C c;
> +
> + ?if (middleman (&c, get_input ()) != 4)
> + ? ?abort ();
> +
> + ?return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump "Immediately devirtualizing call.*into.*C::.*foo" ?"devirt" ?} } */
> +/* { dg-final { cleanup-tree-dump "devirt" } } */
> Index: src/gcc/ipa-cp.c
> ===================================================================
> --- src.orig/gcc/ipa-cp.c
> +++ src/gcc/ipa-cp.c
> @@ -674,20 +674,6 @@ ipa_get_jf_ancestor_result (struct ipa_j
> ? ? return NULL_TREE;
> ?}
>
> -/* Extract the acual BINFO being described by JFUNC which must be a known type
> - ? jump function. ?*/
> -
> -static tree
> -ipa_value_from_known_type_jfunc (struct ipa_jump_func *jfunc)
> -{
> - ?tree base_binfo = TYPE_BINFO (jfunc->value.known_type.base_type);
> - ?if (!base_binfo)
> - ? ?return NULL_TREE;
> - ?return get_binfo_at_offset (base_binfo,
> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? jfunc->value.known_type.offset,
> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? jfunc->value.known_type.component_type);
> -}
> -
> ?/* Determine whether JFUNC evaluates to a known value (that is either a
> ? ?constant or a binfo) and if so, return it. ?Otherwise return NULL. INFO
> ? ?describes the caller node so that pass-through jump functions can be
> @@ -699,7 +685,7 @@ ipa_value_from_jfunc (struct ipa_node_pa
> ? if (jfunc->type == IPA_JF_CONST)
> ? ? return jfunc->value.constant;
> ? else if (jfunc->type == IPA_JF_KNOWN_TYPE)
> - ? ?return ipa_value_from_known_type_jfunc (jfunc);
> + ? ?return ipa_binfo_from_known_type_jfunc (jfunc);
> ? else if (jfunc->type == IPA_JF_PASS_THROUGH
> ? ? ? ? ? || jfunc->type == IPA_JF_ANCESTOR)
> ? ? {
> @@ -1006,7 +992,7 @@ propagate_accross_jump_function (struct
>
> ? ? ? if (jfunc->type == IPA_JF_KNOWN_TYPE)
> ? ? ? ?{
> - ? ? ? ? val = ipa_value_from_known_type_jfunc (jfunc);
> + ? ? ? ? val = ipa_binfo_from_known_type_jfunc (jfunc);
> ? ? ? ? ?if (!val)
> ? ? ? ? ? ?return set_lattice_contains_variable (dest_lat);
> ? ? ? ?}
> Index: src/gcc/ipa-prop.c
> ===================================================================
> --- src.orig/gcc/ipa-prop.c
> +++ src/gcc/ipa-prop.c
> @@ -3069,3 +3069,107 @@ ipa_update_after_lto_read (void)
> ? ? if (node->analyzed)
> ? ? ? ipa_initialize_node_params (node);
> ?}
> +
> +/* Extract the acual BINFO being described by JFUNC which must be a known type
> + ? jump function. ?*/
> +
> +tree
> +ipa_binfo_from_known_type_jfunc (struct ipa_jump_func *jfunc)
> +{
> + ?tree base_binfo = TYPE_BINFO (jfunc->value.known_type.base_type);
> + ?if (!base_binfo)
> + ? ?return NULL_TREE;
> + ?return get_binfo_at_offset (base_binfo,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? jfunc->value.known_type.offset,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? jfunc->value.known_type.component_type);
> +}
> +
> +/* Intraprocedural (early) type-based devirtualization pass. ?Looks at all call
> + ? statements and attempts type-base devirtualization on those calling an
> + ? OBJ_TYPE_REF. ?*/
> +
> +static unsigned int
> +intraprocedural_devirtualization (void)
> +{
> + ?basic_block bb;
> + ?gimple_stmt_iterator gsi;
> + ?bool cfg_changed = false;
> +
> + ?FOR_EACH_BB (bb)
> + ? ?for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> + ? ? ?if (is_gimple_call (gsi_stmt (gsi)))
> + ? ? ? {
> + ? ? ? ? tree binfo, token, fndecl;
> + ? ? ? ? gimple call = gsi_stmt (gsi);
> + ? ? ? ? tree target = gimple_call_fn (call);
> + ? ? ? ? struct ipa_jump_func jfunc;
> +
> + ? ? ? ? if (TREE_CODE (target) != OBJ_TYPE_REF)
> + ? ? ? ? ? continue;
> +
> + ? ? ? ? jfunc.type = IPA_JF_UNKNOWN;
> + ? ? ? ? compute_known_type_jump_func (OBJ_TYPE_REF_OBJECT (target), &jfunc,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? call);
> + ? ? ? ? if (jfunc.type != IPA_JF_KNOWN_TYPE)
> + ? ? ? ? ? continue;
> + ? ? ? ? binfo = ipa_binfo_from_known_type_jfunc (&jfunc);
> + ? ? ? ? if (!binfo)
> + ? ? ? ? ? continue;
> + ? ? ? ? token = OBJ_TYPE_REF_TOKEN (target);
> + ? ? ? ? fndecl = gimple_get_virt_method_for_binfo (tree_low_cst (token, 1),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?binfo);
> + ? ? ? ? if (!fndecl)
> + ? ? ? ? ? continue;
> +
> + ? ? ? ? if (dump_file)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? fprintf (dump_file, "ipa-prop: Immediately devirtualizing call ");
> + ? ? ? ? ? ? print_gimple_expr (dump_file, call, 0, 0);
> + ? ? ? ? ? }
> +
> + ? ? ? ? gimple_call_set_fndecl (call, fndecl);
> + ? ? ? ? update_stmt (call);
> + ? ? ? ? if (maybe_clean_eh_stmt (call)
> + ? ? ? ? ? ? && gimple_purge_dead_eh_edges (bb))
> + ? ? ? ? ? cfg_changed = true;
> +
> + ? ? ? ? if (dump_file)
> + ? ? ? ? ? {
> + ? ? ? ? ? ? fprintf (dump_file, " into ");
> + ? ? ? ? ? ? print_gimple_expr (dump_file, call, 0, 0);
> + ? ? ? ? ? ? fprintf (dump_file, "\n");
> + ? ? ? ? ? }
> + ? ? ? }
> +
> +
> + if (cfg_changed)
> + ? ?return TODO_cleanup_cfg;
> + ?else
> + ? ?return 0;
> +}
> +
> +static bool
> +gate_intra_devirtualization (void)
> +{
> + ?return flag_devirtualize != 0;
> +}
> +
> +
> +struct gimple_opt_pass pass_intra_devirt =
> + ?{
> + ? ?{
> + ? ? ?GIMPLE_PASS,
> + ? ? ?"devirt", ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?/* name */
> + ? ? ?gate_intra_devirtualization, ? ? ? ? ? ? /* gate */
> + ? ? ?intraprocedural_devirtualization, ? ? ? ?/* execute */
> + ? ? ?NULL, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?/* sub */
> + ? ? ?NULL, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?/* next */
> + ? ? ?0, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /* static_pass_number */
> + ? ? ?TV_CGRAPH, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /* tv_id */
> + ? ? ?PROP_cfg, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?/* properties_required */
> + ? ? ?0, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /* properties_provided */
> + ? ? ?0, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /* properties_destroyed */
> + ? ? ?0, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /* todo_flags_start */
> + ? ? ?0, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? /* todo_flags_finish */
> + ? ?}
> + ?};
> Index: src/gcc/ipa-prop.h
> ===================================================================
> --- src.orig/gcc/ipa-prop.h
> +++ src/gcc/ipa-prop.h
> @@ -347,6 +347,7 @@ bool ipa_propagate_indirect_call_infos (
>
> ?/* Indirect edge and binfo processing. ?*/
> ?struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree);
> +tree ipa_binfo_from_known_type_jfunc (struct ipa_jump_func *);
>
> ?/* Functions related to both. ?*/
> ?void ipa_analyze_node (struct cgraph_node *);
> Index: src/gcc/passes.c
> ===================================================================
> --- src.orig/gcc/passes.c
> +++ src/gcc/passes.c
> @@ -1225,6 +1225,7 @@ init_optimization_passes (void)
> ? ? ? ? ? NEXT_PASS (pass_cleanup_eh);
> ? ? ? ? ? NEXT_PASS (pass_profile);
> ? ? ? ? ? NEXT_PASS (pass_local_pure_const);
> + ? ? ? ? NEXT_PASS (pass_intra_devirt);
> ? ? ? ? ?/* Split functions creates parts that are not run through
> ? ? ? ? ? ? early optimizations again. ?It is thus good idea to do this
> ? ? ? ? ? ? late. ?*/
> Index: src/gcc/tree-pass.h
> ===================================================================
> --- src.orig/gcc/tree-pass.h
> +++ src/gcc/tree-pass.h
> @@ -449,6 +449,7 @@ extern struct gimple_opt_pass pass_trace
> ?extern struct gimple_opt_pass pass_warn_unused_result;
> ?extern struct gimple_opt_pass pass_split_functions;
> ?extern struct gimple_opt_pass pass_feedback_split_functions;
> +extern struct gimple_opt_pass pass_intra_devirt;
>
> ?/* IPA Passes */
> ?extern struct simple_ipa_opt_pass pass_ipa_lower_emutls;
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]