From patchwork Thu Apr 4 12:41:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1919793 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=LKKd/3xR; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=YSM74VXt; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=LKKd/3xR; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=YSM74VXt; 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 4V9LpT38qVz1yYf for ; Thu, 4 Apr 2024 23:41:36 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8A59B385841D for ; Thu, 4 Apr 2024 12:41:34 +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 [IPv6:2a07:de40:b251:101:10:150:64:1]) by sourceware.org (Postfix) with ESMTPS id 7C59D3858C98 for ; Thu, 4 Apr 2024 12:41:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7C59D3858C98 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 7C59D3858C98 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:1 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712234472; cv=none; b=p/DbuaP4odl291Rj+3URzcIhnNfBmfHmhQQc/pf/nUOEYQU5t9nso+qLfMNXZ9Jzix9e/uJMs+DPOqPLG2urxM+q4H7rY+ksyyP3HW2ZaCVu1usH9BhBo0zAi9+nCJarcdgT5ECoTm6lFno5ff7u4wWd3WGe2Tg859lvGsYwnDc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1712234472; c=relaxed/simple; bh=shigNc//4pwH3XZI950ab6KNsFqWycUUhHXMoTiSeag=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=kEyEDiU9wQydSJEEreOZWW24H6640vqmdQc694HgI+XuYTYxL1qhXaJC1Xs9Vq/yp1iHcHHJ5K3O0bK6YaRMKHiCVgAIAMI0HJDO+ovpFGDmTANvuBXQlTcqBTd0DIFO92reoSF5nKAyycDwrVXRBjcLbcfojL9IPlET0UPA1sY= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from [10.168.5.241] (unknown [10.168.5.241]) (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 5987137B8C; Thu, 4 Apr 2024 12:41:08 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712234468; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=KGih6W8lkZmQUab7qkUxnJNUytqQmJ/T9qJfXbZERoc=; b=LKKd/3xRWhZs+Xh6c6degCzS8WKRnw5igV/riNIz22tjcnGS/urnciwrf9HhCxiiNTLhdP UKsU5cMhX3jK49a8BSeWhDTVf5riPN/7g5IWIRd+Wf6mUvzjK18mj9wgaUM9P6hKr5GkWz xZCv0G3vEwUFfSB8KevMCFLFWi3wa88= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712234468; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=KGih6W8lkZmQUab7qkUxnJNUytqQmJ/T9qJfXbZERoc=; b=YSM74VXtZ2wEaxIrKt1hf+ZDhIc8QlwVw4L4wT5IgsIAavQ0OtJMVlolxcYkcXKrQ1X3Hs B6268BQdYsnUCcCg== Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1712234468; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=KGih6W8lkZmQUab7qkUxnJNUytqQmJ/T9qJfXbZERoc=; b=LKKd/3xRWhZs+Xh6c6degCzS8WKRnw5igV/riNIz22tjcnGS/urnciwrf9HhCxiiNTLhdP UKsU5cMhX3jK49a8BSeWhDTVf5riPN/7g5IWIRd+Wf6mUvzjK18mj9wgaUM9P6hKr5GkWz xZCv0G3vEwUFfSB8KevMCFLFWi3wa88= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1712234468; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=KGih6W8lkZmQUab7qkUxnJNUytqQmJ/T9qJfXbZERoc=; b=YSM74VXtZ2wEaxIrKt1hf+ZDhIc8QlwVw4L4wT5IgsIAavQ0OtJMVlolxcYkcXKrQ1X3Hs B6268BQdYsnUCcCg== Date: Thu, 4 Apr 2024 14:41:08 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jakub Jelinek , Michael Matz Subject: [PATCH] middle-end/114579 - speed up add_scope_conflicts MIME-Version: 1.0 X-Spam-Level: X-Spamd-Result: default: False [0.55 / 50.00]; BAYES_HAM(-3.00)[100.00%]; MISSING_MID(2.50)[]; NEURAL_SPAM_LONG(1.28)[0.365]; NEURAL_HAM_SHORT(-0.13)[-0.655]; MIME_GOOD(-0.10)[text/plain]; FUZZY_BLOCKED(0.00)[rspamd.com]; ARC_NA(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; RCVD_COUNT_ZERO(0.00)[0]; MISSING_XM_UA(0.00)[]; TO_DN_SOME(0.00)[] X-Spam-Score: 0.55 X-Spam-Status: No, score=-10.4 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: <20240404124134.8A59B385841D@sourceware.org> The following speeds up stack variable conflict detection by recognizing that the all-to-all conflict recording is only necessary for CFG merges as it's the unioning of the live variable sets that doesn't come with explicit mentions we record conflicts for. If we employ this optimization we have to make sure to perform the all-to-all conflict recording for all CFG merges even those into empty blocks where we might previously have skipped this. I have reworded the comment before the all-to-all conflict recording since it seemed to be confusing and missing the point - but maybe I am also missing something here. Nevertheless for the testcase in the PR the compile-time spend in add_scope_conflicts at -O1 drops from previously 67s (39%) to 10s (9%). Bootstrapped and tested on x86_64-unknown-linux-gnu, OK for trunk? Thanks, Richard. PR middle-end/114579 * cfgexpand.cc (add_scope_conflicts_1): Record all-to-all conflicts only when there's a CFG merge but for all CFG merges. --- gcc/cfgexpand.cc | 46 +++++++++++++++++++++++++++++++++------------- 1 file changed, 33 insertions(+), 13 deletions(-) diff --git a/gcc/cfgexpand.cc b/gcc/cfgexpand.cc index eef565eddb5..fa48a4c633f 100644 --- a/gcc/cfgexpand.cc +++ b/gcc/cfgexpand.cc @@ -640,21 +640,26 @@ add_scope_conflicts_1 (basic_block bb, bitmap work, bool for_conflict) { if (for_conflict && visit == visit_op) { - /* If this is the first real instruction in this BB we need - to add conflicts for everything live at this point now. - Unlike classical liveness for named objects we can't - rely on seeing a def/use of the names we're interested in. - There might merely be indirect loads/stores. We'd not add any - conflicts for such partitions. */ + /* When we are inheriting live variables from our predecessors + through a CFG merge we might not see an actual mention of + the variables to record the approprate conflict as defs/uses + might be through indirect stores/loads. For this reason + we have to make sure each live variable conflicts with + each other. When there's just a single predecessor the + set of conflicts is already up-to-date. + We perform this delayed at the first real instruction to + allow clobbers starting this block to remove variables from + the set of live variables. */ bitmap_iterator bi; unsigned i; - EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi) - { - class stack_var *a = &stack_vars[i]; - if (!a->conflicts) - a->conflicts = BITMAP_ALLOC (&stack_var_bitmap_obstack); - bitmap_ior_into (a->conflicts, work); - } + if (EDGE_COUNT (bb->preds) > 1) + EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi) + { + class stack_var *a = &stack_vars[i]; + if (!a->conflicts) + a->conflicts = BITMAP_ALLOC (&stack_var_bitmap_obstack); + bitmap_ior_into (a->conflicts, work); + } visit = visit_conflict; } walk_stmt_load_store_addr_ops (stmt, work, visit, visit, visit); @@ -662,6 +667,21 @@ add_scope_conflicts_1 (basic_block bb, bitmap work, bool for_conflict) add_scope_conflicts_2 (USE_FROM_PTR (use_p), work, visit); } } + + /* When there was no real instruction but there's a CFG merge we need + to add the conflicts now. */ + if (for_conflict && visit == visit_op && EDGE_COUNT (bb->preds) > 1) + { + bitmap_iterator bi; + unsigned i; + EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi) + { + class stack_var *a = &stack_vars[i]; + if (!a->conflicts) + a->conflicts = BITMAP_ALLOC (&stack_var_bitmap_obstack); + bitmap_ior_into (a->conflicts, work); + } + } } /* Generate stack partition conflicts between all partitions that are