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 3/6] Folding of virtual calls


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" } } */
>
>


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