gcc/ChangeLog:
2018-06-07 Martin Liska <mli...@suse.cz>
* 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.
gcc/testsuite/ChangeLog:
2018-06-07 Martin Liska <mli...@suse.cz>
* gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL.
---
gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 2 +-
gcc/tree-switch-conversion.c | 1343 ++++++++++++++----------
gcc/tree-switch-conversion.h | 545 ++++++++++
3 files changed, 1325 insertions(+), 565 deletions(-)
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 2f848fcb6aa..8f3dc8fd8a4 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -175,6 +175,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;
}
bool
@@ -861,6 +866,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)
{
@@ -909,409 +930,481 @@ 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 {
-
-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
+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 *);
-
-}; // class pass_convert_switch
+ m_cases.release ();
+}
-unsigned int
-pass_convert_switch::execute (function *fun)
+group_cluster::group_cluster (vec<cluster *> &clusters,
+ unsigned start, unsigned end)
{
- basic_block bb;
- bool cfg_altered = false;
+ 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<simple_cluster *> (clusters[i]));
+ m_prob += clusters[i]->m_prob;
+ }
+ m_subtree_prob = m_prob;
+}
- 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));
+void
+group_cluster::dump (FILE *f, bool details)
+{
+ unsigned total_values = 0;
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
+ m_cases[i]->get_high ());
- 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<simple_cluster *> (m_cases[i]);
+ comparison_count += sc->m_range_p ? 2 : 1;
+ }
- switch_conversion sconv;
- sconv.expand (as_a <gswitch *> (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
-
-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 <tree> 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
+bool
+jump_table_cluster::can_be_handled (const vec<cluster *> &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<tree, tree> *);
+ 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<simple_cluster *> (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. */
-
-static inline void
-reset_out_edges_aux (basic_block bb)
+bool
+jump_table_cluster::is_beneficial (const vec<cluster *> &,
+ 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. */
+bool
+bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
+ unsigned int uniq)
+{
+ /* Check overflow. */
+ if (range == 0)
+ return 0;
+
+ if (range >= GET_MODE_BITSIZE (word_mode))
+ return false;
+
+ return uniq <= 3;
+}
-static inline void
-compute_cases_per_edge (gswitch *stmt)
+bool
+bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
+ unsigned start, unsigned end)
{
- 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)
+ 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<simple_cluster *> (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.
- 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 can_be_handled (range, bitmap_count_bits (dest_bbs));
+}
-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> &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. */
-
-static void
-dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
+bool
+bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
+ unsigned start, unsigned end)
{
- if (root == 0)
- return;
- indent_level++;
+ auto_bitmap dest_bbs;
- dump_case_nodes (f, root->left, indent_step, indent_level);
-
- 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<simple_cluster *> (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.
+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;
- 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. */
+ /* Stabilize the sort. */
+ return (LABEL_DECL_UID (CASE_LABEL (d2->label))
+ - LABEL_DECL_UID (CASE_LABEL (d1->label)));
+}
-static void
-balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
+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<simple_cluster *> (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);
+ }
+
+ /* We should have removed all edges now. */
+ gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
-static bool
-expand_switch_as_decision_tree_p (tree range,
- unsigned int uniq ATTRIBUTE_UNUSED,
- unsigned int count)
+ /* If nothing matched, go to the default label. */
+ make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
+}
+
+basic_block
+bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
+ tree cond, basic_block case_bb)
{
- int max_ratio;
+ tree tmp;
+ gcond *cond_stmt;
+ edge e_false;
+ basic_block new_bb, split_bb = gsi_bb (*gsip);
- /* 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
+ edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
+ gcc_assert (e_true->src == split_bb);
- /* 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.
+ 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);
- 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.
+ e_false = split_block (split_bb, cond_stmt);
+ new_bb = e_false->dest;
+ redirect_edge_pred (e_true, split_bb);
- 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;
+ 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 false;
+ return new_bb;
}
-static void
-fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
+
+void
+switch_decision_tree::compute_cases_per_edge ()
{
- basic_block bb = e->dest;
- gphi_iterator gsi;
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ 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)
{
- gphi *phi = gsi.phi ();
-
- tree *definition = phi_mapping->get (gimple_phi_result (phi));
- if (definition)
- add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
+ 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);
}
}
-
-/* Add an unconditional jump to CASE_BB that happens in basic block BB. */
-
-static void
-emit_jump (basic_block bb, basic_block case_bb,
- hash_map<tree, tree> *phi_mapping)
+bool
+switch_decision_tree::analyze_switch_statement ()
{
- edge e = single_succ_edge (bb);
- redirect_edge_succ (e, case_bb);
- fix_phi_operands_for_edge (e, phi_mapping);
-}
+ unsigned l = gimple_switch_num_labels (m_switch);
+ basic_block bb = gimple_bb (m_switch);
+ auto_vec<cluster *> clusters;
+ clusters.create (l - 1);
-/* 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.
+ 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);
- We generate a binary decision tree to select the appropriate target
- code. */
-
-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<tree, tree> *phi_mapping)
-{
- balance_case_nodes (&case_list, NULL);
+ compute_cases_per_edge ();
- if (dump_file)
- dump_function_to_file (current_function_decl, dump_file, dump_flags);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ for (unsigned i = 1; i < l; i++)
{
- int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
- fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
- dump_case_nodes (dump_file, case_list, indent_step, 0);
+ 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<cluster *> 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)
+ {
+ 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;
+}
+
+bool
+switch_decision_tree::try_switch_expansion (vec<cluster *> &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))
@@ -1323,27 +1416,46 @@ 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;
+ }
+
+ /* 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);
+ }
- if (bb)
- emit_jump (bb, default_bb, phi_mapping);
+ fix_phi_operands_for_edges ();
- /* Remove all edges and do just an edge that will reach default_bb. */
- gsi = gsi_last_bb (gimple_bb (s));
- gsi_remove (&gsi, true);
+ return true;
}
-static void
-record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
- hash_map <tree, tree> *map)
+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 ();
@@ -1355,7 +1467,7 @@ record_phi_operand_mapping (const vec<basic_block> 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;
}
}
@@ -1363,133 +1475,332 @@ record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
}
}
-/* Attempt to expand gimple switch STMT to a decision tree. */
-
-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<tree, tree> phi_mapping;
- auto_vec<basic_block> 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;
+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);
- /* A pool for case nodes. */
- object_allocator<case_node> case_node_pool ("struct case_node pool");
+ 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);
+ }
- /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
- expressions being INTEGER_CST. */
- gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+ bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type);
- if (ncases == 1)
- return false;
+ if (bb)
+ emit_jump (bb, m_default_bb);
- /* 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));
+ /* 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);
- /* Compute span of values. */
- range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
+ delete_basic_block (bb);
+}
- /* Listify the labels queue and gather some numbers to decide
- how to expand this switch. */
- uniq = 0;
- count = 0;
- hash_set<tree> seen_labels;
- compute_cases_per_edge (stmt);
+void
+switch_decision_tree::balance_case_nodes (case_tree_node **head,
+ case_tree_node *parent)
+{
+ case_tree_node *np;
- for (i = ncases - 1; i >= 1; --i)
+ 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. */
+
+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);
+}
+
+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);
+}
+
+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;
+}
+
+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);
- return false;
+ /* 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 <gswitch *> (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
@@ -1538,23 +1849,35 @@ pass_lower_switch<O0>::execute (function *fun)
basic_block bb;
bool expanded = false;
+ auto_vec<gimple *> 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<gswitch *> (stmt));
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+ if (swtch)
+ {
+ switch_decision_tree dt (swtch);
+ expanded |= dt.analyze_switch_statement ();
}
}
@@ -1581,112 +1904,4 @@ make_pass_lower_switch (gcc::context *ctxt)
return new pass_lower_switch<false> (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<tree, tree> *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<tree, tree> *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 297faec119f..54dd2c34ee8 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -22,6 +22,538 @@ 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<cluster *> &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<simple_cluster *> 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<cluster *> &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<cluster *> &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<cluster *> &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<<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
+*/
+
+struct bit_test_cluster: public group_cluster
+{
+ /* Constructor. */
+ bit_test_cluster (vec<cluster *> &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<cluster *> &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<cluster *> &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<cluster *> &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<tree, tree> m_phi_mapping;
+
+ /* List of basic blocks that belong to labels of the switch. */
+ auto_vec<basic_block> m_case_bbs;
+
+ /* Basic block with default label. */
+ basic_block m_default_bb;
+
+ /* A pool for case nodes. */
+ object_allocator<case_tree_node> m_case_node_pool;
+
+ /* Balanced tree of case nodes. */
+ case_tree_node *m_case_list;
+};
+
/*
Switch initialization conversion
@@ -271,6 +803,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;
@@ -278,6 +813,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
