[gcc r14-142] Stabilize inliner

[gcc r14-142] Stabilize inliner

[Jan Hubicka]

https://gcc.gnu.org/g:68c0df8da73cf46e29834cc825f488f4d6b33f98

commit r14-142-g68c0df8da73cf46e29834cc825f488f4d6b33f98
Author: Jan Hubicka <jh@suse.cz>
Date:   Fri Apr 21 15:46:38 2023 +0200

    Stabilize inliner
    
    The Fibonacci heap can change its behaviour quite significantly for no good
    reasons when multiple edges with same key occurs.  This is quite common
    for small functions.
    
    This patch stabilizes the order by adding edge uids into the info.
    Again I think this is good idea regardless of the incremental WPA project
    since we do not want random changes in inline decisions.
    
    gcc/ChangeLog:
    
    2023-04-21  Jan Hubicka  <hubicka@ucw.cz>
                Michal Jires  <michal@jires.eu>
    
            * ipa-inline.cc (class inline_badness): New class.
            (edge_heap_t, edge_heap_node_t): Use inline_badness for badness instead
            of sreal.
            (update_edge_key): Update.
            (lookup_recursive_calls): Likewise.
            (recursive_inlining): Likewise.
            (add_new_edges_to_heap): Likewise.
            (inline_small_functions): Likewise.

Diff:
---
 gcc/ipa-inline.cc | 83 ++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 70 insertions(+), 13 deletions(-)

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