[Fortran] Fix error cleanup of select rank (PR93522)
[gcc.git] / gcc / tree-switch-conversion.c
index 47acb0c8ae884e15000128200848be0c92c5a094..bf910dd62b538cba2984d031e061b9499470c602 100644 (file)
@@ -1,6 +1,6 @@
 /* Lower GIMPLE_SWITCH expressions to something more efficient than
    a jump table.
-   Copyright (C) 2006-2018 Free Software Foundation, Inc.
+   Copyright (C) 2006-2020 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -36,7 +36,6 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "optabs-tree.h"
 #include "cgraph.h"
 #include "gimple-pretty-print.h"
-#include "params.h"
 #include "fold-const.h"
 #include "varasm.h"
 #include "stor-layout.h"
@@ -44,6 +43,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "gimplify.h"
 #include "gimple-iterator.h"
 #include "gimplify-me.h"
+#include "gimple-fold.h"
 #include "tree-cfg.h"
 #include "cfgloop.h"
 #include "alloc-pool.h"
@@ -61,7 +61,7 @@ using namespace tree_switch_conversion;
 
 /* Constructor.  */
 
-switch_conversion::switch_conversion (): m_final_bb (NULL), m_other_count (),
+switch_conversion::switch_conversion (): m_final_bb (NULL),
   m_constructors (NULL), m_default_values (NULL),
   m_arr_ref_first (NULL), m_arr_ref_last (NULL),
   m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false)
@@ -89,10 +89,6 @@ switch_conversion::collect (gswitch *swtch)
   e_default = gimple_switch_default_edge (cfun, swtch);
   m_default_bb = e_default->dest;
   m_default_prob = e_default->probability;
-  m_default_count = e_default->count ();
-  FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
-    if (e != e_default)
-      m_other_count += e->count ();
 
   /* Get upper and lower bounds of case values, and the covered range.  */
   min_case = gimple_switch_label (swtch, 1);
@@ -193,7 +189,7 @@ switch_conversion::check_range ()
     }
 
   if (tree_to_uhwi (m_range_size)
-      > ((unsigned) m_count * SWITCH_CONVERSION_BRANCH_RATIO))
+      > ((unsigned) m_count * param_switch_conversion_branch_ratio))
     {
       m_reason = "the maximum range-branch ratio exceeded";
       return false;
@@ -439,25 +435,65 @@ switch_conversion::build_constructors ()
     }
 }
 
-/* If all values in the constructor vector are the same, return the value.
-   Otherwise return NULL_TREE.  Not supposed to be called for empty
-   vectors.  */
+/* If all values in the constructor vector are products of a linear function
+   a * x + b, then return true.  When true, COEFF_A and COEFF_B and
+   coefficients of the linear function.  Note that equal values are special
+   case of a linear function with a and b equal to zero.  */
 
