Propagate profile counts after switch case expansion (issue5896043)

This patch propagates execution count of thee case labels of a
switch-case statement after its expansion. Bootstraps and all
tests pass. OK for trunk?

2012-03-23   Easwaran Raman  <eraman@google.com>

	* cfgbuild.c (non_zero_profile_counts): New function.
	(compute_outgoing_frequencies): If at least one successor of a
	BB has non-zero profile count, retain the counts.
	* expr.c (do_tablejump): Add a REG_BR_PROB note on the
	jump to default label.
	(try_tablejump): Add a parameter to specify the probability
	of jumping to the default label.
	* expr.h (try_tablejump): Add a new parameter.
	* stmt.c (case_node): Add new fields COUNT and SUBTREE_COUNT.
	(add_case_node): Pass execution count of the case node and use
	it to initialize COUNT field.
	(case_probability): New macro.
	(expand_case): Propagate execution counts to generated
	branches using REG_BR_PROB notes.
	(emit_case_nodes): Likewise.
	(do_jump_if_equal): Pass probability for REG_BR_PROB note.
	(compute_subtree_counts): New function to compute
	SUBTREE_COUNT fields of case nodes.
	(add_prob_note_to_last_insn): Add a REG_BR_PROB note with the
	given probability to the last generated instruction.

gcc/testsuite/ChangeLog:
2012-03-23   Easwaran Raman  <eraman@google.com>
	* gcc.dg/tree-prof/switch-case-1.c: New test case.
	* gcc.dg/tree-prof/switch-case-2.c: New test case.


--
This patch is available for review at http://codereview.appspot.com/5896043

Some more background on this patch: Right now, while the execution
counts of different case labels of a switch statement are obtained
during profile collection, they are not propagated to RTL. Instead,
counts are regenerated at the RTL level using static heuristics that
tend to weigh branches equally which can cause poor optimization of
hot code. This patch ensures that the counts collected during profile
collection are correctly propagated allowing hot code to be better
optimized by RTL optimizations.  Patch tested on x86_64.

- Easwaran

