[3/3] incremental lto: Remap node order for stability.

diff --git a/gcc/ipa-devirt.cc b/gcc/ipa-devirt.cc
index c406e5138db..098798281b7 100644
--- a/gcc/ipa-devirt.cc
+++ b/gcc/ipa-devirt.cc
@@ -4131,7 +4131,7 @@  ipa_odr_summary_write (void)
       odr_enum_map = NULL;
     }
 
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 }
 
diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
index b3824783406..badc5e703b2 100644
--- a/gcc/ipa-fnsummary.cc
+++ b/gcc/ipa-fnsummary.cc
@@ -4911,7 +4911,7 @@  ipa_fn_summary_write (void)
 	}
     }
   streamer_write_char_stream (ob->main_stream, 0);
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 
   ipa_prop_write_jump_functions ();
diff --git a/gcc/ipa-icf.cc b/gcc/ipa-icf.cc
index b10a6baf109..d9cd7d0c1c0 100644
--- a/gcc/ipa-icf.cc
+++ b/gcc/ipa-icf.cc
@@ -2216,7 +2216,7 @@  sem_item_optimizer::write_summary (void)
     }
 
   streamer_write_char_stream (ob->main_stream, 0);
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 }
 
diff --git a/gcc/ipa-modref.cc b/gcc/ipa-modref.cc
index 19359662f8f..7f36fab3db2 100644
--- a/gcc/ipa-modref.cc
+++ b/gcc/ipa-modref.cc
@@ -3739,7 +3739,7 @@  modref_write ()
     {
       streamer_write_uhwi (ob, 0);
       streamer_write_char_stream (ob->main_stream, 0);
-      produce_asm (ob, NULL);
+      produce_asm (ob, NULL, -1);
       destroy_output_block (ob);
       return;
     }
@@ -3814,7 +3814,7 @@  modref_write ()
 	}
     }
   streamer_write_char_stream (ob->main_stream, 0);
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 }
 
diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index 78d1fb7086d..032358fde22 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -5297,7 +5297,7 @@  ipa_prop_write_jump_functions (void)
         ipa_write_node_info (ob, node);
     }
   streamer_write_char_stream (ob->main_stream, 0);
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 }
 
@@ -5489,7 +5489,7 @@  ipcp_write_transformation_summaries (void)
 	write_ipcp_transformation_info (ob, cnode, ts);
     }
   streamer_write_char_stream (ob->main_stream, 0);
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 }
 
diff --git a/gcc/ipa-sra.cc b/gcc/ipa-sra.cc
index 04920f2aa8e..630f4d6c14f 100644
--- a/gcc/ipa-sra.cc
+++ b/gcc/ipa-sra.cc
@@ -2898,7 +2898,7 @@  ipa_sra_write_summary (void)
         isra_write_node_summary (ob, node);
     }
   streamer_write_char_stream (ob->main_stream, 0);
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 }
 
diff --git a/gcc/lto-cgraph.cc b/gcc/lto-cgraph.cc
index 1d4311a8832..53cc965bdfd 100644
--- a/gcc/lto-cgraph.cc
+++ b/gcc/lto-cgraph.cc
@@ -96,6 +96,8 @@  lto_symtab_encoder_delete (lto_symtab_encoder_t encoder)
    encoder->nodes.release ();
    if (encoder->map)
      delete encoder->map;
+   if (encoder->order_remap)
+     delete encoder->order_remap;
    free (encoder);
 }
 
