From patchwork Wed Mar 27 15:42:21 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 87706 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B1885385DC18 for ; Wed, 27 Mar 2024 15:43:01 +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 E63833858C31 for ; Wed, 27 Mar 2024 15:42:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E63833858C31 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 E63833858C31 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=1711554144; cv=none; b=vdNgSgSuLyYmUmKjUJEWckZyMm2x0353YA5oBU4hMSmxL+N/VD0qarIMjlIcid9nmWxHj9sm1QL7BKrSV4huPwtBgfD++p7vzXs8+QffwpoZkMXw0/TCmgJfRW/4NSO12uwFQZCWiv9Bb4COyfDYenvQRJaWdn7xBouOyfkaz10= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711554144; c=relaxed/simple; bh=r4J60JKWlBYwxoYZckKtbcCPynFmjsrDqyuCybmQqrA=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=nUwxkZbUglb8ihN98N8vjgrcj0lCjp0jGr/iOExyX83BayHktXotJLkIo3Uxsr7TOzGKnsXmg9eJfKAsSRANt95O+uVcX6ocEIWQT47raLvbM8alk/x5h8LEj8RGBj0rQAyZ5aKN0hc17LH6Cyqeb+9OmHTiQfNoz/c5cJJnZAQ= 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-out1.suse.de (Postfix) with ESMTPS id 971DB38BBE; Wed, 27 Mar 2024 15:42:21 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1711554141; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=HQieKATiWDdCcKpdHBFIA4yYZeSIupSHzrnMFcgZh3A=; b=oWWsZEeagV6RChCk5CtqHkTo2VGp8Y7rdQQOt7IeX/KwSXwwZLhoIeQ4bCojdIzfirYEz1 p2aWYw0v981D96dEDuECpnbzVuneSYXPdr8LoMDke7FTywQqdV1GR65rTf8s7tz92jNpPd zWfvbhGbqNzpW9yjEtPZmi65BAgtPY4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1711554141; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=HQieKATiWDdCcKpdHBFIA4yYZeSIupSHzrnMFcgZh3A=; b=42KOp1NjKQx3xPFfoeSsuSjzywrT34gz5BVLr4/jY9NKoAdLAChXFS3y/eMV+hxbD+ydxJ U71EQZQSKnjrIrBQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1711554141; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=HQieKATiWDdCcKpdHBFIA4yYZeSIupSHzrnMFcgZh3A=; b=oWWsZEeagV6RChCk5CtqHkTo2VGp8Y7rdQQOt7IeX/KwSXwwZLhoIeQ4bCojdIzfirYEz1 p2aWYw0v981D96dEDuECpnbzVuneSYXPdr8LoMDke7FTywQqdV1GR65rTf8s7tz92jNpPd zWfvbhGbqNzpW9yjEtPZmi65BAgtPY4= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1711554141; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=HQieKATiWDdCcKpdHBFIA4yYZeSIupSHzrnMFcgZh3A=; b=42KOp1NjKQx3xPFfoeSsuSjzywrT34gz5BVLr4/jY9NKoAdLAChXFS3y/eMV+hxbD+ydxJ U71EQZQSKnjrIrBQ== Date: Wed, 27 Mar 2024 16:42:21 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jakub Jelinek Subject: [PATCH] middle-end/114480 - IDF compute is slow MIME-Version: 1.0 Authentication-Results: smtp-out1.suse.de; none X-Spam-Score: 1.34 X-Spamd-Result: default: False [1.34 / 50.00]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; NEURAL_HAM_LONG(-1.00)[-0.998]; MIME_GOOD(-0.10)[text/plain]; MISSING_MID(2.50)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.06)[-0.309]; 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)[35.28%] 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+patchwork=sourceware.org@gcc.gnu.org Message-Id: <20240327154301.B1885385DC18@sourceware.org> The testcase in this PR shows very slow IDF compute: tree SSA rewrite : 76.99 ( 31%) 24.78% 243663 cc1plus cc1plus [.] compute_idf which can be mitigated to some extent by refactoring the bitmap operations to simpler variants. With the patch below this becomes tree SSA rewrite : 15.23 ( 8%) when not optimizing and in addition to that tree SSA incremental : 181.52 ( 30%) to tree SSA incremental : 24.09 ( 6%) when optimizing. Bootstrap and regtest running on x86_64-unknown-linux-gnu. OK if that succeeds? Thanks, Richard. PR middle-end/114480 * cfganal.cc (compute_idf): Use simpler bitmap iteration, touch work_set only when phi_insertion_points changed. --- gcc/cfganal.cc | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) diff --git a/gcc/cfganal.cc b/gcc/cfganal.cc index 432775decf1..5ef629f677e 100644 --- a/gcc/cfganal.cc +++ b/gcc/cfganal.cc @@ -1701,8 +1701,7 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) on earlier blocks first is better. ??? Basic blocks are by no means guaranteed to be ordered in optimal order for this iteration. */ - bb_index = bitmap_first_set_bit (work_set); - bitmap_clear_bit (work_set, bb_index); + bb_index = bitmap_clear_first_set_bit (work_set); /* Since the registration of NEW -> OLD name mappings is done separately from the call to update_ssa, when updating the SSA @@ -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); - } } return phi_insertion_points;