diff options
| author | Martin Liska <mliska@suse.cz> | 2018-09-03 09:51:56 +0200 |
|---|---|---|
| committer | Martin Liska <marxin@gcc.gnu.org> | 2018-09-03 07:51:56 +0000 |
| commit | add4cbca8cf60d1108959de10a6c4b66d90464dc (patch) | |
| tree | 42056a80e427e22c26a9f90994acf4d459f9b414 /gcc/tree-switch-conversion.c | |
| parent | 106fd43fee5e964ddf3017cfd3de1046978d490d (diff) | |
Make __builtin_expect effective in switch statements (PR middle-end/PR59521).
2018-09-03 Martin Liska <mliska@suse.cz>
PR middle-end/59521
* predict.c (set_even_probabilities): Add likely_edges
argument and handle cases where we have precisely one
likely edge.
(combine_predictions_for_bb): Catch also likely_edges.
(tree_predict_by_opcode): Handle gswitch statements.
* tree-cfg.h (find_case_label_for_value): New declaration.
(find_taken_edge_switch_expr): Likewise.
* tree-switch-conversion.c (switch_decision_tree::balance_case_nodes):
Find pivot in decision tree based on probabily, not by number of
nodes.
2018-09-03 Martin Liska <mliska@suse.cz>
PR middle-end/59521
* c-c++-common/pr59521-1.c: New test.
* c-c++-common/pr59521-2.c: New test.
* gcc.dg/tree-prof/pr59521-3.c: New test.
From-SVN: r264050
Diffstat (limited to 'gcc/tree-switch-conversion.c')
| -rw-r--r-- | gcc/tree-switch-conversion.c | 46 |
1 files changed, 22 insertions, 24 deletions
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 7e4f34c71f8..d7d1c3972a0 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1914,6 +1914,7 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head, int ranges = 0; case_tree_node **npp; case_tree_node *left; + profile_probability prob = profile_probability::never (); /* Count the number of entries on branch. Also count the ranges. */ @@ -1923,6 +1924,7 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head, ranges++; i++; + prob += np->m_c->m_prob; np = np->m_right; } @@ -1931,39 +1933,35 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head, /* Split this list if it is long enough for that to help. */ npp = head; left = *npp; + profile_probability pivot_prob = prob.apply_scale (1, 2); - /* 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. */ + while (1) { - /* 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; - } + /* Skip nodes while their probability does not reach + that amount. */ + prob -= (*npp)->m_c->m_prob; + if (prob.initialized_p () + && (prob < pivot_prob || ! (*npp)->m_right)) + break; + npp = &(*npp)->m_right; } - *head = np = *npp; - *npp = 0; + + np = *npp; + *npp = 0; + *head = np; np->m_parent = parent; - np->m_left = left; + np->m_left = left == np ? NULL : left; /* 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; + if (np->m_left) + np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob; + if (np->m_right) + np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob; } else { |