From patchwork Fri Apr 21 12:03:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1771864 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=R9fEpyrJ; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Q2tVV03Jrz23rW for ; Fri, 21 Apr 2023 22:04:17 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 515AF385842D for ; Fri, 21 Apr 2023 12:04:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 515AF385842D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682078655; bh=kKZbCGQhd9rgnVcdoeawXSxZmdQVi0Ntzes0sq/x4L4=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=R9fEpyrJ1YbGJ/VcyRp40sbc6J7CHE3NZczh2J2hRythrPYzWxWkrg6GhgiALJ2Iy NpAN5In3PjcrZ+CIjffd8f/xkGMa00xPSvxPimIfk5TnA8AkGrL5W3/7y8JczAVdrk nlEMsiFulb57iTSOoSum9RE2GvTgGZfm9/Q+3XsE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id 261BB3858C83 for ; Fri, 21 Apr 2023 12:03:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 261BB3858C83 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id E7D5E28A923; Fri, 21 Apr 2023 14:03:52 +0200 (CEST) Date: Fri, 21 Apr 2023 14:03:52 +0200 To: michal@jires.eu, rguenther@suse.de, gcc-patches@gcc.gnu.org Subject: Stabilize inliner Fibonacci heap Message-ID: MIME-Version: 1.0 Content-Disposition: inline X-Spam-Status: No, score=-11.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Jan Hubicka via Gcc-patches From: Jan Hubicka Reply-To: Jan Hubicka Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, This fixes another problem Michal noticed while working on incrmeental WHOPR. 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. Bootstrapped/regtested x86_64-linux, plan to commit it shortly. gcc/ChangeLog: * 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 --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