It is not necessary to maintain the pointer-map from cache entry to
cache index when reading trees. A quick estimate using the latest
WPA stats from firefox estimates its size to at least 1.5GB - apart
from the cost to maintain it. So the following patch makes it
possible to not maintain that map.
LTO bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2013-06-18 Richard Biener <rguent...@suse.de>
* tree-streamer.h (streamer_tree_cache_create): Adjust prototype.
* tree-streamer.c (streamer_tree_cache_create): Make maintaining
the map from cache entry to cache index optional.
(streamer_tree_cache_replace_tree): Adjust accordingly.
(streamer_tree_cache_append): Likewise.
(streamer_tree_cache_delete): Likewise.
* lto-streamer-in.c (lto_data_in_create): Do not maintain the
streamer cache map from cache entry to cache index.
* lto-streamer-out.c (create_output_block): Adjust.
lto/
* lto.c (lto_register_var_decl_in_symtab): Pass in cache index
and use it.
(lto_register_function_decl_in_symtab): Likewise.
(cmp_tree): New function.
(unify_scc): Instead of using the streamer cache map from entry
to cache index match up the two maps we have by sorting them.
Adjust calls to lto_register_var_decl_in_symtab and
lto_register_function_decl_in_symtab.
Index: gcc/tree-streamer.c
===================================================================
*** gcc/tree-streamer.c.orig 2013-06-18 13:00:34.000000000 +0200
--- gcc/tree-streamer.c 2013-06-18 13:00:46.042791385 +0200
*************** streamer_tree_cache_replace_tree (struct
*** 197,203 ****
hashval_t hash = 0;
if (cache->hashes.exists ())
hash = streamer_tree_cache_get_hash (cache, ix);
! streamer_tree_cache_insert_1 (cache, t, hash, &ix, false);
}
--- 197,206 ----
hashval_t hash = 0;
if (cache->hashes.exists ())
hash = streamer_tree_cache_get_hash (cache, ix);
! if (!cache->node_map)
! streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
! else
! streamer_tree_cache_insert_1 (cache, t, hash, &ix, false);
}
*************** streamer_tree_cache_append (struct strea
*** 208,214 ****
tree t, hashval_t hash)
{
unsigned ix = cache->nodes.length ();
! streamer_tree_cache_insert_1 (cache, t, hash, &ix, false);
}
/* Return true if tree node T exists in CACHE, otherwise false. If IX_P is
--- 211,220 ----
tree t, hashval_t hash)
{
unsigned ix = cache->nodes.length ();
! if (!cache->node_map)
! streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
! else
! streamer_tree_cache_insert_1 (cache, t, hash, &ix, false);
}
/* Return true if tree node T exists in CACHE, otherwise false. If IX_P is
*************** preload_common_nodes (struct streamer_tr
*** 319,331 ****
/* Create a cache of pickled nodes. */
struct streamer_tree_cache_d *
! streamer_tree_cache_create (bool with_hashes)
{
struct streamer_tree_cache_d *cache;
cache = XCNEW (struct streamer_tree_cache_d);
! cache->node_map = pointer_map_create ();
cache->nodes.create (165);
if (with_hashes)
cache->hashes.create (165);
--- 325,338 ----
/* Create a cache of pickled nodes. */
struct streamer_tree_cache_d *
! streamer_tree_cache_create (bool with_hashes, bool with_map)
{
struct streamer_tree_cache_d *cache;
cache = XCNEW (struct streamer_tree_cache_d);
! if (with_map)
! cache->node_map = pointer_map_create ();
cache->nodes.create (165);
if (with_hashes)
cache->hashes.create (165);
*************** streamer_tree_cache_delete (struct strea
*** 347,353 ****
if (c == NULL)
return;
! pointer_map_destroy (c->node_map);
c->nodes.release ();
c->hashes.release ();
free (c);
--- 354,361 ----
if (c == NULL)
return;
! if (c->node_map)
! pointer_map_destroy (c->node_map);
c->nodes.release ();
c->hashes.release ();
free (c);
Index: gcc/tree-streamer.h
===================================================================
*** gcc/tree-streamer.h.orig 2013-06-18 13:00:34.000000000 +0200
--- gcc/tree-streamer.h 2013-06-18 13:00:46.061791614 +0200
*************** void streamer_tree_cache_append (struct
*** 98,104 ****
hashval_t);
bool streamer_tree_cache_lookup (struct streamer_tree_cache_d *, tree,
unsigned *);
! struct streamer_tree_cache_d *streamer_tree_cache_create (bool);
void streamer_tree_cache_delete (struct streamer_tree_cache_d *);
/* Return the tree node at slot IX in CACHE. */
--- 98,104 ----
hashval_t);
bool streamer_tree_cache_lookup (struct streamer_tree_cache_d *, tree,
unsigned *);
! struct streamer_tree_cache_d *streamer_tree_cache_create (bool, bool);
void streamer_tree_cache_delete (struct streamer_tree_cache_d *);
/* Return the tree node at slot IX in CACHE. */
Index: gcc/lto-streamer-in.c
===================================================================
*** gcc/lto-streamer-in.c.orig 2013-06-18 13:00:34.000000000 +0200
--- gcc/lto-streamer-in.c 2013-06-18 13:00:46.062791626 +0200
*************** lto_data_in_create (struct lto_file_decl
*** 1305,1311 ****
data_in->strings = strings;
data_in->strings_len = len;
data_in->globals_resolution = resolutions;
! data_in->reader_cache = streamer_tree_cache_create (false);
return data_in;
}
--- 1305,1311 ----
data_in->strings = strings;
data_in->strings_len = len;
data_in->globals_resolution = resolutions;
! data_in->reader_cache = streamer_tree_cache_create (false, false);
return data_in;
}
Index: gcc/lto-streamer-out.c
===================================================================
*** gcc/lto-streamer-out.c.orig 2013-06-18 13:00:34.000000000 +0200
--- gcc/lto-streamer-out.c 2013-06-18 13:00:46.062791626 +0200
*************** create_output_block (enum lto_section_ty
*** 71,77 ****
ob->decl_state = lto_get_out_decl_state ();
ob->main_stream = XCNEW (struct lto_output_stream);
ob->string_stream = XCNEW (struct lto_output_stream);
! ob->writer_cache = streamer_tree_cache_create (!flag_wpa);
if (section_type == LTO_section_function_body)
ob->cfg_stream = XCNEW (struct lto_output_stream);
--- 71,77 ----
ob->decl_state = lto_get_out_decl_state ();
ob->main_stream = XCNEW (struct lto_output_stream);
ob->string_stream = XCNEW (struct lto_output_stream);
! ob->writer_cache = streamer_tree_cache_create (!flag_wpa, true);
if (section_type == LTO_section_function_body)
ob->cfg_stream = XCNEW (struct lto_output_stream);
Index: gcc/lto/lto.c
===================================================================
*** gcc/lto/lto.c.orig 2013-06-18 13:00:34.000000000 +0200
--- gcc/lto/lto.c 2013-06-18 13:07:57.105986871 +0200
*************** register_resolution (struct lto_file_dec
*** 1608,1614 ****
different files. */
static void
! lto_register_var_decl_in_symtab (struct data_in *data_in, tree decl)
{
tree context;
--- 1608,1615 ----
different files. */
static void
! lto_register_var_decl_in_symtab (struct data_in *data_in, tree decl,
! unsigned ix)
{
tree context;
*************** lto_register_var_decl_in_symtab (struct
*** 1616,1634 ****
if (!TREE_PUBLIC (decl)
&& !((context = decl_function_context (decl))
&& auto_var_in_fn_p (decl, context)))
! {
! rest_of_decl_compilation (decl, 1, 0);
! }
/* If this variable has already been declared, queue the
declaration for merging. */
if (TREE_PUBLIC (decl))
! {
! unsigned ix;
! if (!streamer_tree_cache_lookup (data_in->reader_cache, decl, &ix))
! gcc_unreachable ();
! register_resolution (data_in->file_data, decl, get_resolution (data_in,
ix));
! }
}
--- 1617,1629 ----
if (!TREE_PUBLIC (decl)
&& !((context = decl_function_context (decl))
&& auto_var_in_fn_p (decl, context)))
! rest_of_decl_compilation (decl, 1, 0);
/* If this variable has already been declared, queue the
declaration for merging. */
if (TREE_PUBLIC (decl))
! register_resolution (data_in->file_data,
! decl, get_resolution (data_in, ix));
}
*************** lto_register_var_decl_in_symtab (struct
*** 1638,1654 ****
file being read. */
static void
! lto_register_function_decl_in_symtab (struct data_in *data_in, tree decl)
{
/* If this variable has already been declared, queue the
declaration for merging. */
if (TREE_PUBLIC (decl) && !DECL_ABSTRACT (decl))
! {
! unsigned ix;
! if (!streamer_tree_cache_lookup (data_in->reader_cache, decl, &ix))
! gcc_unreachable ();
! register_resolution (data_in->file_data, decl, get_resolution (data_in,
ix));
! }
}
--- 1633,1646 ----
file being read. */
static void
! lto_register_function_decl_in_symtab (struct data_in *data_in, tree decl,
! unsigned ix)
{
/* If this variable has already been declared, queue the
declaration for merging. */
if (TREE_PUBLIC (decl) && !DECL_ABSTRACT (decl))
! register_resolution (data_in->file_data,
! decl, get_resolution (data_in, ix));
}
*************** compare_tree_sccs (tree_scc *pscc, tree_
*** 2259,2264 ****
--- 2251,2269 ----
return false;
}
+ /* QSort sort function to sort a map of two pointers after the 2nd
+ pointer. */
+
+ static int
+ cmp_tree (const void *p1_, const void *p2_)
+ {
+ tree *p1 = (tree *)(const_cast<void *>(p1_));
+ tree *p2 = (tree *)(const_cast<void *>(p2_));
+ if (p1[1] == p2[1])
+ return 0;
+ return ((uintptr_t)p1[1] < (uintptr_t)p2[1]) ? -1 : 1;
+ }
+
/* Try to unify the SCC with nodes FROM to FROM + LEN in CACHE and
hash value SCC_HASH with an already recorded SCC. Return true if
that was successful, otherwise return false. */
*************** unify_scc (struct streamer_tree_cache_d
*** 2323,2351 ****
num_sccs_merged++;
total_scc_size_merged += len;
! /* Fixup the streamer cache with the prevailing nodes according
! to the tree node mapping computed by compare_tree_sccs. */
for (unsigned i = 0; i < len; ++i)
{
tree t = map[2*i+1];
enum tree_code code = TREE_CODE (t);
- unsigned ix;
- bool r;
/* IDENTIFIER_NODEs should be singletons and are merged by the
streamer. The others should be singletons, too, and we
should not merge them in any way. */
gcc_assert (code != TRANSLATION_UNIT_DECL
&& code != IDENTIFIER_NODE
&& !streamer_handle_as_builtin_p (t));
- r = streamer_tree_cache_lookup (cache, t, &ix);
- gcc_assert (r && ix >= from);
- streamer_tree_cache_replace_tree (cache, map[2 * i], ix);
- if (TYPE_P (t))
- num_merged_types++;
}
/* Free the tree nodes from the read SCC. */
for (unsigned i = 0; i < len; ++i)
! ggc_free (scc->entries[i]);
break;
}
--- 2328,2374 ----
num_sccs_merged++;
total_scc_size_merged += len;
! #ifdef ENABLE_CHECKING
for (unsigned i = 0; i < len; ++i)
{
tree t = map[2*i+1];
enum tree_code code = TREE_CODE (t);
/* IDENTIFIER_NODEs should be singletons and are merged by the
streamer. The others should be singletons, too, and we
should not merge them in any way. */
gcc_assert (code != TRANSLATION_UNIT_DECL
&& code != IDENTIFIER_NODE
&& !streamer_handle_as_builtin_p (t));
}
+ #endif
+
+ /* Fixup the streamer cache with the prevailing nodes according
+ to the tree node mapping computed by compare_tree_sccs. */
+ if (len == 1)
+ streamer_tree_cache_replace_tree (cache, pscc->entries[0], from);
+ else
+ {
+ tree *map2 = XALLOCAVEC (tree, 2 * len);
+ for (unsigned i = 0; i < len; ++i)
+ {
+ map2[i*2] = (tree)(uintptr_t)(from + i);
+ map2[i*2+1] = scc->entries[i];
+ }
+ qsort (map2, len, 2 * sizeof (tree), cmp_tree);
+ qsort (map, len, 2 * sizeof (tree), cmp_tree);
+ for (unsigned i = 0; i < len; ++i)
+ streamer_tree_cache_replace_tree (cache, map[2*i],
+ (uintptr_t)map2[2*i]);
+ }
+
/* Free the tree nodes from the read SCC. */
for (unsigned i = 0; i < len; ++i)
! {
! if (TYPE_P (scc->entries[i]))
! num_merged_types++;
! ggc_free (scc->entries[i]);
! }
!
break;
}
*************** lto_read_decls (struct lto_file_decl_dat
*** 2493,2502 ****
/* Register variables and functions with the
symbol table. */
if (TREE_CODE (t) == VAR_DECL)
! lto_register_var_decl_in_symtab (data_in, t);
else if (TREE_CODE (t) == FUNCTION_DECL
&& !DECL_BUILT_IN (t))
! lto_register_function_decl_in_symtab (data_in, t);
/* Scan the tree for references to global functions or
variables and record those for later fixup. */
maybe_remember_with_vars (t);
--- 2516,2525 ----
/* Register variables and functions with the
symbol table. */
if (TREE_CODE (t) == VAR_DECL)
! lto_register_var_decl_in_symtab (data_in, t, from + i);
else if (TREE_CODE (t) == FUNCTION_DECL
&& !DECL_BUILT_IN (t))
! lto_register_function_decl_in_symtab (data_in, t, from + i);
/* Scan the tree for references to global functions or
variables and record those for later fixup. */
maybe_remember_with_vars (t);
