[pph] Re-organize handling of mergeable nodes

[Diego Novillo, 2011-10-21 02:57:15]

This patch re-organizes the streaming of mergeable nodes so that we
can separate the process of merging the incoming ASTs into the current
compilation context from the reading of their contents.

This problem occurs when two or more PPH images in the same
compilation unit have embedded the same text header file.  For
example, in the following scenario files "image1.h" and "image2.h" can
be converted into PPH images, while "text.h" is a regular header
inclusion:

tu.cc:
	#include "image1.h"
	#include "image2.h"

image1.h
	#ifndef __IMAGE1_H
	#define __IMAGE1_H
	#include "text.h"
	...
	#endif

image2.h
	#ifndef __IMAGE2_H
	#define __IMAGE2_H
	#include "text.h"
	...
	#endif


Since the ASTs generated by text.h are embedded inside both image1.pph
and image2.pph.  When we read those file, we will read the same
symbols.  To avoid multiple definition errors, we need to merge the
symbols coming from these file.

This is not the usual merge done by the parser, however.  In here we
are merging full definitions, callgraph nodes, types, etc.

What the patch does is to break the writing of a tree into two pieces.
The first piece is the merge key, which is necessary for allocation
and used as a lookup key into the parser data structures to determine
if that object has already been seen by the parser. The second piece
is the merge body, which carries the bulk of the information,
particularly any information that causes circularity.

The serialization algorithm occurs in two phases. The first phase
walks the data structure emitting only merge keys for all mergeable
trees. The second phase walks the data structure emitting only bodies
for all mergeable trees. Non-mergeable trees will be emitted in whole
as a side effect of the second phase.

The de-serialization algorithm follows the same two phases. The first
phase reads the tree merge keys, searches for merge matches, and
either allocates a new tree or redirects references to an existing
tree. The second phase reads the tree merge bodies. When the body
corresponds to a matched tree, it must incorporate new information
into the existing tree, i.e. do merging. For example, a function
definition could come from the first pph file read, or the second pph
file read, but in either case the definition must reside in the final
data structures.

We are still not doing proper merging of everything.  This patch
simply implements the mechanics of splitting up the streaming of
mergeable nodes.  We will be working on the actual merge logic on top
of this change.

Tested on x86_64.  Committed to branch.


Diego.


	* pph-streamer-in.c (ALLOC_AND_REGISTER_ALTERNATE): Remove.
 	(pph_in_tree_1): Remove.
 	(pph_in_tree): Rename from pph_in_tree_1.
 	(pph_in_chain): Call streamer_read_chain.
 	(pph_in_merge_key_chain): New.
 	(pph_in_merge_body_chain): Rename from pph_in_mergeable_chain.
 	(pph_in_binding_level_1): Switch the order of the arguments.
 	Update all users.
 	Read fields this_entity and static_decls.
 	(pph_in_mergeable_binding_level): Remove.
 	(pph_in_merge_key_tree): New.
 	(pph_in_tree): Handle PPH_RECORD_START_MERGE_BODY.
 	(pph_in_merge_keys): New.
 	(pph_in_global_binding): New.
 	(pph_read_file_1): Call it.
 	* pph-streamer-out.c (pph_get_marker_for):
 	(pph_out_start_tree_record): Handle PPH_RECORD_START_MERGE_BODY.
 	(pph_out_start_merge_key_record): New.
 	(pph_out_tree_1): Remove.
 	(pph_out_tree): Rename from pph_out_tree_1.
 	Handle PPH_RECORD_START_MERGE_BODY.
 	(pph_out_merge_key_vec): Rename from pph_out_mergeable_tree_vec.
 	Call pph_out_merge_key_tree.
 	(pph_out_merge_key_chain): Rename from pph_out_mergeable_chain_filtered.
 	(pph_out_binding_level_1): Handle fields this_entity and static_decls.
 	(pph_out_mergeable_binding_level): Remove.
 	(pph_out_merge_key_tree): New.
 	(pph_out_merge_keys): New.
 	(pph_out_global_binding): Call pph_out_merge_keys.
 	* pph-streamer.c (pph_cache_insert_at): Return the inserted entry.
 	Update all users.
 	(pph_cache_add): Likewise.
 	(pph_cache_lookup): Return the found entry.  Update all users.
 	(pph_cache_lookup_in_includes): Likewise.
 	(pph_merge_name): Ignore EXPRs with no lang-specific info.
 	* pph-streamer.h (pph_cache_entry): Add field needs_merge_body.
 	Update all users.
 	(pph_tag_to_tree_code): Remove.
 	(pph_tree_is_mergeable): New.
 	* pph.h (enum pph_record_marker): Add values PPH_RECORD_START_MERGE_KEY
 	and PPH_RECORD_START_MERGE_BODY.

diff --git a/gcc/cp/pph-streamer-in.c b/gcc/cp/pph-streamer-in.c
index d8f17b9..ecb7182 100644
--- a/gcc/cp/pph-streamer-in.c
+++ b/gcc/cp/pph-streamer-in.c
@@ -58,20 +58,6 @@ static VEC(char_p,heap) *string_tables = NULL;
       pph_cache_insert_at (CACHE, DATA, IX, TAG);		\
     } while (0)
 
-/* FIXME pph: Unneeded macro.  */
-/* Same as ALLOC_AND_REGISTER, but instead of registering DATA into the
-   cache at slot IX, it registers ALT_DATA.  Used to support mapping
-   pointers to global data in the original CACHE that need to point
-   to a different instance when aggregating individual PPH files into
-   the current translation unit (see pph_in_binding_level for an
-   example).  */
-#define ALLOC_AND_REGISTER_ALTERNATE(CACHE, IX, TAG, DATA, ALLOC_EXPR,  \
-                                     ALT_DATA)                  \
-    do {							\
-      (DATA) = (ALLOC_EXPR);					\
-      pph_cache_insert_at (CACHE, ALT_DATA, IX, TAG);		\
-    } while (0)
-
 /* Set in pph_in_and_merge_line_table. Represents the source_location offset
    which every streamed in token must add to it's serialized source_location.
 
@@ -80,6 +66,8 @@ static VEC(char_p,heap) *string_tables = NULL;
    */
 static int pph_loc_offset;
 