-tree
-switch_conversion::contains_same_values_p (vec<constructor_elt, va_gc> *vec)
+bool
+switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
+                                              wide_int *coeff_a,
+                                              wide_int *coeff_b)
 {
   unsigned int i;
-  tree prev = NULL_TREE;
   constructor_elt *elt;
 
+  gcc_assert (vec->length () >= 2);
+
+  /* Let's try to find any linear function a * x + y that can apply to
+     given values. 'a' can be calculated as follows:
+
+     a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
+     a = y2 - y1
+
+     and
+
+     b = y2 - a * x2
+
+  */
+
+  tree elt0 = (*vec)[0].value;
+  tree elt1 = (*vec)[1].value;
+
+  if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
+    return false;
+
+  wide_int range_min
+    = wide_int::from (wi::to_wide (m_range_min),
+                     TYPE_PRECISION (TREE_TYPE (elt0)),
+                     TYPE_SIGN (TREE_TYPE (m_range_min)));
+  wide_int y1 = wi::to_wide (elt0);
+  wide_int y2 = wi::to_wide (elt1);
+  wide_int a = y2 - y1;
+  wide_int b = y2 - a * (range_min + 1);
+
+  /* Verify that all values fulfill the linear function.  */
   FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
     {
-      if (!prev)
-       prev = elt->value;
-      else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
-       return NULL_TREE;
+      if (TREE_CODE (elt->value) != INTEGER_CST)
+       return false;
+
+      wide_int value = wi::to_wide (elt->value);
+      if (a * range_min + b != value)
+       return false;
+
+      ++range_min;
     }
-  return prev;
+
+  *coeff_a = a;
+  *coeff_b = b;
+
+  return true;
 }
 
 /* Return type which should be used for array elements, either TYPE's
@@ -551,7 +587,7 @@ void
 switch_conversion::build_one_array (int num, tree arr_index_type,
                                    gphi *phi, tree tidx)
 {
-  tree name, cst;
+  tree name;
   gimple *load;
   gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
   location_t loc = gimple_location (m_switch);
@@ -561,9 +597,29 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
   name = copy_ssa_name (PHI_RESULT (phi));
   m_target_inbound_names[num] = name;
 
-  cst = contains_same_values_p (m_constructors[num]);
-  if (cst)
-    load = gimple_build_assign (name, cst);
+  vec<constructor_elt, va_gc> *constructor = m_constructors[num];
+  wide_int coeff_a, coeff_b;
+  bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
+  tree type;
+  if (linear_p
+      && (type = range_check_type (TREE_TYPE ((*constructor)[0].value))))
+    {
+      if (dump_file && coeff_a.to_uhwi () > 0)
+       fprintf (dump_file, "Linear transformation with A = %" PRId64
+                " and B = %" PRId64 "\n", coeff_a.to_shwi (),
+                coeff_b.to_shwi ());
+
+      /* We must use type of constructor values.  */
+      gimple_seq seq = NULL;
+      tree tmp = gimple_convert (&seq, type, m_index_expr);
+      tree tmp2 = gimple_build (&seq, MULT_EXPR, type,
+                               wide_int_to_tree (type, coeff_a), tmp);
+      tree tmp3 = gimple_build (&seq, PLUS_EXPR, type, tmp2,
+                               wide_int_to_tree (type, coeff_b));
+      tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
+      gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
+      load = gimple_build_assign (name, tmp4);
+    }
   else
     {
       tree array_type, ctor, decl, value_type, fetch, default_type;
@@ -576,10 +632,10 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
          unsigned int i;
          constructor_elt *elt;
 
-         FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
+         FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
            elt->value = fold_convert (value_type, elt->value);
        }
-      ctor = build_constructor (array_type, m_constructors[num]);
+      ctor = build_constructor (array_type, constructor);
       TREE_CONSTANT (ctor) = true;
       TREE_STATIC (ctor) = true;
 
@@ -1153,14 +1209,14 @@ jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
     }
 
   /* No result.  */
-  if (min[l].m_count == INT_MAX)
+  if (min[l].m_count == l)
     return clusters.copy ();
 
   vec<cluster *> output;
   output.create (4);
 
   /* Find and build the clusters.  */
-  for (int end = l;;)
+  for (unsigned int end = l;;)
     {
       int start = min[end].m_start;
 
@@ -1197,18 +1253,18 @@ jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
      make a sequence of conditional branches instead of a dispatch.
 
      The definition of "much bigger" depends on whether we are
-     optimizing for size or for speed.  */
-  if (!flag_jump_tables)
-    return false;
+     optimizing for size or for speed.
 
-  /* For algorithm correctness, jump table for a single case must return
+     For algorithm correctness, jump table 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 max_ratio
-    = optimize_insn_for_size_p () ? max_ratio_for_size : max_ratio_for_speed;
+    = (optimize_insn_for_size_p ()
+       ? param_jump_table_max_growth_ratio_for_size
+       : param_jump_table_max_growth_ratio_for_speed);
   unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
                                            clusters[end]->get_high ());
   /* Check overflow.  */
@@ -1222,7 +1278,11 @@ jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
       comparison_count += sc->m_range_p ? 2 : 1;
     }
 
