X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Ftree-switch-conversion.c;h=bf910dd62b538cba2984d031e061b9499470c602;hb=224efaf7e1e9240b64602ea81a255cb43e4dcb0c;hp=e64a3169249be4eecbeef3f02ef41dc3933c074e;hpb=5624e564d2239a74daa140e726b7b229d6e9a115;p=gcc.git diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index e64a3169249..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-2015 Free Software Foundation, Inc. + Copyright (C) 2006-2020 Free Software Foundation, Inc. This file is part of GCC. @@ -25,1405 +25,2322 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "line-map.h" -#include "params.h" -#include "flags.h" +#include "backend.h" +#include "insn-codes.h" +#include "rtl.h" #include "tree.h" +#include "gimple.h" +#include "cfghooks.h" +#include "tree-pass.h" +#include "ssa.h" +#include "optabs-tree.h" +#include "cgraph.h" +#include "gimple-pretty-print.h" +#include "fold-const.h" #include "varasm.h" #include "stor-layout.h" -#include "predict.h" -#include "vec.h" -#include "hashtab.h" -#include "hash-set.h" -#include "machmode.h" -#include "hard-reg-set.h" -#include "input.h" -#include "function.h" -#include "dominance.h" -#include "cfg.h" #include "cfganal.h" -#include "basic-block.h" -#include "tree-ssa-alias.h" -#include "internal-fn.h" -#include "gimple-expr.h" -#include "is-a.h" -#include "gimple.h" #include "gimplify.h" #include "gimple-iterator.h" #include "gimplify-me.h" -#include "gimple-ssa.h" -#include "hash-map.h" -#include "plugin-api.h" -#include "ipa-ref.h" -#include "cgraph.h" +#include "gimple-fold.h" #include "tree-cfg.h" -#include "tree-phinodes.h" -#include "stringpool.h" -#include "tree-ssanames.h" -#include "tree-pass.h" -#include "gimple-pretty-print.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" -/* Need to include expr.h and optabs.h for lshift_cheap_p. */ -#include "expr.h" -#include "insn-codes.h" -#include "optabs.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 - -/* 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. +using namespace tree_switch_conversion; - 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 = REG_BR_PROB_BASE - e_true->probability; - 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; -/* 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. */ + if (single_pred_p (e->dest) + && single_succ_p (e->dest) + && single_succ (e->dest) == m_final_bb) + continue; -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); -} - -/* Implement switch statements with bit tests + if (e == e_default && m_contiguous_range) + { + m_default_case_nonstandard = true; + continue; + } -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: + m_final_bb = NULL; + break; + } - if ((x==4) || (x==6) || (x==9) || (x==11)) + m_range_size + = int_const_binop (MINUS_EXPR, m_range_max, m_range_min); -as a single bit test: + /* 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++; + } - if ((1<succs) - 1; +} -This transformation is only applied if the number of case targets is small, -if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are -performed in "word_mode". +/* 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. */ -The following example shows the code the transformation generates: +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; + } - int bar(int x) - { - 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 (tree_to_uhwi (m_range_size) + > ((unsigned) m_count * param_switch_conversion_branch_ratio)) + { + m_reason = "the maximum range-branch ratio exceeded"; + 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; - } +/* Checks whether all but the final BB basic blocks are empty. */ -TODO: There are still some improvements to this transformation that could -be implemented: +bool +switch_conversion::check_all_empty_except_final () +{ + edge e, e_default = find_edge (m_switch_bb, m_default_bb); + edge_iterator ei; -* 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. + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) + { + if (e->dest == m_final_bb) + continue; -* 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 (!empty_block_p (e->dest)) + { + if (m_contiguous_range && e == e_default) + { + m_default_case_nonstandard = true; + continue; + } -This transformation was contributed by Roger Sayle, see this e-mail: - http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html -*/ + m_reason = "bad case - a non-final BB not empty"; + return false; + } + } -/* 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. */ + return true; +} -struct case_bit_test -{ - wide_int mask; - edge target_edge; - tree label; - int bits; -}; +/* 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. */ -/* 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) +bool +switch_conversion::check_final_bb () { - 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; + gphi_iterator gsi; - if (d2->target_edge->count != d1->target_edge->count) - return d2->target_edge->count - d1->target_edge->count; - if (d2->bits != d1->bits) - return d2->bits - d1->bits; + 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; - /* Stabilize the sort. */ - return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label); -} + if (virtual_operand_p (gimple_phi_result (phi))) + continue; -/* 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. + m_phi_count++; - INDEX_EXPR is the value being switched on. + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + basic_block bb = gimple_phi_arg_edge (phi, i)->src; - 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. + 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; - There *MUST* be MAX_CASE_BIT_TESTS or less unique case - node targets. */ + 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; + } + + 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; + } + } + } + } -static void -emit_case_bit_tests (gswitch *swtch, tree index_expr, - tree minval, tree range, tree maxval) + 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. */ + +void +switch_conversion::create_temp_arrays () { - struct case_bit_test test[MAX_CASE_BIT_TESTS]; - unsigned int i, j, k; - unsigned int count; + int i; - 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); + 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); +} - vec bbs_to_fix_dom = vNULL; +/* 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. */ - 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); +void +switch_conversion::gather_default_values (tree default_case) +{ + gphi_iterator gsi; + basic_block bb = label_to_block (cfun, CASE_LABEL (default_case)); + edge e; + int i = 0; - gimple_stmt_iterator gsi; - gassign *shift_stmt; + gcc_assert (CASE_LOW (default_case) == NULL_TREE + || m_default_case_nonstandard); - 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); + if (bb == m_final_bb) + e = find_edge (m_switch_bb, bb); + else + e = single_succ_edge (bb); + + 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; + } +} - memset (&test, 0, sizeof (test)); +/* 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) + if (bb == m_final_bb) + e = find_edge (m_switch_bb, bb); + else + e = single_succ_edge (bb); + gcc_assert (e); + + while (tree_int_cst_lt (pos, CASE_LOW (cs))) { - 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++; + int k; + for (k = 0; k < m_phi_count; k++) + { + constructor_elt elt; + + 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); + } + + pos = int_const_binop (PLUS_EXPR, pos, pos_one); } - else - test[k].bits++; + gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); - lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, - CASE_LOW (cs), minval)); - if (CASE_HIGH (cs) == NULL_TREE) - hi = lo; + j = 0; + if (CASE_HIGH (cs)) + high = CASE_HIGH (cs); else - hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, - CASE_HIGH (cs), minval)); + high = CASE_LOW (cs); + 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); + tree low = CASE_LOW (cs); + pos = CASE_LOW (cs); - for (j = lo; j <= hi; j++) - test[k].mask |= wi::lshift (wone, j); + do + { + constructor_elt elt; + + elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min); + elt.value = unshare_expr_without_location (val); + m_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++; + } } +} - qsort (test, count, sizeof (*test), case_bit_test_cmp); +/* 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. */ - /* 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), 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), 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; - } - } - - /* 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); +bool +switch_conversion::contains_linear_function_p (vec *vec, + wide_int *coeff_a, + wide_int *coeff_b) +{ + unsigned int i; + constructor_elt *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); - } + gcc_assert (vec->length () >= 2); - /* Now build the test-and-branch code. */ + /* Let's try to find any linear function a * x + y that can apply to + given values. 'a' can be calculated as follows: - gsi = gsi_last_bb (switch_bb); + a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices) + a = y2 - y1 - /* 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); + and - /* 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; + b = y2 - a * x2 - 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 (); - } + */ - /* 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); + tree elt0 = (*vec)[0].value; + tree elt1 = (*vec)[1].value; - /* 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); - } + if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST) + return false; - /* We should have removed all edges now. */ - gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); + 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); - /* If nothing matched, go to the default label. */ - make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU); + /* 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; - /* The GIMPLE_SWITCH is now redundant. */ - gsi_remove (&gsi, true); + wide_int value = wi::to_wide (elt->value); + if (a * range_min + b != value) + 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 (); + ++range_min; } -} - -/* - Switch initialization conversion -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: + *coeff_a = a; + *coeff_b = b; - int a,b; + return true; +} - 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 +/* 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. */ +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; -is changed into: + /* 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. */ - 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}; + type = TYPE_MAIN_VARIANT (type); - 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 + if (!INTEGRAL_TYPE_P (type)) + return 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. + 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; -This transformation was contributed by Martin Jambor, see this e-mail: - http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */ + if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32)) + return type; -/* The main structure of the pass. */ -struct switch_conv_info -{ - /* The expression used to decide the switch branch. */ - tree index_expr; + FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt) + { + wide_int cst; - /* The following integer constants store the minimum and maximum value - covered by the case labels. */ - tree range_min; - tree range_max; + if (TREE_CODE (elt->value) != INTEGER_CST) + 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; + cst = wi::to_wide (elt->value); + while (1) + { + unsigned int prec = GET_MODE_BITSIZE (mode); + if (prec > HOST_BITS_PER_WIDE_INT) + return type; - /* Basic block that contains the actual GIMPLE_SWITCH. */ - basic_block switch_bb; + 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; + } - /* Basic block that is the target of the default case. */ - basic_block default_bb; + if (sign == 1) + sign = 0; - /* The single successor block of all branches out of the GIMPLE_SWITCH, - if such a block exists. Otherwise NULL. */ - basic_block final_bb; + if (!GET_MODE_WIDER_MODE (mode).exists (&mode) + || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode)) + return type; + } + } - /* The probability of the default edge in the replaced switch. */ - int default_prob; + 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; - /* The count of the default edge in the replaced switch. */ - gcov_type default_count; + return smaller_type; +} - /* Combined count of all other (non-default) edges in the replaced switch. */ - gcov_type other_count; +/* 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. */ - /* Number of phi nodes in the final bb (that we'll be replacing). */ - int phi_count; +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 default values, in the same order as phi nodes. */ - tree *default_values; + gcc_assert (m_default_values[num]); - /* Constructors of new static arrays. */ - vec **constructors; + 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; - /* Array of ssa names that are initialized with a value from a new static - array. */ - tree *target_inbound_names; + 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; - /* Array of ssa names that are initialized with the default value if the - switch expression is out of range. */ - tree *target_outbound_names; + 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; - /* The first load statement that loads a temporary from a new static array. - */ - gimple arr_ref_first; + decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type); + TREE_STATIC (decl) = 1; + DECL_INITIAL (decl) = ctor; - /* The last load statement that loads a temporary from a new static array. */ - gimple arr_ref_last; + 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); - /* String reason why the case wasn't a good candidate that is written to the - dump file, if there is one. */ - const char *reason; + 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; - edge_iterator ei; - - 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; - - /* 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 default case as guess - or its destination in case it is a forwarder block. */ - if (! single_pred_p (e_default->dest)) - info->final_bb = e_default->dest; - else if (single_succ_p (e_default->dest) - && ! single_pred_p (single_succ (e_default->dest))) - info->final_bb = single_succ (e_default->dest); - /* Require that all switch destinations are either that common - FINAL_BB or a forwarder to it. */ - 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; - - info->final_bb = NULL; - break; - } + 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->range_size = - int_const_binop (MINUS_EXPR, info->range_max, info->range_min); + 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, 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); - /* 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++) + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + update_stmt (stmt); + m_arr_ref_first = stmt; + + for (gpi = gsi_start_phis (m_final_bb), i = 0; + !gsi_end_p (gpi); gsi_next (&gpi)) { - tree elt = gimple_switch_label (swtch, i); - count++; - if (CASE_HIGH (elt) - && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt))) - count++; + gphi *phi = gpi.phi (); + if (!virtual_operand_p (gimple_phi_result (phi))) + build_one_array (i++, arr_index_type, phi, tidx); + else + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) + { + if (e->dest == m_final_bb) + break; + if (!m_default_case_nonstandard + || e->dest != m_default_bb) + { + e = single_succ_edge (e->dest); + break; + } + } + gcc_assert (e && e->dest == m_final_bb); + m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e); + } } - 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. */ +/* Generates and appropriately inserts loads of default values at the position + given by GSI. Returns the last inserted statement. */ -static bool -check_range (struct switch_conv_info *info) +gassign * +switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi) { - 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; - } + int i; + gassign *assign = NULL; - if (tree_to_uhwi (info->range_size) - > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO)) + for (i = 0; i < m_phi_count; i++) { - info->reason = "the maximum range-branch ratio exceeded"; - return false; + 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); } - - return true; + return assign; } -/* Checks whether all but the FINAL_BB basic blocks are empty. */ +/* 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). */ -static bool -check_all_empty_except_final (struct switch_conv_info *info) +void +switch_conversion::prune_bbs (basic_block bbd, basic_block final, + basic_block default_bb) { - edge e; edge_iterator ei; + edge e; - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) + for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); ) { - if (e->dest == info->final_bb) - continue; + basic_block bb; + bb = e->dest; + remove_edge (e); + if (bb != final && bb != default_bb) + delete_basic_block (bb); + } + delete_basic_block (bbd); +} - if (!empty_block_p (e->dest)) +/* Add values to phi nodes in final_bb for the two new edges. E1F is the edge + from the basic block loading values from an array and E2F from the basic + block loading default values. BBF is the last switch basic block (see the + bbf description in the comment below). */ + +void +switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) +{ + gphi_iterator gsi; + int i; + + for (gsi = gsi_start_phis (bbf), i = 0; + !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + tree inbound, outbound; + if (virtual_operand_p (gimple_phi_result (phi))) + inbound = outbound = m_target_vop; + else { - info->reason = "bad case - a non-final BB not empty"; - return false; + inbound = m_target_inbound_names[i]; + outbound = m_target_outbound_names[i++]; } + add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION); + if (!m_default_case_nonstandard) + add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION); } - - 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. */ +/* 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. */ -static bool -check_final_bb (struct switch_conv_info *info) +void +switch_conversion::gen_inbound_check () { - gphi_iterator gsi; + tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); + tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); + tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION); + glabel *label1, *label2, *label3; + tree utype, tidx; + tree bound; - 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; + gcond *cond_stmt; - info->phi_count++; + gassign *last_assign = NULL; + gimple_stmt_iterator gsi; + basic_block bb0, bb1, bb2, bbf, bbd; + edge e01 = NULL, e02, e21, e1d, e1f, e2f; + location_t loc = gimple_location (m_switch); - for (i = 0; i < gimple_phi_num_args (phi); i++) - { - basic_block bb = gimple_phi_arg_edge (phi, i)->src; + gcc_assert (m_default_values); - if (bb == info->switch_bb - || (single_pred_p (bb) && single_pred (bb) == info->switch_bb)) - { - tree reloc, val; + bb0 = gimple_bb (m_switch); - val = gimple_phi_arg_def (phi, i); - if (!is_gimple_ip_invariant (val)) - { - info->reason = "non-invariant value from a case"; - return false; /* Non-invariant argument. */ - } - reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); - if ((flag_pic && reloc != null_pointer_node) - || (!flag_pic && reloc == NULL_TREE)) - { - if (reloc) - info->reason - = "value from a case would need runtime relocations"; - else - info->reason - = "value from a case is not a valid initializer"; - return false; - } - } - } + tidx = gimple_assign_lhs (m_arr_ref_first); + utype = TREE_TYPE (tidx); + + /* (end of) block 0 */ + gsi = gsi_for_stmt (m_arr_ref_first); + gsi_next (&gsi); + + 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 (!m_default_case_nonstandard) + { + label2 = gimple_build_label (label_decl2); + gsi_insert_before (&gsi, label2, GSI_SAME_STMT); + last_assign = gen_def_assigns (&gsi); } - return true; -} + /* block 1 */ + label1 = gimple_build_label (label_decl1); + gsi_insert_before (&gsi, label1, GSI_SAME_STMT); -/* 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. */ + /* block F */ + gsi = gsi_start_bb (m_final_bb); + label3 = gimple_build_label (label_decl3); + gsi_insert_before (&gsi, label3, GSI_SAME_STMT); -static void -create_temp_arrays (struct switch_conv_info *info) -{ - int i; + /* cfg fix */ + e02 = split_block (bb0, cond_stmt); + bb2 = e02->dest; - 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); -} + if (m_default_case_nonstandard) + { + bb1 = bb2; + bb2 = m_default_bb; + e01 = e02; + e01->flags = EDGE_TRUE_VALUE; + e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE); + edge e_default = find_edge (bb1, bb2); + for (gphi_iterator gsi = gsi_start_phis (bb2); + !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default); + add_phi_arg (phi, arg, e02, + gimple_phi_arg_location_from_edge (phi, e_default)); + } + /* Partially fix the dominator tree, if it is available. */ + if (dom_info_available_p (CDI_DOMINATORS)) + redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0); + } + else + { + e21 = split_block (bb2, last_assign); + bb1 = e21->dest; + remove_edge (e21); + } -/* 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. */ + e1d = split_block (bb1, m_arr_ref_last); + bbd = e1d->dest; + remove_edge (e1d); -static void -free_temp_arrays (struct switch_conv_info *info) -{ - XDELETEVEC (info->constructors); - XDELETEVEC (info->default_values); -} + /* 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 (); -/* Populate the array of default values in the order of phi nodes. - DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */ + /* 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; -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; + bbf = m_final_bb; - gcc_assert (CASE_LOW (default_case) == NULL_TREE); + e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); + e1f->probability = profile_probability::always (); - if (bb == info->final_bb) - e = find_edge (info->switch_bb, bb); + if (m_default_case_nonstandard) + e2f = NULL; else - e = single_succ_edge (bb); + { + 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); - for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + /* Fix the dominator tree, if it is available. */ + if (dom_info_available_p (CDI_DOMINATORS)) { - gphi *phi = gsi.phi (); - tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); - gcc_assert (val); - info->default_values[i++] = val; + 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 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. */ +/* 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. */ -static void -build_constructors (gswitch *swtch, struct switch_conv_info *info) +void +switch_conversion::expand (gswitch *swtch) { - unsigned i, branch_num = gimple_switch_num_labels (swtch); - tree pos = info->range_min; + /* 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); - for (i = 1; i < branch_num; i++) + /* 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) { - 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; + m_reason = "switch is a degenerate case"; + return; + } - if (bb == info->final_bb) - e = find_edge (info->switch_bb, bb); - else - e = single_succ_edge (bb); - gcc_assert (e); + collect (swtch); - while (tree_int_cst_lt (pos, CASE_LOW (cs))) - { - int k; - for (k = 0; k < info->phi_count; k++) - { - constructor_elt elt; + /* No error markers should reach here (they should be filtered out + during gimplification). */ + gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node); - 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); - } + /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ + gcc_checking_assert (!TREE_CONSTANT (m_index_expr)); - pos = int_const_binop (PLUS_EXPR, pos, - build_int_cst (TREE_TYPE (pos), 1)); - } - gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); + /* 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; + } - 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 (); - tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); - tree low = CASE_LOW (cs); - pos = CASE_LOW (cs); + if (m_uniq <= 2) + { + /* This will be expanded as a decision tree . */ + m_reason = "expanding as jumps is preferable"; + return; + } - do - { - constructor_elt elt; + /* 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; + } - elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); - elt.value = unshare_expr_without_location (val); - info->constructors[j]->quick_push (elt); + /* Check the case label values are within reasonable range: */ + if (!check_range ()) + { + gcc_assert (m_reason); + return; + } - pos = int_const_binop (PLUS_EXPR, pos, - build_int_cst (TREE_TYPE (pos), 1)); - } while (!tree_int_cst_lt (high, pos) - && tree_int_cst_lt (low, pos)); - j++; - } + /* 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; } -/* 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. */ +/* Destructor. */ -static tree -constructor_contains_same_values_p (vec *vec) +switch_conversion::~switch_conversion () { - unsigned int i; - tree prev = NULL_TREE; - constructor_elt *elt; + XDELETEVEC (m_constructors); + XDELETEVEC (m_default_values); +} - FOR_EACH_VEC_SAFE_ELT (vec, i, elt) +/* 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++) { - if (!prev) - prev = elt->value; - else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST)) - return NULL_TREE; + m_cases.quick_push (static_cast (clusters[i])); + m_prob += clusters[i]->m_prob; } - return prev; + m_subtree_prob = m_prob; } -/* Return type which should be used for array elements, either TYPE, - or for integral type some smaller integral type that can still hold - all the constants. */ +/* Destructor. */ -static tree -array_value_type (gswitch *swtch, tree type, int num, - struct switch_conv_info *info) +group_cluster::~group_cluster () { - unsigned int i, len = vec_safe_length (info->constructors[num]); - constructor_elt *elt; - machine_mode mode; - int sign = 0; - tree smaller_type; + for (unsigned i = 0; i < m_cases.length (); i++) + delete m_cases[i]; - if (!INTEGRAL_TYPE_P (type)) - return type; + m_cases.release (); +} - mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type))); - if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode)) - return type; +/* Dump content of a cluster. */ - if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32)) - return type; +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 ()); - FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) + unsigned comparison_count = 0; + for (unsigned i = 0; i < m_cases.length (); i++) { - wide_int cst; + simple_cluster *sc = static_cast (m_cases[i]); + comparison_count += sc->m_range_p ? 2 : 1; + } - if (TREE_CODE (elt->value) != INTEGER_CST) - return type; + unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ()); + fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT"); - cst = elt->value; - while (1) - { - unsigned int prec = GET_MODE_BITSIZE (mode); - if (prec > HOST_BITS_PER_WIDE_INT) - return type; + 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); - 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; - } + fprintf (f, ":"); + PRINT_CASE (f, get_low ()); + fprintf (f, "-"); + PRINT_CASE (f, get_high ()); + fprintf (f, " "); +} - if (sign == 1) - sign = 0; +/* Emit GIMPLE code to handle the cluster. */ - mode = GET_MODE_WIDER_MODE (mode); - if (mode == VOIDmode - || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type))) - return type; - } +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); } - 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 (type)) - <= GET_MODE_SIZE (TYPE_MODE (smaller_type))) - return type; + 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); - return smaller_type; + /* 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); } -/* 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. */ +/* Find jump tables of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ -static void -build_one_array (gswitch *swtch, int num, tree arr_index_type, - gphi *phi, tree tidx, struct switch_conv_info *info) +vec +jump_table_cluster::find_jump_tables (vec &clusters) { - tree name, cst; - gimple load; - gimple_stmt_iterator gsi = gsi_for_stmt (swtch); - location_t loc = gimple_location (swtch); + if (!is_enabled ()) + return clusters.copy (); - gcc_assert (info->default_values[num]); + unsigned l = clusters.length (); + auto_vec min; + min.reserve (l + 1); - name = copy_ssa_name (PHI_RESULT (phi)); - info->target_inbound_names[num] = name; + min.quick_push (min_cluster_item (0, 0, 0)); - cst = constructor_contains_same_values_p (info->constructors[num]); - if (cst) - load = gimple_build_assign (name, cst); - else + for (unsigned i = 1; i <= l; i++) { - tree array_type, ctor, decl, value_type, fetch, default_type; + /* Set minimal # of clusters with i-th item to infinite. */ + min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); - 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) + for (unsigned j = 0; j < i; j++) { - unsigned int i; - constructor_elt *elt; + 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); + } - FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) - elt->value = fold_convert (value_type, elt->value); + 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; +} + +/* Return true if cluster starting at START and ending at END (inclusive) + is profitable transformation. */ + +bool +jump_table_cluster::is_beneficial (const vec &, + unsigned start, unsigned end) +{ + /* Single case bail out. */ + if (start == end) + return false; + + return end - start + 1 >= case_values_threshold (); +} + +/* Find bit tests of given CLUSTERS, where all members of the vector + are of type simple_cluster. New clusters are returned. */ + +vec +bit_test_cluster::find_bit_tests (vec &clusters) +{ + 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++) + { + 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); } - 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; + gcc_checking_assert (min[i].m_count != INT_MAX); + } - DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); - DECL_ARTIFICIAL (decl) = 1; - TREE_CONSTANT (decl) = 1; - TREE_READONLY (decl) = 1; - varpool_node::finalize_decl (decl); + /* No result. */ + if (min[l].m_count == l) + return clusters.copy (); - fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, - NULL_TREE); - if (default_type != value_type) + vec output; + output.create (4); + + /* Find and build the clusters. */ + for (unsigned end = l;;) + { + int start = min[end].m_start; + + if (is_beneficial (clusters, start, end - 1)) { - fetch = fold_convert (default_type, fetch); - fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE, - true, GSI_SAME_STMT); + bool entire = start == 0 && end == clusters.length (); + output.safe_push (new bit_test_cluster (clusters, start, end - 1, + entire)); } - load = gimple_build_assign (name, fetch); + else + for (int i = end - 1; i >= start; i--) + output.safe_push (clusters[i]); + + end = start; + + if (start <= 0) + break; } - gsi_insert_before (&gsi, load, GSI_SAME_STMT); - update_stmt (load); - info->arr_ref_last = load; + output.reverse (); + return output; } -/* Builds and initializes static arrays initialized with values gathered from - the SWTCH switch statement. Also creates statements that load values from - them. */ +/* Return true when RANGE of case values with UNIQ labels + can build a bit test. */ -static void -build_arrays (gswitch *swtch, struct switch_conv_info *info) +bool +bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range, + unsigned int uniq) { - tree arr_index_type; - tree tidx, sub, utype; - gimple stmt; + /* Check overflow. */ + if (range == 0) + return 0; + + if (range >= GET_MODE_BITSIZE (word_mode)) + return false; + + return uniq <= 3; +} + +/* Return true when cluster starting at START and ending at END (inclusive) + can build a bit test. */ + +bool +bit_test_cluster::can_be_handled (const vec &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; + + unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), + clusters[end]->get_high ()); + auto_bitmap dest_bbs; + + for (unsigned i = start; i <= end; i++) + { + simple_cluster *sc = static_cast (clusters[i]); + bitmap_set_bit (dest_bbs, sc->m_case_bb->index); + } + + return can_be_handled (range, bitmap_count_bits (dest_bbs)); +} + +/* Return true when COUNT of cases of UNIQ labels is beneficial for bit test + transformation. */ + +bool +bit_test_cluster::is_beneficial (unsigned count, unsigned uniq) +{ + 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++) + { + simple_cluster *sc = static_cast (clusters[i]); + bitmap_set_bit (dest_bbs, sc->m_case_bb->index); + } + + unsigned uniq = bitmap_count_bits (dest_bbs); + unsigned count = end - start + 1; + return is_beneficial (count, uniq); +} + +/* Comparison function for qsort to order bit tests by decreasing + probability of execution. */ + +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; + + if (d2->bits != d1->bits) + return d2->bits - d1->bits; + + /* Stabilize the sort. */ + return (LABEL_DECL_UID (CASE_LABEL (d2->label)) + - LABEL_DECL_UID (CASE_LABEL (d1->label))); +} + +/* 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. + + INDEX_EXPR is the value being switched on. + + 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. + + 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) +{ + case_bit_test test[m_max_case_bit_tests] = { {} }; + unsigned int i, j, k; + unsigned int count; + + tree unsigned_index_type = range_check_type (index_type); + gimple_stmt_iterator gsi; - gphi_iterator gpi; - int i; - location_t loc = gimple_location (swtch); + gassign *shift_stmt; - gsi = gsi_for_stmt (swtch); + 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); - /* 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); + 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); + + /* 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; + + 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++; + } + + test[k].bits += n->get_range (n->get_low (), n->get_high ()); + + 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); + } + + /* We should have removed all edges now. */ + gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); + + /* If nothing matched, go to the default label. */ + edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU); + e->probability = profile_probability::always (); +} + +/* 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. */ + +basic_block +bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, + tree cond, basic_block case_bb, + profile_probability prob) +{ + tree tmp; + gcond *cond_stmt; + edge e_false; + basic_block new_bb, split_bb = gsi_bb (*gsip); + + edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE); + e_true->probability = prob; + gcc_assert (e_true->src == split_bb); + + 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); + + e_false = split_block (split_bb, cond_stmt); + new_bb = e_false->dest; + redirect_edge_pred (e_true, split_bb); + + 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 + switch statement. Record this information in the aux field of the edge. */ + +void +switch_decision_tree::compute_cases_per_edge () +{ + reset_out_edges_aux (m_switch); + int ncases = gimple_switch_num_labels (m_switch); + for (int i = ncases - 1; i >= 1; --i) + { + edge case_edge = gimple_switch_edge (cfun, m_switch, i); + case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1); + } +} + +/* Analyze switch statement and return true when the statement is expanded + as decision tree. */ + +bool +switch_decision_tree::analyze_switch_statement () +{ + unsigned l = gimple_switch_num_labels (m_switch); + basic_block bb = gimple_bb (m_switch); + auto_vec clusters; + clusters.create (l - 1); + + basic_block default_bb = gimple_switch_default_bb (cfun, m_switch); + m_case_bbs.reserve (l); + m_case_bbs.quick_push (default_bb); + + compute_cases_per_edge (); + + for (unsigned i = 1; i < l; i++) + { + 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); + + 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); + } + + reset_out_edges_aux (m_switch); + + /* Find jump table clusters. */ + vec output = jump_table_cluster::find_jump_tables (clusters); + + /* Find bit test clusters. */ + vec output2; + auto_vec tmp; + output2.create (1); + tmp.create (1); + + for (unsigned i = 0; i < output.length (); i++) + { + cluster *c = output[i]; + if (c->get_type () != SIMPLE_CASE) + { + if (!tmp.is_empty ()) + { + vec n = bit_test_cluster::find_bit_tests (tmp); + output2.safe_splice (n); + n.release (); + tmp.truncate (0); + } + output2.safe_push (c); + } + else + tmp.safe_push (c); + } + + /* 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 (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"); + } + + output.release (); - arr_index_type = build_index_type (info->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)); - sub = force_gimple_operand_gsi (&gsi, sub, - false, NULL, true, GSI_SAME_STMT); - stmt = gimple_build_assign (tidx, sub); + bool expanded = try_switch_expansion (output2); - gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); - update_stmt (stmt); - info->arr_ref_first = stmt; + for (unsigned i = 0; i < output2.length (); i++) + delete output2[i]; + + output2.release (); - for (gpi = gsi_start_phis (info->final_bb), i = 0; - !gsi_end_p (gpi); gsi_next (&gpi), i++) - build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, info); + return expanded; } -/* Generates and appropriately inserts loads of default values at the position - given by BSI. Returns the last inserted statement. */ +/* Attempt to expand CLUSTERS as a decision tree. Return true when + expanded. */ -static gassign * -gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info) +bool +switch_decision_tree::try_switch_expansion (vec &clusters) { - int i; - gassign *assign = NULL; + tree index_expr = gimple_switch_index (m_switch); + tree index_type = TREE_TYPE (index_expr); + basic_block bb = gimple_bb (m_switch); - for (i = 0; i < info->phi_count; i++) + if (gimple_switch_num_labels (m_switch) == 1 + || range_check_type (index_type) == NULL_TREE) + return false; + + /* Find the default case target label. */ + edge default_edge = gimple_switch_default_edge (cfun, m_switch); + m_default_bb = default_edge->dest; + + /* 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. */ + + for (int i = clusters.length () - 1; i >= 0; 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]); - gsi_insert_before (gsi, assign, GSI_SAME_STMT); - update_stmt (assign); + 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]; } - return assign; -} -/* 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). */ + record_phi_operand_mapping (); -static void -prune_bbs (basic_block bbd, basic_block final) -{ - edge_iterator ei; + /* Split basic block that contains the gswitch statement. */ + gimple_stmt_iterator gsi = gsi_last_bb (bb); edge e; + if (gsi_end_p (gsi)) + e = split_block_after_labels (bb); + else + { + gsi_prev (&gsi); + e = split_block (bb, gsi_stmt (gsi)); + } + bb = split_edge (e); - for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); ) + /* 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; + } + + /* Do not do an extra work for a single cluster. */ + if (clusters.length () == 1 + && clusters[0]->get_type () != SIMPLE_CASE) { - basic_block bb; - bb = e->dest; - remove_edge (e); - if (bb != final) - delete_basic_block (bb); + 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); } - delete_basic_block (bbd); + 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); + } + + fix_phi_operands_for_edges (); + + return true; } -/* Add values to phi nodes in final_bb for the two new edges. E1F is the edge - from the basic block loading values from an array and E2F from the basic - block loading default values. BBF is the last switch basic block (see the - bbf description in the comment below). */ +/* 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 < m_case_bbs.length (); 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 (); + + for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) + { + basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src; + if (phi_src_bb == switch_bb) + { + tree def = gimple_phi_arg_def (phi, i); + tree result = gimple_phi_result (phi); + m_phi_mapping.put (result, def); + break; + } + } + } + } +} -static void -fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, - struct switch_conv_info *info) +/* Append new operands to PHI statements that were introduced due to + addition of new edges to case labels. */ + +void +switch_decision_tree::fix_phi_operands_for_edges () { gphi_iterator gsi; - int i; - for (gsi = gsi_start_phis (bbf), i = 0; - !gsi_end_p (gsi); gsi_next (&gsi), i++) + for (unsigned i = 0; i < m_case_bbs.length (); i++) { - gphi *phi = gsi.phi (); - add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION); - add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION); + 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); + } + } + } } } -/* 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. +/* Generate a decision tree, switching on INDEX_EXPR and jumping to + one of the labels in CASE_LIST or to the DEFAULT_LABEL. - bb1 is the bb to be used when the range check went ok. It is derived from - the switch BB + We generate a binary decision tree to select the appropriate target + code. */ - 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. +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); - bbF is a fall through for both bb1 and bb2 and contains exactly what - originally followed the switch statement. + if (dump_file) + dump_function_to_file (current_function_decl, dump_file, dump_flags); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + 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); + } - bbD contains the switch statement (in the end). It is unreachable but we - still need to strip off its edges. -*/ + bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type, + gimple_location (m_switch)); -static void -gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) -{ - tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); - tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); - tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION); - glabel *label1, *label2, *label3; - tree utype, tidx; - tree bound; + if (bb) + emit_jump (bb, m_default_bb); - gcond *cond_stmt; + /* 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); - gassign *last_assign; - gimple_stmt_iterator gsi; - basic_block bb0, bb1, bb2, bbf, bbd; - edge e01, e02, e21, e1d, e1f, e2f; - location_t loc = gimple_location (swtch); + delete_basic_block (bb); +} - gcc_assert (info->default_values); +/* 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. - bb0 = gimple_bb (swtch); + 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. */ - tidx = gimple_assign_lhs (info->arr_ref_first); - utype = TREE_TYPE (tidx); +void +switch_decision_tree::balance_case_nodes (case_tree_node **head, + case_tree_node *parent) +{ + case_tree_node *np; - /* (end of) block 0 */ - gsi = gsi_for_stmt (info->arr_ref_first); - gsi_next (&gsi); + np = *head; + if (np) + { + int i = 0; + int ranges = 0; + case_tree_node **npp; + case_tree_node *left; + profile_probability prob = profile_probability::never (); - bound = fold_convert_loc (loc, utype, info->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); + /* Count the number of entries on branch. Also count the ranges. */ - /* block 2 */ - label2 = gimple_build_label (label_decl2); - gsi_insert_before (&gsi, label2, GSI_SAME_STMT); - last_assign = gen_def_assigns (&gsi, info); + while (np) + { + if (!tree_int_cst_equal (np->m_c->get_low (), np->m_c->get_high ())) + ranges++; - /* block 1 */ - label1 = gimple_build_label (label_decl1); - gsi_insert_before (&gsi, label1, GSI_SAME_STMT); + i++; + prob += np->m_c->m_prob; + np = np->m_right; + } - /* block F */ - gsi = gsi_start_bb (info->final_bb); - label3 = gimple_build_label (label_decl3); - gsi_insert_before (&gsi, label3, GSI_SAME_STMT); + 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); + + /* 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; + } - /* cfg fix */ - e02 = split_block (bb0, cond_stmt); - bb2 = e02->dest; + np = *npp; + *npp = 0; + *head = np; + np->m_parent = parent; + np->m_left = left == np ? NULL : left; + + /* Optimize each of the two split parts. */ + balance_case_nodes (&np->m_left, np); + balance_case_nodes (&np->m_right, np); + np->m_c->m_subtree_prob = np->m_c->m_prob; + 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 + { + /* 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) + { + np->m_right->m_parent = np; + (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob; + } + } + } +} - e21 = split_block (bb2, last_assign); - bb1 = e21->dest; - remove_edge (e21); +/* Dump ROOT, a list or tree of case nodes, to file. */ - e1d = split_block (bb1, info->arr_ref_last); - bbd = e1d->dest; - remove_edge (e1d); +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++; - /* flags and profiles of the edge for in-range values */ - e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); - e01->probability = REG_BR_PROB_BASE - info->default_prob; - e01->count = info->other_count; + dump_case_nodes (f, root->m_left, indent_step, indent_level); - /* 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; + 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); - bbf = info->final_bb; + dump_case_nodes (f, root->m_right, indent_step, indent_level); +} - e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); - e1f->probability = REG_BR_PROB_BASE; - e1f->count = info->other_count; - e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); - e2f->probability = REG_BR_PROB_BASE; - e2f->count = info->default_count; +/* Add an unconditional jump to CASE_BB that happens in basic block BB. */ - /* frequencies of the new BBs */ - bb1->frequency = EDGE_FREQUENCY (e01); - bb2->frequency = EDGE_FREQUENCY (e02); - bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); +void +switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb) +{ + edge e = single_succ_edge (bb); + redirect_edge_succ (e, case_bb); +} - /* Tidy blocks that have become unreachable. */ - prune_bbs (bbd, info->final_bb); +/* 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) +{ + // TODO: it's once called with lhs != index. + op1 = fold_convert (TREE_TYPE (op0), op1); - /* Fixup the PHI nodes in bbF. */ - fix_phi_nodes (e1f, e2f, bbf, info); + gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE); + gimple_set_location (cond, loc); + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gsi_insert_after (&gsi, cond, GSI_NEW_STMT); - /* Fix the dominator tree, if it is available. */ - if (dom_info_available_p (CDI_DOMINATORS)) - { - vec bbs_to_fix_dom; + gcc_assert (single_succ_p (bb)); - set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); - 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); + /* Make a new basic block where false branch will take place. */ + edge false_edge = split_block (bb, cond); + false_edge->flags = EDGE_FALSE_VALUE; + false_edge->probability = prob.invert (); - bbs_to_fix_dom.create (4); - bbs_to_fix_dom.quick_push (bb0); - bbs_to_fix_dom.quick_push (bb1); - bbs_to_fix_dom.quick_push (bb2); - bbs_to_fix_dom.quick_push (bbf); + edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); + true_edge->probability = prob; - iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); - bbs_to_fix_dom.release (); - } + return false_edge->dest; } -/* 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. */ +/* 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 const char * -process_switch (gswitch *swtch) +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) { - struct switch_conv_info info; + op1 = fold_convert (TREE_TYPE (op0), op1); - /* 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); + gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE); + gimple_set_location (cond, loc); + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gsi_insert_before (&gsi, cond, GSI_SAME_STMT); - /* 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"; + gcc_assert (single_succ_p (bb)); - collect_switch_conv_info (swtch, &info); + /* Make a new basic block where false branch will take place. */ + edge false_edge = split_block (bb, cond); + false_edge->flags = EDGE_FALSE_VALUE; + false_edge->probability = prob.invert (); - /* No error markers should reach here (they should be filtered out - during gimplification). */ - gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node); + edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); + true_edge->probability = prob; - /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ - gcc_checking_assert (! TREE_CONSTANT (info.index_expr)); + return false_edge->dest; +} + +/* Emit step-by-step code to select a case for the value of INDEX. + The thus generated decision tree follows the form of the + case-node binary tree NODE, whose nodes represent test conditions. + 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) +{ + profile_probability p; - if (info.uniq <= MAX_CASE_BIT_TESTS) + /* If node is null, we are done. */ + if (node == NULL) + return bb; + + /* Single value case. */ + if (node->m_c->is_single_value_p ()) { - if (expand_switch_using_bit_tests_p (info.range_size, - info.uniq, info.count, - optimize_bb_for_speed_p - (gimple_bb (swtch)))) + /* Node is single valued. First see if the index expression matches + this node and then check our children, if any. */ + p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); + bb = do_jump_if_equal (bb, index, node->m_c->get_low (), + node->m_c->m_case_bb, p, loc); + /* Since this case is taken at this point, reduce its weight from + subtree_weight. */ + node->m_c->m_subtree_prob -= p; + + if (node->m_left != NULL && node->m_right != NULL) { - 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; + /* 1) the node has both children + + If both children are single-valued cases with no + children, finish up all the work. This way, we can save + one ordered comparison. */ + + if (!node->m_left->has_child () + && node->m_left->m_c->is_single_value_p () + && !node->m_right->has_child () + && node->m_right->m_c->is_single_value_p ()) + { + p = (node->m_right->m_c->m_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), + node->m_right->m_c->m_case_bb, p, loc); + + p = (node->m_left->m_c->m_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (), + node->m_left->m_c->m_case_bb, p, loc); + } + else + { + /* Branch to a label where we will handle it later. */ + basic_block test_bb = split_edge (single_succ_edge (bb)); + redirect_edge_succ (single_pred_edge (test_bb), + single_succ_edge (bb)->dest); + + p = ((node->m_right->m_c->m_subtree_prob + + default_prob.apply_scale (1, 2)) + / (node->m_c->m_subtree_prob + default_prob)); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), + GT_EXPR, test_bb, p, loc); + default_prob = default_prob.apply_scale (1, 2); + + /* Handle the left-hand subtree. */ + bb = emit_case_nodes (bb, index, node->m_left, + default_prob, index_type, loc); + + /* If the left-hand subtree fell through, + don't let it fall into the right-hand subtree. */ + if (bb && m_default_bb) + emit_jump (bb, m_default_bb); + + bb = emit_case_nodes (test_bb, index, node->m_right, + default_prob, index_type, loc); + } } + else if (node->m_left == NULL && node->m_right != NULL) + { + /* 2) the node has only right child. */ - if (info.uniq <= 2) - /* This will be expanded as a decision tree in stmt.c:expand_case. */ - return " expanding as jumps is preferable"; - } + /* Here we have a right child but no left so we issue a conditional + branch to default and process the right child. - /* 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"; + Omit the conditional branch to default if the right child + does not have any children and is single valued; it would + cost too much space to save so little time. */ - /* Check the case label values are within reasonable range: */ - if (!check_range (&info)) - { - gcc_assert (info.reason); - return info.reason; - } + if (node->m_right->has_child () + || !node->m_right->m_c->is_single_value_p ()) + { + p = (default_prob.apply_scale (1, 2) + / (node->m_c->m_subtree_prob + default_prob)); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), + LT_EXPR, m_default_bb, p, loc); + default_prob = default_prob.apply_scale (1, 2); + + bb = emit_case_nodes (bb, index, node->m_right, default_prob, + index_type, loc); + } + else + { + /* We cannot process node->right normally + since we haven't ruled out the numbers less than + this node's value. So handle node->right explicitly. */ + p = (node->m_right->m_c->m_subtree_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), + node->m_right->m_c->m_case_bb, p, loc); + } + } + else if (node->m_left != NULL && node->m_right == NULL) + { + /* 3) just one subtree, on the left. Similar case as previous. */ - /* 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 (node->m_left->has_child () + || !node->m_left->m_c->is_single_value_p ()) + { + p = (default_prob.apply_scale (1, 2) + / (node->m_c->m_subtree_prob + default_prob)); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), + GT_EXPR, m_default_bb, p, loc); + default_prob = default_prob.apply_scale (1, 2); + + bb = emit_case_nodes (bb, index, node->m_left, default_prob, + index_type, loc); + } + else + { + /* We cannot process node->left normally + since we haven't ruled out the numbers less than + this node's value. So handle node->left explicitly. */ + p = (node->m_left->m_c->m_subtree_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (), + node->m_left->m_c->m_case_bb, p, loc); + } + } } - if (!check_final_bb (&info)) + else { - gcc_assert (info.reason); - return info.reason; + /* Node is a range. These cases are very similar to those for a single + value, except that we do not start by testing whether this node + is the one to branch to. */ + if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE) + { + /* Branch to a label where we will handle it later. */ + basic_block test_bb = split_edge (single_succ_edge (bb)); + redirect_edge_succ (single_pred_edge (test_bb), + single_succ_edge (bb)->dest); + + + profile_probability right_prob = profile_probability::never (); + if (node->m_right) + right_prob = node->m_right->m_c->m_subtree_prob; + p = ((right_prob + default_prob.apply_scale (1, 2)) + / (node->m_c->m_subtree_prob + default_prob)); + + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), + GT_EXPR, test_bb, p, loc); + default_prob = default_prob.apply_scale (1, 2); + + /* Value belongs to this node or to the left-hand subtree. */ + p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), + GE_EXPR, node->m_c->m_case_bb, p, loc); + + /* Handle the left-hand subtree. */ + bb = emit_case_nodes (bb, index, node->m_left, + default_prob, index_type, loc); + + /* If the left-hand subtree fell through, + don't let it fall into the right-hand subtree. */ + if (bb && m_default_bb) + emit_jump (bb, m_default_bb); + + bb = emit_case_nodes (test_bb, index, node->m_right, + default_prob, index_type, loc); + } + else + { + /* Node has no children so we check low and high bounds to remove + redundant tests. Only one of the bounds can exist, + since otherwise this node is bounded--a case tested already. */ + tree lhs, rhs; + generate_range_test (bb, index, node->m_c->get_low (), + node->m_c->get_high (), &lhs, &rhs); + p = default_prob / (node->m_c->m_subtree_prob + default_prob); + + bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, + m_default_bb, p, loc); + + emit_jump (bb, node->m_c->m_case_bb); + return NULL; + } } - /* At this point all checks have passed and we can proceed with the - transformation. */ - - create_temp_arrays (&info); - gather_default_values (gimple_switch_default_label (swtch), &info); - build_constructors (swtch, &info); - - build_arrays (swtch, &info); /* Build the static arrays and assignments. */ - gen_inbound_check (swtch, &info); /* Build the bounds check. */ - - /* Cleanup: */ - free_temp_arrays (&info); - return NULL; + return bb; } /* The main function of the pass scans statements for switches and invokes @@ -1461,11 +2378,11 @@ unsigned int pass_convert_switch::execute (function *fun) { basic_block bb; + bool cfg_altered = false; FOR_EACH_BB_FN (bb, fun) { - const char *failure_reason; - gimple stmt = last_stmt (bb); + gimple *stmt = last_stmt (bb); if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) { if (dump_file) @@ -1479,8 +2396,10 @@ pass_convert_switch::execute (function *fun) putc ('\n', dump_file); } - failure_reason = process_switch (as_a (stmt)); - if (! failure_reason) + switch_conversion sconv; + sconv.expand (as_a (stmt)); + cfg_altered |= sconv.m_cfg_altered; + if (!sconv.m_reason) { if (dump_file) { @@ -1488,9 +2407,10 @@ pass_convert_switch::execute (function *fun) fputs ("--------------------------------\n", dump_file); } - /* 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. */ + /* 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 @@ -1498,14 +2418,14 @@ pass_convert_switch::execute (function *fun) if (dump_file) { fputs ("Bailing out - ", dump_file); - fputs (failure_reason, dump_file); + fputs (sconv.m_reason, dump_file); fputs ("\n--------------------------------\n", dump_file); } } } } - return 0; + return cfg_altered ? TODO_cleanup_cfg : 0;; } } // anon namespace @@ -1515,3 +2435,111 @@ make_pass_convert_switch (gcc::context *ctxt) { return new pass_convert_switch (ctxt); } + +/* The main function of the pass scans statements for switches and invokes + process_switch on them. */ + +namespace { + +template class pass_lower_switch: public gimple_opt_pass +{ +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); + } + + virtual bool + gate (function *) + { + return !O0 || !optimize; + } + + virtual unsigned int execute (function *fun); +}; // class pass_lower_switch + +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 */ +}; + +template +unsigned int +pass_lower_switch::execute (function *fun) +{ + basic_block bb; + bool expanded = false; + + auto_vec switch_statements; + switch_statements.create (1); + + 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); + } + } + + 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)); + + 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); + } + + gswitch *swtch = dyn_cast (stmt); + if (swtch) + { + switch_decision_tree dt (swtch); + expanded |= dt.analyze_switch_statement (); + } + } + + if (expanded) + { + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + mark_virtual_operands_for_renaming (cfun); + } + + return 0; +} + +} // anon namespace + +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 new pass_lower_switch (ctxt); +} + +