+/* Forward declarations to avoid circularity.  */
+static tree pph_in_merge_key_tree (pph_stream *, tree *);
 
 /***************************************************** stream initialization */
 
@@ -433,6 +421,8 @@ pph_in_record_marker (pph_stream *stream, enum pph_tag
*tag_p)
   gcc_assert (m == PPH_RECORD_START
               || m == PPH_RECORD_START_NO_CACHE
               || m == PPH_RECORD_START_MUTATED
+	      || m == PPH_RECORD_START_MERGE_KEY
+	      || m == PPH_RECORD_START_MERGE_BODY
               || m == PPH_RECORD_END
               || m == PPH_RECORD_IREF
               || m == PPH_RECORD_XREF
@@ -493,7 +483,9 @@ pph_in_start_record (pph_stream *stream, unsigned
*include_ix_p,
      Also read the preloaded cache slot in IX for PPH_RECORD_PREF.  */
   if (marker == PPH_RECORD_START
       || marker == PPH_RECORD_IREF
-      || marker == PPH_RECORD_PREF)
+      || marker == PPH_RECORD_PREF
+      || marker == PPH_RECORD_START_MERGE_BODY
+      || marker == PPH_RECORD_START_MERGE_KEY)
     *cache_ix_p = pph_in_uint (stream);
   else if (marker == PPH_RECORD_XREF
            || marker == PPH_RECORD_START_MUTATED)
@@ -510,22 +502,6 @@ pph_in_start_record (pph_stream *stream, unsigned
*include_ix_p,
 }
 
 
-/*************************************************************** tree shells */
-
-
-/* The core tree reader is defined much later.  */
-static tree pph_in_tree_1 (pph_stream *stream, tree *chain);
-
-
-/* Load a non-mergeable AST from STREAM.  Return the corresponding tree.  */
-
-tree
-pph_in_tree (pph_stream *stream)
-{
-  return pph_in_tree_1 (stream, NULL);
-}
-
-
 /********************************************************** lexical elements */
 
 
@@ -704,38 +680,41 @@ pph_in_tree_pair_vec (pph_stream *stream)
 /******************************************************************** chains */
 
 
-/* Read a chain of ASTs from STREAM.  If CHAIN is set, the ASTs are
-   incorporated at the head of *CHAIN as they are read.  */
+/* Read a chain of ASTs from STREAM.  */
 
 static tree
-pph_in_chain_1 (pph_stream *stream, tree *chain)
+pph_in_chain (pph_stream *stream)
 {
-  HOST_WIDE_INT i, count;
+  return streamer_read_chain (stream->encoder.r.ib, stream->encoder.r.data_in);
+}
 
-  if (chain == NULL)
-    return streamer_read_chain (stream->encoder.r.ib,
-                                stream->encoder.r.data_in);
 
-  count = pph_in_hwi (stream);
-  for (i = 0; i < count; i++)
-    pph_in_tree_1 (stream, chain);
-
-  return *chain;
-}
+/* Read a chain of AST merge keys from STREAM.  Merge each tree
+   into *CHAIN.  */
 
-static tree
-pph_in_chain (pph_stream *stream)
+static void
+pph_in_merge_key_chain (pph_stream *stream, tree *chain)
 {
-  return pph_in_chain_1 (stream, NULL);
+  unsigned i;
+  HOST_WIDE_INT count;
+
+  count = pph_in_hwi (stream);
+  for (i = 0; i < count; i++)
+    pph_in_merge_key_tree (stream, chain);
 }
 
 
-/* Read and merge a chain of ASTs from STREAM into an existing CHAIN.  */
+/* Read a chain of AST merge bodies from STREAM.  */
 
 static void
-pph_in_mergeable_chain (pph_stream *stream, tree *chain)
+pph_in_merge_body_chain (pph_stream *stream)
 {
-  pph_in_chain_1 (stream, chain);
+  unsigned i;
+  HOST_WIDE_INT count;
+
+  count = pph_in_hwi (stream);
+  for (i = 0; i < count; i++)
+    pph_in_tree (stream);
 }
 
 
@@ -842,7 +821,7 @@ pph_search_in_chain (tree expr, location_t where, const char
*idstr,
 }
 
 
-/* Prepend an tree EXPR to a CHAIN.  */
+/* Prepend a tree EXPR to a CHAIN.  */
 
 static tree
 pph_prepend_to_chain (tree expr, tree *chain)
@@ -890,7 +869,6 @@ pph_merge_into_chain (pph_stream *stream, tree expr, tree
*chain)
 
 /* Forward declaration to break cyclic dependencies.  */
 static cp_binding_level *pph_in_binding_level (pph_stream *);
-static void pph_in_mergeable_binding_level (cp_binding_level *, pph_stream *);
 
 /* Helper for pph_in_cxx_binding.  Read and return a cxx_binding
    instance from STREAM.  */
@@ -995,15 +973,17 @@ pph_in_label_binding (pph_stream *stream)
 }
 
 
-/* Help read binding level BL.
-   FIXME pph: Much of this may be wrong for mergeable bindings.  */
+/* Read the contents of binding level BL from STREAM.  */
 
 static void
-pph_in_binding_level_1 (cp_binding_level *bl, pph_stream *stream)
+pph_in_binding_level_1 (pph_stream *stream, cp_binding_level *bl)
 {
   unsigned i, num;
   struct bitpack_d bp;
 
+  bl->this_entity = pph_in_tree (stream);
+  bl->static_decls = pph_in_tree_vec (stream);
+
   num = pph_in_uint (stream);
   bl->class_shadowed = NULL;
   for (i = 0; i < num; i++)
@@ -1058,54 +1038,18 @@ pph_in_binding_level (pph_stream *stream)
     }
 
   ALLOC_AND_REGISTER (&stream->cache, ix, PPH_cp_binding_level, bl,
-			ggc_alloc_cleared_cp_binding_level ());
+		      ggc_alloc_cleared_cp_binding_level ());
 
-  bl->this_entity = pph_in_tree (stream);
   bl->names = pph_in_chain (stream);
   bl->namespaces = pph_in_chain (stream);
   bl->usings = pph_in_chain (stream);
   bl->using_directives = pph_in_chain (stream);
