[PATCH] rtl-optimization/104686 - speed up conflict iteration

[PATCH] rtl-optimization/104686 - speed up conflict iteration

[Richard Biener]

The following replaces

       /* Skip bits that are zero.  */
       for (; (word & 1) == 0; word >>= 1)
         bit_num++;

idioms in ira-int.h in the attempt to speedup update_conflict_hard_regno_costs
which we're bound on in PR104686.  The trick is to use ctz_hwi here
which should pay off even with dense bitmaps on architectures that
have HW support for this.

For the PR in question this speeds up compile-time from 31s to 24s for
me.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

OK for trunk?

Thanks,
Richard.

2022-02-25  Richard Biener  <rguenther@suse.de>

	PR rtl-optimization/104686
	* ira-int.h (minmax_set_iter_cond): Use ctz_hwi to elide loop
	skipping bits that are zero.
	(ira_object_conflict_iter_cond): Likewise.
---
 gcc/ira-int.h | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/gcc/ira-int.h b/gcc/ira-int.h
index 957604b22e9..f42a314fa7f 100644
--- a/gcc/ira-int.h
+++ b/gcc/ira-int.h
@@ -764,8 +764,9 @@ minmax_set_iter_cond (minmax_set_iterator *i, int *n)
     }
 
   /* Skip bits that are zero.  */
-  for (; (i->word & 1) == 0; i->word >>= 1)
-    i->bit_num++;
+  int off = ctz_hwi (i->word);
+  i->bit_num += off;
+  i->word >>= off;
 
   *n = (int) i->bit_num + i->start_val;
 
@@ -1379,8 +1380,9 @@ ira_object_conflict_iter_cond (ira_object_conflict_iterator *i,
 	}
 
       /* Skip bits that are zero.  */
-      for (; (word & 1) == 0; word >>= 1)
-	bit_num++;
+      int off = ctz_hwi (word);
+      bit_num += off;
+      word >>= off;
 
       obj = ira_object_id_map[bit_num + i->base_conflict_id];
       i->bit_num = bit_num + 1;
-- 
2.34.1

Re: [PATCH] rtl-optimization/104686 - speed up conflict iteration

[Vladimir Makarov]

On 2022-02-25 09:14, Richard Biener wrote:
> The following replaces
>
>         /* Skip bits that are zero.  */
>         for (; (word & 1) == 0; word >>= 1)
>           bit_num++;
>
> idioms in ira-int.h in the attempt to speedup update_conflict_hard_regno_costs
> which we're bound on in PR104686.  The trick is to use ctz_hwi here
> which should pay off even with dense bitmaps on architectures that
> have HW support for this.
>
> For the PR in question this speeds up compile-time from 31s to 24s for
> me.
It is a really significant improvement.
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> OK for trunk?
Yes.  Thank you for working on this PR, Richard.
> 2022-02-25  Richard Biener  <rguenther@suse.de>
>
> 	PR rtl-optimization/104686
> 	* ira-int.h (minmax_set_iter_cond): Use ctz_hwi to elide loop
> 	skipping bits that are zero.
> 	(ira_object_conflict_iter_cond): Likewise.