-  return range <= max_ratio * comparison_count;
+  unsigned HOST_WIDE_INT lhs = 100 * range;
+  if (lhs < range)
+    return false;
+
+  return lhs <= max_ratio * comparison_count;
 }
 
 /* Return true if cluster starting at START and ending at END (inclusive)
@@ -1239,20 +1299,12 @@ jump_table_cluster::is_beneficial (const vec<cluster *> &,
   return end - start + 1 >= case_values_threshold ();
 }
 
-/* Definition of jump_table_cluster constants.  */
-
-const unsigned HOST_WIDE_INT jump_table_cluster::max_ratio_for_size;
-const unsigned HOST_WIDE_INT jump_table_cluster::max_ratio_for_speed;
-
 /* Find bit tests of given CLUSTERS, where all members of the vector
    are of type simple_cluster.  New clusters are returned.  */
 
 vec<cluster *>
 bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
 {
-  vec<cluster *> output;
-  output.create (4);
-
   unsigned l = clusters.length ();
   auto_vec<min_cluster_item> min;
   min.reserve (l + 1);
@@ -1275,9 +1327,12 @@ bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
     }
 
   /* No result.  */
-  if (min[l].m_count == INT_MAX)
+  if (min[l].m_count == l)
     return clusters.copy ();
 
+  vec<cluster *> output;
+  output.create (4);
+
   /* Find and build the clusters.  */
   for (unsigned end = l;;)
     {
@@ -1290,7 +1345,7 @@ bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
                                                  entire));
        }
       else
-       for (int i = end - 1; i >=  start; i--)
+       for (int i = end - 1; i >= start; i--)
          output.safe_push (clusters[i]);
 
       end = start;
@@ -1387,8 +1442,8 @@ bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
 int
 case_bit_test::cmp (const void *p1, const void *p2)
 {
-  const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
-  const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
+  const case_bit_test *const d1 = (const case_bit_test *) p1;
+  const case_bit_test *const d2 = (const case_bit_test *) p2;
 
   if (d2->bits != d1->bits)
     return d2->bits - d1->bits;
@@ -1419,11 +1474,11 @@ void
 bit_test_cluster::emit (tree index_expr, tree index_type,
                        tree, basic_block default_bb)
 {
-  struct case_bit_test test[m_max_case_bit_tests] = { {} };
+  case_bit_test test[m_max_case_bit_tests] = { {} };
   unsigned int i, j, k;
   unsigned int count;
 
-  tree unsigned_index_type = unsigned_type_for (index_type);
+  tree unsigned_index_type = range_check_type (index_type);
 
   gimple_stmt_iterator gsi;
   gassign *shift_stmt;
@@ -1733,7 +1788,8 @@ switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
   tree index_type = TREE_TYPE (index_expr);
   basic_block bb = gimple_bb (m_switch);
 
-  if (gimple_switch_num_labels (m_switch) == 1)
+  if (gimple_switch_num_labels (m_switch) == 1
+      || range_check_type (index_type) == NULL_TREE)
     return false;
 
   /* Find the default case target label.  */
@@ -1773,6 +1829,7 @@ switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
     if (clusters[i]->get_type () != SIMPLE_CASE)
       {
        clusters[i]->m_case_bb = create_empty_bb (bb);
+       clusters[i]->m_case_bb->count = bb->count;
        clusters[i]->m_case_bb->loop_father = bb->loop_father;
       }
 
@@ -1885,7 +1942,8 @@ switch_decision_tree::emit (basic_block bb, tree index_expr,
       dump_case_nodes (dump_file, m_case_list, indent_step, 0);
     }
 
-  bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type);
+  bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type,
+                       gimple_location (m_switch));
 
   if (bb)
     emit_jump (bb, m_default_bb);
@@ -1921,6 +1979,7 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head,
       int ranges = 0;
       case_tree_node **npp;
       case_tree_node *left;
+      profile_probability prob = profile_probability::never ();
 
       /* Count the number of entries on branch.  Also count the ranges.  */
 
@@ -1930,6 +1989,7 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head,
            ranges++;
 
          i++;
+         prob += np->m_c->m_prob;
          np = np->m_right;
        }
 
@@ -1938,39 +1998,35 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head,
          /* Split this list if it is long enough for that to help.  */
          npp = head;
          left = *npp;
+         profile_probability pivot_prob = prob.apply_scale (1, 2);
 
