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 <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)