On Fri, Mar 23, 2012 at 10:43 AM, Easwaran Raman <eraman@google.com> wrote:
> This patch propagates execution count of thee case labels of a
> switch-case statement after its expansion. Bootstraps and all
> tests pass. OK for trunk?
>
> 2012-03-23   Easwaran Raman  <eraman@google.com>
>
>        * cfgbuild.c (non_zero_profile_counts): New function.
>        (compute_outgoing_frequencies): If at least one successor of a
>        BB has non-zero profile count, retain the counts.
>        * expr.c (do_tablejump): Add a REG_BR_PROB note on the
>        jump to default label.
>        (try_tablejump): Add a parameter to specify the probability
>        of jumping to the default label.
>        * expr.h (try_tablejump): Add a new parameter.
>        * stmt.c (case_node): Add new fields COUNT and SUBTREE_COUNT.
>        (add_case_node): Pass execution count of the case node and use
>        it to initialize COUNT field.
>        (case_probability): New macro.
>        (expand_case): Propagate execution counts to generated
>        branches using REG_BR_PROB notes.
>        (emit_case_nodes): Likewise.
>        (do_jump_if_equal): Pass probability for REG_BR_PROB note.
>        (compute_subtree_counts): New function to compute
>        SUBTREE_COUNT fields of case nodes.
>        (add_prob_note_to_last_insn): Add a REG_BR_PROB note with the
>        given probability to the last generated instruction.
>
> gcc/testsuite/ChangeLog:
> 2012-03-23   Easwaran Raman  <eraman@google.com>
>        * gcc.dg/tree-prof/switch-case-1.c: New test case.
>        * gcc.dg/tree-prof/switch-case-2.c: New test case.
>
> diff --git a/gcc/cfgbuild.c b/gcc/cfgbuild.c
> index 692fea8..d75fbda 100644
> --- a/gcc/cfgbuild.c
> +++ b/gcc/cfgbuild.c
> @@ -534,6 +534,21 @@ find_bb_boundaries (basic_block bb)
>     purge_dead_tablejump_edges (bb, table);
>  }
>
> +/* Check if there is at least one edge in EDGES with a non-zero count
> +   field.  */
> +
> +static bool
> +non_zero_profile_counts ( VEC(edge,gc) *edges) {
> +  edge e;
> +  edge_iterator ei;
> +  FOR_EACH_EDGE(e, ei, edges)
> +    {
> +      if (e->count > 0)
> +        return true;
> +    }
> +  return false;
> +}
> +
>  /*  Assume that frequency of basic block B is known.  Compute frequencies
>     and probabilities of outgoing edges.  */
>
> @@ -569,6 +584,10 @@ compute_outgoing_frequencies (basic_block b)
>       e->count = b->count;
>       return;
>     }
> +  else if (non_zero_profile_counts (b->succs)){
> +    /*Profile counts already set, but REG_NOTE missing. Retain the counts.  */
> +    return;
> +  }
>   guess_outgoing_edge_probabilities (b);
>   if (b->count)
>     FOR_EACH_EDGE (e, ei, b->succs)
> diff --git a/gcc/expr.c b/gcc/expr.c
> index f9de908..fb8eef9 100644
> --- a/gcc/expr.c
> +++ b/gcc/expr.c
> @@ -156,7 +156,7 @@ static rtx do_store_flag (sepops, rtx, enum machine_mode);
>  #ifdef PUSH_ROUNDING
>  static void emit_single_push_insn (enum machine_mode, rtx, tree);
>  #endif
> -static void do_tablejump (rtx, enum machine_mode, rtx, rtx, rtx);
> +static void do_tablejump (rtx, enum machine_mode, rtx, rtx, rtx, int);
>  static rtx const_vector_from_tree (tree);
>  static void write_complex_part (rtx, rtx, bool);
>
> @@ -10694,11 +10694,13 @@ try_casesi (tree index_type, tree index_expr, tree minval, tree range,
>    TABLE_LABEL is a CODE_LABEL rtx for the table itself.
>
>    DEFAULT_LABEL is a CODE_LABEL rtx to jump to if the
> -   index value is out of range.  */
> +   index value is out of range.
> +   DEFAULT_PROBABILITY is the probability of jumping to the
> +   DEFAULT_LABEL.  */
>
>  static void
>  do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label,
> -             rtx default_label)
> +             rtx default_label, int default_probability)
>  {
>   rtx temp, vector;
>
> @@ -10714,8 +10716,16 @@ do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label,
>      the maximum value of the range.  */
>
>   if (default_label)
> -    emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
> -                            default_label);
> +    {
> +      emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
> +                              default_label);
> +      if (default_probability != -1)
> +        {
> +          rtx jump_insn = get_last_insn();
> +          add_reg_note (jump_insn, REG_BR_PROB, GEN_INT (default_probability));
> +        }
> +    }
> +
>
>   /* If index is in range, it must fit in Pmode.
>      Convert to Pmode so we can index with it.  */
> @@ -10758,7 +10768,7 @@ do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label,
>
>  int
>  try_tablejump (tree index_type, tree index_expr, tree minval, tree range,
> -              rtx table_label, rtx default_label)
> +              rtx table_label, rtx default_label, int default_probability)
>  {
>   rtx index;
>
> @@ -10776,7 +10786,7 @@ try_tablejump (tree index_type, tree index_expr, tree minval, tree range,
>                               TYPE_MODE (TREE_TYPE (range)),
>                               expand_normal (range),
>                               TYPE_UNSIGNED (TREE_TYPE (range))),
> -               table_label, default_label);
> +               table_label, default_label, default_probability);
>   return 1;
>  }
>
> diff --git a/gcc/expr.h b/gcc/expr.h
> index 0096367..9691041 100644
> --- a/gcc/expr.h
> +++ b/gcc/expr.h
> @@ -484,7 +484,7 @@ extern void do_compare_rtx_and_jump (rtx, rtx, enum rtx_code, int,
>
>  /* Two different ways of generating switch statements.  */
>  extern int try_casesi (tree, tree, tree, tree, rtx, rtx, rtx);
> -extern int try_tablejump (tree, tree, tree, tree, rtx, rtx);
> +extern int try_tablejump (tree, tree, tree, tree, rtx, rtx, int);
>
>  /* Functions from alias.c */
>  #include "alias.h"
> diff --git a/gcc/stmt.c b/gcc/stmt.c
> index 93d643a..9c6e211 100644
> --- a/gcc/stmt.c
> +++ b/gcc/stmt.c
> @@ -54,6 +54,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "pretty-print.h"
>  #include "bitmap.h"
>  #include "params.h"
> +#include "tree-flow.h"
>
>
>  /* Functions and data structures for expanding case statements.  */
> @@ -93,6 +94,7 @@ struct case_node
>   tree                 low;    /* Lowest index value for this label */
>   tree                 high;   /* Highest index value for this label */
>   tree                 code_label; /* Label to jump to when node matches */
> +  gcov_type             subtree_count, count; /* Execution counts */
>  };
>
>  typedef struct case_node case_node;
> @@ -122,12 +124,14 @@ static bool lshift_cheap_p (void);
>  static int case_bit_test_cmp (const void *, const void *);
>  static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
>  static void balance_case_nodes (case_node_ptr *, case_node_ptr);
> +static void compute_subtree_counts(case_node_ptr);
>  static int node_has_low_bound (case_node_ptr, tree);
>  static int node_has_high_bound (case_node_ptr, tree);
>  static int node_is_bounded (case_node_ptr, tree);
> -static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
> +static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree);
>  static struct case_node *add_case_node (struct case_node *, tree,
> -                                        tree, tree, tree, alloc_pool);
> +                                        tree, tree, tree, gcov_type,
> +                                        alloc_pool);
>
>
>  /* Return the rtx-label that corresponds to a LABEL_DECL,
> @@ -1929,11 +1933,12 @@ expand_stack_restore (tree var)
>    fed to us in descending order from the sorted vector of case labels used
>    in the tree part of the middle end.  So the list we construct is
>    sorted in ascending order.  The bounds on the case range, LOW and HIGH,
> -   are converted to case's index type TYPE.  */
> +   are converted to case's index type TYPE. COUNT is the expected number
> +   of executions of the case label.  */
>
>  static struct case_node *
>  add_case_node (struct case_node *head, tree type, tree low, tree high,
> -               tree label, alloc_pool case_node_pool)
> +               tree label, gcov_type count, alloc_pool case_node_pool)
>  {
>   tree min_value, max_value;
>   struct case_node *r;
> @@ -1992,6 +1997,7 @@ add_case_node (struct case_node *head, tree type, tree low, tree high,
>                                TREE_INT_CST_HIGH (high));
>   r->code_label = label;
>   r->parent = r->left = NULL;
> +  r->count = count;
>   r->right = head;
>   return r;
>  }
> @@ -2189,6 +2195,8 @@ case_values_threshold (void)
>   return threshold;
>  }
>
> +#define case_probability(x, y) ((y) ? ((x) * REG_BR_PROB_BASE  / (y))  : -1)
> +
>  /* Terminate a case (Pascal/Ada) or switch (C) statement
>    in which ORIG_INDEX is the expression to be tested.
>    If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
> @@ -2212,6 +2220,7 @@ expand_case (gimple stmt)
>   tree index_expr = gimple_switch_index (stmt);
>   tree index_type = TREE_TYPE (index_expr);
>   int unsignedp = TYPE_UNSIGNED (index_type);
> +  basic_block bb = gimple_bb (stmt);
>
>   /* The insn after which the case dispatch should finally
>      be emitted.  Zero for a dummy.  */
> @@ -2224,6 +2233,8 @@ expand_case (gimple stmt)
>   /* Label to jump to if no case matches.  */
>   tree default_label_decl = NULL_TREE;
>
> +  gcov_type default_count = 0;
> +
>   alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
>                                                  sizeof (struct case_node),
>                                                  100);
> @@ -2235,7 +2246,9 @@ expand_case (gimple stmt)
>     {
>       tree elt;
>       bitmap label_bitmap;
> +      edge case_edge = NULL, default_edge = NULL;
>       int stopi = 0;
> +      bool has_gaps = false;
>
>       /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
>         expressions being INTEGER_CST.  */
> @@ -2246,12 +2259,17 @@ expand_case (gimple stmt)
>       if (!CASE_LOW (elt) && !CASE_HIGH (elt))
>        {
>          default_label_decl = CASE_LABEL (elt);
> +          case_edge = EDGE_SUCC(bb, 0);
> +          default_edge = case_edge;
> +          default_count = case_edge->count;
>          stopi = 1;
>        }
>
>       for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
>        {
>          tree low, high;
> +          basic_block case_bb;
> +          edge case_edge;
>          elt = gimple_switch_label (stmt, i);
>
>          low = CASE_LOW (elt);
> @@ -2261,9 +2279,11 @@ expand_case (gimple stmt)
>          /* Discard empty ranges.  */
>          if (high && tree_int_cst_lt (high, low))
>            continue;
> -
> +          case_bb = label_to_block (CASE_LABEL(elt));
> +          case_edge = find_edge (bb, case_bb);
>          case_list = add_case_node (case_list, index_type, low, high,
> -                                     CASE_LABEL (elt), case_node_pool);
> +                                     CASE_LABEL (elt), case_edge->count,
> +                                     case_node_pool);
>        }
>
>
> @@ -2287,6 +2307,15 @@ expand_case (gimple stmt)
>            }
>          else
>            {
> +              tree min_minus_one = fold_build2 (MINUS_EXPR, index_type,
> +                                                n->low,
> +                                                build_int_cst (index_type, 1));
> +              /* case_list is sorted in increasing order. If the minval - 1 of
> +                 this node is greater than the previous maxval, then there is a
> +                 gap. If jump table expansion is used, this gap will be filled
> +                 with the default label.  */
> +             if (tree_int_cst_lt (maxval, min_minus_one))
> +               has_gaps = true;
>              if (tree_int_cst_lt (n->low, minval))
>                minval = n->low;
>              if (tree_int_cst_lt (maxval, n->high))
> @@ -2398,18 +2427,24 @@ expand_case (gimple stmt)
>
>          use_cost_table = estimate_case_costs (case_list);
>          balance_case_nodes (&case_list, NULL);
> -         emit_case_nodes (index, case_list, default_label, index_type);
> +          compute_subtree_counts (case_list);
> +         emit_case_nodes (index, case_list, default_label, default_count,
> +                           index_type);
>          if (default_label)
>            emit_jump (default_label);
>        }
>       else
>        {
>          rtx fallback_label = label_rtx (case_list->code_label);
> +          edge e;
> +          edge_iterator ei;
> +          gcov_type count = bb->count;
>          table_label = gen_label_rtx ();
>          if (! try_casesi (index_type, index_expr, minval, range,
>                            table_label, default_label, fallback_label))
>            {
>              bool ok;
> +              int default_probability;
>
>              /* Index jumptables from zero for suitable values of
>                  minval to avoid a subtraction.  */
> @@ -2419,12 +2454,40 @@ expand_case (gimple stmt)
>                {
>                  minval = build_int_cst (index_type, 0);
>                  range = maxval;
> +                  has_gaps = true;
>                }
> +              if (has_gaps)
> +                {
> +                  /* There is at least one entry in the jump table that jumps
> +                     to default label. The default label can either be reached
> +                     through the indirect jump or the direct conditional jump
> +                     before that. Split the probability of reaching the
> +                     default label among these two jumps.  */
> +                  default_probability = case_probability (default_count/2,
> +                                                          bb->count);
> +                  default_count /= 2;
> +                  count -= default_count;
> +                }
> +              else
> +                {
> +                  default_probability = case_probability (default_count,
> +                                                          bb->count);
> +                  count -= default_count;
> +                  default_count = 0;
> +                }
>
>              ok = try_tablejump (index_type, index_expr, minval, range,
> -                                 table_label, default_label);
> +                                 table_label, default_label,
> +                                  default_probability);
>              gcc_assert (ok);
>            }
> +          if (default_edge)
> +            {
> +              default_edge->count = default_count;
> +              if (count)
> +                FOR_EACH_EDGE (e, ei, bb->succs)
> +                  e->probability = e->count * REG_BR_PROB_BASE / count;
> +            }
>
>          /* Get table of labels to jump to, in order of case index.  */
>
> @@ -2485,14 +2548,15 @@ expand_case (gimple stmt)
>   free_alloc_pool (case_node_pool);
>  }
>
> -/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.  */
> +/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
> +   PROB is the probability of jumping to LABEL.  */
>
>  static void
>  do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
> -                 int unsignedp)
> +                 int unsignedp, int prob)
>  {
>   do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
> -                          NULL_RTX, NULL_RTX, label, -1);
> +                          NULL_RTX, NULL_RTX, label, prob);
>  }
>
>  /* Not all case values are encountered equally.  This function
> @@ -2575,6 +2639,26 @@ estimate_case_costs (case_node_ptr node)
>   return 1;
>  }
>
> +/*  Compute the SUBTREE_COUNT of all nodes in the tree rooted at NODE.  */
> +
> +static void
> +compute_subtree_counts (case_node_ptr node)
> +{
> +  if (node == NULL)
> +    return;
> +  node->subtree_count = node->count;
> +  if (node->left)
> +    {
> +      compute_subtree_counts (node->left);
> +      node->subtree_count += node->left->subtree_count;
> +    }
> +  if (node->right)
> +    {
> +      compute_subtree_counts (node->right);
> +      node->subtree_count += node->right->subtree_count;
> +    }
> +}
> +
>  /* Take an ordered list of case nodes
>    and transform them into a near optimal binary tree,
>    on the assumption that any target code selection value is as
> @@ -2800,6 +2886,20 @@ node_is_bounded (case_node_ptr node, tree index_type)
>          && node_has_high_bound (node, index_type));
>  }
>
> +
> +/* Attach a REG_BR_PROB note to the last created RTX instruction if
> +   PROBABILITY is not -1.  */
> +
> +static void
> +add_prob_note_to_last_insn(int probability)
> +{
> +  if (probability != -1)
> +    {
> +      rtx jump_insn = get_last_insn();
> +      add_reg_note (jump_insn, REG_BR_PROB, GEN_INT (probability));
> +    }
> +}
> +
>  /* Emit step-by-step code to select a case for the value of INDEX.
>    The thus generated decision tree follows the form of the
>    case-node binary tree NODE, whose nodes represent test conditions.
> @@ -2828,10 +2928,12 @@ node_is_bounded (case_node_ptr node, tree index_type)
>
>  static void
>  emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
> -                tree index_type)
> +                int default_count, tree index_type)
>  {
>   /* If INDEX has an unsigned type, we must make unsigned branches.  */
>   int unsignedp = TYPE_UNSIGNED (index_type);
> +  int probability;
> +  gcov_type count = node->count, subtree_count = node->subtree_count;
>   enum machine_mode mode = GET_MODE (index);
>   enum machine_mode imode = TYPE_MODE (index_type);
>
> @@ -2846,15 +2948,17 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>
>   else if (tree_int_cst_equal (node->low, node->high))
>     {
> +      probability = case_probability (count, subtree_count + default_count);
>       /* Node is single valued.  First see if the index expression matches
>         this node and then check our children, if any.  */
> -
>       do_jump_if_equal (mode, index,
>                        convert_modes (mode, imode,
>                                       expand_normal (node->low),
>                                       unsignedp),
> -                       label_rtx (node->code_label), unsignedp);
> -
> +                       label_rtx (node->code_label), unsignedp, probability);
> +      /* Since this case is taken at this point, reduce its weight from
> +         subtree_weight.  */
> +      subtree_count -= count;
>       if (node->right != 0 && node->left != 0)
>        {
>          /* This node has children on both sides.
> @@ -2872,7 +2976,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       GT, NULL_RTX, mode, unsignedp,
>                                       label_rtx (node->right->code_label));
> -             emit_case_nodes (index, node->left, default_label, index_type);
> +              probability = case_probability (node->right->count,
> +                                              subtree_count + default_count);
> +              add_prob_note_to_last_insn (probability);
> +             emit_case_nodes (index, node->left, default_label, default_count,
> +                               index_type);
>            }
>
>          else if (node_is_bounded (node->left, index_type))
> @@ -2884,7 +2992,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       LT, NULL_RTX, mode, unsignedp,
>                                       label_rtx (node->left->code_label));
> -             emit_case_nodes (index, node->right, default_label, index_type);
> +              probability = case_probability (node->left->count,
> +                                              subtree_count + default_count);
> +              add_prob_note_to_last_insn (probability);
> +             emit_case_nodes (index, node->right, default_label, default_count, index_type);
>            }
>
>          /* If both children are single-valued cases with no
> @@ -2902,21 +3013,25 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>
>              /* See if the value matches what the right hand side
>                 wants.  */
> +              probability = case_probability (node->right->count,
> +                                              subtree_count + default_count);
>              do_jump_if_equal (mode, index,
>                                convert_modes (mode, imode,
>                                               expand_normal (node->right->low),
>                                               unsignedp),
>                                label_rtx (node->right->code_label),
> -                               unsignedp);
> +                               unsignedp, probability);
>
>              /* See if the value matches what the left hand side
>                 wants.  */
> +              probability = case_probability (node->left->count,
> +                                              subtree_count + default_count);
>              do_jump_if_equal (mode, index,
>                                convert_modes (mode, imode,
>                                               expand_normal (node->left->low),
>                                               unsignedp),
>                                label_rtx (node->left->code_label),
> -                               unsignedp);
> +                               unsignedp, probability);
>            }
>
>          else
> @@ -2936,10 +3051,18 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       GT, NULL_RTX, mode, unsignedp,
>                                       label_rtx (test_label));
> +              /* The default label could be reached either through the right
> +                 subtree or the left subtree. Divide the probability
> +                 equally.  */
> +              probability = case_probability (
> +                  node->right->subtree_count + default_count/2,
> +                  subtree_count + default_count);
> +              default_count /= 2;
> +              add_prob_note_to_last_insn (probability);
>
>              /* Value must be on the left.
>                 Handle the left-hand subtree.  */
> -             emit_case_nodes (index, node->left, default_label, index_type);
> +             emit_case_nodes (index, node->left, default_label, default_count, index_type);
>              /* If left-hand subtree does nothing,
>                 go to default.  */
>              if (default_label)
> @@ -2947,7 +3070,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>
>              /* Code branches here for the right-hand subtree.  */
>              expand_label (test_label);
> -             emit_case_nodes (index, node->right, default_label, index_type);
> +             emit_case_nodes (index, node->right, default_label, default_count, index_type);
>            }
>        }
>
> @@ -2972,21 +3095,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                            unsignedp),
>                                           LT, NULL_RTX, mode, unsignedp,
>                                           default_label);
> +                  probability = case_probability (default_count/2,
> +                                                  subtree_count + default_count);
> +                  default_count /= 2;
> +                  add_prob_note_to_last_insn (probability);
>                }
>
> -             emit_case_nodes (index, node->right, default_label, index_type);
> +             emit_case_nodes (index, node->right, default_label, default_count, index_type);
>            }
>          else
> -           /* We cannot process node->right normally
> -              since we haven't ruled out the numbers less than
> -              this node's value.  So handle node->right explicitly.  */
> -           do_jump_if_equal (mode, index,
> -                             convert_modes
> -                             (mode, imode,
> -                              expand_normal (node->right->low),
> -                              unsignedp),
> -                             label_rtx (node->right->code_label), unsignedp);
> -       }
> +            {
> +              probability = case_probability (node->right->subtree_count,
> +                                              subtree_count + default_count);
> +             /* We cannot process node->right normally
> +                since we haven't ruled out the numbers less than
> +                this node's value.  So handle node->right explicitly.  */
> +             do_jump_if_equal (mode, index,
> +                               convert_modes
> +                               (mode, imode,
> +                                expand_normal (node->right->low),
> +                                unsignedp),
> +                               label_rtx (node->right->code_label), unsignedp, probability);
> +            }
> +         }
>
>       else if (node->right == 0 && node->left != 0)
>        {
> @@ -3003,20 +3134,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                            unsignedp),
>                                           GT, NULL_RTX, mode, unsignedp,
>                                           default_label);
> +                  probability = case_probability (
> +                      default_count/2, subtree_count + default_count);
> +                  default_count /= 2;
> +                  add_prob_note_to_last_insn (probability);
>                }
>
> -             emit_case_nodes (index, node->left, default_label, index_type);
> +             emit_case_nodes (index, node->left, default_label,
> +                               default_count, index_type);
>            }
>          else
> -           /* We cannot process node->left normally
> -              since we haven't ruled out the numbers less than
> -              this node's value.  So handle node->left explicitly.  */
> -           do_jump_if_equal (mode, index,
> -                             convert_modes
> -                             (mode, imode,
> -                              expand_normal (node->left->low),
> -                              unsignedp),
> -                             label_rtx (node->left->code_label), unsignedp);
> +            {
> +              probability = case_probability (node->left->subtree_count,
> +                                              subtree_count + default_count);
> +             /* We cannot process node->left normally
> +                since we haven't ruled out the numbers less than
> +                this node's value.  So handle node->left explicitly.  */
> +             do_jump_if_equal (mode, index,
> +                               convert_modes
> +                               (mode, imode,
> +                                expand_normal (node->left->low),
> +                                unsignedp),
> +                               label_rtx (node->left->code_label), unsignedp, probability);
> +            }
>        }
>     }
>   else
> @@ -3035,15 +3175,20 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>          tree test_label = 0;
>
>          if (node_is_bounded (node->right, index_type))
> -           /* Right hand node is fully bounded so we can eliminate any
> -              testing and branch directly to the target code.  */
> -           emit_cmp_and_jump_insns (index,
> -                                    convert_modes
> -                                    (mode, imode,
> -                                     expand_normal (node->high),
> -                                     unsignedp),
> -                                    GT, NULL_RTX, mode, unsignedp,
> -                                    label_rtx (node->right->code_label));
> +            {
> +             /* Right hand node is fully bounded so we can eliminate any
> +                testing and branch directly to the target code.  */
> +             emit_cmp_and_jump_insns (index,
> +                                      convert_modes
> +                                      (mode, imode,
> +                                       expand_normal (node->high),
> +                                       unsignedp),
> +                                      GT, NULL_RTX, mode, unsignedp,
> +                                      label_rtx (node->right->code_label));
> +              probability = case_probability (node->right->subtree_count,
> +                                              subtree_count + default_count);
> +              add_prob_note_to_last_insn (probability);
> +            }
>          else
>            {
>              /* Right hand node requires testing.
> @@ -3058,6 +3203,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       GT, NULL_RTX, mode, unsignedp,
>                                       label_rtx (test_label));
> +              probability = case_probability (node->right->subtree_count + default_count/2,
> +                                              subtree_count + default_count);
> +              default_count /= 2;
> +              add_prob_note_to_last_insn (probability);
>            }
>
>          /* Value belongs to this node or to the left-hand subtree.  */
> @@ -3069,9 +3218,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                    unsignedp),
>                                   GE, NULL_RTX, mode, unsignedp,
>                                   label_rtx (node->code_label));
> +          probability = case_probability (count, subtree_count + default_count);
> +          add_prob_note_to_last_insn (probability);
>
>          /* Handle the left-hand subtree.  */
> -         emit_case_nodes (index, node->left, default_label, index_type);
> +         emit_case_nodes (index, node->left, default_label, default_count, index_type);
>
>          /* If right node had to be handled later, do that now.  */
>
> @@ -3083,7 +3234,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                emit_jump (default_label);
>
>              expand_label (test_label);
> -             emit_case_nodes (index, node->right, default_label, index_type);
> +             emit_case_nodes (index, node->right, default_label, default_count, index_type);
>            }
>        }
>
> @@ -3100,6 +3251,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       LT, NULL_RTX, mode, unsignedp,
>                                       default_label);
> +              probability = case_probability (default_count/2,
> +                                              subtree_count + default_count);
> +              default_count /= 2;
> +              add_prob_note_to_last_insn (probability);
>            }
>
>          /* Value belongs to this node or to the right-hand subtree.  */
> @@ -3111,8 +3266,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                    unsignedp),
>                                   LE, NULL_RTX, mode, unsignedp,
>                                   label_rtx (node->code_label));
> +          probability = case_probability (count, subtree_count + default_count);
> +          add_prob_note_to_last_insn (probability);
>
> -         emit_case_nodes (index, node->right, default_label, index_type);
> +         emit_case_nodes (index, node->right, default_label, default_count, index_type);
>        }
>
>       else if (node->right == 0 && node->left != 0)
> @@ -3128,6 +3285,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       GT, NULL_RTX, mode, unsignedp,
>                                       default_label);
> +              probability = case_probability (default_count/2,
> +                                              subtree_count + default_count);
> +              default_count /= 2;
> +              add_prob_note_to_last_insn (probability);
>            }
>
>          /* Value belongs to this node or to the left-hand subtree.  */
> @@ -3139,8 +3300,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                    unsignedp),
>                                   GE, NULL_RTX, mode, unsignedp,
>                                   label_rtx (node->code_label));
> +          probability = case_probability (count, subtree_count + default_count);
> +          add_prob_note_to_last_insn (probability);
>
> -         emit_case_nodes (index, node->left, default_label, index_type);
> +         emit_case_nodes (index, node->left, default_label, default_count, index_type);
>        }
>
>       else
> @@ -3160,6 +3323,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       GT, NULL_RTX, mode, unsignedp,
>                                       default_label);
> +              probability = case_probability (default_count,
> +                                              subtree_count + default_count);
> +              add_prob_note_to_last_insn (probability);
>            }
>
>          else if (!low_bound && high_bound)
> @@ -3171,6 +3337,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>                                        unsignedp),
>                                       LT, NULL_RTX, mode, unsignedp,
>                                       default_label);
> +              probability = case_probability (default_count,
> +                                              subtree_count + default_count);
> +              add_prob_note_to_last_insn (probability);
>            }
>          else if (!low_bound && !high_bound)
>            {
> @@ -3192,6 +3361,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
>
>              emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
>                                       mode, 1, default_label);
> +              probability = case_probability (default_count,
> +                                              subtree_count + default_count);
> +              add_prob_note_to_last_insn (probability);
>            }
>
>          emit_jump (label_rtx (node->code_label));
> diff --git a/gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c b/gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c
> new file mode 100644
> index 0000000..ef094fa
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c
> @@ -0,0 +1,40 @@
> +/* { dg-options "-O2 -fdump-rtl-expand-blocks" } */
> +int g;
> +
> +__attribute__((noinline)) void foo (int  n)
> +{
> +  switch (n)
> +    {
> +    case 1:
> +      g++; break;
> +    case 2:
> +      g += 2; break;
> +    case 3:
> +      g += 1; break;
> +    case 4:
> +      g += 3; break;
> +    case 5:
> +      g += 4; break;
> +    case 6:
> +      g += 5; break;
> +    case 7:
> +      g += 6; break;
> +    case 8:
> +      g += 7; break;
> +    case 9:
> +      g += 8; break;
> +    default:
> +      g += 8; break;
> +   }
> +}
> +
> +int main ()
> +{
> + int i;
> + for (i = 0; i < 10000; i++)
> +   foo ((i * i) % 5);
> + return 0;
> +}
> +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 4000" 2 "expand"} } */
> +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 2000" 1 "expand"} } */
> +/* { dg-final-use { cleanup-rtl-dump "expand" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c b/gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c
> new file mode 100644
> index 0000000..8adc380
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c
> @@ -0,0 +1,40 @@
> +/* { dg-options "-O2 -fdump-rtl-expand-blocks" } */
> +int g;
> +
> +__attribute__((noinline)) void foo (int  n)
> +{
> +  switch (n)
> +    {
> +    case 99:
> +      g += 2; break;
> +    case 1:
> +      g++; break;
> +    case 100:
> +      g += 1; break;
> +    case 4:
> +      g += 3; break;
> +    case 5:
> +      g += 4; break;
> +    case 6:
> +      g += 5; break;
> +    case 7:
> +      g += 6; break;
> +    case 8:
> +      g += 7; break;
> +    case 9:
> +      g += 8; break;
> +    default:
> +      g += 8; break;
> +   }
> +}
> +
> +int main ()
> +{
> + int i;
> + for (i = 0; i < 10000; i++)
> +   foo ((i * i) % 5);
> + return 0;
> +}
> +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 4000" 2 "expand"} } */
> +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 2000" 1 "expand"} } */
> +/* { dg-final-use { cleanup-rtl-dump "expand" } } */
>
> --
> This patch is available for review at http://codereview.appspot.com/5896043

