From patchwork Mon Feb 19 10:47:11 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1900913 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=mqJBIYom; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=FsNAzZTC; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=mqJBIYom; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=FsNAzZTC; 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 4TdfPl5JLYz1ybl for ; Mon, 19 Feb 2024 21:47:39 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 70DE5386480B for ; Mon, 19 Feb 2024 10:47:37 +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 [IPv6:2a07:de40:b251:101:10:150:64:2]) by sourceware.org (Postfix) with ESMTPS id 2E2B8386187E for ; Mon, 19 Feb 2024 10:47:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2E2B8386187E 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 2E2B8386187E Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:2 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1708339643; cv=none; b=WtyW5PIbbX0oBROTS+FUBI0n6/9Qqzp7XmFyM84WyuwSH/OGOI8YtH/u+JC9OjZKLxT6oTeWIUDX8JzLFa+q/YMvqcrEVchxyNnj9FiaCdDYDYllVFmTt6IUAyZUIZFSrcSg6afbR8F4Wz1ezAR2HpmvXisuEjUymv3SVpiuFLc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1708339643; c=relaxed/simple; bh=n2XNpsFduS4FN5KKVLjntppbuuIcwjtixW+bohm3aVs=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=NyrBqjkFBbLJieKONZXKHjN2x408tREhWsktfRaYLj0CJFaqBOPIIrD6AxB6XhaDyDuxPr4+2mWFqT/hSb46AUNz/tVh2qpRdl8+qOqaTLEDDWepik5lOzF451xqPjfdtxDlZjP8TPb/kpYKby4/ia1Eb5uipQOsFtf+oTA9BRI= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from [10.168.4.150] (unknown [10.168.4.150]) (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 366141F7F3; Mon, 19 Feb 2024 10:47:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1708339631; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=H9ATbrDp9aFYLVc7pAi+8XBMBmSG2tX2H74wINo+hB4=; b=mqJBIYomaaK/4Jx6tmAxHZqbsEzWcblb6h21rGhWd4kY0Pow+qyRTN+x4MnnR8MY/Cpf2R FV5UbE4TTYNWsWX/pjKUR9+fGQaLI4uxvZODUmK2RZYyQA3JznZJIvdBGo+EcHNqiRv4MF vgYWC/Kz+yWZ64tOp/VyIDlU1UFWMQ8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1708339631; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=H9ATbrDp9aFYLVc7pAi+8XBMBmSG2tX2H74wINo+hB4=; b=FsNAzZTC/KwPyKi/rXWpABrhHp5dH7IWJNxS4RvNHoZuxCAqeOoHIcMPg91uRw+RJ7OwCj W+3cXEimCb2kBMDA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1708339631; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=H9ATbrDp9aFYLVc7pAi+8XBMBmSG2tX2H74wINo+hB4=; b=mqJBIYomaaK/4Jx6tmAxHZqbsEzWcblb6h21rGhWd4kY0Pow+qyRTN+x4MnnR8MY/Cpf2R FV5UbE4TTYNWsWX/pjKUR9+fGQaLI4uxvZODUmK2RZYyQA3JznZJIvdBGo+EcHNqiRv4MF vgYWC/Kz+yWZ64tOp/VyIDlU1UFWMQ8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1708339631; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=H9ATbrDp9aFYLVc7pAi+8XBMBmSG2tX2H74wINo+hB4=; b=FsNAzZTC/KwPyKi/rXWpABrhHp5dH7IWJNxS4RvNHoZuxCAqeOoHIcMPg91uRw+RJ7OwCj W+3cXEimCb2kBMDA== Date: Mon, 19 Feb 2024 11:47:11 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: richard.sandiford@arm.com Subject: [PATCH] rtl-optimization/54052 - RTL SSA PHI insertion compile-time hog MIME-Version: 1.0 Authentication-Results: smtp-out2.suse.de; none X-Spamd-Result: default: False [2.40 / 50.00]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; MIME_GOOD(-0.10)[text/plain]; TO_DN_NONE(0.00)[]; MISSING_MID(2.50)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; RCPT_COUNT_TWO(0.00)[2]; FUZZY_BLOCKED(0.00)[rspamd.com]; RCVD_COUNT_ZERO(0.00)[0]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; BAYES_HAM(-0.00)[13.74%] X-Spam-Score: 2.40 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, 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.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: <20240219104737.70DE5386480B@sourceware.org> The following tries to address the PHI insertion compile-time hog in RTL fwprop observed with the PR54052 testcase where the loop computing the "unfiltered" set of variables possibly needing PHI nodes for each block exhibits quadratic compile-time and memory-use. Instead of only pruning the set of candidate regs by LR_IN in the second worklist loop do this when computing "unfiltered" already. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. I'll note that in PR98863 you say in comment#39 "Just to give an update on this: I have a patch that reduces the amount of memory consumed by fwprop so that it no longer seems to be outlier. However, it involves doing more bitmap operations. In this testcase we have a larger number of registers that seem to be live but unused across a large region of code, so bitmap ANDs with the live in sets are expensive and hit the worst-case O(nblocksnregisters). I'm still trying to find a way of reducing the effect of that." suggesting that the very AND operation I'm introducing below was an actual problem. It's just not very clear what testcase this was on (the PR hasn't one, it just talks about WRF with LTO and then some individual TUs of it). Indeed the patch doesn't do anything about quadraticness but it seems to effectively reduce the size of 'unfiltered' (but bringing in LR_IN into the workset). For the PR54052 testcase this improves compile-time from 1420s to 64s and slightly reduces peak memory use (I would have expected more but didn't do any statistics on the 'unfiltered' bitmaps themselves). OK for trunk and branches if tests go well? Thanks, Richard. PR rtl-optimization/54052 * rtl-ssa/blocks.cc (function_info::place_phis): Filter unfiltered by LR_IN. --- gcc/rtl-ssa/blocks.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/gcc/rtl-ssa/blocks.cc b/gcc/rtl-ssa/blocks.cc index 8996443e8d5..9d1cd1b0365 100644 --- a/gcc/rtl-ssa/blocks.cc +++ b/gcc/rtl-ssa/blocks.cc @@ -649,7 +649,8 @@ function_info::place_phis (build_info &bi) bitmap_iterator bmi; unsigned int b2; EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi) - if (bitmap_ior_into (&unfiltered[b2], b1_def) + if (bitmap_ior_and_into (&unfiltered[b2], b1_def, + DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn, b2))) && !bitmap_empty_p (&frontiers[b2])) // Propagate the (potential) new phi node definitions in B2. bitmap_set_bit (worklist, b2);