[PATCH 3/6] Folding of virtual calls
Richard Guenther
richard.guenther@gmail.com
Sat Feb 13 18:12:00 GMT 2010
On Sat, Feb 13, 2010 at 7:01 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> this patch has not changed at all since I posted it last time in
> January but needs to be applied before the next one is so I send it
> along again.
>
> The purpose of the patch is to allow folding of more complex
> OBJ_TYPE_REFs, as opposed to only the simple class we are able to fold
> today. This patch only implements devirtualization through statement
> folding (which is also greatly improved, for example we can now fold
> when early inlining makes type information available). However, it
> also facilitates interface necessary for IPA devirtualization
> including indirect inlining of virtual calls.
>
> The juggling with binfos is a bit bizarre and perhaps a C++ maintainer
> should have a look at it but it has worked seamlessly in my tests for
> a few months now so I'm becoming quite confident it is in fact
> correct.
May I ask you to start populating new gimple-fold.[ch] files instead of
adding to gimple.c? Eventually all of fold_stmt should move there
from tree-ssa-ccp.c, but of course not as part of this patch.
Thanks,
Richard.
> Thanks,
>
> Martin
>
>
> 2010-02-10 Martin Jambor <mjambor@suse.cz>
>
> * gimple.c (get_base_binfo_for_type): New function.
> (get_relevant_ref_binfo_single_inh): New function.
> (get_relevant_ref_binfo_multi_inh): New function.
> (gimple_fold_obj_type_ref_known_binfo): New function.
> (gimple_fold_obj_type_ref): Get binfo from
> get_relevant_ref_binfo_single_inh and
> get_relevant_ref_binfo_multi_inh and use
> gimple_fold_obj_type_ref_known_binfo.
> * gimple.h (gimple_fold_obj_type_ref): Declare.
> (gimple_fold_obj_type_ref_known_binfo): Declare.
> * tree-ssa-ccp.c (fold_gimple_call): Simplify condition for
> folding virtual calls and call gimple_fold_obj_type_ref.
>
>
> Index: icln/gcc/gimple.c
> ===================================================================
> --- icln.orig/gcc/gimple.c
> +++ icln/gcc/gimple.c
> @@ -4632,27 +4632,167 @@ gimple_decl_printable_name (tree decl, i
> return IDENTIFIER_POINTER (DECL_NAME (decl));
> }
>
> +/* Search for a base binfo of BINFO that corresponds to TYPE and return it if
> + it is found or NULL_TREE if it is not. */
> +
> +static tree
> +get_base_binfo_for_type (tree binfo, tree type)
> +{
> + int i;
> + tree base_binfo;
> + tree res = NULL_TREE;
> +
> + for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> + if (TREE_TYPE (base_binfo) == type)
> + {
> + gcc_assert (!res);
> + res = base_binfo;
> + }
> +
> + return res;
> +}
> +
> +/* Return a binfo describing the true type of object referenced by expression
> + REF if all component references access first ancestors. REF can consist of
> + a series of COMPONENT_REFs of with a declaration or an INDIREC_REF. It can
> + also be just a simple declaration, indirect reference or an SSA_NAME. If
> + the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
> + the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
> + KNOWN_BINFO is NULL_TREE. Otherwise the first nonartifical field declaration
> + or the base declaration will be examined to get the encapsulating type. If
> + a COMPONENT_REF referencing an ancestor which is not the first one, this
> + function returns NULL_TREE and sets *try_multi to true. */
> +
> +static tree
> +get_relevant_ref_binfo_single_inh (tree ref, tree known_binfo, bool *try_multi)
> +{
> + while (true)
> + {
> + if (TREE_CODE (ref) == COMPONENT_REF)
> + {
> + tree par_type;
> + tree binfo, base_binfo;
> + tree field = TREE_OPERAND (ref, 1);
> +
> + if (!DECL_ARTIFICIAL (field))
> + {
> + tree type = TREE_TYPE (field);
> + if (TREE_CODE (type) == RECORD_TYPE)
> + return TYPE_BINFO (type);
> + else
> + return NULL_TREE;
> + }
> +
> + par_type = TREE_TYPE (TREE_OPERAND (ref, 0));
> + binfo = TYPE_BINFO (par_type);
> + if (!binfo
> + || BINFO_N_BASE_BINFOS (binfo) == 0)
> + {
> + if (try_multi)
> + *try_multi = 1;
> + return NULL_TREE;
> + }
> + base_binfo = BINFO_BASE_BINFO (binfo, 0);
> + if (TREE_TYPE (base_binfo) != TREE_TYPE (field))
> + {
> + if (try_multi)
> + *try_multi = 1;
> + return NULL_TREE;
> + }
> +
> + ref = TREE_OPERAND (ref, 0);
> + }
> + else if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
> + return TYPE_BINFO (TREE_TYPE (ref));
> + else if (known_binfo
> + && (TREE_CODE (ref) == SSA_NAME
> + || TREE_CODE (ref) == INDIRECT_REF))
> + return known_binfo;
> + else
> + return NULL_TREE;
> + }
> +}
>
> -/* Fold a OBJ_TYPE_REF expression to the address of a function.
> - KNOWN_TYPE carries the true type of OBJ_TYPE_REF_OBJECT(REF). Adapted
> - from cp_fold_obj_type_ref, but it tolerates types with no binfo
> - data. */
> +
> +/* Return a binfo describing the part of object referenced by expression REF.
> + This can and often is a base_binfo of a descendatn binfo. REF can consist of
> + a series of COMPONENT_REFs of with a declaration or an INDIREC_REF. It can
> + also be just a simple declaration, indirect reference or an SSA_NAME. If
> + the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
> + the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
> + KNOWN_BINFO is NULL_TREE. Otherwise the first nonartifical field
> + declaration or the base declaration will be examined to get the
> + encapsulating type. */
> +
> +static tree
> +get_relevant_ref_binfo_multi_inh (tree ref, tree known_binfo)
> +{
> + if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
> + return TYPE_BINFO (TREE_TYPE (ref));
> + else if (TREE_CODE (ref) == COMPONENT_REF)
> + {
> + tree desc_binfo;
> + tree field = TREE_OPERAND (ref, 1);
> +
> + if (!DECL_ARTIFICIAL (field))
> + {
> + tree type = TREE_TYPE (field);
> + if (TREE_CODE (type) == RECORD_TYPE)
> + return TYPE_BINFO (type);
> + else
> + return NULL_TREE;
> + }
> +
> + desc_binfo = get_relevant_ref_binfo_multi_inh (TREE_OPERAND (ref, 0),
> + known_binfo);
> + if (!desc_binfo)
> + return NULL_TREE;
> + return get_base_binfo_for_type (desc_binfo, TREE_TYPE (field));
> + }
> + else if (known_binfo
> + && (TREE_CODE (ref) == SSA_NAME
> + || TREE_CODE (ref) == INDIRECT_REF))
> + return known_binfo;
> + else
> + return NULL_TREE;
> +}
> +
> +/* Return a binfo describing the part of object referenced by expression REF
> + using both get_relevant_ref_binfo_single_inh and
> + get_relevant_ref_binfo_multi_inh in this particular order. */
>
> tree
> -gimple_fold_obj_type_ref (tree ref, tree known_type)
> +gimple_get_relevant_ref_binfo (tree ref, tree known_binfo)
> +{
> + bool try_multi = false;
> + tree binfo;
> +
> + binfo = get_relevant_ref_binfo_single_inh (ref, known_binfo, &try_multi);
> + if (!binfo && try_multi)
> + binfo = get_relevant_ref_binfo_multi_inh (ref, known_binfo);
> + return binfo;
> +}
> +
> +
> +/* Fold a OBJ_TYPE_REF expression to the address of a function. 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_fold_obj_type_ref_known_binfo (HOST_WIDE_INT token, tree known_binfo)
> {
> - HOST_WIDE_INT index;
> HOST_WIDE_INT i;
> - tree v;
> - tree fndecl;
> + tree v, fndecl;
>
> - if (TYPE_BINFO (known_type) == NULL_TREE)
> + /* If binfo flag 2 is not set, this binfo does not "have its own virtual
> + table" (according to cp/cp-tree.h) and cannot be safely used for
> + devirtualization. Purely empirical experience also shows that we can also
> + bail out if flag 5 is set. This test also probably works in lto. */
> + if (BINFO_FLAG_5 (known_binfo))
> return NULL_TREE;
> -
> - v = BINFO_VIRTUALS (TYPE_BINFO (known_type));
> - index = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
> + v = BINFO_VIRTUALS (known_binfo);
> i = 0;
> - while (i != index)
> + while (i != token)
> {
> i += (TARGET_VTABLE_USES_DESCRIPTORS
> ? TARGET_VTABLE_USES_DESCRIPTORS : 1);
> @@ -4660,15 +4800,34 @@ gimple_fold_obj_type_ref (tree ref, tree
> }
>
> fndecl = TREE_VALUE (v);
> + return build_fold_addr_expr (fndecl);
> +}
>
> -#ifdef ENABLE_CHECKING
> - gcc_assert (tree_int_cst_equal (OBJ_TYPE_REF_TOKEN (ref),
> - DECL_VINDEX (fndecl)));
> -#endif
>
> - cgraph_node (fndecl)->local.vtable_method = true;
> +/* Fold a OBJ_TYPE_REF expression to the address of a function. If KNOWN_TYPE
> + is not NULL_TREE, it is the true type of the outmost encapsulating object if
> + that comes from a pointer SSA_NAME. If the true outmost encapsulating type
> + can be determined from a declaration OBJ_TYPE_REF_OBJECT(REF), it is used
> + regardless of KNOWN_TYPE (which thuc can be NULL_TREE). */
>
> - return build_fold_addr_expr (fndecl);
> +tree
> +gimple_fold_obj_type_ref (tree ref, tree known_type)
> +{
> + tree obj = OBJ_TYPE_REF_OBJECT (ref);
> + tree known_binfo = known_type ? TYPE_BINFO (known_type) : NULL_TREE;
> + tree binfo;
> +
> + if (TREE_CODE (obj) == ADDR_EXPR)
> + obj = TREE_OPERAND (obj, 0);
> +
> + binfo = gimple_get_relevant_ref_binfo (obj, known_binfo);
> + if (binfo)
> + {
> + HOST_WIDE_INT token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
> + return gimple_fold_obj_type_ref_known_binfo (token, binfo);
> + }
> + else
> + return NULL_TREE;
> }
>
> #include "gt-gimple.h"
> Index: icln/gcc/tree-ssa-ccp.c
> ===================================================================
> --- icln.orig/gcc/tree-ssa-ccp.c
> +++ icln/gcc/tree-ssa-ccp.c
> @@ -3007,9 +3007,6 @@ fold_gimple_call (gimple_stmt_iterator *
> }
> else
> {
> - /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
> - here are when we've propagated the address of a decl into the
> - object slot. */
> /* ??? Should perhaps do this in fold proper. However, doing it
> there requires that we create a new CALL_EXPR, and that requires
> copying EH region info to the new node. Easier to just do it
> @@ -3017,19 +3014,11 @@ fold_gimple_call (gimple_stmt_iterator *
> /* ??? Is there a good reason not to do this in fold_stmt_inplace? */
> callee = gimple_call_fn (stmt);
> if (TREE_CODE (callee) == OBJ_TYPE_REF
> - && lang_hooks.fold_obj_type_ref
> - && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
> - && DECL_P (TREE_OPERAND
> - (OBJ_TYPE_REF_OBJECT (callee), 0)))
> + && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR)
> {
> tree t;
>
> - /* ??? Caution: Broken ADDR_EXPR semantics means that
> - looking at the type of the operand of the addr_expr
> - can yield an array type. See silly exception in
> - check_pointer_types_r. */
> - t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
> - t = lang_hooks.fold_obj_type_ref (callee, t);
> + t = gimple_fold_obj_type_ref (callee, NULL_TREE);
> if (t)
> {
> gimple_call_set_fn (stmt, t);
> Index: icln/gcc/gimple.h
> ===================================================================
> --- icln.orig/gcc/gimple.h
> +++ icln/gcc/gimple.h
> @@ -864,7 +864,9 @@ unsigned get_gimple_rhs_num_ops (enum tr
> #define gimple_alloc(c, n) gimple_alloc_stat (c, n MEM_STAT_INFO)
> gimple gimple_alloc_stat (enum gimple_code, unsigned MEM_STAT_DECL);
> const char *gimple_decl_printable_name (tree, int);
> +tree gimple_get_relevant_ref_binfo (tree ref, tree known_binfo);
> tree gimple_fold_obj_type_ref (tree, tree);
> +tree gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT, tree);
>
> /* Returns true iff T is a valid GIMPLE statement. */
> extern bool is_gimple_stmt (tree);
> Index: icln/gcc/testsuite/g++.dg/otr-fold-1.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/otr-fold-1.C
> @@ -0,0 +1,77 @@
> +/* Verify that simple virtual calls are inlined even without early
> + inlining, even when a typecast to an ancestor is involved along the
> + way. */
> +/* { dg-do run } */
> +/* { dg-options "-O -fdump-tree-optimized-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 Distraction, public A
> +{
> +public:
> + virtual int foo (int i);
> +};
> +
> +float Distraction::bar (float z)
> +{
> + f += z;
> + return f/2;
> +}
> +
> +int A::foo (int i)
> +{
> + return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> + return i + 2;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> + return 1;
> +}
> +
> +static int middleman_1 (class A *obj, int i)
> +{
> + return obj->foo (i);
> +}
> +
> +static 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 "= B::foo" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
>
More information about the Gcc-patches
mailing list