Easwaran Raman <eraman@google.com> writes:

> Some more background on this patch: Right now, while the execution
> counts of different case labels of a switch statement are obtained
> during profile collection, they are not propagated to RTL. Instead,
> counts are regenerated at the RTL level using static heuristics that
> tend to weigh branches equally which can cause poor optimization of
> hot code. This patch ensures that the counts collected during profile
> collection are correctly propagated allowing hot code to be better
> optimized by RTL optimizations.  Patch tested on x86_64.

I think your patch doesn't use the probably to weight the decision 
tree for non tablejump, right? I looked at this some time ago,
but the patch always had problems.

-Andi

On Fri, Mar 23, 2012 at 3:29 PM, Andi Kleen <andi@firstfloor.org> wrote:
> Easwaran Raman <eraman@google.com> writes:
>
>> Some more background on this patch: Right now, while the execution
>> counts of different case labels of a switch statement are obtained
>> during profile collection, they are not propagated to RTL. Instead,
>> counts are regenerated at the RTL level using static heuristics that
>> tend to weigh branches equally which can cause poor optimization of
>> hot code. This patch ensures that the counts collected during profile
>> collection are correctly propagated allowing hot code to be better
>> optimized by RTL optimizations.  Patch tested on x86_64.
>
> I think your patch doesn't use the probably to weight the decision
> tree for non tablejump, right? I looked at this some time ago,
> but the patch always had problems.

