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);

Reply via email to