From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.223.131]) by sourceware.org (Postfix) with ESMTPS id E7FA33858D20 for ; Thu, 28 Mar 2024 08:12:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E7FA33858D20 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 E7FA33858D20 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=1711613572; cv=none; b=FiLGnlyVWrMxqX0HU+83EggiOOVfU9fwroycVfafl0mZ1EHNFObRj4p96+2/NA7bMpGDn+JMDPXGi0zMSxOcMaYyHs2NxY9jIeqnaeRuGOn/jgzgWo/g6mYbkcP3r1tmwHi8enymRVlkpEhcQhrLaREFj0Qvs3pxn2x/GY2V72s= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711613572; c=relaxed/simple; bh=mnDpsVlRcNY1iUYZkO45rLjxmlu1att+xU9neUpOyqk=; h=Date:From:To:Subject:Message-ID:MIME-Version; b=xBKqeQwJiWPPUnT61dpjF7jRQkN3RejFvsa3aoj5/nGKUgF4jJOyyL5ryms17RhvgJpWhyvNu8jkJw9oX9NI3gtEC5UoDYiWtKVAGy5RYSr/PRZAH3IyIvdTieGwcrSFKoKv/AE5sP8RluY/0RNoY/Qm1RojpzFJ3SHjwS2M+9c= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap2.dmz-prg2.suse.org (imap2.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:98]) (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 DD38F205B1; Thu, 28 Mar 2024 08:12:49 +0000 (UTC) Received: from imap2.dmz-prg2.suse.org (localhost [127.0.0.1]) (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 imap2.dmz-prg2.suse.org (Postfix) with ESMTPS id B6B7F13AF7; Thu, 28 Mar 2024 08:12:49 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap2.dmz-prg2.suse.org with ESMTPSA id vR4CK4EmBWZrVwAAn2gu4w (envelope-from ); Thu, 28 Mar 2024 08:12:49 +0000 Date: Thu, 28 Mar 2024 09:12:49 +0100 (CET) From: Richard Biener To: Michael Matz cc: Jakub Jelinek , gcc-patches@gcc.gnu.org Subject: Re: [PATCH] middle-end/114480 - IDF compute is slow In-Reply-To: Message-ID: <63s447o4-pn43-noqp-rr6s-qpq7onsso813@fhfr.qr> References: <96606.124032711422300395@us-mta-154.us.mimecast.lan> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Level: Authentication-Results: smtp-out2.suse.de; none X-Rspamd-Server: rspamd2.dmz-prg2.suse.org X-Spamd-Result: default: False [-4.00 / 50.00]; REPLY(-4.00)[] X-Spam-Score: -4.00 X-Rspamd-Queue-Id: DD38F205B1 X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00,KAM_DMARC_STATUS,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 List-Id: On Wed, 27 Mar 2024, Michael Matz wrote: > Hey, > > On Wed, 27 Mar 2024, Jakub Jelinek wrote: > > > > @@ -1712,12 +1711,9 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) > > > gcc_checking_assert (bb_index > > > < (unsigned) last_basic_block_for_fn (cfun)); > > > > > > - EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points, > > > - 0, i, bi) > > > - { > > > + EXECUTE_IF_SET_IN_BITMAP (&dfs[bb_index], 0, i, bi) > > > + if (bitmap_set_bit (phi_insertion_points, i)) > > > bitmap_set_bit (work_set, i); > > > - bitmap_set_bit (phi_insertion_points, i); > > > - } > > > } > > > > I don't understand why the above is better. > > Wouldn't it be best to do > > bitmap_ior_and_compl_into (work_set, &dfs[bb_index], > > phi_insertion_points); > > bitmap_ior_into (phi_insertion_points, &dfs[bb_index]); > > ? > > I had the same hunch, but: > > 1) One would have to make work_set be non-tree-view again (which with the > current structure is a wash anyway, and that makes sense as accesses to > work_set aren't heavily random here). The tree-view is a wash indeed (I tried many things). > 2) But doing that and using bitmap_ior.._into is still measurably slower: > on a reduced testcase with -O0 -fno-checking, proposed structure > (tree-view or not-tree-view workset doesn't matter): > > tree SSA rewrite : 14.93 ( 12%) 0.01 ( 2%) 14.95 ( > 12%) 27M ( 8%) > > with non-tree-view, and your suggestion: > > tree SSA rewrite : 20.68 ( 12%) 0.02 ( 4%) 20.75 ( > 12%) 27M ( 8%) > > I can only speculate that the usually extreme sparsity of the bitmaps in > question make the setup costs of the two bitmap_ior calls actually more > expensive than the often skipped second call to bitmap_set_bit in Richis > proposed structure. (That or cache effects) So slightly "better" than Jakubs variant would be if (bitmap_ior_and_compl_into (work_set, &dfs[bb_index], phi_insertion_points)) bitmap_ior_into (phi_insertion_points, &dfs[bb_index]); since phi_insertion_points grows that IOR becomes more expensive over time. The above for me (today Zen2, yesterday Zen4) is tree SSA rewrite : 181.02 ( 37%) with unconditiona ior_into: tree SSA rewrite : 180.93 ( 36%) while my patch is tree SSA rewrite : 22.04 ( 6%) not sure what uarch Micha tested on. I think the testcase has simply many variables we write into SSA (man compute_idf calls), many BBs but very low popcount DFS[] so iterating over DFS[] only is very beneficial here as opposed to also walk phi_insertion_points and work_set. I think low popcount DFS[] is quite typical for a CFG - but for sure popcount of DFS[] is going to be lower than popcount of the IDF (phi_insertion_points). Btw, with my patch compute_idf is completely off the profile so it's hard to improve further (we do process blocks possibly twice for example, but that doesn't make a difference here) Indeed doing statistics shows the maximum popcount of a dominance frontier is 8 but 99% have just a single block. But the popcount of the final IDF is more than 10000 half of the time and more than 1000 90% of the time. I have pushed the patch now. Richard.