From patchwork Sun Jan 14 08:48:05 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 124439 Delivered-To: patch@linaro.org Received: by 10.46.64.148 with SMTP id r20csp324674lje; Sun, 14 Jan 2018 00:48:56 -0800 (PST) X-Google-Smtp-Source: ACJfBotTN98P9+54mxEKD/7VxKn6JsXRSlrJC5YQOwhF+mPRhnnDJ/6fluRPTCSi/Diwghf78D0S X-Received: by 10.98.26.151 with SMTP id a145mr28295780pfa.206.1515919735895; Sun, 14 Jan 2018 00:48:55 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1515919735; cv=none; d=google.com; s=arc-20160816; b=nP2BLjkgeiBvNEeod+vDe4dD+VHirsBmPk5n3R6SWP37shIFS8Bg3tVDnu1FWgihSh mjoFJ15xahsx+/5tkvp0/l73zKaem56mhOeR9L4TCGCuUYp3Fs62CJ0aJE4wgElMqKnm isD8ogZ4QQnF3kfWW1cVKpc0gStIfO09uTncApyhilhK415sqCH6ynyUCjYJziBVWe9p L4mEG5ERZBrp//qLVJhmp5S4KyVmVJkpkeHwYb0f3W1UN17TRetVngjp/4DVEJZVH5OW to/iau9aS3v4v8ginBJcHmoguvtRubBfWSX4ewX2KlKiXpjdlSdocVYZMTuxwKxnuX39 n6Dg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:date:subject:mail-followup-to:to :from:delivered-to:sender:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:mailing-list:dkim-signature :domainkey-signature:arc-authentication-results; bh=9mgij704zcDu0IuQ88nDeuQs43vH2JJv6Tn5MulP5wo=; b=MApemASrI5t9golyfS7ID+La1+lurpDvTyUNrIsB4hJ80nGV4RfqQDQKm13m/IWeZr P731LnTa+Oh+4gtXQaI+UTPGVGiu82v6bKgoMaXjLVXwpKlGW7eGmSOxyxn4DQy4gDqF R3NbyTtkNhsukjPsXejWruao+7hi+Re24rxat52ZXcicifAO32OBUzJGQhBK1a6ap3O+ 6EavXuRSCPfPXcJ/lSR/A2PvL9UyEczqn93PXMvPyLjiSJzOGGhiWASU+iZCFNNDLbeH RWHsMADP0d7AwHebeuLRUZuRyQBQkG/Vko7QADhjG/7TOWOsJhdIpXN4lEMWUBo0/RFf hAFA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SrNBNPfh; spf=pass (google.com: domain of gcc-patches-return-471138-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-471138-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id h91si8208107pld.654.2018.01.14.00.48.55 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 14 Jan 2018 00:48:55 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-471138-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SrNBNPfh; spf=pass (google.com: domain of gcc-patches-return-471138-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-471138-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=rgxnJ2kONJT8jn/M7suArX25+s6endvrcCaq1sUcM+I3v8oHlSyQz ZXqOuG+YH6AJ1YjcqqshZgjziSm9cmQGGY66vxTXlRrN2lnTYbGyfEg+rsKBiDDo K7GZlKwufJFWxp+mHUHTON3xRjBE8MArYw5GGMjzL36f7EG9DCmcTY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=QREE5GvF2jOx/muyQKSCz+u4YBY=; b=SrNBNPfhTAzdTAjcUU3L 2xMMrQvlliI2Tq43ggCWdHyNNODGuSKpn4T3LyH0gjmTXkb21yACzicO+d8nwl37 d1H+xRHHa8FDX2a9GhWFDmuz6jAzd0OBlQz0P0oG+2lP7TPq5JKf2IVOzbG4jcsQ dx5ND6sfkmLJjRz+d7/9JvQ= Received: (qmail 49313 invoked by alias); 14 Jan 2018 08:48:33 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 49130 invoked by uid 89); 14 Jan 2018 08:48:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=dramatic, 13168, HX-Received:Sun, Hx-languages-length:3658 X-HELO: mail-oi0-f49.google.com Received: from mail-oi0-f49.google.com (HELO mail-oi0-f49.google.com) (209.85.218.49) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 14 Jan 2018 08:48:13 +0000 Received: by mail-oi0-f49.google.com with SMTP id g128so6508716oib.11 for ; Sun, 14 Jan 2018 00:48:10 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:mail-followup-to:subject:date:message-id :user-agent:mime-version; bh=9mgij704zcDu0IuQ88nDeuQs43vH2JJv6Tn5MulP5wo=; b=enxOhUJl4Zs0aEbAAWT/iab6S5tTxTmXP4doI57zeoWizkvQCJz+gxGlM6soJXcNP4 bJze+W4mQO08ECOrq4SqOQ/sx0YnLHbeWWbg41F+7h5ofd1nG1YLnsVwM3c5/MTZDaIU 5GeIsC/DTU2umwvj4E0K3gsvYcsUkG4aN1s88JueoEtwCQVn7o/aRq5jzcS+8XGmA385 cpKBCW/Qs8c3ZzfBwnMKdhV6Lo0c601OHJF/1H6QXo3/XQKuK4LDq0Xlh4ZTBJ2IvAPh 5TqP1ES5h9ZIM9WtDzPjMbEkynWMCHlUuxvzrgr9S7BvFYhe0Vf+u0L/d0vn7lNfc4SG EVaw== X-Gm-Message-State: AKwxytf4+Au8Q5LPPaTwCGJrQnjIYiJUq2n1+tpAMkUMzw7ONjxqI8no BI9FoDfhdMXNyhGfjz+YMUAMhzc3pm4= X-Received: by 10.202.236.6 with SMTP id k6mr7591249oih.191.1515919688554; Sun, 14 Jan 2018 00:48:08 -0800 (PST) Received: from localhost ([95.144.14.233]) by smtp.gmail.com with ESMTPSA id j16sm5400577oth.42.2018.01.14.00.48.06 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sun, 14 Jan 2018 00:48:07 -0800 (PST) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@linaro.org Subject: inline_small_functions speedup Date: Sun, 14 Jan 2018 08:48:05 +0000 Message-ID: <877eskygfu.fsf@linaro.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) MIME-Version: 1.0 After inlining A into B, inline_small_functions updates the information for (most) callees and callers of the new B: update_callee_keys (&edge_heap, where, updated_nodes); [...] /* Our profitability metric can depend on local properties such as number of inlinable calls and size of the function body. After inlining these properties might change for the function we inlined into (since it's body size changed) and for the functions called by function we inlined (since number of it inlinable callers might change). */ update_caller_keys (&edge_heap, where, updated_nodes, NULL); These functions in turn call can_inline_edge_p for most of the associated edges: if (can_inline_edge_p (edge, false) && want_inline_small_function_p (edge, false)) update_edge_key (heap, edge); can_inline_edge_p indirectly calls estimate_calls_size_and_time on the caller node, which seems to recursively process all callee edges rooted at the node. It looks from this like algorithm can be at least quadratic in the worst case. Maybe there's something we can do to make can_inline_edge_p cheaper, but since neither of these two calls is responsible for reporting an inline failure reason, it seems cheaper to test want_inline_small_function_p first, so that we don't calculate an estimate for something that we already know isn't a "small function". I think the only change needed to make that work is to check for CIF_FINAL_ERROR in want_inline_small_function_p; at the moment we rely on can_inline_edge_p to make that check. This cuts the time to build optabs.ii by over 4% with an --enable-checking=release compiler on x86_64-linux-gnu. I've seen more dramatic wins on aarch64-linux-gnu due to the NUM_POLY_INT_COEFFS==2 thing. The patch doesn't affect the output code. Tested on aarch64-linux-gnu, x86_64-linux-gnu and powerpc64le-linux-gnu. OK to install? Richard 2018-01-13 Richard Sandiford gcc/ * ipa-inline.c (want_inline_small_function_p): Return false if inlining has already failed with CIF_FINAL_ERROR. (update_caller_keys): Call want_inline_small_function_p before can_inline_edge_p. (update_callee_keys): Likewise. Index: gcc/ipa-inline.c =================================================================== --- gcc/ipa-inline.c 2018-01-09 14:29:35.151550415 +0000 +++ gcc/ipa-inline.c 2018-01-14 08:43:35.653122186 +0000 @@ -706,7 +706,11 @@ want_inline_small_function_p (struct cgr bool want_inline = true; struct cgraph_node *callee = e->callee->ultimate_alias_target (); - if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) + /* Allow this function to be called before can_inline_edge_p, + since it's usually cheaper. */ + if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR) + want_inline = false; + else if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) ; else if (!DECL_DECLARED_INLINE_P (callee->decl) && !opt_for_fn (e->caller->decl, flag_inline_small_functions)) @@ -1312,8 +1316,8 @@ update_caller_keys (edge_heap_t *heap, s if (!check_inlinablity_for || check_inlinablity_for == edge) { - if (can_inline_edge_p (edge, false) - && want_inline_small_function_p (edge, false)) + if (want_inline_small_function_p (edge, false) + && can_inline_edge_p (edge, false)) update_edge_key (heap, edge); else if (edge->aux) { @@ -1356,8 +1360,8 @@ update_callee_keys (edge_heap_t *heap, s && avail >= AVAIL_AVAILABLE && !bitmap_bit_p (updated_nodes, callee->uid)) { - if (can_inline_edge_p (e, false) - && want_inline_small_function_p (e, false)) + if (want_inline_small_function_p (e, false) + && can_inline_edge_p (e, false)) update_edge_key (heap, e); else if (e->aux) {