-         /* If there are just three nodes, split at the middle one.  */
-         if (i == 3)
-           npp = &(*npp)->m_right;
-         else
+         /* Find the place in the list that bisects the list's total cost,
+            where ranges count as 2.  */
+         while (1)
            {
-             /* Find the place in the list that bisects the list's total cost,
-                where ranges count as 2.
-                Here I gets half the total cost.  */
-             i = (i + ranges + 1) / 2;
-             while (1)
-               {
-                 /* Skip nodes while their cost does not reach that amount.  */
-                 if (!tree_int_cst_equal ((*npp)->m_c->get_low (),
-                                          (*npp)->m_c->get_high ()))
-                   i--;
-                 i--;
-                 if (i <= 0)
-                   break;
-                 npp = &(*npp)->m_right;
-               }
+             /* Skip nodes while their probability does not reach
+                that amount.  */
+             prob -= (*npp)->m_c->m_prob;
+             if ((prob.initialized_p () && prob < pivot_prob)
+                 || ! (*npp)->m_right)
+               break;
+             npp = &(*npp)->m_right;
            }
-         *head = np = *npp;
-         *npp = 0;
+
+         np = *npp;
+         *npp = 0;
+         *head = np;
          np->m_parent = parent;
-         np->m_left = left;
+         np->m_left = left == np ? NULL : left;
 
          /* Optimize each of the two split parts.  */
          balance_case_nodes (&np->m_left, np);
          balance_case_nodes (&np->m_right, np);
          np->m_c->m_subtree_prob = np->m_c->m_prob;
-         np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
-         np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
+         if (np->m_left)
+           np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
+         if (np->m_right)
+           np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
        }
       else
        {
@@ -2004,7 +2060,9 @@ switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
   fprintf (f, "%*s", indent_step * indent_level, "");
   root->m_c->dump (f);
   root->m_c->m_prob.dump (f);
-  fputs ("\n", f);
+  fputs (" subtree: ", f);
+  root->m_c->m_subtree_prob.dump (f);
+  fputs (")\n", f);
 
   dump_case_nodes (f, root->m_right, indent_step, indent_level);
 }
@@ -2028,12 +2086,14 @@ basic_block
 switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
                                               tree op1, tree_code comparison,
                                               basic_block label_bb,
-                                              profile_probability prob)
+                                              profile_probability prob,
+                                              location_t loc)
 {
   // TODO: it's once called with lhs != index.
   op1 = fold_convert (TREE_TYPE (op0), op1);
 
   gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
+  gimple_set_location (cond, loc);
   gimple_stmt_iterator gsi = gsi_last_bb (bb);
   gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
 
@@ -2050,6 +2110,36 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
   return false_edge->dest;
 }
 
+/* Generate code to jump to LABEL if OP0 and OP1 are equal.
+   PROB is the probability of jumping to LABEL_BB.
+   BB is a basic block where the new condition will be placed.  */
+
+basic_block
+switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
+                                       basic_block label_bb,
+                                       profile_probability prob,
+                                       location_t loc)
+{
+  op1 = fold_convert (TREE_TYPE (op0), op1);
+
+  gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
+  gimple_set_location (cond, loc);
+  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+  gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
+
+  gcc_assert (single_succ_p (bb));
+
+  /* Make a new basic block where false branch will take place.  */
+  edge false_edge = split_block (bb, cond);
+  false_edge->flags = EDGE_FALSE_VALUE;
+  false_edge->probability = prob.invert ();
+
+  edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
+  true_edge->probability = prob;
+
+  return false_edge->dest;
+}
+
 /* Emit step-by-step code to select a case for the value of INDEX.
    The thus generated decision tree follows the form of the
    case-node binary tree NODE, whose nodes represent test conditions.
@@ -2060,43 +2150,195 @@ basic_block
 switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
                                       case_tree_node *node,
                                       profile_probability default_prob,
-                                      tree index_type)
+                                      tree index_type, location_t loc)
 {
+  profile_probability p;
+
   /* If node is null, we are done.  */
   if (node == NULL)
     return bb;
 