@@ -406,7 +408,8 @@  lto_output_node (struct lto_simple_output_block *ob, struct cgraph_node *node,
 
   streamer_write_enum (ob->main_stream, LTO_symtab_tags, LTO_symtab_last_tag,
 		       tag);
-  streamer_write_hwi_stream (ob->main_stream, node->order);
+  int output_order = *encoder->order_remap->get (node->order);
+  streamer_write_hwi_stream (ob->main_stream, output_order);
 
   /* In WPA mode, we only output part of the call-graph.  Also, we
      fake cgraph node attributes.  There are two cases that we care.
@@ -603,7 +606,8 @@  lto_output_varpool_node (struct lto_simple_output_block *ob, varpool_node *node,
 
   streamer_write_enum (ob->main_stream, LTO_symtab_tags, LTO_symtab_last_tag,
 		       LTO_symtab_variable);
-  streamer_write_hwi_stream (ob->main_stream, node->order);
+  int output_order = *encoder->order_remap->get (node->order);
+  streamer_write_hwi_stream (ob->main_stream, output_order);
   lto_output_var_decl_ref (ob->decl_state, ob->main_stream, node->decl);
   bp = bitpack_create (ob->main_stream);
   bp_pack_value (&bp, node->externally_visible, 1);
@@ -2097,7 +2101,7 @@  output_cgraph_opt_summary (void)
 	  output_node_opt_summary (ob, cnode, encoder);
 	}
     }
-  produce_asm (ob, NULL);
+  produce_asm (ob, NULL, -1);
   destroy_output_block (ob);
 }
 
diff --git a/gcc/lto-streamer-out.cc b/gcc/lto-streamer-out.cc
index a464c2d5ddf..2b6b11ecf8b 100644
--- a/gcc/lto-streamer-out.cc
+++ b/gcc/lto-streamer-out.cc
@@ -2207,7 +2207,7 @@  output_cfg (struct output_block *ob, struct function *fn)
    a function, set FN to the decl for that function.  */
 
 void
-produce_asm (struct output_block *ob, tree fn)
+produce_asm (struct output_block *ob, tree fn, int output_order)
 {
   enum lto_section_type section_type = ob->section_type;
   struct lto_function_header header;
@@ -2217,8 +2217,7 @@  produce_asm (struct output_block *ob, tree fn)
     {
       const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fn));
       section_name = lto_get_section_name (section_type, name,
-					   symtab_node::get (fn)->order,
-					   NULL);
+					   output_order, NULL);
     }
   else
     section_name = lto_get_section_name (section_type, NULL, 0, NULL);
@@ -2402,7 +2401,7 @@  streamer_write_chain (struct output_block *ob, tree t, bool ref_p)
 /* Output the body of function NODE->DECL.  */
 
 static void
-output_function (struct cgraph_node *node)
+output_function (struct cgraph_node *node, int output_order)
 {
   tree function;
   struct function *fn;
@@ -2479,7 +2478,7 @@  output_function (struct cgraph_node *node)
     streamer_write_uhwi (ob, 0);
 
   /* Create a section to hold the pickled output of this function.   */
-  produce_asm (ob, function);
+  produce_asm (ob, function, output_order);
 
   destroy_output_block (ob);
   if (streamer_dump_file)
@@ -2490,7 +2489,7 @@  output_function (struct cgraph_node *node)
 /* Output the body of function NODE->DECL.  */
 
 static void
-output_constructor (struct varpool_node *node)
+output_constructor (struct varpool_node *node, int output_order)
 {
   tree var = node->decl;
   struct output_block *ob;
@@ -2512,7 +2511,7 @@  output_constructor (struct varpool_node *node)
   stream_write_tree (ob, DECL_INITIAL (var), true);
 
   /* Create a section to hold the pickled output of this function.   */
-  produce_asm (ob, var);
+  produce_asm (ob, var, output_order);
 
   destroy_output_block (ob);
   if (streamer_dump_file)
@@ -2573,7 +2572,7 @@  lto_output_toplevel_asms (void)
 /* Copy the function body or variable constructor of NODE without deserializing. */
 
 static void
-copy_function_or_variable (struct symtab_node *node)
+copy_function_or_variable (struct symtab_node *node, int output_order)
 {
   tree function = node->decl;
   struct lto_file_decl_data *file_data = node->lto_file_data;
@@ -2581,7 +2580,7 @@  copy_function_or_variable (struct symtab_node *node)
   size_t len;
   const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (function));
   char *section_name =
-    lto_get_section_name (LTO_section_function_body, name, node->order, NULL);
+    lto_get_section_name (LTO_section_function_body, name, output_order, NULL);
   size_t i, j;
   struct lto_in_decl_state *in_state;
   struct lto_out_decl_state *out_state = lto_get_out_decl_state ();
@@ -2726,6 +2725,63 @@  cmp_symbol_files (const void *pn1, const void *pn2, void *id_map_)
   return n1->order - n2->order;
 }
 
+/* Compare ints, callback for qsort.  */
+
+static int
+cmp_int (const void *a, const void *b)
+{
+  int ia = *(int const*) a;
+  int ib = *(int const*) b;
+  return ia - ib;
+}
+
+/* Create order mapping independent on symbols outside of the partition.
+   Results in stable order values for incremental LTO.
+
+   Remapping is not done in place, because symbols can be used
+   by multiple partitions.  */
+
+static void
+create_order_remap (lto_symtab_encoder_t encoder)
+{
+  auto_vec<int> orders;
+  unsigned i;
+  struct asm_node* anode;
+  encoder->order_remap = new hash_map<int_hash<int, -1, -2>, int>;
+  unsigned n_nodes = lto_symtab_encoder_size (encoder);
+
+  for (i = 0; i < n_nodes; i++)
+    orders.safe_push (lto_symtab_encoder_deref (encoder, i)->order);
+
+  if (!asm_nodes_output)
+    {
+      for (anode = symtab->first_asm_symbol (); anode; anode = anode->next)
+	orders.safe_push (anode->order);
+    }
+
+  orders.qsort (cmp_int);
+  int ord = 0;
+  int last_order = -1;
+  for (i = 0; i < orders.length (); i++)
+    {
+      int order = orders[i];
+      if (order != last_order)
+	{
+	  last_order = order;
+	  encoder->order_remap->put (order, ord);
+	  ord++;
+	}
+    }
+
+  /* Asm nodes are currently always output only into first partition.
+     We can remap already here.  */
+  if (!asm_nodes_output)
+    {
+      for (anode = symtab->first_asm_symbol (); anode; anode = anode->next)
+	anode->order = *encoder->order_remap->get (anode->order);
+    }
+}
+
 /* Main entry point from the pass manager.  */
 
 void
@@ -2738,6 +2794,8 @@  lto_output (void)
   lto_symtab_encoder_t encoder = lto_get_out_decl_state ()->symtab_node_encoder;
   auto_vec<symtab_node *> symbols_to_copy;
 
+  create_order_remap (encoder);
+
   prune_offload_funcs ();
 
   if (flag_checking)
@@ -2800,6 +2858,8 @@  lto_output (void)
       cgraph_node *cnode;
       varpool_node *vnode;
 
+      int output_order = *encoder->order_remap->get (snode->order);
+
       if (flag_checking)
 	gcc_assert (bitmap_set_bit (output, DECL_UID (snode->decl)));
 
@@ -2814,14 +2874,14 @@  lto_output (void)
 		 at WPA time.  */
 	      || DECL_ARGUMENTS (cnode->decl)
 	      || cnode->declare_variant_alt))
