X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Ftree-switch-conversion.c;h=bf910dd62b538cba2984d031e061b9499470c602;hb=224efaf7e1e9240b64602ea81a255cb43e4dcb0c;hp=47acb0c8ae884e15000128200848be0c92c5a094;hpb=377afcd5beb350a1b7cd07b0a868a766345073e0;p=gcc.git diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 47acb0c8ae8..bf910dd62b5 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -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 *vec) +bool +switch_conversion::contains_linear_function_p (vec *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 = 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 &clusters) } /* No result. */ - if (min[l].m_count == INT_MAX) + if (min[l].m_count == l) return clusters.copy (); vec 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 &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 &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 &, 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 bit_test_cluster::find_bit_tests (vec &clusters) { - vec output; - output.create (4); - unsigned l = clusters.length (); auto_vec min; min.reserve (l + 1); @@ -1275,9 +1327,12 @@ bit_test_cluster::find_bit_tests (vec &clusters) } /* No result. */ - if (min[l].m_count == INT_MAX) + if (min[l].m_count == l) return clusters.copy (); + vec output; + output.create (4); + /* Find and build the clusters. */ for (unsigned end = l;;) { @@ -1290,7 +1345,7 @@ bit_test_cluster::find_bit_tests (vec &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 &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 &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 &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::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 (stmt))) + { + if (!O0) + group_case_labels_stmt (swtch); + switch_statements.safe_push (swtch); + } } for (unsigned i = 0; i < switch_statements.length (); i++)