Do you mean use the weights to decide the shape of the binary tree
(similar to COST_TABLE heuristic)? I am planning to send a separate
patch for that. This one just makes sure that the profile counts are
propagated correctly. So you will still have a situation where a
branch corresponding to an infrequently executed case dominates a
frequently executed case, but the BB of the cases gets the right
profile weight.

- Easwaran

> -Andi
>
> --
> ak@linux.intel.com -- Speaking for myself only

> Do you mean use the weights to decide the shape of the binary tree

Yes.

> (similar to COST_TABLE heuristic)?

COST_TABLE should die I hope.

> I am planning to send a separate patch for that. 

Great.

-Andi

> This patch propagates execution count of thee case labels of a
> switch-case statement after its expansion. Bootstraps and all
> tests pass. OK for trunk?

Hi,
while this is resonable thing to do, I belive it would make most sense
to make switch lowering at gimple level: i.e. reorganize the existing
code to produce gimple statement and change expansion code to produce
tablejump from every gimple switch statement that was left in the
code.

This would be both cleaner and would allow gimple optimizers to improve the
generated code. Incrementally it would also allow us to improve switch exansion
that is quite baroque and not realy producing very good code in some common
cases.

If you would be interested working on this (i.e. reorganizing the expansion
code to produce gimple), I would be very happy. If not, I can review the
profile updating part for mainline, since in any case this is desriable thing
to do.

