From dc223ad48971b2d2b1e4bcfbbb47a96354e3d2ea Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Wed, 20 Jun 2018 10:52:12 +0200 Subject: [PATCH] Switch other switch expansion methods into classes. 2018-06-20 Martin Liska * tree-switch-conversion.c (switch_conversion::collect): Record m_uniq property. (switch_conversion::expand): Bail out for special conditions. (group_cluster::~group_cluster): New. (group_cluster::group_cluster): Likewise. (group_cluster::dump): Likewise. (jump_table_cluster::emit): New. (switch_decision_tree::fix_phi_operands_for_edges): New. (struct case_node): Remove struct. (jump_table_cluster::can_be_handled): New. (case_values_threshold): Moved to header. (reset_out_edges_aux): Likewise. (jump_table_cluster::is_beneficial): New. (bit_test_cluster::can_be_handled): Likewise. (add_case_node): Remove. (bit_test_cluster::is_beneficial): New. (case_bit_test::cmp): New. (bit_test_cluster::emit): New. (expand_switch_as_decision_tree_p): Remove. (bit_test_cluster::hoist_edge_and_branch_if_true): New. (fix_phi_operands_for_edge): Likewise. (switch_decision_tree::analyze_switch_statement): New. (compute_cases_per_edge): Move ... (switch_decision_tree::compute_cases_per_edge): ... here. (try_switch_expansion): Likewise. (switch_decision_tree::try_switch_expansion): Likewise. (record_phi_operand_mapping): Likewise. (switch_decision_tree::record_phi_operand_mapping): Likewise. (emit_case_decision_tree): Likewise. (switch_decision_tree::emit): Likewise. (balance_case_nodes): Likewise. (switch_decision_tree::balance_case_nodes): Likewise. (dump_case_nodes): Likewise. (switch_decision_tree::dump_case_nodes): Likewise. (emit_jump): Likewise. (switch_decision_tree::emit_jump): Likewise. (emit_cmp_and_jump_insns): Likewise. (switch_decision_tree::emit_cmp_and_jump_insns): Likewise. (emit_case_nodes): Likewise. (switch_decision_tree::emit_case_nodes): Likewise. (conditional_probability): Remove. * tree-switch-conversion.h (enum cluster_type): New. (PRINT_CASE): New. (struct cluster): Likewise. (cluster::cluster): Likewise. (struct simple_cluster): Likewise. (simple_cluster::simple_cluster): Likewise. (struct group_cluster): Likewise. (struct jump_table_cluster): Likewise. (struct bit_test_cluster): Likewise. (struct min_cluster_item): Likewise. (struct case_tree_node): Likewise. (case_tree_node::case_tree_node): Likewise. (jump_table_cluster::case_values_threshold): Likewise. (struct case_bit_test): Likewise. (struct switch_decision_tree): Likewise. (struct switch_conversion): Likewise. (switch_decision_tree::reset_out_edges_aux): Likewise. 2018-06-20 Martin Liska * gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL. From-SVN: r261793 --- gcc/ChangeLog | 61 + gcc/testsuite/ChangeLog | 4 + gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 2 +- gcc/tree-switch-conversion.c | 1430 +++++++++++++++--------- gcc/tree-switch-conversion.h | 543 +++++++++ 5 files changed, 1484 insertions(+), 556 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 61759ed5776..4b919a8c957 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,64 @@ +2018-06-20 Martin Liska + + * tree-switch-conversion.c (switch_conversion::collect): + Record m_uniq property. + (switch_conversion::expand): Bail out for special conditions. + (group_cluster::~group_cluster): New. + (group_cluster::group_cluster): Likewise. + (group_cluster::dump): Likewise. + (jump_table_cluster::emit): New. + (switch_decision_tree::fix_phi_operands_for_edges): New. + (struct case_node): Remove struct. + (jump_table_cluster::can_be_handled): New. + (case_values_threshold): Moved to header. + (reset_out_edges_aux): Likewise. + (jump_table_cluster::is_beneficial): New. + (bit_test_cluster::can_be_handled): Likewise. + (add_case_node): Remove. + (bit_test_cluster::is_beneficial): New. + (case_bit_test::cmp): New. + (bit_test_cluster::emit): New. + (expand_switch_as_decision_tree_p): Remove. + (bit_test_cluster::hoist_edge_and_branch_if_true): New. + (fix_phi_operands_for_edge): Likewise. + (switch_decision_tree::analyze_switch_statement): New. + (compute_cases_per_edge): Move ... + (switch_decision_tree::compute_cases_per_edge): ... here. + (try_switch_expansion): Likewise. + (switch_decision_tree::try_switch_expansion): Likewise. + (record_phi_operand_mapping): Likewise. + (switch_decision_tree::record_phi_operand_mapping): Likewise. + (emit_case_decision_tree): Likewise. + (switch_decision_tree::emit): Likewise. + (balance_case_nodes): Likewise. + (switch_decision_tree::balance_case_nodes): Likewise. + (dump_case_nodes): Likewise. + (switch_decision_tree::dump_case_nodes): Likewise. + (emit_jump): Likewise. + (switch_decision_tree::emit_jump): Likewise. + (emit_cmp_and_jump_insns): Likewise. + (switch_decision_tree::emit_cmp_and_jump_insns): Likewise. + (emit_case_nodes): Likewise. + (switch_decision_tree::emit_case_nodes): Likewise. + (conditional_probability): Remove. + * tree-switch-conversion.h (enum cluster_type): New. + (PRINT_CASE): New. + (struct cluster): Likewise. + (cluster::cluster): Likewise. + (struct simple_cluster): Likewise. + (simple_cluster::simple_cluster): Likewise. + (struct group_cluster): Likewise. + (struct jump_table_cluster): Likewise. + (struct bit_test_cluster): Likewise. + (struct min_cluster_item): Likewise. + (struct case_tree_node): Likewise. + (case_tree_node::case_tree_node): Likewise. + (jump_table_cluster::case_values_threshold): Likewise. + (struct case_bit_test): Likewise. + (struct switch_decision_tree): Likewise. + (struct switch_conversion): Likewise. + (switch_decision_tree::reset_out_edges_aux): Likewise. + 2018-06-20 Martin Liska * tree-switch-conversion.c (MAX_CASE_BIT_TESTS): Remove. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 5ce5b61c927..4dd987bcd64 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2018-06-20 Martin Liska + + * gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL. + 2018-06-19 Martin Sebor PR tree-optimization/48560 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c index 71fa3bfa2ca..1bef76f1a21 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c @@ -2,7 +2,7 @@ /* { dg-options "-O2 -fdump-tree-switchlower" } */ /* We scan for 2 switches as the dump file reports a transformation, IL really contains just a single. */ -/* { dg-final { scan-tree-dump-times "switch" 2 "switchlower1" } } */ +/* { dg-final { scan-tree-dump-times "switch \\(" 2 "switchlower1" } } */ void foo (void); void bar (void); diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index e8b44bdd2d8..1260ba2e145 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -179,6 +179,11 @@ switch_conversion::collect (gswitch *swtch) && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt))) m_count++; } + + /* Get the number of unique non-default targets out of the GIMPLE_SWITCH + block. Assume a CFG cleanup would have already removed degenerate + switch statements, this allows us to just use EDGE_COUNT. */ + m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1; } /* Checks whether the range given by individual case statements of the switch @@ -935,6 +940,22 @@ switch_conversion::expand (gswitch *swtch) /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ gcc_checking_assert (!TREE_CONSTANT (m_index_expr)); + /* Prefer bit test if possible. */ + if (tree_fits_uhwi_p (m_range_size) + && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq) + && bit_test_cluster::is_beneficial (m_count, m_uniq)) + { + m_reason = "expanding as bit test is preferable"; + return; + } + + if (m_uniq <= 2) + { + /* This will be expanded as a decision tree . */ + m_reason = "expanding as jumps is preferable"; + return; + } + /* If there is no common successor, we cannot do the transformation. */ if (!m_final_bb) { @@ -985,409 +1006,550 @@ switch_conversion::~switch_conversion () XDELETEVEC (m_default_values); } -/* The main function of the pass scans statements for switches and invokes - process_switch on them. */ - -namespace { +/* Constructor. */ -const pass_data pass_data_convert_switch = +group_cluster::group_cluster (vec &clusters, + unsigned start, unsigned end) { - GIMPLE_PASS, /* type */ - "switchconv", /* name */ - OPTGROUP_NONE, /* optinfo_flags */ - TV_TREE_SWITCH_CONVERSION, /* tv_id */ - ( PROP_cfg | PROP_ssa ), /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_update_ssa, /* todo_flags_finish */ -}; + gcc_checking_assert (end - start + 1 >= 1); + m_prob = profile_probability::never (); + m_cases.create (end - start + 1); + for (unsigned i = start; i <= end; i++) + { + m_cases.quick_push (static_cast (clusters[i])); + m_prob += clusters[i]->m_prob; + } + m_subtree_prob = m_prob; +} -class pass_convert_switch : public gimple_opt_pass +/* Destructor. */ + +group_cluster::~group_cluster () { -public: - pass_convert_switch (gcc::context *ctxt) - : gimple_opt_pass (pass_data_convert_switch, ctxt) - {} + for (unsigned i = 0; i < m_cases.length (); i++) + delete m_cases[i]; - /* opt_pass methods: */ - virtual bool gate (function *) { return flag_tree_switch_conversion != 0; } - virtual unsigned int execute (function *); + m_cases.release (); +} -}; // class pass_convert_switch +/* Dump content of a cluster. */ -unsigned int -pass_convert_switch::execute (function *fun) +void +group_cluster::dump (FILE *f, bool details) { - basic_block bb; - bool cfg_altered = false; - - FOR_EACH_BB_FN (bb, fun) - { - gimple *stmt = last_stmt (bb); - if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) - { - if (dump_file) - { - expanded_location loc = expand_location (gimple_location (stmt)); + 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 ()); - 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); - } + unsigned comparison_count = 0; + for (unsigned i = 0; i < m_cases.length (); i++) + { + simple_cluster *sc = static_cast (m_cases[i]); + comparison_count += sc->m_range_p ? 2 : 1; + } - switch_conversion sconv; - sconv.expand (as_a (stmt)); - cfg_altered |= sconv.m_cfg_altered; - if (!sconv.m_reason) - { - if (dump_file) - { - fputs ("Switch converted\n", dump_file); - fputs ("--------------------------------\n", dump_file); - } + unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ()); + fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT"); - /* Make no effort to update the post-dominator tree. - It is actually not that hard for the transformations - we have performed, but it is not supported - by iterate_fix_dominators. */ - free_dominance_info (CDI_POST_DOMINATORS); - } - else - { - if (dump_file) - { - fputs ("Bailing out - ", dump_file); - fputs (sconv.m_reason, dump_file); - fputs ("\n--------------------------------\n", dump_file); - } - } - } - } + 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); - return cfg_altered ? TODO_cleanup_cfg : 0;; + fprintf (f, ":"); + PRINT_CASE (f, get_low ()); + fprintf (f, "-"); + PRINT_CASE (f, get_high ()); + fprintf (f, " "); } -} // anon namespace +/* Emit GIMPLE code to handle the cluster. */ -gimple_opt_pass * -make_pass_convert_switch (gcc::context *ctxt) +void +jump_table_cluster::emit (tree index_expr, tree, + tree default_label_expr, basic_block default_bb) { - return new pass_convert_switch (ctxt); + /* For jump table we just emit a new gswitch statement that will + be latter lowered to jump table. */ + auto_vec labels; + labels.create (m_cases.length ()); + + make_edge (m_case_bb, default_bb, 0); + for (unsigned i = 0; i < m_cases.length (); i++) + { + labels.quick_push (unshare_expr (m_cases[i]->m_case_label_expr)); + make_edge (m_case_bb, m_cases[i]->m_case_bb, 0); + } + + gswitch *s = gimple_build_switch (index_expr, + unshare_expr (default_label_expr), labels); + gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb); + gsi_insert_after (&gsi, s, GSI_NEW_STMT); } -struct case_node +/* 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) { - case_node *left; /* Left son in binary tree. */ - case_node *right; /* Right son in binary tree; - also node chain. */ - case_node *parent; /* Parent of node in binary tree. */ - tree low; /* Lowest index value for this label. */ - tree high; /* Highest index value for this label. */ - basic_block case_bb; /* Label to jump to when node matches. */ - tree case_label; /* Label to jump to when node matches. */ - profile_probability prob; /* Probability of taking this case. */ - profile_probability subtree_prob; /* Probability of reaching subtree - rooted at this node. */ -}; + /* 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. -typedef case_node *case_node_ptr; + 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. -static basic_block emit_case_nodes (basic_block, tree, case_node_ptr, - basic_block, tree, profile_probability, - tree, hash_map *); + The definition of "much bigger" depends on whether we are + optimizing for size or for speed. If the former, the maximum + ratio range/count = 3, because this was found to be the optimal + ratio for size on i686-pc-linux-gnu, see PR11823. The ratio + 10 is much older, and was probably selected after an extensive + benchmarking investigation on numerous platforms. Or maybe it + just made sense to someone at some point in the history of GCC, + who knows... */ + if (!flag_jump_tables) + return false; -/* Return the smallest number of different values for which it is best to use a - jump-table instead of a tree of conditional branches. */ + unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 10; -static unsigned int -case_values_threshold (void) -{ - unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD); + unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), + clusters[end]->get_high ()); + /* Check overflow. */ + if (range == 0) + return false; - if (threshold == 0) - threshold = targetm.case_values_threshold (); + 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; + } - return threshold; + return range <= max_ratio * comparison_count; } -/* Reset the aux field of all outgoing edges of basic block BB. */ +/* Return true if cluster starting at START and ending at END (inclusive) + is profitable transformation. */ -static inline void -reset_out_edges_aux (basic_block bb) +bool +jump_table_cluster::is_beneficial (const vec &, + unsigned start, unsigned end) { - edge e; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->succs) - e->aux = (void *) 0; + return end - start + 1 >= case_values_threshold (); } -/* Compute the number of case labels that correspond to each outgoing edge of - STMT. Record this information in the aux field of the edge. */ +/* Return true when RANGE of case values with UNIQ labels + can build a bit test. */ -static inline void -compute_cases_per_edge (gswitch *stmt) +bool +bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range, + unsigned int uniq) { - basic_block bb = gimple_bb (stmt); - reset_out_edges_aux (bb); - int ncases = gimple_switch_num_labels (stmt); - for (int i = ncases - 1; i >= 1; --i) + /* 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) +{ + 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++) { - tree elt = gimple_switch_label (stmt, i); - tree lab = CASE_LABEL (elt); - basic_block case_bb = label_to_block_fn (cfun, lab); - edge case_edge = find_edge (bb, case_bb); - case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1); + simple_cluster *sc = static_cast (clusters[i]); + bitmap_set_bit (dest_bbs, sc->m_case_bb->index); } -} -/* Do the insertion of a case label into case_list. The labels are - fed to us in descending order from the sorted vector of case labels used - in the tree part of the middle end. So the list we construct is - sorted in ascending order. + return can_be_handled (range, bitmap_count_bits (dest_bbs)); +} - LABEL is the case label to be inserted. LOW and HIGH are the bounds - against which the index is compared to jump to LABEL and PROB is the - estimated probability LABEL is reached from the switch statement. */ +/* Return true when COUNT of cases of UNIQ labels is beneficial for bit test + transformation. */ -static case_node * -add_case_node (case_node *head, tree low, tree high, basic_block case_bb, - tree case_label, profile_probability prob, - object_allocator &case_node_pool) +bool +bit_test_cluster::is_beneficial (unsigned count, unsigned uniq) { - case_node *r; - - gcc_checking_assert (low); - gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high))); - - /* Add this label to the chain. */ - r = case_node_pool.allocate (); - r->low = low; - r->high = high; - r->case_bb = case_bb; - r->case_label = case_label; - r->parent = r->left = NULL; - r->prob = prob; - r->subtree_prob = prob; - r->right = head; - return r; + return (((uniq == 1 && count >= 3) + || (uniq == 2 && count >= 5) + || (uniq == 3 && count >= 6))); } -/* Dump ROOT, a list or tree of case nodes, to file. */ +/* Return true if cluster starting at START and ending at END (inclusive) + is profitable transformation. */ -static void -dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level) +bool +bit_test_cluster::is_beneficial (const vec &clusters, + unsigned start, unsigned end) { - if (root == 0) - return; - indent_level++; - - dump_case_nodes (f, root->left, indent_step, indent_level); + auto_bitmap dest_bbs; - fputs (";; ", f); - fprintf (f, "%*s", indent_step * indent_level, ""); - print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low))); - if (!tree_int_cst_equal (root->low, root->high)) + for (unsigned i = start; i <= end; i++) { - fprintf (f, " ... "); - print_dec (wi::to_wide (root->high), f, - TYPE_SIGN (TREE_TYPE (root->high))); + simple_cluster *sc = static_cast (clusters[i]); + bitmap_set_bit (dest_bbs, sc->m_case_bb->index); } - fputs ("\n", f); - dump_case_nodes (f, root->right, indent_step, indent_level); + unsigned uniq = bitmap_count_bits (dest_bbs); + unsigned count = end - start + 1; + return is_beneficial (count, uniq); } -/* 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. +/* Comparison function for qsort to order bit tests by decreasing + probability of execution. */ - 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. */ +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->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. -static void -balance_case_nodes (case_node_ptr *head, case_node_ptr parent) + 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_node_ptr np; + struct case_bit_test test[m_max_case_bit_tests] = { {} }; + unsigned int i, j, k; + unsigned int count; - np = *head; - if (np) - { - int i = 0; - int ranges = 0; - case_node_ptr *npp; - case_node_ptr left; + tree unsigned_index_type = unsigned_type_for (index_type); - /* Count the number of entries on branch. Also count the ranges. */ + gimple_stmt_iterator gsi; + gassign *shift_stmt; - while (np) - { - if (!tree_int_cst_equal (np->low, np->high)) - ranges++; + 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); - i++; - np = np->right; - } + tree minval = get_low (); + tree maxval = get_high (); + tree range = int_const_binop (MINUS_EXPR, maxval, minval); - if (i > 2) + /* 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) { - /* Split this list if it is long enough for that to help. */ - npp = head; - left = *npp; + 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 = 1; + count++; + } + else + test[k].bits++; - /* If there are just three nodes, split at the middle one. */ - if (i == 3) - npp = &(*npp)->right; - else - { - /* Find the place in the list that bisects the list's total cost, - where ranges count as 2. - Here I gets half the total cost. */ - i = (i + ranges + 1) / 2; - while (1) - { - /* Skip nodes while their cost does not reach that amount. */ - if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) - i--; - i--; - if (i <= 0) - break; - npp = &(*npp)->right; - } - } - *head = np = *npp; - *npp = 0; - np->parent = parent; - np->left = left; + 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)); - /* Optimize each of the two split parts. */ - balance_case_nodes (&np->left, np); - balance_case_nodes (&np->right, np); - np->subtree_prob = np->prob; - np->subtree_prob += np->left->subtree_prob; - np->subtree_prob += np->right->subtree_prob; + 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); } - else + if (cost_diff > 0) { - /* Else leave this branch as one level, - but fill in `parent' fields. */ - np = *head; - np->parent = parent; - np->subtree_prob = np->prob; - for (; np->right; np = np->right) - { - np->right->parent = np; - (*head)->subtree_prob += np->right->subtree_prob; - } + for (i = 0; i < count; i++) + test[i].mask = wi::lshift (test[i].mask, m); + minval = build_zero_cst (TREE_TYPE (minval)); + range = maxval; } } -} -/* Return true if a switch should be expanded as a decision tree. - RANGE is the difference between highest and lowest case. - UNIQ is number of unique case node targets, not counting the default case. - COUNT is the number of comparisons needed, not counting the default case. */ + /* 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 (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); + 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); + + /* 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_bb); + gsi = gsi_last_bb (new_bb); + } -static bool -expand_switch_as_decision_tree_p (tree range, - unsigned int uniq ATTRIBUTE_UNUSED, - unsigned int count) -{ - int max_ratio; + /* We should have removed all edges now. */ + gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); - /* If neither casesi or tablejump is available, or flag_jump_tables - over-ruled us, we really have no choice. */ - if (!targetm.have_casesi () && !targetm.have_tablejump ()) - return true; - if (!flag_jump_tables) - return true; -#ifndef ASM_OUTPUT_ADDR_DIFF_ELT - if (flag_pic) - return true; -#endif + /* If nothing matched, go to the default label. */ + make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU); +} - /* 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. +/* 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. - 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. + 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 definition of "much bigger" depends on whether we are - optimizing for size or for speed. If the former, the maximum - ratio range/count = 3, because this was found to be the optimal - ratio for size on i686-pc-linux-gnu, see PR11823. The ratio - 10 is much older, and was probably selected after an extensive - benchmarking investigation on numerous platforms. Or maybe it - just made sense to someone at some point in the history of GCC, - who knows... */ - max_ratio = optimize_insn_for_size_p () ? 3 : 10; - if (count < case_values_threshold () || !tree_fits_uhwi_p (range) - || compare_tree_int (range, max_ratio * count) > 0) - return true; + The CFG is updated. The dominator tree will not be valid after + this transformation, but the immediate dominators are updated if + UPDATE_DOMINATORS is true. - return false; -} + Returns the newly created basic block. */ -static void -fix_phi_operands_for_edge (edge e, hash_map *phi_mapping) +basic_block +bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, + tree cond, basic_block case_bb) { - basic_block bb = e->dest; - gphi_iterator gsi; - for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gphi *phi = gsi.phi (); + tree tmp; + gcond *cond_stmt; + edge e_false; + basic_block new_bb, split_bb = gsi_bb (*gsip); - tree *definition = phi_mapping->get (gimple_phi_result (phi)); - if (definition) - add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION); - } -} + edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE); + 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); -/* Add an unconditional jump to CASE_BB that happens in basic block BB. */ + e_false = split_block (split_bb, cond_stmt); + new_bb = e_false->dest; + redirect_edge_pred (e_true, split_bb); -static void -emit_jump (basic_block bb, basic_block case_bb, - hash_map *phi_mapping) -{ - edge e = single_succ_edge (bb); - redirect_edge_succ (e, case_bb); - fix_phi_operands_for_edge (e, phi_mapping); + 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; } -/* Generate a decision tree, switching on INDEX_EXPR and jumping to - one of the labels in CASE_LIST or to the DEFAULT_LABEL. - DEFAULT_PROB is the estimated probability that it jumps to - DEFAULT_LABEL. +/* 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. */ - We generate a binary decision tree to select the appropriate target - code. */ +void +switch_decision_tree::compute_cases_per_edge () +{ + basic_block bb = gimple_bb (m_switch); + reset_out_edges_aux (); + int ncases = gimple_switch_num_labels (m_switch); + for (int i = ncases - 1; i >= 1; --i) + { + tree elt = gimple_switch_label (m_switch, i); + tree lab = CASE_LABEL (elt); + basic_block case_bb = label_to_block_fn (cfun, lab); + edge case_edge = find_edge (bb, case_bb); + case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1); + } +} + +/* Analyze switch statement and return true when the statement is expanded + as decision tree. */ -static void -emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type, - case_node_ptr case_list, basic_block default_bb, - tree default_label, profile_probability default_prob, - hash_map *phi_mapping) +bool +switch_decision_tree::analyze_switch_statement () { - balance_case_nodes (&case_list, NULL); + unsigned l = gimple_switch_num_labels (m_switch); + basic_block bb = gimple_bb (m_switch); + auto_vec clusters; + clusters.create (l - 1); + + tree default_label = CASE_LABEL (gimple_switch_default_label (m_switch)); + basic_block default_bb = label_to_block_fn (cfun, default_label); + 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_fn (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_bb, p)); + m_case_bbs.quick_push (case_bb); + } + + reset_out_edges_aux (); + + vec output; + output.create (1); + + /* Find whether the switch statement can be expanded with a method + different from decision tree. */ + unsigned end = clusters.length () - 1; + if (jump_table_cluster::can_be_handled (clusters, 0, end) + && jump_table_cluster::is_beneficial (clusters, 0, end)) + output.safe_push (new jump_table_cluster (clusters, 0, end)); + else if (bit_test_cluster::can_be_handled (clusters, 0, end) + && bit_test_cluster::is_beneficial (clusters, 0, end)) + output.safe_push (new bit_test_cluster (clusters, 0, end)); + else + output = clusters; 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"); - dump_case_nodes (dump_file, case_list, indent_step, 0); + fprintf (dump_file, ";; GIMPLE switch case clusters: "); + for (unsigned i = 0; i < output.length (); i++) + output[i]->dump (dump_file, dump_flags & TDF_DETAILS); + fprintf (dump_file, "\n"); + } + + bool expanded = try_switch_expansion (output); + + for (unsigned i = 0; i < output.length (); i++) + delete output[i]; + + return expanded; +} + +/* Attempt to expand CLUSTERS as a decision tree. Return true when + expanded. */ + +bool +switch_decision_tree::try_switch_expansion (vec &clusters) +{ + tree index_expr = gimple_switch_index (m_switch); + tree index_type = TREE_TYPE (index_expr); + basic_block bb = gimple_bb (m_switch); + + if (gimple_switch_num_labels (m_switch) == 1) + return false; + + /* Find the default case target label. */ + tree default_label_expr = CASE_LABEL (gimple_switch_default_label (m_switch)); + m_default_bb = label_to_block_fn (cfun, default_label_expr); + edge default_edge = find_edge (bb, m_default_bb); + + /* 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--) + { + case_tree_node *r = m_case_list; + m_case_list = m_case_node_pool.allocate (); + m_case_list->m_right = r; + m_case_list->m_c = clusters[i]; } - basic_block bb = gimple_bb (s); + record_phi_operand_mapping (); + + /* Split basic block that contains the gswitch statement. */ gimple_stmt_iterator gsi = gsi_last_bb (bb); edge e; if (gsi_end_p (gsi)) @@ -1399,27 +1561,49 @@ emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type, } bb = split_edge (e); - bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label, - default_prob, index_type, phi_mapping); + /* Create new basic blocks for non-case clusters where specific expansion + needs to happen. */ + for (unsigned i = 0; i < clusters.length (); i++) + if (clusters[i]->get_type () != SIMPLE_CASE) + { + clusters[i]->m_case_bb = create_empty_bb (bb); + clusters[i]->m_case_bb->loop_father = bb->loop_father; + } - if (bb) - emit_jump (bb, default_bb, phi_mapping); + /* Do not do an extra work for a single cluster. */ + if (clusters.length () == 1 + && clusters[0]->get_type () != SIMPLE_CASE) + clusters[0]->emit (index_expr, index_type, + gimple_switch_default_label (m_switch), m_default_bb); + else + { + emit (bb, index_expr, default_edge->probability, index_type); + + /* Emit cluster-specific switch handling. */ + for (unsigned i = 0; i < clusters.length (); i++) + if (clusters[i]->get_type () != SIMPLE_CASE) + clusters[i]->emit (index_expr, index_type, + gimple_switch_default_label (m_switch), + m_default_bb); + } - /* Remove all edges and do just an edge that will reach default_bb. */ - gsi = gsi_last_bb (gimple_bb (s)); - gsi_remove (&gsi, true); + fix_phi_operands_for_edges (); + + return true; } -static void -record_phi_operand_mapping (const vec bbs, basic_block switch_bb, - hash_map *map) +/* Before switch transformation, record all SSA_NAMEs defined in switch BB + and used in a label basic block. */ + +void +switch_decision_tree::record_phi_operand_mapping () { + basic_block switch_bb = gimple_bb (m_switch); /* Record all PHI nodes that have to be fixed after conversion. */ - for (unsigned i = 0; i < bbs.length (); i++) + for (unsigned i = 0; i < m_case_bbs.length (); i++) { - basic_block bb = bbs[i]; - gphi_iterator gsi; + basic_block bb = m_case_bbs[i]; for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); @@ -1431,7 +1615,7 @@ record_phi_operand_mapping (const vec bbs, basic_block switch_bb, { tree def = gimple_phi_arg_def (phi, i); tree result = gimple_phi_result (phi); - map->put (result, def); + m_phi_mapping.put (result, def); break; } } @@ -1439,133 +1623,365 @@ record_phi_operand_mapping (const vec bbs, basic_block switch_bb, } } -/* Attempt to expand gimple switch STMT to a decision tree. */ +/* Append new operands to PHI statements that were introduced due to + addition of new edges to case labels. */ -static bool -try_switch_expansion (gswitch *stmt) +void +switch_decision_tree::fix_phi_operands_for_edges () { - tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; - basic_block default_bb; - unsigned int count, uniq; - int i; - int ncases = gimple_switch_num_labels (stmt); - tree index_expr = gimple_switch_index (stmt); - tree index_type = TREE_TYPE (index_expr); - tree elt; - basic_block bb = gimple_bb (stmt); + gphi_iterator gsi; - hash_map phi_mapping; - auto_vec case_bbs; + for (unsigned i = 0; i < m_case_bbs.length (); i++) + { + basic_block bb = m_case_bbs[i]; + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + for (unsigned j = 0; j < gimple_phi_num_args (phi); j++) + { + tree def = gimple_phi_arg_def (phi, j); + if (def == NULL_TREE) + { + edge e = gimple_phi_arg_edge (phi, j); + tree *definition + = m_phi_mapping.get (gimple_phi_result (phi)); + gcc_assert (definition); + add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION); + } + } + } + } +} - /* A list of case labels; it is first built as a list and it may then - be rearranged into a nearly balanced binary tree. */ - case_node *case_list = 0; +/* Generate a decision tree, switching on INDEX_EXPR and jumping to + one of the labels in CASE_LIST or to the DEFAULT_LABEL. - /* A pool for case nodes. */ - object_allocator case_node_pool ("struct case_node pool"); + We generate a binary decision tree to select the appropriate target + code. */ - /* cleanup_tree_cfg removes all SWITCH_EXPR with their index - expressions being INTEGER_CST. */ - gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); +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); - if (ncases == 1) - return false; + 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); + } - /* Find the default case target label. */ - tree default_label = CASE_LABEL (gimple_switch_default_label (stmt)); - default_bb = label_to_block_fn (cfun, default_label); - edge default_edge = find_edge (bb, default_bb); - profile_probability default_prob = default_edge->probability; - case_bbs.safe_push (default_bb); - - /* Get upper and lower bounds of case values. */ - elt = gimple_switch_label (stmt, 1); - minval = fold_convert (index_type, CASE_LOW (elt)); - elt = gimple_switch_label (stmt, ncases - 1); - if (CASE_HIGH (elt)) - maxval = fold_convert (index_type, CASE_HIGH (elt)); - else - maxval = fold_convert (index_type, CASE_LOW (elt)); + bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type); - /* Compute span of values. */ - range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); + if (bb) + emit_jump (bb, m_default_bb); - /* Listify the labels queue and gather some numbers to decide - how to expand this switch. */ - uniq = 0; - count = 0; - hash_set seen_labels; - compute_cases_per_edge (stmt); + /* 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); - for (i = ncases - 1; i >= 1; --i) + delete_basic_block (bb); +} + +/* 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. + + 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. */ + +void +switch_decision_tree::balance_case_nodes (case_tree_node **head, + case_tree_node *parent) +{ + case_tree_node *np; + + np = *head; + if (np) { - elt = gimple_switch_label (stmt, i); - tree low = CASE_LOW (elt); - gcc_assert (low); - tree high = CASE_HIGH (elt); - gcc_assert (!high || tree_int_cst_lt (low, high)); - tree lab = CASE_LABEL (elt); + int i = 0; + int ranges = 0; + case_tree_node **npp; + case_tree_node *left; - /* Count the elements. - A range counts double, since it requires two compares. */ - count++; - if (high) - count++; - - /* If we have not seen this label yet, then increase the - number of unique case node targets seen. */ - if (!seen_labels.add (lab)) - uniq++; - - /* The bounds on the case range, LOW and HIGH, have to be converted - to case's index type TYPE. Note that the original type of the - case index in the source code is usually "lost" during - gimplification due to type promotion, but the case labels retain the - original type. Make sure to drop overflow flags. */ - low = fold_convert (index_type, low); - if (TREE_OVERFLOW (low)) - low = wide_int_to_tree (index_type, wi::to_wide (low)); - - /* The canonical from of a case label in GIMPLE is that a simple case - has an empty CASE_HIGH. For the casesi and tablejump expanders, - the back ends want simple cases to have high == low. */ - if (!high) - high = low; - high = fold_convert (index_type, high); - if (TREE_OVERFLOW (high)) - high = wide_int_to_tree (index_type, wi::to_wide (high)); + /* Count the number of entries on branch. Also count the ranges. */ - basic_block case_bb = label_to_block_fn (cfun, lab); - edge case_edge = find_edge (bb, case_bb); - case_list = add_case_node ( - case_list, low, high, case_bb, lab, - case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)), - case_node_pool); + while (np) + { + if (!tree_int_cst_equal (np->m_c->get_low (), np->m_c->get_high ())) + ranges++; - case_bbs.safe_push (case_bb); - } - reset_out_edges_aux (bb); - record_phi_operand_mapping (case_bbs, bb, &phi_mapping); + i++; + np = np->m_right; + } - /* cleanup_tree_cfg removes all SWITCH_EXPR with a single - destination, such as one with a default case only. - It also removes cases that are out of range for the switch - type, so we should never get a zero here. */ - gcc_assert (count > 0); + if (i > 2) + { + /* Split this list if it is long enough for that to help. */ + npp = head; + left = *npp; - /* Decide how to expand this switch. - The two options at this point are a dispatch table (casesi or - tablejump) or a decision tree. */ + /* If there are just three nodes, split at the middle one. */ + if (i == 3) + npp = &(*npp)->m_right; + else + { + /* Find the place in the list that bisects the list's total cost, + where ranges count as 2. + Here I gets half the total cost. */ + i = (i + ranges + 1) / 2; + while (1) + { + /* Skip nodes while their cost does not reach that amount. */ + if (!tree_int_cst_equal ((*npp)->m_c->get_low (), + (*npp)->m_c->get_high ())) + i--; + i--; + if (i <= 0) + break; + npp = &(*npp)->m_right; + } + } + *head = np = *npp; + *npp = 0; + np->m_parent = parent; + np->m_left = left; - if (expand_switch_as_decision_tree_p (range, uniq, count)) - { - emit_case_decision_tree (stmt, index_expr, index_type, case_list, - default_bb, default_label, default_prob, - &phi_mapping); - return true; + /* Optimize each of the two split parts. */ + balance_case_nodes (&np->m_left, np); + balance_case_nodes (&np->m_right, np); + np->m_c->m_subtree_prob = np->m_c->m_prob; + np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob; + np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob; + } + 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; + } + } } +} + +/* Dump ROOT, a list or tree of case nodes, to file. */ - return false; +void +switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root, + int indent_step, int indent_level) +{ + if (root == 0) + return; + indent_level++; + + dump_case_nodes (f, root->m_left, indent_step, indent_level); + + fputs (";; ", f); + fprintf (f, "%*s", indent_step * indent_level, ""); + root->m_c->dump (f); + root->m_c->m_prob.dump (f); + fputs ("\n", f); + + dump_case_nodes (f, root->m_right, indent_step, indent_level); +} + + +/* Add an unconditional jump to CASE_BB that happens in basic block BB. */ + +void +switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb) +{ + edge e = single_succ_edge (bb); + redirect_edge_succ (e, case_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) +{ + // TODO: it's once called with lhs != index. + op1 = fold_convert (TREE_TYPE (op0), op1); + + gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE); + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gsi_insert_after (&gsi, cond, GSI_NEW_STMT); + + gcc_assert (single_succ_p (bb)); + + /* Make a new basic block where false branch will take place. */ + edge false_edge = split_block (bb, cond); + false_edge->flags = EDGE_FALSE_VALUE; + false_edge->probability = prob.invert (); + + edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); + true_edge->probability = prob; + + return false_edge->dest; +} + +/* Emit step-by-step code to select a case for the value of INDEX. + The thus generated decision tree follows the form of the + case-node binary tree NODE, whose nodes represent test conditions. + 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) +{ + /* If node is null, we are done. */ + if (node == NULL) + return bb; + + /* Branch to a label where we will handle it later. */ + basic_block test_bb = split_edge (single_succ_edge (bb)); + redirect_edge_succ (single_pred_edge (test_bb), + single_succ_edge (bb)->dest); + + profile_probability probability + = (node->m_right + ? node->m_right->m_c->m_subtree_prob : profile_probability::never ()); + probability = ((probability + default_prob.apply_scale (1, 2)) + / (node->m_c->m_subtree_prob + default_prob)); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), GT_EXPR, + test_bb, probability); + default_prob = default_prob.apply_scale (1, 2); + + /* Value belongs to this node or to the left-hand subtree. */ + probability = node->m_c->m_prob / + (node->m_c->m_subtree_prob + default_prob); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), GE_EXPR, + node->m_c->m_case_bb, probability); + + /* Handle the left-hand subtree. */ + bb = emit_case_nodes (bb, index, node->m_left, + default_prob, index_type); + + /* If the left-hand subtree fell through, + don't let it fall into the right-hand subtree. */ + if (m_default_bb) + emit_jump (bb, m_default_bb); + + bb = emit_case_nodes (test_bb, index, node->m_right, + default_prob, index_type); + + return bb; +} + +/* The main function of the pass scans statements for switches and invokes + process_switch on them. */ + +namespace { + +const pass_data pass_data_convert_switch = +{ + GIMPLE_PASS, /* type */ + "switchconv", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_SWITCH_CONVERSION, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_update_ssa, /* todo_flags_finish */ +}; + +class pass_convert_switch : public gimple_opt_pass +{ +public: + pass_convert_switch (gcc::context *ctxt) + : gimple_opt_pass (pass_data_convert_switch, ctxt) + {} + + /* opt_pass methods: */ + virtual bool gate (function *) { return flag_tree_switch_conversion != 0; } + virtual unsigned int execute (function *); + +}; // class pass_convert_switch + +unsigned int +pass_convert_switch::execute (function *fun) +{ + basic_block bb; + bool cfg_altered = false; + + FOR_EACH_BB_FN (bb, fun) + { + gimple *stmt = last_stmt (bb); + if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) + { + if (dump_file) + { + expanded_location loc = expand_location (gimple_location (stmt)); + + 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); + } + + switch_conversion sconv; + sconv.expand (as_a (stmt)); + cfg_altered |= sconv.m_cfg_altered; + if (!sconv.m_reason) + { + if (dump_file) + { + fputs ("Switch converted\n", dump_file); + fputs ("--------------------------------\n", dump_file); + } + + /* Make no effort to update the post-dominator tree. + It is actually not that hard for the transformations + we have performed, but it is not supported + by iterate_fix_dominators. */ + free_dominance_info (CDI_POST_DOMINATORS); + } + else + { + if (dump_file) + { + fputs ("Bailing out - ", dump_file); + fputs (sconv.m_reason, dump_file); + fputs ("\n--------------------------------\n", dump_file); + } + } + } + } + + return cfg_altered ? TODO_cleanup_cfg : 0;; +} + +} // anon namespace + +gimple_opt_pass * +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 @@ -1614,23 +2030,35 @@ 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); if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) + switch_statements.safe_push (stmt); + } + + for (unsigned i = 0; i < switch_statements.length (); i++) + { + gimple *stmt = switch_statements[i]; + if (dump_file) { - if (dump_file) - { - expanded_location loc = expand_location (gimple_location (stmt)); + 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); - } + 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); + } - expanded |= try_switch_expansion (as_a (stmt)); + gswitch *swtch = dyn_cast (stmt); + if (swtch) + { + switch_decision_tree dt (swtch); + expanded |= dt.analyze_switch_statement (); } } @@ -1657,112 +2085,4 @@ make_pass_lower_switch (gcc::context *ctxt) return new pass_lower_switch (ctxt); } -/* Generate code to compare X with Y so that the condition codes are - set and to jump to LABEL if the condition is true. If X is a - constant and Y is not a constant, then the comparison is swapped to - ensure that the comparison RTL has the canonical form. - UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they - need to be widened. UNSIGNEDP is also used to select the proper - branch condition code. - - If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y. - - MODE is the mode of the inputs (in case they are const_int). - - COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.). - It will be potentially converted into an unsigned variant based on - UNSIGNEDP to select a proper jump instruction. - - PROB is the probability of jumping to LABEL. */ - -static basic_block -emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1, - tree_code comparison, basic_block label_bb, - profile_probability prob, - hash_map *phi_mapping) -{ - gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE); - gimple_stmt_iterator gsi = gsi_last_bb (bb); - gsi_insert_after (&gsi, cond, GSI_NEW_STMT); - - gcc_assert (single_succ_p (bb)); - - /* Make a new basic block where false branch will take place. */ - edge false_edge = split_block (bb, cond); - false_edge->flags = EDGE_FALSE_VALUE; - false_edge->probability = prob.invert (); - - edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); - fix_phi_operands_for_edge (true_edge, phi_mapping); - true_edge->probability = prob; - - return false_edge->dest; -} - -/* Computes the conditional probability of jumping to a target if the branch - instruction is executed. - TARGET_PROB is the estimated probability of jumping to a target relative - to some basic block BB. - BASE_PROB is the probability of reaching the branch instruction relative - to the same basic block BB. */ - -static inline profile_probability -conditional_probability (profile_probability target_prob, - profile_probability base_prob) -{ - return target_prob / base_prob; -} - -/* Emit step-by-step code to select a case for the value of INDEX. - The thus generated decision tree follows the form of the - case-node binary tree NODE, whose nodes represent test conditions. - INDEX_TYPE is the type of the index of the switch. */ - -static basic_block -emit_case_nodes (basic_block bb, tree index, case_node_ptr node, - basic_block default_bb, tree default_label, - profile_probability default_prob, tree index_type, - hash_map *phi_mapping) -{ - /* If node is null, we are done. */ - if (node == NULL) - return bb; - - /* Branch to a label where we will handle it later. */ - basic_block test_bb = split_edge (single_succ_edge (bb)); - redirect_edge_succ (single_pred_edge (test_bb), - single_succ_edge (bb)->dest); - - profile_probability probability - = node->right ? node->right->subtree_prob : profile_probability::never (); - probability - = conditional_probability (probability + default_prob.apply_scale (1, 2), - node->subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, - test_bb, probability, phi_mapping); - default_prob = default_prob.apply_scale (1, 2); - - /* Value belongs to this node or to the left-hand subtree. */ - probability - = conditional_probability (node->prob, node->subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR, - node->case_bb, probability, - phi_mapping); - - /* Handle the left-hand subtree. */ - bb = emit_case_nodes (bb, index, node->left, default_bb, - default_label, default_prob, index_type, - phi_mapping); - - /* If the left-hand subtree fell through, - don't let it fall into the right-hand subtree. */ - if (default_bb) - emit_jump (bb, default_bb, phi_mapping); - - bb = emit_case_nodes (test_bb, index, node->right, default_bb, - default_label, default_prob, index_type, - phi_mapping); - - return bb; -} diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index 4518c2ed23a..946077c25ec 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -22,6 +22,536 @@ along with GCC; see the file COPYING3. If not see namespace tree_switch_conversion { +/* Type of cluster. */ + +enum cluster_type +{ + SIMPLE_CASE, + JUMP_TABLE, + BIT_TEST +}; + +#define PRINT_CASE(f,c) print_generic_expr (f, c) + +/* Abstract base class for representing a cluster of cases. */ + +struct cluster +{ + /* Constructor. */ + cluster (tree case_label_expr, basic_block case_bb, profile_probability prob, + profile_probability subtree_prob); + + /* Destructor. */ + virtual ~cluster () + {} + + /* Return type. */ + virtual cluster_type get_type () = 0; + + /* Get low value covered by a cluster. */ + virtual tree get_low () = 0; + + /* Get high value covered by a cluster. */ + virtual tree get_high () = 0; + + /* Debug content of a cluster. */ + virtual void debug () = 0; + + /* Dump content of a cluster. */ + virtual void dump (FILE *f, bool details = false) = 0; + + /* Emit GIMPLE code to handle the cluster. */ + virtual void emit (tree, tree, tree, basic_block) = 0; + + /* Return range of a cluster. If value would overflow in type of LOW, + then return 0. */ + static unsigned HOST_WIDE_INT get_range (tree low, tree high) + { + tree r = fold_build2 (MINUS_EXPR, TREE_TYPE (low), high, low); + if (!tree_fits_uhwi_p (r)) + return 0; + + return tree_to_uhwi (r) + 1; + } + + /* Case label. */ + tree m_case_label_expr; + + /* Basic block of the case. */ + basic_block m_case_bb; + + /* Probability of taking this cluster. */ + profile_probability m_prob; + + /* Probability of reaching subtree rooted at this node. */ + profile_probability m_subtree_prob; + +protected: + /* Default constructor. */ + cluster () {} +}; + +cluster::cluster (tree case_label_expr, basic_block case_bb, + profile_probability prob, profile_probability subtree_prob): + m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob), + m_subtree_prob (subtree_prob) +{ +} + +/* Subclass of cluster representing a simple contiguous range + from [low..high]. */ + +struct simple_cluster: public cluster +{ + /* Constructor. */ + simple_cluster (tree low, tree high, tree case_label_expr, + basic_block case_bb, profile_probability prob); + + /* Destructor. */ + ~simple_cluster () + {} + + cluster_type + get_type () + { + return SIMPLE_CASE; + } + + tree + get_low () + { + return m_low; + } + + tree + get_high () + { + return m_high; + } + + void + debug () + { + dump (stderr); + } + + void + dump (FILE *f, bool details ATTRIBUTE_UNUSED = false) + { + PRINT_CASE (f, get_low ()); + if (get_low () != get_high ()) + { + fprintf (f, "-"); + PRINT_CASE (f, get_high ()); + } + fprintf (f, " "); + } + + void emit (tree, tree, tree, basic_block) + { + gcc_unreachable (); + } + + /* Low value of the case. */ + tree m_low; + + /* High value of the case. */ + tree m_high; + + /* True if case is a range. */ + bool m_range_p; +}; + +simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr, + basic_block case_bb, profile_probability prob): + cluster (case_label_expr, case_bb, prob, prob), + m_low (low), m_high (high) +{ + m_range_p = m_high != NULL; + if (m_high == NULL) + m_high = m_low; +} + +/* Abstract subclass of jump table and bit test cluster, + handling a collection of simple_cluster instances. */ + +struct group_cluster: public cluster +{ + /* Constructor. */ + group_cluster (vec &clusters, unsigned start, unsigned end); + + /* Destructor. */ + ~group_cluster (); + + tree + get_low () + { + return m_cases[0]->get_low (); + } + + tree + get_high () + { + return m_cases[m_cases.length () - 1]->get_high (); + } + + void + debug () + { + dump (stderr); + } + + void dump (FILE *f, bool details = false); + + /* List of simple clusters handled by the group. */ + vec m_cases; +}; + +/* Concrete subclass of group_cluster representing a collection + of cases to be implemented as a jump table. + The "emit" vfunc gernerates a nested switch statement which + is later lowered to a jump table. */ + +struct jump_table_cluster: public group_cluster +{ + /* Constructor. */ + jump_table_cluster (vec &clusters, unsigned start, unsigned end) + : group_cluster (clusters, start, end) + {} + + cluster_type + get_type () + { + return JUMP_TABLE; + } + + void emit (tree index_expr, tree index_type, + tree default_label_expr, basic_block default_bb); + + /* Return true when cluster starting at START and ending at END (inclusive) + can build a jump-table. */ + static bool can_be_handled (const vec &clusters, unsigned start, + unsigned end); + + /* Return true if cluster starting at START and ending at END (inclusive) + is profitable transformation. */ + static bool is_beneficial (const vec &clusters, unsigned start, + unsigned end); + + /* Return the smallest number of different values for which it is best + to use a jump-table instead of a tree of conditional branches. */ + static inline unsigned int case_values_threshold (void); +}; + +/* 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< + + 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 +*/ + +struct bit_test_cluster: public group_cluster +{ + /* Constructor. */ + bit_test_cluster (vec &clusters, unsigned start, unsigned end) + :group_cluster (clusters, start, end) + {} + + cluster_type + get_type () + { + return BIT_TEST; + } + +/* 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 emit (tree index_expr, tree index_type, + tree default_label_expr, basic_block default_bb); + + /* Return true when RANGE of case values with UNIQ labels + can build a bit test. */ + static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq); + + /* Return true when cluster starting at START and ending at END (inclusive) + can build a bit test. */ + static bool can_be_handled (const vec &clusters, unsigned start, + unsigned end); + + /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test + transformation. */ + static bool is_beneficial (unsigned count, unsigned uniq); + + /* Return true if cluster starting at START and ending at END (inclusive) + is profitable transformation. */ + static bool is_beneficial (const vec &clusters, unsigned start, + unsigned end); + +/* 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. */ + static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, + tree cond, + basic_block case_bb); + + /* Maximum number of different basic blocks that can be handled by + a bit test. */ + static const int m_max_case_bit_tests = 3; +}; + +/* Helper struct to find minimal clusters. */ + +struct min_cluster_item +{ + /* Constructor. */ + min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases): + m_count (count), m_start (start), m_non_jt_cases (non_jt_cases) + {} + + /* Count of clusters. */ + unsigned m_count; + + /* Index where is cluster boundary. */ + unsigned m_start; + + /* Total number of cases that will not be in a jump table. */ + unsigned m_non_jt_cases; +}; + +/* Helper struct to represent switch decision tree. */ + +struct case_tree_node +{ + /* Empty Constructor. */ + case_tree_node (); + + /* Left son in binary tree. */ + case_tree_node *m_left; + + /* Right son in binary tree; also node chain. */ + case_tree_node *m_right; + + /* Parent of node in binary tree. */ + case_tree_node *m_parent; + + /* Cluster represented by this tree node. */ + cluster *m_c; +}; + +inline +case_tree_node::case_tree_node (): + m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL) +{ +} + +unsigned int +jump_table_cluster::case_values_threshold (void) +{ + unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD); + + if (threshold == 0) + threshold = targetm.case_values_threshold (); + + return threshold; +} + +/* 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; + basic_block target_bb; + tree label; + int bits; + + /* Comparison function for qsort to order bit tests by decreasing + probability of execution. */ + static int cmp (const void *p1, const void *p2); +}; + +struct switch_decision_tree +{ + /* Constructor. */ + switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (), + m_case_bbs (), m_case_node_pool ("struct case_node pool"), + m_case_list (NULL) + { + } + + /* Analyze switch statement and return true when the statement is expanded + as decision tree. */ + bool analyze_switch_statement (); + + /* Attempt to expand CLUSTERS as a decision tree. Return true when + expanded. */ + bool try_switch_expansion (vec &clusters); + + /* Reset the aux field of all outgoing edges of switch basic block. */ + inline void reset_out_edges_aux (); + + /* 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 compute_cases_per_edge (); + + /* Before switch transformation, record all SSA_NAMEs defined in switch BB + and used in a label basic block. */ + void record_phi_operand_mapping (); + + /* Append new operands to PHI statements that were introduced due to + addition of new edges to case labels. */ + void fix_phi_operands_for_edges (); + + /* Generate a decision tree, switching on INDEX_EXPR and jumping to + one of the labels in CASE_LIST or to the DEFAULT_LABEL. + + We generate a binary decision tree to select the appropriate target + code. */ + void emit (basic_block bb, tree index_expr, + profile_probability default_prob, tree index_type); + + /* 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 emit_case_nodes (basic_block bb, tree index, + case_tree_node *node, + profile_probability default_prob, + tree index_type); + + /* 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. + + 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. */ + static void balance_case_nodes (case_tree_node **head, + case_tree_node *parent); + + /* Dump ROOT, a list or tree of case nodes, to file F. */ + static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step, + int indent_level); + + /* Add an unconditional jump to CASE_BB that happens in basic block BB. */ + static void emit_jump (basic_block bb, basic_block case_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. */ + static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0, + tree op1, tree_code comparison, + basic_block label_bb, + profile_probability prob); + + /* Switch statement. */ + gswitch *m_switch; + + /* Map of PHI nodes that have to be fixed after expansion. */ + hash_map m_phi_mapping; + + /* List of basic blocks that belong to labels of the switch. */ + auto_vec m_case_bbs; + + /* Basic block with default label. */ + basic_block m_default_bb; + + /* A pool for case nodes. */ + object_allocator m_case_node_pool; + + /* Balanced tree of case nodes. */ + case_tree_node *m_case_list; +}; + /* Switch initialization conversion @@ -254,6 +784,9 @@ struct switch_conversion labels. */ bool m_default_case_nonstandard; + /* Number of uniq labels for non-default edges. */ + unsigned int m_uniq; + /* Count is number of non-default edges. */ unsigned int m_count; @@ -261,6 +794,16 @@ struct switch_conversion bool m_cfg_altered; }; +void +switch_decision_tree::reset_out_edges_aux () +{ + basic_block bb = gimple_bb (m_switch); + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->succs) + e->aux = (void *) 0; +} + } // tree_switch_conversion namespace #endif // TREE_SWITCH_CONVERSION_H -- 2.30.2