X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Ftree-switch-conversion.c;h=bf910dd62b538cba2984d031e061b9499470c602;hb=224efaf7e1e9240b64602ea81a255cb43e4dcb0c;hp=dc9fc84c6a01bca5a379117aa2e0a4425faf7678;hpb=8e6cdc90d41633e09a3a34bb8c6f71cf246101b2;p=gcc.git diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index dc9fc84c6a0..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-2017 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,1217 +43,712 @@ 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" #include "target.h" #include "tree-into-ssa.h" +#include "omp-general.h" /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode type in the GIMPLE type system that is language-independent? */ #include "langhooks.h" +#include "tree-switch-conversion.h" -/* Maximum number of case bit tests. - FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and - targetm.case_values_threshold(), or be its own param. */ -#define MAX_CASE_BIT_TESTS 3 +using namespace tree_switch_conversion; -/* Split the basic block at the statement pointed to by GSIP, and insert - a branch to the target basic block of E_TRUE conditional on tree - expression COND. - - It is assumed that there is already an edge from the to-be-split - basic block to E_TRUE->dest block. This edge is removed, and the - profile information on the edge is re-used for the new conditional - jump. - - The CFG is updated. The dominator tree will not be valid after - this transformation, but the immediate dominators are updated if - UPDATE_DOMINATORS is true. - - Returns the newly created basic block. */ +/* Constructor. */ -static basic_block -hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, - tree cond, edge e_true, - bool update_dominators) +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) { - tree tmp; - gcond *cond_stmt; - edge e_false; - basic_block new_bb, split_bb = gsi_bb (*gsip); - bool dominated_e_true = false; +} - gcc_assert (e_true->src == split_bb); +/* Collection information about SWTCH statement. */ - if (update_dominators - && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb) - dominated_e_true = true; +void +switch_conversion::collect (gswitch *swtch) +{ + unsigned int branch_num = gimple_switch_num_labels (swtch); + tree min_case, max_case; + unsigned int i; + edge e, e_default, e_first; + edge_iterator ei; - tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL, - /*before=*/true, GSI_SAME_STMT); - cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE); - gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT); + m_switch = swtch; - e_false = split_block (split_bb, cond_stmt); - new_bb = e_false->dest; - redirect_edge_pred (e_true, split_bb); + /* The gimplifier has already sorted the cases by CASE_LOW and ensured there + is a default label which is the first in the vector. + Collect the bits we can deduce from the CFG. */ + m_index_expr = gimple_switch_index (swtch); + m_switch_bb = gimple_bb (swtch); + e_default = gimple_switch_default_edge (cfun, swtch); + m_default_bb = e_default->dest; + m_default_prob = e_default->probability; - e_true->flags &= ~EDGE_FALLTHRU; - e_true->flags |= EDGE_TRUE_VALUE; + /* Get upper and lower bounds of case values, and the covered range. */ + min_case = gimple_switch_label (swtch, 1); + max_case = gimple_switch_label (swtch, branch_num - 1); - e_false->flags &= ~EDGE_FALLTHRU; - e_false->flags |= EDGE_FALSE_VALUE; - e_false->probability = e_true->probability.invert (); - e_false->count = split_bb->count - e_true->count; - new_bb->count = e_false->count; + m_range_min = CASE_LOW (min_case); + if (CASE_HIGH (max_case) != NULL_TREE) + m_range_max = CASE_HIGH (max_case); + else + m_range_max = CASE_LOW (max_case); - if (update_dominators) + m_contiguous_range = true; + tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min; + for (i = 2; i < branch_num; i++) { - if (dominated_e_true) - set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb); - set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb); + tree elt = gimple_switch_label (swtch, i); + if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt))) + { + m_contiguous_range = false; + break; + } + last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt); } - return new_bb; -} + if (m_contiguous_range) + e_first = gimple_switch_edge (cfun, swtch, 1); + else + e_first = e_default; + + /* See if there is one common successor block for all branch + targets. If it exists, record it in FINAL_BB. + Start with the destination of the first non-default case + if the range is contiguous and default case otherwise as + guess or its destination in case it is a forwarder block. */ + if (! single_pred_p (e_first->dest)) + m_final_bb = e_first->dest; + else if (single_succ_p (e_first->dest) + && ! single_pred_p (single_succ (e_first->dest))) + m_final_bb = single_succ (e_first->dest); + /* Require that all switch destinations are either that common + FINAL_BB or a forwarder to it, except for the default + case if contiguous range. */ + if (m_final_bb) + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) + { + if (e->dest == m_final_bb) + continue; + + if (single_pred_p (e->dest) + && single_succ_p (e->dest) + && single_succ (e->dest) == m_final_bb) + continue; + + if (e == e_default && m_contiguous_range) + { + m_default_case_nonstandard = true; + continue; + } + m_final_bb = NULL; + break; + } -/* Return true if a switch should be expanded as a bit test. - RANGE is the difference between highest and lowest case. - UNIQ is number of unique case node targets, not counting the default case. - COUNT is the number of comparisons needed, not counting the default case. */ + m_range_size + = int_const_binop (MINUS_EXPR, m_range_max, m_range_min); -static bool -expand_switch_using_bit_tests_p (tree range, - unsigned int uniq, - unsigned int count, bool speed_p) -{ - return (((uniq == 1 && count >= 3) - || (uniq == 2 && count >= 5) - || (uniq == 3 && count >= 6)) - && lshift_cheap_p (speed_p) - && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 - && compare_tree_int (range, 0) > 0); + /* Get a count of the number of case labels. Single-valued case labels + simply count as one, but a case range counts double, since it may + require two compares if it gets lowered as a branching tree. */ + m_count = 0; + for (i = 1; i < branch_num; i++) + { + tree elt = gimple_switch_label (swtch, i); + m_count++; + if (CASE_HIGH (elt) + && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt))) + m_count++; + } + + /* Get the number of unique non-default targets out of the GIMPLE_SWITCH + block. Assume a CFG cleanup would have already removed degenerate + switch statements, this allows us to just use EDGE_COUNT. */ + m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1; } - -/* Implement switch statements with bit tests -A GIMPLE switch statement can be expanded to a short sequence of bit-wise -comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)" -where CST and MINVAL are integer constants. This is better than a series -of compare-and-banch insns in some cases, e.g. we can implement: +/* Checks whether the range given by individual case statements of the switch + switch statement isn't too big and whether the number of branches actually + satisfies the size of the new array. */ + +bool +switch_conversion::check_range () +{ + gcc_assert (m_range_size); + if (!tree_fits_uhwi_p (m_range_size)) + { + m_reason = "index range way too large or otherwise unusable"; + return false; + } - if ((x==4) || (x==6) || (x==9) || (x==11)) + if (tree_to_uhwi (m_range_size) + > ((unsigned) m_count * param_switch_conversion_branch_ratio)) + { + m_reason = "the maximum range-branch ratio exceeded"; + return false; + } -as a single bit test: + return true; +} - if ((1<succs) + { + if (e->dest == m_final_bb) + continue; - int bar(int x) + if (!empty_block_p (e->dest)) { - switch (x) - { - case '0': case '1': case '2': case '3': case '4': - case '5': case '6': case '7': case '8': case '9': - case 'A': case 'B': case 'C': case 'D': case 'E': - case 'F': - return 1; - } - return 0; + if (m_contiguous_range && e == e_default) + { + m_default_case_nonstandard = true; + continue; + } + + m_reason = "bad case - a non-final BB not empty"; + return false; } + } -==> + return true; +} - bar (int x) - { - tmp1 = x - 48; - if (tmp1 > (70 - 48)) goto L2; - tmp2 = 1 << tmp1; - tmp3 = 0b11111100000001111111111; - if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2; - L1: - return 1; - L2: - return 0; - } +/* This function checks whether all required values in phi nodes in final_bb + are constants. Required values are those that correspond to a basic block + which is a part of the examined switch statement. It returns true if the + phi nodes are OK, otherwise false. */ -TODO: There are still some improvements to this transformation that could -be implemented: +bool +switch_conversion::check_final_bb () +{ + gphi_iterator gsi; -* A narrower mode than word_mode could be used if that is cheaper, e.g. - for x86_64 where a narrower-mode shift may result in smaller code. + m_phi_count = 0; + for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + unsigned int i; -* The compounded constant could be shifted rather than the one. The - test would be either on the sign bit or on the least significant bit, - depending on the direction of the shift. On some machines, the test - for the branch would be free if the bit to test is already set by the - shift operation. + if (virtual_operand_p (gimple_phi_result (phi))) + continue; -This transformation was contributed by Roger Sayle, see this e-mail: - http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html -*/ + m_phi_count++; -/* A case_bit_test represents a set of case nodes that may be - selected from using a bit-wise comparison. HI and LO hold - the integer to be tested against, TARGET_EDGE contains the - edge to the basic block to jump to upon success and BITS - counts the number of case nodes handled by this test, - typically the number of bits set in HI:LO. The LABEL field - is used to quickly identify all cases in this set without - looking at label_to_block for every case label. */ + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + basic_block bb = gimple_phi_arg_edge (phi, i)->src; -struct case_bit_test -{ - wide_int mask; - edge target_edge; - tree label; - int bits; -}; + if (bb == m_switch_bb + || (single_pred_p (bb) + && single_pred (bb) == m_switch_bb + && (!m_default_case_nonstandard + || empty_block_p (bb)))) + { + tree reloc, val; + const char *reason = NULL; -/* Comparison function for qsort to order bit tests by decreasing - probability of execution. Our best guess comes from a measured - profile. If the profile counts are equal, break even on the - number of case nodes, i.e. the node with the most cases gets - tested first. - - TODO: Actually this currently runs before a profile is available. - Therefore the case-as-bit-tests transformation should be done - later in the pass pipeline, or something along the lines of - "Efficient and effective branch reordering using profile data" - (Yang et. al., 2002) should be implemented (although, how good - is a paper is called "Efficient and effective ..." when the - latter is implied by the former, but oh well...). */ - -static 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; + val = gimple_phi_arg_def (phi, i); + if (!is_gimple_ip_invariant (val)) + reason = "non-invariant value from a case"; + else + { + reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); + if ((flag_pic && reloc != null_pointer_node) + || (!flag_pic && reloc == NULL_TREE)) + { + if (reloc) + reason + = "value from a case would need runtime relocations"; + else + reason + = "value from a case is not a valid initializer"; + } + } + if (reason) + { + /* For contiguous range, we can allow non-constant + or one that needs relocation, as long as it is + only reachable from the default case. */ + if (bb == m_switch_bb) + bb = m_final_bb; + if (!m_contiguous_range || bb != m_default_bb) + { + m_reason = reason; + return false; + } - if (d2->target_edge->count < d1->target_edge->count) - return -1; - if (d2->target_edge->count > d1->target_edge->count) - return 1; - if (d2->bits != d1->bits) - return d2->bits - d1->bits; + unsigned int branch_num = gimple_switch_num_labels (m_switch); + for (unsigned int i = 1; i < branch_num; i++) + { + if (gimple_switch_label_bb (cfun, m_switch, i) == bb) + { + m_reason = reason; + return false; + } + } + m_default_case_nonstandard = true; + } + } + } + } - /* Stabilize the sort. */ - return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label); + return true; } -/* Expand a switch statement by a short sequence of bit-wise - comparisons. "switch(x)" is effectively converted into - "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are - integer constants. +/* The following function allocates default_values, target_{in,out}_names and + constructors arrays. The last one is also populated with pointers to + vectors that will become constructors of new arrays. */ - INDEX_EXPR is the value being switched on. +void +switch_conversion::create_temp_arrays () +{ + int i; - MINVAL is the lowest case value of in the case nodes, - and RANGE is highest value minus MINVAL. MINVAL and RANGE - are not guaranteed to be of the same type as INDEX_EXPR - (the gimplifier doesn't change the type of case label values, - and MINVAL and RANGE are derived from those values). - MAXVAL is MINVAL + RANGE. + m_default_values = XCNEWVEC (tree, m_phi_count * 3); + /* ??? Macros do not support multi argument templates in their + argument list. We create a typedef to work around that problem. */ + typedef vec *vec_constructor_elt_gc; + m_constructors = XCNEWVEC (vec_constructor_elt_gc, m_phi_count); + m_target_inbound_names = m_default_values + m_phi_count; + m_target_outbound_names = m_target_inbound_names + m_phi_count; + for (i = 0; i < m_phi_count; i++) + vec_alloc (m_constructors[i], tree_to_uhwi (m_range_size) + 1); +} - There *MUST* be MAX_CASE_BIT_TESTS or less unique case - node targets. */ +/* Populate the array of default values in the order of phi nodes. + DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch + if the range is non-contiguous or the default case has standard + structure, otherwise it is the first non-default case instead. */ -static void -emit_case_bit_tests (gswitch *swtch, tree index_expr, - tree minval, tree range, tree maxval) +void +switch_conversion::gather_default_values (tree default_case) { - struct case_bit_test test[MAX_CASE_BIT_TESTS] = { {} }; - unsigned int i, j, k; - unsigned int count; - - basic_block switch_bb = gimple_bb (swtch); - basic_block default_bb, new_default_bb, new_bb; - edge default_edge; - bool update_dom = dom_info_available_p (CDI_DOMINATORS); + gphi_iterator gsi; + basic_block bb = label_to_block (cfun, CASE_LABEL (default_case)); + edge e; + int i = 0; - vec bbs_to_fix_dom = vNULL; + gcc_assert (CASE_LOW (default_case) == NULL_TREE + || m_default_case_nonstandard); - tree index_type = TREE_TYPE (index_expr); - tree unsigned_index_type = unsigned_type_for (index_type); - unsigned int branch_num = gimple_switch_num_labels (swtch); + if (bb == m_final_bb) + e = find_edge (m_switch_bb, bb); + else + e = single_succ_edge (bb); - gimple_stmt_iterator gsi; - gassign *shift_stmt; + for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; + tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); + gcc_assert (val); + m_default_values[i++] = val; + } +} - tree idx, tmp, csui; - tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1); - tree word_mode_zero = fold_convert (word_type_node, integer_zero_node); - tree word_mode_one = fold_convert (word_type_node, integer_one_node); - int prec = TYPE_PRECISION (word_type_node); - wide_int wone = wi::one (prec); +/* The following function populates the vectors in the constructors array with + future contents of the static arrays. The vectors are populated in the + order of phi nodes. */ - /* Get the edge for the default case. */ - tmp = gimple_switch_default_label (swtch); - default_bb = label_to_block (CASE_LABEL (tmp)); - default_edge = find_edge (switch_bb, default_bb); +void +switch_conversion::build_constructors () +{ + unsigned i, branch_num = gimple_switch_num_labels (m_switch); + tree pos = m_range_min; + tree pos_one = build_int_cst (TREE_TYPE (pos), 1); - /* Go through all case labels, and collect the case labels, profile - counts, and other information we need to build the branch tests. */ - count = 0; for (i = 1; i < branch_num; i++) { - unsigned int lo, hi; - tree cs = gimple_switch_label (swtch, i); - tree label = CASE_LABEL (cs); - edge e = find_edge (switch_bb, label_to_block (label)); - for (k = 0; k < count; k++) - if (e == test[k].target_edge) - break; + tree cs = gimple_switch_label (m_switch, i); + basic_block bb = label_to_block (cfun, CASE_LABEL (cs)); + edge e; + tree high; + gphi_iterator gsi; + int j; - if (k == count) - { - gcc_checking_assert (count < MAX_CASE_BIT_TESTS); - test[k].mask = wi::zero (prec); - test[k].target_edge = e; - test[k].label = label; - test[k].bits = 1; - count++; - } + if (bb == m_final_bb) + e = find_edge (m_switch_bb, bb); else - test[k].bits++; - - lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, - CASE_LOW (cs), minval)); - if (CASE_HIGH (cs) == NULL_TREE) - hi = lo; - else - hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, - CASE_HIGH (cs), minval)); + e = single_succ_edge (bb); + gcc_assert (e); - for (j = lo; j <= hi; j++) - test[k].mask |= wi::lshift (wone, j); - } + while (tree_int_cst_lt (pos, CASE_LOW (cs))) + { + int k; + for (k = 0; k < m_phi_count; k++) + { + constructor_elt elt; - qsort (test, count, sizeof (*test), case_bit_test_cmp); + elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min); + elt.value + = unshare_expr_without_location (m_default_values[k]); + m_constructors[k]->quick_push (elt); + } - /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of - the minval subtractions, but it might make the mask constants more - expensive. So, compare the costs. */ - if (compare_tree_int (minval, 0) > 0 - && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) - { - int cost_diff; - HOST_WIDE_INT m = tree_to_uhwi (minval); - rtx reg = gen_raw_REG (word_mode, 10000); - bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch)); - cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg, - GEN_INT (-m)), speed_p); - for (i = 0; i < count; i++) - { - rtx r = immed_wide_int_const (test[i].mask, word_mode); - cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), - word_mode, speed_p); - r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode); - cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), - word_mode, speed_p); + pos = int_const_binop (PLUS_EXPR, pos, pos_one); } - if (cost_diff > 0) + gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); + + j = 0; + if (CASE_HIGH (cs)) + high = CASE_HIGH (cs); + else + high = CASE_LOW (cs); + for (gsi = gsi_start_phis (m_final_bb); + !gsi_end_p (gsi); gsi_next (&gsi)) { - for (i = 0; i < count; i++) - test[i].mask = wi::lshift (test[i].mask, m); - minval = build_zero_cst (TREE_TYPE (minval)); - range = maxval; - } - } + gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; + tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); + tree low = CASE_LOW (cs); + pos = CASE_LOW (cs); + + do + { + constructor_elt elt; - /* We generate two jumps to the default case label. - Split the default edge, so that we don't have to do any PHI node - updating. */ - new_default_bb = split_edge (default_edge); + elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min); + elt.value = unshare_expr_without_location (val); + m_constructors[j]->quick_push (elt); - if (update_dom) - { - bbs_to_fix_dom.create (10); - bbs_to_fix_dom.quick_push (switch_bb); - bbs_to_fix_dom.quick_push (default_bb); - bbs_to_fix_dom.quick_push (new_default_bb); + pos = int_const_binop (PLUS_EXPR, pos, pos_one); + } while (!tree_int_cst_lt (high, pos) + && tree_int_cst_lt (low, pos)); + j++; + } } +} - /* Now build the test-and-branch code. */ +/* 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. */ - gsi = gsi_last_bb (switch_bb); +bool +switch_conversion::contains_linear_function_p (vec *vec, + wide_int *coeff_a, + wide_int *coeff_b) +{ + unsigned int i; + constructor_elt *elt; - /* idx = (unsigned)x - minval. */ - idx = fold_convert (unsigned_index_type, index_expr); - idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx, - fold_convert (unsigned_index_type, minval)); - idx = force_gimple_operand_gsi (&gsi, idx, - /*simple=*/true, NULL_TREE, - /*before=*/true, GSI_SAME_STMT); + gcc_assert (vec->length () >= 2); - /* if (idx > range) goto default */ - range = force_gimple_operand_gsi (&gsi, - fold_convert (unsigned_index_type, range), - /*simple=*/true, NULL_TREE, - /*before=*/true, GSI_SAME_STMT); - tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); - new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom); - if (update_dom) - bbs_to_fix_dom.quick_push (new_bb); - gcc_assert (gimple_bb (swtch) == new_bb); - gsi = gsi_last_bb (new_bb); - - /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors - of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */ - if (update_dom) - { - vec dom_bbs; - basic_block dom_son; + /* Let's try to find any linear function a * x + y that can apply to + given values. 'a' can be calculated as follows: - dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb); - FOR_EACH_VEC_ELT (dom_bbs, i, dom_son) - { - edge e = find_edge (new_bb, dom_son); - if (e && single_pred_p (e->dest)) - continue; - set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb); - bbs_to_fix_dom.safe_push (dom_son); - } - dom_bbs.release (); - } + a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices) + a = y2 - y1 - /* csui = (1 << (word_mode) idx) */ - csui = make_ssa_name (word_type_node); - tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one, - fold_convert (word_type_node, idx)); - tmp = force_gimple_operand_gsi (&gsi, tmp, - /*simple=*/false, NULL_TREE, - /*before=*/true, GSI_SAME_STMT); - shift_stmt = gimple_build_assign (csui, tmp); - gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT); - update_stmt (shift_stmt); + and - /* for each unique set of cases: - if (const & csui) goto target */ - for (k = 0; k < count; k++) - { - tmp = wide_int_to_tree (word_type_node, test[k].mask); - tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); - tmp = force_gimple_operand_gsi (&gsi, tmp, - /*simple=*/true, NULL_TREE, - /*before=*/true, GSI_SAME_STMT); - tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero); - new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge, - update_dom); - if (update_dom) - bbs_to_fix_dom.safe_push (new_bb); - gcc_assert (gimple_bb (swtch) == new_bb); - gsi = gsi_last_bb (new_bb); - } + b = y2 - a * x2 - /* We should have removed all edges now. */ - gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); + */ - /* If nothing matched, go to the default label. */ - make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU); + tree elt0 = (*vec)[0].value; + tree elt1 = (*vec)[1].value; - /* The GIMPLE_SWITCH is now redundant. */ - gsi_remove (&gsi, true); + if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST) + return false; - if (update_dom) - { - /* Fix up the dominator tree. */ - iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); - bbs_to_fix_dom.release (); - } -} - -/* - Switch initialization conversion + 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); -The following pass changes simple initializations of scalars in a switch -statement into initializations from a static array. Obviously, the values -must be constant and known at compile time and a default branch must be -provided. For example, the following code: + /* Verify that all values fulfill the linear function. */ + FOR_EACH_VEC_SAFE_ELT (vec, i, elt) + { + if (TREE_CODE (elt->value) != INTEGER_CST) + return false; - int a,b; + wide_int value = wi::to_wide (elt->value); + if (a * range_min + b != value) + return false; - switch (argc) - { - case 1: - case 2: - a_1 = 8; - b_1 = 6; - break; - case 3: - a_2 = 9; - b_2 = 5; - break; - case 12: - a_3 = 10; - b_3 = 4; - break; - default: - a_4 = 16; - b_4 = 1; - break; - } - a_5 = PHI - b_5 = PHI + ++range_min; + } + *coeff_a = a; + *coeff_b = b; -is changed into: + return true; +} - static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4}; - static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16, - 16, 16, 10}; +/* Return type which should be used for array elements, either TYPE's + main variant or, for integral types, some smaller integral type + that can still hold all the constants. */ - if (((unsigned) argc) - 1 < 11) - { - a_6 = CSWTCH02[argc - 1]; - b_6 = CSWTCH01[argc - 1]; - } - else - { - a_7 = 16; - b_7 = 1; - } - a_5 = PHI - b_b = PHI +tree +switch_conversion::array_value_type (tree type, int num) +{ + unsigned int i, len = vec_safe_length (m_constructors[num]); + constructor_elt *elt; + int sign = 0; + tree smaller_type; -There are further constraints. Specifically, the range of values across all -case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default -eight) times the number of the actual switch branches. + /* Types with alignments greater than their size can reach here, e.g. out of + SRA. We couldn't use these as an array component type so get back to the + main variant first, which, for our purposes, is fine for other types as + well. */ -This transformation was contributed by Martin Jambor, see this e-mail: - http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */ + type = TYPE_MAIN_VARIANT (type); -/* The main structure of the pass. */ -struct switch_conv_info -{ - /* The expression used to decide the switch branch. */ - tree index_expr; + if (!INTEGRAL_TYPE_P (type)) + return type; - /* The following integer constants store the minimum and maximum value - covered by the case labels. */ - tree range_min; - tree range_max; + scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type); + scalar_int_mode mode = get_narrowest_mode (type_mode); + if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode)) + return type; - /* The difference between the above two numbers. Stored here because it - is used in all the conversion heuristics, as well as for some of the - transformation, and it is expensive to re-compute it all the time. */ - tree range_size; + if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32)) + return type; - /* Basic block that contains the actual GIMPLE_SWITCH. */ - basic_block switch_bb; + FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt) + { + wide_int cst; - /* Basic block that is the target of the default case. */ - basic_block default_bb; + if (TREE_CODE (elt->value) != INTEGER_CST) + return type; - /* The single successor block of all branches out of the GIMPLE_SWITCH, - if such a block exists. Otherwise NULL. */ - basic_block final_bb; + cst = wi::to_wide (elt->value); + while (1) + { + unsigned int prec = GET_MODE_BITSIZE (mode); + if (prec > HOST_BITS_PER_WIDE_INT) + return type; - /* The probability of the default edge in the replaced switch. */ - profile_probability default_prob; + if (sign >= 0 && cst == wi::zext (cst, prec)) + { + if (sign == 0 && cst == wi::sext (cst, prec)) + break; + sign = 1; + break; + } + if (sign <= 0 && cst == wi::sext (cst, prec)) + { + sign = -1; + break; + } - /* The count of the default edge in the replaced switch. */ - profile_count default_count; + if (sign == 1) + sign = 0; - /* Combined count of all other (non-default) edges in the replaced switch. */ - profile_count other_count; + if (!GET_MODE_WIDER_MODE (mode).exists (&mode) + || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode)) + return type; + } + } - /* Number of phi nodes in the final bb (that we'll be replacing). */ - int phi_count; + if (sign == 0) + sign = TYPE_UNSIGNED (type) ? 1 : -1; + smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0); + if (GET_MODE_SIZE (type_mode) + <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type))) + return type; - /* Array of default values, in the same order as phi nodes. */ - tree *default_values; + return smaller_type; +} - /* Constructors of new static arrays. */ - vec **constructors; +/* Create an appropriate array type and declaration and assemble a static + array variable. Also create a load statement that initializes + the variable in question with a value from the static array. SWTCH is + the switch statement being converted, NUM is the index to + arrays of constructors, default values and target SSA names + for this particular array. ARR_INDEX_TYPE is the type of the index + of the new array, PHI is the phi node of the final BB that corresponds + to the value that will be loaded from the created array. TIDX + is an ssa name of a temporary variable holding the index for loads from the + new array. */ - /* Array of ssa names that are initialized with a value from a new static - array. */ - tree *target_inbound_names; +void +switch_conversion::build_one_array (int num, tree arr_index_type, + gphi *phi, tree tidx) +{ + tree name; + gimple *load; + gimple_stmt_iterator gsi = gsi_for_stmt (m_switch); + location_t loc = gimple_location (m_switch); - /* Array of ssa names that are initialized with the default value if the - switch expression is out of range. */ - tree *target_outbound_names; + gcc_assert (m_default_values[num]); - /* VOP SSA_NAME. */ - tree target_vop; + name = copy_ssa_name (PHI_RESULT (phi)); + m_target_inbound_names[num] = name; + + 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; - /* The first load statement that loads a temporary from a new static array. - */ - gimple *arr_ref_first; + default_type = TREE_TYPE (m_default_values[num]); + value_type = array_value_type (default_type, num); + array_type = build_array_type (value_type, arr_index_type); + if (default_type != value_type) + { + unsigned int i; + constructor_elt *elt; - /* The last load statement that loads a temporary from a new static array. */ - gimple *arr_ref_last; + FOR_EACH_VEC_SAFE_ELT (constructor, i, elt) + elt->value = fold_convert (value_type, elt->value); + } + ctor = build_constructor (array_type, constructor); + TREE_CONSTANT (ctor) = true; + TREE_STATIC (ctor) = true; - /* String reason why the case wasn't a good candidate that is written to the - dump file, if there is one. */ - const char *reason; + decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type); + TREE_STATIC (decl) = 1; + DECL_INITIAL (decl) = ctor; - /* True if default case is not used for any value between range_min and - range_max inclusive. */ - bool contiguous_range; + DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); + DECL_ARTIFICIAL (decl) = 1; + DECL_IGNORED_P (decl) = 1; + TREE_CONSTANT (decl) = 1; + TREE_READONLY (decl) = 1; + DECL_IGNORED_P (decl) = 1; + if (offloading_function_p (cfun->decl)) + DECL_ATTRIBUTES (decl) + = tree_cons (get_identifier ("omp declare target"), NULL_TREE, + NULL_TREE); + varpool_node::finalize_decl (decl); - /* True if default case does not have the required shape for other case - labels. */ - bool default_case_nonstandard; + fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, + NULL_TREE); + if (default_type != value_type) + { + fetch = fold_convert (default_type, fetch); + fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE, + true, GSI_SAME_STMT); + } + load = gimple_build_assign (name, fetch); + } - /* Parameters for expand_switch_using_bit_tests. Should be computed - the same way as in expand_case. */ - unsigned int uniq; - unsigned int count; -}; + gsi_insert_before (&gsi, load, GSI_SAME_STMT); + update_stmt (load); + m_arr_ref_last = load; +} -/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */ +/* Builds and initializes static arrays initialized with values gathered from + the switch statement. Also creates statements that load values from + them. */ -static void -collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info) +void +switch_conversion::build_arrays () { - unsigned int branch_num = gimple_switch_num_labels (swtch); - tree min_case, max_case; - unsigned int count, i; - edge e, e_default, e_first; - edge_iterator ei; - basic_block first; - - memset (info, 0, sizeof (*info)); - - /* The gimplifier has already sorted the cases by CASE_LOW and ensured there - is a default label which is the first in the vector. - Collect the bits we can deduce from the CFG. */ - info->index_expr = gimple_switch_index (swtch); - info->switch_bb = gimple_bb (swtch); - info->default_bb - = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch))); - e_default = find_edge (info->switch_bb, info->default_bb); - info->default_prob = e_default->probability; - info->default_count = e_default->count; - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) - if (e != e_default) - info->other_count += e->count; + tree arr_index_type; + tree tidx, sub, utype; + gimple *stmt; + gimple_stmt_iterator gsi; + gphi_iterator gpi; + int i; + location_t loc = gimple_location (m_switch); - /* Get upper and lower bounds of case values, and the covered range. */ - min_case = gimple_switch_label (swtch, 1); - max_case = gimple_switch_label (swtch, branch_num - 1); + gsi = gsi_for_stmt (m_switch); - info->range_min = CASE_LOW (min_case); - if (CASE_HIGH (max_case) != NULL_TREE) - info->range_max = CASE_HIGH (max_case); + /* Make sure we do not generate arithmetics in a subrange. */ + utype = TREE_TYPE (m_index_expr); + if (TREE_TYPE (utype)) + utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1); else - info->range_max = CASE_LOW (max_case); + utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1); - info->contiguous_range = true; - tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min; - for (i = 2; i < branch_num; i++) - { - tree elt = gimple_switch_label (swtch, i); - if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt))) - { - info->contiguous_range = false; - break; - } - last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt); - } - - if (info->contiguous_range) - { - first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1))); - e_first = find_edge (info->switch_bb, first); - } - else - { - first = info->default_bb; - e_first = e_default; - } - - /* See if there is one common successor block for all branch - targets. If it exists, record it in FINAL_BB. - Start with the destination of the first non-default case - if the range is contiguous and default case otherwise as - guess or its destination in case it is a forwarder block. */ - if (! single_pred_p (e_first->dest)) - info->final_bb = e_first->dest; - else if (single_succ_p (e_first->dest) - && ! single_pred_p (single_succ (e_first->dest))) - info->final_bb = single_succ (e_first->dest); - /* Require that all switch destinations are either that common - FINAL_BB or a forwarder to it, except for the default - case if contiguous range. */ - if (info->final_bb) - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) - { - if (e->dest == info->final_bb) - continue; - - if (single_pred_p (e->dest) - && single_succ_p (e->dest) - && single_succ (e->dest) == info->final_bb) - continue; - - if (e == e_default && info->contiguous_range) - { - info->default_case_nonstandard = true; - continue; - } - - info->final_bb = NULL; - break; - } - - info->range_size - = int_const_binop (MINUS_EXPR, info->range_max, info->range_min); - - /* Get a count of the number of case labels. Single-valued case labels - simply count as one, but a case range counts double, since it may - require two compares if it gets lowered as a branching tree. */ - count = 0; - for (i = 1; i < branch_num; i++) - { - tree elt = gimple_switch_label (swtch, i); - count++; - if (CASE_HIGH (elt) - && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt))) - count++; - } - info->count = count; - - /* Get the number of unique non-default targets out of the GIMPLE_SWITCH - block. Assume a CFG cleanup would have already removed degenerate - switch statements, this allows us to just use EDGE_COUNT. */ - info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1; -} - -/* Checks whether the range given by individual case statements of the SWTCH - switch statement isn't too big and whether the number of branches actually - satisfies the size of the new array. */ - -static bool -check_range (struct switch_conv_info *info) -{ - gcc_assert (info->range_size); - if (!tree_fits_uhwi_p (info->range_size)) - { - info->reason = "index range way too large or otherwise unusable"; - return false; - } - - if (tree_to_uhwi (info->range_size) - > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO)) - { - info->reason = "the maximum range-branch ratio exceeded"; - return false; - } - - return true; -} - -/* Checks whether all but the FINAL_BB basic blocks are empty. */ - -static bool -check_all_empty_except_final (struct switch_conv_info *info) -{ - edge e, e_default = find_edge (info->switch_bb, info->default_bb); - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) - { - if (e->dest == info->final_bb) - continue; - - if (!empty_block_p (e->dest)) - { - if (info->contiguous_range && e == e_default) - { - info->default_case_nonstandard = true; - continue; - } - - info->reason = "bad case - a non-final BB not empty"; - return false; - } - } - - return true; -} - -/* This function checks whether all required values in phi nodes in final_bb - are constants. Required values are those that correspond to a basic block - which is a part of the examined switch statement. It returns true if the - phi nodes are OK, otherwise false. */ - -static bool -check_final_bb (gswitch *swtch, struct switch_conv_info *info) -{ - gphi_iterator gsi; - - info->phi_count = 0; - for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); - unsigned int i; - - if (virtual_operand_p (gimple_phi_result (phi))) - continue; - - info->phi_count++; - - for (i = 0; i < gimple_phi_num_args (phi); i++) - { - basic_block bb = gimple_phi_arg_edge (phi, i)->src; - - if (bb == info->switch_bb - || (single_pred_p (bb) - && single_pred (bb) == info->switch_bb - && (!info->default_case_nonstandard - || empty_block_p (bb)))) - { - tree reloc, val; - const char *reason = NULL; - - val = gimple_phi_arg_def (phi, i); - if (!is_gimple_ip_invariant (val)) - reason = "non-invariant value from a case"; - else - { - reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); - if ((flag_pic && reloc != null_pointer_node) - || (!flag_pic && reloc == NULL_TREE)) - { - if (reloc) - reason - = "value from a case would need runtime relocations"; - else - reason - = "value from a case is not a valid initializer"; - } - } - if (reason) - { - /* For contiguous range, we can allow non-constant - or one that needs relocation, as long as it is - only reachable from the default case. */ - if (bb == info->switch_bb) - bb = info->final_bb; - if (!info->contiguous_range || bb != info->default_bb) - { - info->reason = reason; - return false; - } - - unsigned int branch_num = gimple_switch_num_labels (swtch); - for (unsigned int i = 1; i < branch_num; i++) - { - tree lab = CASE_LABEL (gimple_switch_label (swtch, i)); - if (label_to_block (lab) == bb) - { - info->reason = reason; - return false; - } - } - info->default_case_nonstandard = true; - } - } - } - } - - return true; -} - -/* The following function allocates default_values, target_{in,out}_names and - constructors arrays. The last one is also populated with pointers to - vectors that will become constructors of new arrays. */ - -static void -create_temp_arrays (struct switch_conv_info *info) -{ - int i; - - info->default_values = XCNEWVEC (tree, info->phi_count * 3); - /* ??? Macros do not support multi argument templates in their - argument list. We create a typedef to work around that problem. */ - typedef vec *vec_constructor_elt_gc; - info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count); - info->target_inbound_names = info->default_values + info->phi_count; - info->target_outbound_names = info->target_inbound_names + info->phi_count; - for (i = 0; i < info->phi_count; i++) - vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1); -} - -/* Free the arrays created by create_temp_arrays(). The vectors that are - created by that function are not freed here, however, because they have - already become constructors and must be preserved. */ - -static void -free_temp_arrays (struct switch_conv_info *info) -{ - XDELETEVEC (info->constructors); - XDELETEVEC (info->default_values); -} - -/* Populate the array of default values in the order of phi nodes. - DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch - if the range is non-contiguous or the default case has standard - structure, otherwise it is the first non-default case instead. */ - -static void -gather_default_values (tree default_case, struct switch_conv_info *info) -{ - gphi_iterator gsi; - basic_block bb = label_to_block (CASE_LABEL (default_case)); - edge e; - int i = 0; - - gcc_assert (CASE_LOW (default_case) == NULL_TREE - || info->default_case_nonstandard); - - if (bb == info->final_bb) - e = find_edge (info->switch_bb, bb); - else - e = single_succ_edge (bb); - - for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); - if (virtual_operand_p (gimple_phi_result (phi))) - continue; - tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); - gcc_assert (val); - info->default_values[i++] = val; - } -} - -/* The following function populates the vectors in the constructors array with - future contents of the static arrays. The vectors are populated in the - order of phi nodes. SWTCH is the switch statement being converted. */ - -static void -build_constructors (gswitch *swtch, struct switch_conv_info *info) -{ - unsigned i, branch_num = gimple_switch_num_labels (swtch); - tree pos = info->range_min; - tree pos_one = build_int_cst (TREE_TYPE (pos), 1); - - for (i = 1; i < branch_num; i++) - { - tree cs = gimple_switch_label (swtch, i); - basic_block bb = label_to_block (CASE_LABEL (cs)); - edge e; - tree high; - gphi_iterator gsi; - int j; - - if (bb == info->final_bb) - e = find_edge (info->switch_bb, bb); - else - e = single_succ_edge (bb); - gcc_assert (e); - - while (tree_int_cst_lt (pos, CASE_LOW (cs))) - { - int k; - gcc_assert (!info->contiguous_range); - for (k = 0; k < info->phi_count; k++) - { - constructor_elt elt; - - elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); - elt.value - = unshare_expr_without_location (info->default_values[k]); - info->constructors[k]->quick_push (elt); - } - - pos = int_const_binop (PLUS_EXPR, pos, pos_one); - } - gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); - - j = 0; - if (CASE_HIGH (cs)) - high = CASE_HIGH (cs); - else - high = CASE_LOW (cs); - for (gsi = gsi_start_phis (info->final_bb); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); - if (virtual_operand_p (gimple_phi_result (phi))) - continue; - tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); - tree low = CASE_LOW (cs); - pos = CASE_LOW (cs); - - do - { - constructor_elt elt; - - elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); - elt.value = unshare_expr_without_location (val); - info->constructors[j]->quick_push (elt); - - pos = int_const_binop (PLUS_EXPR, pos, pos_one); - } while (!tree_int_cst_lt (high, pos) - && tree_int_cst_lt (low, pos)); - j++; - } - } -} - -/* 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. */ - -static tree -constructor_contains_same_values_p (vec *vec) -{ - unsigned int i; - tree prev = NULL_TREE; - constructor_elt *elt; - - 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; - } - return prev; -} - -/* Return type which should be used for array elements, either TYPE's - main variant or, for integral types, some smaller integral type - that can still hold all the constants. */ - -static tree -array_value_type (gswitch *swtch, tree type, int num, - struct switch_conv_info *info) -{ - unsigned int i, len = vec_safe_length (info->constructors[num]); - constructor_elt *elt; - int sign = 0; - tree smaller_type; - - /* Types with alignments greater than their size can reach here, e.g. out of - SRA. We couldn't use these as an array component type so get back to the - main variant first, which, for our purposes, is fine for other types as - well. */ - - type = TYPE_MAIN_VARIANT (type); - - if (!INTEGRAL_TYPE_P (type)) - return type; - - scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type); - scalar_int_mode mode = get_narrowest_mode (type_mode); - if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode)) - return type; - - if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32)) - return type; - - FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) - { - wide_int cst; - - if (TREE_CODE (elt->value) != INTEGER_CST) - return type; - - cst = wi::to_wide (elt->value); - while (1) - { - unsigned int prec = GET_MODE_BITSIZE (mode); - if (prec > HOST_BITS_PER_WIDE_INT) - return type; - - if (sign >= 0 && cst == wi::zext (cst, prec)) - { - if (sign == 0 && cst == wi::sext (cst, prec)) - break; - sign = 1; - break; - } - if (sign <= 0 && cst == wi::sext (cst, prec)) - { - sign = -1; - break; - } - - if (sign == 1) - sign = 0; - - if (!GET_MODE_WIDER_MODE (mode).exists (&mode) - || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode)) - return type; - } - } - - if (sign == 0) - sign = TYPE_UNSIGNED (type) ? 1 : -1; - smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0); - if (GET_MODE_SIZE (type_mode) - <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type))) - return type; - - return smaller_type; -} - -/* Create an appropriate array type and declaration and assemble a static array - variable. Also create a load statement that initializes the variable in - question with a value from the static array. SWTCH is the switch statement - being converted, NUM is the index to arrays of constructors, default values - and target SSA names for this particular array. ARR_INDEX_TYPE is the type - of the index of the new array, PHI is the phi node of the final BB that - corresponds to the value that will be loaded from the created array. TIDX - is an ssa name of a temporary variable holding the index for loads from the - new array. */ - -static void -build_one_array (gswitch *swtch, int num, tree arr_index_type, - gphi *phi, tree tidx, struct switch_conv_info *info) -{ - tree name, cst; - gimple *load; - gimple_stmt_iterator gsi = gsi_for_stmt (swtch); - location_t loc = gimple_location (swtch); - - gcc_assert (info->default_values[num]); - - name = copy_ssa_name (PHI_RESULT (phi)); - info->target_inbound_names[num] = name; - - cst = constructor_contains_same_values_p (info->constructors[num]); - if (cst) - load = gimple_build_assign (name, cst); - else - { - tree array_type, ctor, decl, value_type, fetch, default_type; - - default_type = TREE_TYPE (info->default_values[num]); - value_type = array_value_type (swtch, default_type, num, info); - array_type = build_array_type (value_type, arr_index_type); - if (default_type != value_type) - { - unsigned int i; - constructor_elt *elt; - - FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) - elt->value = fold_convert (value_type, elt->value); - } - ctor = build_constructor (array_type, info->constructors[num]); - TREE_CONSTANT (ctor) = true; - TREE_STATIC (ctor) = true; - - decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type); - TREE_STATIC (decl) = 1; - DECL_INITIAL (decl) = ctor; - - DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); - DECL_ARTIFICIAL (decl) = 1; - DECL_IGNORED_P (decl) = 1; - TREE_CONSTANT (decl) = 1; - TREE_READONLY (decl) = 1; - DECL_IGNORED_P (decl) = 1; - varpool_node::finalize_decl (decl); - - fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, - NULL_TREE); - if (default_type != value_type) - { - fetch = fold_convert (default_type, fetch); - fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE, - true, GSI_SAME_STMT); - } - load = gimple_build_assign (name, fetch); - } - - gsi_insert_before (&gsi, load, GSI_SAME_STMT); - update_stmt (load); - info->arr_ref_last = load; -} - -/* Builds and initializes static arrays initialized with values gathered from - the SWTCH switch statement. Also creates statements that load values from - them. */ - -static void -build_arrays (gswitch *swtch, struct switch_conv_info *info) -{ - tree arr_index_type; - tree tidx, sub, utype; - gimple *stmt; - gimple_stmt_iterator gsi; - gphi_iterator gpi; - int i; - location_t loc = gimple_location (swtch); - - gsi = gsi_for_stmt (swtch); - - /* Make sure we do not generate arithmetics in a subrange. */ - utype = TREE_TYPE (info->index_expr); - if (TREE_TYPE (utype)) - utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1); - else - utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1); - - arr_index_type = build_index_type (info->range_size); + arr_index_type = build_index_type (m_range_size); tidx = make_ssa_name (utype); sub = fold_build2_loc (loc, MINUS_EXPR, utype, - fold_convert_loc (loc, utype, info->index_expr), - fold_convert_loc (loc, utype, info->range_min)); + fold_convert_loc (loc, utype, m_index_expr), + fold_convert_loc (loc, utype, m_range_min)); sub = force_gimple_operand_gsi (&gsi, sub, false, NULL, true, GSI_SAME_STMT); stmt = gimple_build_assign (tidx, sub); gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); update_stmt (stmt); - info->arr_ref_first = stmt; + m_arr_ref_first = stmt; - for (gpi = gsi_start_phis (info->final_bb), i = 0; + for (gpi = gsi_start_phis (m_final_bb), i = 0; !gsi_end_p (gpi); gsi_next (&gpi)) { gphi *phi = gpi.phi (); if (!virtual_operand_p (gimple_phi_result (phi))) - build_one_array (swtch, i++, arr_index_type, phi, tidx, info); + build_one_array (i++, arr_index_type, phi, tidx); else { edge e; edge_iterator ei; - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) { - if (e->dest == info->final_bb) + if (e->dest == m_final_bb) break; - if (!info->default_case_nonstandard - || e->dest != info->default_bb) + if (!m_default_case_nonstandard + || e->dest != m_default_bb) { e = single_succ_edge (e->dest); break; } } - gcc_assert (e && e->dest == info->final_bb); - info->target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e); + gcc_assert (e && e->dest == m_final_bb); + m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e); } } } /* Generates and appropriately inserts loads of default values at the position - given by BSI. Returns the last inserted statement. */ + given by GSI. Returns the last inserted statement. */ -static gassign * -gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info) +gassign * +switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi) { int i; gassign *assign = NULL; - for (i = 0; i < info->phi_count; i++) + for (i = 0; i < m_phi_count; i++) { - tree name = copy_ssa_name (info->target_inbound_names[i]); - info->target_outbound_names[i] = name; - assign = gimple_build_assign (name, info->default_values[i]); + tree name = copy_ssa_name (m_target_inbound_names[i]); + m_target_outbound_names[i] = name; + assign = gimple_build_assign (name, m_default_values[i]); gsi_insert_before (gsi, assign, GSI_SAME_STMT); update_stmt (assign); } @@ -1262,12 +756,13 @@ gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info) } /* Deletes the unused bbs and edges that now contain the switch statement and - its empty branch bbs. BBD is the now dead BB containing the original switch - statement, FINAL is the last BB of the converted switch statement (in terms - of succession). */ + its empty branch bbs. BBD is the now dead BB containing + the original switch statement, FINAL is the last BB of the converted + switch statement (in terms of succession). */ -static void -prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) +void +switch_conversion::prune_bbs (basic_block bbd, basic_block final, + basic_block default_bb) { edge_iterator ei; edge e; @@ -1288,9 +783,8 @@ prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) block loading default values. BBF is the last switch basic block (see the bbf description in the comment below). */ -static void -fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, - struct switch_conv_info *info) +void +switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) { gphi_iterator gsi; int i; @@ -1301,41 +795,24 @@ fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, gphi *phi = gsi.phi (); tree inbound, outbound; if (virtual_operand_p (gimple_phi_result (phi))) - inbound = outbound = info->target_vop; + inbound = outbound = m_target_vop; else { - inbound = info->target_inbound_names[i]; - outbound = info->target_outbound_names[i++]; + inbound = m_target_inbound_names[i]; + outbound = m_target_outbound_names[i++]; } add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION); - if (!info->default_case_nonstandard) + if (!m_default_case_nonstandard) add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION); } } /* Creates a check whether the switch expression value actually falls into the range given by all the cases. If it does not, the temporaries are loaded - with default values instead. SWTCH is the switch statement being converted. - - bb0 is the bb with the switch statement, however, we'll end it with a - condition instead. - - bb1 is the bb to be used when the range check went ok. It is derived from - the switch BB + with default values instead. */ - bb2 is the bb taken when the expression evaluated outside of the range - covered by the created arrays. It is populated by loads of default - values. - - bbF is a fall through for both bb1 and bb2 and contains exactly what - originally followed the switch statement. - - bbD contains the switch statement (in the end). It is unreachable but we - still need to strip off its edges. -*/ - -static void -gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) +void +switch_conversion::gen_inbound_check () { tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); @@ -1350,30 +827,30 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) gimple_stmt_iterator gsi; basic_block bb0, bb1, bb2, bbf, bbd; edge e01 = NULL, e02, e21, e1d, e1f, e2f; - location_t loc = gimple_location (swtch); + location_t loc = gimple_location (m_switch); - gcc_assert (info->default_values); + gcc_assert (m_default_values); - bb0 = gimple_bb (swtch); + bb0 = gimple_bb (m_switch); - tidx = gimple_assign_lhs (info->arr_ref_first); + tidx = gimple_assign_lhs (m_arr_ref_first); utype = TREE_TYPE (tidx); /* (end of) block 0 */ - gsi = gsi_for_stmt (info->arr_ref_first); + gsi = gsi_for_stmt (m_arr_ref_first); gsi_next (&gsi); - bound = fold_convert_loc (loc, utype, info->range_size); + bound = fold_convert_loc (loc, utype, m_range_size); cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE); gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); update_stmt (cond_stmt); /* block 2 */ - if (!info->default_case_nonstandard) + if (!m_default_case_nonstandard) { label2 = gimple_build_label (label_decl2); gsi_insert_before (&gsi, label2, GSI_SAME_STMT); - last_assign = gen_def_assigns (&gsi, info); + last_assign = gen_def_assigns (&gsi); } /* block 1 */ @@ -1381,7 +858,7 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) gsi_insert_before (&gsi, label1, GSI_SAME_STMT); /* block F */ - gsi = gsi_start_bb (info->final_bb); + gsi = gsi_start_bb (m_final_bb); label3 = gimple_build_label (label_decl3); gsi_insert_before (&gsi, label3, GSI_SAME_STMT); @@ -1389,10 +866,10 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) e02 = split_block (bb0, cond_stmt); bb2 = e02->dest; - if (info->default_case_nonstandard) + if (m_default_case_nonstandard) { bb1 = bb2; - bb2 = info->default_bb; + bb2 = m_default_bb; e01 = e02; e01->flags = EDGE_TRUE_VALUE; e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE); @@ -1416,567 +893,925 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) remove_edge (e21); } - e1d = split_block (bb1, info->arr_ref_last); - bbd = e1d->dest; - remove_edge (e1d); + e1d = split_block (bb1, m_arr_ref_last); + bbd = e1d->dest; + remove_edge (e1d); + + /* Flags and profiles of the edge for in-range values. */ + if (!m_default_case_nonstandard) + e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); + e01->probability = m_default_prob.invert (); + + /* Flags and profiles of the edge taking care of out-of-range values. */ + e02->flags &= ~EDGE_FALLTHRU; + e02->flags |= EDGE_FALSE_VALUE; + e02->probability = m_default_prob; + + bbf = m_final_bb; + + e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); + e1f->probability = profile_probability::always (); + + if (m_default_case_nonstandard) + e2f = NULL; + else + { + e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); + e2f->probability = profile_probability::always (); + } + + /* frequencies of the new BBs */ + bb1->count = e01->count (); + bb2->count = e02->count (); + if (!m_default_case_nonstandard) + bbf->count = e1f->count () + e2f->count (); + + /* Tidy blocks that have become unreachable. */ + prune_bbs (bbd, m_final_bb, + m_default_case_nonstandard ? m_default_bb : NULL); + + /* Fixup the PHI nodes in bbF. */ + fix_phi_nodes (e1f, e2f, bbf); + + /* Fix the dominator tree, if it is available. */ + if (dom_info_available_p (CDI_DOMINATORS)) + { + vec bbs_to_fix_dom; + + set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); + if (!m_default_case_nonstandard) + set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); + if (! get_immediate_dominator (CDI_DOMINATORS, bbf)) + /* If bbD was the immediate dominator ... */ + set_immediate_dominator (CDI_DOMINATORS, bbf, bb0); + + bbs_to_fix_dom.create (3 + (bb2 != bbf)); + bbs_to_fix_dom.quick_push (bb0); + bbs_to_fix_dom.quick_push (bb1); + if (bb2 != bbf) + bbs_to_fix_dom.quick_push (bb2); + bbs_to_fix_dom.quick_push (bbf); + + iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); + bbs_to_fix_dom.release (); + } +} + +/* The following function is invoked on every switch statement (the current + one is given in SWTCH) and runs the individual phases of switch + conversion on it one after another until one fails or the conversion + is completed. On success, NULL is in m_reason, otherwise points + to a string with the reason why the conversion failed. */ + +void +switch_conversion::expand (gswitch *swtch) +{ + /* Group case labels so that we get the right results from the heuristics + that decide on the code generation approach for this switch. */ + m_cfg_altered |= group_case_labels_stmt (swtch); + + /* If this switch is now a degenerate case with only a default label, + there is nothing left for us to do. */ + if (gimple_switch_num_labels (swtch) < 2) + { + m_reason = "switch is a degenerate case"; + return; + } + + collect (swtch); + + /* No error markers should reach here (they should be filtered out + during gimplification). */ + gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node); + + /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ + gcc_checking_assert (!TREE_CONSTANT (m_index_expr)); + + /* Prefer bit test if possible. */ + if (tree_fits_uhwi_p (m_range_size) + && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq) + && bit_test_cluster::is_beneficial (m_count, m_uniq)) + { + m_reason = "expanding as bit test is preferable"; + return; + } + + if (m_uniq <= 2) + { + /* This will be expanded as a decision tree . */ + m_reason = "expanding as jumps is preferable"; + return; + } + + /* If there is no common successor, we cannot do the transformation. */ + if (!m_final_bb) + { + m_reason = "no common successor to all case label target blocks found"; + return; + } + + /* Check the case label values are within reasonable range: */ + if (!check_range ()) + { + gcc_assert (m_reason); + return; + } + + /* For all the cases, see whether they are empty, the assignments they + represent constant and so on... */ + if (!check_all_empty_except_final ()) + { + gcc_assert (m_reason); + return; + } + if (!check_final_bb ()) + { + gcc_assert (m_reason); + return; + } + + /* At this point all checks have passed and we can proceed with the + transformation. */ + + create_temp_arrays (); + gather_default_values (m_default_case_nonstandard + ? gimple_switch_label (swtch, 1) + : gimple_switch_default_label (swtch)); + build_constructors (); + + build_arrays (); /* Build the static arrays and assignments. */ + gen_inbound_check (); /* Build the bounds check. */ + + m_cfg_altered = true; +} + +/* Destructor. */ + +switch_conversion::~switch_conversion () +{ + XDELETEVEC (m_constructors); + XDELETEVEC (m_default_values); +} + +/* Constructor. */ + +group_cluster::group_cluster (vec &clusters, + unsigned start, unsigned end) +{ + gcc_checking_assert (end - start + 1 >= 1); + m_prob = profile_probability::never (); + m_cases.create (end - start + 1); + for (unsigned i = start; i <= end; i++) + { + m_cases.quick_push (static_cast (clusters[i])); + m_prob += clusters[i]->m_prob; + } + m_subtree_prob = m_prob; +} + +/* Destructor. */ + +group_cluster::~group_cluster () +{ + for (unsigned i = 0; i < m_cases.length (); i++) + delete m_cases[i]; + + m_cases.release (); +} + +/* Dump content of a cluster. */ + +void +group_cluster::dump (FILE *f, bool details) +{ + unsigned total_values = 0; + for (unsigned i = 0; i < m_cases.length (); i++) + total_values += m_cases[i]->get_range (m_cases[i]->get_low (), + m_cases[i]->get_high ()); + + unsigned comparison_count = 0; + for (unsigned i = 0; i < m_cases.length (); i++) + { + simple_cluster *sc = static_cast (m_cases[i]); + comparison_count += sc->m_range_p ? 2 : 1; + } + + unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ()); + fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT"); + + if (details) + fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC + " density: %.2f%%)", total_values, comparison_count, range, + 100.0f * comparison_count / range); + + fprintf (f, ":"); + PRINT_CASE (f, get_low ()); + fprintf (f, "-"); + PRINT_CASE (f, get_high ()); + fprintf (f, " "); +} + +/* Emit GIMPLE code to handle the cluster. */ + +void +jump_table_cluster::emit (tree index_expr, tree, + tree default_label_expr, basic_block default_bb) +{ + unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ()); + unsigned HOST_WIDE_INT nondefault_range = 0; + + /* For jump table we just emit a new gswitch statement that will + be latter lowered to jump table. */ + auto_vec labels; + labels.create (m_cases.length ()); + + make_edge (m_case_bb, default_bb, 0); + for (unsigned i = 0; i < m_cases.length (); i++) + { + labels.quick_push (unshare_expr (m_cases[i]->m_case_label_expr)); + make_edge (m_case_bb, m_cases[i]->m_case_bb, 0); + } + + gswitch *s = gimple_build_switch (index_expr, + unshare_expr (default_label_expr), labels); + gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb); + gsi_insert_after (&gsi, s, GSI_NEW_STMT); + + /* Set up even probabilities for all cases. */ + for (unsigned i = 0; i < m_cases.length (); i++) + { + simple_cluster *sc = static_cast (m_cases[i]); + edge case_edge = find_edge (m_case_bb, sc->m_case_bb); + unsigned HOST_WIDE_INT case_range + = sc->get_range (sc->get_low (), sc->get_high ()); + nondefault_range += case_range; + + /* case_edge->aux is number of values in a jump-table that are covered + by the case_edge. */ + case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range); + } + + edge default_edge = gimple_switch_default_edge (cfun, s); + default_edge->probability = profile_probability::never (); + + for (unsigned i = 0; i < m_cases.length (); i++) + { + simple_cluster *sc = static_cast (m_cases[i]); + edge case_edge = find_edge (m_case_bb, sc->m_case_bb); + case_edge->probability + = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux, + range); + } + + /* Number of non-default values is probability of default edge. */ + default_edge->probability + += profile_probability::always ().apply_scale (nondefault_range, + range).invert (); + + switch_decision_tree::reset_out_edges_aux (s); +} + +/* Find jump tables of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ + +vec +jump_table_cluster::find_jump_tables (vec &clusters) +{ + if (!is_enabled ()) + return clusters.copy (); + + unsigned l = clusters.length (); + auto_vec min; + min.reserve (l + 1); + + min.quick_push (min_cluster_item (0, 0, 0)); + + 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)); + + for (unsigned j = 0; j < i; j++) + { + unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases; + if (i - j < case_values_threshold ()) + s += i - j; + + /* 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 + && s < min[i].m_non_jt_cases)) + && can_be_handled (clusters, j, i - 1)) + min[i] = min_cluster_item (min[j].m_count + 1, j, s); + } + + gcc_checking_assert (min[i].m_count != INT_MAX); + } + + /* No result. */ + if (min[l].m_count == l) + return clusters.copy (); + + vec output; + output.create (4); + + /* Find and build the clusters. */ + for (unsigned int end = l;;) + { + int start = min[end].m_start; + + /* Do not allow clusters with small number of cases. */ + if (is_beneficial (clusters, start, end - 1)) + output.safe_push (new jump_table_cluster (clusters, start, end - 1)); + else + for (int i = end - 1; i >= start; i--) + output.safe_push (clusters[i]); + + end = start; + + if (start <= 0) + break; + } + + output.reverse (); + return output; +} + +/* Return true when cluster starting at START and ending at END (inclusive) + can build a jump-table. */ + +bool +jump_table_cluster::can_be_handled (const vec &clusters, + unsigned start, unsigned end) +{ + /* If the switch is relatively small such that the cost of one + indirect jump on the target are higher than the cost of a + decision tree, go with the decision tree. + + If range of values is much bigger than number of values, + or if it is too large to represent in a HOST_WIDE_INT, + 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. + + 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 () + ? 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. */ + if (range == 0) + return false; + + unsigned HOST_WIDE_INT comparison_count = 0; + for (unsigned i = start; i <= end; i++) + { + simple_cluster *sc = static_cast (clusters[i]); + comparison_count += sc->m_range_p ? 2 : 1; + } + + unsigned HOST_WIDE_INT lhs = 100 * range; + if (lhs < range) + return false; + + return lhs <= max_ratio * comparison_count; +} - /* flags and profiles of the edge for in-range values */ - if (!info->default_case_nonstandard) - e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); - e01->probability = info->default_prob.invert (); - e01->count = info->other_count; +/* Return true if cluster starting at START and ending at END (inclusive) + is profitable transformation. */ - /* flags and profiles of the edge taking care of out-of-range values */ - e02->flags &= ~EDGE_FALLTHRU; - e02->flags |= EDGE_FALSE_VALUE; - e02->probability = info->default_prob; - e02->count = info->default_count; +bool +jump_table_cluster::is_beneficial (const vec &, + unsigned start, unsigned end) +{ + /* Single case bail out. */ + if (start == end) + return false; - bbf = info->final_bb; + return end - start + 1 >= case_values_threshold (); +} - e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); - e1f->probability = profile_probability::always (); - e1f->count = info->other_count; +/* Find bit tests of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ - if (info->default_case_nonstandard) - e2f = NULL; - else +vec +bit_test_cluster::find_bit_tests (vec &clusters) +{ + unsigned l = clusters.length (); + auto_vec min; + min.reserve (l + 1); + + min.quick_push (min_cluster_item (0, 0, 0)); + + for (unsigned i = 1; i <= l; i++) { - e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); - e2f->probability = profile_probability::always (); - e2f->count = info->default_count; - } + /* Set minimal # of clusters with i-th item to infinite. */ + min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); - /* frequencies of the new BBs */ - bb1->frequency = EDGE_FREQUENCY (e01); - bb2->frequency = EDGE_FREQUENCY (e02); - if (!info->default_case_nonstandard) - bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); + 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); + } - /* Tidy blocks that have become unreachable. */ - prune_bbs (bbd, info->final_bb, - info->default_case_nonstandard ? info->default_bb : NULL); + gcc_checking_assert (min[i].m_count != INT_MAX); + } - /* Fixup the PHI nodes in bbF. */ - fix_phi_nodes (e1f, e2f, bbf, info); + /* No result. */ + if (min[l].m_count == l) + return clusters.copy (); - /* Fix the dominator tree, if it is available. */ - if (dom_info_available_p (CDI_DOMINATORS)) + vec output; + output.create (4); + + /* Find and build the clusters. */ + for (unsigned end = l;;) { - vec bbs_to_fix_dom; + int start = min[end].m_start; - set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); - if (!info->default_case_nonstandard) - set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); - if (! get_immediate_dominator (CDI_DOMINATORS, bbf)) - /* If bbD was the immediate dominator ... */ - set_immediate_dominator (CDI_DOMINATORS, bbf, bb0); + if (is_beneficial (clusters, start, end - 1)) + { + 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]); - bbs_to_fix_dom.create (3 + (bb2 != bbf)); - bbs_to_fix_dom.quick_push (bb0); - bbs_to_fix_dom.quick_push (bb1); - if (bb2 != bbf) - bbs_to_fix_dom.quick_push (bb2); - bbs_to_fix_dom.quick_push (bbf); + end = start; - iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); - bbs_to_fix_dom.release (); + if (start <= 0) + break; } + + output.reverse (); + return output; } -/* The following function is invoked on every switch statement (the current one - is given in SWTCH) and runs the individual phases of switch conversion on it - one after another until one fails or the conversion is completed. - Returns NULL on success, or a pointer to a string with the reason why the - conversion failed. */ +/* Return true when RANGE of case values with UNIQ labels + can build a bit test. */ -static const char * -process_switch (gswitch *swtch) +bool +bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range, + unsigned int uniq) { - struct switch_conv_info info; + /* Check overflow. */ + if (range == 0) + return 0; - /* Group case labels so that we get the right results from the heuristics - that decide on the code generation approach for this switch. */ - group_case_labels_stmt (swtch); + if (range >= GET_MODE_BITSIZE (word_mode)) + return false; - /* If this switch is now a degenerate case with only a default label, - there is nothing left for us to do. */ - if (gimple_switch_num_labels (swtch) < 2) - return "switch is a degenerate case"; + return uniq <= 3; +} - collect_switch_conv_info (swtch, &info); +/* Return true when cluster starting at START and ending at END (inclusive) + can build a bit test. */ - /* No error markers should reach here (they should be filtered out - during gimplification). */ - gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node); +bool +bit_test_cluster::can_be_handled (const vec &clusters, + unsigned start, unsigned end) +{ + /* 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; - /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ - gcc_checking_assert (! TREE_CONSTANT (info.index_expr)); + unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), + clusters[end]->get_high ()); + auto_bitmap dest_bbs; - if (info.uniq <= MAX_CASE_BIT_TESTS) + for (unsigned i = start; i <= end; i++) { - if (expand_switch_using_bit_tests_p (info.range_size, - info.uniq, info.count, - optimize_bb_for_speed_p - (gimple_bb (swtch)))) - { - if (dump_file) - fputs (" expanding as bit test is preferable\n", dump_file); - emit_case_bit_tests (swtch, info.index_expr, info.range_min, - info.range_size, info.range_max); - loops_state_set (LOOPS_NEED_FIXUP); - return NULL; - } - - if (info.uniq <= 2) - /* This will be expanded as a decision tree in stmt.c:expand_case. */ - return " expanding as jumps is preferable"; + simple_cluster *sc = static_cast (clusters[i]); + bitmap_set_bit (dest_bbs, sc->m_case_bb->index); } - /* If there is no common successor, we cannot do the transformation. */ - if (! info.final_bb) - return "no common successor to all case label target blocks found"; + return can_be_handled (range, bitmap_count_bits (dest_bbs)); +} - /* Check the case label values are within reasonable range: */ - if (!check_range (&info)) - { - gcc_assert (info.reason); - return info.reason; - } +/* Return true when COUNT of cases of UNIQ labels is beneficial for bit test + transformation. */ - /* For all the cases, see whether they are empty, the assignments they - represent constant and so on... */ - if (! check_all_empty_except_final (&info)) - { - gcc_assert (info.reason); - return info.reason; - } - if (!check_final_bb (swtch, &info)) +bool +bit_test_cluster::is_beneficial (unsigned count, unsigned uniq) +{ + 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 &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++) { - gcc_assert (info.reason); - return info.reason; + simple_cluster *sc = static_cast (clusters[i]); + bitmap_set_bit (dest_bbs, sc->m_case_bb->index); } - /* At this point all checks have passed and we can proceed with the - transformation. */ + unsigned uniq = bitmap_count_bits (dest_bbs); + unsigned count = end - start + 1; + return is_beneficial (count, uniq); +} - create_temp_arrays (&info); - gather_default_values (info.default_case_nonstandard - ? gimple_switch_label (swtch, 1) - : gimple_switch_default_label (swtch), &info); - build_constructors (swtch, &info); +/* Comparison function for qsort to order bit tests by decreasing + probability of execution. */ + +int +case_bit_test::cmp (const void *p1, const void *p2) +{ + const case_bit_test *const d1 = (const case_bit_test *) p1; + const case_bit_test *const d2 = (const case_bit_test *) p2; - build_arrays (swtch, &info); /* Build the static arrays and assignments. */ - gen_inbound_check (swtch, &info); /* Build the bounds check. */ + if (d2->bits != d1->bits) + return d2->bits - d1->bits; - /* Cleanup: */ - free_temp_arrays (&info); - return NULL; + /* Stabilize the sort. */ + return (LABEL_DECL_UID (CASE_LABEL (d2->label)) + - LABEL_DECL_UID (CASE_LABEL (d1->label))); } -/* The main function of the pass scans statements for switches and invokes - process_switch on them. */ +/* Expand a switch statement by a short sequence of bit-wise + comparisons. "switch(x)" is effectively converted into + "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are + integer constants. -namespace { + INDEX_EXPR is the value being switched on. -const pass_data pass_data_convert_switch = -{ - GIMPLE_PASS, /* type */ - "switchconv", /* name */ - OPTGROUP_NONE, /* optinfo_flags */ - TV_TREE_SWITCH_CONVERSION, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_update_ssa, /* todo_flags_finish */ -}; + MINVAL is the lowest case value of in the case nodes, + and RANGE is highest value minus MINVAL. MINVAL and RANGE + are not guaranteed to be of the same type as INDEX_EXPR + (the gimplifier doesn't change the type of case label values, + and MINVAL and RANGE are derived from those values). + MAXVAL is MINVAL + RANGE. -class pass_convert_switch : public gimple_opt_pass + There *MUST* be max_case_bit_tests or less unique case + node targets. */ + +void +bit_test_cluster::emit (tree index_expr, tree index_type, + tree, basic_block default_bb) { -public: - pass_convert_switch (gcc::context *ctxt) - : gimple_opt_pass (pass_data_convert_switch, ctxt) - {} + case_bit_test test[m_max_case_bit_tests] = { {} }; + unsigned int i, j, k; + unsigned int count; - /* opt_pass methods: */ - virtual bool gate (function *) { return flag_tree_switch_conversion != 0; } - virtual unsigned int execute (function *); + tree unsigned_index_type = range_check_type (index_type); -}; // class pass_convert_switch + gimple_stmt_iterator gsi; + gassign *shift_stmt; -unsigned int -pass_convert_switch::execute (function *fun) -{ - basic_block bb; + tree idx, tmp, csui; + tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1); + tree word_mode_zero = fold_convert (word_type_node, integer_zero_node); + tree word_mode_one = fold_convert (word_type_node, integer_one_node); + int prec = TYPE_PRECISION (word_type_node); + wide_int wone = wi::one (prec); - FOR_EACH_BB_FN (bb, fun) - { - const char *failure_reason; - gimple *stmt = last_stmt (bb); - if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) - { - if (dump_file) - { - expanded_location loc = expand_location (gimple_location (stmt)); + tree minval = get_low (); + tree maxval = get_high (); + tree range = int_const_binop (MINUS_EXPR, maxval, minval); + unsigned HOST_WIDE_INT bt_range = get_range (minval, maxval); - fprintf (dump_file, "beginning to process the following " - "SWITCH statement (%s:%d) : ------- \n", - loc.file, loc.line); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - putc ('\n', dump_file); - } + /* Go through all case labels, and collect the case labels, profile + counts, and other information we need to build the branch tests. */ + count = 0; + for (i = 0; i < m_cases.length (); i++) + { + unsigned int lo, hi; + simple_cluster *n = static_cast (m_cases[i]); + for (k = 0; k < count; k++) + if (n->m_case_bb == test[k].target_bb) + break; - failure_reason = process_switch (as_a (stmt)); - if (! failure_reason) - { - if (dump_file) - { - fputs ("Switch converted\n", dump_file); - fputs ("--------------------------------\n", dump_file); - } + if (k == count) + { + gcc_checking_assert (count < m_max_case_bit_tests); + test[k].mask = wi::zero (prec); + test[k].target_bb = n->m_case_bb; + test[k].label = n->m_case_label_expr; + test[k].bits = 0; + count++; + } - /* Make no effort to update the post-dominator tree. It is actually not - that hard for the transformations we have performed, but it is not - supported by iterate_fix_dominators. */ - free_dominance_info (CDI_POST_DOMINATORS); - } - else - { - if (dump_file) - { - fputs ("Bailing out - ", dump_file); - fputs (failure_reason, dump_file); - fputs ("\n--------------------------------\n", dump_file); - } - } - } - } + test[k].bits += n->get_range (n->get_low (), n->get_high ()); - return 0; -} + lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval)); + if (n->get_high () == NULL_TREE) + hi = lo; + else + hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (), + minval)); + + for (j = lo; j <= hi; j++) + test[k].mask |= wi::lshift (wone, j); + } + + qsort (test, count, sizeof (*test), case_bit_test::cmp); + + /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of + the minval subtractions, but it might make the mask constants more + expensive. So, compare the costs. */ + if (compare_tree_int (minval, 0) > 0 + && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) + { + int cost_diff; + HOST_WIDE_INT m = tree_to_uhwi (minval); + rtx reg = gen_raw_REG (word_mode, 10000); + bool speed_p = optimize_insn_for_speed_p (); + cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg, + GEN_INT (-m)), speed_p); + for (i = 0; i < count; i++) + { + rtx r = immed_wide_int_const (test[i].mask, word_mode); + cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), + word_mode, speed_p); + r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode); + cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), + word_mode, speed_p); + } + if (cost_diff > 0) + { + for (i = 0; i < count; i++) + test[i].mask = wi::lshift (test[i].mask, m); + minval = build_zero_cst (TREE_TYPE (minval)); + range = maxval; + } + } + + /* Now build the test-and-branch code. */ + + gsi = gsi_last_bb (m_case_bb); + + /* idx = (unsigned)x - minval. */ + idx = fold_convert (unsigned_index_type, index_expr); + idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx, + fold_convert (unsigned_index_type, minval)); + idx = force_gimple_operand_gsi (&gsi, idx, + /*simple=*/true, NULL_TREE, + /*before=*/true, GSI_SAME_STMT); + + if (m_handles_entire_switch) + { + /* if (idx > range) goto default */ + range + = force_gimple_operand_gsi (&gsi, + fold_convert (unsigned_index_type, range), + /*simple=*/true, NULL_TREE, + /*before=*/true, GSI_SAME_STMT); + tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); + basic_block new_bb + = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb, + profile_probability::unlikely ()); + gsi = gsi_last_bb (new_bb); + } + + /* csui = (1 << (word_mode) idx) */ + csui = make_ssa_name (word_type_node); + tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one, + fold_convert (word_type_node, idx)); + tmp = force_gimple_operand_gsi (&gsi, tmp, + /*simple=*/false, NULL_TREE, + /*before=*/true, GSI_SAME_STMT); + shift_stmt = gimple_build_assign (csui, tmp); + gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT); + update_stmt (shift_stmt); + + profile_probability prob = profile_probability::always (); + + /* for each unique set of cases: + if (const & csui) goto target */ + for (k = 0; k < count; k++) + { + prob = profile_probability::always ().apply_scale (test[k].bits, + bt_range); + bt_range -= test[k].bits; + tmp = wide_int_to_tree (word_type_node, test[k].mask); + tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); + tmp = force_gimple_operand_gsi (&gsi, tmp, + /*simple=*/true, NULL_TREE, + /*before=*/true, GSI_SAME_STMT); + tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero); + basic_block new_bb + = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb, prob); + gsi = gsi_last_bb (new_bb); + } -} // anon namespace + /* We should have removed all edges now. */ + gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); -gimple_opt_pass * -make_pass_convert_switch (gcc::context *ctxt) -{ - return new pass_convert_switch (ctxt); + /* If nothing matched, go to the default label. */ + edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU); + e->probability = profile_probability::always (); } -struct case_node -{ - case_node *left; /* Left son in binary tree. */ - case_node *right; /* Right son in binary tree; - also node chain. */ - case_node *parent; /* Parent of node in binary tree. */ - tree low; /* Lowest index value for this label. */ - tree high; /* Highest index value for this label. */ - basic_block case_bb; /* Label to jump to when node matches. */ - tree case_label; /* Label to jump to when node matches. */ - profile_probability prob; /* Probability of taking this case. */ - profile_probability subtree_prob; /* Probability of reaching subtree - rooted at this node. */ -}; +/* Split the basic block at the statement pointed to by GSIP, and insert + a branch to the target basic block of E_TRUE conditional on tree + expression COND. -typedef case_node *case_node_ptr; + It is assumed that there is already an edge from the to-be-split + basic block to E_TRUE->dest block. This edge is removed, and the + profile information on the edge is re-used for the new conditional + jump. -static basic_block emit_case_nodes (basic_block, tree, case_node_ptr, - basic_block, tree, profile_probability, - tree, hash_map *); -static bool node_has_low_bound (case_node_ptr, tree); -static bool node_has_high_bound (case_node_ptr, tree); -static bool node_is_bounded (case_node_ptr, tree); + The CFG is updated. The dominator tree will not be valid after + this transformation, but the immediate dominators are updated if + UPDATE_DOMINATORS is true. -/* Return the smallest number of different values for which it is best to use a - jump-table instead of a tree of conditional branches. */ + Returns the newly created basic block. */ -static unsigned int -case_values_threshold (void) +basic_block +bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, + tree cond, basic_block case_bb, + profile_probability prob) { - unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD); + tree tmp; + gcond *cond_stmt; + edge e_false; + basic_block new_bb, split_bb = gsi_bb (*gsip); - if (threshold == 0) - threshold = targetm.case_values_threshold (); + edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE); + e_true->probability = prob; + gcc_assert (e_true->src == split_bb); - return threshold; -} + tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL, + /*before=*/true, GSI_SAME_STMT); + cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE); + gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT); -/* Reset the aux field of all outgoing edges of basic block BB. */ + e_false = split_block (split_bb, cond_stmt); + new_bb = e_false->dest; + redirect_edge_pred (e_true, split_bb); -static inline void -reset_out_edges_aux (basic_block bb) -{ - edge e; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->succs) - e->aux = (void *) 0; + e_false->flags &= ~EDGE_FALLTHRU; + e_false->flags |= EDGE_FALSE_VALUE; + e_false->probability = e_true->probability.invert (); + new_bb->count = e_false->count (); + + return new_bb; } /* Compute the number of case labels that correspond to each outgoing edge of - STMT. Record this information in the aux field of the edge. */ + switch statement. Record this information in the aux field of the edge. */ -static inline void -compute_cases_per_edge (gswitch *stmt) +void +switch_decision_tree::compute_cases_per_edge () { - basic_block bb = gimple_bb (stmt); - reset_out_edges_aux (bb); - int ncases = gimple_switch_num_labels (stmt); + reset_out_edges_aux (m_switch); + int ncases = gimple_switch_num_labels (m_switch); for (int i = ncases - 1; i >= 1; --i) { - tree elt = gimple_switch_label (stmt, i); - tree lab = CASE_LABEL (elt); - basic_block case_bb = label_to_block_fn (cfun, lab); - edge case_edge = find_edge (bb, case_bb); + edge case_edge = gimple_switch_edge (cfun, m_switch, i); case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1); } } -/* Do the insertion of a case label into case_list. The labels are - fed to us in descending order from the sorted vector of case labels used - in the tree part of the middle end. So the list we construct is - sorted in ascending order. +/* Analyze switch statement and return true when the statement is expanded + as decision tree. */ - LABEL is the case label to be inserted. LOW and HIGH are the bounds - against which the index is compared to jump to LABEL and PROB is the - estimated probability LABEL is reached from the switch statement. */ - -static case_node * -add_case_node (case_node *head, tree low, tree high, basic_block case_bb, - tree case_label, profile_probability prob, - object_allocator &case_node_pool) +bool +switch_decision_tree::analyze_switch_statement () { - case_node *r; - - gcc_checking_assert (low); - gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high))); - - /* Add this label to the chain. */ - r = case_node_pool.allocate (); - r->low = low; - r->high = high; - r->case_bb = case_bb; - r->case_label = case_label; - r->parent = r->left = NULL; - r->prob = prob; - r->subtree_prob = prob; - r->right = head; - return r; -} + unsigned l = gimple_switch_num_labels (m_switch); + basic_block bb = gimple_bb (m_switch); + auto_vec clusters; + clusters.create (l - 1); -/* Dump ROOT, a list or tree of case nodes, to file. */ - -static void -dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level) -{ - if (root == 0) - return; - indent_level++; + basic_block default_bb = gimple_switch_default_bb (cfun, m_switch); + m_case_bbs.reserve (l); + m_case_bbs.quick_push (default_bb); - dump_case_nodes (f, root->left, indent_step, indent_level); + compute_cases_per_edge (); - fputs (";; ", f); - fprintf (f, "%*s", indent_step * indent_level, ""); - print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low))); - if (!tree_int_cst_equal (root->low, root->high)) + for (unsigned i = 1; i < l; i++) { - fprintf (f, " ... "); - print_dec (wi::to_wide (root->high), f, - TYPE_SIGN (TREE_TYPE (root->high))); - } - fputs ("\n", f); + tree elt = gimple_switch_label (m_switch, i); + tree lab = CASE_LABEL (elt); + basic_block case_bb = label_to_block (cfun, lab); + edge case_edge = find_edge (bb, case_bb); + tree low = CASE_LOW (elt); + tree high = CASE_HIGH (elt); - dump_case_nodes (f, root->right, indent_step, indent_level); -} + profile_probability p + = case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)); + clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest, + p)); + m_case_bbs.quick_push (case_edge->dest); + } -/* Take an ordered list of case nodes - and transform them into a near optimal binary tree, - on the assumption that any target code selection value is as - likely as any other. + reset_out_edges_aux (m_switch); - The transformation is performed by splitting the ordered - list into two equal sections plus a pivot. The parts are - then attached to the pivot as left and right branches. Each - branch is then transformed recursively. */ + /* Find jump table clusters. */ + vec output = jump_table_cluster::find_jump_tables (clusters); -static void -balance_case_nodes (case_node_ptr *head, case_node_ptr parent) -{ - case_node_ptr np; + /* Find bit test clusters. */ + vec output2; + auto_vec tmp; + output2.create (1); + tmp.create (1); - np = *head; - if (np) + for (unsigned i = 0; i < output.length (); i++) { - int i = 0; - int ranges = 0; - case_node_ptr *npp; - case_node_ptr left; - - /* Count the number of entries on branch. Also count the ranges. */ - - while (np) + cluster *c = output[i]; + if (c->get_type () != SIMPLE_CASE) { - if (!tree_int_cst_equal (np->low, np->high)) - ranges++; - - i++; - np = np->right; - } - - if (i > 2) - { - /* Split this list if it is long enough for that to help. */ - npp = head; - left = *npp; - - /* If there are just three nodes, split at the middle one. */ - if (i == 3) - npp = &(*npp)->right; - else + if (!tmp.is_empty ()) { - /* 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)->low, (*npp)->high)) - i--; - i--; - if (i <= 0) - break; - npp = &(*npp)->right; - } + vec n = bit_test_cluster::find_bit_tests (tmp); + output2.safe_splice (n); + n.release (); + tmp.truncate (0); } - *head = np = *npp; - *npp = 0; - np->parent = parent; - np->left = left; - - /* Optimize each of the two split parts. */ - balance_case_nodes (&np->left, np); - balance_case_nodes (&np->right, np); - np->subtree_prob = np->prob; - np->subtree_prob += np->left->subtree_prob; - np->subtree_prob += np->right->subtree_prob; + output2.safe_push (c); } else - { - /* Else leave this branch as one level, - but fill in `parent' fields. */ - np = *head; - np->parent = parent; - np->subtree_prob = np->prob; - for (; np->right; np = np->right) - { - np->right->parent = np; - (*head)->subtree_prob += np->right->subtree_prob; - } - } + tmp.safe_push (c); } -} -/* Return true if a switch should be expanded as a decision tree. - RANGE is the difference between highest and lowest case. - UNIQ is number of unique case node targets, not counting the default case. - COUNT is the number of comparisons needed, not counting the default case. */ - -static bool -expand_switch_as_decision_tree_p (tree range, - unsigned int uniq ATTRIBUTE_UNUSED, - unsigned int count) -{ - int max_ratio; - - /* If neither casesi or tablejump is available, or flag_jump_tables - over-ruled us, we really have no choice. */ - if (!targetm.have_casesi () && !targetm.have_tablejump ()) - return true; - if (!flag_jump_tables) - return true; -#ifndef ASM_OUTPUT_ADDR_DIFF_ELT - if (flag_pic) - return true; -#endif + /* We still can have a temporary vector to test. */ + if (!tmp.is_empty ()) + { + vec n = bit_test_cluster::find_bit_tests (tmp); + output2.safe_splice (n); + n.release (); + } - /* If the switch is relatively small such that the cost of one - indirect jump on the target are higher than the cost of a - decision tree, go with the decision tree. + if (dump_file) + { + fprintf (dump_file, ";; GIMPLE switch case clusters: "); + for (unsigned i = 0; i < output2.length (); i++) + output2[i]->dump (dump_file, dump_flags & TDF_DETAILS); + fprintf (dump_file, "\n"); + } - If range of values is much bigger than number of values, - or if it is too large to represent in a HOST_WIDE_INT, - make a sequence of conditional branches instead of a dispatch. + output.release (); - The definition of "much bigger" depends on whether we are - optimizing for size or for speed. If the former, the maximum - ratio range/count = 3, because this was found to be the optimal - ratio for size on i686-pc-linux-gnu, see PR11823. The ratio - 10 is much older, and was probably selected after an extensive - benchmarking investigation on numerous platforms. Or maybe it - just made sense to someone at some point in the history of GCC, - who knows... */ - max_ratio = optimize_insn_for_size_p () ? 3 : 10; - if (count < case_values_threshold () || !tree_fits_uhwi_p (range) - || compare_tree_int (range, max_ratio * count) > 0) - return true; + bool expanded = try_switch_expansion (output2); - return false; -} + for (unsigned i = 0; i < output2.length (); i++) + delete output2[i]; -static void -fix_phi_operands_for_edge (edge e, hash_map *phi_mapping) -{ - basic_block bb = e->dest; - gphi_iterator gsi; - for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); + output2.release (); - tree *definition = phi_mapping->get (gimple_phi_result (phi)); - if (definition) - add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION); - } + return expanded; } +/* Attempt to expand CLUSTERS as a decision tree. Return true when + expanded. */ -/* Add an unconditional jump to CASE_BB that happens in basic block BB. */ - -static void -emit_jump (basic_block bb, basic_block case_bb, - hash_map *phi_mapping) +bool +switch_decision_tree::try_switch_expansion (vec &clusters) { - edge e = single_succ_edge (bb); - redirect_edge_succ (e, case_bb); - fix_phi_operands_for_edge (e, phi_mapping); -} + tree index_expr = gimple_switch_index (m_switch); + tree index_type = TREE_TYPE (index_expr); + basic_block bb = gimple_bb (m_switch); -/* Generate a decision tree, switching on INDEX_EXPR and jumping to - one of the labels in CASE_LIST or to the DEFAULT_LABEL. - DEFAULT_PROB is the estimated probability that it jumps to - DEFAULT_LABEL. + if (gimple_switch_num_labels (m_switch) == 1 + || range_check_type (index_type) == NULL_TREE) + return false; - We generate a binary decision tree to select the appropriate target - code. */ + /* Find the default case target label. */ + edge default_edge = gimple_switch_default_edge (cfun, m_switch); + m_default_bb = default_edge->dest; -static void -emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type, - case_node_ptr case_list, basic_block default_bb, - tree default_label, profile_probability default_prob, - hash_map *phi_mapping) -{ - balance_case_nodes (&case_list, NULL); + /* Do the insertion of a case label into m_case_list. The labels are + fed to us in descending order from the sorted vector of case labels used + in the tree part of the middle end. So the list we construct is + sorted in ascending order. */ - if (dump_file) - dump_function_to_file (current_function_decl, dump_file, dump_flags); - if (dump_file && (dump_flags & TDF_DETAILS)) + for (int i = clusters.length () - 1; i >= 0; i--) { - int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2; - fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n"); - dump_case_nodes (dump_file, case_list, indent_step, 0); + case_tree_node *r = m_case_list; + m_case_list = m_case_node_pool.allocate (); + m_case_list->m_right = r; + m_case_list->m_c = clusters[i]; } - basic_block bb = gimple_bb (s); + record_phi_operand_mapping (); + + /* Split basic block that contains the gswitch statement. */ gimple_stmt_iterator gsi = gsi_last_bb (bb); edge e; if (gsi_end_p (gsi)) @@ -1988,27 +1823,54 @@ emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type, } bb = split_edge (e); - bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label, - default_prob, index_type, phi_mapping); + /* Create new basic blocks for non-case clusters where specific expansion + needs to happen. */ + for (unsigned i = 0; i < clusters.length (); i++) + 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; + } - if (bb) - emit_jump (bb, default_bb, phi_mapping); + /* Do not do an extra work for a single cluster. */ + if (clusters.length () == 1 + && clusters[0]->get_type () != SIMPLE_CASE) + { + cluster *c = clusters[0]; + c->emit (index_expr, index_type, + gimple_switch_default_label (m_switch), m_default_bb); + redirect_edge_succ (single_succ_edge (bb), c->m_case_bb); + } + else + { + emit (bb, index_expr, default_edge->probability, index_type); + + /* Emit cluster-specific switch handling. */ + for (unsigned i = 0; i < clusters.length (); i++) + if (clusters[i]->get_type () != SIMPLE_CASE) + clusters[i]->emit (index_expr, index_type, + gimple_switch_default_label (m_switch), + m_default_bb); + } - /* Remove all edges and do just an edge that will reach default_bb. */ - gsi = gsi_last_bb (gimple_bb (s)); - gsi_remove (&gsi, true); + fix_phi_operands_for_edges (); + + return true; } -static void -record_phi_operand_mapping (const vec bbs, basic_block switch_bb, - hash_map *map) +/* Before switch transformation, record all SSA_NAMEs defined in switch BB + and used in a label basic block. */ + +void +switch_decision_tree::record_phi_operand_mapping () { + basic_block switch_bb = gimple_bb (m_switch); /* Record all PHI nodes that have to be fixed after conversion. */ - for (unsigned i = 0; i < bbs.length (); i++) + for (unsigned i = 0; i < m_case_bbs.length (); i++) { - basic_block bb = bbs[i]; - gphi_iterator gsi; + basic_block bb = m_case_bbs[i]; for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); @@ -2020,7 +1882,7 @@ record_phi_operand_mapping (const vec bbs, basic_block switch_bb, { tree def = gimple_phi_arg_def (phi, i); tree result = gimple_phi_result (phi); - map->put (result, def); + m_phi_mapping.put (result, def); break; } } @@ -2028,219 +1890,212 @@ record_phi_operand_mapping (const vec bbs, basic_block switch_bb, } } -/* Attempt to expand gimple switch STMT to a decision tree. */ +/* Append new operands to PHI statements that were introduced due to + addition of new edges to case labels. */ -static bool -try_switch_expansion (gswitch *stmt) +void +switch_decision_tree::fix_phi_operands_for_edges () { - tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; - basic_block default_bb; - unsigned int count, uniq; - int i; - int ncases = gimple_switch_num_labels (stmt); - tree index_expr = gimple_switch_index (stmt); - tree index_type = TREE_TYPE (index_expr); - tree elt; - basic_block bb = gimple_bb (stmt); - - hash_map phi_mapping; - auto_vec case_bbs; - - /* A list of case labels; it is first built as a list and it may then - be rearranged into a nearly balanced binary tree. */ - case_node *case_list = 0; - - /* A pool for case nodes. */ - object_allocator case_node_pool ("struct case_node pool"); - - /* cleanup_tree_cfg removes all SWITCH_EXPR with their index - expressions being INTEGER_CST. */ - gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); + gphi_iterator gsi; - if (ncases == 1) - return false; + for (unsigned i = 0; i < m_case_bbs.length (); i++) + { + basic_block bb = m_case_bbs[i]; + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + for (unsigned j = 0; j < gimple_phi_num_args (phi); j++) + { + tree def = gimple_phi_arg_def (phi, j); + if (def == NULL_TREE) + { + edge e = gimple_phi_arg_edge (phi, j); + tree *definition + = m_phi_mapping.get (gimple_phi_result (phi)); + gcc_assert (definition); + add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION); + } + } + } + } +} - /* Find the default case target label. */ - tree default_label = CASE_LABEL (gimple_switch_default_label (stmt)); - default_bb = label_to_block_fn (cfun, default_label); - edge default_edge = find_edge (bb, default_bb); - profile_probability default_prob = default_edge->probability; - case_bbs.safe_push (default_bb); - - /* Get upper and lower bounds of case values. */ - elt = gimple_switch_label (stmt, 1); - minval = fold_convert (index_type, CASE_LOW (elt)); - elt = gimple_switch_label (stmt, ncases - 1); - if (CASE_HIGH (elt)) - maxval = fold_convert (index_type, CASE_HIGH (elt)); - else - maxval = fold_convert (index_type, CASE_LOW (elt)); +/* Generate a decision tree, switching on INDEX_EXPR and jumping to + one of the labels in CASE_LIST or to the DEFAULT_LABEL. - /* Compute span of values. */ - range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); + We generate a binary decision tree to select the appropriate target + code. */ - /* Listify the labels queue and gather some numbers to decide - how to expand this switch. */ - uniq = 0; - count = 0; - hash_set seen_labels; - compute_cases_per_edge (stmt); +void +switch_decision_tree::emit (basic_block bb, tree index_expr, + profile_probability default_prob, tree index_type) +{ + balance_case_nodes (&m_case_list, NULL); - for (i = ncases - 1; i >= 1; --i) + if (dump_file) + dump_function_to_file (current_function_decl, dump_file, dump_flags); + if (dump_file && (dump_flags & TDF_DETAILS)) { - elt = gimple_switch_label (stmt, i); - tree low = CASE_LOW (elt); - gcc_assert (low); - tree high = CASE_HIGH (elt); - gcc_assert (!high || tree_int_cst_lt (low, high)); - tree lab = CASE_LABEL (elt); - - /* Count the elements. - A range counts double, since it requires two compares. */ - count++; - if (high) - count++; - - /* If we have not seen this label yet, then increase the - number of unique case node targets seen. */ - if (!seen_labels.add (lab)) - uniq++; - - /* The bounds on the case range, LOW and HIGH, have to be converted - to case's index type TYPE. Note that the original type of the - case index in the source code is usually "lost" during - gimplification due to type promotion, but the case labels retain the - original type. Make sure to drop overflow flags. */ - low = fold_convert (index_type, low); - if (TREE_OVERFLOW (low)) - low = wide_int_to_tree (index_type, wi::to_wide (low)); - - /* The canonical from of a case label in GIMPLE is that a simple case - has an empty CASE_HIGH. For the casesi and tablejump expanders, - the back ends want simple cases to have high == low. */ - if (!high) - high = low; - high = fold_convert (index_type, high); - if (TREE_OVERFLOW (high)) - high = wide_int_to_tree (index_type, wi::to_wide (high)); - - basic_block case_bb = label_to_block_fn (cfun, lab); - edge case_edge = find_edge (bb, case_bb); - case_list = add_case_node ( - case_list, low, high, case_bb, lab, - case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)), - case_node_pool); - - case_bbs.safe_push (case_bb); + int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2; + fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n"); + gcc_assert (m_case_list != NULL); + dump_case_nodes (dump_file, m_case_list, indent_step, 0); } - reset_out_edges_aux (bb); - record_phi_operand_mapping (case_bbs, bb, &phi_mapping); - /* cleanup_tree_cfg removes all SWITCH_EXPR with a single - destination, such as one with a default case only. - It also removes cases that are out of range for the switch - type, so we should never get a zero here. */ - gcc_assert (count > 0); + bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type, + gimple_location (m_switch)); - /* Decide how to expand this switch. - The two options at this point are a dispatch table (casesi or - tablejump) or a decision tree. */ + if (bb) + emit_jump (bb, m_default_bb); - if (expand_switch_as_decision_tree_p (range, uniq, count)) - { - emit_case_decision_tree (stmt, index_expr, index_type, case_list, - default_bb, default_label, default_prob, - &phi_mapping); - return true; - } + /* Remove all edges and do just an edge that will reach default_bb. */ + bb = gimple_bb (m_switch); + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gsi_remove (&gsi, true); - return false; + delete_basic_block (bb); } -/* The main function of the pass scans statements for switches and invokes - process_switch on them. */ +/* Take an ordered list of case nodes + and transform them into a near optimal binary tree, + on the assumption that any target code selection value is as + likely as any other. -namespace { + The transformation is performed by splitting the ordered + list into two equal sections plus a pivot. The parts are + then attached to the pivot as left and right branches. Each + branch is then transformed recursively. */ -const pass_data pass_data_lower_switch = +void +switch_decision_tree::balance_case_nodes (case_tree_node **head, + case_tree_node *parent) { - GIMPLE_PASS, /* type */ - "switchlower", /* name */ - OPTGROUP_NONE, /* optinfo_flags */ - TV_TREE_SWITCH_LOWERING, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */ -}; + case_tree_node *np; -class pass_lower_switch : public gimple_opt_pass -{ -public: - pass_lower_switch (gcc::context *ctxt) - : gimple_opt_pass (pass_data_lower_switch, ctxt) - {} + np = *head; + if (np) + { + int i = 0; + int ranges = 0; + case_tree_node **npp; + case_tree_node *left; + profile_probability prob = profile_probability::never (); - /* opt_pass methods: */ - virtual bool gate (function *) { return true; } - virtual unsigned int execute (function *); + /* Count the number of entries on branch. Also count the ranges. */ + + while (np) + { + if (!tree_int_cst_equal (np->m_c->get_low (), np->m_c->get_high ())) + ranges++; + + i++; + prob += np->m_c->m_prob; + np = np->m_right; + } + + if (i > 2) + { + /* 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); -}; // class pass_lower_switch + /* Find the place in the list that bisects the list's total cost, + where ranges count as 2. */ + while (1) + { + /* 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; + } -unsigned int -pass_lower_switch::execute (function *fun) -{ - basic_block bb; - bool expanded = false; + np = *npp; + *npp = 0; + *head = np; + np->m_parent = parent; + np->m_left = left == np ? NULL : left; - FOR_EACH_BB_FN (bb, fun) - { - gimple *stmt = last_stmt (bb); - if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) + /* 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; + 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 { - if (dump_file) + /* Else leave this branch as one level, + but fill in `parent' fields. */ + np = *head; + np->m_parent = parent; + np->m_c->m_subtree_prob = np->m_c->m_prob; + for (; np->m_right; np = np->m_right) { - expanded_location loc = expand_location (gimple_location (stmt)); - - fprintf (dump_file, "beginning to process the following " - "SWITCH statement (%s:%d) : ------- \n", - loc.file, loc.line); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - putc ('\n', dump_file); + np->m_right->m_parent = np; + (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob; } - - expanded |= try_switch_expansion (as_a (stmt)); } } +} - if (expanded) - { - free_dominance_info (CDI_DOMINATORS); - free_dominance_info (CDI_POST_DOMINATORS); - mark_virtual_operands_for_renaming (cfun); - } +/* Dump ROOT, a list or tree of case nodes, to file. */ - return 0; +void +switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root, + int indent_step, int indent_level) +{ + if (root == 0) + return; + indent_level++; + + dump_case_nodes (f, root->m_left, indent_step, indent_level); + + fputs (";; ", f); + fprintf (f, "%*s", indent_step * indent_level, ""); + root->m_c->dump (f); + root->m_c->m_prob.dump (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); } -} // anon namespace -gimple_opt_pass * -make_pass_lower_switch (gcc::context *ctxt) +/* Add an unconditional jump to CASE_BB that happens in basic block BB. */ + +void +switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb) { - return new pass_lower_switch (ctxt); + edge e = single_succ_edge (bb); + redirect_edge_succ (e, case_bb); } -/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. - PROB is the probability of jumping to LABEL. */ -static basic_block -do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb, - profile_probability prob, hash_map *phi_mapping) +/* Generate code to compare OP0 with OP1 so that the condition codes are + set and to jump to LABEL_BB if the condition is true. + COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.). + PROB is the probability of jumping to LABEL_BB. */ + +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, + location_t loc) { - gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE); + // 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_before (&gsi, cond, GSI_SAME_STMT); + gsi_insert_after (&gsi, cond, GSI_NEW_STMT); gcc_assert (single_succ_p (bb)); @@ -2248,44 +2103,29 @@ do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb, edge false_edge = split_block (bb, cond); false_edge->flags = EDGE_FALSE_VALUE; false_edge->probability = prob.invert (); - false_edge->count = bb->count.apply_probability (false_edge->probability); edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); - fix_phi_operands_for_edge (true_edge, phi_mapping); true_edge->probability = prob; - true_edge->count = bb->count.apply_probability (true_edge->probability); return false_edge->dest; } -/* Generate code to compare X with Y so that the condition codes are - set and to jump to LABEL if the condition is true. If X is a - constant and Y is not a constant, then the comparison is swapped to - ensure that the comparison RTL has the canonical form. - - UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they - need to be widened. UNSIGNEDP is also used to select the proper - branch condition code. - - If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y. - - MODE is the mode of the inputs (in case they are const_int). - - COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.). - It will be potentially converted into an unsigned variant based on - UNSIGNEDP to select a proper jump instruction. - - PROB is the probability of jumping to LABEL. */ +/* 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. */ -static basic_block -emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1, - tree_code comparison, basic_block label_bb, - profile_probability prob, - hash_map *phi_mapping) +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) { - gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE); + 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_after (&gsi, cond, GSI_NEW_STMT); + gsi_insert_before (&gsi, cond, GSI_SAME_STMT); gcc_assert (single_succ_p (bb)); @@ -2293,188 +2133,97 @@ emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1, edge false_edge = split_block (bb, cond); false_edge->flags = EDGE_FALSE_VALUE; false_edge->probability = prob.invert (); - false_edge->count = bb->count.apply_probability (false_edge->probability); edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); - fix_phi_operands_for_edge (true_edge, phi_mapping); true_edge->probability = prob; - true_edge->count = bb->count.apply_probability (true_edge->probability); return false_edge->dest; } -/* Computes the conditional probability of jumping to a target if the branch - instruction is executed. - TARGET_PROB is the estimated probability of jumping to a target relative - to some basic block BB. - BASE_PROB is the probability of reaching the branch instruction relative - to the same basic block BB. */ - -static inline profile_probability -conditional_probability (profile_probability target_prob, - profile_probability base_prob) -{ - return target_prob / base_prob; -} - /* 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. - INDEX_TYPE is the type of the index of the switch. - - Care is taken to prune redundant tests from the decision tree - by detecting any boundary conditions already checked by - emitted rtx. (See node_has_high_bound, node_has_low_bound - and node_is_bounded, above.) - - Where the test conditions can be shown to be redundant we emit - an unconditional jump to the target code. As a further - optimization, the subordinates of a tree node are examined to - check for bounded nodes. In this case conditional and/or - unconditional jumps as a result of the boundary check for the - current node are arranged to target the subordinates associated - code for out of bound conditions on the current node. - - We can assume that when control reaches the code generated here, - the index value has already been compared with the parents - of this node, and determined to be on the same side of each parent - as this node is. Thus, if this node tests for the value 51, - and a parent tested for 52, we don't need to consider - the possibility of a value greater than 51. If another parent - tests for the value 50, then this node need not test anything. */ - -static basic_block -emit_case_nodes (basic_block bb, tree index, case_node_ptr node, - basic_block default_bb, tree default_label, - profile_probability default_prob, tree index_type, - hash_map *phi_mapping) + DEFAULT_PROB is probability of cases leading to default BB. + INDEX_TYPE is the type of the index of the switch. */ + +basic_block +switch_decision_tree::emit_case_nodes (basic_block bb, tree index, + case_tree_node *node, + profile_probability default_prob, + tree index_type, location_t loc) { - /* If INDEX has an unsigned type, we must make unsigned branches. */ - profile_probability probability; - profile_probability prob = node->prob, subtree_prob = node->subtree_prob; + profile_probability p; - /* See if our parents have already tested everything for us. - If they have, emit an unconditional jump for this node. */ - if (node_is_bounded (node, index_type)) - { - emit_jump (bb, node->case_bb, phi_mapping); - return NULL; - } + /* If node is null, we are done. */ + if (node == NULL) + return bb; - else if (tree_int_cst_equal (node->low, node->high)) + /* Single value case. */ + if (node->m_c->is_single_value_p ()) { - probability = conditional_probability (prob, subtree_prob + default_prob); /* Node is single valued. First see if the index expression matches this node and then check our children, if any. */ - bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability, - phi_mapping); + 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. */ - subtree_prob -= prob; - if (node->right != 0 && node->left != 0) - { - /* This node has children on both sides. - Dispatch to one side or the other - by comparing the index value with this node's value. - If one subtree is bounded, check that one first, - so we can avoid real branches in the tree. */ + node->m_c->m_subtree_prob -= p; - if (node_is_bounded (node->right, index_type)) - { - probability - = conditional_probability (node->right->prob, - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - node->right->case_bb, probability, - phi_mapping); - bb = emit_case_nodes (bb, index, node->left, default_bb, - default_label, default_prob, index_type, - phi_mapping); - } - - else if (node_is_bounded (node->left, index_type)) - { - probability - = conditional_probability (node->left->prob, - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR, - node->left->case_bb, probability, - phi_mapping); - bb = emit_case_nodes (bb, index, node->right, default_bb, - default_label, default_prob, index_type, - phi_mapping); - } + if (node->m_left != NULL && node->m_right != NULL) + { + /* 1) the node has both children - /* If both children are single-valued cases with no + If both children are single-valued cases with no children, finish up all the work. This way, we can save one ordered comparison. */ - else if (tree_int_cst_equal (node->right->low, node->right->high) - && node->right->left == 0 && node->right->right == 0 - && tree_int_cst_equal (node->left->low, node->left->high) - && node->left->left == 0 && node->left->right == 0) + + 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 ()) { - /* Neither node is bounded. First distinguish the two sides; - then emit the code for one side at a time. */ - - /* See if the value matches what the right hand side - wants. */ - probability - = conditional_probability (node->right->prob, - subtree_prob + default_prob); - bb = do_jump_if_equal (bb, index, node->right->low, - node->right->case_bb, probability, - phi_mapping); - - /* See if the value matches what the left hand side - wants. */ - probability - = conditional_probability (node->left->prob, - subtree_prob + default_prob); - bb = do_jump_if_equal (bb, index, node->left->low, - node->left->case_bb, probability, - phi_mapping); + 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 { - /* Neither node is bounded. First distinguish the two sides; - then emit the code for one side at a time. */ - + /* 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); - /* The default label could be reached either through the right - subtree or the left subtree. Divide the probability - equally. */ - probability - = conditional_probability (node->right->subtree_prob - + default_prob.apply_scale (1, 2), - subtree_prob + default_prob); - /* See if the value is on the right. */ - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - test_bb, probability, phi_mapping); + 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); - /* Value must be on the left. - Handle the left-hand subtree. */ - bb = emit_case_nodes (bb, index, node->left, default_bb, - default_label, default_prob, index_type, - phi_mapping); - /* If left-hand subtree does nothing, - go to default. */ - - if (bb && default_bb) - emit_jump (bb, default_bb, phi_mapping); - - /* Code branches here for the right-hand subtree. */ - bb = emit_case_nodes (test_bb, index, node->right, default_bb, - default_label, default_prob, index_type, - phi_mapping); + /* 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->right != 0 && node->left == 0) + 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. @@ -2482,69 +2231,54 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node, does not have any children and is single valued; it would cost too much space to save so little time. */ - if (node->right->right || node->right->left - || !tree_int_cst_equal (node->right->low, node->right->high)) + if (node->m_right->has_child () + || !node->m_right->m_c->is_single_value_p ()) { - if (!node_has_low_bound (node, index_type)) - { - probability - = conditional_probability (default_prob.apply_scale (1, 2), - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR, - default_bb, probability, - phi_mapping); - default_prob = default_prob.apply_scale (1, 2); - } + 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->right, default_bb, - default_label, default_prob, index_type, - phi_mapping); + bb = emit_case_nodes (bb, index, node->m_right, default_prob, + index_type, loc); } else { - probability - = conditional_probability (node->right->subtree_prob, - subtree_prob + default_prob); /* 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. */ - bb = do_jump_if_equal (bb, index, node->right->low, - node->right->case_bb, probability, - phi_mapping); + 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->right == 0 && node->left != 0) + else if (node->m_left != NULL && node->m_right == NULL) { - /* Just one subtree, on the left. */ - if (node->left->left || node->left->right - || !tree_int_cst_equal (node->left->low, node->left->high)) + /* 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 ()) { - if (!node_has_high_bound (node, index_type)) - { - probability - = conditional_probability (default_prob.apply_scale (1, 2), - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - default_bb, probability, - phi_mapping); + 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->left, default_bb, - default_label, default_prob, index_type, - phi_mapping); + bb = emit_case_nodes (bb, index, node->m_left, default_prob, + index_type, loc); } else { - probability - = conditional_probability (node->left->subtree_prob, - subtree_prob + default_prob); /* 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. */ - do_jump_if_equal (bb, index, node->left->low, node->left->case_bb, - probability, phi_mapping); + 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); } } } @@ -2553,169 +2287,55 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node, /* 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->right != 0 && node->left != 0) + if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE) { - /* Node has subtrees on both sides. - If the right-hand subtree is bounded, - test for it first, since we can go straight there. - Otherwise, we need to make a branch in the control structure, - then handle the two subtrees. */ - basic_block test_bb = NULL; - - if (node_is_bounded (node->right, index_type)) - { - /* Right hand node is fully bounded so we can eliminate any - testing and branch directly to the target code. */ - probability - = conditional_probability (node->right->subtree_prob, - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - node->right->case_bb, probability, - phi_mapping); - } - else - { - /* Right hand node requires testing. - Branch to a label where we will handle it later. */ + /* 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); - test_bb = split_edge (single_succ_edge (bb)); - redirect_edge_succ (single_pred_edge (test_bb), - single_succ_edge (bb)->dest); - probability - = conditional_probability (node->right->subtree_prob - + default_prob.apply_scale (1, 2), - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - test_bb, probability, phi_mapping); - default_prob = default_prob.apply_scale (1, 2); - } + 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)); - /* Value belongs to this node or to the left-hand subtree. */ + 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); - probability - = conditional_probability (prob, subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR, - node->case_bb, probability, - phi_mapping); + /* 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->left, default_bb, - default_label, default_prob, index_type, - phi_mapping); - - /* If right node had to be handled later, do that now. */ - if (test_bb) - { - /* If the left-hand subtree fell through, - don't let it fall into the right-hand subtree. */ - if (bb && default_bb) - emit_jump (bb, default_bb, phi_mapping); - - bb = emit_case_nodes (test_bb, index, node->right, default_bb, - default_label, default_prob, index_type, - phi_mapping); - } - } - - else if (node->right != 0 && node->left == 0) - { - /* Deal with values to the left of this node, - if they are possible. */ - if (!node_has_low_bound (node, index_type)) - { - probability - = conditional_probability (default_prob.apply_scale (1, 2), - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR, - default_bb, probability, - phi_mapping); - default_prob = default_prob.apply_scale (1, 2); - } - - /* Value belongs to this node or to the right-hand subtree. */ - - probability - = conditional_probability (prob, subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR, - node->case_bb, probability, - phi_mapping); - - bb = emit_case_nodes (bb, index, node->right, default_bb, - default_label, default_prob, index_type, - phi_mapping); - } - - else if (node->right == 0 && node->left != 0) - { - /* Deal with values to the right of this node, - if they are possible. */ - if (!node_has_high_bound (node, index_type)) - { - probability - = conditional_probability (default_prob.apply_scale (1, 2), - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - default_bb, probability, - phi_mapping); - default_prob = default_prob.apply_scale (1, 2); - } - - /* Value belongs to this node or to the left-hand subtree. */ + bb = emit_case_nodes (bb, index, node->m_left, + default_prob, index_type, loc); - probability - = conditional_probability (prob, subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR, - node->case_bb, probability, - phi_mapping); + /* 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 (bb, index, node->left, default_bb, - default_label, default_prob, index_type, - phi_mapping); + 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. */ - bool high_bound = node_has_high_bound (node, index_type); - bool low_bound = node_has_low_bound (node, index_type); - - if (!high_bound && low_bound) - { - probability - = conditional_probability (default_prob, - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - default_bb, probability, - phi_mapping); - } + 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); - else if (!low_bound && high_bound) - { - probability - = conditional_probability (default_prob, - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR, - default_bb, probability, - phi_mapping); - } - else if (!low_bound && !high_bound) - { - tree lhs, rhs; - generate_range_test (bb, index, node->low, node->high, - &lhs, &rhs); - probability - = conditional_probability (default_prob, - subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, - default_bb, probability, - phi_mapping); - } + bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, + m_default_bb, p, loc); - emit_jump (bb, node->case_bb, phi_mapping); + emit_jump (bb, node->m_c->m_case_bb); return NULL; } } @@ -2723,108 +2343,203 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node, return bb; } -/* Search the parent sections of the case node tree - to see if a test for the lower bound of NODE would be redundant. - INDEX_TYPE is the type of the index expression. +/* The main function of the pass scans statements for switches and invokes + process_switch on them. */ - The instructions to generate the case decision tree are - output in the same order as nodes are processed so it is - known that if a parent node checks the range of the current - node minus one that the current node is bounded at its lower - span. Thus the test would be redundant. */ +namespace { -static bool -node_has_low_bound (case_node_ptr node, tree index_type) +const pass_data pass_data_convert_switch = { - tree low_minus_one; - case_node_ptr pnode; + GIMPLE_PASS, /* type */ + "switchconv", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_SWITCH_CONVERSION, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_update_ssa, /* todo_flags_finish */ +}; - /* If the lower bound of this node is the lowest value in the index type, - we need not test it. */ +class pass_convert_switch : public gimple_opt_pass +{ +public: + pass_convert_switch (gcc::context *ctxt) + : gimple_opt_pass (pass_data_convert_switch, ctxt) + {} - if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) - return true; + /* opt_pass methods: */ + virtual bool gate (function *) { return flag_tree_switch_conversion != 0; } + virtual unsigned int execute (function *); - /* If this node has a left branch, the value at the left must be less - than that at this node, so it cannot be bounded at the bottom and - we need not bother testing any further. */ +}; // class pass_convert_switch - if (node->left) - return false; +unsigned int +pass_convert_switch::execute (function *fun) +{ + basic_block bb; + bool cfg_altered = false; + + FOR_EACH_BB_FN (bb, fun) + { + gimple *stmt = last_stmt (bb); + if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) + { + if (dump_file) + { + expanded_location loc = expand_location (gimple_location (stmt)); - low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low, - build_int_cst (TREE_TYPE (node->low), 1)); + fprintf (dump_file, "beginning to process the following " + "SWITCH statement (%s:%d) : ------- \n", + loc.file, loc.line); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + putc ('\n', dump_file); + } - /* If the subtraction above overflowed, we can't verify anything. - Otherwise, look for a parent that tests our value - 1. */ + switch_conversion sconv; + sconv.expand (as_a (stmt)); + cfg_altered |= sconv.m_cfg_altered; + if (!sconv.m_reason) + { + if (dump_file) + { + fputs ("Switch converted\n", dump_file); + fputs ("--------------------------------\n", dump_file); + } - if (!tree_int_cst_lt (low_minus_one, node->low)) - return false; + /* Make no effort to update the post-dominator tree. + It is actually not that hard for the transformations + we have performed, but it is not supported + by iterate_fix_dominators. */ + free_dominance_info (CDI_POST_DOMINATORS); + } + else + { + if (dump_file) + { + fputs ("Bailing out - ", dump_file); + fputs (sconv.m_reason, dump_file); + fputs ("\n--------------------------------\n", dump_file); + } + } + } + } - for (pnode = node->parent; pnode; pnode = pnode->parent) - if (tree_int_cst_equal (low_minus_one, pnode->high)) - return true; + return cfg_altered ? TODO_cleanup_cfg : 0;; +} + +} // anon namespace - return false; +gimple_opt_pass * +make_pass_convert_switch (gcc::context *ctxt) +{ + return new pass_convert_switch (ctxt); } -/* Search the parent sections of the case node tree - to see if a test for the upper bound of NODE would be redundant. - INDEX_TYPE is the type of the index expression. +/* The main function of the pass scans statements for switches and invokes + process_switch on them. */ - The instructions to generate the case decision tree are - output in the same order as nodes are processed so it is - known that if a parent node checks the range of the current - node plus one that the current node is bounded at its upper - span. Thus the test would be redundant. */ +namespace { -static bool -node_has_high_bound (case_node_ptr node, tree index_type) +template class pass_lower_switch: public gimple_opt_pass { - tree high_plus_one; - case_node_ptr pnode; +public: + pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {} + + static const pass_data data; + opt_pass * + clone () + { + return new pass_lower_switch (m_ctxt); + } - /* If there is no upper bound, obviously no test is needed. */ + virtual bool + gate (function *) + { + return !O0 || !optimize; + } - if (TYPE_MAX_VALUE (index_type) == NULL) - return true; + virtual unsigned int execute (function *fun); +}; // class pass_lower_switch - /* If the upper bound of this node is the highest value in the type - of the index expression, we need not test against it. */ +template +const pass_data pass_lower_switch::data = { + GIMPLE_PASS, /* type */ + O0 ? "switchlower_O0" : "switchlower", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_SWITCH_LOWERING, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */ +}; - if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) - return true; +template +unsigned int +pass_lower_switch::execute (function *fun) +{ + basic_block bb; + bool expanded = false; - /* If this node has a right branch, the value at the right must be greater - than that at this node, so it cannot be bounded at the top and - we need not bother testing any further. */ + auto_vec switch_statements; + switch_statements.create (1); - if (node->right) - return false; + FOR_EACH_BB_FN (bb, fun) + { + gimple *stmt = last_stmt (bb); + gswitch *swtch; + if (stmt && (swtch = dyn_cast (stmt))) + { + if (!O0) + group_case_labels_stmt (swtch); + switch_statements.safe_push (swtch); + } + } - high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high, - build_int_cst (TREE_TYPE (node->high), 1)); + for (unsigned i = 0; i < switch_statements.length (); i++) + { + gimple *stmt = switch_statements[i]; + if (dump_file) + { + expanded_location loc = expand_location (gimple_location (stmt)); - /* If the addition above overflowed, we can't verify anything. - Otherwise, look for a parent that tests our value + 1. */ + fprintf (dump_file, "beginning to process the following " + "SWITCH statement (%s:%d) : ------- \n", + loc.file, loc.line); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + putc ('\n', dump_file); + } - if (!tree_int_cst_lt (node->high, high_plus_one)) - return false; + gswitch *swtch = dyn_cast (stmt); + if (swtch) + { + switch_decision_tree dt (swtch); + expanded |= dt.analyze_switch_statement (); + } + } - for (pnode = node->parent; pnode; pnode = pnode->parent) - if (tree_int_cst_equal (high_plus_one, pnode->low)) - return true; + if (expanded) + { + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + mark_virtual_operands_for_renaming (cfun); + } - return false; + return 0; } -/* Search the parent sections of the - case node tree to see if both tests for the upper and lower - bounds of NODE would be redundant. */ +} // anon namespace -static bool -node_is_bounded (case_node_ptr node, tree index_type) +gimple_opt_pass * +make_pass_lower_switch_O0 (gcc::context *ctxt) +{ + return new pass_lower_switch (ctxt); +} +gimple_opt_pass * +make_pass_lower_switch (gcc::context *ctxt) { - return (node_has_low_bound (node, index_type) - && node_has_high_bound (node, index_type)); + return new pass_lower_switch (ctxt); } + +