[pph] Fix chain merging

[Diego Novillo, 2011-10-14 15:44:46]

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