1 files changed, 73 insertions, 172 deletions

diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc
index 39a8a89..dea217a 100644
--- a/gcc/tree-switch-conversion.cc
+++ b/gcc/tree-switch-conversion.cc
@@ -1773,122 +1773,108 @@ jump_table_cluster::is_beneficial (const vec<cluster *> &,
   return end - start + 1 >= case_values_threshold ();
 }
 
-/* Find bit tests of given CLUSTERS, where all members of the vector are of
-   type simple_cluster.  Use a fast algorithm that might not find the optimal
-   solution (minimal number of clusters on the output).  New clusters are
-   returned.
-
-   You should call find_bit_tests () instead of calling this function
-   directly.  */
+/* Find bit tests of given CLUSTERS, where all members of the vector
+   are of type simple_cluster.  MAX_C is the approx max number of cases per
+   label.  New clusters are returned.  */
 
 vec<cluster *>
-bit_test_cluster::find_bit_tests_fast (vec<cluster *> &clusters)
+bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c)
 {
-  unsigned l = clusters.length ();
-  vec<cluster *> output;
+  if (!is_enabled () || max_c == 1)
+    return clusters.copy ();
 
-  output.create (l);
+  /* Dynamic programming algorithm.
 
-  /* 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 k;
-  for (unsigned i = 0; i < l; i += k)
-    {
-      hash_set<basic_block> targets;
-      cluster *start_cluster = clusters[i];
+     In: List of simple clusters
+     Out: List of simple clusters and bit test clusters such that each bit test
+     cluster can_be_handled() and is_beneficial()
 
-      /* Find the biggest k such that clusters i to i+k-1 can be turned into a
-	 one big bit test cluster.  */
-      k = 0;
-      while (i + k < l)
-	{
-	  cluster *end_cluster = clusters[i + k];
+     Tries to merge consecutive clusters into bigger (bit test) ones.  Tries to
+     end up with as few clusters as possible.  */
 
-	  /* 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;
+  unsigned l = clusters.length ();
+  auto_vec<min_cluster_item> min;
+  min.reserve (l + 1);
 
-	  /* Check for max # of targets.  */
-	  if (targets.elements () == m_max_case_bit_tests
-	      && !targets.contains (end_cluster->m_case_bb))
-	    break;
+  gcc_checking_assert (l > 0);
+  gcc_checking_assert (l <= INT_MAX);
 
-	  targets.add (end_cluster->m_case_bb);
-	  k++;
-	}
+  int bits_in_word = GET_MODE_BITSIZE (word_mode);
 
-      if (is_beneficial (k, targets.elements ()))
-	{
-	  output.safe_push (new bit_test_cluster (clusters, i, i + k - 1,
-						  i == 0 && k == l));
-	}
-      else
-	{
-	  output.safe_push (clusters[i]);
-	  /* ??? Might be able to skip more.  */
-	  k = 1;
-	}
-    }
+  /* First phase: Compute the minimum number of clusters for each prefix of the
+     input list incrementally
 
-  return output;
-}
-
-/* Find bit tests of given CLUSTERS, where all members of the vector
-   are of type simple_cluster.  Use a slow (quadratic) algorithm that always
-   finds the optimal solution (minimal number of clusters on the output).  New
-   clusters are returned.
+     min[i] = (count, j, _) means that the prefix ending with the (i-1)-th
+     element can be made to contain as few as count clusters and that in such
+     clustering the last cluster is made up of input clusters [j, i-1]
+     (inclusive).  */
+  min.quick_push (min_cluster_item (0, 0, INT_MAX));
+  min.quick_push (min_cluster_item (1, 0, INT_MAX));
+  for (int i = 2; i <= (int) l; i++)
+    {
+      auto_vec<unsigned, m_max_case_bit_tests> unique_labels;
 
-   You should call find_bit_tests () instead of calling this function
-   directly.  */
+      /* Since each cluster contains at least one case number and one bit test
+	 cluster can cover at most bits_in_word case numbers, we don't need to
+	 look farther than bits_in_word clusters back.  */
+      for (int j = i - 1; j >= 0 && j >= i - bits_in_word; j--)
+	{
+	  /* Consider creating a bit test cluster from input clusters [j, i-1]
+	     (inclusive)  */
 
-vec<cluster *>
-bit_test_cluster::find_bit_tests_slow (vec<cluster *> &clusters)
-{
-  unsigned l = clusters.length ();
-  auto_vec<min_cluster_item> min;
-  min.reserve (l + 1);
+	  simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
+	  unsigned label = sc->m_case_bb->index;
+	  if (!unique_labels.contains (label))
+	    {
+	      if (unique_labels.length () >= m_max_case_bit_tests)
+		/* is_beneficial() will be false for this and the following
+		   iterations.  */
+		break;
+	      unique_labels.quick_push (label);
+	    }
 
-  min.quick_push (min_cluster_item (0, 0, 0));
+	  unsigned new_count = min[j].m_count + 1;
 
-  for (unsigned i = 1; i <= l; i++)
-    {
-      /* Set minimal # of clusters with i-th item to infinite.  */
-      min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
+	  if (j == i - 1)
+	    {
+	      min.quick_push (min_cluster_item (new_count, j, INT_MAX));
+	      continue;
+	    }
 
-      for (unsigned j = 0; j < i; j++)
-	{
-	  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);
+	  unsigned HOST_WIDE_INT range
+	    = get_range (clusters[j]->get_low (), clusters[i-1]->get_high ());
+	  if (new_count < min[i].m_count
+	      && can_be_handled (range, unique_labels.length ())
+	      && is_beneficial (i - j, unique_labels.length ()))
+	    min[i] = min_cluster_item (new_count, j, INT_MAX);
 	}
-
-      gcc_checking_assert (min[i].m_count != INT_MAX);
     }
 
-  /* No result.  */
   if (min[l].m_count == l)
+    /* No bit test clustering opportunities.  */
     return clusters.copy ();
 
   vec<cluster *> output;
   output.create (4);
 
-  /* Find and build the clusters.  */
+  /* Second phase: Find and build the bit test clusters by traversing min
+     array backwards.  */
   for (unsigned end = l;;)
     {
-      int start = min[end].m_start;
+      unsigned start = min[end].m_start;
+      gcc_checking_assert (start < end);
 
-      if (is_beneficial (clusters, start, end - 1))
+      /* This cluster will be made out of input clusters [start, end - 1].  */
+
+      if (start == end - 1)
+	/* Let the cluster be a simple cluster.  */
+	output.safe_push (clusters[start]);
+      else
 	{
-	  bool entire = start == 0 && end == clusters.length ();
+	  bool entire = start == 0 && end == l;
 	  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]);
 
       end = start;
 
@@ -1900,25 +1886,6 @@ bit_test_cluster::find_bit_tests_slow (vec<cluster *> &clusters)
   return output;
 }
 
-/* Find bit tests of given CLUSTERS, where all members of the vector
-   are of type simple_cluster.  MAX_C is the approx max number of cases per
-   label.  New clusters are returned.  */
-
-vec<cluster *>
-bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c)
-{
-  if (!is_enabled () || max_c == 1)
-    return clusters.copy ();
-
-  unsigned l = clusters.length ();
-
-  /* Note: l + 1 is the number of cases of the switch.  */
-  if (l + 1 > (unsigned) param_switch_lower_slow_alg_max_cases)
-    return find_bit_tests_fast (clusters);
-  else
-    return find_bit_tests_slow (clusters);
-}
-
 /* Return true when RANGE of case values with UNIQ labels
    can build a bit test.  */
 