Honza

On Sun, Mar 25, 2012 at 12:22 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> This patch propagates execution count of thee case labels of a
>> switch-case statement after its expansion. Bootstraps and all
>> tests pass. OK for trunk?
>
> Hi,
> while this is resonable thing to do, I belive it would make most sense
> to make switch lowering at gimple level: i.e. reorganize the existing
> code to produce gimple statement and change expansion code to produce
> tablejump from every gimple switch statement that was left in the
> code.
>
> This would be both cleaner and would allow gimple optimizers to improve the
> generated code. Incrementally it would also allow us to improve switch exansion
> that is quite baroque and not realy producing very good code in some common
> cases.
>
> If you would be interested working on this (i.e. reorganizing the expansion
> code to produce gimple), I would be very happy. If not, I can review the
> profile updating part for mainline, since in any case this is desriable thing
> to do.

I am planning to explore improvements to switch expansion (peeling
some cases and using jump tables for the rest, for example) and I
think the reorganization you suggest is the right way to do such
improvements. But until I can spend time on it and get it done, I
would like this patch to get reviewed and checked in.

Thanks,
Easwaran

> Honza

On Sun, Mar 25, 2012 at 9:40 PM, Easwaran Raman <eraman@google.com> wrote:
> On Sun, Mar 25, 2012 at 12:22 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>> This patch propagates execution count of thee case labels of a
>>> switch-case statement after its expansion. Bootstraps and all
>>> tests pass. OK for trunk?
>>
>> Hi,
>> while this is resonable thing to do, I belive it would make most sense
>> to make switch lowering at gimple level: i.e. reorganize the existing
>> code to produce gimple statement and change expansion code to produce
>> tablejump from every gimple switch statement that was left in the
>> code.
>>
>> This would be both cleaner and would allow gimple optimizers to improve the
>> generated code. Incrementally it would also allow us to improve switch exansion
>> that is quite baroque and not realy producing very good code in some common
>> cases.
>>
>> If you would be interested working on this (i.e. reorganizing the expansion
>> code to produce gimple), I would be very happy. If not, I can review the
>> profile updating part for mainline, since in any case this is desriable thing
>> to do.
>
> I am planning to explore improvements to switch expansion (peeling
> some cases and using jump tables for the rest, for example) and I
> think the reorganization you suggest is the right way to do such
> improvements. But until I can spend time on it and get it done, I
> would like this patch to get reviewed and checked in.
>
> Thanks,
> Easwaran