-  bl->static_decls = pph_in_tree_vec (stream);
-  pph_in_binding_level_1 (bl, stream);
+  pph_in_binding_level_1 (stream, bl);
 
   return bl;
 }
 
 
-/* Read an instance of cp_binding_level from STREAM and merge into EXISTING.
-   The existing specifies the binding level to register in the cache
-   in place of allocating a binding.  */
-
-static void
-pph_in_mergeable_binding_level (cp_binding_level *existing, pph_stream *stream)
-{
-  unsigned image_ix, ix;
-  enum pph_record_marker marker;
-  tree entity;
-
-  marker = pph_in_start_record (stream, &image_ix, &ix, PPH_cp_binding_level);
-  gcc_assert (marker != PPH_RECORD_END && !pph_is_reference_marker (marker));
-  pph_cache_insert_at (&stream->cache, existing, ix, PPH_cp_binding_level);
-
-  entity = pph_in_tree (stream);
-  gcc_assert (entity == existing->this_entity);
-  if (flag_pph_debug >= 3)
-    {
-      fprintf (pph_logfile, "PPH: Merging into this chain:\n");
-      pph_dump_chain (pph_logfile, existing->names);
-      fprintf (pph_logfile, "\n");
-    }
-  pph_in_mergeable_chain (stream, &existing->names);
-  pph_in_mergeable_chain (stream, &existing->namespaces);
-  pph_in_mergeable_chain (stream, &existing->usings);
-  pph_in_mergeable_chain (stream, &existing->using_directives);
-  /* FIXME pph: We should really be merging the static_decls.  */
-  existing->static_decls = pph_in_tree_vec (stream);
-  /* FIXME pph: Note the suspect overwriting in the next call.  */
-  pph_in_binding_level_1 (existing, stream);
-}
-
-
 /********************************************************** tree aux classes */
 
 
@@ -1951,15 +1895,50 @@ pph_in_tree_header (pph_stream *stream, enum LTO_tags
tag)
 }
 
 
-/* Read a tree from the STREAM.  If CHAIN is not NULL, the tree may be
-   unified with an existing tree in that chain.  */
+/* Read a merge key from STREAM.  If the merge key read from
+   STREAM is not found in *CHAIN, the newly allocated tree is added to
+   it.  */
 
 static tree
-pph_in_tree_1 (pph_stream *stream, tree *chain)
+pph_in_merge_key_tree (pph_stream *stream, tree *chain)
+{
+  struct lto_input_block *ib = stream->encoder.r.ib;
+  enum pph_record_marker marker;
+  unsigned image_ix, ix;
+  tree read_expr, expr;
+  enum LTO_tags tag;
+
+  marker = pph_in_start_record (stream, &image_ix, &ix, PPH_any_tree);
+  gcc_assert (marker == PPH_RECORD_START_MERGE_KEY);
+  tag = streamer_read_record_start (ib);
+
+  /* Materialize a new node from STREAM.  This will also read all the
+     language-independent bitfields for the new tree.  */
+  read_expr = pph_in_tree_header (stream, tag);
+
+  /* Look for a match in CHAIN to READ_EXPR's header.  If we found a
+     match, EXPR will be the existing tree that matches READ_EXPR.
+     Otherwise, EXPR is the newly allocated READ_EXPR.  */
+  expr = pph_merge_into_chain (stream, read_expr, chain);
+
+  gcc_assert (expr != NULL);
+
+  pph_cache_insert_at (&stream->cache, expr, ix, pph_tree_code_to_tag (expr));
+
+  if (flag_pph_tracer)
+    pph_trace_tree (expr, true, expr != read_expr);
+
+  return expr;
+}
+
+
+/* Read and return a tree from STREAM.  */
+
+tree
+pph_in_tree (pph_stream *stream)
 {
   struct lto_input_block *ib = stream->encoder.r.ib;
   struct data_in *data_in = stream->encoder.r.data_in;
-  tree read = NULL;
   tree expr = NULL;
   enum pph_record_marker marker;
   unsigned image_ix, ix;
@@ -1997,26 +1976,12 @@ 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);
-
-      /* 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);
-
-	  /* 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);
+      expr = pph_in_tree_header (stream, tag);
     }
 
   gcc_assert (marker == PPH_RECORD_START
-              || marker == PPH_RECORD_START_MUTATED);
+              || marker == PPH_RECORD_START_MUTATED
+	      || marker == PPH_RECORD_START_MERGE_BODY);
 
   if (marker == PPH_RECORD_START_MUTATED)
     {
@@ -2029,21 +1994,39 @@ pph_in_tree_1 (pph_stream *stream, tree *chain)
       /* Read the internal cache slot where EXPR should be stored at.  */
       ix = pph_in_uint (stream);
     }
+  else if (marker == PPH_RECORD_START_MERGE_BODY)
+    {
+      /* When reading a merge body, the tree has already been allocated
+	 and added to STREAM's cache.  All we have to do now is read
+	 its body.  FIXME pph, this read should be a merging read; we are
+	 overwriting EXPR's fields now.  */
+      expr = (tree) pph_cache_get (&stream->cache, ix);
+    }
+
+  /* Add the new tree to the cache and read its body.  The tree is
+     added to the cache before we read its body to handle circular
+     references and references from children nodes.  If we are reading
+     a merge body, then the tree is already in the cache (it was added
+     by pph_in_merge_key_tree).  */
+  if (marker != PPH_RECORD_START_MERGE_BODY)
+    pph_cache_insert_at (&stream->cache, expr, ix, pph_tree_code_to_tag
(expr));
+
+  /* If we are reading a merge body, it means that EXPR is already in
+     some chain.  Given that EXPR may now be in a different location
+     in the chain, we need to make sure we do not lose it.  */
+  if (marker == PPH_RECORD_START_MERGE_BODY)
+    saved_expr_chain = TREE_CHAIN (expr);
 
-  /* Add the new tree to the cache and read its body.  The tree
-     is added to the cache before we read its body to handle
-     circular references and references from children nodes.  */
-  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))
+  /* Restore TREE_CHAIN if necessary.  FIXME pph, we should just not
+     save TREE_CHAIN for merge bodies.  */
+  if (marker == PPH_RECORD_START_MERGE_BODY)
     TREE_CHAIN (expr) = saved_expr_chain;
 
