Hi.
For correctness of clustering algorithm:
https://www.semanticscholar.org/paper/Short-Communication%3A-Correction-to-'Producing-Good-Kannan-Proebsting/311091fb9fb9d38f7b76e768a603c02acc799fe0
one needs to allow single case clusters as possible. Note that we never
end with a jump table, or a bit test handling just a single case.
I also add tests for that catch that.
Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
Ready to be installed?
Martin
gcc/ChangeLog:
2018-06-21 Martin Liska <mli...@suse.cz>
* tree-switch-conversion.c (jump_table_cluster::find_jump_tables):
Add new checking assert to catch invalid state.
(jump_table_cluster::can_be_handled): Handle single case
clusters.
(jump_table_cluster::is_beneficial): Bail out for such case.
(bit_test_cluster::find_bit_tests):
Add new checking assert to catch invalid state.
(bit_test_cluster::can_be_handled): Handle single case
clusters.
(bit_test_cluster::is_beneficial): Bail out for such case.
(switch_decision_tree::analyze_switch_statement):
Fix comment.
gcc/testsuite/ChangeLog:
2018-06-21 Martin Liska <mli...@suse.cz>
* gcc.dg/tree-ssa/switch-1.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/switch-1.c | 110 +++++++++++++++++++++++
gcc/tree-switch-conversion.c | 27 +++++-
2 files changed, 135 insertions(+), 2 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
new file mode 100644
index 00000000000..149687ca2bb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
@@ -0,0 +1,110 @@
+/* { dg-do compile { target { { x86_64-*-* aarch64-*-* ia64-*-* powerpc64-*-* } && lp64 } } } */
+/* { dg-options "-O2 -fdump-tree-switchlower1 --param case-values-threshold=4" } */
+
+int global;
+
+int foo (int x)
+{
+ switch (x) {
+ case 0:
+ case 10:
+ case 1000:
+ case 1010:
+ case 1025 ... 1030:
+ return 1;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: 0 10 BT:1000-1030" "switchlower1" } } */
+
+int foo2 (int x)
+{
+ switch (x) {
+ case -100:
+ case 100:
+ case 1000:
+ case 10000:
+ case 100000:
+ return 1;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: -100 100 1000 10000 100000" "switchlower1" } } */
+
+int foo3 (int x)
+{
+ switch (x) {
+ case 0:
+ case 10:
+ case 20:
+ global += 1;
+ return 3;
+ case 30:
+ case 33 ... 55:
+ case 57:
+ return 4;
+ case 60 ... 62:
+ return 1;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: JT:0-62" "switchlower1" } } */
+
+int foo4 (int x)
+{
+ switch (x) {
+ case -100:
+ case 10:
+ case 20:
+ global += 1;
+ return 3;
+ case 30:
+ case 33 ... 55:
+ case 57:
+ return 4;
+ case 60 ... 62:
+ return 1;
+ case 600 ... 700:
+ return 12;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: -100 JT:10-62 600-700" "switchlower1" } } */
+
+int foo5 (int x)
+{
+ switch (x) {
+ case 10:
+ case 20:
+ global += 1;
+ return 3;
+ case 30:
+ case 33 ... 55:
+ case 57:
+ return 4;
+ case 60 ... 62:
+ return 1;
+ case 600 ... 700:
+ return 12;
+ case 1000 ... 1010:
+ case 1012:
+ return 333;
+ case 1019:
+ case 1021:
+ return 9;
+ case 111111:
+ return 3;
+ default:
+ return 0;
+ }
+}
+
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: JT:10-62 600-700 JT:1000-1021 111111" "switchlower1" } } */
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 62ae8849474..5048a6cb951 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1118,6 +1118,8 @@ jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
&& can_be_handled (clusters, j, i - 1))
min[i] = min_cluster_item (min[j].m_count + 1, j, s);
}
+
+ gcc_checking_assert (min[i].m_count != INT_MAX);
}
/* No result. */
@@ -1169,8 +1171,13 @@ jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
if (!flag_jump_tables)
return false;
- unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 8;
+ /* For algorithm correctness, jump table for a single case must return
+ true. We bail out in is_beneficial if it's called just for
+ a single case. */
+ if (start == end)
+ return true;
+ unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 8;
unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
clusters[end]->get_high ());
/* Check overflow. */
@@ -1194,6 +1201,10 @@ bool
jump_table_cluster::is_beneficial (const vec<cluster *> &,
unsigned start, unsigned end)
{
+ /* Single case bail out. */
+ if (start == end)
+ return false;
+
return end - start + 1 >= case_values_threshold ();
}
@@ -1223,6 +1234,8 @@ bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
&& can_be_handled (clusters, j, i - 1))
min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
}
+
+ gcc_checking_assert (min[i].m_count != INT_MAX);
}
/* No result. */
@@ -1274,6 +1287,12 @@ bool
bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
unsigned start, unsigned end)
{
+ /* For algorithm correctness, bit test for a single case must return
+ true. We bail out in is_beneficial if it's called just for
+ a single case. */
+ if (start == end)
+ return true;
+
unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
clusters[end]->get_high ());
auto_bitmap dest_bbs;
@@ -1305,6 +1324,10 @@ bool
bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
unsigned start, unsigned end)
{
+ /* Single case bail out. */
+ if (start == end)
+ return false;
+
auto_bitmap dest_bbs;
for (unsigned i = start; i <= end; i++)
@@ -1596,7 +1619,7 @@ switch_decision_tree::analyze_switch_statement ()
/* Find jump table clusters. */
vec<cluster *> output = jump_table_cluster::find_jump_tables (clusters);
- /* Find jump table clusters. */
+ /* Find bit test clusters. */
vec<cluster *> output2;
auto_vec<cluster *> tmp;
output2.create (1);
