On Wed, Jun 1, 2011 at 5:07 PM, Michael Matz <[email protected]> wrote:
> Hi,
>
> On Wed, 1 Jun 2011, Michael Matz wrote:
>
>> Hi,
>>
>> so here's something more of my patch queue. It adds the facility to merge
>> also other trees than types over compilation unit borders. This specific
>> patch only deals with STRING_CST and INTEGER_CST nodes. Originally I used
>> that place for merging declarations, hence the naming of some variables.
>> That needs to wait for adjustments of the cgraph/varpool streamer.
>>
>> On building cc1 the overall numbers of trees that stay around after all
>> global sections are streamed in goes down from 620818 to 598843 trees,
>> overall saving 1 MB (out of 76 MB for just the trees). Not much, but
>> hey...
>>
>> Regstrapping on x86_64-linux in progress. Okay for trunk?
Ok.
Thanks,
Richard.
> Ahem.
>
> * lto.c (top_decls): New hash table.
> (simple_tree_hash, simple_tree_eq, uniquify_top): New.
> (LTO_FIXUP_TREE): Call uniquify_top.
> (uniquify_nodes): Ditto.
> (read_cgraph_and_symbols): Allocate and destroy top_decls.
>
> Index: lto/lto.c
> ===================================================================
> *** lto/lto.c (revision 174524)
> --- lto/lto.c (working copy)
> *************** lto_read_in_decl_state (struct data_in *
> *** 231,236 ****
> --- 231,316 ----
> that must be replaced with their prevailing variant. */
> static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node))) htab_t
> tree_with_vars;
> + /* A hashtable of top-level trees that can potentially be merged with trees
> + from other compilation units. */
> + static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node))) htab_t
> + top_decls;
> +
> + /* Given a tree in ITEM, return a hash value designed to easily recognize
> + equal trees. */
> + static hashval_t
> + simple_tree_hash (const void *item)
> + {
> + tree t = CONST_CAST_TREE ((const_tree) item);
> + enum tree_code code = TREE_CODE (t);
> + hashval_t hashcode = 0;
> + hashcode = iterative_hash_object (code, hashcode);
> + if (TREE_CODE (t) == STRING_CST)
> + {
> + if (TREE_TYPE (t))
> + hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (t)),
> hashcode);
> + hashcode = iterative_hash_hashval_t ((hashval_t)TREE_STRING_LENGTH
> (t),
> + hashcode);
> + hashcode = iterative_hash (TREE_STRING_POINTER (t),
> + TREE_STRING_LENGTH (t), hashcode);
> + return hashcode;
> + }
> + gcc_unreachable ();
> + }
> +
> + /* Given two trees in VA and VB return true if both trees can be considered
> + equal for easy merging across different compilation units. */
> + static int
> + simple_tree_eq (const void *va, const void *vb)
> + {
> + tree a = CONST_CAST_TREE ((const_tree) va);
> + tree b = CONST_CAST_TREE ((const_tree) vb);
> + if (a == b)
> + return 1;
> + if (TREE_CODE (a) != TREE_CODE (b))
> + return 0;
> + if (TREE_CODE (a) == STRING_CST)
> + {
> + return TREE_TYPE (a) == TREE_TYPE (b)
> + && TREE_STRING_LENGTH (a) == TREE_STRING_LENGTH (b)
> + && !memcmp (TREE_STRING_POINTER (a), TREE_STRING_POINTER (b),
> + TREE_STRING_LENGTH (a));
> + }
> + gcc_unreachable ();
> + }
> +
> + /* Given a tree T return its canonical variant, considering merging
> + of equal trees across different compilation units. */
> + static tree
> + uniquify_top (tree t)
> + {
> + switch (TREE_CODE (t))
> + {
> + case INTEGER_CST:
> + {
> + tree newtype = gimple_register_type (TREE_TYPE (t));
> + if (newtype != TREE_TYPE (t))
> + t = build_int_cst_wide (newtype, TREE_INT_CST_LOW (t),
> + TREE_INT_CST_HIGH (t));
> + }
> + break;
> + case STRING_CST:
> + {
> + tree *t2;
> + if (TREE_TYPE (t))
> + TREE_TYPE (t) = gimple_register_type (TREE_TYPE (t));
> + t2 = (tree *) htab_find_slot (top_decls, t, INSERT);
> + if (*t2)
> + t = *t2;
> + else
> + *t2 = t;
> + }
> + break;
> + default:
> + break;
> + }
> + return t;
> + }
>
> /* Remember that T is a tree that (potentially) refers to a variable
> or function decl that may be replaced with its prevailing variant. */
> *************** remember_with_vars (tree t)
> *** 247,252 ****
> --- 327,334 ----
> { \
> if (TYPE_P (tt)) \
> (tt) = gimple_register_type (tt); \
> + else\
> + (tt) = uniquify_top (tt); \
> if (VAR_OR_FUNCTION_DECL_P (tt) && TREE_PUBLIC (tt)) \
> remember_with_vars (t); \
> } \
> *************** lto_fixup_types (tree t)
> *** 504,510 ****
> /* Given a streamer cache structure DATA_IN (holding a sequence of trees
> for one compilation unit) go over all trees starting at index FROM until
> the
> end of the sequence and replace fields of those trees, and the trees
> ! themself with their canonical variants as per gimple_register_type. */
>
> static void
> uniquify_nodes (struct data_in *data_in, unsigned from)
> --- 586,593 ----
> /* Given a streamer cache structure DATA_IN (holding a sequence of trees
> for one compilation unit) go over all trees starting at index FROM until
> the
> end of the sequence and replace fields of those trees, and the trees
> ! themself with their canonical variants as per gimple_register_type and
> ! uniquify_top. */
>
> static void
> uniquify_nodes (struct data_in *data_in, unsigned from)
> *************** uniquify_nodes (struct data_in *data_in,
> *** 522,529 ****
> for (i = len; i-- > from;)
> {
> tree t = VEC_index (tree, cache->nodes, i);
> ! if (!t
> ! || !TYPE_P (t))
> continue;
>
> gimple_register_type (t);
> --- 605,611 ----
> for (i = len; i-- > from;)
> {
> tree t = VEC_index (tree, cache->nodes, i);
> ! if (!t || !TYPE_P (t))
> continue;
>
> gimple_register_type (t);
> *************** uniquify_nodes (struct data_in *data_in,
> *** 540,552 ****
> /* First fixup the fields of T. */
> lto_fixup_types (t);
>
> ! if (!TYPE_P (t))
> ! continue;
> !
> ! /* Now try to find a canonical variant of T itself. */
> ! t = gimple_register_type (t);
>
> ! if (t == oldt)
> {
> /* The following re-creates proper variant lists while fixing up
> the variant leaders. We do not stream TYPE_NEXT_VARIANT so the
> --- 622,634 ----
> /* First fixup the fields of T. */
> lto_fixup_types (t);
>
> ! if (TYPE_P (t))
> ! /* Now try to find a canonical variant of T itself. */
> ! t = gimple_register_type (t);
> ! else
> ! t = uniquify_top (t);
>
> ! if (t == oldt && TYPE_P (t))
> {
> /* The following re-creates proper variant lists while fixing up
> the variant leaders. We do not stream TYPE_NEXT_VARIANT so the
> *************** uniquify_nodes (struct data_in *data_in,
> *** 609,619 ****
> TYPE_REFERENCE_TO (TREE_TYPE (t)) = t;
> }
> }
> -
> else
> {
> if (RECORD_OR_UNION_TYPE_P (t))
> {
> tree f1, f2;
> if (TYPE_FIELDS (t) != TYPE_FIELDS (oldt))
> for (f1 = TYPE_FIELDS (t), f2 = TYPE_FIELDS (oldt);
> --- 691,705 ----
> TYPE_REFERENCE_TO (TREE_TYPE (t)) = t;
> }
> }
> else
> {
> if (RECORD_OR_UNION_TYPE_P (t))
> {
> + /* We could record FIELD_DECLs either in top_decls,
> + and uniquify them in uniquify_top, or we can simply replace
> + all FIELD_DECLs in one go if we found an already registered
> + type. The latter is faster and doesn't waste space in the
> + hash table. */
> tree f1, f2;
> if (TYPE_FIELDS (t) != TYPE_FIELDS (oldt))
> for (f1 = TYPE_FIELDS (t), f2 = TYPE_FIELDS (oldt);
> *************** uniquify_nodes (struct data_in *data_in,
> *** 656,663 ****
> for (i = len; i-- > from;)
> {
> tree t = VEC_index (tree, cache->nodes, i);
> ! if (!t
> ! || !TYPE_P (t))
> continue;
>
> if (!TYPE_CANONICAL (t))
> --- 742,748 ----
> for (i = len; i-- > from;)
> {
> tree t = VEC_index (tree, cache->nodes, i);
> ! if (!t || !TYPE_P (t))
> continue;
>
> if (!TYPE_CANONICAL (t))
> *************** read_cgraph_and_symbols (unsigned nfiles
> *** 2301,2306 ****
> --- 2386,2392 ----
> gcc_assert (num_objects == nfiles);
> }
>
> + top_decls = htab_create_ggc (101, simple_tree_hash, simple_tree_eq, NULL);
> tree_with_vars = htab_create_ggc (101, htab_hash_pointer, htab_eq_pointer,
> NULL);
>
> *************** read_cgraph_and_symbols (unsigned nfiles
> *** 2340,2345 ****
> --- 2426,2433 ----
> lto_stats.num_input_files = count;
> ggc_free(decl_data);
> real_file_decl_data = NULL;
> + htab_delete (top_decls);
> + top_decls = NULL;
>
> if (resolution_file_name)
> fclose (resolution);
>
