From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1075) id 2F11E3858C50; Fri, 21 Apr 2023 13:47:17 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2F11E3858C50 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682084837; bh=aKbjNtI44m2ksP1AcABRrox7Y573Ry8i0CoU8o8odWY=; h=From:To:Subject:Date:From; b=tFepixrO/5oEUKj0cnAH+yvhoo3gGlGu2XoUnM0k8DCvi3OzM+6FVuFkUor30/GoL 1oPbgqaHPpJdqGf5+6+1EGuNuV7sd7FxbxpbYs9XCjBOTPKr2rUE0LCu398N3WrnCA Ec44mfbG8VWkUp6eI28rUVpfRoKuAFeI446pVezQ= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Jan Hubicka To: gcc-cvs@gcc.gnu.org Subject: [gcc r14-142] Stabilize inliner X-Act-Checkin: gcc X-Git-Author: Jan Hubicka X-Git-Refname: refs/heads/master X-Git-Oldrev: b5c3abcd77cbca6b2d921fa2f7d21a52e5a36080 X-Git-Newrev: 68c0df8da73cf46e29834cc825f488f4d6b33f98 Message-Id: <20230421134717.2F11E3858C50@sourceware.org> Date: Fri, 21 Apr 2023 13:47:17 +0000 (GMT) List-Id: https://gcc.gnu.org/g:68c0df8da73cf46e29834cc825f488f4d6b33f98 commit r14-142-g68c0df8da73cf46e29834cc825f488f4d6b33f98 Author: Jan Hubicka 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 Michal Jires * 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 edge_heap_t; -typedef fibonacci_node 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 edge_heap_t; +typedef fibonacci_node 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 &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 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