From 9e1f4e00169f251d6777a6e594fb88fd581184f3 Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Wed, 2 Jan 2019 08:49:07 +0000
Subject: [PATCH] re PR lto/85574 (LTO bootstapped binaries differ)

2019-01-02  Richard Biener  <rguenther@suse.de>

	PR ipa/85574
	* ipa-icf.h (sem_item_optimizer::sort_congruence_split): Declare.
	* ipa-icf.c (sem_item_optimizer::sort_congruence_split): New
	function.
	(sem_item_optimizer::do_congruence_step_f): Sort the congruence
	set after UIDs before splitting them.

From-SVN: r267506
---
 gcc/ChangeLog |  9 +++++++++
 gcc/ipa-icf.c | 27 +++++++++++++++++++++++++--
 gcc/ipa-icf.h |  3 +++
 3 files changed, 37 insertions(+), 2 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8d243aa03c57..d896edc1b020 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2019-01-02  Richard Biener  <rguenther@suse.de>
+
+	PR ipa/85574
+	* ipa-icf.h (sem_item_optimizer::sort_congruence_split): Declare.
+	* ipa-icf.c (sem_item_optimizer::sort_congruence_split): New
+	function.
+	(sem_item_optimizer::do_congruence_step_f): Sort the congruence
+	set after UIDs before splitting them.
+
 2019-01-01  Martin Sebor  <msebor@redhat.com>
             Jeff Law  <law@redhat.com>
 
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index 6701931ecbdd..ebaf5825e1e9 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -3117,6 +3117,22 @@ sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
   return true;
 }
 
+/* Compare function for sorting pairs in do_congruence_step_f.  */
+
+int
+sem_item_optimizer::sort_congruence_split (const void *a_, const void *b_)
+{
+  const std::pair<congruence_class *, bitmap> *a
+    = (const std::pair<congruence_class *, bitmap> *)a_;
+  const std::pair<congruence_class *, bitmap> *b
+    = (const std::pair<congruence_class *, bitmap> *)b_;
+  if (a->first->id < b->first->id)
+    return -1;
+  else if (a->first->id > b->first->id)
+    return 1;
+  return 0;
+}
+
 /* Tests if a class CLS used as INDEXth splits any congruence classes.
    Bitmap stack BMSTACK is used for bitmap allocation.  */
 
@@ -3157,13 +3173,20 @@ sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
 	}
     }
 
+  auto_vec<std::pair<congruence_class *, bitmap> > to_split;
+  to_split.reserve_exact (split_map.elements ());
+  for (hash_map <congruence_class *, bitmap>::iterator i = split_map.begin ();
+       i != split_map.end (); ++i)
+    to_split.safe_push (*i);
+  to_split.qsort (sort_congruence_split);
+
   traverse_split_pair pair;
   pair.optimizer = this;
   pair.cls = cls;
 
   splitter_class_removed = false;
-  split_map.traverse <traverse_split_pair *,
-		      sem_item_optimizer::traverse_congruence_split> (&pair);
+  for (unsigned i = 0; i < to_split.length (); ++i)
+    traverse_congruence_split (to_split[i].first, to_split[i].second, &pair);
 
   /* Bitmap clean-up.  */
   split_map.traverse <traverse_split_pair *,
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index d8a8d43e0aa8..27d588c9c12c 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -599,6 +599,9 @@ private:
 					 bitmap const &b,
 					 traverse_split_pair *pair);
 
+  /* Compare function for sorting pairs in do_congruence_step_f.  */
+  static int sort_congruence_split (const void *, const void *);
+
   /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
      contains LEN bytes.  */
   void read_section (lto_file_decl_data *file_data, const char *data,
-- 
2.43.5