diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/ChangeLog | 15 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 6 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/switch-3.c | 20 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/vrp105.c | 37 | ||||
| -rw-r--r-- | gcc/tree-switch-conversion.c | 244 | ||||
| -rw-r--r-- | gcc/tree-switch-conversion.h | 24 |
6 files changed, 278 insertions, 68 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 698f677..47844ef 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,20 @@ 2018-08-27 Martin Liska <mliska@suse.cz> + PR tree-optimization/86847 + * tree-switch-conversion.c (switch_decision_tree::dump_case_nodes): + Dump also subtree probability. + (switch_decision_tree::do_jump_if_equal): New function. + (switch_decision_tree::emit_case_nodes): Handle special + situations in balanced tree that can be emitted much simpler. + Fix calculation of probabilities that happen in tree expansion. + * tree-switch-conversion.h (struct cluster): Add + is_single_value_p. + (struct simple_cluster): Likewise. + (struct case_tree_node): Add new function has_child. + (do_jump_if_equal): New. + +2018-08-27 Martin Liska <mliska@suse.cz> + * tree-switch-conversion.c (bit_test_cluster::find_bit_tests): Add new argument to bit_test_cluster constructor. (bit_test_cluster::emit): Set bits really number of values diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index f20f43a..6e74b17 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,5 +1,11 @@ 2018-08-27 Martin Liska <mliska@suse.cz> + PR tree-optimization/86847 + * gcc.dg/tree-ssa/switch-3.c: New test. + * gcc.dg/tree-ssa/vrp105.c: Remove. + +2018-08-27 Martin Liska <mliska@suse.cz> + * gcc.dg/tree-ssa/switch-2.c: New test. 2018-08-27 Richard Biener <rguenther@suse.de> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c new file mode 100644 index 0000000..44981e1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c @@ -0,0 +1,20 @@ +/* { dg-options "-O2 -fdump-tree-switchlower1" } */ + +int cipher_to_alg(int cipher) +{ + switch (cipher) + { + case 8: return 2; + case 16: return 3; + case 32: return 4; + case 64: return 6; + case 256: return 9; + case 512: return 10; + case 2048: return 11; + case 4096: return 12; + case 8192: return 13; + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "if \\(cipher\[^\n ]*" 12 "switchlower1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c deleted file mode 100644 index 7cdd4dd..0000000 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c +++ /dev/null @@ -1,37 +0,0 @@ -/* PR tree-optimization/18046 */ -/* { dg-options "-O2 -fdump-tree-vrp2-details" } */ -/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp2" } } */ -/* In the 2nd VRP pass (after PRE) we expect to thread the default label of the - 1st switch straight to that of the 2nd switch. */ - -extern void foo (void); -extern void bar (void); - -extern int i; -void -test (void) -{ - switch (i) - { - case 0: - foo (); - break; - case 1: - bar (); - break; - default: - break; - } - - switch (i) - { - case 0: - foo (); - break; - case 1: - bar (); - break; - default: - break; - } -} diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 47acb0c..a31ff94 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -2004,7 +2004,9 @@ switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root, fprintf (f, "%*s", indent_step * indent_level, ""); root->m_c->dump (f); root->m_c->m_prob.dump (f); - fputs ("\n", f); + fputs (" subtree: ", f); + root->m_c->m_subtree_prob.dump (f); + fputs (")\n", f); dump_case_nodes (f, root->m_right, indent_step, indent_level); } @@ -2050,6 +2052,34 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0, return false_edge->dest; } +/* Generate code to jump to LABEL if OP0 and OP1 are equal. + PROB is the probability of jumping to LABEL_BB. + BB is a basic block where the new condition will be placed. */ + +basic_block +switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1, + basic_block label_bb, + profile_probability prob) +{ + op1 = fold_convert (TREE_TYPE (op0), op1); + + 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); + true_edge->probability = prob; + + return false_edge->dest; +} + /* Emit step-by-step code to select a case for the value of INDEX. The thus generated decision tree follows the form of the case-node binary tree NODE, whose nodes represent test conditions. @@ -2062,41 +2092,193 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index, profile_probability default_prob, tree index_type) { + profile_probability p; + /* If node is null, we are done. */ if (node == NULL) return bb; - /* Branch to a label where we will handle it later. */ - basic_block test_bb = split_edge (single_succ_edge (bb)); - redirect_edge_succ (single_pred_edge (test_bb), - single_succ_edge (bb)->dest); - - profile_probability probability - = (node->m_right - ? node->m_right->m_c->m_subtree_prob : profile_probability::never ()); - probability = ((probability + default_prob.apply_scale (1, 2)) - / (node->m_c->m_subtree_prob + default_prob)); - bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), GT_EXPR, - test_bb, probability); - default_prob = default_prob.apply_scale (1, 2); - - /* Value belongs to this node or to the left-hand subtree. */ - probability = node->m_c->m_prob / - (node->m_c->m_subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), GE_EXPR, - node->m_c->m_case_bb, probability); - - /* Handle the left-hand subtree. */ - bb = emit_case_nodes (bb, index, node->m_left, - default_prob, index_type); - - /* If the left-hand subtree fell through, - don't let it fall into the right-hand subtree. */ - if (m_default_bb) - emit_jump (bb, m_default_bb); + /* Single value case. */ + if (node->m_c->is_single_value_p ()) + { + /* Node is single valued. First see if the index expression matches + this node and then check our children, if any. */ + p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); + bb = do_jump_if_equal (bb, index, node->m_c->get_low (), + node->m_c->m_case_bb, p); + /* Since this case is taken at this point, reduce its weight from + subtree_weight. */ + node->m_c->m_subtree_prob -= p; + + if (node->m_left != NULL && node->m_right != NULL) + { + /* 1) the node has both children + + If both children are single-valued cases with no + children, finish up all the work. This way, we can save + one ordered comparison. */ + + if (!node->m_left->has_child () + && node->m_left->m_c->is_single_value_p () + && !node->m_right->has_child () + && node->m_right->m_c->is_single_value_p ()) + { + p = (node->m_right->m_c->m_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), + node->m_right->m_c->m_case_bb, p); + + p = (node->m_left->m_c->m_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (), + node->m_left->m_c->m_case_bb, p); + } + else + { + /* Branch to a label where we will handle it later. */ + basic_block test_bb = split_edge (single_succ_edge (bb)); + redirect_edge_succ (single_pred_edge (test_bb), + single_succ_edge (bb)->dest); + + p = ((node->m_right->m_c->m_subtree_prob + + default_prob.apply_scale (1, 2)) + / (node->m_c->m_subtree_prob + default_prob)); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), + GT_EXPR, test_bb, p); + default_prob = default_prob.apply_scale (1, 2); + + /* Handle the left-hand subtree. */ + bb = emit_case_nodes (bb, index, node->m_left, + default_prob, index_type); + + /* If the left-hand subtree fell through, + don't let it fall into the right-hand subtree. */ + if (bb && m_default_bb) + emit_jump (bb, m_default_bb); + + bb = emit_case_nodes (test_bb, index, node->m_right, + default_prob, index_type); + } + } + else if (node->m_left == NULL && node->m_right != NULL) + { + /* 2) the node has only right child. */ - bb = emit_case_nodes (test_bb, index, node->m_right, - default_prob, index_type); + /* 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->m_right->has_child () + || !node->m_right->m_c->is_single_value_p ()) + { + p = (default_prob.apply_scale (1, 2) + / (node->m_c->m_subtree_prob + default_prob)); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), + LT_EXPR, m_default_bb, p); + default_prob = default_prob.apply_scale (1, 2); + + bb = emit_case_nodes (bb, index, node->m_right, default_prob, + index_type); + } + else + { + /* We cannot process node->right normally + since we haven't ruled out the numbers less than + this node's value. So handle node->right explicitly. */ + p = (node->m_right->m_c->m_subtree_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (), + node->m_right->m_c->m_case_bb, p); + } + } + else if (node->m_left != NULL && node->m_right == NULL) + { + /* 3) just one subtree, on the left. Similar case as previous. */ + + if (node->m_left->has_child () + || !node->m_left->m_c->is_single_value_p ()) + { + p = (default_prob.apply_scale (1, 2) + / (node->m_c->m_subtree_prob + default_prob)); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), + GT_EXPR, m_default_bb, p); + default_prob = default_prob.apply_scale (1, 2); + + bb = emit_case_nodes (bb, index, node->m_left, default_prob, + index_type); + } + else + { + /* We cannot process node->left normally + since we haven't ruled out the numbers less than + this node's value. So handle node->left explicitly. */ + p = (node->m_left->m_c->m_subtree_prob + / (node->m_c->m_subtree_prob + default_prob)); + bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (), + node->m_left->m_c->m_case_bb, p); + } + } + } + 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->has_child () || node->m_c->get_type () != SIMPLE_CASE) + { + /* Branch to a label where we will handle it later. */ + basic_block test_bb = split_edge (single_succ_edge (bb)); + redirect_edge_succ (single_pred_edge (test_bb), + single_succ_edge (bb)->dest); + + + profile_probability right_prob = profile_probability::never (); + if (node->m_right) + right_prob = node->m_right->m_c->m_subtree_prob; + p = ((right_prob + default_prob.apply_scale (1, 2)) + / (node->m_c->m_subtree_prob + default_prob)); + + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), + GT_EXPR, test_bb, p); + default_prob = default_prob.apply_scale (1, 2); + + /* Value belongs to this node or to the left-hand subtree. */ + p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob); + bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), + GE_EXPR, node->m_c->m_case_bb, p); + + /* 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 (bb && m_default_bb) + emit_jump (bb, m_default_bb); + + bb = emit_case_nodes (test_bb, index, node->m_right, + 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. */ + tree lhs, rhs; + generate_range_test (bb, index, node->m_c->get_low (), + node->m_c->get_high (), &lhs, &rhs); + p = default_prob / (node->m_c->m_subtree_prob + default_prob); + + bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, + m_default_bb, p); + + emit_jump (bb, node->m_c->m_case_bb); + return NULL; + } + } return bb; } diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index 726d54a..37ed219 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -72,6 +72,13 @@ struct cluster /* Emit GIMPLE code to handle the cluster. */ virtual void emit (tree, tree, tree, basic_block) = 0; + /* Return true if a cluster handles only a single case value and the + value is not a range. */ + virtual bool is_single_value_p () + { + return false; + } + /* 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) @@ -161,6 +168,11 @@ struct simple_cluster: public cluster gcc_unreachable (); } + bool is_single_value_p () + { + return tree_int_cst_equal (get_low (), get_high ()); + } + /* Low value of the case. */ tree m_low; @@ -435,6 +447,12 @@ struct case_tree_node /* Empty Constructor. */ case_tree_node (); + /* Return true when it has a child. */ + bool has_child () + { + return m_left != NULL || m_right != NULL; + } + /* Left son in binary tree. */ case_tree_node *m_left; @@ -578,6 +596,12 @@ struct switch_decision_tree basic_block label_bb, profile_probability prob); + /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. + PROB is the probability of jumping to LABEL_BB. */ + static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1, + basic_block label_bb, + profile_probability prob); + /* Reset the aux field of all outgoing edges of switch basic block. */ static inline void reset_out_edges_aux (gswitch *swtch); |