Revert "Simplify switch bit test clustering algorithm"

This reverts commit 3d06e9c3e07e13eab715e19dafbcfc1a0b7e43d6.

5 files changed, 40 insertions, 47 deletions

diff --git a/gcc/testsuite/gcc.dg/pr21643.c b/gcc/testsuite/gcc.dg/pr21643.c
index a722a83..42517b5 100644
--- a/gcc/testsuite/gcc.dg/pr21643.c
+++ b/gcc/testsuite/gcc.dg/pr21643.c
@@ -1,6 +1,6 @@
 /* PR tree-optimization/21643 */
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1 -fno-bit-tests" } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1" } */
 
 int
 f1 (unsigned char c)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
index 657af77..b164067 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
@@ -39,4 +39,4 @@ int main(int argc, char **argv)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump "Condition chain" "iftoswitch" } } */
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
index f1654ab..6f70c9d 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c
@@ -107,4 +107,4 @@ int foo5 (int x)
   }
 }
 
-/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:10-62 600-700 BT:1000-1021 111111" "switchlower1" } } */
+/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: BT:10-62 600-700 JT:1000-1021 111111" "switchlower1" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr99988.c b/gcc/testsuite/gcc.target/aarch64/pr99988.c
index c09ce67..7cca496 100644
--- a/gcc/testsuite/gcc.target/aarch64/pr99988.c
+++ b/gcc/testsuite/gcc.target/aarch64/pr99988.c
@@ -1,5 +1,5 @@
 /* { dg-do compile { target lp64 } } */
-/* { dg-options "-O2 -mbranch-protection=standard -fno-bit-tests" } */
+/* { dg-options "-O2 -mbranch-protection=standard" } */
 /* { dg-final { scan-assembler-times {bti j} 13 } } */
 int a;
 int c();
diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 9b4ddcd..852419b 100644
--- a/gcc/tree-switch-conversion.cc
+++ b/gcc/tree-switch-conversion.cc
@@ -1783,62 +1783,55 @@ bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c)
     return clusters.copy ();
 
   unsigned l = clusters.length ();
-  vec<cluster *> output;
+  auto_vec<min_cluster_item> min;
+  min.reserve (l + 1);
 
-  output.create (l);
+  min.quick_push (min_cluster_item (0, 0, 0));
 
-  /* Look at sliding BITS_PER_WORD sized windows in the switch value space
-     and determine if they are suitable for a bit test cluster.  Worst case
-     this can examine every value BITS_PER_WORD-1 times.  */
-  unsigned end;
-  for (unsigned i = 0; i < l; i += end)
+  for (unsigned i = 1; i <= l; i++)
     {
-      HOST_WIDE_INT values = 0;
-      hash_set<basic_block> targets;
-      cluster *start_cluster = clusters[i];
+      /* Set minimal # of clusters with i-th item to infinite.  */
+      min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
 
-      end = 0;
-      while (i + end < l)
+      for (unsigned j = 0; j < i; j++)
 	{
-	  cluster *end_cluster = clusters[i + end];
-
-	  /* Does value range fit into the BITS_PER_WORD window?  */
-	  HOST_WIDE_INT w = cluster::get_range (start_cluster->get_low (),
-						end_cluster->get_high ());
-	  if (w == 0 || w > BITS_PER_WORD)
-	    break;
-
-	  /* Compute # of values tested for new case.  */
-	  HOST_WIDE_INT r = 1;
-	  if (!end_cluster->is_single_value_p ())
-	    r = cluster::get_range (end_cluster->get_low (),
-			            end_cluster->get_high ());
-	  if (r == 0)
-	    break;
-
-	  /* Check for max # of targets.  */
-	  if (targets.elements() == m_max_case_bit_tests
-	      && !targets.contains (end_cluster->m_case_bb))
-	    break;
-
-	  targets.add (end_cluster->m_case_bb);
-	  values += r;
-	  end++;
+	  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);
 	}
 
-      if (is_beneficial (values, targets.elements ()))
+      gcc_checking_assert (min[i].m_count != INT_MAX);
+    }
+
+  /* No result.  */
+  if (min[l].m_count == l)
+    return clusters.copy ();
+
+  vec<cluster *> output;
+  output.create (4);
+
+  /* Find and build the clusters.  */
+  for (unsigned end = l;;)
+    {
+      int start = min[end].m_start;
+
+      if (is_beneficial (clusters, start, end - 1))
 	{
-	  output.safe_push (new bit_test_cluster (clusters, i, i + end - 1,
-						  i == 0 && end == l));
+	  bool entire = start == 0 && end == clusters.length ();
+	  output.safe_push (new bit_test_cluster (clusters, start, end - 1,
+						  entire));
 	}
       else
-	{
+	for (int i = end - 1; i >= start; i--)
 	  output.safe_push (clusters[i]);
-	  /* ??? Might be able to skip more.  */
-	  end = 1;
-	}
+
+      end = start;
+
+      if (start <= 0)
+	break;
     }
 
+  output.reverse ();
   return output;
 }