@@ -1930,84 +1897,25 @@ bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
   if (range == 0)
     return false;
 
-  if (range >= GET_MODE_BITSIZE (word_mode))
+  if (range > GET_MODE_BITSIZE (word_mode))
     return false;
 
   return uniq <= m_max_case_bit_tests;
 }
 
-/* Return true when cluster starting at START and ending at END (inclusive)
-   can build a bit test.  */
-
-bool
-bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
-				  unsigned start, unsigned end)
-{
-  auto_vec<int, m_max_case_bit_tests> dest_bbs;
-  /* For algorithm correctness, bit test for a single case must return
-     true.  We bail out in is_beneficial if it's called just for
-     a single case.  */
-  if (start == end)
-    return true;
-
-  unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
-					    clusters[end]->get_high ());
-
-  /* Make a guess first.  */
-  if (!can_be_handled (range, m_max_case_bit_tests))
-    return false;
-
-  for (unsigned i = start; i <= end; i++)
-    {
-      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
-      /* m_max_case_bit_tests is very small integer, thus the operation
-	 is constant. */
-      if (!dest_bbs.contains (sc->m_case_bb->index))
-	{
-	  if (dest_bbs.length () >= m_max_case_bit_tests)
-	    return false;
-	  dest_bbs.quick_push (sc->m_case_bb->index);
-	}
-    }
-
-  return true;
-}
-
 /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
    transformation.  */
 
 bool
 bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
 {
+  /* NOTE: When modifying this, keep in mind the value of
+     m_max_case_bit_tests.  */
   return (((uniq == 1 && count >= 3)
 	   || (uniq == 2 && count >= 5)
 	   || (uniq == 3 && count >= 6)));
 }
 
-/* Return true if cluster starting at START and ending at END (inclusive)
-   is profitable transformation.  */
-
-bool
-bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
-				 unsigned start, unsigned end)
-{
-  /* Single case bail out.  */
-  if (start == end)
-    return false;
-
-  auto_bitmap dest_bbs;
-
-  for (unsigned i = start; i <= end; i++)
-    {
-      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
-      bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
-    }
-
-  unsigned uniq = bitmap_count_bits (dest_bbs);
-  unsigned count = end - start + 1;
-  return is_beneficial (count, uniq);
-}
-
 /* Comparison function for qsort to order bit tests by decreasing
    probability of execution.  */
 
@@ -2349,13 +2257,6 @@ switch_decision_tree::analyze_switch_statement ()
 
   reset_out_edges_aux (m_switch);
 
-  if (l > (unsigned) param_switch_lower_slow_alg_max_cases)
-    warning_at (gimple_location (m_switch), OPT_Wdisabled_optimization,
-	       "Using faster switch lowering algorithms. "
-	       "Number of switch cases (%d) exceeds "
-	       "%<--param=switch-lower-slow-alg-max-cases=%d%> limit.",
-	       l, param_switch_lower_slow_alg_max_cases);
-
   /* Find bit-test clusters.  */
   vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters, max_c);