From 44b41fe75b9e1236282779a11f48c40bb1a8fa2d Mon Sep 17 00:00:00 2001 From: marxin Date: Mon, 3 Sep 2018 07:51:56 +0000 Subject: [PATCH] Make __builtin_expect effective in switch statements (PR middle-end/PR59521). 2018-09-03 Martin Liska 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 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. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@264050 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 14 ++++ gcc/predict.c | 100 +++++++++++++++++++++++------ gcc/testsuite/ChangeLog | 7 ++ gcc/testsuite/c-c++-common/pr59521-1.c | 15 +++++ gcc/testsuite/c-c++-common/pr59521-2.c | 15 +++++ gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c | 34 ++++++++++ gcc/tree-cfg.c | 6 +- gcc/tree-cfg.h | 2 + gcc/tree-switch-conversion.c | 46 +++++++------ 9 files changed, 191 insertions(+), 48 deletions(-) create mode 100644 gcc/testsuite/c-c++-common/pr59521-1.c create mode 100644 gcc/testsuite/c-c++-common/pr59521-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index bb492bf31f4..71bf60fffaa 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2018-09-03 Martin Liska + + 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-02 Gerald Pfeifer * doc/standards.texi (Standards): Update Objective-C reference. diff --git a/gcc/predict.c b/gcc/predict.c index ca6a901cd56..51145526d2a 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -827,11 +827,14 @@ unlikely_executed_bb_p (basic_block bb) /* We can not predict the probabilities of outgoing edges of bb. Set them evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute even probability for all edges not mentioned in the set. These edges - are given PROB_VERY_UNLIKELY probability. */ + are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES, + if we have exactly one likely edge, make the other edges predicted + as not probable. */ static void set_even_probabilities (basic_block bb, - hash_set *unlikely_edges = NULL) + hash_set *unlikely_edges = NULL, + hash_set *likely_edges = NULL) { unsigned nedges = 0, unlikely_count = 0; edge e = NULL; @@ -843,7 +846,7 @@ set_even_probabilities (basic_block bb, all -= e->probability; else if (!unlikely_executed_edge_p (e)) { - nedges ++; + nedges++; if (unlikely_edges != NULL && unlikely_edges->contains (e)) { all -= profile_probability::very_unlikely (); @@ -852,26 +855,54 @@ set_even_probabilities (basic_block bb, } /* Make the distribution even if all edges are unlikely. */ + unsigned likely_count = likely_edges ? likely_edges->elements () : 0; if (unlikely_count == nedges) { unlikely_edges = NULL; unlikely_count = 0; } - unsigned c = nedges - unlikely_count; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->probability.initialized_p ()) - ; - else if (!unlikely_executed_edge_p (e)) - { - if (unlikely_edges != NULL && unlikely_edges->contains (e)) - e->probability = profile_probability::very_unlikely (); + /* If we have one likely edge, then use its probability and distribute + remaining probabilities as even. */ + if (likely_count == 1) + { + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->probability.initialized_p ()) + ; + else if (!unlikely_executed_edge_p (e)) + { + edge_prediction *prediction = *likely_edges->begin (); + int p = prediction->ep_probability; + profile_probability prob + = profile_probability::from_reg_br_prob_base (p); + profile_probability remainder = prob.invert (); + + if (prediction->ep_edge == e) + e->probability = prob; + else + e->probability = remainder.apply_scale (1, nedges - 1); + } else - e->probability = all.apply_scale (1, c).guessed (); - } - else - e->probability = profile_probability::never (); + e->probability = profile_probability::never (); + } + else + { + /* Make all unlikely edges unlikely and the rest will have even + probability. */ + unsigned scale = nedges - unlikely_count; + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->probability.initialized_p ()) + ; + else if (!unlikely_executed_edge_p (e)) + { + if (unlikely_edges != NULL && unlikely_edges->contains (e)) + e->probability = profile_probability::very_unlikely (); + else + e->probability = all.apply_scale (1, scale); + } + else + e->probability = profile_probability::never (); + } } /* Add REG_BR_PROB note to JUMP with PROB. */ @@ -1175,6 +1206,7 @@ combine_predictions_for_bb (basic_block bb, bool dry_run) if (nedges != 2) { hash_set unlikely_edges (4); + hash_set likely_edges (4); /* Identify all edges that have a probability close to very unlikely. Doing the approach for very unlikely doesn't worth for doing as @@ -1182,11 +1214,16 @@ combine_predictions_for_bb (basic_block bb, bool dry_run) edge_prediction **preds = bb_predictions->get (bb); if (preds) for (pred = *preds; pred; pred = pred->ep_next) - if (pred->ep_probability <= PROB_VERY_UNLIKELY) - unlikely_edges.add (pred->ep_edge); + { + if (pred->ep_probability <= PROB_VERY_UNLIKELY) + unlikely_edges.add (pred->ep_edge); + if (pred->ep_probability >= PROB_VERY_LIKELY + || pred->ep_predictor == PRED_BUILTIN_EXPECT) + likely_edges.add (pred); + } if (!dry_run) - set_even_probabilities (bb, &unlikely_edges); + set_even_probabilities (bb, &unlikely_edges, &likely_edges); clear_bb_predictions (bb); if (dump_file) { @@ -2575,7 +2612,30 @@ tree_predict_by_opcode (basic_block bb) enum br_predictor predictor; HOST_WIDE_INT probability; - if (!stmt || gimple_code (stmt) != GIMPLE_COND) + if (!stmt) + return; + + if (gswitch *sw = dyn_cast (stmt)) + { + tree index = gimple_switch_index (sw); + tree val = expr_expected_value (index, auto_bitmap (), + &predictor, &probability); + if (val && TREE_CODE (val) == INTEGER_CST) + { + edge e = find_taken_edge_switch_expr (sw, val); + if (predictor == PRED_BUILTIN_EXPECT) + { + int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY); + gcc_assert (percent >= 0 && percent <= 100); + predict_edge (e, PRED_BUILTIN_EXPECT, + HITRATE (percent)); + } + else + predict_edge_def (e, predictor, TAKEN); + } + } + + if (gimple_code (stmt) != GIMPLE_COND) return; FOR_EACH_EDGE (then_edge, ei, bb->succs) if (then_edge->flags & EDGE_TRUE_VALUE) diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index c192dcc3611..e4eaeb7ef82 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,10 @@ +2018-09-03 Martin Liska + + 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. + 2018-09-02 Bernd Edlinger * c-c++-common/array-init.c: New test. diff --git a/gcc/testsuite/c-c++-common/pr59521-1.c b/gcc/testsuite/c-c++-common/pr59521-1.c new file mode 100644 index 00000000000..32320b57052 --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr59521-1.c @@ -0,0 +1,15 @@ +/* { dg-options "-O2" } */ +/* { dg-do compile } */ + +extern int puts (const char *); + +void +f(int ch) { + switch (ch) { + case 3: puts("a"); break; + case 42: puts("e"); break; + case 333: puts("i"); break; + } +} + +/* { dg-final { scan-assembler "cmp.*42,.*cmp.*333,.*cmp.*3," { target i?86-*-* x86_64-*-* } } } */ diff --git a/gcc/testsuite/c-c++-common/pr59521-2.c b/gcc/testsuite/c-c++-common/pr59521-2.c new file mode 100644 index 00000000000..3c48825b347 --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr59521-2.c @@ -0,0 +1,15 @@ +/* { dg-options "-O2" } */ +/* { dg-do compile } */ + +extern int puts (const char *); + +void +f(int ch) { + switch (__builtin_expect(ch, 333)) { + case 3: puts("a"); break; + case 42: puts("e"); break; + case 333: puts("i"); break; + } +} + +/* { dg-final { scan-assembler "cmp.*333,.*cmp.*3,.*cmp.*42," { target i?86-*-* x86_64-*-* } } } */ diff --git a/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c b/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c new file mode 100644 index 00000000000..497643bed3d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c @@ -0,0 +1,34 @@ +/* { dg-options "-O2 -save-temps" } */ + +#include + +__attribute__((noinline,noclone)) void +sink(const char *s) { + asm("" :: "r"(s)); +} + +void +foo(int ch) { + switch (ch) { + case 100: sink("100"); break; + case 10: sink("10"); break; + case 1: sink("1"); break; + } +} + +int main() +{ + for (int i = 0; i < 10000; i++) + { + int v; + if (i % 100 == 0) + v = 100; + else if(i % 10 == 0) + v = 10; + else + v = 1; + foo(v); + } +} + +/* { dg-final-use-not-autofdo { scan-assembler "\nfoo:\n.*cmp.*1,.*cmp.*10,.*cmp.*100" { target i?86-*-* x86_64-*-* } } } */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index cf12cb1f391..87979bc4d75 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -171,8 +171,6 @@ static bool gimple_can_merge_blocks_p (basic_block, basic_block); static void remove_bb (basic_block); static edge find_taken_edge_computed_goto (basic_block, tree); static edge find_taken_edge_cond_expr (const gcond *, tree); -static edge find_taken_edge_switch_expr (const gswitch *, tree); -static tree find_case_label_for_value (const gswitch *, tree); static void lower_phi_internal_fn (); void @@ -2436,7 +2434,7 @@ find_taken_edge_cond_expr (const gcond *cond_stmt, tree val) If VAL is NULL_TREE, then the current value of SWITCH_STMT's index is used. */ -static edge +edge find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val) { basic_block dest_bb; @@ -2466,7 +2464,7 @@ find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val) We can make optimal use here of the fact that the case labels are sorted: We can do a binary search for a case matching VAL. */ -static tree +tree find_case_label_for_value (const gswitch *switch_stmt, tree val) { size_t low, high, n = gimple_switch_num_labels (switch_stmt); diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h index 349a9543168..95c070a2fb2 100644 --- a/gcc/tree-cfg.h +++ b/gcc/tree-cfg.h @@ -102,6 +102,8 @@ extern tree gimplify_build2 (gimple_stmt_iterator *, enum tree_code, extern tree gimplify_build1 (gimple_stmt_iterator *, enum tree_code, tree, tree); extern void extract_true_false_edges_from_block (basic_block, edge *, edge *); +extern tree find_case_label_for_value (const gswitch *switch_stmt, tree val); +extern edge find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val); extern unsigned int execute_fixup_cfg (void); extern unsigned int split_critical_edges (void); extern basic_block insert_cond_bb (basic_block, gimple *, gimple *, 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 { -- 2.11.4.GIT