gcc/ChangeLog: 2018-06-07 Martin Liska <mli...@suse.cz>
* tree-switch-conversion.c (MAX_CASE_BIT_TESTS): Remove. (hoist_edge_and_branch_if_true): Likewise. (expand_switch_using_bit_tests_p): Likewise. (struct case_bit_test): Likewise. (case_bit_test_cmp): Likewise. (emit_case_bit_tests): Likewise. (switch_conversion::switch_conversion): New class. (struct switch_conv_info): Remove old struct. (collect_switch_conv_info): More to ... (switch_conversion::collect): ... this. (check_range): Likewise. (switch_conversion::check_range): Likewise. (check_all_empty_except_final): Likewise. (switch_conversion::check_all_empty_except_final): Likewise. (check_final_bb): Likewise. (switch_conversion::check_final_bb): Likewise. (create_temp_arrays): Likewise. (switch_conversion::create_temp_arrays): Likewise. (free_temp_arrays): Likewise. (gather_default_values): Likewise. (switch_conversion::gather_default_values): Likewise. (build_constructors): Likewise. (switch_conversion::build_constructors): Likewise. (constructor_contains_same_values_p): Likewise. (switch_conversion::contains_same_values_p): Likewise. (array_value_type): Likewise. (switch_conversion::array_value_type): Likewise. (build_one_array): Likewise. (switch_conversion::build_one_array): Likewise. (build_arrays): Likewise. (switch_conversion::build_arrays): Likewise. (gen_def_assigns): Likewise. (switch_conversion::gen_def_assigns): Likewise. (prune_bbs): Likewise. (switch_conversion::prune_bbs): Likewise. (fix_phi_nodes): Likewise. (switch_conversion::fix_phi_nodes): Likewise. (gen_inbound_check): Likewise. (switch_conversion::gen_inbound_check): Likewise. (process_switch): Use the newly created class. (switch_conversion::expand): New. (switch_conversion::~switch_conversion): New. * tree-switch-conversion.h: New file. --- gcc/tree-switch-conversion.c | 1125 +++++++--------------------------- gcc/tree-switch-conversion.h | 283 +++++++++ 2 files changed, 511 insertions(+), 897 deletions(-) create mode 100644 gcc/tree-switch-conversion.h
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index dc60b34f506..2f848fcb6aa 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -55,626 +55,74 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA type in the GIMPLE type system that is language-independent? */ #include "langhooks.h" +#include "tree-switch-conversion.h" -/* Maximum number of case bit tests. - FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and - targetm.case_values_threshold(), or be its own param. */ -#define MAX_CASE_BIT_TESTS 3 - -/* Track whether or not we have altered the CFG and thus may need to - cleanup the CFG when complete. */ -bool cfg_altered; - -/* 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. */ +using namespace tree_switch_conversion; -static basic_block -hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, - tree cond, edge e_true, - bool update_dominators) -{ - 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); - - if (update_dominators - && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb) - dominated_e_true = true; - - 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_true->flags &= ~EDGE_FALLTHRU; - e_true->flags |= EDGE_TRUE_VALUE; - - e_false->flags &= ~EDGE_FALLTHRU; - e_false->flags |= EDGE_FALSE_VALUE; - e_false->probability = e_true->probability.invert (); - new_bb->count = e_false->count (); - - if (update_dominators) - { - if (dominated_e_true) - set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb); - set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb); - } - - return new_bb; -} - - -/* 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. */ - -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 - -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: - - if ((x==4) || (x==6) || (x==9) || (x==11)) - -as a single bit test: - - if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11))) - -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". - -The following example shows the code the transformation generates: - - 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; - } - -==> - - 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; - } - -TODO: There are still some improvements to this transformation that could -be implemented: - -* 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. - -* 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. - -This transformation was contributed by Roger Sayle, see this e-mail: - http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html -*/ - -/* 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. */ - -struct case_bit_test -{ - wide_int mask; - edge target_edge; - tree label; - int bits; -}; - -/* Comparison function for qsort to order bit tests by decreasing - probability of execution. Our best guess comes from a measured - profile. If the profile counts are equal, break even on the - number of case nodes, i.e. the node with the most cases gets - tested first. - - TODO: Actually this currently runs before a profile is available. - Therefore the case-as-bit-tests transformation should be done - later in the pass pipeline, or something along the lines of - "Efficient and effective branch reordering using profile data" - (Yang et. al., 2002) should be implemented (although, how good - is a paper is called "Efficient and effective ..." when the - latter is implied by the former, but oh well...). */ - -static int -case_bit_test_cmp (const void *p1, const void *p2) -{ - const struct case_bit_test *const d1 = (const struct case_bit_test *) p1; - const struct case_bit_test *const d2 = (const struct case_bit_test *) p2; - - if (d2->target_edge->count () < d1->target_edge->count ()) - return -1; - if (d2->target_edge->count () > d1->target_edge->count ()) - return 1; - if (d2->bits != d1->bits) - return d2->bits - d1->bits; - - /* Stabilize the sort. */ - return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (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. */ - -static void -emit_case_bit_tests (gswitch *swtch, tree index_expr, - tree minval, tree range, tree maxval) +switch_conversion::switch_conversion (): m_final_bb (NULL), m_other_count (), + 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) { - struct case_bit_test test[MAX_CASE_BIT_TESTS] = { {} }; - unsigned int i, j, k; - unsigned int count; - - basic_block switch_bb = gimple_bb (swtch); - basic_block default_bb, new_default_bb, new_bb; - edge default_edge; - bool update_dom = dom_info_available_p (CDI_DOMINATORS); - - vec<basic_block> bbs_to_fix_dom = vNULL; - - 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); - - gimple_stmt_iterator gsi; - gassign *shift_stmt; - - 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); - - /* 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); - - /* 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; - - if (k == count) - { - gcc_checking_assert (count < MAX_CASE_BIT_TESTS); - test[k].mask = wi::zero (prec); - test[k].target_edge = e; - test[k].label = label; - test[k].bits = 1; - count++; - } - else - test[k].bits++; - - lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, - CASE_LOW (cs), minval)); - if (CASE_HIGH (cs) == NULL_TREE) - hi = lo; - else - hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, - CASE_HIGH (cs), minval)); - - 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_bb_for_speed_p (gimple_bb (swtch)); - cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg, - GEN_INT (-m)), speed_p); - for (i = 0; i < count; i++) - { - rtx r = immed_wide_int_const (test[i].mask, word_mode); - cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), - word_mode, speed_p); - r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode); - cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), - word_mode, speed_p); - } - 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); - - 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); - } - - /* Now build the test-and-branch code. */ - - gsi = gsi_last_bb (switch_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 (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<basic_block> dom_bbs; - basic_block dom_son; - - 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); - - /* 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); - } - - /* We should have removed all edges now. */ - gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); - - /* If nothing matched, go to the default label. */ - make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU); - - /* The GIMPLE_SWITCH is now redundant. */ - gsi_remove (&gsi, true); - - if (update_dom) - { - /* Fix up the dominator tree. */ - iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); - bbs_to_fix_dom.release (); - } } - -/* - Switch initialization conversion - -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: - - int a,b; - - 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 <a_1, a_2, a_3, a_4> - b_5 = PHI <b_1, b_2, b_3, b_4> - - -is changed into: - - 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}; - - 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 <a_6, a_7> - b_b = PHI <b_6, b_7> - -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. - -This transformation was contributed by Martin Jambor, see this e-mail: - http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */ - -/* The main structure of the pass. */ -struct switch_conv_info -{ - /* The expression used to decide the switch branch. */ - tree index_expr; - - /* The following integer constants store the minimum and maximum value - covered by the case labels. */ - tree range_min; - tree range_max; - - /* 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; - /* Basic block that contains the actual GIMPLE_SWITCH. */ - basic_block switch_bb; - - /* Basic block that is the target of the default case. */ - basic_block default_bb; - - /* The single successor block of all branches out of the GIMPLE_SWITCH, - if such a block exists. Otherwise NULL. */ - basic_block final_bb; - - /* The probability of the default edge in the replaced switch. */ - profile_probability default_prob; - - /* The count of the default edge in the replaced switch. */ - profile_count default_count; - - /* Combined count of all other (non-default) edges in the replaced switch. */ - profile_count other_count; - - /* Number of phi nodes in the final bb (that we'll be replacing). */ - int phi_count; - - /* Array of default values, in the same order as phi nodes. */ - tree *default_values; - - /* Constructors of new static arrays. */ - vec<constructor_elt, va_gc> **constructors; - - /* Array of ssa names that are initialized with a value from a new static - array. */ - tree *target_inbound_names; - - /* Array of ssa names that are initialized with the default value if the - switch expression is out of range. */ - tree *target_outbound_names; - - /* VOP SSA_NAME. */ - tree target_vop; - - /* The first load statement that loads a temporary from a new static array. - */ - gimple *arr_ref_first; - - /* The last load statement that loads a temporary from a new static array. */ - gimple *arr_ref_last; - - /* String reason why the case wasn't a good candidate that is written to the - dump file, if there is one. */ - const char *reason; - - /* True if default case is not used for any value between range_min and - range_max inclusive. */ - bool contiguous_range; - - /* True if default case does not have the required shape for other case - labels. */ - bool default_case_nonstandard; - - /* Parameters for expand_switch_using_bit_tests. Should be computed - the same way as in expand_case. */ - unsigned int uniq; - unsigned int count; -}; - -/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */ - -static void -collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info) +void +switch_conversion::collect (gswitch *swtch) { unsigned int branch_num = gimple_switch_num_labels (swtch); tree min_case, max_case; - unsigned int count, i; + unsigned int i; edge e, e_default, e_first; edge_iterator ei; basic_block first; - memset (info, 0, sizeof (*info)); + m_switch = swtch; /* 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 + m_index_expr = gimple_switch_index (swtch); + m_switch_bb = gimple_bb (swtch); + m_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) + e_default = find_edge (m_switch_bb, m_default_bb); + m_default_prob = e_default->probability; + m_default_count = e_default->count (); + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) if (e != e_default) - info->other_count += e->count (); + m_other_count += e->count (); /* 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); - info->range_min = CASE_LOW (min_case); + m_range_min = CASE_LOW (min_case); if (CASE_HIGH (max_case) != NULL_TREE) - info->range_max = CASE_HIGH (max_case); + m_range_max = CASE_HIGH (max_case); else - info->range_max = CASE_LOW (max_case); + m_range_max = CASE_LOW (max_case); - info->contiguous_range = true; - tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min; + m_contiguous_range = true; + tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min; for (i = 2; i < branch_num; i++) { tree elt = gimple_switch_label (swtch, i); if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt))) { - info->contiguous_range = false; + m_contiguous_range = false; break; } last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt); } - if (info->contiguous_range) + if (m_contiguous_range) { first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1))); - e_first = find_edge (info->switch_bb, first); + e_first = find_edge (m_switch_bb, first); } else { - first = info->default_bb; + first = m_default_bb; e_first = e_default; } @@ -684,103 +132,91 @@ collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info) if the range is contiguous and default case otherwise as guess or its destination in case it is a forwarder block. */ if (! single_pred_p (e_first->dest)) - info->final_bb = e_first->dest; + m_final_bb = e_first->dest; else if (single_succ_p (e_first->dest) && ! single_pred_p (single_succ (e_first->dest))) - info->final_bb = single_succ (e_first->dest); + 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 (info->final_bb) - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) + if (m_final_bb) + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) { - if (e->dest == info->final_bb) + if (e->dest == m_final_bb) continue; if (single_pred_p (e->dest) && single_succ_p (e->dest) - && single_succ (e->dest) == info->final_bb) + && single_succ (e->dest) == m_final_bb) continue; - if (e == e_default && info->contiguous_range) + if (e == e_default && m_contiguous_range) { - info->default_case_nonstandard = true; + m_default_case_nonstandard = true; continue; } - info->final_bb = NULL; + m_final_bb = NULL; break; } - info->range_size - = int_const_binop (MINUS_EXPR, info->range_max, info->range_min); + m_range_size + = int_const_binop (MINUS_EXPR, m_range_max, m_range_min); /* Get a count of the number of case labels. Single-valued case labels simply count as one, but a case range counts double, since it may require two compares if it gets lowered as a branching tree. */ - count = 0; + m_count = 0; for (i = 1; i < branch_num; i++) { tree elt = gimple_switch_label (swtch, i); - count++; + m_count++; if (CASE_HIGH (elt) && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt))) - count++; + m_count++; } - info->count = count; - - /* Get the number of unique non-default targets out of the GIMPLE_SWITCH - block. Assume a CFG cleanup would have already removed degenerate - switch statements, this allows us to just use EDGE_COUNT. */ - info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1; } -/* Checks whether the range given by individual case statements of the SWTCH - switch statement isn't too big and whether the number of branches actually - satisfies the size of the new array. */ - -static bool -check_range (struct switch_conv_info *info) +bool +switch_conversion::check_range () { - gcc_assert (info->range_size); - if (!tree_fits_uhwi_p (info->range_size)) + gcc_assert (m_range_size); + if (!tree_fits_uhwi_p (m_range_size)) { - info->reason = "index range way too large or otherwise unusable"; + m_reason = "index range way too large or otherwise unusable"; return false; } - if (tree_to_uhwi (info->range_size) - > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO)) + if (tree_to_uhwi (m_range_size) + > ((unsigned) m_count * SWITCH_CONVERSION_BRANCH_RATIO)) { - info->reason = "the maximum range-branch ratio exceeded"; + m_reason = "the maximum range-branch ratio exceeded"; return false; } return true; } -/* Checks whether all but the FINAL_BB basic blocks are empty. */ - -static bool -check_all_empty_except_final (struct switch_conv_info *info) +bool +switch_conversion::check_all_empty_except_final () { - edge e, e_default = find_edge (info->switch_bb, info->default_bb); + edge e, e_default = find_edge (m_switch_bb, m_default_bb); edge_iterator ei; - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) { - if (e->dest == info->final_bb) + if (e->dest == m_final_bb) continue; if (!empty_block_p (e->dest)) { - if (info->contiguous_range && e == e_default) + if (m_contiguous_range && e == e_default) { - info->default_case_nonstandard = true; + m_default_case_nonstandard = true; continue; } - info->reason = "bad case - a non-final BB not empty"; + m_reason = "bad case - a non-final BB not empty"; return false; } } @@ -788,18 +224,13 @@ check_all_empty_except_final (struct switch_conv_info *info) return true; } -/* This function checks whether all required values in phi nodes in final_bb - are constants. Required values are those that correspond to a basic block - which is a part of the examined switch statement. It returns true if the - phi nodes are OK, otherwise false. */ - -static bool -check_final_bb (gswitch *swtch, struct switch_conv_info *info) +bool +switch_conversion::check_final_bb () { gphi_iterator gsi; - info->phi_count = 0; - for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + 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; @@ -807,16 +238,16 @@ check_final_bb (gswitch *swtch, struct switch_conv_info *info) if (virtual_operand_p (gimple_phi_result (phi))) continue; - info->phi_count++; + m_phi_count++; for (i = 0; i < gimple_phi_num_args (phi); i++) { basic_block bb = gimple_phi_arg_edge (phi, i)->src; - if (bb == info->switch_bb + if (bb == m_switch_bb || (single_pred_p (bb) - && single_pred (bb) == info->switch_bb - && (!info->default_case_nonstandard + && single_pred (bb) == m_switch_bb + && (!m_default_case_nonstandard || empty_block_p (bb)))) { tree reloc, val; @@ -844,25 +275,25 @@ check_final_bb (gswitch *swtch, struct switch_conv_info *info) /* For contiguous range, we can allow non-constant or one that needs relocation, as long as it is only reachable from the default case. */ - if (bb == info->switch_bb) - bb = info->final_bb; - if (!info->contiguous_range || bb != info->default_bb) + if (bb == m_switch_bb) + bb = m_final_bb; + if (!m_contiguous_range || bb != m_default_bb) { - info->reason = reason; + m_reason = reason; return false; } - unsigned int branch_num = gimple_switch_num_labels (swtch); + unsigned int branch_num = gimple_switch_num_labels (m_switch); for (unsigned int i = 1; i < branch_num; i++) { - tree lab = CASE_LABEL (gimple_switch_label (swtch, i)); + tree lab = CASE_LABEL (gimple_switch_label (m_switch, i)); if (label_to_block (lab) == bb) { - info->reason = reason; + m_reason = reason; return false; } } - info->default_case_nonstandard = true; + m_default_case_nonstandard = true; } } } @@ -871,44 +302,24 @@ check_final_bb (gswitch *swtch, struct switch_conv_info *info) return true; } -/* The following function allocates default_values, target_{in,out}_names and - constructors arrays. The last one is also populated with pointers to - vectors that will become constructors of new arrays. */ - -static void -create_temp_arrays (struct switch_conv_info *info) +void +switch_conversion::create_temp_arrays () { int i; - info->default_values = XCNEWVEC (tree, info->phi_count * 3); + 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<constructor_elt, va_gc> *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); + 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); } -/* Free the arrays created by create_temp_arrays(). The vectors that are - created by that function are not freed here, however, because they have - already become constructors and must be preserved. */ - -static void -free_temp_arrays (struct switch_conv_info *info) -{ - XDELETEVEC (info->constructors); - XDELETEVEC (info->default_values); -} - -/* Populate the array of default values in the order of phi nodes. - DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch - if the range is non-contiguous or the default case has standard - structure, otherwise it is the first non-default case instead. */ - -static void -gather_default_values (tree default_case, struct switch_conv_info *info) +void +switch_conversion::gather_default_values (tree default_case) { gphi_iterator gsi; basic_block bb = label_to_block (CASE_LABEL (default_case)); @@ -916,46 +327,42 @@ gather_default_values (tree default_case, struct switch_conv_info *info) int i = 0; gcc_assert (CASE_LOW (default_case) == NULL_TREE - || info->default_case_nonstandard); + || m_default_case_nonstandard); - if (bb == info->final_bb) - e = find_edge (info->switch_bb, bb); + if (bb == m_final_bb) + e = find_edge (m_switch_bb, bb); else e = single_succ_edge (bb); - for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + 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); - info->default_values[i++] = val; + m_default_values[i++] = val; } } -/* The following function populates the vectors in the constructors array with - future contents of the static arrays. The vectors are populated in the - order of phi nodes. SWTCH is the switch statement being converted. */ - -static void -build_constructors (gswitch *swtch, struct switch_conv_info *info) +void +switch_conversion::build_constructors () { - unsigned i, branch_num = gimple_switch_num_labels (swtch); - tree pos = info->range_min; + 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); for (i = 1; i < branch_num; i++) { - tree cs = gimple_switch_label (swtch, i); + tree cs = gimple_switch_label (m_switch, i); basic_block bb = label_to_block (CASE_LABEL (cs)); edge e; tree high; gphi_iterator gsi; int j; - if (bb == info->final_bb) - e = find_edge (info->switch_bb, bb); + if (bb == m_final_bb) + e = find_edge (m_switch_bb, bb); else e = single_succ_edge (bb); gcc_assert (e); @@ -963,15 +370,14 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info) while (tree_int_cst_lt (pos, CASE_LOW (cs))) { int k; - gcc_assert (!info->contiguous_range); - for (k = 0; k < info->phi_count; k++) + for (k = 0; k < m_phi_count; k++) { constructor_elt elt; - elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); + elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min); elt.value - = unshare_expr_without_location (info->default_values[k]); - info->constructors[k]->quick_push (elt); + = unshare_expr_without_location (m_default_values[k]); + m_constructors[k]->quick_push (elt); } pos = int_const_binop (PLUS_EXPR, pos, pos_one); @@ -983,7 +389,7 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info) high = CASE_HIGH (cs); else high = CASE_LOW (cs); - for (gsi = gsi_start_phis (info->final_bb); + for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); @@ -997,9 +403,9 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info) { constructor_elt elt; - elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); + elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min); elt.value = unshare_expr_without_location (val); - info->constructors[j]->quick_push (elt); + m_constructors[j]->quick_push (elt); pos = int_const_binop (PLUS_EXPR, pos, pos_one); } while (!tree_int_cst_lt (high, pos) @@ -1009,12 +415,8 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info) } } -/* If all values in the constructor vector are the same, return the value. - Otherwise return NULL_TREE. Not supposed to be called for empty - vectors. */ - -static tree -constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec) +tree +switch_conversion::contains_same_values_p (vec<constructor_elt, va_gc> *vec) { unsigned int i; tree prev = NULL_TREE; @@ -1030,15 +432,10 @@ constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec) return prev; } -/* Return type which should be used for array elements, either TYPE's - main variant or, for integral types, some smaller integral type - that can still hold all the constants. */ - -static tree -array_value_type (gswitch *swtch, tree type, int num, - struct switch_conv_info *info) +tree +switch_conversion::array_value_type (tree type, int num) { - unsigned int i, len = vec_safe_length (info->constructors[num]); + unsigned int i, len = vec_safe_length (m_constructors[num]); constructor_elt *elt; int sign = 0; tree smaller_type; @@ -1058,10 +455,10 @@ array_value_type (gswitch *swtch, tree type, int num, if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode)) return type; - if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32)) + if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32)) return type; - FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) + FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt) { wide_int cst; @@ -1107,49 +504,39 @@ array_value_type (gswitch *swtch, tree type, int num, return smaller_type; } -/* Create an appropriate array type and declaration and assemble a static array - variable. Also create a load statement that initializes the variable in - question with a value from the static array. SWTCH is the switch statement - being converted, NUM is the index to arrays of constructors, default values - and target SSA names for this particular array. ARR_INDEX_TYPE is the type - of the index of the new array, PHI is the phi node of the final BB that - corresponds to the value that will be loaded from the created array. TIDX - is an ssa name of a temporary variable holding the index for loads from the - new array. */ - -static void -build_one_array (gswitch *swtch, int num, tree arr_index_type, - gphi *phi, tree tidx, struct switch_conv_info *info) +void +switch_conversion::build_one_array (int num, tree arr_index_type, + gphi *phi, tree tidx) { tree name, cst; gimple *load; - gimple_stmt_iterator gsi = gsi_for_stmt (swtch); - location_t loc = gimple_location (swtch); + gimple_stmt_iterator gsi = gsi_for_stmt (m_switch); + location_t loc = gimple_location (m_switch); - gcc_assert (info->default_values[num]); + gcc_assert (m_default_values[num]); name = copy_ssa_name (PHI_RESULT (phi)); - info->target_inbound_names[num] = name; + m_target_inbound_names[num] = name; - cst = constructor_contains_same_values_p (info->constructors[num]); + cst = contains_same_values_p (m_constructors[num]); if (cst) load = gimple_build_assign (name, cst); else { tree array_type, ctor, decl, value_type, fetch, default_type; - default_type = TREE_TYPE (info->default_values[num]); - value_type = array_value_type (swtch, default_type, num, info); + 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; - FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) + FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt) elt->value = fold_convert (value_type, elt->value); } - ctor = build_constructor (array_type, info->constructors[num]); + ctor = build_constructor (array_type, m_constructors[num]); TREE_CONSTANT (ctor) = true; TREE_STATIC (ctor) = true; @@ -1182,15 +569,11 @@ build_one_array (gswitch *swtch, int num, tree arr_index_type, gsi_insert_before (&gsi, load, GSI_SAME_STMT); update_stmt (load); - info->arr_ref_last = load; + m_arr_ref_last = load; } -/* Builds and initializes static arrays initialized with values gathered from - the SWTCH switch statement. Also creates statements that load values from - them. */ - -static void -build_arrays (gswitch *swtch, struct switch_conv_info *info) +void +switch_conversion::build_arrays () { tree arr_index_type; tree tidx, sub, utype; @@ -1198,84 +581,77 @@ build_arrays (gswitch *swtch, struct switch_conv_info *info) gimple_stmt_iterator gsi; gphi_iterator gpi; int i; - location_t loc = gimple_location (swtch); + location_t loc = gimple_location (m_switch); - gsi = gsi_for_stmt (swtch); + gsi = gsi_for_stmt (m_switch); /* Make sure we do not generate arithmetics in a subrange. */ - utype = TREE_TYPE (info->index_expr); + utype = TREE_TYPE (m_index_expr); if (TREE_TYPE (utype)) utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1); else utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1); - arr_index_type = build_index_type (info->range_size); + arr_index_type = build_index_type (m_range_size); tidx = make_ssa_name (utype); sub = fold_build2_loc (loc, MINUS_EXPR, utype, - fold_convert_loc (loc, utype, info->index_expr), - fold_convert_loc (loc, utype, info->range_min)); + fold_convert_loc (loc, utype, m_index_expr), + fold_convert_loc (loc, utype, m_range_min)); sub = force_gimple_operand_gsi (&gsi, sub, false, NULL, true, GSI_SAME_STMT); stmt = gimple_build_assign (tidx, sub); gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); update_stmt (stmt); - info->arr_ref_first = stmt; + m_arr_ref_first = stmt; - for (gpi = gsi_start_phis (info->final_bb), i = 0; + for (gpi = gsi_start_phis (m_final_bb), i = 0; !gsi_end_p (gpi); gsi_next (&gpi)) { gphi *phi = gpi.phi (); if (!virtual_operand_p (gimple_phi_result (phi))) - build_one_array (swtch, i++, arr_index_type, phi, tidx, info); + build_one_array (i++, arr_index_type, phi, tidx); else { edge e; edge_iterator ei; - FOR_EACH_EDGE (e, ei, info->switch_bb->succs) + FOR_EACH_EDGE (e, ei, m_switch_bb->succs) { - if (e->dest == info->final_bb) + if (e->dest == m_final_bb) break; - if (!info->default_case_nonstandard - || e->dest != info->default_bb) + if (!m_default_case_nonstandard + || e->dest != m_default_bb) { e = single_succ_edge (e->dest); break; } } - gcc_assert (e && e->dest == info->final_bb); - info->target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e); + gcc_assert (e && e->dest == m_final_bb); + m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e); } } } -/* Generates and appropriately inserts loads of default values at the position - given by BSI. Returns the last inserted statement. */ - -static gassign * -gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info) +gassign * +switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi) { int i; gassign *assign = NULL; - for (i = 0; i < info->phi_count; i++) + for (i = 0; i < m_phi_count; i++) { - tree name = copy_ssa_name (info->target_inbound_names[i]); - info->target_outbound_names[i] = name; - assign = gimple_build_assign (name, info->default_values[i]); + tree name = copy_ssa_name (m_target_inbound_names[i]); + m_target_outbound_names[i] = name; + assign = gimple_build_assign (name, m_default_values[i]); gsi_insert_before (gsi, assign, GSI_SAME_STMT); update_stmt (assign); } 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). */ - -static void -prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) +void +switch_conversion::prune_bbs (basic_block bbd, basic_block final, + basic_block default_bb) { edge_iterator ei; edge e; @@ -1291,14 +667,8 @@ prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) delete_basic_block (bbd); } -/* 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). */ - -static void -fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, - struct switch_conv_info *info) +void +switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) { gphi_iterator gsi; int i; @@ -1309,41 +679,20 @@ fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, gphi *phi = gsi.phi (); tree inbound, outbound; if (virtual_operand_p (gimple_phi_result (phi))) - inbound = outbound = info->target_vop; + inbound = outbound = m_target_vop; else { - inbound = info->target_inbound_names[i]; - outbound = info->target_outbound_names[i++]; + inbound = m_target_inbound_names[i]; + outbound = m_target_outbound_names[i++]; } add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION); - if (!info->default_case_nonstandard) + if (!m_default_case_nonstandard) add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION); } } -/* Creates a check whether the switch expression value actually falls into the - range given by all the cases. If it does not, the temporaries are loaded - with default values instead. SWTCH is the switch statement being converted. - - bb0 is the bb with the switch statement, however, we'll end it with a - condition instead. - - bb1 is the bb to be used when the range check went ok. It is derived from - the switch BB - - bb2 is the bb taken when the expression evaluated outside of the range - covered by the created arrays. It is populated by loads of default - values. - - bbF is a fall through for both bb1 and bb2 and contains exactly what - originally followed the switch statement. - - bbD contains the switch statement (in the end). It is unreachable but we - still need to strip off its edges. -*/ - -static void -gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) +void +switch_conversion::gen_inbound_check () { tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); @@ -1358,30 +707,30 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) gimple_stmt_iterator gsi; basic_block bb0, bb1, bb2, bbf, bbd; edge e01 = NULL, e02, e21, e1d, e1f, e2f; - location_t loc = gimple_location (swtch); + location_t loc = gimple_location (m_switch); - gcc_assert (info->default_values); + gcc_assert (m_default_values); - bb0 = gimple_bb (swtch); + bb0 = gimple_bb (m_switch); - tidx = gimple_assign_lhs (info->arr_ref_first); + tidx = gimple_assign_lhs (m_arr_ref_first); utype = TREE_TYPE (tidx); /* (end of) block 0 */ - gsi = gsi_for_stmt (info->arr_ref_first); + gsi = gsi_for_stmt (m_arr_ref_first); gsi_next (&gsi); - bound = fold_convert_loc (loc, utype, info->range_size); + bound = fold_convert_loc (loc, utype, m_range_size); cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE); gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); update_stmt (cond_stmt); /* block 2 */ - if (!info->default_case_nonstandard) + if (!m_default_case_nonstandard) { label2 = gimple_build_label (label_decl2); gsi_insert_before (&gsi, label2, GSI_SAME_STMT); - last_assign = gen_def_assigns (&gsi, info); + last_assign = gen_def_assigns (&gsi); } /* block 1 */ @@ -1389,7 +738,7 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) gsi_insert_before (&gsi, label1, GSI_SAME_STMT); /* block F */ - gsi = gsi_start_bb (info->final_bb); + gsi = gsi_start_bb (m_final_bb); label3 = gimple_build_label (label_decl3); gsi_insert_before (&gsi, label3, GSI_SAME_STMT); @@ -1397,10 +746,10 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) e02 = split_block (bb0, cond_stmt); bb2 = e02->dest; - if (info->default_case_nonstandard) + if (m_default_case_nonstandard) { bb1 = bb2; - bb2 = info->default_bb; + bb2 = m_default_bb; e01 = e02; e01->flags = EDGE_TRUE_VALUE; e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE); @@ -1424,26 +773,26 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) remove_edge (e21); } - e1d = split_block (bb1, info->arr_ref_last); + e1d = split_block (bb1, m_arr_ref_last); bbd = e1d->dest; remove_edge (e1d); - /* flags and profiles of the edge for in-range values */ - if (!info->default_case_nonstandard) + /* 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 = info->default_prob.invert (); + e01->probability = m_default_prob.invert (); - /* flags and profiles of the edge taking care of out-of-range values */ + /* 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->probability = m_default_prob; - bbf = info->final_bb; + bbf = m_final_bb; e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); e1f->probability = profile_probability::always (); - if (info->default_case_nonstandard) + if (m_default_case_nonstandard) e2f = NULL; else { @@ -1454,15 +803,15 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) /* frequencies of the new BBs */ bb1->count = e01->count (); bb2->count = e02->count (); - if (!info->default_case_nonstandard) + if (!m_default_case_nonstandard) bbf->count = e1f->count () + e2f->count (); /* Tidy blocks that have become unreachable. */ - prune_bbs (bbd, info->final_bb, - info->default_case_nonstandard ? info->default_bb : NULL); + 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, info); + fix_phi_nodes (e1f, e2f, bbf); /* Fix the dominator tree, if it is available. */ if (dom_info_available_p (CDI_DOMINATORS)) @@ -1470,7 +819,7 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) vec<basic_block> bbs_to_fix_dom; set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); - if (!info->default_case_nonstandard) + 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 ... */ @@ -1488,95 +837,76 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) } } -/* 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. */ - -static const char * -process_switch (gswitch *swtch) +void +switch_conversion::expand (gswitch *swtch) { - struct switch_conv_info info; - /* Group case labels so that we get the right results from the heuristics that decide on the code generation approach for this switch. */ - cfg_altered |= group_case_labels_stmt (swtch); + m_cfg_altered |= group_case_labels_stmt (swtch); /* If this switch is now a degenerate case with only a default label, - there is nothing left for us to do. */ + there is nothing left for us to do. */ if (gimple_switch_num_labels (swtch) < 2) - return "switch is a degenerate case"; + { + m_reason = "switch is a degenerate case"; + return; + } - collect_switch_conv_info (swtch, &info); + collect (swtch); /* No error markers should reach here (they should be filtered out during gimplification). */ - gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node); + gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node); /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ - gcc_checking_assert (! TREE_CONSTANT (info.index_expr)); + gcc_checking_assert (!TREE_CONSTANT (m_index_expr)); - if (info.uniq <= MAX_CASE_BIT_TESTS) + /* If there is no common successor, we cannot do the transformation. */ + if (!m_final_bb) { - if (expand_switch_using_bit_tests_p (info.range_size, - info.uniq, info.count, - optimize_bb_for_speed_p - (gimple_bb (swtch)))) - { - if (dump_file) - fputs (" expanding as bit test is preferable\n", dump_file); - emit_case_bit_tests (swtch, info.index_expr, info.range_min, - info.range_size, info.range_max); - loops_state_set (LOOPS_NEED_FIXUP); - return NULL; - } - - if (info.uniq <= 2) - /* This will be expanded as a decision tree in stmt.c:expand_case. */ - return " expanding as jumps is preferable"; + m_reason = "no common successor to all case label target blocks found"; + return; } - /* 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"; - /* Check the case label values are within reasonable range: */ - if (!check_range (&info)) + if (!check_range ()) { - gcc_assert (info.reason); - return info.reason; + gcc_assert (m_reason); + return; } /* For all the cases, see whether they are empty, the assignments they represent constant and so on... */ - if (! check_all_empty_except_final (&info)) + if (!check_all_empty_except_final ()) { - gcc_assert (info.reason); - return info.reason; + gcc_assert (m_reason); + return; } - if (!check_final_bb (swtch, &info)) + if (!check_final_bb ()) { - gcc_assert (info.reason); - return info.reason; + gcc_assert (m_reason); + return; } /* At this point all checks have passed and we can proceed with the transformation. */ - create_temp_arrays (&info); - gather_default_values (info.default_case_nonstandard + create_temp_arrays (); + gather_default_values (m_default_case_nonstandard ? gimple_switch_label (swtch, 1) - : gimple_switch_default_label (swtch), &info); - if (info.phi_count) - build_constructors (swtch, &info); + : gimple_switch_default_label (swtch)); + build_constructors (); - build_arrays (swtch, &info); /* Build the static arrays and assignments. */ - gen_inbound_check (swtch, &info); /* Build the bounds check. */ + build_arrays (); /* Build the static arrays and assignments. */ + gen_inbound_check (); /* Build the bounds check. */ - /* Cleanup: */ - free_temp_arrays (&info); - return NULL; + m_cfg_altered = true; +} + +switch_conversion::~switch_conversion () +{ + XDELETEVEC (m_constructors); + XDELETEVEC (m_default_values); } /* The main function of the pass scans statements for switches and invokes @@ -1614,11 +944,10 @@ unsigned int pass_convert_switch::execute (function *fun) { basic_block bb; + bool cfg_altered = false; - cfg_altered = false; FOR_EACH_BB_FN (bb, fun) { - const char *failure_reason; gimple *stmt = last_stmt (bb); if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) { @@ -1633,19 +962,21 @@ pass_convert_switch::execute (function *fun) putc ('\n', dump_file); } - failure_reason = process_switch (as_a <gswitch *> (stmt)); - if (! failure_reason) + switch_conversion sconv; + sconv.expand (as_a <gswitch *> (stmt)); + cfg_altered |= sconv.m_cfg_altered; + if (!sconv.m_reason) { - cfg_altered = true; if (dump_file) { fputs ("Switch converted\n", dump_file); 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 @@ -1653,14 +984,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 cfg_altered ? TODO_cleanup_cfg : 0; + return cfg_altered ? TODO_cleanup_cfg : 0;; } } // anon namespace diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h new file mode 100644 index 00000000000..297faec119f --- /dev/null +++ b/gcc/tree-switch-conversion.h @@ -0,0 +1,283 @@ +/* Tree switch conversion for GNU compiler. + Copyright (C) 2017 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef TREE_SWITCH_CONVERSION_H +#define TREE_SWITCH_CONVERSION_H + +namespace tree_switch_conversion { + +/* + 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: + + int a,b; + + 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 <a_1, a_2, a_3, a_4> + b_5 = PHI <b_1, b_2, b_3, b_4> + + +is changed into: + + 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}; + + 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 <a_6, a_7> + b_b = PHI <b_6, b_7> + +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. + +This transformation was contributed by Martin Jambor, see this e-mail: + http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */ + +/* The main structure of the pass. */ +struct switch_conversion +{ + /* Constructor. */ + switch_conversion (); + + /* Destructor. */ + ~switch_conversion (); + + /* The following function is invoked on every switch statement (the current + one is given in SWTCH) and runs the individual phases of switch + conversion on it one after another until one fails or the conversion + is completed. On success, NULL is in m_reason, otherwise points + to a string with the reason why the conversion failed. */ + void expand (gswitch *swtch); + + /* Collection information about SWTCH statement. */ + void collect (gswitch *swtch); + + /* Checks whether the range given by individual case statements of the switch + switch statement isn't too big and whether the number of branches actually + satisfies the size of the new array. */ + bool check_range (); + + /* Checks whether all but the final BB basic blocks are empty. */ + bool check_all_empty_except_final (); + + /* 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. */ + bool check_final_bb (); + + /* 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 create_temp_arrays (); + + /* 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. */ + void gather_default_values (tree default_case); + + /* 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. */ + void build_constructors (); + + /* If all values in the constructor vector are the same, return the value. + Otherwise return NULL_TREE. Not supposed to be called for empty + vectors. */ + tree contains_same_values_p (vec<constructor_elt, va_gc> *vec); + + /* 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 array_value_type (tree type, int num); + + /* 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. */ + void build_one_array (int num, tree arr_index_type, + gphi *phi, tree tidx); + + /* Builds and initializes static arrays initialized with values gathered from + the switch statement. Also creates statements that load values from + them. */ + void build_arrays (); + + /* Generates and appropriately inserts loads of default values at the position + given by GSI. Returns the last inserted statement. */ + gassign *gen_def_assigns (gimple_stmt_iterator *gsi); + + /* 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). */ + void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb); + + /* 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 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf); + + /* Creates a check whether the switch expression value actually falls into the + range given by all the cases. If it does not, the temporaries are loaded + with default values instead. SWTCH is the switch statement being + converted. + + bb0 is the bb with the switch statement, however, we'll end it with a + condition instead. + + bb1 is the bb to be used when the range check went ok. It is derived from + the switch BB + + bb2 is the bb taken when the expression evaluated outside of the range + covered by the created arrays. It is populated by loads of default + values. + + bbF is a fall through for both bb1 and bb2 and contains exactly what + originally followed the switch statement. + + bbD contains the switch statement (in the end). It is unreachable but we + still need to strip off its edges. */ + void gen_inbound_check (); + + /* Switch statement for which switch conversion takes place. */ + gswitch *m_switch; + + /* The expression used to decide the switch branch. */ + tree m_index_expr; + + /* The following integer constants store the minimum and maximum value + covered by the case labels. */ + tree m_range_min; + tree m_range_max; + + /* 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 m_range_size; + + /* Basic block that contains the actual GIMPLE_SWITCH. */ + basic_block m_switch_bb; + + /* Basic block that is the target of the default case. */ + basic_block m_default_bb; + + /* The single successor block of all branches out of the GIMPLE_SWITCH, + if such a block exists. Otherwise NULL. */ + basic_block m_final_bb; + + /* The probability of the default edge in the replaced switch. */ + profile_probability m_default_prob; + + /* The count of the default edge in the replaced switch. */ + profile_count m_default_count; + + /* Combined count of all other (non-default) edges in the replaced switch. */ + profile_count m_other_count; + + /* Number of phi nodes in the final bb (that we'll be replacing). */ + int m_phi_count; + + /* Constructors of new static arrays. */ + vec<constructor_elt, va_gc> **m_constructors; + + /* Array of default values, in the same order as phi nodes. */ + tree *m_default_values; + + /* Array of ssa names that are initialized with a value from a new static + array. */ + tree *m_target_inbound_names; + + /* Array of ssa names that are initialized with the default value if the + switch expression is out of range. */ + tree *m_target_outbound_names; + + /* VOP SSA_NAME. */ + tree m_target_vop; + + /* The first load statement that loads a temporary from a new static array. + */ + gimple *m_arr_ref_first; + + /* The last load statement that loads a temporary from a new static array. */ + gimple *m_arr_ref_last; + + /* String reason why the case wasn't a good candidate that is written to the + dump file, if there is one. */ + const char *m_reason; + + /* True if default case is not used for any value between range_min and + range_max inclusive. */ + bool m_contiguous_range; + + /* True if default case does not have the required shape for other case + labels. */ + bool m_default_case_nonstandard; + + /* Count is number of non-default edges. */ + unsigned int m_count; + + /* True if CFG has been changed. */ + bool m_cfg_altered; +}; + +} // tree_switch_conversion namespace + +#endif // TREE_SWITCH_CONVERSION_H