This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCHv3][PR 59521] Respect __builtin_expect in switch statements


> 
> 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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]