diff mbox series

[2/2] Only do switch bit test clustering when multiple labels point to same bb

Message ID 20241017005100.3620061-2-ak@linux.intel.com
State New
Headers show
Series [1/2] Disable -fbit-tests and -fjump-tables at -O0 | expand

Commit Message

Andi Kleen Oct. 17, 2024, 12:50 a.m. UTC 
From: Andi Kleen <ak@gcc.gnu.org>

The bit cluster code generation strategy is only beneficial when
multiple case labels point to the same code. Do a quick check if
that is the case before trying to cluster.

This fixes the switch part of PR117091 where all case labels are unique
however it doesn't address the performance problems for non unique
cases.

gcc/ChangeLog:

	PR middle-end/117091
	* gimple-if-to-switch.cc (if_chain::is_beneficial): Update
	find_bit_test call.
	* tree-switch-conversion.cc (bit_test_cluster::find_bit_tests):
	Get max_c argument and bail out early if all case labels are
	unique.
	(switch_decision_tree::compute_cases_per_edge): Record number of
	targets per label and return.
	(switch_decision_tree::analyze_switch_statement): ... pass to
	find_bit_tests.
	* tree-switch-conversion.h: Update prototypes.
---
 gcc/gimple-if-to-switch.cc    |  2 +-
 gcc/tree-switch-conversion.cc | 23 ++++++++++++++++-------
 gcc/tree-switch-conversion.h  |  5 +++--
 3 files changed, 20 insertions(+), 10 deletions(-)

Comments

Filip Kastl Oct. 17, 2024, 9:35 a.m. UTC | #1 
Hi Andi,

This seems like a reasonable way to avoid the specific issue in PR117091 and
generally speed up switch lowering of switches with all cases unique.  I cannot
approve this but want to share some comments.

On Wed 2024-10-16 17:50:59, Andi Kleen wrote:
> diff --git a/gcc/gimple-if-to-switch.cc b/gcc/gimple-if-to-switch.cc
> index 96ce1c380a59..4151d1bb520e 100644
> --- a/gcc/gimple-if-to-switch.cc
> +++ b/gcc/gimple-if-to-switch.cc
> @@ -254,7 +254,7 @@ if_chain::is_beneficial ()
>    else
>      output.release ();
>  
> -  output = bit_test_cluster::find_bit_tests (filtered_clusters);
> +  output = bit_test_cluster::find_bit_tests (filtered_clusters, 2);

Maybe it would be nicer to not have max_c as a parameter of find_bit_tests()
but just guard the call to find_bit_tests() in analyze_switch_statement() with
max_c > 2.  Since we don't have max_c in if_chain::is_beneficial(), having
max_c as parameter leads to this constant 2 in this call that will possibly
confuse people reading if_chain::is_beneficial().  But this is a minor thing
and I guess your way (max_c as a parameter) is also fine by me.

>    r = output.length () < filtered_clusters.length ();
>    if (r)
>      dump_clusters (&output, "BT can be built");
> diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
> index 00426d400006..bb7b8cf215a3 100644
> --- a/gcc/tree-switch-conversion.cc
> +++ b/gcc/tree-switch-conversion.cc
> @@ -1772,12 +1772,13 @@ jump_table_cluster::is_beneficial (const vec<cluster *> &,
>  }
>  
>  /* Find bit tests of given CLUSTERS, where all members of the vector
> -   are of type simple_cluster.  New clusters are returned.  */
> +   are of type simple_cluster. max_c is the max number of cases per label.

There should be two spaces before "max_c".  Also it would be nice if MAX_C was
written in uppercase for consistency with other function comments in
tree-switch-conversion.cc.

> @@ -577,8 +577,9 @@ public:
>    bool try_switch_expansion (vec<cluster *> &clusters);
>    /* Compute the number of case labels that correspond to each outgoing edge of
>       switch statement.  Record this information in the aux field of the edge.
> +     Returns max number of cases per edge.
>       */

I would specify "approx max number" instead of "max number" here.

Otherwise looks good to me.

Cheers,
Filip Kastl
diff mbox series

Patch