+
   if (flag_pph_tracer)
-    pph_trace_tree (expr, chain != NULL, expr != read);
+    pph_trace_tree (expr, false, false);
 
   /* If needed, sign the recently materialized tree to detect
      mutations.  Note that we only need to compute signatures
@@ -2349,6 +2332,72 @@ pph_in_identifiers (pph_stream *stream, cpp_idents_used
*identifiers)
 }
 
 
+/* Read all the merge keys from STREAM.  Merge into the corresponding
+   contexts.  Return a VEC of all the merge keys read.  */
+
+static void
+pph_in_merge_keys (pph_stream *stream)
+{
+  cp_binding_level *bl = scope_chain->bindings;
+
+  /* First read all the merge keys and merge into the global bindings.  */
+  pph_in_merge_key_chain (stream, &bl->names);
+  pph_in_merge_key_chain (stream, &bl->namespaces);
+  pph_in_merge_key_chain (stream, &bl->usings);
+  pph_in_merge_key_chain (stream, &bl->using_directives);
+
+  /* Now read the bodies of all the trees merged above.  */
+  pph_in_merge_body_chain (stream);
+  pph_in_merge_body_chain (stream);
+  pph_in_merge_body_chain (stream);
+  pph_in_merge_body_chain (stream);
+}
+
+
+/* Read global bindings from STREAM into scope_chain->bindings.  Note
+   that this does not call pph_in_binding_level because that would
+   overwrite the fields merged by pph_in_merge_keys.  */
+
+static void
+pph_in_global_binding (pph_stream *stream)
+{
+  unsigned image_ix, ix;
+  enum pph_record_marker marker;
+  cp_binding_level *bl;
+
+  bl = scope_chain->bindings;
+  marker = pph_in_start_record (stream, &image_ix, &ix, PPH_cp_binding_level);
+  gcc_assert (marker != PPH_RECORD_END);
+
+  if (pph_is_reference_marker (marker))
+    {
+      /* If we found a reference to BL, it should be the same.  This happens
+	 when we pull BL from a nested PPH image.  */
+      cp_binding_level *other_bl;
+      other_bl = (cp_binding_level *) pph_cache_find (stream, marker, image_ix,
+						      ix, PPH_cp_binding_level);
+      gcc_assert (other_bl == bl);
+    }
+  else
+    {
+      /* Note that here we do not allocate a new binding level.  Since we
+	 are reading into the global one, we register the current
+	 scope_chain->bindings into the cache.  Otherwise, we would be
+	 associating these symbols into the global binding level from
+	 STREAM, instead of the current translation unit.  */
+      pph_cache_insert_at (&stream->cache, bl, ix, PPH_cp_binding_level);
+    }
+
+  /* Read the merge keys and merge them into the current compilation
+     context.  Since we have registered scope_chain->bindings in the
+     same slot IX that the writer used, the trees read now will be
+     bound to scope_chain->bindings.  */
+  pph_in_merge_keys (stream);
+
+  pph_in_binding_level_1 (stream, bl);
+}
+
+
 /* Helper for pph_read_file.  Read contents of PPH file in STREAM.  */
 
 static void
@@ -2393,8 +2442,8 @@ pph_read_file_1 (pph_stream *stream)
      working towards an identical line_table in pph and non-pph.  */
   cpp_lt_replay (parse_in, &idents_used, &cpp_token_replay_loc);
 
-  /* Read the bindings from STREAM and merge them with the current bindings. 
*/
-  pph_in_mergeable_binding_level (scope_chain->bindings, stream);
+  /* Read the bindings from STREAM.  */
+  pph_in_global_binding (stream);
 
   /* Read and merge the other global state collected during parsing of
      the original header.  */
diff --git a/gcc/cp/pph-streamer-out.c b/gcc/cp/pph-streamer-out.c
index 6570b13..32cf96c 100644
--- a/gcc/cp/pph-streamer-out.c
+++ b/gcc/cp/pph-streamer-out.c
@@ -40,6 +40,8 @@ along with GCC; see the file COPYING3.  If not see
    cp_rest_of_decl_compilation).  */
 static pph_stream *pph_out_stream = NULL;
 
+/* Forward declarations to avoid circular references.  */
+static void pph_out_merge_key_tree (pph_stream *, tree);
 
 /***************************************************** stream initialization */
 
@@ -558,10 +560,24 @@ pph_out_start_tree_record (pph_stream *stream, tree t)
         marker = PPH_RECORD_START_MUTATED;
     }
 
+  /* If we are about to write an internal reference for a mergeable
+     tree, it means that we have already written the merge key for it.
+     Check whether we still need to write its merge body.  If so,
+     MARKER should be PPH_RECORD_START_MERGE_BODY.  */
+  if (marker == PPH_RECORD_IREF && pph_tree_is_mergeable (t))
+    {
+      pph_cache_entry *e = pph_cache_get_entry (&stream->cache, ix);
+      if (e->needs_merge_body)
+	{
+	  marker = PPH_RECORD_START_MERGE_BODY;
+	  e->needs_merge_body = false;
+	}
+    }
+
   /* Write a record header according to the value of MARKER.  */
   if (marker == PPH_RECORD_END || pph_is_reference_marker (marker))
     pph_out_reference_record (stream, marker, include_ix, ix, tag);
-  else if (marker == PPH_RECORD_START)
+  else if (marker == PPH_RECORD_START || marker == PPH_RECORD_START_MERGE_BODY)
     {
       /* We want to prevent some trees from hitting the cache.
          For example, we do not want to cache regular constants (as
@@ -573,7 +589,7 @@ pph_out_start_tree_record (pph_stream *stream, tree t)
         marker = PPH_RECORD_START_NO_CACHE;
 
       pph_out_record_marker (stream, marker, tag);
-      if (marker == PPH_RECORD_START)
+      if (marker == PPH_RECORD_START || marker == PPH_RECORD_START_MERGE_BODY)
         {
           unsigned ix;
           pph_cache_add (&stream->cache, t, &ix, tag);
@@ -610,27 +626,37 @@ pph_out_start_tree_record (pph_stream *stream, tree t)
          internal cache.  */
       pph_out_uint (stream, internal_ix);
     }
