Stabilize inliner Fibonacci heap

diff --git a/gcc/ipa-inline.cc b/gcc/ipa-inline.cc
index 474fbff2057..efc8df7d4e0 100644
--- a/gcc/ipa-inline.cc
+++ b/gcc/ipa-inline.cc
@@ -120,8 +120,54 @@  along with GCC; see the file COPYING3.  If not see
 #include "attribs.h"
 #include "asan.h"
 
-typedef fibonacci_heap <sreal, cgraph_edge> edge_heap_t;
-typedef fibonacci_node <sreal, cgraph_edge> edge_heap_node_t;
+/* Inliner uses greedy algorithm to inline calls in a priority order.
+   Badness is used as the key in a Fibonacci heap which roughly corresponds
+   to negation of benefit to cost ratios.
+   In case multiple calls has same priority we want to stabilize the outcomes
+   for which we use ids.  */
+class inline_badness
+{
+public:
+  sreal badness;
+  int uid;
+  inline_badness ()
+  : badness (sreal::min ()), uid (0)
+  {
+  }
+  inline_badness (cgraph_edge *e, sreal b)
+  : badness (b), uid (e->get_uid ())
+  {
+  }
+  bool operator<= (const inline_badness &other)
+  {
+    if (badness != other.badness)
+      return badness <= other.badness;
+    return uid <= other.uid;
+  }
+  bool operator== (const inline_badness &other)
+  {
+    return badness == other.badness && uid == other.uid;
+  }
+  bool operator!= (const inline_badness &other)
+  {
+    return badness != other.badness || uid != other.uid;
+  }
+  bool operator< (const inline_badness &other)
+  {
+    if (badness != other.badness)
+      return badness < other.badness;
+    return uid < other.uid;
+  }
+  bool operator> (const inline_badness &other)
+  {
+    if (badness != other.badness)
+      return badness > other.badness;
+    return uid > other.uid;
+  }
+};
+
+typedef fibonacci_heap <inline_badness, cgraph_edge> edge_heap_t;
+typedef fibonacci_node <inline_badness, cgraph_edge> edge_heap_node_t;
 
 /* Statistics we collect about inlining algorithm.  */
 static int overall_size;
@@ -1399,7 +1445,7 @@  update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge)
 	 We do lazy increases: after extracting minimum if the key
 	 turns out to be out of date, it is re-inserted into heap
 	 with correct value.  */
-      if (badness < n->get_key ())
+      if (badness < n->get_key ().badness)
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
@@ -1407,10 +1453,11 @@  update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge)
 		       "  decreasing badness %s -> %s, %f to %f\n",
 		       edge->caller->dump_name (),
 		       edge->callee->dump_name (),
-		       n->get_key ().to_double (),
+		       n->get_key ().badness.to_double (),
 		       badness.to_double ());
 	    }
-	  heap->decrease_key (n, badness);
+	  inline_badness b (edge, badness);
+	  heap->decrease_key (n, b);
 	}
     }
   else
@@ -1423,7 +1470,8 @@  update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge)
 		    edge->callee->dump_name (),
 		    badness.to_double ());
 	 }
-      edge->aux = heap->insert (badness, edge);
+      inline_badness b (edge, badness);
+      edge->aux = heap->insert (b, edge);
     }
 }
 
@@ -1630,7 +1678,10 @@  lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
     if (e->callee == node
 	|| (e->callee->ultimate_alias_target (&avail, e->caller) == node
 	    && avail > AVAIL_INTERPOSABLE))
-      heap->insert (-e->sreal_frequency (), e);
+    {
+      inline_badness b (e, -e->sreal_frequency ());
+      heap->insert (b, e);
+    }
   for (e = where->callees; e; e = e->next_callee)
     if (!e->inline_failed)
       lookup_recursive_calls (node, e->callee, heap);
@@ -1649,7 +1700,8 @@  recursive_inlining (struct cgraph_edge *edge,
 		      ? edge->caller->inlined_to : edge->caller);
   int limit = opt_for_fn (to->decl,
 			  param_max_inline_insns_recursive_auto);
-  edge_heap_t heap (sreal::min ());
+  inline_badness b (edge, sreal::min ());
+  edge_heap_t heap (b);
   struct cgraph_node *node;
   struct cgraph_edge *e;
   struct cgraph_node *master_clone = NULL, *next;
@@ -1809,7 +1861,10 @@  add_new_edges_to_heap (edge_heap_t *heap, vec<cgraph_edge *> &new_edges)
 	  && can_inline_edge_p (edge, true)
 	  && want_inline_small_function_p (edge, true)
 	  && can_inline_edge_by_limits_p (edge, true))
-        edge->aux = heap->insert (edge_badness (edge, false), edge);
+	{
+	  inline_badness b (edge, edge_badness (edge, false));
+	  edge->aux = heap->insert (b, edge);
+	}
     }
 }
 
@@ -1950,7 +2005,8 @@  inline_small_functions (void)
 {
   struct cgraph_node *node;
   struct cgraph_edge *edge;
-  edge_heap_t edge_heap (sreal::min ());
+  inline_badness b;
+  edge_heap_t edge_heap (b);
   auto_bitmap updated_nodes;
   int min_size;
   auto_vec<cgraph_edge *> new_indirect_edges;
@@ -2088,7 +2144,7 @@  inline_small_functions (void)
     {
       int old_size = overall_size;
       struct cgraph_node *where, *callee;
-      sreal badness = edge_heap.min_key ();
+      sreal badness = edge_heap.min_key ().badness;
       sreal current_badness;
       int growth;
 
@@ -2141,9 +2197,10 @@  inline_small_functions (void)
         current_badness = edge_badness (edge, false);
       if (current_badness != badness)
 	{
-	  if (edge_heap.min () && current_badness > edge_heap.min_key ())
+	  if (edge_heap.min () && current_badness > edge_heap.min_key ().badness)
 	    {
-	      edge->aux = edge_heap.insert (current_badness, edge);
+	      inline_badness b (edge, current_badness);
+	      edge->aux = edge_heap.insert (b, edge);
 	      continue;
 	    }
 	  else