Ping.

Ping.

On Mon, Apr 9, 2012 at 2:33 PM, Easwaran Raman <eraman@google.com> wrote:
> On Sun, Mar 25, 2012 at 9:40 PM, Easwaran Raman <eraman@google.com> wrote:
>> On Sun, Mar 25, 2012 at 12:22 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>>> This patch propagates execution count of thee case labels of a
>>>> switch-case statement after its expansion. Bootstraps and all
>>>> tests pass. OK for trunk?
>>>
>>> Hi,
>>> while this is resonable thing to do, I belive it would make most sense
>>> to make switch lowering at gimple level: i.e. reorganize the existing
>>> code to produce gimple statement and change expansion code to produce
>>> tablejump from every gimple switch statement that was left in the
>>> code.
>>>
>>> This would be both cleaner and would allow gimple optimizers to improve the
>>> generated code. Incrementally it would also allow us to improve switch exansion
>>> that is quite baroque and not realy producing very good code in some common
>>> cases.
>>>
>>> If you would be interested working on this (i.e. reorganizing the expansion
>>> code to produce gimple), I would be very happy. If not, I can review the
>>> profile updating part for mainline, since in any case this is desriable thing
>>> to do.
>>
>> I am planning to explore improvements to switch expansion (peeling
>> some cases and using jump tables for the rest, for example) and I
>> think the reorganization you suggest is the right way to do such
>> improvements. But until I can spend time on it and get it done, I
>> would like this patch to get reviewed and checked in.
>>
>> Thanks,
>> Easwaran
>
> Ping.