-	output_function (cnode);
+	output_function (cnode, output_order);
       else if ((vnode = dyn_cast <varpool_node *> (snode))
 	       && (DECL_INITIAL (vnode->decl) != error_mark_node
 		   || (!flag_wpa
 		       && flag_incremental_link != INCREMENTAL_LINK_LTO)))
-	output_constructor (vnode);
+	output_constructor (vnode, output_order);
       else
-	copy_function_or_variable (snode);
+	copy_function_or_variable (snode, output_order);
       gcc_assert (lto_get_out_decl_state () == decl_state);
       lto_pop_out_decl_state ();
       lto_record_function_out_decl_state (snode->decl, decl_state);
diff --git a/gcc/lto-streamer.h b/gcc/lto-streamer.h
index 4da1a3efe03..397f5fc8d68 100644
--- a/gcc/lto-streamer.h
+++ b/gcc/lto-streamer.h
@@ -461,6 +461,9 @@  struct lto_symtab_encoder_d
 {
   vec<lto_encoder_entry> nodes;
   hash_map<symtab_node *, size_t> *map;
+
+  /* Mapping of input order of nodes onto output order.  */
+  hash_map<int_hash<int, -1, -2>, int> *order_remap;
 };
 
 typedef struct lto_symtab_encoder_d *lto_symtab_encoder_t;
@@ -887,7 +890,7 @@  extern void lto_output_fn_decl_ref (struct lto_out_decl_state *,
 extern tree lto_input_var_decl_ref (lto_input_block *, lto_file_decl_data *);
 extern tree lto_input_fn_decl_ref (lto_input_block *, lto_file_decl_data *);
 extern void lto_output_toplevel_asms (void);
-extern void produce_asm (struct output_block *ob, tree fn);
+extern void produce_asm (struct output_block *ob, tree fn, int output_order);
 extern void lto_output ();
 extern void produce_asm_for_decls ();
 void lto_output_decl_state_streams (struct output_block *,