From df7c79742af79bc2873ca28a8b3037a088444ca7 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Thu, 28 Jun 2018 09:14:57 +0200 Subject: [PATCH] Fix clustering algorithm in switch expansion. 2018-06-28 Martin Liska * 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. 2018-06-28 Martin Liska * gcc.dg/tree-ssa/switch-1.c: New test. From-SVN: r262211 --- gcc/ChangeLog | 15 ++++ gcc/testsuite/ChangeLog | 4 + gcc/testsuite/gcc.dg/tree-ssa/switch-1.c | 110 +++++++++++++++++++++++ gcc/tree-switch-conversion.c | 27 +++++- 4 files changed, 154 insertions(+), 2 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-1.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d4d1d86e2d8..926f8bcac39 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2018-06-28 Martin Liska + + * 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. + 2018-06-28 Martin Liska * common.opt: Introduce -completion option. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 13502600094..4c3c92744c1 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2018-06-28 Martin Liska + + * gcc.dg/tree-ssa/switch-1.c: New test. + 2018-06-28 Eric Botcazou * gnat.dg/debug15.adb: New test. 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 029ce8c363f..ddd8cba7b98 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1121,6 +1121,8 @@ jump_table_cluster::find_jump_tables (vec &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. */ @@ -1172,8 +1174,13 @@ jump_table_cluster::can_be_handled (const vec &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. */ @@ -1197,6 +1204,10 @@ bool jump_table_cluster::is_beneficial (const vec &, unsigned start, unsigned end) { + /* Single case bail out. */ + if (start == end) + return false; + return end - start + 1 >= case_values_threshold (); } @@ -1226,6 +1237,8 @@ bit_test_cluster::find_bit_tests (vec &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. */ @@ -1277,6 +1290,12 @@ bool bit_test_cluster::can_be_handled (const vec &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; @@ -1308,6 +1327,10 @@ bool bit_test_cluster::is_beneficial (const vec &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++) @@ -1599,7 +1622,7 @@ switch_decision_tree::analyze_switch_statement () /* Find jump table clusters. */ vec output = jump_table_cluster::find_jump_tables (clusters); - /* Find jump table clusters. */ + /* Find bit test clusters. */ vec output2; auto_vec tmp; output2.create (1); -- 2.30.2