On September 22, 2020 1:22:12 PM GMT+02:00, "Martin Liška" <mli...@suse.cz> wrote: >Hi. > >The patch is about a bail out limit that needs to be added to switch >lowering. >Currently the algorithm is quadratic and needs some bail out. I've >tested value >of 100K which corresponds to about 0.2s in the problematic test-case >before >it's reached. > >Patch can bootstrap on x86_64-linux-gnu and survives regression tests. > >Ready to be installed?
OK. Though the default limit looks high? Richard. >Thanks, >Martin > >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 1d864047ad2..f4dcb5426c7 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(100000) >+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<cluster >*> &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<cluster *> &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<cluster *> >&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<cluster *> >&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);