From patchwork Tue Sep 24 12:34:42 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1988912 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=ugljWwDc; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=xZ3jSkUg; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=ugljWwDc; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=xZ3jSkUg; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XCfT92xP5z1xst for ; Tue, 24 Sep 2024 22:35:08 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A03853858D26 for ; Tue, 24 Sep 2024 12:35:06 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.223.131]) by sourceware.org (Postfix) with ESMTPS id 8CFFD3858D20 for ; Tue, 24 Sep 2024 12:34:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8CFFD3858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 8CFFD3858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.131 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727181285; cv=none; b=CIQaIv+TOzsMDAc7eLAY3HcPB4+tA8omEncJ0c1EcQ83d2HsSciVceplLuIgmaLZSiijZjcgOLfM/9dei2+gVWh1615QB/DhckSctnXymt0+NO3H5wxU5p06VJliBQJtuoxwDy6qiYrxYmX4pi8NU6EirifIT67BBcDUhDDl6tQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727181285; c=relaxed/simple; bh=DxkaE31eyHjSmhxX0wgjlF2vEOJJlzKwj1AN3lI0SVY=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=JK5iHNZwmVrJ5hamb2gUInmBR0nyplwgaDDXDHqyylY37xKhSiVYZ6rQlSVpRzJQmBWOkyY0BZoHO29SfdwDY68062fxL456SKFxXIA/jUB7F3vtgP26auGfx3Amu5GsX+KR0UvQI/nte7XhbLSZgDAhlgVjd6KO4AFKNYRefbc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from murzim.nue2.suse.org (unknown [10.168.4.243]) (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 smtp-out2.suse.de (Postfix) with ESMTPS id 7CC291F79C; Tue, 24 Sep 2024 12:34:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727181282; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=mA+x3tZiFlPpmlrrMXPYy0lUAjeMYuaC1AHi2jEY61Y=; b=ugljWwDcTJ+lQCW/c/03rxdtHhoR2DS5dwhQ0AWPkU3B2w0BEE1dwRhr6x2FTP9mK7sLtR kyMgDYvLKr6koTMDG5vEZgzV4lgwPuQaKstgk2VjKCPAFDR4GP/ToSVyRRHJaWtBpyyaMK 3bo1lDryY4Ed5Zdpq/xo40sxLAB+UQU= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727181282; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=mA+x3tZiFlPpmlrrMXPYy0lUAjeMYuaC1AHi2jEY61Y=; b=xZ3jSkUg1i4YdWitsR5B/WG/qm+aT3GlRBlzFd3yVGht4PJ9zlUbJLfjZq3bnHWHo804P9 NOdVACJ3ysLQ/7Aw== Authentication-Results: smtp-out2.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727181282; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=mA+x3tZiFlPpmlrrMXPYy0lUAjeMYuaC1AHi2jEY61Y=; b=ugljWwDcTJ+lQCW/c/03rxdtHhoR2DS5dwhQ0AWPkU3B2w0BEE1dwRhr6x2FTP9mK7sLtR kyMgDYvLKr6koTMDG5vEZgzV4lgwPuQaKstgk2VjKCPAFDR4GP/ToSVyRRHJaWtBpyyaMK 3bo1lDryY4Ed5Zdpq/xo40sxLAB+UQU= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727181282; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=mA+x3tZiFlPpmlrrMXPYy0lUAjeMYuaC1AHi2jEY61Y=; b=xZ3jSkUg1i4YdWitsR5B/WG/qm+aT3GlRBlzFd3yVGht4PJ9zlUbJLfjZq3bnHWHo804P9 NOdVACJ3ysLQ/7Aw== Date: Tue, 24 Sep 2024 14:34:42 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: jeffreyalaw@gmail.com, vmakarov@redhat.com Subject: [PATCH 1/2] rtl-optimization/114855 - slow add_store_equivs in IRA MIME-Version: 1.0 X-Spam-Score: -1.51 X-Spamd-Result: default: False [-1.51 / 50.00]; BAYES_HAM(-3.00)[99.99%]; MISSING_MID(2.50)[]; NEURAL_HAM_LONG(-0.72)[-0.715]; NEURAL_HAM_SHORT(-0.20)[-0.995]; MIME_GOOD(-0.10)[text/plain]; ARC_NA(0.00)[]; MISSING_XM_UA(0.00)[]; RCVD_COUNT_ZERO(0.00)[0]; FREEMAIL_ENVRCPT(0.00)[gmail.com]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FUZZY_BLOCKED(0.00)[rspamd.com]; FROM_HAS_DN(0.00)[]; FREEMAIL_CC(0.00)[gmail.com,redhat.com]; MIME_TRACE(0.00)[0:+]; FROM_EQ_ENVFROM(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; TO_DN_NONE(0.00)[]; RCPT_COUNT_THREE(0.00)[3] X-Spam-Level: X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Message-Id: <20240924123506.A03853858D26@sourceware.org> For the testcase in PR114855 at -O1 add_store_equivs shows up as the main sink for bitmap_set_bit because it uses a bitmap to mark all seen insns by UID to make sure the forward walk in memref_used_between_p will find the insn in question. Given we do have a CFG here the functions operation is questionable, given memref_used_between_p together with the walk of all insns is obviously quadratic in the worst case that whole thing should be re-done ... but, for the testcase, using a sbitmap of size get_max_uid () + 1 gets bitmap_set_bit off the profile and improves IRA time from 15.58s (8%) to 3.46s (2%). Now, given above quadraticness I wonder whether we should instead gate add_store_equivs on optimize > 1 or flag_expensive_optimizations. Jeff, you added the bitmap in r6-7529-g14d7d4be52585b, I have no idea how get_insns () works at this point and in which CFG mode we are but a simplification might be to simply verify both insns are in the same BB and hopefully get_insns gets us walk the insns in order there, thus we could elide the bitmap completely (with some loss of cases, but the function comment suggests it is supposed to catch single-BB cases only anyway?!). Bootstrap and regtest running on x86_64-unknown-linux-gnu. OK if that succeeds? Thanks, Richard. PR rtl-optimization/114855 * ira.cc (add_store_equivs): Use sbitmap for tracking visited insns. --- gcc/ira.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/gcc/ira.cc b/gcc/ira.cc index 156541df4e6..3936456c4ed 100644 --- a/gcc/ira.cc +++ b/gcc/ira.cc @@ -3838,7 +3838,8 @@ update_equiv_regs (void) static void add_store_equivs (void) { - auto_bitmap seen_insns; + auto_sbitmap seen_insns (get_max_uid () + 1); + bitmap_clear (seen_insns); for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn)) { From patchwork Tue Sep 24 12:35:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1988913 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=0sjw23t6; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=7UK11ocm; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=0sjw23t6; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=7UK11ocm; dkim-atps=neutral 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=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XCfTr5LFyz1xst for ; Tue, 24 Sep 2024 22:35:44 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8FA5D385C6D1 for ; Tue, 24 Sep 2024 12:35:42 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by sourceware.org (Postfix) with ESMTPS id 070103858D3C for ; Tue, 24 Sep 2024 12:35:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 070103858D3C Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 070103858D3C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727181320; cv=none; b=omX4hY1HDXciNp+jDkaLvdI4mDY7f4bt4W4qkb8drEJ4pjwx/QZ/KjMXJZUY0ri1RHTumKvoWzzr4lL7Dpm8RnPBj4TYiXH/QeMbldOxaea1TE/9WLnlLTVrElWtZoexY9yCGWuccxVaoZErJrBph9iBHfW54Px4fXO7Z5pm01c= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727181320; c=relaxed/simple; bh=ehbLhMR7rmoDkgEh4PL7iURFYPrBuIVCnzNRMXpEh9g=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=tfPvU7ERFJr75VXjdUT8iErPSju1g4qmyl7wSd6MQaGp1zAPlwotzpkoBJtXLjcrkx9hE2h38o3TlebjdGEv+EVGJaGIADYMmphmupc7G530ysfmPskUAEY9wIvsf90d7lvGKwcWA3ile+zAjVrXwpmvjUSiWa37NXF1/ZqH0O8= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from murzim.nue2.suse.org (unknown [10.168.4.243]) (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 smtp-out1.suse.de (Postfix) with ESMTPS id 14746219EA; Tue, 24 Sep 2024 12:35:18 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727181318; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=iOKyfhDFvGm9UzUAwKAzeyUov+yTfpZjxU60JJrQ3Kw=; b=0sjw23t6ld1jkfSYBqCdlWW0VRxMnRBRvHvRdZapo1VpP2QFrVFigPN15F/PqBjzeMTdL+ OYk2H9y8PGY0mSn/X0vsxIwv4jS/ZYbqWFsqbSMwIP3Myi+73jO1wbxm+7ROUXNjVy+tcP Q/NGqN+znz/3iUQ+ipTNaKEP/KqPAZA= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727181318; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=iOKyfhDFvGm9UzUAwKAzeyUov+yTfpZjxU60JJrQ3Kw=; b=7UK11ocm/QG+2QR3Ir+jmqxcUbe9TqI1eocSfMIYqZdADOJGVlPk9mu1bsP8ZAF7Sm7FGO yiF9BI7/lxXboRCg== Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727181318; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=iOKyfhDFvGm9UzUAwKAzeyUov+yTfpZjxU60JJrQ3Kw=; b=0sjw23t6ld1jkfSYBqCdlWW0VRxMnRBRvHvRdZapo1VpP2QFrVFigPN15F/PqBjzeMTdL+ OYk2H9y8PGY0mSn/X0vsxIwv4jS/ZYbqWFsqbSMwIP3Myi+73jO1wbxm+7ROUXNjVy+tcP Q/NGqN+znz/3iUQ+ipTNaKEP/KqPAZA= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727181318; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=iOKyfhDFvGm9UzUAwKAzeyUov+yTfpZjxU60JJrQ3Kw=; b=7UK11ocm/QG+2QR3Ir+jmqxcUbe9TqI1eocSfMIYqZdADOJGVlPk9mu1bsP8ZAF7Sm7FGO yiF9BI7/lxXboRCg== Date: Tue, 24 Sep 2024 14:35:17 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: vmakarov@redhat.com Subject: [PATCH 2/2] Disable add_store_equivs when -fno-expensive-optimizations MIME-Version: 1.0 X-Spam-Score: -1.51 X-Spamd-Result: default: False [-1.51 / 50.00]; BAYES_HAM(-3.00)[99.99%]; MISSING_MID(2.50)[]; NEURAL_HAM_LONG(-0.71)[-0.712]; NEURAL_HAM_SHORT(-0.20)[-0.978]; MIME_GOOD(-0.10)[text/plain]; FROM_HAS_DN(0.00)[]; RCVD_COUNT_ZERO(0.00)[0]; MISSING_XM_UA(0.00)[]; ARC_NA(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; TO_MATCH_ENVRCPT_ALL(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; FROM_EQ_ENVFROM(0.00)[]; TO_DN_NONE(0.00)[]; MIME_TRACE(0.00)[0:+] X-Spam-Level: X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Message-Id: <20240924123542.8FA5D385C6D1@sourceware.org> IRAs add_store_equivs is quadratic in the size of the function worst case, disable it when -fno-expensive-optimizations which means at -O1 and -Og. Bootstrap and regtest running on x86_64-unknown-linux-gnu. OK? Thanks, Richard. * ira.cc (ira): Gate add_store_equivs on flag_expensive_optimizations. --- gcc/ira.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/gcc/ira.cc b/gcc/ira.cc index 3936456c4ed..5231f63398e 100644 --- a/gcc/ira.cc +++ b/gcc/ira.cc @@ -5739,7 +5739,7 @@ ira (FILE *f) combine_and_move_insns (); /* Gather additional equivalences with memory. */ - if (optimize) + if (optimize && flag_expensive_optimizations) add_store_equivs (); loop_optimizer_finalize ();