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 CC7C33858413 for ; Tue, 14 Feb 2023 13:58:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CC7C33858413 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 14CB6221AB; Tue, 14 Feb 2023 13:58:40 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1676383120; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=G5hSzwK1tiTdAytYUdf6EZFB87foJGG4DlMfn0D7428=; b=xnKw5eZFoiI+MNZJHKeJFbNfSnjbqTD32nrSgraDvHpNE1mJrx26XvZK2l4jPVmNwRJMg8 3uGtUkkmbe89GyOCfX3YQn4v4FI92CeGRjU7+dROpGRojsQqXsEW6KJD90p99sBrZ1vbGc qeXCAxhbLtXHj2P8ybeZC425KI3Byek= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1676383120; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=G5hSzwK1tiTdAytYUdf6EZFB87foJGG4DlMfn0D7428=; b=hHFXIerAqvnAuoiSB5WN7Xk9vP+pN0U2z1Ztez0jDNQoRMAM6kDUMCME8fptP+wMTvKLvV WoVNDZ3LmgXA0VBA== 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 066662C141; Tue, 14 Feb 2023 13:58:40 +0000 (UTC) Date: Tue, 14 Feb 2023 13:58:39 +0000 (UTC) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: ubizjak@gmail.com, Jan Hubicka Subject: Re: [PATCH] target/108738 - STV bitmap operations compile-time hog Message-ID: 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=-11.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,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 Thu, 9 Feb 2023, Richard Biener wrote: > 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? Ping - sorry, forgot to CC maintainers. Richard. > 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); > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman; HRB 36809 (AG Nuernberg)