On Mon, Oct 28, 2024 at 9:58 PM Andi Kleen <[email protected]> wrote:
>
> From: Andi Kleen <[email protected]>
>
> 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.
OK.
Thanks,
Richard.
> 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(-)
>
> 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..3436c2a8b98c 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 approx 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 6468995eb316..e6a85fa60258 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. */
> @@ -576,8 +576,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 approx 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. */
> --
> 2.46.2
>
