From 27f5901b340e73900ef992470aa52b51ccfb86b9 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Mon, 31 Jul 2017 14:01:53 +0200
Subject: [PATCH] Make expansion of balanced binary trees of switches on tree
level.
gcc/ChangeLog:
2017-07-31 Martin Liska <mliska@suse.cz>
* passes.def: Include pass_lower_switch.
* stmt.c (dump_case_nodes): Remove and move to
tree-switch-conversion.
(case_values_threshold): Likewise.
(expand_switch_as_decision_tree_p): Likewise.
(emit_case_decision_tree): Likewise.
(expand_case): Likewise.
(balance_case_nodes): Likewise.
(node_has_low_bound): Likewise.
(node_has_high_bound): Likewise.
(node_is_bounded): Likewise.
(emit_case_nodes): Likewise.
* timevar.def: Add TV_TREE_SWITCH_LOWERING.
* tree-pass.h: Add make_pass_lower_switch.
gcc/testsuite/ChangeLog:
2017-07-31 Martin Liska <mliska@suse.cz>
* gcc.dg/tree-prof/update-loopch.c: Scan patterns in
switchlower.
* gcc.dg/tree-ssa/vrp104.c: Likewise.
---
gcc/passes.def | 1 +
gcc/stmt.c | 861 -----------------
gcc/testsuite/gcc.dg/tree-prof/update-loopch.c | 10 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 2 +-
gcc/timevar.def | 1 +
gcc/tree-pass.h | 1 +
gcc/tree-switch-conversion.c | 1178 ++++++++++++++++++++++++
7 files changed, 1187 insertions(+), 867 deletions(-)
@@ -394,6 +394,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_lower_vaarg);
NEXT_PASS (pass_lower_vector);
NEXT_PASS (pass_lower_complex_O0);
+ NEXT_PASS (pass_lower_switch);
NEXT_PASS (pass_sancov_O0);
NEXT_PASS (pass_asan_O0);
NEXT_PASS (pass_tsan_O0);
@@ -104,12 +104,6 @@ extern basic_block label_to_block_fn (struct function *, tree);
static bool check_unique_operand_names (tree, tree, tree);
static char *resolve_operand_name_1 (char *, tree, tree, tree);
-static void balance_case_nodes (case_node_ptr *, case_node_ptr);
-static int node_has_low_bound (case_node_ptr, tree);
-static int node_has_high_bound (case_node_ptr, tree);
-static int node_is_bounded (case_node_ptr, tree);
-static void emit_case_nodes (rtx, case_node_ptr, rtx_code_label *,
- profile_probability, tree);
/* Return the rtx-label that corresponds to a LABEL_DECL,
creating it if necessary. */
@@ -742,164 +736,6 @@ add_case_node (struct case_node *head, tree low, tree high,
return r;
}
-/* Dump ROOT, a list or tree of case nodes, to file. */
-
-static void
-dump_case_nodes (FILE *f, struct case_node *root,
- int indent_step, int indent_level)
-{
- if (root == 0)
- return;
- indent_level++;
-
- dump_case_nodes (f, root->left, indent_step, indent_level);
-
- fputs (";; ", f);
- fprintf (f, "%*s", indent_step * indent_level, "");
- print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
- if (!tree_int_cst_equal (root->low, root->high))
- {
- fprintf (f, " ... ");
- print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
- }
- fputs ("\n", f);
-
- dump_case_nodes (f, root->right, indent_step, indent_level);
-}
-
-/* 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 unsigned int
-case_values_threshold (void)
-{
- unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
-
- if (threshold == 0)
- threshold = targetm.case_values_threshold ();
-
- return threshold;
-}
-
-/* Return true if a switch should be expanded as a decision tree.
- RANGE is the difference between highest and lowest case.
- UNIQ is number of unique case node targets, not counting the default case.
- COUNT is the number of comparisons needed, not counting the default case. */
-
-static bool
-expand_switch_as_decision_tree_p (tree range,
- unsigned int uniq ATTRIBUTE_UNUSED,
- unsigned int count)
-{
- int max_ratio;
-
- /* If neither casesi or tablejump is available, or flag_jump_tables
- over-ruled us, we really have no choice. */
- if (!targetm.have_casesi () && !targetm.have_tablejump ())
- return true;
- if (!flag_jump_tables)
- return true;
-#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
- if (flag_pic)
- return true;
-#endif
-
- /* If the switch is relatively small such that the cost of one
- indirect jump on the target are higher than the cost of a
- decision tree, go with the decision tree.
-
- If range of values is much bigger than number of values,
- or if it is too large to represent in a HOST_WIDE_INT,
- make a sequence of conditional branches instead of a dispatch.
-
- The definition of "much bigger" depends on whether we are
- optimizing for size or for speed. 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;
-
- return false;
-}
-
-/* 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.
-
- We generate a binary decision tree to select the appropriate target
- code. This is done as follows:
-
- If the index is a short or char that we do not have
- an insn to handle comparisons directly, convert it to
- a full integer now, rather than letting each comparison
- generate the conversion.
-
- Load the index into a register.
-
- The list of cases is rearranged into a binary tree,
- nearly optimal assuming equal probability for each case.
-
- The tree is transformed into RTL, eliminating redundant
- test conditions at the same time.
-
- If program flow could reach the end of the decision tree
- an unconditional jump to the default code is emitted.
-
- The above process is unaware of the CFG. The caller has to fix up
- the CFG itself. This is done in cfgexpand.c. */
-
-static void
-emit_case_decision_tree (tree index_expr, tree index_type,
- case_node_ptr case_list, rtx_code_label *default_label,
- profile_probability default_prob)
-{
- rtx index = expand_normal (index_expr);
-
- if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
- && ! have_insn_for (COMPARE, GET_MODE (index)))
- {
- int unsignedp = TYPE_UNSIGNED (index_type);
- machine_mode wider_mode;
- for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
- wider_mode = GET_MODE_WIDER_MODE (wider_mode))
- if (have_insn_for (COMPARE, wider_mode))
- {
- index = convert_to_mode (wider_mode, index, unsignedp);
- break;
- }
- }
-
- do_pending_stack_adjust ();
-
- if (MEM_P (index))
- {
- index = copy_to_reg (index);
- if (TREE_CODE (index_expr) == SSA_NAME)
- set_reg_attrs_for_decl_rtl (index_expr, index);
- }
-
- balance_case_nodes (&case_list, NULL);
-
- 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);
- }
-
- emit_case_nodes (index, case_list, default_label, default_prob, index_type);
- if (default_label)
- emit_jump (default_label);
-}
-
/* Return the sum of probabilities of outgoing edges of basic block BB. */
static profile_probability
@@ -1150,7 +986,6 @@ expand_case (gswitch *stmt)
default_label = jump_target_rtx
(CASE_LABEL (gimple_switch_default_label (stmt)));
edge default_edge = EDGE_SUCC (bb, 0);
- profile_probability default_prob = default_edge->probability;
/* Get upper and lower bounds of case values. */
elt = gimple_switch_label (stmt, 1);
@@ -1230,11 +1065,6 @@ expand_case (gswitch *stmt)
The two options at this point are a dispatch table (casesi or
tablejump) or a decision tree. */
- if (expand_switch_as_decision_tree_p (range, uniq, count))
- emit_case_decision_tree (index_expr, index_type,
- case_list, default_label,
- default_prob);
- else
{
/* If the default case is unreachable, then set default_label to NULL
so that we omit the range check when generating the dispatch table.
@@ -1355,694 +1185,3 @@ expand_sjlj_dispatch_table (rtx dispatch_index,
}
-/* 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_node_ptr *head, case_node_ptr parent)
-{
- case_node_ptr np;
-
- np = *head;
- if (np)
- {
- int i = 0;
- int ranges = 0;
- case_node_ptr *npp;
- case_node_ptr left;
-
- /* Count the number of entries on branch. Also count the ranges. */
-
- while (np)
- {
- if (!tree_int_cst_equal (np->low, np->high))
- ranges++;
-
- i++;
- np = np->right;
- }
-
- if (i > 2)
- {
- /* Split this list if it is long enough for that to help. */
- npp = head;
- left = *npp;
-
- /* If there are just three nodes, split at the middle one. */
- if (i == 3)
- npp = &(*npp)->right;
- else
- {
- /* 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;
-
- /* 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;
- }
- else
- {
- /* Else leave this branch as one level,
- but fill in `parent' fields. */
- np = *head;
- np->parent = parent;
- np->subtree_prob = np->prob;
- for (; np->right; np = np->right)
- {
- np->right->parent = np;
- (*head)->subtree_prob += np->right->subtree_prob;
- }
- }
- }
-}
-
-/* Search the parent sections of the case node tree
- to see if a test for the lower bound of NODE would be redundant.
- INDEX_TYPE is the type of the index expression.
-
- The instructions to generate the case decision tree are
- output in the same order as nodes are processed so it is
- known that if a parent node checks the range of the current
- node minus one that the current node is bounded at its lower
- span. Thus the test would be redundant. */
-
-static int
-node_has_low_bound (case_node_ptr node, tree index_type)
-{
- tree low_minus_one;
- case_node_ptr pnode;
-
- /* If the lower bound of this node is the lowest value in the index type,
- we need not test it. */
-
- if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
- return 1;
-
- /* If this node has a left branch, the value at the left must be less
- than that at this node, so it cannot be bounded at the bottom and
- we need not bother testing any further. */
-
- if (node->left)
- return 0;
-
- low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
- node->low,
- build_int_cst (TREE_TYPE (node->low), 1));
-
- /* If the subtraction above overflowed, we can't verify anything.
- Otherwise, look for a parent that tests our value - 1. */
-
- if (! tree_int_cst_lt (low_minus_one, node->low))
- return 0;
-
- for (pnode = node->parent; pnode; pnode = pnode->parent)
- if (tree_int_cst_equal (low_minus_one, pnode->high))
- return 1;
-
- return 0;
-}
-
-/* Search the parent sections of the case node tree
- to see if a test for the upper bound of NODE would be redundant.
- INDEX_TYPE is the type of the index expression.
-
- The instructions to generate the case decision tree are
- output in the same order as nodes are processed so it is
- known that if a parent node checks the range of the current
- node plus one that the current node is bounded at its upper
- span. Thus the test would be redundant. */
-
-static int
-node_has_high_bound (case_node_ptr node, tree index_type)
-{
- tree high_plus_one;
- case_node_ptr pnode;
-
- /* If there is no upper bound, obviously no test is needed. */
-
- if (TYPE_MAX_VALUE (index_type) == NULL)
- return 1;
-
- /* If the upper bound of this node is the highest value in the type
- of the index expression, we need not test against it. */
-
- if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
- return 1;
-
- /* If this node has a right branch, the value at the right must be greater
- than that at this node, so it cannot be bounded at the top and
- we need not bother testing any further. */
-
- if (node->right)
- return 0;
-
- high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
- node->high,
- build_int_cst (TREE_TYPE (node->high), 1));
-
- /* If the addition above overflowed, we can't verify anything.
- Otherwise, look for a parent that tests our value + 1. */
-
- if (! tree_int_cst_lt (node->high, high_plus_one))
- return 0;
-
- for (pnode = node->parent; pnode; pnode = pnode->parent)
- if (tree_int_cst_equal (high_plus_one, pnode->low))
- return 1;
-
- return 0;
-}
-
-/* Search the parent sections of the
- case node tree to see if both tests for the upper and lower
- bounds of NODE would be redundant. */
-
-static int
-node_is_bounded (case_node_ptr node, tree index_type)
-{
- return (node_has_low_bound (node, index_type)
- && node_has_high_bound (node, 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.
- INDEX_TYPE is the type of the index of the switch.
-
- Care is taken to prune redundant tests from the decision tree
- by detecting any boundary conditions already checked by
- emitted rtx. (See node_has_high_bound, node_has_low_bound
- and node_is_bounded, above.)
-
- Where the test conditions can be shown to be redundant we emit
- an unconditional jump to the target code. As a further
- optimization, the subordinates of a tree node are examined to
- check for bounded nodes. In this case conditional and/or
- unconditional jumps as a result of the boundary check for the
- current node are arranged to target the subordinates associated
- code for out of bound conditions on the current node.
-
- We can assume that when control reaches the code generated here,
- the index value has already been compared with the parents
- of this node, and determined to be on the same side of each parent
- as this node is. Thus, if this node tests for the value 51,
- and a parent tested for 52, we don't need to consider
- the possibility of a value greater than 51. If another parent
- tests for the value 50, then this node need not test anything. */
-
-static void
-emit_case_nodes (rtx index, case_node_ptr node, rtx_code_label *default_label,
- profile_probability default_prob, tree index_type)
-{
- /* If INDEX has an unsigned type, we must make unsigned branches. */
- int unsignedp = TYPE_UNSIGNED (index_type);
- profile_probability probability;
- profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
- machine_mode mode = GET_MODE (index);
- machine_mode imode = TYPE_MODE (index_type);
-
- /* Handle indices detected as constant during RTL expansion. */
- if (mode == VOIDmode)
- mode = imode;
-
- /* See if our parents have already tested everything for us.
- If they have, emit an unconditional jump for this node. */
- if (node_is_bounded (node, index_type))
- emit_jump (label_rtx (node->code_label));
-
- else if (tree_int_cst_equal (node->low, node->high))
- {
- probability = conditional_probability (prob, subtree_prob + default_prob);
- /* Node is single valued. First see if the index expression matches
- this node and then check our children, if any. */
- do_jump_if_equal (mode, index,
- convert_modes (mode, imode,
- expand_normal (node->low),
- unsignedp),
- jump_target_rtx (node->code_label),
- unsignedp, probability);
- /* Since this case is taken at this point, reduce its weight from
- subtree_weight. */
- subtree_prob -= prob;
- if (node->right != 0 && node->left != 0)
- {
- /* This node has children on both sides.
- Dispatch to one side or the other
- by comparing the index value with this node's value.
- If one subtree is bounded, check that one first,
- so we can avoid real branches in the tree. */
-
- if (node_is_bounded (node->right, index_type))
- {
- probability = conditional_probability (
- node->right->prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- GT, NULL_RTX, mode, unsignedp,
- label_rtx (node->right->code_label),
- probability);
- emit_case_nodes (index, node->left, default_label, default_prob,
- index_type);
- }
-
- else if (node_is_bounded (node->left, index_type))
- {
- probability = conditional_probability (
- node->left->prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- LT, NULL_RTX, mode, unsignedp,
- label_rtx (node->left->code_label),
- probability);
- emit_case_nodes (index, node->right, default_label, default_prob,
- index_type);
- }
-
- /* If both children are single-valued cases with no
- children, finish up all the work. This way, we can save
- one ordered comparison. */
- else if (tree_int_cst_equal (node->right->low, node->right->high)
- && node->right->left == 0
- && node->right->right == 0
- && tree_int_cst_equal (node->left->low, node->left->high)
- && node->left->left == 0
- && node->left->right == 0)
- {
- /* Neither node is bounded. First distinguish the two sides;
- then emit the code for one side at a time. */
-
- /* See if the value matches what the right hand side
- wants. */
- probability = conditional_probability (
- node->right->prob,
- subtree_prob + default_prob);
- do_jump_if_equal (mode, index,
- convert_modes (mode, imode,
- expand_normal (node->right->low),
- unsignedp),
- jump_target_rtx (node->right->code_label),
- unsignedp, probability);
-
- /* See if the value matches what the left hand side
- wants. */
- probability = conditional_probability (
- node->left->prob,
- subtree_prob + default_prob);
- do_jump_if_equal (mode, index,
- convert_modes (mode, imode,
- expand_normal (node->left->low),
- unsignedp),
- jump_target_rtx (node->left->code_label),
- unsignedp, probability);
- }
-
- else
- {
- /* Neither node is bounded. First distinguish the two sides;
- then emit the code for one side at a time. */
-
- tree test_label
- = build_decl (curr_insn_location (),
- LABEL_DECL, NULL_TREE, void_type_node);
-
- /* The default label could be reached either through the right
- subtree or the left subtree. Divide the probability
- equally. */
- probability = conditional_probability (
- node->right->subtree_prob + default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- /* See if the value is on the right. */
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- GT, NULL_RTX, mode, unsignedp,
- label_rtx (test_label),
- probability);
- default_prob = default_prob.apply_scale (1, 2);
-
- /* Value must be on the left.
- Handle the left-hand subtree. */
- emit_case_nodes (index, node->left, default_label, default_prob, index_type);
- /* If left-hand subtree does nothing,
- go to default. */
- if (default_label)
- emit_jump (default_label);
-
- /* Code branches here for the right-hand subtree. */
- expand_label (test_label);
- emit_case_nodes (index, node->right, default_label, default_prob, index_type);
- }
- }
-
- else if (node->right != 0 && node->left == 0)
- {
- /* Here we have a right child but no left so we issue a conditional
- branch to default and process the right child.
-
- Omit the conditional branch to default if the right child
- does not have any children and is single valued; it would
- cost too much space to save so little time. */
-
- if (node->right->right || node->right->left
- || !tree_int_cst_equal (node->right->low, node->right->high))
- {
- if (!node_has_low_bound (node, index_type))
- {
- probability = conditional_probability (
- default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- LT, NULL_RTX, mode, unsignedp,
- default_label,
- probability);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- emit_case_nodes (index, node->right, default_label, default_prob, index_type);
- }
- else
- {
- probability = conditional_probability (
- node->right->subtree_prob,
- subtree_prob + default_prob);
- /* We cannot process node->right normally
- since we haven't ruled out the numbers less than
- this node's value. So handle node->right explicitly. */
- do_jump_if_equal (mode, index,
- convert_modes
- (mode, imode,
- expand_normal (node->right->low),
- unsignedp),
- jump_target_rtx (node->right->code_label),
- unsignedp, probability);
- }
- }
-
- else if (node->right == 0 && node->left != 0)
- {
- /* Just one subtree, on the left. */
- if (node->left->left || node->left->right
- || !tree_int_cst_equal (node->left->low, node->left->high))
- {
- if (!node_has_high_bound (node, index_type))
- {
- probability = conditional_probability (
- default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- GT, NULL_RTX, mode, unsignedp,
- default_label,
- probability);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- emit_case_nodes (index, node->left, default_label,
- default_prob, index_type);
- }
- else
- {
- probability = conditional_probability (
- node->left->subtree_prob,
- subtree_prob + default_prob);
- /* We cannot process node->left normally
- since we haven't ruled out the numbers less than
- this node's value. So handle node->left explicitly. */
- do_jump_if_equal (mode, index,
- convert_modes
- (mode, imode,
- expand_normal (node->left->low),
- unsignedp),
- jump_target_rtx (node->left->code_label),
- unsignedp, probability);
- }
- }
- }
- else
- {
- /* Node is a range. These cases are very similar to those for a single
- value, except that we do not start by testing whether this node
- is the one to branch to. */
-
- if (node->right != 0 && node->left != 0)
- {
- /* Node has subtrees on both sides.
- If the right-hand subtree is bounded,
- test for it first, since we can go straight there.
- Otherwise, we need to make a branch in the control structure,
- then handle the two subtrees. */
- tree test_label = 0;
-
- if (node_is_bounded (node->right, index_type))
- {
- /* Right hand node is fully bounded so we can eliminate any
- testing and branch directly to the target code. */
- probability = conditional_probability (
- node->right->subtree_prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- GT, NULL_RTX, mode, unsignedp,
- label_rtx (node->right->code_label),
- probability);
- }
- else
- {
- /* Right hand node requires testing.
- Branch to a label where we will handle it later. */
-
- test_label = build_decl (curr_insn_location (),
- LABEL_DECL, NULL_TREE, void_type_node);
- probability = conditional_probability (
- node->right->subtree_prob + default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- GT, NULL_RTX, mode, unsignedp,
- label_rtx (test_label),
- probability);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the left-hand subtree. */
-
- probability = conditional_probability (
- prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->low),
- unsignedp),
- GE, NULL_RTX, mode, unsignedp,
- label_rtx (node->code_label),
- probability);
-
- /* Handle the left-hand subtree. */
- emit_case_nodes (index, node->left, default_label, default_prob, index_type);
-
- /* If right node had to be handled later, do that now. */
-
- if (test_label)
- {
- /* If the left-hand subtree fell through,
- don't let it fall into the right-hand subtree. */
- if (default_label)
- emit_jump (default_label);
-
- expand_label (test_label);
- emit_case_nodes (index, node->right, default_label, default_prob, index_type);
- }
- }
-
- else if (node->right != 0 && node->left == 0)
- {
- /* Deal with values to the left of this node,
- if they are possible. */
- if (!node_has_low_bound (node, index_type))
- {
- probability = conditional_probability (
- default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->low),
- unsignedp),
- LT, NULL_RTX, mode, unsignedp,
- default_label,
- probability);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the right-hand subtree. */
-
- probability = conditional_probability (
- prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- LE, NULL_RTX, mode, unsignedp,
- label_rtx (node->code_label),
- probability);
-
- emit_case_nodes (index, node->right, default_label, default_prob, index_type);
- }
-
- else if (node->right == 0 && node->left != 0)
- {
- /* Deal with values to the right of this node,
- if they are possible. */
- if (!node_has_high_bound (node, index_type))
- {
- probability = conditional_probability (
- default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- GT, NULL_RTX, mode, unsignedp,
- default_label,
- probability);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the left-hand subtree. */
-
- probability = conditional_probability (
- prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->low),
- unsignedp),
- GE, NULL_RTX, mode, unsignedp,
- label_rtx (node->code_label),
- probability);
-
- emit_case_nodes (index, node->left, default_label, default_prob, index_type);
- }
-
- else
- {
- /* Node has no children so we check low and high bounds to remove
- redundant tests. Only one of the bounds can exist,
- since otherwise this node is bounded--a case tested already. */
- int high_bound = node_has_high_bound (node, index_type);
- int low_bound = node_has_low_bound (node, index_type);
-
- if (!high_bound && low_bound)
- {
- probability = conditional_probability (
- default_prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->high),
- unsignedp),
- GT, NULL_RTX, mode, unsignedp,
- default_label,
- probability);
- }
-
- else if (!low_bound && high_bound)
- {
- probability = conditional_probability (
- default_prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (index,
- convert_modes
- (mode, imode,
- expand_normal (node->low),
- unsignedp),
- LT, NULL_RTX, mode, unsignedp,
- default_label,
- probability);
- }
- else if (!low_bound && !high_bound)
- {
- /* Widen LOW and HIGH to the same width as INDEX. */
- tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
- tree low = build1 (CONVERT_EXPR, type, node->low);
- tree high = build1 (CONVERT_EXPR, type, node->high);
- rtx low_rtx, new_index, new_bound;
-
- /* Instead of doing two branches, emit one unsigned branch for
- (index-low) > (high-low). */
- low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
- new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
- NULL_RTX, unsignedp,
- OPTAB_WIDEN);
- new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
- high, low),
- NULL_RTX, mode, EXPAND_NORMAL);
-
- probability = conditional_probability (
- default_prob,
- subtree_prob + default_prob);
- emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
- mode, 1, default_label, probability);
- }
-
- emit_jump (jump_target_rtx (node->code_label));
- }
- }
-}
@@ -1,4 +1,4 @@
-/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-optimized-blocks-details" } */
+/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-switchlower-blocks-details" } */
int max = 33333;
int a[8];
int
@@ -16,7 +16,7 @@ main ()
edge. */
/* autofdo cannot do that precise counts */
/* { dg-final-use-not-autofdo { scan-ipa-dump "loop depth 1, count 33334" "profile"} } */
-/* { dg-final-use-not-autofdo { scan-tree-dump "loop depth 1, count 33333" "optimized"} } */
-/* { dg-final-use-not-autofdo { scan-tree-dump-not "loop depth 1, count 33332" "optimized"} } */
-/* { dg-final-use-not-autofdo { scan-tree-dump "Removing basic block" "optimized"} } */
-/* { dg-final-use { scan-tree-dump-not "Invalid sum" "optimized"} } */
+/* { dg-final-use-not-autofdo { scan-tree-dump "loop depth 1, count 33333" "switchlower"} } */
+/* { dg-final-use-not-autofdo { scan-tree-dump-not "loop depth 1, count 33332" "switchlower"} } */
+/* { dg-final-use-not-autofdo { scan-tree-dump "Removing basic block" "switchlower"} } */
+/* { dg-final-use { scan-tree-dump-not "Invalid sum" "switchlower"} } */
@@ -1,6 +1,6 @@
/* PR tree-optimization/18046 */
/* { dg-options "-O2 -fdump-tree-optimized" } */
-/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "switch" 1 "switchlower" } } */
void foo (void);
void bar (void);
@@ -208,6 +208,7 @@ DEFTIMEVAR (TV_TREE_COPY_RENAME , "tree rename SSA copies")
DEFTIMEVAR (TV_TREE_SSA_VERIFY , "tree SSA verifier")
DEFTIMEVAR (TV_TREE_STMT_VERIFY , "tree STMT verifier")
DEFTIMEVAR (TV_TREE_SWITCH_CONVERSION, "tree switch conversion")
+DEFTIMEVAR (TV_TREE_SWITCH_LOWERING, "tree switch lowering")
DEFTIMEVAR (TV_TRANS_MEM , "transactional memory")
DEFTIMEVAR (TV_TREE_STRLEN , "tree strlen optimization")
DEFTIMEVAR (TV_CGRAPH_VERIFY , "callgraph verifier")
@@ -409,6 +409,7 @@ extern gimple_opt_pass *make_pass_profile (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_strip_predict_hints (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_complex_O0 (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_complex (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_lower_switch (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_vector (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_vector_ssa (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_omp (gcc::context *ctxt);
@@ -46,6 +46,9 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
#include "gimplify-me.h"
#include "tree-cfg.h"
#include "cfgloop.h"
+#include "alloc-pool.h"
+#include "target.h"
+#include "tree-into-ssa.h"
/* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
type in the GIMPLE type system that is language-independent? */
@@ -1662,3 +1665,1178 @@ make_pass_convert_switch (gcc::context *ctxt)
{
return new pass_convert_switch (ctxt);
}
+
+struct case_node
+{
+ case_node *left; /* Left son in binary tree. */
+ case_node *right; /* Right son in binary tree;
+ also node chain. */
+ case_node *parent; /* Parent of node in binary tree. */
+ tree low; /* Lowest index value for this label. */
+ tree high; /* Highest index value for this label. */
+ basic_block case_bb; /* Label to jump to when node matches. */
+ tree case_label; /* Label to jump to when node matches. */
+ profile_probability prob; /* Probability of taking this case. */
+ profile_probability subtree_prob; /* Probability of reaching subtree
+ rooted at this node. */
+};
+
+typedef case_node *case_node_ptr;
+
+static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
+ basic_block, tree, profile_probability,
+ tree, hash_map<tree, tree> *);
+static bool node_has_low_bound (case_node_ptr, tree);
+static bool node_has_high_bound (case_node_ptr, tree);
+static bool node_is_bounded (case_node_ptr, tree);
+
+/* 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 unsigned int
+case_values_threshold (void)
+{
+ unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
+
+ if (threshold == 0)
+ threshold = targetm.case_values_threshold ();
+
+ return threshold;
+}
+
+/* Reset the aux field of all outgoing edges of basic block BB. */
+
+static inline void
+reset_out_edges_aux (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ e->aux = (void *) 0;
+}
+
+/* Compute the number of case labels that correspond to each outgoing edge of
+ STMT. Record this information in the aux field of the edge. */
+
+static inline void
+compute_cases_per_edge (gswitch *stmt)
+{
+ 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)
+ {
+ 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);
+ }
+}
+
+/* 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. */
+
+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)
+{
+ 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;
+}
+
+/* Dump ROOT, a list or tree of case nodes, to file. */
+
+static void
+dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
+{
+ if (root == 0)
+ return;
+ indent_level++;
+
+ dump_case_nodes (f, root->left, indent_step, indent_level);
+
+ fputs (";; ", f);
+ fprintf (f, "%*s", indent_step * indent_level, "");
+ print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
+ if (!tree_int_cst_equal (root->low, root->high))
+ {
+ fprintf (f, " ... ");
+ print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
+ }
+ fputs ("\n", f);
+
+ dump_case_nodes (f, root->right, indent_step, indent_level);
+}
+
+/* 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_node_ptr *head, case_node_ptr parent)
+{
+ case_node_ptr np;
+
+ np = *head;
+ if (np)
+ {
+ int i = 0;
+ int ranges = 0;
+ case_node_ptr *npp;
+ case_node_ptr left;
+
+ /* Count the number of entries on branch. Also count the ranges. */
+
+ while (np)
+ {
+ if (!tree_int_cst_equal (np->low, np->high))
+ ranges++;
+
+ i++;
+ np = np->right;
+ }
+
+ if (i > 2)
+ {
+ /* Split this list if it is long enough for that to help. */
+ npp = head;
+ left = *npp;
+
+ /* If there are just three nodes, split at the middle one. */
+ if (i == 3)
+ npp = &(*npp)->right;
+ else
+ {
+ /* 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;
+
+ /* 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;
+ }
+ else
+ {
+ /* Else leave this branch as one level,
+ but fill in `parent' fields. */
+ np = *head;
+ np->parent = parent;
+ np->subtree_prob = np->prob;
+ for (; np->right; np = np->right)
+ {
+ np->right->parent = np;
+ (*head)->subtree_prob += np->right->subtree_prob;
+ }
+ }
+ }
+}
+
+/* Return true if a switch should be expanded as a decision tree.
+ RANGE is the difference between highest and lowest case.
+ UNIQ is number of unique case node targets, not counting the default case.
+ COUNT is the number of comparisons needed, not counting the default case. */
+
+static bool
+expand_switch_as_decision_tree_p (tree range,
+ unsigned int uniq ATTRIBUTE_UNUSED,
+ unsigned int count)
+{
+ int max_ratio;
+
+ /* If neither casesi or tablejump is available, or flag_jump_tables
+ over-ruled us, we really have no choice. */
+ if (!targetm.have_casesi () && !targetm.have_tablejump ())
+ return true;
+ if (!flag_jump_tables)
+ return true;
+#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
+ if (flag_pic)
+ return true;
+#endif
+
+ /* If the switch is relatively small such that the cost of one
+ indirect jump on the target are higher than the cost of a
+ decision tree, go with the decision tree.
+
+ If range of values is much bigger than number of values,
+ or if it is too large to represent in a HOST_WIDE_INT,
+ make a sequence of conditional branches instead of a dispatch.
+
+ The definition of "much bigger" depends on whether we are
+ optimizing for size or for speed. 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;
+
+ return false;
+}
+
+static void
+fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
+{
+ basic_block bb = e->dest;
+ gphi_iterator gsi;
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+
+ tree *definition = phi_mapping->get (gimple_phi_result (phi));
+ if (definition)
+ add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
+ }
+}
+
+
+/* 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)
+{
+ edge e = single_succ_edge (bb);
+ redirect_edge_succ (e, case_bb);
+ fix_phi_operands_for_edge (e, phi_mapping);
+}
+
+/* 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.
+
+ 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);
+
+ 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);
+ }
+
+ basic_block bb = gimple_bb (s);
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ edge e;
+ if (gsi_end_p (gsi))
+ e = split_block_after_labels (bb);
+ else
+ {
+ gsi_prev (&gsi);
+ e = split_block (bb, gsi_stmt (gsi));
+ }
+ bb = split_edge (e);
+
+ bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
+ default_prob, index_type, phi_mapping);
+
+ if (bb)
+ emit_jump (bb, default_bb, phi_mapping);
+
+ /* Remove all edges and do just an edge that will reach default_bb. */
+ gsi = gsi_last_bb (gimple_bb (s));
+ gsi_remove (&gsi, true);
+}
+
+static void
+record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
+ hash_map <tree, tree> *map)
+{
+ /* Record all PHI nodes that have to be fixed after conversion. */
+ for (unsigned i = 0; i < bbs.length (); i++)
+ {
+ basic_block bb = bbs[i];
+
+ gphi_iterator gsi;
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
+ if (phi_src_bb == switch_bb)
+ {
+ tree def = gimple_phi_arg_def (phi, i);
+ tree result = gimple_phi_result (phi);
+ map->put (result, def);
+ break;
+ }
+ }
+ }
+ }
+}
+
+/* Attempt to expand gimple switch STMT to a decision tree. */
+
+static bool
+try_switch_expansion (gswitch *stmt)
+{
+ tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
+ basic_block default_bb;
+ unsigned int count, uniq;
+ int i;
+ int ncases = gimple_switch_num_labels (stmt);
+ tree index_expr = gimple_switch_index (stmt);
+ tree index_type = TREE_TYPE (index_expr);
+ tree elt;
+ basic_block bb = gimple_bb (stmt);
+
+ hash_map<tree, tree> phi_mapping;
+ auto_vec<basic_block> case_bbs;
+
+ /* A list of case labels; it is first built as a list and it may then
+ be rearranged into a nearly balanced binary tree. */
+ case_node *case_list = 0;
+
+ /* A pool for case nodes. */
+ object_allocator<case_node> case_node_pool ("struct case_node pool");
+
+ /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
+ expressions being INTEGER_CST. */
+ gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+
+ /* Optimization of switch statements with only one label has already
+ occurred, so we should never see them at this point. */
+ gcc_assert (ncases > 1);
+
+ /* 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 = EDGE_SUCC (bb, 0);
+ 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));
+
+ /* Compute span of values. */
+ range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
+
+ /* 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);
+
+ for (i = ncases - 1; i >= 1; --i)
+ {
+ elt = gimple_switch_label (stmt, i);
+ tree low = CASE_LOW (elt);
+ gcc_assert (low);
+ tree high = CASE_HIGH (elt);
+ gcc_assert (!high || tree_int_cst_lt (low, high));
+ tree lab = CASE_LABEL (elt);
+
+ /* Count the elements.
+ A range counts double, since it requires two compares. */
+ count++;
+ if (high)
+ count++;
+
+ /* If we have not seen this label yet, then increase the
+ number of unique case node targets seen. */
+ if (!seen_labels.add (lab))
+ uniq++;
+
+ /* The bounds on the case range, LOW and HIGH, have to be converted
+ to case's index type TYPE. Note that the original type of the
+ case index in the source code is usually "lost" during
+ gimplification due to type promotion, but the case labels retain the
+ original type. Make sure to drop overflow flags. */
+ low = fold_convert (index_type, low);
+ if (TREE_OVERFLOW (low))
+ low = wide_int_to_tree (index_type, 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, high);
+
+ basic_block case_bb = label_to_block_fn (cfun, lab);
+ edge case_edge = find_edge (bb, case_bb);
+ case_list = add_case_node (
+ case_list, low, high, case_bb, lab,
+ case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)),
+ case_node_pool);
+
+ case_bbs.safe_push (case_bb);
+ }
+ reset_out_edges_aux (bb);
+ record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
+
+ /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
+ destination, such as one with a default case only.
+ It also removes cases that are out of range for the switch
+ type, so we should never get a zero here. */
+ gcc_assert (count > 0);
+
+ /* Decide how to expand this switch.
+ The two options at this point are a dispatch table (casesi or
+ tablejump) or a decision tree. */
+
+ 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;
+ }
+
+ return false;
+}
+
+/* The main function of the pass scans statements for switches and invokes
+ process_switch on them. */
+
+namespace {
+
+const pass_data pass_data_lower_switch =
+{
+ GIMPLE_PASS, /* type */
+ "switchlower", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_SWITCH_LOWERING, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
+};
+
+class pass_lower_switch : public gimple_opt_pass
+{
+public:
+ pass_lower_switch (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_lower_switch, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return true; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_lower_switch
+
+unsigned int
+pass_lower_switch::execute (function *fun)
+{
+ basic_block bb;
+ bool expanded = 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);
+ }
+
+ expanded |= try_switch_expansion (as_a<gswitch *> (stmt));
+ }
+ }
+
+ if (expanded)
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ mark_virtual_operands_for_renaming (cfun);
+ }
+
+ return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_lower_switch (gcc::context *ctxt)
+{
+ return new pass_lower_switch (ctxt);
+}
+
+/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
+ PROB is the probability of jumping to LABEL. */
+static basic_block
+do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
+ profile_probability prob, hash_map<tree, tree> *phi_mapping)
+{
+ gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ gsi_insert_before (&gsi, cond, GSI_SAME_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;
+}
+
+/* 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.
+
+ Care is taken to prune redundant tests from the decision tree
+ by detecting any boundary conditions already checked by
+ emitted rtx. (See node_has_high_bound, node_has_low_bound
+ and node_is_bounded, above.)
+
+ Where the test conditions can be shown to be redundant we emit
+ an unconditional jump to the target code. As a further
+ optimization, the subordinates of a tree node are examined to
+ check for bounded nodes. In this case conditional and/or
+ unconditional jumps as a result of the boundary check for the
+ current node are arranged to target the subordinates associated
+ code for out of bound conditions on the current node.
+
+ We can assume that when control reaches the code generated here,
+ the index value has already been compared with the parents
+ of this node, and determined to be on the same side of each parent
+ as this node is. Thus, if this node tests for the value 51,
+ and a parent tested for 52, we don't need to consider
+ the possibility of a value greater than 51. If another parent
+ tests for the value 50, then this node need not test anything. */
+
+static basic_block
+emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
+ basic_block default_bb, tree default_label,
+ profile_probability default_prob, tree index_type,
+ hash_map<tree, tree> *phi_mapping)
+{
+ /* If INDEX has an unsigned type, we must make unsigned branches. */
+ profile_probability probability;
+ profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
+
+ /* See if our parents have already tested everything for us.
+ If they have, emit an unconditional jump for this node. */
+ if (node_is_bounded (node, index_type))
+ {
+ emit_jump (bb, node->case_bb, phi_mapping);
+ return NULL;
+ }
+
+ else if (tree_int_cst_equal (node->low, node->high))
+ {
+ probability = conditional_probability (prob, subtree_prob + default_prob);
+ /* Node is single valued. First see if the index expression matches
+ this node and then check our children, if any. */
+ bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
+ phi_mapping);
+ /* Since this case is taken at this point, reduce its weight from
+ subtree_weight. */
+ subtree_prob -= prob;
+ if (node->right != 0 && node->left != 0)
+ {
+ /* This node has children on both sides.
+ Dispatch to one side or the other
+ by comparing the index value with this node's value.
+ If one subtree is bounded, check that one first,
+ so we can avoid real branches in the tree. */
+
+ if (node_is_bounded (node->right, index_type))
+ {
+ probability
+ = conditional_probability (node->right->prob,
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ node->right->case_bb, probability,
+ phi_mapping);
+ bb = emit_case_nodes (bb, index, node->left, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+
+ else if (node_is_bounded (node->left, index_type))
+ {
+ probability
+ = conditional_probability (node->left->prob,
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
+ node->left->case_bb, probability,
+ phi_mapping);
+ bb = emit_case_nodes (bb, index, node->right, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+
+ /* If both children are single-valued cases with no
+ children, finish up all the work. This way, we can save
+ one ordered comparison. */
+ else if (tree_int_cst_equal (node->right->low, node->right->high)
+ && node->right->left == 0 && node->right->right == 0
+ && tree_int_cst_equal (node->left->low, node->left->high)
+ && node->left->left == 0 && node->left->right == 0)
+ {
+ /* Neither node is bounded. First distinguish the two sides;
+ then emit the code for one side at a time. */
+
+ /* See if the value matches what the right hand side
+ wants. */
+ probability
+ = conditional_probability (node->right->prob,
+ subtree_prob + default_prob);
+ bb = do_jump_if_equal (bb, index, node->right->low,
+ node->right->case_bb, probability,
+ phi_mapping);
+
+ /* See if the value matches what the left hand side
+ wants. */
+ probability
+ = conditional_probability (node->left->prob,
+ subtree_prob + default_prob);
+ bb = do_jump_if_equal (bb, index, node->left->low,
+ node->left->case_bb, probability,
+ phi_mapping);
+ }
+
+ else
+ {
+ /* Neither node is bounded. First distinguish the two sides;
+ then emit the code for one side at a time. */
+
+ basic_block test_bb = split_edge (single_succ_edge (bb));
+ redirect_edge_succ (single_pred_edge (test_bb),
+ single_succ_edge (bb)->dest);
+
+ /* The default label could be reached either through the right
+ subtree or the left subtree. Divide the probability
+ equally. */
+ probability
+ = conditional_probability (node->right->subtree_prob
+ + default_prob.apply_scale (1, 2),
+ subtree_prob + default_prob);
+ /* See if the value is on the right. */
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ test_bb, probability, phi_mapping);
+ default_prob = default_prob.apply_scale (1, 2);
+
+ /* Value must be on the left.
+ Handle the left-hand subtree. */
+ bb = emit_case_nodes (bb, index, node->left, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ /* If left-hand subtree does nothing,
+ go to default. */
+
+ if (bb && default_bb)
+ emit_jump (bb, default_bb, phi_mapping);
+
+ /* Code branches here for the right-hand subtree. */
+ bb = emit_case_nodes (test_bb, index, node->right, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+ }
+ else if (node->right != 0 && node->left == 0)
+ {
+ /* Here we have a right child but no left so we issue a conditional
+ branch to default and process the right child.
+
+ Omit the conditional branch to default if the right child
+ does not have any children and is single valued; it would
+ cost too much space to save so little time. */
+
+ if (node->right->right || node->right->left
+ || !tree_int_cst_equal (node->right->low, node->right->high))
+ {
+ if (!node_has_low_bound (node, index_type))
+ {
+ probability
+ = conditional_probability (default_prob.apply_scale (1, 2),
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
+ default_bb, probability,
+ phi_mapping);
+ default_prob = default_prob.apply_scale (1, 2);
+ }
+
+ bb = emit_case_nodes (bb, index, node->right, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+ else
+ {
+ probability
+ = conditional_probability (node->right->subtree_prob,
+ subtree_prob + default_prob);
+ /* We cannot process node->right normally
+ since we haven't ruled out the numbers less than
+ this node's value. So handle node->right explicitly. */
+ bb = do_jump_if_equal (bb, index, node->right->low,
+ node->right->case_bb, probability,
+ phi_mapping);
+ }
+ }
+
+ else if (node->right == 0 && node->left != 0)
+ {
+ /* Just one subtree, on the left. */
+ if (node->left->left || node->left->right
+ || !tree_int_cst_equal (node->left->low, node->left->high))
+ {
+ if (!node_has_high_bound (node, index_type))
+ {
+ probability
+ = conditional_probability (default_prob.apply_scale (1, 2),
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ default_bb, probability,
+ phi_mapping);
+ default_prob = default_prob.apply_scale (1, 2);
+ }
+
+ bb = emit_case_nodes (bb, index, node->left, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+ else
+ {
+ probability
+ = conditional_probability (node->left->subtree_prob,
+ subtree_prob + default_prob);
+ /* We cannot process node->left normally
+ since we haven't ruled out the numbers less than
+ this node's value. So handle node->left explicitly. */
+ do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
+ probability, phi_mapping);
+ }
+ }
+ }
+ else
+ {
+ /* Node is a range. These cases are very similar to those for a single
+ value, except that we do not start by testing whether this node
+ is the one to branch to. */
+
+ if (node->right != 0 && node->left != 0)
+ {
+ /* Node has subtrees on both sides.
+ If the right-hand subtree is bounded,
+ test for it first, since we can go straight there.
+ Otherwise, we need to make a branch in the control structure,
+ then handle the two subtrees. */
+ basic_block test_bb = NULL;
+
+ if (node_is_bounded (node->right, index_type))
+ {
+ /* Right hand node is fully bounded so we can eliminate any
+ testing and branch directly to the target code. */
+ probability
+ = conditional_probability (node->right->subtree_prob,
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ node->right->case_bb, probability,
+ phi_mapping);
+ }
+ else
+ {
+ /* Right hand node requires testing.
+ Branch to a label where we will handle it later. */
+
+ test_bb = split_edge (single_succ_edge (bb));
+ redirect_edge_succ (single_pred_edge (test_bb),
+ single_succ_edge (bb)->dest);
+
+ probability
+ = conditional_probability (node->right->subtree_prob
+ + default_prob.apply_scale (1, 2),
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ test_bb, probability, phi_mapping);
+ default_prob = default_prob.apply_scale (1, 2);
+ }
+
+ /* Value belongs to this node or to the left-hand subtree. */
+
+ probability
+ = conditional_probability (prob, subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
+ node->case_bb, probability,
+ phi_mapping);
+
+ /* Handle the left-hand subtree. */
+ bb = emit_case_nodes (bb, index, node->left, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+
+ /* If right node had to be handled later, do that now. */
+ if (test_bb)
+ {
+ /* If the left-hand subtree fell through,
+ don't let it fall into the right-hand subtree. */
+ if (bb && default_bb)
+ emit_jump (bb, default_bb, phi_mapping);
+
+ bb = emit_case_nodes (test_bb, index, node->right, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+ }
+
+ else if (node->right != 0 && node->left == 0)
+ {
+ /* Deal with values to the left of this node,
+ if they are possible. */
+ if (!node_has_low_bound (node, index_type))
+ {
+ probability
+ = conditional_probability (default_prob.apply_scale (1, 2),
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
+ default_bb, probability,
+ phi_mapping);
+ default_prob = default_prob.apply_scale (1, 2);
+ }
+
+ /* Value belongs to this node or to the right-hand subtree. */
+
+ probability
+ = conditional_probability (prob, subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
+ node->case_bb, probability,
+ phi_mapping);
+
+ bb = emit_case_nodes (bb, index, node->right, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+
+ else if (node->right == 0 && node->left != 0)
+ {
+ /* Deal with values to the right of this node,
+ if they are possible. */
+ if (!node_has_high_bound (node, index_type))
+ {
+ probability
+ = conditional_probability (default_prob.apply_scale (1, 2),
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ default_bb, probability,
+ phi_mapping);
+ default_prob = default_prob.apply_scale (1, 2);
+ }
+
+ /* Value belongs to this node or to the left-hand subtree. */
+
+ probability
+ = conditional_probability (prob, subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
+ node->case_bb, probability,
+ phi_mapping);
+
+ bb = emit_case_nodes (bb, index, node->left, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
+ }
+
+ else
+ {
+ /* Node has no children so we check low and high bounds to remove
+ redundant tests. Only one of the bounds can exist,
+ since otherwise this node is bounded--a case tested already. */
+ bool high_bound = node_has_high_bound (node, index_type);
+ bool low_bound = node_has_low_bound (node, index_type);
+
+ if (!high_bound && low_bound)
+ {
+ probability
+ = conditional_probability (default_prob,
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ default_bb, probability,
+ phi_mapping);
+ }
+
+ else if (!low_bound && high_bound)
+ {
+ probability
+ = conditional_probability (default_prob,
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
+ default_bb, probability,
+ phi_mapping);
+ }
+ else if (!low_bound && !high_bound)
+ {
+ tree type = TREE_TYPE (index);
+ tree utype = unsigned_type_for (type);
+
+ tree lhs = make_ssa_name (type);
+ gassign *sub1
+ = gimple_build_assign (lhs, MINUS_EXPR, index, node->low);
+
+ tree converted = make_ssa_name (utype);
+ gassign *a = gimple_build_assign (converted, NOP_EXPR, lhs);
+
+ tree rhs = fold_build2 (MINUS_EXPR, utype,
+ fold_convert (type, node->high),
+ fold_convert (type, node->low));
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ gsi_insert_before (&gsi, sub1, GSI_SAME_STMT);
+ gsi_insert_before (&gsi, a, GSI_SAME_STMT);
+
+ probability
+ = conditional_probability (default_prob,
+ subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, converted, rhs, GT_EXPR,
+ default_bb, probability,
+ phi_mapping);
+ }
+
+ emit_jump (bb, node->case_bb, phi_mapping);
+ return NULL;
+ }
+ }
+
+ return bb;
+}
+
+/* Search the parent sections of the case node tree
+ to see if a test for the lower bound of NODE would be redundant.
+ INDEX_TYPE is the type of the index expression.
+
+ The instructions to generate the case decision tree are
+ output in the same order as nodes are processed so it is
+ known that if a parent node checks the range of the current
+ node minus one that the current node is bounded at its lower
+ span. Thus the test would be redundant. */
+
+static bool
+node_has_low_bound (case_node_ptr node, tree index_type)
+{
+ tree low_minus_one;
+ case_node_ptr pnode;
+
+ /* If the lower bound of this node is the lowest value in the index type,
+ we need not test it. */
+
+ if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
+ return true;
+
+ /* If this node has a left branch, the value at the left must be less
+ than that at this node, so it cannot be bounded at the bottom and
+ we need not bother testing any further. */
+
+ if (node->left)
+ return false;
+
+ low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
+ build_int_cst (TREE_TYPE (node->low), 1));
+
+ /* If the subtraction above overflowed, we can't verify anything.
+ Otherwise, look for a parent that tests our value - 1. */
+
+ if (!tree_int_cst_lt (low_minus_one, node->low))
+ return false;
+
+ for (pnode = node->parent; pnode; pnode = pnode->parent)
+ if (tree_int_cst_equal (low_minus_one, pnode->high))
+ return true;
+
+ return false;
+}
+
+/* Search the parent sections of the case node tree
+ to see if a test for the upper bound of NODE would be redundant.
+ INDEX_TYPE is the type of the index expression.
+
+ The instructions to generate the case decision tree are
+ output in the same order as nodes are processed so it is
+ known that if a parent node checks the range of the current
+ node plus one that the current node is bounded at its upper
+ span. Thus the test would be redundant. */
+
+static bool
+node_has_high_bound (case_node_ptr node, tree index_type)
+{
+ tree high_plus_one;
+ case_node_ptr pnode;
+
+ /* If there is no upper bound, obviously no test is needed. */
+
+ if (TYPE_MAX_VALUE (index_type) == NULL)
+ return true;
+
+ /* If the upper bound of this node is the highest value in the type
+ of the index expression, we need not test against it. */
+
+ if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
+ return true;
+
+ /* If this node has a right branch, the value at the right must be greater
+ than that at this node, so it cannot be bounded at the top and
+ we need not bother testing any further. */
+
+ if (node->right)
+ return false;
+
+ high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
+ build_int_cst (TREE_TYPE (node->high), 1));
+
+ /* If the addition above overflowed, we can't verify anything.
+ Otherwise, look for a parent that tests our value + 1. */
+
+ if (!tree_int_cst_lt (node->high, high_plus_one))
+ return false;
+
+ for (pnode = node->parent; pnode; pnode = pnode->parent)
+ if (tree_int_cst_equal (high_plus_one, pnode->low))
+ return true;
+
+ return false;
+}
+
+/* Search the parent sections of the
+ case node tree to see if both tests for the upper and lower
+ bounds of NODE would be redundant. */
+
+static bool
+node_is_bounded (case_node_ptr node, tree index_type)
+{
+ return (node_has_low_bound (node, index_type)
+ && node_has_high_bound (node, index_type));
+}
--
2.13.3