From patchwork Wed Mar 16 08:12:31 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1606040 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=nextmovesoftware.com header.i=@nextmovesoftware.com header.a=rsa-sha256 header.s=default header.b=FUF6CxqN; dkim-atps=neutral Authentication-Results: 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=) 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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KJNLp3tqWz9sCq for ; Wed, 16 Mar 2022 19:13:04 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0B15B385EC59 for ; Wed, 16 Mar 2022 08:13:00 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from server.nextmovesoftware.com (server.nextmovesoftware.com [162.254.253.69]) by sourceware.org (Postfix) with ESMTPS id 00E74385E83F for ; Wed, 16 Mar 2022 08:12:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 00E74385E83F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=nextmovesoftware.com DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=nextmovesoftware.com; s=default; h=Content-Type:MIME-Version:Message-ID: Date:Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=mV58Uo1i6vL6I8FITE2qU4s6WvxuCFhIOBn33K9lm8w=; b=FUF6CxqNcmtTbl8rB8SjqPq1Fl Fw6CzqiS4k+FMT2AljwUJJqIDbvYY0wwveXtq5OyE+vrqMrFdD1YpXueCFZfMpv9Pvhprj587dQlh 8KDfRyaZFhb/a6HvNPmT1GODDAyhfIeTIjCitFcgOgnaj43BHIArkFTQCFs4TdEYpyNgn2gbVp3f8 tMdx0mT6gOHqgx0i+kO3EPqWhLgotEfFzhPyFNdopmaKV2+5GnrRGChtZXwQRn2Fk66jGDZdALmNI Ik5NnZCXXn6HCjeRChNUlEdHrTfbSe1PCxo3nAeS/jGX6u2+aPvR7OBg3qnFm+letv9AWbr3mQq/e sooNXWpQ==; Received: from host86-186-213-42.range86-186.btcentralplus.com ([86.186.213.42]:63652 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1nUOln-0006FB-AK; Wed, 16 Mar 2022 04:12:35 -0400 From: "Roger Sayle" To: "'Richard Biener'" Subject: [PATCH v2] Performance/size improvement to single_use when matching GIMPLE. Date: Wed, 16 Mar 2022 08:12:31 -0000 Message-ID: <001a01d8390d$97d052c0$c770f840$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: Adg5DNl3W05cYRMCR86WKKUNBVCMJA== Content-Language: en-gb X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - server.nextmovesoftware.com X-AntiAbuse: Original Domain - gcc.gnu.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - nextmovesoftware.com X-Get-Message-Sender-Via: server.nextmovesoftware.com: authenticated_id: roger@nextmovesoftware.com X-Authenticated-Sender: server.nextmovesoftware.com: roger@nextmovesoftware.com X-Source: X-Source-Args: X-Source-Dir: X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: , Cc: 'GCC Patches' , 'Marc Glisse' Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Here's version 2 of my patch, incorporating Richard Biener's suggestions. I've also done an analysis of the stage3 sizes of gimple-match.o on x86_64-pc-linux-gnu, which I believe is dominated by debug information, the .o file is 30MB in stage3, but only 4.8M in stage2. Before my proposed patch gimple-match.o is 31385160 bytes. The patch as proposed yesterday (using a single loop in single_use) reduces that to 31105040 bytes, saving 280120 bytes. The suggestion to remove the "inline" keyword saves only 56 more bytes, but annotating ATTRIBUTE_PURE on a function prototype was curiously effective, saving 1888 bytes. before: 31385160 after: 31105040 saved 280120 -inline: 31104984 saved 56 +pure: 31103096 saved 1888 I'll post two more patches later today, that save an additional 53K and 58K respectively (by tweaking genmatch) but the issue is with the size of debugging info (or something else?). This revised patch has been tested on x86_64-pc-linux-gnu with make bootstrap and make -k check with no new failures. Ok for mainline? 2022-03-16 Roger Sayle Richard Biener gcc/ChangeLog * gimple-match-head.cc (single_use): Implement inline using a single loop. Thanks in advance, Roger --- > -----Original Message----- > From: Richard Biener > Sent: 15 March 2022 09:18 > To: Roger Sayle > Cc: 'GCC Patches' ; 'Marc Glisse' > > Subject: Re: [PATCH] Performance/size improvement to single_use when > matching GIMPLE. > > On Tue, 15 Mar 2022, Roger Sayle wrote: > > > > > > > This patch improves the implementation of single_use as used in code > > > > generated from match.pd for patterns using :s. The current > > implementation > > > > contains the logic "has_zero_uses (t) || has_single_use (t)" which > > > > performs a loop over the uses to first check if there are zero > > non-debug > > > > uses [which is rare], then another loop over these uses to check if > > there > > > > is exactly one non-debug use. This can be better implemented using a > > > > single loop. > > > > > > > > This function is currently inlined over 800 times in gimple-match.cc, > > > > whose .o on x86_64-pc-linux-gnu is now up to 30 Mbytes, so speeding up > > > > and shrinking this function should help offset the growth in match.pd > > > > for GCC 12. > > > > > > > > This patch has been tested on x86_64-pc-linux-gnu with make bootstrap > > > > and make -k check with no new failures. Ok for mainline? > > Note the intent of has_zero_uses () is even simpler - it's the case for when > there's no SSA operand info on the stmt (no update_stmt called yet). More > precisely it wants to catch the case where the definition of the SSA name is not > in the IL. > > I'm not sure if we want to twist the effective semantics at this point (I guess we > do not want that), so the patch looks like an improvement. But may I ask to > move the function out of line for even more savings? Just put it in gimple- > match-head.cc and have it not declared inline. I think we may want to go as far > and declare the function 'pure' using ATTRIBUTE_PURE. > > > > > > > > > > > 2022-03-15 Roger Sayle > > > > > > > > gcc/ChangeLog > > > > * gimple-match-head.cc (single_use): Implement inline using a > > > > single loop. > > > > > > > > Thanks in advance, > > > > Roger > > > > -- > > > > > > > > > > -- > Richard Biener > SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg, > Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg) diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc index 74d5818..1c74d38 100644 --- a/gcc/gimple-match-head.cc +++ b/gcc/gimple-match-head.cc @@ -1160,10 +1160,28 @@ types_match (tree t1, tree t2) non-SSA_NAME (ie constants) and zero uses to cope with uses that aren't linked up yet. */ -static inline bool -single_use (tree t) +static bool +single_use (const_tree) ATTRIBUTE_PURE; + +static bool +single_use (const_tree t) { - return TREE_CODE (t) != SSA_NAME || has_zero_uses (t) || has_single_use (t); + if (TREE_CODE (t) != SSA_NAME) + return true; + + /* Inline return has_zero_uses (t) || has_single_use (t); */ + const ssa_use_operand_t *const head = &(SSA_NAME_IMM_USE_NODE (t)); + const ssa_use_operand_t *ptr; + bool single = false; + + for (ptr = head->next; ptr != head; ptr = ptr->next) + if (USE_STMT(ptr) && !is_gimple_debug (USE_STMT (ptr))) + { + if (single) + return false; + single = true; + } + return true; } /* Return true if math operations should be canonicalized,