[PATCH] switch lowering: limit number of cluster attemps

[Martin Liška]

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