On 08/31/2018 03:10 PM, Jan Hubicka wrote:
>>
>> 2018-08-23 Martin Liska <mli...@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 <mli...@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)
Hello.
Thanks for review.
>
> Please add/update documentation of set_even_probabilities.
Done.
>> {
>> 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.
According to my Cauldron 2017 slides, it looks that majority of switch
statements have
# of cases equal to # of BB. That means a shared edge in between multiple cases
is not so common :) But yes, it's not ideal.
>> 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?
Eventually not needed.
>
>> 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, fixed as:
if (prob.initialized_p ()
&& (prob < pivot_prob || ! (*npp)->m_right))
break;
Hope it's fine. I'm going to install the patch.
Martin
>
> OK with those changes.
> Honza
>
