From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 4A52E385843A for ; Thu, 9 Feb 2023 14:25:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4A52E385843A Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 75007375A9 for ; Thu, 9 Feb 2023 14:25:01 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1675952701; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=7LP8Pe/MqFdFzSm+XBk+vsuOTKY7/Pco0OUayhkwk5w=; b=HBIhus/3JgQiXZ2oOaLYrQIwFhoXD96BcX+Y6wjQT65Z3PiVxMrmGYz8rC1izzz+NOZlOj a4h9ZRjEA2iWqBM0VpbyFCuq1sXcrhxwYnRLBhkzAl4UYdHQDPlHIy0Qoz6ELT+5PDwrYb M/U/HfAecR1a3ag8xMaMWJHnSf8rJCQ= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1675952701; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=7LP8Pe/MqFdFzSm+XBk+vsuOTKY7/Pco0OUayhkwk5w=; b=KlU6jlTViCmRWNqhw9mMu2jzg+Tkg/PCfZzggJRy4BpePc+Dm/MU6aRbWfhtmNnz6yuekd 3w1D8AEyAUgsStAQ== Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 652322C141 for ; Thu, 9 Feb 2023 14:25:01 +0000 (UTC) Date: Thu, 9 Feb 2023 14:25:01 +0000 (UTC) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] target/108738 - STV bitmap operations compile-time hog User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII 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 List-Id: Message-ID: <20230209142501.ZObWFqJd4rIBj9fFr-ZYly4H6LE6ZsFgn1OAiOGtGs4@z> When the set of candidates becomes very large then repeated bit checks on it during the build of an actual chain can become slow because of the O(n) nature of bitmap tests. The following switches the candidates bitmaps to the tree representation before building the chains to get O(log n) amortized behavior. For the testcase at hand this improves STV time by 50%. Bootstrapped and tested on x86_64-unknown-linux-gnu, OK? Thanks, Richard. PR target/108738 * config/i386/i386-features.cc (convert_scalars_to_vector): Switch candidates bitmaps to tree view before building the chains. --- gcc/config/i386/i386-features.cc | 49 +++++++++++++++++--------------- 1 file changed, 26 insertions(+), 23 deletions(-) diff --git a/gcc/config/i386/i386-features.cc b/gcc/config/i386/i386-features.cc index ec13d4e7489..9bd6d8677bb 100644 --- a/gcc/config/i386/i386-features.cc +++ b/gcc/config/i386/i386-features.cc @@ -2283,30 +2283,33 @@ convert_scalars_to_vector (bool timode_p) fprintf (dump_file, "There are no candidates for optimization.\n"); for (unsigned i = 0; i <= 2; ++i) - while (!bitmap_empty_p (&candidates[i])) - { - unsigned uid = bitmap_first_set_bit (&candidates[i]); - scalar_chain *chain; - - if (cand_mode[i] == TImode) - chain = new timode_scalar_chain; - else - chain = new general_scalar_chain (cand_mode[i], cand_vmode[i]); - - /* Find instructions chain we want to convert to vector mode. - Check all uses and definitions to estimate all required - conversions. */ - chain->build (&candidates[i], uid); - - if (chain->compute_convert_gain () > 0) - converted_insns += chain->convert (); - else - if (dump_file) - fprintf (dump_file, "Chain #%d conversion is not profitable\n", - chain->chain_id); + { + bitmap_tree_view (&candidates[i]); + while (!bitmap_empty_p (&candidates[i])) + { + unsigned uid = bitmap_first_set_bit (&candidates[i]); + scalar_chain *chain; - delete chain; - } + if (cand_mode[i] == TImode) + chain = new timode_scalar_chain; + else + chain = new general_scalar_chain (cand_mode[i], cand_vmode[i]); + + /* Find instructions chain we want to convert to vector mode. + Check all uses and definitions to estimate all required + conversions. */ + chain->build (&candidates[i], uid); + + if (chain->compute_convert_gain () > 0) + converted_insns += chain->convert (); + else + if (dump_file) + fprintf (dump_file, "Chain #%d conversion is not profitable\n", + chain->chain_id); + + delete chain; + } + } if (dump_file) fprintf (dump_file, "Total insns converted: %d\n", converted_insns); -- 2.35.3