Re: [PATCH] target/108738 - STV bitmap operations compile-time hog

Re: [PATCH] target/108738 - STV bitmap operations compile-time hog

[Uros Bizjak]

On Thu, Feb 9, 2023 at 3:25 PM Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> 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?
>
> Thanks,
> Richard.
>
>         PR target/108738
>         * config/i386/i386-features.cc (convert_scalars_to_vector):
>         Switch candidates bitmaps to tree view before building the chains.

'git diff -w' shows the true change ;)

LGTM.

Thanks,
Uros.

> ---
>  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

Re: [PATCH] target/108738 - STV bitmap operations compile-time hog

[Richard Biener]

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 <rguenther@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)

[PATCH] target/108738 - STV bitmap operations compile-time hog

[Richard Biener]

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