-  /* Branch to a label where we will handle it later.  */
-  basic_block test_bb = split_edge (single_succ_edge (bb));
-  redirect_edge_succ (single_pred_edge (test_bb),
-                     single_succ_edge (bb)->dest);
-
-  profile_probability probability
-    = (node->m_right
-       ? node->m_right->m_c->m_subtree_prob : profile_probability::never ());
-  probability = ((probability + default_prob.apply_scale (1, 2))
-                / (node->m_c->m_subtree_prob + default_prob));
-  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), GT_EXPR,
-                               test_bb, probability);
-  default_prob = default_prob.apply_scale (1, 2);
-
-  /* Value belongs to this node or to the left-hand subtree.  */
-  probability = node->m_c->m_prob /
-    (node->m_c->m_subtree_prob + default_prob);
-  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), GE_EXPR,
-                               node->m_c->m_case_bb, probability);
-
-  /* Handle the left-hand subtree.  */
-  bb = emit_case_nodes (bb, index, node->m_left,
-                       default_prob, index_type);
-
-  /* If the left-hand subtree fell through,
-     don't let it fall into the right-hand subtree.  */
-  if (m_default_bb)
-    emit_jump (bb, m_default_bb);
+  /* Single value case.  */
+  if (node->m_c->is_single_value_p ())
+    {
+      /* Node is single valued.  First see if the index expression matches
+        this node and then check our children, if any.  */
+      p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
+      bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
+                            node->m_c->m_case_bb, p, loc);
+      /* Since this case is taken at this point, reduce its weight from
+        subtree_weight.  */
+      node->m_c->m_subtree_prob -= p;
+
+      if (node->m_left != NULL && node->m_right != NULL)
+       {
+         /* 1) the node has both children
 
-  bb = emit_case_nodes (test_bb, index, node->m_right,
-                       default_prob, index_type);
+            If both children are single-valued cases with no
+            children, finish up all the work.  This way, we can save
+            one ordered comparison.  */
+
+         if (!node->m_left->has_child ()
+             && node->m_left->m_c->is_single_value_p ()
+             && !node->m_right->has_child ()
+             && node->m_right->m_c->is_single_value_p ())
+           {
+             p = (node->m_right->m_c->m_prob
+                  / (node->m_c->m_subtree_prob + default_prob));
+             bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
+                                    node->m_right->m_c->m_case_bb, p, loc);
+
+             p = (node->m_left->m_c->m_prob
+                  / (node->m_c->m_subtree_prob + default_prob));
+             bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
+                                    node->m_left->m_c->m_case_bb, p, loc);
+           }
+         else
+           {
+             /* Branch to a label where we will handle it later.  */
+             basic_block test_bb = split_edge (single_succ_edge (bb));
+             redirect_edge_succ (single_pred_edge (test_bb),
+                                 single_succ_edge (bb)->dest);
+
+             p = ((node->m_right->m_c->m_subtree_prob
+                   + default_prob.apply_scale (1, 2))
+                  / (node->m_c->m_subtree_prob + default_prob));
+             bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+                                           GT_EXPR, test_bb, p, loc);
+             default_prob = default_prob.apply_scale (1, 2);
+
+             /* Handle the left-hand subtree.  */
+             bb = emit_case_nodes (bb, index, node->m_left,
+                                   default_prob, index_type, loc);
+
+             /* If the left-hand subtree fell through,
+                don't let it fall into the right-hand subtree.  */
+             if (bb && m_default_bb)
+               emit_jump (bb, m_default_bb);
+
+             bb = emit_case_nodes (test_bb, index, node->m_right,
+                                   default_prob, index_type, loc);
+           }
+       }
+      else if (node->m_left == NULL && node->m_right != NULL)
+       {
+         /* 2) the node has only right child.  */
+
+         /* Here we have a right child but no left so we issue a conditional
+            branch to default and process the right child.
+
+            Omit the conditional branch to default if the right child
+            does not have any children and is single valued; it would
+            cost too much space to save so little time.  */
+
+         if (node->m_right->has_child ()
+             || !node->m_right->m_c->is_single_value_p ())
+           {
+             p = (default_prob.apply_scale (1, 2)
+                  / (node->m_c->m_subtree_prob + default_prob));
+             bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
+                                           LT_EXPR, m_default_bb, p, loc);
+             default_prob = default_prob.apply_scale (1, 2);
+
+             bb = emit_case_nodes (bb, index, node->m_right, default_prob,
+                                   index_type, loc);
+           }
+         else
+           {
+             /* We cannot process node->right normally
+                since we haven't ruled out the numbers less than
+                this node's value.  So handle node->right explicitly.  */
+             p = (node->m_right->m_c->m_subtree_prob
+                  / (node->m_c->m_subtree_prob + default_prob));
+             bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
+                                    node->m_right->m_c->m_case_bb, p, loc);
+           }
+       }
+      else if (node->m_left != NULL && node->m_right == NULL)
+       {
+         /* 3) just one subtree, on the left.  Similar case as previous.  */
+
+         if (node->m_left->has_child ()
+             || !node->m_left->m_c->is_single_value_p ())
+           {
+             p = (default_prob.apply_scale (1, 2)
+                  / (node->m_c->m_subtree_prob + default_prob));
+             bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+                                           GT_EXPR, m_default_bb, p, loc);
+                 default_prob = default_prob.apply_scale (1, 2);
+
+             bb = emit_case_nodes (bb, index, node->m_left, default_prob,
+                                   index_type, loc);
+           }
+         else
+           {
+             /* We cannot process node->left normally
+                since we haven't ruled out the numbers less than
+                this node's value.  So handle node->left explicitly.  */
+             p = (node->m_left->m_c->m_subtree_prob
+                  / (node->m_c->m_subtree_prob + default_prob));
+             bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
+                                    node->m_left->m_c->m_case_bb, p, loc);
+           }
+       }
+    }
+  else
+    {
+      /* Node is a range.  These cases are very similar to those for a single
+        value, except that we do not start by testing whether this node
+        is the one to branch to.  */
+      if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
+       {
+         /* Branch to a label where we will handle it later.  */
+         basic_block test_bb = split_edge (single_succ_edge (bb));
+         redirect_edge_succ (single_pred_edge (test_bb),
+                             single_succ_edge (bb)->dest);
+
+
+          profile_probability right_prob = profile_probability::never ();
+          if (node->m_right)
+            right_prob = node->m_right->m_c->m_subtree_prob;
+         p = ((right_prob + default_prob.apply_scale (1, 2))
+              / (node->m_c->m_subtree_prob + default_prob));
+
+         bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+                                       GT_EXPR, test_bb, p, loc);
+         default_prob = default_prob.apply_scale (1, 2);
+
+         /* Value belongs to this node or to the left-hand subtree.  */
+         p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
+         bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
+                                       GE_EXPR, node->m_c->m_case_bb, p, loc);
+
+         /* Handle the left-hand subtree.  */
+         bb = emit_case_nodes (bb, index, node->m_left,
+                               default_prob, index_type, loc);
+
+         /* If the left-hand subtree fell through,
+            don't let it fall into the right-hand subtree.  */
+         if (bb && m_default_bb)
+           emit_jump (bb, m_default_bb);
+
+         bb = emit_case_nodes (test_bb, index, node->m_right,
+                               default_prob, index_type, loc);
+       }
+      else
+       {
+         /* Node has no children so we check low and high bounds to remove
+            redundant tests.  Only one of the bounds can exist,
+            since otherwise this node is bounded--a case tested already.  */
+         tree lhs, rhs;
+         generate_range_test (bb, index, node->m_c->get_low (),
+                              node->m_c->get_high (), &lhs, &rhs);
+         p = default_prob / (node->m_c->m_subtree_prob + default_prob);
+
+         bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
+                                       m_default_bb, p, loc);
+
+         emit_jump (bb, node->m_c->m_case_bb);
+         return NULL;
+       }
+    }
 
   return bb;
 }
@@ -2246,8 +2488,13 @@ pass_lower_switch<O0>::execute (function *fun)
   FOR_EACH_BB_FN (bb, fun)
     {
       gimple *stmt = last_stmt (bb);
-      if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
-       switch_statements.safe_push (stmt);
+      gswitch *swtch;
+      if (stmt && (swtch = dyn_cast<gswitch *> (stmt)))
+       {
+         if (!O0)
+           group_case_labels_stmt (swtch);
+         switch_statements.safe_push (swtch);
+       }
     }
 
   for (unsigned i = 0; i < switch_statements.length (); i++)