+  else
+    gcc_unreachable ();
 
   return marker;
 }
 
 
-/*************************************************************** tree shells */
-
+/* Start a merge key record for EXPR on STREAM.  */
 
-/* The core tree writer is defined much later.  */
-static void pph_out_tree_1 (pph_stream *stream, tree t, bool mergeable);
+static void
+pph_out_start_merge_key_record (pph_stream *stream, tree expr)
+{
+  enum pph_tag tag;
+  enum pph_record_marker marker;
+  pph_cache_entry *e;
+  unsigned ix;
 
+  tag = pph_tree_code_to_tag (expr);
+  marker = pph_get_marker_for (stream, expr, NULL, NULL, tag);
 
-/* Output non-mergeable tree T to STREAM.  */
+  /* This should be the first time that we try to write EXPR.  */
+  gcc_assert (marker == PPH_RECORD_START);
 
-void
-pph_out_tree (pph_stream *stream, tree t)
-{
-  pph_out_tree_1 (stream, t, false);
+  pph_out_record_marker (stream, PPH_RECORD_START_MERGE_KEY, tag);
+  e = pph_cache_add (&stream->cache, expr, &ix, tag);
+  e->needs_merge_body = true;
+  pph_out_uint (stream, ix);
 }
 
 
+
 /********************************************************** lexical elements */
 
 
@@ -839,23 +865,17 @@ pph_out_tree_vec_unchain (pph_stream *stream, VEC(tree,gc)
*v)
 }
 
 
-/* Write all the mergeable trees in VEC V to STREAM.
-   The trees must go out in declaration order, i.e. reversed.
-   Unchain each before writing and rechain after writing.  */
+/* Write all the merge keys for trees in VEC V to STREAM.  The keys
+   must go out in declaration order, i.e. reversed.  */
 
 static void
-pph_out_mergeable_tree_vec (pph_stream *stream, VEC(tree,gc) *v)
+pph_out_merge_key_vec (pph_stream *stream, VEC(tree,gc) *v)
 {
   unsigned i;
   tree t;
   pph_out_hwi (stream, VEC_length (tree, v));
   FOR_EACH_VEC_ELT_REVERSE (tree, v, i, t)
-    {
-      tree prev = TREE_CHAIN (t);
-      TREE_CHAIN (t) = NULL;
-      pph_out_tree_1 (stream, t, /*mergeable=*/true);
-      TREE_CHAIN (t) = prev;
-    }
+    pph_out_merge_key_tree (stream, t);
 }
 
 
@@ -975,20 +995,19 @@ pph_out_chain_filtered (pph_stream *stream, tree first,
unsigned filter)
 }
 
 
-/* Write, in reverse, a chain of mergeable trees to STREAM starting
+/* Write, in reverse, a chain of merge keys to STREAM starting
    with the last element of CHAIN.  Only write the trees that match
    FILTER.  */
 
 static void
-pph_out_mergeable_chain_filtered (pph_stream *stream, tree chain,
-				  unsigned filter)
+pph_out_merge_key_chain (pph_stream *stream, tree chain, unsigned filter)
 {
   VEC(tree,heap) *w;
   if (filter == PPHF_NONE)
     w = chain2vec (chain);
   else
     w = chain2vec_filter (stream, chain, filter);
-  pph_out_mergeable_tree_vec (stream, (VEC(tree,gc) *)w);
+  pph_out_merge_key_vec (stream, (VEC(tree,gc) *)w);
   VEC_free (tree, heap, w);
 }
 
@@ -1067,9 +1086,8 @@ pph_out_label_binding (pph_stream *stream,
cp_label_binding *lb)
 }
 
 
