From patchwork Tue Sep 24 06:44:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1988783 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=dOqcgQFK; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=e91uIaMy; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=dOqcgQFK; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=e91uIaMy; 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 4XCVjG6nQ6z1xsM for ; Tue, 24 Sep 2024 16:45:06 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C877C385841F for ; Tue, 24 Sep 2024 06:45:04 +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 7183A3858D26 for ; Tue, 24 Sep 2024 06:44:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7183A3858D26 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 7183A3858D26 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=1727160283; cv=none; b=vf7L/OBVmw281yt0UnBVNWwPfvat9bV6D/kO1gm8xUC+jqzyEJfXmO4BMyry4rjxy+v1YXChrBJ8GJ99z2gLO/xCtkDB1/uF3w4EXSsB2oXbNVyjZHe1oT9fcmm38cYE4+/crx5NfGyXfg8nDXn1BytI9e0s/JjQ+2BU8vfXKBw= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727160283; c=relaxed/simple; bh=5WiY2LLkLH9k7CHPkspVOd7dpzjNgUXddUpjaT74RjY=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=tjgxJ/gmX9XBQfm0brbE3nxpaIGaFp2EmW0rXStGBMAAawG14SCQtW4VQL4RJodKrc17RHVYQWIz8YtVTdRw0bLuPOc8yy4QMWCIyv4ByvTbSfK50vSRhEmpuwWAc5jCavdzKvA16PjyOPawtsBYP5p9Jn31XxaEB2t+RB+g4ss= 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 2F2BB1F788 for ; Tue, 24 Sep 2024 06:44:40 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727160280; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=uGoGxqMs4mXQrIKVGVcjMTu7OGV0Mur2PvB4Ln2PbiI=; b=dOqcgQFKAv4RCfvRaJvjY+d1+ZeMQpWRM2cWaGpcWFYX8HiVJbyv1uSobQpHUsxC9nDtHm HVGDhuvtfiYnhLAVrg28Wp7N0lCRSJYoXctlsHfC3bOk1Pqbb2VCXp1quL18tBImVKAP8i gszDJba6EipUSMxGJjJFsloeisCdP/c= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727160280; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=uGoGxqMs4mXQrIKVGVcjMTu7OGV0Mur2PvB4Ln2PbiI=; b=e91uIaMyKh/4qEqZ3hxuqfXfYdB/hKMGO9yDglgJOdIaBMfLyhW6DT/cJkSBp2pIc129cm 2uh+8OORcBcSLmCg== Authentication-Results: smtp-out2.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727160280; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=uGoGxqMs4mXQrIKVGVcjMTu7OGV0Mur2PvB4Ln2PbiI=; b=dOqcgQFKAv4RCfvRaJvjY+d1+ZeMQpWRM2cWaGpcWFYX8HiVJbyv1uSobQpHUsxC9nDtHm HVGDhuvtfiYnhLAVrg28Wp7N0lCRSJYoXctlsHfC3bOk1Pqbb2VCXp1quL18tBImVKAP8i gszDJba6EipUSMxGJjJFsloeisCdP/c= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727160280; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=uGoGxqMs4mXQrIKVGVcjMTu7OGV0Mur2PvB4Ln2PbiI=; b=e91uIaMyKh/4qEqZ3hxuqfXfYdB/hKMGO9yDglgJOdIaBMfLyhW6DT/cJkSBp2pIc129cm 2uh+8OORcBcSLmCg== Date: Tue, 24 Sep 2024 08:44:40 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/114855 - high update_ssa time MIME-Version: 1.0 X-Spam-Score: -1.07 X-Spamd-Result: default: False [-1.07 / 50.00]; BAYES_HAM(-3.00)[100.00%]; MISSING_MID(2.50)[]; NEURAL_HAM_LONG(-0.31)[-0.307]; NEURAL_HAM_SHORT(-0.16)[-0.800]; MIME_GOOD(-0.10)[text/plain]; RCPT_COUNT_ONE(0.00)[1]; RCVD_COUNT_ZERO(0.00)[0]; ARC_NA(0.00)[]; MISSING_XM_UA(0.00)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FUZZY_BLOCKED(0.00)[rspamd.com]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; TO_DN_NONE(0.00)[]; URIBL_BLOCKED(0.00)[tree-into-ssa.cc:url,murzim.nue2.suse.org:helo]; TO_MATCH_ENVRCPT_ALL(0.00)[]; FROM_HAS_DN(0.00)[] 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: <20240924064504.C877C385841F@sourceware.org> Part of the problem in PR114855 is high update_ssa time. When one fixes the backward jump threading issue tree SSA incremental is at 439.91s ( 26%), mostly doing bitmap element searches for blocks_with_phis_to_rewrite. The following turns that bitmap to tree view noticing the two-dimensional vector of PHIs it guards is excessive compared to what we actually save with it - walking all PHI nodes in a block, something we already do once to initialize stmt flags. So instead of optimizing that walk we use the stmt flag, saving allocations and global state that lives throughout the whole compilation. This reduces the tree SSA incremental time to 203.13 ( 14%) The array was added in r0-74758-g2ce798794df8e1 when we still possibly had gazillion virtual operands for PR26830, I checked the testcase still behaves OK. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. PR tree-optimization/114855 * tree-into-ssa.cc (phis_to_rewrite): Remove global var. (mark_phi_for_rewrite): Simplify. (rewrite_update_phi_arguments): Walk all PHIs, process those satisfying rewrite_uses_p. (delete_update_ssa): Simplify. (update_ssa): Likewise. Switch blocks_with_phis_to_rewrite to tree view. --- gcc/tree-into-ssa.cc | 44 ++++++++------------------------------------ 1 file changed, 8 insertions(+), 36 deletions(-) diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc index 5b367c35812..1cce9d62809 100644 --- a/gcc/tree-into-ssa.cc +++ b/gcc/tree-into-ssa.cc @@ -101,12 +101,7 @@ static sbitmap interesting_blocks; released after we finish updating the SSA web. */ bitmap names_to_release; -/* vec of vec of PHIs to rewrite in a basic block. Element I corresponds - the to basic block with index I. Allocated once per compilation, *not* - released between different functions. */ -static vec< vec > phis_to_rewrite; - -/* The bitmap of non-NULL elements of PHIS_TO_REWRITE. */ +/* The bitmap of blocks with PHIs to rewrite. */ static bitmap blocks_with_phis_to_rewrite; /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES. These sets need @@ -942,9 +937,6 @@ find_def_blocks_for (tree var) static void mark_phi_for_rewrite (basic_block bb, gphi *phi) { - vec phis; - unsigned n, idx = bb->index; - if (rewrite_uses_p (phi)) return; @@ -953,21 +945,7 @@ mark_phi_for_rewrite (basic_block bb, gphi *phi) if (!blocks_with_phis_to_rewrite) return; - if (bitmap_set_bit (blocks_with_phis_to_rewrite, idx)) - { - n = (unsigned) last_basic_block_for_fn (cfun) + 1; - if (phis_to_rewrite.length () < n) - phis_to_rewrite.safe_grow_cleared (n, true); - - phis = phis_to_rewrite[idx]; - gcc_assert (!phis.exists ()); - phis.create (10); - } - else - phis = phis_to_rewrite[idx]; - - phis.safe_push (phi); - phis_to_rewrite[idx] = phis; + bitmap_set_bit (blocks_with_phis_to_rewrite, bb->index); } /* Insert PHI nodes for variable VAR using the iterated dominance @@ -2097,18 +2075,17 @@ rewrite_update_phi_arguments (basic_block bb) FOR_EACH_EDGE (e, ei, bb->succs) { - vec phis; - if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index)) continue; - phis = phis_to_rewrite[e->dest->index]; - for (gphi *phi : phis) + for (auto gsi = gsi_start_phis (e->dest); + !gsi_end_p (gsi); gsi_next(&gsi)) { tree arg, lhs_sym, reaching_def = NULL; use_operand_p arg_p; - - gcc_checking_assert (rewrite_uses_p (phi)); + gphi *phi = *gsi; + if (!rewrite_uses_p (*gsi)) + continue; arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); arg = USE_FROM_PTR (arg_p); @@ -3060,10 +3037,6 @@ delete_update_ssa (void) fini_ssa_renamer (); - if (blocks_with_phis_to_rewrite) - EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi) - phis_to_rewrite[i].release (); - BITMAP_FREE (blocks_with_phis_to_rewrite); BITMAP_FREE (blocks_to_update); @@ -3470,8 +3443,7 @@ update_ssa (unsigned update_flags) gcc_assert (update_ssa_initialized_fn == cfun); blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL); - if (!phis_to_rewrite.exists ()) - phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1); + bitmap_tree_view (blocks_with_phis_to_rewrite); blocks_to_update = BITMAP_ALLOC (NULL); insert_phi_p = (update_flags != TODO_update_ssa_no_phi);