[PATCHv3][PR 59521] Respect __builtin_expect in switch statements
Jan Hubicka
hubicka@ucw.cz
Fri Aug 31 13:10:00 GMT 2018
>
> 2018-08-23 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.c (find_taken_edge_switch_expr): Remove
> const quantifier.
> (find_case_label_for_value): Likewise.
> * 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.
>
> gcc/testsuite/ChangeLog:
>
> 2018-08-23 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.
> ---
> gcc/predict.c | 96 +++++++++++++++++-----
> 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 | 10 +--
> gcc/tree-cfg.h | 2 +
> gcc/tree-switch-conversion.c | 45 +++++-----
> 7 files changed, 168 insertions(+), 49 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/predict.c b/gcc/predict.c
> index 8c8e79153fc..db1fe737cb4 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -831,7 +831,8 @@ unlikely_executed_bb_p (basic_block bb)
>
> static void
> set_even_probabilities (basic_block bb,
> - hash_set<edge> *unlikely_edges = NULL)
> + hash_set<edge> *unlikely_edges = NULL,
> + hash_set<edge_prediction *> *likely_edges = NULL)
Please add/update documentation of set_even_probabilities.
> {
> unsigned nedges = 0, unlikely_count = 0;
> edge e = NULL;
> @@ -843,7 +844,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 +853,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 +1204,7 @@ combine_predictions_for_bb (basic_block bb, bool dry_run)
> if (nedges != 2)
> {
> hash_set<edge> unlikely_edges (4);
> + hash_set<edge_prediction *> 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 +1212,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);
Of course we are losing info here if there are multiple cases with same target basic block...
It may be possible to keep the information by adding histogram to the stmt.
> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
> index b021fb0f97b..738e0e7fe7f 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);
Why do you remove const?
> static void lower_phi_internal_fn ();
>
> void
> @@ -2436,8 +2434,8 @@ 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
> -find_taken_edge_switch_expr (const gswitch *switch_stmt, tree val)
> +edge
> +find_taken_edge_switch_expr (gswitch *switch_stmt, tree val)
> {
> basic_block dest_bb;
> edge e;
> @@ -2466,8 +2464,8 @@ 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
> -find_case_label_for_value (const gswitch *switch_stmt, tree val)
> +tree
> +find_case_label_for_value (gswitch *switch_stmt, tree val)
> {
> size_t low, high, n = gimple_switch_num_labels (switch_stmt);
> tree default_case = gimple_switch_default_label (switch_stmt);
> diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
> index 349a9543168..10ec50e95fd 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 (gswitch *switch_stmt, tree val);
> +extern edge find_taken_edge_switch_expr (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 a31ff94b895..5e4876474f9 100644
> --- a/gcc/tree-switch-conversion.c
> +++ b/gcc/tree-switch-conversion.c
> @@ -1921,6 +1921,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. */
>
> @@ -1930,6 +1931,7 @@ switch_decision_tree::balance_case_nodes (case_tree_node **head,
> ranges++;
>
> i++;
> + prob += np->m_c->m_prob;
> np = np->m_right;
> }
>
> @@ -1938,39 +1940,34 @@ 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 <= pivot_prob || ! (*npp)->m_right)
> + break;
> + npp = &(*npp)->m_right;
You probably want to verify that probability is initialized and pivot_prob is not
same as prob. Otherwise the decisison will also degenerate when all probailities
are zero or such.
OK with those changes.
Honza
More information about the Gcc-patches
mailing list