-/* Helper for pph_out_binding_level and pph_out_mergeable_binding_level.
-   Write the fields of BL to STREAM that do not differ depending on mering.
-   Do not emit any nodes in BL that do not match FILTER.  */
+/* Helper for pph_out_binding_level.  Write the fields of BL to
+   STREAM.  Do not emit any nodes in BL that do not match FILTER.  */
 
 static void
 pph_out_binding_level_1 (pph_stream *stream, cp_binding_level *bl,
@@ -1080,6 +1098,10 @@ pph_out_binding_level_1 (pph_stream *stream,
cp_binding_level *bl,
   cp_label_binding *sl;
   struct bitpack_d bp;
 
+  pph_out_tree (stream, bl->this_entity);
+
+  pph_out_tree_vec_filtered (stream, bl->static_decls, filter);
+
   pph_out_uint (stream, VEC_length (cp_class_binding, bl->class_shadowed));
   FOR_EACH_VEC_ELT (cp_class_binding, bl->class_shadowed, i, cs)
     pph_out_class_binding (stream, cs);
@@ -1112,50 +1134,13 @@ static void
 pph_out_binding_level (pph_stream *stream, cp_binding_level *bl,
 		       unsigned filter)
 {
-  unsigned aux_filter;
-  tree entity;
-
   if (pph_out_start_record (stream, bl, PPH_cp_binding_level))
     return;
 
-  aux_filter = PPHF_NO_BUILTINS | filter;
-  entity = bl->this_entity;
-  pph_out_tree (stream, entity);
-
-  pph_out_chain_filtered (stream, bl->names, aux_filter);
-  pph_out_chain_filtered (stream, bl->namespaces, aux_filter);
-  pph_out_chain_filtered (stream, bl->usings, aux_filter);
-  pph_out_chain_filtered (stream, bl->using_directives, aux_filter);
-  pph_out_tree_vec_filtered (stream, bl->static_decls, filter);
-  pph_out_binding_level_1 (stream, bl, filter);
-}
-
-
-/* Helper for pph_out_binding_level.  Write the fields of BL to STREAM
-   for the non-merging case.
-   Do not emit any nodes in BL that do not match FILTER.  */
-
-static void
-pph_out_mergeable_binding_level (pph_stream *stream, cp_binding_level *bl,
-		         unsigned filter)
-{
-  unsigned aux_filter, ix;
-  tree entity;
-
-  pph_cache_add (&stream->cache, scope_chain->bindings, &ix,
-                 PPH_cp_binding_level);
-  pph_out_record_marker (stream, PPH_RECORD_START, PPH_cp_binding_level);
-  pph_out_uint (stream, ix);
-
-  aux_filter = PPHF_NO_BUILTINS | filter;
-  entity = bl->this_entity;
-  pph_out_tree (stream, entity);
-
-  pph_out_mergeable_chain_filtered (stream, bl->names, aux_filter);
-  pph_out_mergeable_chain_filtered (stream, bl->namespaces, aux_filter);
-  pph_out_mergeable_chain_filtered (stream, bl->usings, aux_filter);
-  pph_out_mergeable_chain_filtered (stream, bl->using_directives, aux_filter);
-  pph_out_tree_vec_filtered (stream, bl->static_decls, filter);
+  pph_out_chain_filtered (stream, bl->names, filter);
+  pph_out_chain_filtered (stream, bl->namespaces, filter);
+  pph_out_chain_filtered (stream, bl->usings, filter);
+  pph_out_chain_filtered (stream, bl->using_directives, filter);
   pph_out_binding_level_1 (stream, bl, filter);
 }
 
@@ -1928,10 +1913,31 @@ pph_out_merge_name (pph_stream *stream, tree expr)
 }
 
 
-/* Write a tree EXPR (MERGEABLE or not) to STREAM.  */
+/* Write the merge key for tree EXPR to STREAM.  */
 
 static void
-pph_out_tree_1 (pph_stream *stream, tree expr, bool mergeable)
+pph_out_merge_key_tree (pph_stream *stream, tree expr)
+{
+  gcc_assert (pph_tree_is_mergeable (expr));
+
+  pph_out_start_merge_key_record (stream, expr);
+
+  if (flag_pph_tracer)
+    pph_trace_tree (expr, true, false);
+
+  /* Write merge key information.  This includes EXPR's header (needed
+     to re-allocate EXPR in the reader) and the merge key, used to
+     lookup EXPR in the reader's context and merge if necessary.  */
+  pph_out_tree_header (stream, expr);
+  pph_out_location (stream, DECL_SOURCE_LOCATION (expr));
+  pph_out_merge_name (stream, expr);
+}
+
+
+/* Write a tree EXPR to STREAM.  */
+
+void
+pph_out_tree (pph_stream *stream, tree expr)
 {
   enum pph_record_marker marker;
 
@@ -1963,7 +1969,7 @@ pph_out_tree_1 (pph_stream *stream, tree expr, bool
mergeable)
   else if (marker == PPH_RECORD_START || marker == PPH_RECORD_START_MUTATED)
     {
       if (flag_pph_tracer)
-	pph_trace_tree (expr, mergeable, false);
+	pph_trace_tree (expr, false, false);
 
       /* This is the first time we see EXPR, write it out.  */
       if (marker == PPH_RECORD_START)
@@ -1973,16 +1979,22 @@ pph_out_tree_1 (pph_stream *stream, tree expr, bool
mergeable)
              state of an existing tree, then we only need to write its
              body.  */
           pph_out_tree_header (stream, expr);
-          if (mergeable && DECL_P (expr))
-            {
-              /* We may need to unify two declarations.  */
-              pph_out_location (stream, DECL_SOURCE_LOCATION (expr));
-              pph_out_merge_name (stream, expr);
-            }
         }
 
       pph_out_tree_body (stream, expr);
     }
+  else if (marker == PPH_RECORD_START_MERGE_BODY)
+    {
+      gcc_assert (pph_tree_is_mergeable (expr));
+
+      if (flag_pph_tracer)
+	pph_trace_tree (expr, true, false);
+
+      /* When writing a merge body, we do not need to write EXPR's
+	 header, since that was written out when we wrote the merge
+	 key record for it.  */
+      pph_out_tree_body (stream, expr);
+    }
   else
     gcc_unreachable ();
 }
@@ -2185,13 +2197,40 @@ pph_out_identifiers (pph_stream *stream, cpp_idents_used
*identifiers)
 }
 
 
+/* Write an index of mergeable objects to STREAM.  */
+
+static void
+pph_out_merge_keys (pph_stream *stream)
+{
+  cp_binding_level *bl = scope_chain->bindings;
+  unsigned filter = PPHF_NO_XREFS | PPHF_NO_PREFS | PPHF_NO_BUILTINS;
+
+  /* First emit all the merge keys.  */
+  pph_out_merge_key_chain (stream, bl->names, filter);
+  pph_out_merge_key_chain (stream, bl->namespaces, filter);
+  pph_out_merge_key_chain (stream, bl->usings, filter);
+  pph_out_merge_key_chain (stream, bl->using_directives, filter);
+
+  /* Now emit all the merge bodies.  */
+  pph_out_chain_filtered (stream, bl->names, filter);
+  pph_out_chain_filtered (stream, bl->namespaces, filter);
+  pph_out_chain_filtered (stream, bl->usings, filter);
+  pph_out_chain_filtered (stream, bl->using_directives, filter);
+}
+
+
 /* Write the global bindings in scope_chain to STREAM.  */
 
 static void
 pph_out_global_binding (pph_stream *stream)
 {
-  /* old_namespace should be global_namespace and all entries listed below
-     should be NULL or 0; otherwise the header parsed was incomplete.  */
+  cp_binding_level *bl;
+
+  /* We only need to write out the scope_chain->bindings, everything
+     else should be NULL or be some temporary disposable state.
+     old_namespace should be global_namespace and all entries listed
+     below should be NULL or 0; otherwise the header parsed was
+     incomplete.  */
   gcc_assert (scope_chain->old_namespace == global_namespace
 	      && !(scope_chain->class_name
 		   || scope_chain->class_type
@@ -2210,18 +2249,18 @@ pph_out_global_binding (pph_stream *stream)
 		   || scope_chain->x_stmt_tree.x_cur_stmt_list
 		   || scope_chain->x_stmt_tree.stmts_are_full_exprs_p));
 
-  /* We only need to write out the bindings, everything else should
-     be NULL or be some temporary disposable state.
-
-     Note that we explicitly force the pickling of
-     scope_chain->bindings.  If we had previously read another PPH
-     image, scope_chain->bindings will be in the other image's pickle
-     cache.  This would cause pph_out_binding_level to emit a cache
-     reference to it, instead of writing its fields.  */
-  {
-    pph_out_mergeable_binding_level (stream, scope_chain->bindings,
-				     PPHF_NO_XREFS | PPHF_NO_PREFS);
-  }
+  /* We need to write a record for BL before emitting the merge keys
+     so that the reader can associate the merge keys to it.  */
+  bl = scope_chain->bindings;
+  pph_out_start_record (stream, bl, PPH_cp_binding_level);
+
+  /* Emit all the merge keys for objects that need to be merged when reading
+     multiple PPH images.  */
+  pph_out_merge_keys (stream);
+
+  /* Emit the other fields in BL that need no merging.  */
+  pph_out_binding_level_1 (stream, bl,
+			   PPHF_NO_XREFS | PPHF_NO_PREFS | PPHF_NO_BUILTINS);
 }
 
 
