Re: Make gimple_get_virt_method_for_vtable O(1) and not allocating garbage

[Richard Biener <rguenther at suse dot de>]

On Thu, 6 Feb 2014, Jan Hubicka wrote:

> Hi,
> I did some memory measurements for Firefox.  We seems in shape in exception of
> linemaps that takes about 20% of memory and I also noticed that we produce a lot
> of garbage by copy_tree_r.  Analyzing the reasons for copy_tree_r I found two about
> equally important.  The first one is that gimple_get_virt_method_for_vtable lookup
> virtual method via fold_ctor_reference and this eventually calls unshare_expr on
> the resulting value (that is ADDR_EXPR of FUNCTION_DECL). We make copy of ADDR_EXPR
> and immediately throw it away in gimple_get_virt_method_for_vtable and care
> only about the decl.
> 
> I always considered it stupid to do linear walk of fields here, when we can do
> just simple O(1) lookup, but considered it SEP.  This patch implements that.
> The constructors are fully controlled by frontend (we verify that it is vtable
> by DECL_VIRTUAL flag first), so I think it is safe to use special purpose lookup
> code.
> 
> Bootstrapped/regtested x86_64-linux, OK?

Ok.

Thanks,
Richard.

> Honza
> 
> 	* gimple-fold.c (gimple_get_virt_method_for_vtable): Rewrite
> 	constructor lookup to be O(1).
> Index: gimple-fold.c
> ===================================================================
> --- gimple-fold.c	(revision 207523)
> +++ gimple-fold.c	(working copy)
> @@ -3179,6 +3180,8 @@ gimple_get_virt_method_for_vtable (HOST_
>  {
>    tree vtable = v, init, fn;
>    unsigned HOST_WIDE_INT size;
> +  unsigned HOST_WIDE_INT elt_size, access_index;
> +  tree domain_type;
>  
>    /* First of all double check we have virtual table.  */
>    if (TREE_CODE (v) != VAR_DECL
> @@ -3202,10 +3205,30 @@ gimple_get_virt_method_for_vtable (HOST_
>    offset *= BITS_PER_UNIT;
>    offset += token * size;
>  
> -  /* Do not pass from_decl here, we want to know even about values we can
> -     not use and will check can_refer_decl_in_current_unit_p ourselves.  */
> -  fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), init,
> -			    offset, size, NULL);
> +  /* Lookup the value in the constructor that is assumed to be array.
> +     This is equivalent to
> +     fn = fold_ctor_reference (TREE_TYPE (TREE_TYPE (v)), init,
> +			       offset, size, NULL);
> +     but in a constant time.  We expect that frontend produced a simple
> +     array without indexed initializers.  */
> +
> +  gcc_checking_assert (TREE_CODE (TREE_TYPE (init)) == ARRAY_TYPE);
> +  domain_type = TYPE_DOMAIN (TREE_TYPE (init));
> +  gcc_checking_assert (integer_zerop (TYPE_MIN_VALUE (domain_type)));
> +  elt_size = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (init))));
> +
> +  access_index = offset / BITS_PER_UNIT / elt_size;
> +  gcc_checking_assert (offset % (elt_size * BITS_PER_UNIT) == 0);
> +
> +  /* This code makes an assumption that there are no 
> +     indexed fileds produced by C++ FE, so we can directly index the array. */
> +  if (access_index < CONSTRUCTOR_NELTS (init))
> +    {
> +      fn = CONSTRUCTOR_ELT (init, access_index)->value;
> +      gcc_checking_assert (!CONSTRUCTOR_ELT (init, access_index)->index);
> +    }
> +  else
> +    fn = NULL;
>  
>    /* For type inconsistent program we may end up looking up virtual method
>       in virtual table that does not contain TOKEN entries.  We may overrun
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer