Re: [PATCH, PR 56718] Middle-end intraprocedural type-based devirtualization
On Wed, Apr 17, 2013 at 5:59 PM, Martin Jambor wrote:
> Hi,
>
> this patch implements type-based devirtualization done
> intra-procedurally. This is normally done by the front-end except in
> cases when opportunities for this transformation are created by
> early-inlining. Because we handle this situation at IPA-level
> (especially in inlining but also in IPA-CP), this can currently mean
> that some code runs much faster when compiled without early-inlining,
> e.g. the PR 56718 testcase.
>
> This patch piggy-backs on PRE OBJ_TYPE_REF folding and when that
> fails, it calls into ipa-cp routines that simply use the
> infrastructure we have for construction of known-type jump functions
> to figure out the type of the object involved. If that is known, the
> appropriate method is looked up in the VMT obtained from its BINFO.
>
> From now on I'll concentrate on tracking of VMT pointers within
> objects rather than on type-based techniques in my devirtualization
> efforts. Nevertheless, I do believe we want to have this patch in
> because (as opposed to VMT tracking) it can also work when
> constructors are in a different compilation unit. Even these
> situations do not occur that often, the effects can be quite
> substantial when we miss an inlining opportunity, the testcase in the
> PR 56718 is rather artificial but 2.5 times quicker with the patch.
>
> A very similar patch has passed bootstrap and testing on x86_64-linux
> without any problems, I'm bootstrapping and testing this exact one
> now. OK for trunk if it passes?
Ok.
Thanks,
Richard.
> Thanks,
>
> Martin
>
>
> 2013-03-25 Martin Jambor
>
> PR tree-optimization/56718
> * ipa-cp.c (ipa_value_from_known_type_jfunc): Moved...
> * ipa-prop.c (ipa_binfo_from_known_type_jfunc): ...here, renamed
> and made public. adjusted all callers.
> (ipa_intraprocedural_devirtualization): New function.
> * ipa-prop.h (ipa_binfo_from_known_type_jfunc): Declare.
> (ipa_intraprocedural_devirtualization): Likewise.
>
> * Makefile.in (tree-ssa-pre.o): Add ipa-prop.h to dependencies.
>
> testsuite/
> * g++.dg/ipa/imm-devirt-1.C: New test.
> * g++.dg/ipa/imm-devirt-2.C: Likewise.
>
> *** /tmp/ITGyHx_Makefile.in 2013-04-16 00:02:39.0 +0200
> --- gcc/Makefile.in 2013-04-15 15:02:53.079696533 +0200
> *** tree-ssa-pre.o : tree-ssa-pre.c $(TREE_F
> *** 2369,2375
> $(TM_H) coretypes.h $(TREE_PASS_H) $(FLAGS_H) langhooks.h \
> $(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASH_TABLE_H) \
> $(GIMPLE_H) $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h
> $(PARAMS_H) \
> !$(DBGCNT_H) tree-scalar-evolution.h $(GIMPLE_PRETTY_PRINT_H) domwalk.h
> tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TREE_FLOW_H) $(CONFIG_H) \
> $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) \
> $(TM_H) coretypes.h $(DUMPFILE_H) $(FLAGS_H) $(CFGLOOP_H) \
> --- 2369,2376
> $(TM_H) coretypes.h $(TREE_PASS_H) $(FLAGS_H) langhooks.h \
> $(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASH_TABLE_H) \
> $(GIMPLE_H) $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h
> $(PARAMS_H) \
> !$(DBGCNT_H) tree-scalar-evolution.h $(GIMPLE_PRETTY_PRINT_H) domwalk.h \
> !$(IPA_PROP_H)
> tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TREE_FLOW_H) $(CONFIG_H) \
> $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) \
> $(TM_H) coretypes.h $(DUMPFILE_H) $(FLAGS_H) $(CFGLOOP_H) \
> *** /tmp/CO3mFA_ipa-cp.c2013-04-16 00:02:39.0 +0200
> --- gcc/ipa-cp.c2013-04-15 15:02:53.070696564 +0200
> *** ipa_get_jf_ancestor_result (struct ipa_j
> *** 791,810
> 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 (ipa_get_jf_known_type_base_type (jfunc));
> - if (!base_binfo)
> - return NULL_TREE;
> - return get_binfo_at_offset (base_binfo,
> - ipa_get_jf_known_type_offset (jfunc),
> - ipa_get_jf_known_type_component_type (jfunc));
> - }
> -
> /* 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
> --- 791,796
> *** ipa_value_from_jfunc (struct ipa_node_pa
> *** 816,822
> if (jfunc->type == IPA_JF_CONST)
> return ipa_get_jf_constant (jfunc);
> else if (jfunc->type == IPA_JF_KNOWN_TYPE)
> ! return ipa_value_from_known_type_jfunc (jfunc);
> else if (jfunc->type == IPA_JF_PASS_THROUGH
>|| jfunc->type == IPA_JF_ANCESTOR)
> {
> --- 802,808
> if (jfunc->type == IPA_JF_CONST)
> return ipa_get_jf_constant (jfunc);
> e
[PATCH, PR 56718] Middle-end intraprocedural type-based devirtualization
Hi,
this patch implements type-based devirtualization done
intra-procedurally. This is normally done by the front-end except in
cases when opportunities for this transformation are created by
early-inlining. Because we handle this situation at IPA-level
(especially in inlining but also in IPA-CP), this can currently mean
that some code runs much faster when compiled without early-inlining,
e.g. the PR 56718 testcase.
This patch piggy-backs on PRE OBJ_TYPE_REF folding and when that
fails, it calls into ipa-cp routines that simply use the
infrastructure we have for construction of known-type jump functions
to figure out the type of the object involved. If that is known, the
appropriate method is looked up in the VMT obtained from its BINFO.
>From now on I'll concentrate on tracking of VMT pointers within
objects rather than on type-based techniques in my devirtualization
efforts. Nevertheless, I do believe we want to have this patch in
because (as opposed to VMT tracking) it can also work when
constructors are in a different compilation unit. Even these
situations do not occur that often, the effects can be quite
substantial when we miss an inlining opportunity, the testcase in the
PR 56718 is rather artificial but 2.5 times quicker with the patch.
A very similar patch has passed bootstrap and testing on x86_64-linux
without any problems, I'm bootstrapping and testing this exact one
now. OK for trunk if it passes?
Thanks,
Martin
2013-03-25 Martin Jambor
PR tree-optimization/56718
* ipa-cp.c (ipa_value_from_known_type_jfunc): Moved...
* ipa-prop.c (ipa_binfo_from_known_type_jfunc): ...here, renamed
and made public. adjusted all callers.
(ipa_intraprocedural_devirtualization): New function.
* ipa-prop.h (ipa_binfo_from_known_type_jfunc): Declare.
(ipa_intraprocedural_devirtualization): Likewise.
* Makefile.in (tree-ssa-pre.o): Add ipa-prop.h to dependencies.
testsuite/
* g++.dg/ipa/imm-devirt-1.C: New test.
* g++.dg/ipa/imm-devirt-2.C: Likewise.
*** /tmp/ITGyHx_Makefile.in 2013-04-16 00:02:39.0 +0200
--- gcc/Makefile.in 2013-04-15 15:02:53.079696533 +0200
*** tree-ssa-pre.o : tree-ssa-pre.c $(TREE_F
*** 2369,2375
$(TM_H) coretypes.h $(TREE_PASS_H) $(FLAGS_H) langhooks.h \
$(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASH_TABLE_H) \
$(GIMPLE_H) $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h $(PARAMS_H) \
!$(DBGCNT_H) tree-scalar-evolution.h $(GIMPLE_PRETTY_PRINT_H) domwalk.h
tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) \
$(TM_H) coretypes.h $(DUMPFILE_H) $(FLAGS_H) $(CFGLOOP_H) \
--- 2369,2376
$(TM_H) coretypes.h $(TREE_PASS_H) $(FLAGS_H) langhooks.h \
$(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASH_TABLE_H) \
$(GIMPLE_H) $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h $(PARAMS_H) \
!$(DBGCNT_H) tree-scalar-evolution.h $(GIMPLE_PRETTY_PRINT_H) domwalk.h \
!$(IPA_PROP_H)
tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) \
$(TM_H) coretypes.h $(DUMPFILE_H) $(FLAGS_H) $(CFGLOOP_H) \
*** /tmp/CO3mFA_ipa-cp.c2013-04-16 00:02:39.0 +0200
--- gcc/ipa-cp.c2013-04-15 15:02:53.070696564 +0200
*** ipa_get_jf_ancestor_result (struct ipa_j
*** 791,810
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 (ipa_get_jf_known_type_base_type (jfunc));
- if (!base_binfo)
- return NULL_TREE;
- return get_binfo_at_offset (base_binfo,
- ipa_get_jf_known_type_offset (jfunc),
- ipa_get_jf_known_type_component_type (jfunc));
- }
-
/* 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
--- 791,796
*** ipa_value_from_jfunc (struct ipa_node_pa
*** 816,822
if (jfunc->type == IPA_JF_CONST)
return ipa_get_jf_constant (jfunc);
else if (jfunc->type == IPA_JF_KNOWN_TYPE)
! return ipa_value_from_known_type_jfunc (jfunc);
else if (jfunc->type == IPA_JF_PASS_THROUGH
|| jfunc->type == IPA_JF_ANCESTOR)
{
--- 802,808
if (jfunc->type == IPA_JF_CONST)
return ipa_get_jf_constant (jfunc);
else if (jfunc->type == IPA_JF_KNOWN_TYPE)
! return ipa_binfo_from_known_type_jfunc (jfunc);
else if (jfunc->type == IPA_JF_PASS_THROUGH
|| jfunc->type == IPA_JF_ANCESTOR)
{
*** propagate_scalar_accross_jump_function (
*** 1103,1109
