From c6df6039e9180c580945266302ec14047d358364 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Tue, 22 Sep 2020 12:23:35 +0200 Subject: [PATCH] switch lowering: limit number of cluster attemps gcc/ChangeLog: PR tree-optimization/96979 * doc/invoke.texi: Document new param max-switch-clustering-attempts. * params.opt: Add new parameter. * tree-switch-conversion.c (jump_table_cluster::find_jump_tables): Limit number of attempts. (bit_test_cluster::find_bit_tests): Likewise. gcc/testsuite/ChangeLog: PR tree-optimization/96979 * g++.dg/tree-ssa/pr96979.C: New test. --- gcc/doc/invoke.texi | 4 ++ gcc/params.opt | 4 ++ gcc/testsuite/g++.dg/tree-ssa/pr96979.C | 50 +++++++++++++++++++++++++ gcc/tree-switch-conversion.c | 17 +++++++++ 4 files changed, 75 insertions(+) create mode 100644 gcc/testsuite/g++.dg/tree-ssa/pr96979.C diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 665c0ffc4a1..6a7833b1d75 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -13452,6 +13452,10 @@ The smallest number of different values for which it is best to use a jump-table instead of a tree of conditional branches. If the value is 0, use the default for the machine. +@item max-switch-clustering-attempts +The maximum number of clustering attempts used +in bit-test and jump-table switch expansion. + @item jump-table-max-growth-ratio-for-size The maximum code size growth ratio when expanding into a jump table (in percent). The parameter is used when diff --git a/gcc/params.opt b/gcc/params.opt index dcf5e020f01..5f2e11d6c57 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -82,6 +82,10 @@ The maximum length of a constant string for a builtin string cmp call eligible f Common Joined UInteger Var(param_case_values_threshold) Param Optimization The smallest number of different values for which it is best to use a jump-table instead of a tree of conditional branches, if 0, use the default for the machine. +-param=max-switch-clustering-attempts= +Common Joined UInteger Var(param_max_switch_clustering_attempts) Param Optimization Init(10000) +The maximum number of clustering attempts used in bit-test and jump-table switch expansion. + -param=comdat-sharing-probability= Common Joined UInteger Var(param_comdat_sharing_probability) Init(20) Param Optimization Probability that COMDAT function will be shared with different compilation unit. diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr96979.C b/gcc/testsuite/g++.dg/tree-ssa/pr96979.C new file mode 100644 index 00000000000..85c703a140d --- /dev/null +++ b/gcc/testsuite/g++.dg/tree-ssa/pr96979.C @@ -0,0 +1,50 @@ +/* PR tree-optimization/96979 */ +/* { dg-do compile } */ +/* { dg-options "-std=c++17 -O2 -fdump-tree-switchlower1" } */ + +using u64 = unsigned long long; + +constexpr inline u64 +foo (const char *str) noexcept +{ + u64 value = 0xcbf29ce484222325ULL; + for (u64 i = 0; str[i]; i++) + value = (value ^ u64(str[i])) * 0x100000001b3ULL; + return value; +} + +struct V +{ + enum W + { +#define A(n) n, +#define B(n) A(n##0) A(n##1) A(n##2) A(n##3) A(n##4) A(n##5) A(n##6) A(n##7) A(n##8) A(n##9) +#define C(n) B(n##0) B(n##1) B(n##2) B(n##3) B(n##4) B(n##5) B(n##6) B(n##7) B(n##8) B(n##9) +#define D(n) C(n##0) C(n##1) C(n##2) C(n##3) C(n##4) C(n##5) C(n##6) C(n##7) C(n##8) C(n##9) +#define E D(foo1) D(foo2) D(foo3) + E + last + }; + + constexpr static W + bar (const u64 h) noexcept + { + switch (h) + { +#undef A +#define F(n) #n +#define A(n) case foo (F(n)): return n; + E + } + return last; + } +}; + +int +baz (const char *s) +{ + const u64 h = foo (s); + return V::bar (h); +} + +/* { dg-final { scan-tree-dump-times ";; Bail out: --param=max-switch-clustering-attempts reached" 2 "switchlower1" } } */ diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 186411ff3c4..e6a2c7a6a84 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1183,6 +1183,7 @@ jump_table_cluster::find_jump_tables (vec &clusters) min.quick_push (min_cluster_item (0, 0, 0)); + HOST_WIDE_INT attempts = 0; for (unsigned i = 1; i <= l; i++) { /* Set minimal # of clusters with i-th item to infinite. */ @@ -1194,6 +1195,14 @@ jump_table_cluster::find_jump_tables (vec &clusters) if (i - j < case_values_threshold ()) s += i - j; + if (attempts++ == param_max_switch_clustering_attempts) + { + if (dump_file) + fprintf (dump_file, ";; Bail out: " + "--param=max-switch-clustering-attempts reached\n"); + return clusters.copy (); + } + /* 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 @@ -1308,6 +1317,7 @@ bit_test_cluster::find_bit_tests (vec &clusters) min.quick_push (min_cluster_item (0, 0, 0)); + HOST_WIDE_INT attempts = 0; for (unsigned i = 1; i <= l; i++) { /* Set minimal # of clusters with i-th item to infinite. */ @@ -1315,6 +1325,13 @@ bit_test_cluster::find_bit_tests (vec &clusters) for (unsigned j = 0; j < i; j++) { + if (attempts++ == param_max_switch_clustering_attempts) + { + if (dump_file) + fprintf (dump_file, ";; Bail out: " + "--param=max-switch-clustering-attempts reached\n"); + return clusters.copy (); + } 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); -- 2.30.2