diff --git a/gcc/cp/pph-streamer.c b/gcc/cp/pph-streamer.c
index a79e519..8476717 100644
--- a/gcc/cp/pph-streamer.c
+++ b/gcc/cp/pph-streamer.c
@@ -361,14 +361,14 @@ pph_trace_tree (tree t, bool mergeable, bool merged)
 /* Insert DATA in CACHE at slot IX.  TAG represents the data structure
    pointed-to by DATA.  As a restriction to prevent stomping on cache
    entries, this will not allow inserting into the same slot more than
-   once.  */
+   once.  Return the newly added entry.  */
 
-void
+pph_cache_entry *
 pph_cache_insert_at (pph_cache *cache, void *data, unsigned ix,
                      enum pph_tag tag)
 {
   void **map_slot;
-  pph_cache_entry e = { data, tag, 0, 0 };
+  pph_cache_entry e = { data, tag, false, 0, 0 };
 
   map_slot = pointer_map_insert (cache->m, data);
 
@@ -379,23 +379,26 @@ pph_cache_insert_at (pph_cache *cache, void *data,
unsigned ix,
   if (ix + 1 > VEC_length (pph_cache_entry, cache->v))
     VEC_safe_grow_cleared (pph_cache_entry, heap, cache->v, ix + 1);
   VEC_replace (pph_cache_entry, cache->v, ix, &e);
+
+  return pph_cache_get_entry (cache, ix);
 }
 
 
-/* Return true if DATA exists in CACHE.  If IX_P is not NULL, store
-   the cache slot where DATA resides in *IX_P (or (unsigned)-1 if DATA
-   is not found). If CACHE is NULL use pph_preloaded_cache.
+/* If DATA exists in CACHE, return the cache entry holding it.  If
+   IX_P is not NULL, store the cache slot where DATA resides in *IX_P
+   (or (unsigned)-1 if DATA is not found). If CACHE is NULL use
+   pph_preloaded_cache.
 
    If a cache hit is found, the data type tag for the entry must match
    TAG.  */
 
-bool
+pph_cache_entry *
 pph_cache_lookup (pph_cache *cache, void *data, unsigned *ix_p,
                   enum pph_tag tag)
 {
   void **map_slot;
   unsigned ix;
-  bool existed_p;
+  pph_cache_entry *e;
 
   if (cache == NULL)
     cache = pph_preloaded_cache;
@@ -403,7 +406,7 @@ pph_cache_lookup (pph_cache *cache, void *data, unsigned
*ix_p,
   map_slot = pointer_map_contains (cache->m, data);
   if (map_slot == NULL)
     {
-      existed_p = false;
+      e = NULL;
       ix = (unsigned) -1;
     }
   else
@@ -411,21 +414,18 @@ pph_cache_lookup (pph_cache *cache, void *data, unsigned
*ix_p,
       intptr_t slot_ix = (intptr_t) *map_slot;
       gcc_assert (slot_ix == (intptr_t)(unsigned) slot_ix);
       ix = (unsigned) slot_ix;
-      existed_p = true;
+      e = pph_cache_get_entry (cache, ix);
 
-      /* If the caller is looking for a specific tag, make sure
+      /* If the caller is looking for a specific TAG, make sure
          it matches the tag we pulled from the cache.  */
       if (tag != PPH_null)
-        {
-          pph_cache_entry *e = pph_cache_get_entry (cache, ix);
-          gcc_assert (tag == e->tag);
-        }
+	gcc_assert (tag == e->tag);
     }
 
   if (ix_p)
     *ix_p = ix;
 
-  return existed_p;
+  return e;
 }
 
 
@@ -444,36 +444,37 @@ pph_cache_lookup (pph_cache *cache, void *data, unsigned
*ix_p,
       - *IX_P is set to -1 (if IX_P is not NULL), and,
       - the function returns false.  */
 
-bool
+pph_cache_entry *
 pph_cache_lookup_in_includes (pph_stream *stream, void *data,
 			      unsigned *include_ix_p, unsigned *ix_p,
 			      enum pph_tag tag)
 {
   unsigned include_ix, ix;
   pph_stream *include;
-  bool found_it;
+  pph_cache_entry *e;
 
   /* When searching the external caches, do not try to find a match
      for TAG.  Since this is an external cache, the parser may have
      re-allocated the object pointed by DATA (e.g., when merging
      decls).  In this case, TAG will be different from the tag we find
-     in the cache, so instead of ICEing, we ignore the match so the
-     caller is forced to pickle DATA.  */
-  found_it = false;
+     in the cache, so instead of ICEing, we ignore the match to force
+     the caller to pickle DATA.  */
+  e = NULL;
   FOR_EACH_VEC_ELT (pph_stream_ptr, stream->includes, include_ix, include)
-    if (pph_cache_lookup (&include->cache, data, &ix, PPH_null))
-      {
-        pph_cache_entry *e = pph_cache_get_entry (&include->cache, ix);
-
-        /* Only consider DATA found if its data type matches TAG.  If
-           not, it means that the object pointed by DATA has changed,
-           so DATA will need to be re-pickled.  */
-        if (e->tag == tag)
-          found_it = true;
-        break;
-      }
-
-  if (!found_it)
+    {
+      e = pph_cache_lookup (&include->cache, data, &ix, PPH_null);
+      if (e)
+	{
+	  /* Only consider DATA found if its data type matches TAG.  If
+	     not, it means that the object pointed by DATA has changed,
+	     so DATA will need to be re-pickled.  */
+	  if (e->tag != tag)
+	    e = NULL;
+	  break;
+	}
+    }
+
+  if (e == NULL)
     {
       include_ix = ix = (unsigned) -1;
       ix = (unsigned) -1;
@@ -485,33 +486,31 @@ pph_cache_lookup_in_includes (pph_stream *stream, void
*data,
   if (ix_p)
     *ix_p = ix;
 
-  return found_it;
+  return e;
 }
 
 
 /* Add pointer DATA with data type TAG to CACHE.  If IX_P is not NULL,
    on exit *IX_P will contain the slot number where DATA is stored.
-   Return true if DATA already existed in the CACHE, false otherwise.  */
+   Return the newly added entry.  */
 
-bool
+pph_cache_entry *
 pph_cache_add (pph_cache *cache, void *data, unsigned *ix_p, enum pph_tag tag)
 {
   unsigned ix;
-  bool existed_p;
+  pph_cache_entry *e;
 
-  if (pph_cache_lookup (cache, data, &ix, tag))
-    existed_p = true;
-  else
+  e = pph_cache_lookup (cache, data, &ix, tag);
+  if (e == NULL)
     {
-      existed_p = false;
       ix = VEC_length (pph_cache_entry, cache->v);
-      pph_cache_insert_at (cache, data, ix, tag);
+      e = pph_cache_insert_at (cache, data, ix, tag);
     }
 
   if (ix_p)
     *ix_p = ix;
 
-  return existed_p;
+  return e;
 }
 
 
@@ -579,7 +578,9 @@ pph_get_signature (tree t, size_t *nbytes_p)
 tree
 pph_merge_name (tree expr)
 {
-  if (TREE_CODE (expr) == FUNCTION_DECL && !DECL_BUILT_IN (expr))
+  if (TREE_CODE (expr) == FUNCTION_DECL
+      && !DECL_BUILT_IN (expr)
+      && DECL_LANG_SPECIFIC (expr))
     return DECL_ASSEMBLER_NAME (expr);
   else
     return DECL_NAME (expr);
diff --git a/gcc/cp/pph-streamer.h b/gcc/cp/pph-streamer.h
index eb4076d..61af2e6 100644
--- a/gcc/cp/pph-streamer.h
+++ b/gcc/cp/pph-streamer.h
@@ -89,6 +89,11 @@ typedef struct pph_cache_entry {
   /* Tag describing the type of the cached data.  */
   enum pph_tag tag;
 
+  /* Non-zero if this entry has been emitted as a merge key.  This means
+     that the next time this entry is written out, it should be written
+     as a merge body record (see pph_out_start_tree_record for details).  */
+  unsigned int needs_merge_body : 1;
+
   /* Checksum information for DATA.  */
   unsigned int crc;
 
@@ -232,11 +237,14 @@ void pph_mark_stream_read (pph_stream *);
 void pph_stream_close (pph_stream *);
 void pph_add_include (pph_stream *, pph_stream *);
 void pph_trace_tree (tree, bool, bool);
-void pph_cache_insert_at (pph_cache *, void *, unsigned, enum pph_tag);
-bool pph_cache_lookup (pph_cache *, void *, unsigned *, enum pph_tag);
-bool pph_cache_lookup_in_includes (pph_stream *, void *, unsigned *, unsigned
*,
-                                   enum pph_tag);
-bool pph_cache_add (pph_cache *, void *, unsigned *, enum pph_tag);
+pph_cache_entry *pph_cache_insert_at (pph_cache *, void *, unsigned,
+				      enum pph_tag);
+pph_cache_entry *pph_cache_lookup (pph_cache *, void *, unsigned *,
+				   enum pph_tag);
+pph_cache_entry *pph_cache_lookup_in_includes (pph_stream *, void *,
+					       unsigned *, unsigned *,
+					       enum pph_tag);
+pph_cache_entry *pph_cache_add (pph_cache *, void *, unsigned *, enum pph_tag);
 void pph_cache_sign (pph_cache *, unsigned, unsigned, size_t);
 unsigned pph_get_signature (tree, size_t *);
 void pph_writer_add_include (pph_stream *);
@@ -365,20 +373,24 @@ pph_tag_is_tree_code (enum pph_tag tag)
 }
 
 /* Return the PPH tag associated with tree node T.  */
-/* FIXME pph: apparently unused, except just below.  */
 static inline enum pph_tag
 pph_tree_code_to_tag (tree t)
 {
   return t ? (enum pph_tag) TREE_CODE (t) : PPH_null;
 }
 
-/* Return the tree code associated with PPH tag TAG.  */
-/* FIXME pph: apparently unused.  */
-static inline enum tree_code
-pph_tag_to_tree_code (enum pph_tag tag)
+/* Return true if EXPR can be emitted in two parts: a merge key and
+   a merge body.  This is used to support merging ASTs read from
+   multiple PPH images.  */
+static inline bool
+pph_tree_is_mergeable (tree expr)
 {
-  gcc_assert (pph_tag_is_tree_code (tag));
-  return (enum tree_code) tag;
+  return TREE_CODE (expr) == VAR_DECL
+	 || TREE_CODE (expr) == FUNCTION_DECL
+	 || TREE_CODE (expr) == TYPE_DECL
+	 || TREE_CODE (expr) == TEMPLATE_DECL
+	 || TREE_CODE (expr) == NAMESPACE_DECL
+	 || TREE_CODE (expr) == CONST_DECL;
 }
 
 #endif  /* GCC_CP_PPH_STREAMER_H  */
diff --git a/gcc/cp/pph.h b/gcc/cp/pph.h
index f5b0c24..2a346fd 100644
--- a/gcc/cp/pph.h
+++ b/gcc/cp/pph.h
@@ -62,6 +62,12 @@ enum pph_record_marker {
        top of the already allocated object.  */
   PPH_RECORD_START_MUTATED,
 
+  /* Start a merge key.  */
+  PPH_RECORD_START_MERGE_KEY,
+
+  /* Start a merge body.  */
+  PPH_RECORD_START_MERGE_BODY,
+
   /* End of record marker.  If a record starts with PPH_RECORD_END, the
      reader should return a NULL pointer.  */
   PPH_RECORD_END,
-- 
1.7.3.1


--
This patch is available for review at http://codereview.appspot.com/5318043