From 2f928c1b63e67155f4b3c194e3a9cc53fb6fb107 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Wed, 20 Jun 2018 10:52:35 +0200 Subject: [PATCH] Enable clustering for switch statements. 2018-06-20 Martin Liska * tree-switch-conversion.c (jump_table_cluster::find_jump_tables): New. (bit_test_cluster::find_bit_tests): Likewise. (switch_decision_tree::analyze_switch_statement): Find clusters. * tree-switch-conversion.h (struct jump_table_cluster): Document hierarchy. From-SVN: r261794 --- gcc/ChangeLog | 9 ++ gcc/tree-switch-conversion.c | 176 +++++++++++++++++++++++++++++++---- gcc/tree-switch-conversion.h | 19 +++- 3 files changed, 184 insertions(+), 20 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 4b919a8c957..4106e041598 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2018-06-20 Martin Liska + + * tree-switch-conversion.c (jump_table_cluster::find_jump_tables): + New. + (bit_test_cluster::find_bit_tests): Likewise. + (switch_decision_tree::analyze_switch_statement): Find clusters. + * tree-switch-conversion.h (struct jump_table_cluster): Document + hierarchy. + 2018-06-20 Martin Liska * tree-switch-conversion.c (switch_conversion::collect): diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 1260ba2e145..a438960f8bf 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1088,6 +1088,67 @@ jump_table_cluster::emit (tree index_expr, tree, gsi_insert_after (&gsi, s, GSI_NEW_STMT); } +/* Find jump tables of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ + +vec +jump_table_cluster::find_jump_tables (vec &clusters) +{ + unsigned l = clusters.length (); + auto_vec min; + min.reserve (l + 1); + + min.quick_push (min_cluster_item (0, 0, 0)); + + for (unsigned i = 1; i <= l; i++) + { + /* Set minimal # of clusters with i-th item to infinite. */ + min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); + + for (unsigned j = 0; j < i; j++) + { + unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases; + if (i - j < case_values_threshold ()) + s += i - j; + + /* Prefer clusters with smaller number of numbers covered. */ + if ((min[j].m_count + 1 < min[i].m_count + || (min[j].m_count + 1 == min[i].m_count + && s < min[i].m_non_jt_cases)) + && can_be_handled (clusters, j, i - 1)) + min[i] = min_cluster_item (min[j].m_count + 1, j, s); + } + } + + /* No result. */ + if (min[l].m_count == INT_MAX) + return clusters.copy (); + + vec output; + output.create (4); + + /* Find and build the clusters. */ + for (int end = l;;) + { + int start = min[end].m_start; + + /* Do not allow clusters with small number of cases. */ + if (is_beneficial (clusters, start, end - 1)) + output.safe_push (new jump_table_cluster (clusters, start, end - 1)); + else + for (int i = end - 1; i >= start; i--) + output.safe_push (clusters[i]); + + end = start; + + if (start <= 0) + break; + } + + output.reverse (); + return output; +} + /* Return true when cluster starting at START and ending at END (inclusive) can build a jump-table. */ @@ -1142,6 +1203,59 @@ jump_table_cluster::is_beneficial (const vec &, return end - start + 1 >= case_values_threshold (); } +/* Find bit tests of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ + +vec +bit_test_cluster::find_bit_tests (vec &clusters) +{ + vec output; + output.create (4); + + unsigned l = clusters.length (); + auto_vec min; + min.reserve (l + 1); + + min.quick_push (min_cluster_item (0, 0, 0)); + + for (unsigned i = 1; i <= l; i++) + { + /* Set minimal # of clusters with i-th item to infinite. */ + min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); + + for (unsigned j = 0; j < i; j++) + { + if (min[j].m_count + 1 < min[i].m_count + && can_be_handled (clusters, j, i - 1)) + min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX); + } + } + + /* No result. */ + if (min[l].m_count == INT_MAX) + return clusters.copy (); + + /* Find and build the clusters. */ + for (int end = l;;) + { + int start = min[end].m_start; + + if (is_beneficial (clusters, start, end - 1)) + output.safe_push (new bit_test_cluster (clusters, start, end - 1)); + else + for (int i = end - 1; i >= start; i--) + output.safe_push (clusters[i]); + + end = start; + + if (start <= 0) + break; + } + + output.reverse (); + return output; +} + /* Return true when RANGE of case values with UNIQ labels can build a bit test. */ @@ -1485,33 +1599,57 @@ switch_decision_tree::analyze_switch_statement () reset_out_edges_aux (); - vec output; - output.create (1); - - /* Find whether the switch statement can be expanded with a method - different from decision tree. */ - unsigned end = clusters.length () - 1; - if (jump_table_cluster::can_be_handled (clusters, 0, end) - && jump_table_cluster::is_beneficial (clusters, 0, end)) - output.safe_push (new jump_table_cluster (clusters, 0, end)); - else if (bit_test_cluster::can_be_handled (clusters, 0, end) - && bit_test_cluster::is_beneficial (clusters, 0, end)) - output.safe_push (new bit_test_cluster (clusters, 0, end)); - else - output = clusters; + /* Find jump table clusters. */ + vec output = jump_table_cluster::find_jump_tables (clusters); + + /* Find jump table clusters. */ + vec output2; + auto_vec tmp; + output2.create (1); + tmp.create (1); + + for (unsigned i = 0; i < output.length (); i++) + { + cluster *c = output[i]; + if (c->get_type () != SIMPLE_CASE) + { + if (!tmp.is_empty ()) + { + vec n = bit_test_cluster::find_bit_tests (tmp); + output2.safe_splice (n); + n.release (); + tmp.truncate (0); + } + output2.safe_push (c); + } + else + tmp.safe_push (c); + } + + /* We still can have a temporary vector to test. */ + if (!tmp.is_empty ()) + { + vec n = bit_test_cluster::find_bit_tests (tmp); + output2.safe_splice (n); + n.release (); + } if (dump_file) { fprintf (dump_file, ";; GIMPLE switch case clusters: "); - for (unsigned i = 0; i < output.length (); i++) - output[i]->dump (dump_file, dump_flags & TDF_DETAILS); + for (unsigned i = 0; i < output2.length (); i++) + output2[i]->dump (dump_file, dump_flags & TDF_DETAILS); fprintf (dump_file, "\n"); } - bool expanded = try_switch_expansion (output); + output.release (); - for (unsigned i = 0; i < output.length (); i++) - delete output[i]; + bool expanded = try_switch_expansion (output2); + + for (unsigned i = 0; i < output2.length (); i++) + delete output2[i]; + + output2.release (); return expanded; } diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index 946077c25ec..03352832cb4 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -33,7 +33,16 @@ enum cluster_type #define PRINT_CASE(f,c) print_generic_expr (f, c) -/* Abstract base class for representing a cluster of cases. */ +/* Abstract base class for representing a cluster of cases. + + Here is the inheritance hierarachy, and the enum_cluster_type + values for the concrete subclasses: + + cluster + |-simple_cluster (SIMPLE_CASE) + `-group_cluster + |-jump_table_cluster (JUMP_TABLE) + `-bit_test_cluster (BIT_TEST). */ struct cluster { @@ -228,6 +237,10 @@ struct jump_table_cluster: public group_cluster void emit (tree index_expr, tree index_type, tree default_label_expr, basic_block default_bb); + /* Find jump tables of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ + static vec find_jump_tables (vec &clusters); + /* Return true when cluster starting at START and ending at END (inclusive) can build a jump-table. */ static bool can_be_handled (const vec &clusters, unsigned start, @@ -336,6 +349,10 @@ struct bit_test_cluster: public group_cluster void emit (tree index_expr, tree index_type, tree default_label_expr, basic_block default_bb); + /* Find bit tests of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ + static vec find_bit_tests (vec &clusters); + /* Return true when RANGE of case values with UNIQ labels can build a bit test. */ static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq); -- 2.30.2