[pph] Fix chain merging (issue5264044)
Diego Novillo
dnovillo@google.com
Fri Oct 14 16:13:00 GMT 2011
So, I had not fixed c1limits-externalid.cc. I had simply messed up
merging decls into chains.
The problem here is that we insert decls into a chain *before* we
finish reading them. So, when pph_merge_into_chain inserts the
partially read DECL into the chain (or returns an existing DECL), the
call to pph_in_tree_body proceeds to clobber DECL_CHAIN with whatever
value it had when we had generated that PPH file.
I tried not streaming DECL_CHAINs at all, but we chain decls outside
of "chain" contexts, so that breaks things too. I've added some
documentation on that in the code.
What I ended up doing is saving the value of DECL_CHAIN after
insertion and restoring it if pph_in_tree_body clobbered it.
c1limits-externalid.cc is timing out because we are doing this N^2
search/insert with 100,000 symbols. I've got some ideas on how to fix
that. I'll be trying that next.
Tested on x86_64. Committed to branch.
* pph-streamer-in.c (pph_in_mergeable_tree): Remove. Update all users.
(pph_in_chain_1): Rename from pph_in_chain.
Add argument CHAIN.
(pph_in_chain): Call pph_in_chain_1.
(pph_in_mergeable_chain): Likewise.
(pph_in_tcc_declaration): Add documentation on why reading
DECL_CHAIN is necessary.
(pph_in_tree_1): Prevent getting DECL_CHAIN clobbered after
merging into CHAIN.
* pph-streamer-out.c (pph_out_tree_vec_1): Add argument UNCHAIN.
Update all users.
(pph_out_tcc_declaration): Add documentation on why writing
DECL_CHAIN is necessary
testsuite/ChangeLog.pph:
* testsuite/g++.dg/pph/c1limits-externalid.cc: Restore timeout.
diff --git a/gcc/cp/pph-streamer-in.c b/gcc/cp/pph-streamer-in.c
index 5cdf4d5..23a28bf 100644
--- a/gcc/cp/pph-streamer-in.c
+++ b/gcc/cp/pph-streamer-in.c
@@ -524,15 +524,6 @@ pph_in_tree (pph_stream *stream)
}
-/* Load an AST into CHAIN from STREAM. */
-
-static void
-pph_in_mergeable_tree (pph_stream *stream, tree *chain)
-{
- pph_in_tree_1 (stream, chain);
-}
-
-
/********************************************************** lexical elements */
@@ -711,13 +702,29 @@ pph_in_tree_pair_vec (pph_stream *stream)
/******************************************************************** chains */
-/* Read a chain of ASTs from STREAM. */
+/* Read a chain of ASTs from STREAM. If CHAIN is set, the ASTs are
+ incorporated at the head of *CHAIN as they are read. */
+
static tree
-pph_in_chain (pph_stream *stream)
+pph_in_chain_1 (pph_stream *stream, tree *chain)
{
- tree t = streamer_read_chain (stream->encoder.r.ib,
+ HOST_WIDE_INT i, count;
+
+ if (chain == NULL)
+ return streamer_read_chain (stream->encoder.r.ib,
stream->encoder.r.data_in);
- return t;
+
+ count = pph_in_hwi (stream);
+ for (i = 0; i < count; i++)
+ pph_in_tree_1 (stream, chain);
+
+ return *chain;
+}
+
+static tree
+pph_in_chain (pph_stream *stream)
+{
+ return pph_in_chain_1 (stream, NULL);
}
@@ -726,11 +733,7 @@ pph_in_chain (pph_stream *stream)
static void
pph_in_mergeable_chain (pph_stream *stream, tree *chain)
{
- int i, count;
-
- count = pph_in_hwi (stream);
- for (i = 0; i < count; i++)
- pph_in_mergeable_tree (stream, chain);
+ pph_in_chain_1 (stream, chain);
}
@@ -816,7 +819,7 @@ pph_match_to_link (tree expr, location_t where, const char *idstr, tree *link)
static tree
pph_search_in_chain (tree expr, location_t where, const char *idstr,
- tree *chain)
+ tree *chain)
{
/* FIXME pph: This could resultin O(POW(n,2)) compilation. */
tree *link = chain;
@@ -869,6 +872,7 @@ pph_merge_into_chain (pph_stream *stream, tree expr, tree *chain)
if (flag_pph_debug >= 3)
fprintf (pph_logfile, "PPH: %s FOUND on chain\n", idstr);
+
return found;
}
@@ -1629,8 +1633,11 @@ pph_in_tcc_declaration (pph_stream *stream, tree decl)
pph_in_lang_specific (stream, decl);
DECL_INITIAL (decl) = pph_in_tree (stream);
- /* The tree streamer only writes DECL_CHAIN for PARM_DECL nodes. */
- /* FIXME pph: almost redundant. */
+ /* The tree streamer only writes DECL_CHAIN for PARM_DECL nodes.
+ We need to read DECL_CHAIN for variables and functions because
+ they are sometimes chained together in places other than regular
+ tree chains. For example in BINFO_VTABLEs, the decls are chained
+ together). */
if (TREE_CODE (decl) == VAR_DECL
|| TREE_CODE (decl) == FUNCTION_DECL)
DECL_CHAIN (decl) = pph_in_tree (stream);
@@ -1934,6 +1941,7 @@ pph_in_tree_1 (pph_stream *stream, tree *chain)
enum pph_record_marker marker;
unsigned image_ix, ix;
enum LTO_tags tag;
+ tree saved_expr_chain = NULL;
/* Read record start and test cache. */
marker = pph_in_start_record (stream, &image_ix, &ix, PPH_any_tree);
@@ -1967,9 +1975,20 @@ pph_in_tree_1 (pph_stream *stream, tree *chain)
/* Materialize a new node from STREAM. This will also read all the
language-independent bitfields for the new tree. */
expr = read = pph_in_tree_header (stream, tag);
- gcc_assert (read != NULL);
+
+ /* If we were told to insert the tree into a CHAIN, look for a
+ match in CHAIN to EXPR's header. If we find a match, EXPR
+ will be the tree that we want to return. */
if (chain)
- expr = pph_merge_into_chain (stream, expr, chain);
+ {
+ expr = pph_merge_into_chain (stream, expr, chain);
+
+ /* Save TREE_CHAIN for EXPR because it will be clobbered by
+ the call to pph_in_tree_body below. Given that EXPR may
+ now be in a different location in the chain, we need to
+ make sure we do not lose it. */
+ saved_expr_chain = TREE_CHAIN (expr);
+ }
gcc_assert (expr != NULL);
}
@@ -1994,6 +2013,12 @@ pph_in_tree_1 (pph_stream *stream, tree *chain)
pph_cache_insert_at (&stream->cache, expr, ix, pph_tree_code_to_tag (expr));
pph_in_tree_body (stream, expr);
+ /* If EXPR had been recovered from an existing chain, the TREE_CHAIN
+ that we read from STREAM will be different than the chain
+ location we inserted it when we merged it in. Recover it. */
+ if (chain && saved_expr_chain != TREE_CHAIN (expr))
+ TREE_CHAIN (expr) = saved_expr_chain;
+
if (flag_pph_tracer)
pph_trace_tree (expr, chain != NULL);
diff --git a/gcc/cp/pph-streamer-out.c b/gcc/cp/pph-streamer-out.c
index d534b42..c5d6f04 100644
--- a/gcc/cp/pph-streamer-out.c
+++ b/gcc/cp/pph-streamer-out.c
@@ -807,11 +807,14 @@ vec2vec_filter (pph_stream *stream, VEC(tree,gc) *v, unsigned filter)
/* Write all the trees in VEC V to STREAM. REVERSE is true if V should
be written in reverse. MERGEABLE is true if the tree nodes in V
are mergeable trees (see pph_out_tree_1). If FILTER is set,
- only emit the elements in V that match it. */
+ only emit the elements in V that match it. If UNCHAIN is true,
+ clear TREE_CHAIN on every element written out (this is to support
+ writing chains, as they are supposed to be re-chained by the
+ reader). */
static void
pph_out_tree_vec_1 (pph_stream *stream, VEC(tree,gc) *v, unsigned filter,
- bool mergeable, bool reverse)
+ bool mergeable, bool reverse, bool unchain)
{
unsigned i;
tree t;
@@ -831,10 +834,30 @@ pph_out_tree_vec_1 (pph_stream *stream, VEC(tree,gc) *v, unsigned filter,
if (!reverse)
FOR_EACH_VEC_ELT (tree, to_write, i, t)
- pph_out_tree_1 (stream, t, mergeable);
+ {
+ tree prev = NULL;
+ if (unchain)
+ {
+ prev = TREE_CHAIN (t);
+ TREE_CHAIN (t) = NULL;
+ }
+ pph_out_tree_1 (stream, t, mergeable);
+ if (unchain)
+ TREE_CHAIN (t) = prev;
+ }
else
FOR_EACH_VEC_ELT_REVERSE (tree, to_write, i, t)
- pph_out_tree_1 (stream, t, mergeable);
+ {
+ tree prev = NULL;
+ if (unchain)
+ {
+ prev = TREE_CHAIN (t);
+ TREE_CHAIN (t) = NULL;
+ }
+ pph_out_tree_1 (stream, t, mergeable);
+ if (unchain)
+ TREE_CHAIN (t) = prev;
+ }
/* If we did not have to filter, TO_WRITE == V. Do not free it! */
if (filter != PPHF_NONE)
@@ -847,7 +870,7 @@ pph_out_tree_vec_1 (pph_stream *stream, VEC(tree,gc) *v, unsigned filter,
static void
pph_out_tree_vec (pph_stream *stream, VEC(tree,gc) *v)
{
- pph_out_tree_vec_1 (stream, v, PPHF_NONE, false, false);
+ pph_out_tree_vec_1 (stream, v, PPHF_NONE, false, false, false);
}
@@ -856,7 +879,7 @@ pph_out_tree_vec (pph_stream *stream, VEC(tree,gc) *v)
static void
pph_out_tree_vec_filtered (pph_stream *stream, VEC(tree,gc) *v, unsigned filter)
{
- pph_out_tree_vec_1 (stream, v, filter, false, false);
+ pph_out_tree_vec_1 (stream, v, filter, false, false, false);
}
@@ -937,7 +960,7 @@ pph_out_chain_1 (pph_stream *stream, tree first, unsigned filter,
apply it again. */
vec = chain2vec_filter (stream, first, filter);
pph_out_tree_vec_1 (stream, (VEC(tree,gc) *)vec, reverse, mergeable,
- PPHF_NONE);
+ PPHF_NONE, true);
}
@@ -1580,8 +1603,11 @@ pph_out_tcc_declaration (pph_stream *stream, tree decl)
pph_out_lang_specific (stream, decl);
pph_out_tree (stream, DECL_INITIAL (decl));
- /* The tree streamer only writes DECL_CHAIN for PARM_DECL nodes. */
- /* FIXME pph: almost redundant. */
+ /* The tree streamer only writes DECL_CHAIN for PARM_DECL nodes.
+ We need to write DECL_CHAIN for variables and functions because
+ they are sometimes chained together in places other than regular
+ tree chains. For example in BINFO_VTABLEs, the decls are chained
+ together). */
if (TREE_CODE (decl) == VAR_DECL
|| TREE_CODE (decl) == FUNCTION_DECL)
pph_out_tree (stream, DECL_CHAIN (decl));
diff --git a/gcc/testsuite/g++.dg/pph/c1limits-externalid.cc b/gcc/testsuite/g++.dg/pph/c1limits-externalid.cc
index b10f1c1..8dc6b8a 100644
--- a/gcc/testsuite/g++.dg/pph/c1limits-externalid.cc
+++ b/gcc/testsuite/g++.dg/pph/c1limits-externalid.cc
@@ -1 +1,8 @@
+/* { dg-timeout 15 } */
+/* { dg-xfail-if "BOGUS MERGE HUGE SYMBOL LIST" { *-*-* } { "-fpph-map=pph.map" } } */
+/* FIXME pph - The following timeout may cause failures on slow targets.
+ In general it takes no longer than a couple of seconds to compile
+ this test, but the new merging code is having trouble with this.
+ Probably due to an O(n^2) merging algorithm. */
+
#include "c0limits-externalid.h"
--
This patch is available for review at http://codereview.appspot.com/5264044
More information about the Gcc-patches
mailing list