diff --git a/gcc/gimple-if-to-switch.cc b/gcc/gimple-if-to-switch.cc
index 96ce1c380a59..4151d1bb520e 100644
--- a/gcc/gimple-if-to-switch.cc
+++ b/gcc/gimple-if-to-switch.cc
@@ -254,7 +254,7 @@  if_chain::is_beneficial ()
   else
     output.release ();
 
-  output = bit_test_cluster::find_bit_tests (filtered_clusters);
+  output = bit_test_cluster::find_bit_tests (filtered_clusters, 2);
   r = output.length () < filtered_clusters.length ();
   if (r)
     dump_clusters (&output, "BT can be built");
diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 00426d400006..bb7b8cf215a3 100644
--- a/gcc/tree-switch-conversion.cc
+++ b/gcc/tree-switch-conversion.cc
@@ -1772,12 +1772,13 @@  jump_table_cluster::is_beneficial (const vec<cluster *> &,
 }
 
 /* Find bit tests of given CLUSTERS, where all members of the vector
-   are of type simple_cluster.  New clusters are returned.  */
+   are of type simple_cluster. max_c is the max number of cases per label.
+   New clusters are returned.  */
 
 vec<cluster *>
-bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
+bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c)
 {
-  if (!is_enabled ())
+  if (!is_enabled () || max_c == 1)
     return clusters.copy ();
 
   unsigned l = clusters.length ();
@@ -2206,18 +2207,26 @@  bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
 }
 
 /* Compute the number of case labels that correspond to each outgoing edge of
-   switch statement.  Record this information in the aux field of the edge.  */
+   switch statement.  Record this information in the aux field of the edge.
+   Return the approx max number of cases per edge.  */
 
-void
+int
 switch_decision_tree::compute_cases_per_edge ()
 {
+  int max_c = 0;
   reset_out_edges_aux (m_switch);
   int ncases = gimple_switch_num_labels (m_switch);
   for (int i = ncases - 1; i >= 1; --i)
     {
       edge case_edge = gimple_switch_edge (cfun, m_switch, i);
       case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
+      /* For a range case add one extra. That's enough for the bit
+	 cluster heuristic.  */
+      if ((intptr_t)case_edge->aux > max_c)
+	max_c = (intptr_t)case_edge->aux +
+		!!CASE_HIGH (gimple_switch_label (m_switch, i));
     }
+  return max_c;
 }
 
 /* Analyze switch statement and return true when the statement is expanded
@@ -2235,7 +2244,7 @@  switch_decision_tree::analyze_switch_statement ()
   m_case_bbs.reserve (l);
   m_case_bbs.quick_push (default_bb);
 
-  compute_cases_per_edge ();
+  int max_c = compute_cases_per_edge ();
 
   for (unsigned i = 1; i < l; i++)
     {
@@ -2256,7 +2265,7 @@  switch_decision_tree::analyze_switch_statement ()
   reset_out_edges_aux (m_switch);
 
   /* Find bit-test clusters.  */
-  vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters);
+  vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters, max_c);
 
   /* Find jump table clusters.  */
   vec<cluster *> output2;
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index fbfd7ff7b3ff..15f919f24f9f 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -399,7 +399,7 @@  public:
 
   /* Find bit tests of given CLUSTERS, where all members of the vector
      are of type simple_cluster.  New clusters are returned.  */
-  static vec<cluster *> find_bit_tests (vec<cluster *> &clusters);
+  static vec<cluster *> find_bit_tests (vec<cluster *> &clusters, int max_c);
 
   /* Return true when RANGE of case values with UNIQ labels
      can build a bit test.  */
@@ -577,8 +577,9 @@  public:
   bool try_switch_expansion (vec<cluster *> &clusters);
   /* Compute the number of case labels that correspond to each outgoing edge of
      switch statement.  Record this information in the aux field of the edge.
+     Returns max number of cases per edge.
      */
-  void compute_cases_per_edge ();
+  int compute_cases_per_edge ();
 
   /* Before switch transformation, record all SSA_NAMEs defined in switch BB
      and used in a label basic block.  */