| Message ID | CAPK5YPZMvCS8H696sN=xr1Ok1=GLwxMEJ1gZYpPrDLkCmPVRVw@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
What is the status of switch expansion GIMPLE rewrite? If it is not planned for 4.8, It will be desirable to include this fix into trunk. It also helps set up a good base line to test against regression. thanks, David On Tue, Oct 2, 2012 at 6:09 PM, Easwaran Raman <eraman@google.com> wrote: > Hi, > This patch propagates the profile counts during RTL expansion. In > many cases, there is no way to determine the exact count of an edge > generated during the expansion. So this patch uses some simple > heuristics to estimate the edge counts but ensures that the counts of > the basic blocks corresponding to the cases are (nearly the) same as > at the gimple level. > > Bootstrapped and profile-bootstrapped on an x86_64/linux machine. OK for trunk? > > - Easwaran > > ------ > 2012-10-02 Easwaran Raman <eraman@google.com> > > * cfgbuild.c (gen_probabilities_from_existing_counts): New function. > (compute_outgoing_frequencies): If at least one successor of a > BB has non-zero profile count, use the counts to compute > probabilities. > * 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. > (do_jump_if_equal): Pass probability for REG_BR_PROB note. > (add_case_node): Pass execution count of the case node and use > it to initialize COUNT field. > (emit_case_decision_tree): Pass default_count to emit_case_nodes. > (get_outgoing_edge_counts): New function. > (add_prob_note_to_last_insn): Likewise. > (case_probability): New macro. > (emit_case_dispatch_table): Compute probability of jumping to default > label and apply note to the jump. > (expand_case): Compute and propagate default edge count to > emit_case_dispatch_table. > (expand_sjlj_dispatch_table): Update calls to add_case_node and > emit_case_dispatch_table. > (balance_case_nodes): Update subtree_counts. > (emit_case_nodes): Compute edge probabilities and add note. > > gcc/testsuite/ChangeLog: > 2012-10-02 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. > > Index: gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c > =================================================================== > --- gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c (revision 0) > +++ gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c (revision 0) > @@ -0,0 +1,40 @@ > +/* { dg-options "-O2 -fdump-rtl-expand-all" } */ > +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" } } */ > Index: gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c > =================================================================== > --- gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c (revision 0) > +++ gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c (revision 0) > @@ -0,0 +1,40 @@ > +/* { dg-options "-O2 -fdump-rtl-expand-all" } */ > +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" } } */ > Index: gcc/expr.c > =================================================================== > --- gcc/expr.c (revision 191879) > +++ gcc/expr.c (working copy) > @@ -154,7 +154,7 @@ static rtx do_store_flag (sepops, rtx, enum machin > #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); > > @@ -10894,7 +10894,7 @@ try_casesi (tree index_type, tree index_expr, tree > > 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; > > @@ -10910,9 +10910,17 @@ do_tablejump (rtx index, enum machine_mode mode, r > 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. */ > if (mode != Pmode) > @@ -10954,7 +10962,7 @@ do_tablejump (rtx index, enum machine_mode mode, r > > 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; > > @@ -10972,7 +10980,7 @@ try_tablejump (tree index_type, tree index_expr, t > 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; > } > > Index: gcc/cfgbuild.c > =================================================================== > --- gcc/cfgbuild.c (revision 191879) > +++ gcc/cfgbuild.c (working copy) > @@ -533,6 +533,23 @@ find_bb_boundaries (basic_block bb) > purge_dead_tablejump_edges (bb, table); > } > > +/* If there is at least one edge in EDGES with a non-zero count, then > + compute probabilities based on the existing counts. */ > + > +static bool > +gen_probabilities_from_existing_counts ( VEC(edge,gc) *edges) { > + edge e; > + edge_iterator ei; > + gcov_type count_sum = 0; > + FOR_EACH_EDGE(e, ei, edges) > + count_sum += e->count; > + if (count_sum == 0) > + return false; > + FOR_EACH_EDGE(e, ei, edges) > + e->probability = e->count * REG_BR_PROB_BASE / count_sum; > + return true; > +} > + > /* Assume that frequency of basic block B is known. Compute frequencies > and probabilities of outgoing edges. */ > > @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b) > return; > } > } > - > if (single_succ_p (b)) > { > e = single_succ_edge (b); > @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b) > e->count = b->count; > return; > } > - guess_outgoing_edge_probabilities (b); > + else if (!gen_probabilities_from_existing_counts (b->succs)){ > + /* All outgoing edges of B have zero count. Guess probabilities. */ > + guess_outgoing_edge_probabilities (b); > + } > if (b->count) > FOR_EACH_EDGE (e, ei, b->succs) > e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2) > Index: gcc/expr.h > =================================================================== > --- gcc/expr.h (revision 191879) > +++ gcc/expr.h (working copy) > @@ -486,7 +486,7 @@ extern void do_compare_rtx_and_jump (rtx, rtx, enu > > /* 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" > Index: gcc/stmt.c > =================================================================== > --- gcc/stmt.c (revision 191879) > +++ gcc/stmt.c (working copy) > @@ -94,11 +94,13 @@ 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; > typedef struct case_node *case_node_ptr; > > +extern basic_block label_to_block_fn (struct function *, tree); > > static int n_occurrences (int, const char *); > static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *); > @@ -112,7 +114,7 @@ static void balance_case_nodes (case_node_ptr *, c > 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, gcov_type, tree); > > /* Return the rtx-label that corresponds to a LABEL_DECL, > creating it if necessary. */ > @@ -1648,13 +1650,15 @@ expand_stack_restore (tree var) > fixup_args_size_notes (prev, get_last_insn (), 0); > } > > -/* 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) > { > + gcc_assert (prob <= REG_BR_PROB_BASE); > do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, > - NULL_RTX, NULL_RTX, label, -1); > + NULL_RTX, NULL_RTX, label, prob); > } > > /* Do the insertion of a case label into case_list. The labels are > @@ -1664,7 +1668,7 @@ do_jump_if_equal (enum machine_mode mode, rtx op0, > > static struct case_node * > add_case_node (struct case_node *head, tree low, tree high, > - tree label, alloc_pool case_node_pool) > + tree label, gcov_type count, alloc_pool case_node_pool) > { > struct case_node *r; > > @@ -1677,6 +1681,8 @@ add_case_node (struct case_node *head, tree low, t > r->high = high; > r->code_label = label; > r->parent = r->left = NULL; > + r->count = count; > + r->subtree_count = count; > r->right = head; > return r; > } > @@ -1803,7 +1809,8 @@ expand_switch_as_decision_tree_p (tree range, > > static void > emit_case_decision_tree (tree index_expr, tree index_type, > - struct case_node *case_list, rtx default_label) > + struct case_node *case_list, rtx default_label, > + gcov_type default_count) > { > rtx index = expand_normal (index_expr); > > @@ -1839,15 +1846,29 @@ emit_case_decision_tree (tree index_expr, tree ind > dump_case_nodes (dump_file, case_list, indent_step, 0); > } > > - emit_case_nodes (index, case_list, default_label, index_type); > + emit_case_nodes (index, case_list, default_label, default_count, index_type); > if (default_label) > emit_jump (default_label); > } > > +static gcov_type > +get_outgoing_edge_counts (basic_block bb) > +{ > + edge e; > + edge_iterator ei; > + gcov_type count_sum = 0; > + FOR_EACH_EDGE(e, ei, bb->succs) > + count_sum += e->count; > + return count_sum; > +} > + > +#define case_probability(x, y) \ > + ((y) ? (gcc_assert (x <= y), (x) * REG_BR_PROB_BASE / (y)) : -1) > + > /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to > one of the labels in CASE_LIST or to the DEFAULT_LABEL. > MINVAL, MAXVAL, and RANGE are the extrema and range of the case > - labels in CASE_LIST. > + labels in CASE_LIST. STMT_BB is the basic block containing the statement. > > First, a jump insn is emitted. First we try "casesi". If that > fails, try "tablejump". A target *must* have one of them (or both). > @@ -1860,19 +1881,23 @@ emit_case_decision_tree (tree index_expr, tree ind > static void > emit_case_dispatch_table (tree index_expr, tree index_type, > struct case_node *case_list, rtx default_label, > - tree minval, tree maxval, tree range) > + tree minval, tree maxval, tree range, > + basic_block stmt_bb) > { > int i, ncases; > struct case_node *n; > rtx *labelvec; > rtx fallback_label = label_rtx (case_list->code_label); > rtx table_label = gen_label_rtx (); > + bool has_gaps = false; > + edge default_edge = EDGE_SUCC(stmt_bb, 0); > + gcov_type default_count = default_edge->count; > + gcov_type count = get_outgoing_edge_counts (stmt_bb); > + bool try_with_tablejump = false; > > if (! try_casesi (index_type, index_expr, minval, range, > table_label, default_label, fallback_label)) > { > - bool ok; > - > /* Index jumptables from zero for suitable values of minval to avoid > a subtraction. For the rationale see: > "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */ > @@ -1882,11 +1907,9 @@ emit_case_dispatch_table (tree index_expr, tree in > { > minval = build_int_cst (index_type, 0); > range = maxval; > + has_gaps = true; > } > - > - ok = try_tablejump (index_type, index_expr, minval, range, > - table_label, default_label); > - gcc_assert (ok); > + try_with_tablejump = true; > } > > /* Get table of labels to jump to, in order of case index. */ > @@ -1921,8 +1944,47 @@ emit_case_dispatch_table (tree index_expr, tree in > default_label = fallback_label; > for (i = 0; i < ncases; i++) > if (labelvec[i] == 0) > - labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); > + { > + has_gaps = true; > + labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); > + } > > + int default_probability; > + 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, > + count); > + default_count /= 2; > + count -= default_count; > + } > + else > + { > + default_probability = case_probability (default_count, > + count); > + count -= default_count; > + default_count = 0; > + } > + > + default_edge->count = default_count; > + if (count) > + { > + edge e; > + edge_iterator ei; > + FOR_EACH_EDGE (e, ei, stmt_bb->succs) > + e->probability = e->count * REG_BR_PROB_BASE / count; > + } > + > + if (try_with_tablejump) > + { > + bool ok = try_tablejump (index_type, index_expr, minval, range, > + table_label, default_label, > default_probability); > + gcc_assert (ok); > + } > /* Output the table. */ > emit_label (table_label); > > @@ -1956,6 +2018,7 @@ expand_case (gimple stmt) > tree index_expr = gimple_switch_index (stmt); > tree index_type = TREE_TYPE (index_expr); > tree elt; > + basic_block bb = gimple_bb (stmt); > > /* A list of case labels; it is first built as a list and it may then > be rearranged into a nearly balanced binary tree. */ > @@ -1981,6 +2044,8 @@ expand_case (gimple stmt) > > /* Find the default case target label. */ > default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt))); > + edge default_edge = EDGE_SUCC(bb, 0); > + gcov_type default_count = default_edge->count; > > /* Get upper and lower bounds of case values. */ > elt = gimple_switch_label (stmt, 1); > @@ -1999,7 +2064,7 @@ expand_case (gimple stmt) > uniq = 0; > count = 0; > struct pointer_set_t *seen_labels = pointer_set_create (); > - for (i = gimple_switch_num_labels (stmt) - 1; i >= 1; --i) > + for (i = ncases - 1; i >= 1; --i) > { > elt = gimple_switch_label (stmt, i); > tree low = CASE_LOW (elt); > @@ -2041,8 +2106,10 @@ expand_case (gimple stmt) > TREE_INT_CST_LOW (high), > TREE_INT_CST_HIGH (high)); > > + basic_block case_bb = label_to_block_fn (cfun, lab); > + edge case_edge = find_edge (bb, case_bb); > case_list = add_case_node (case_list, low, high, lab, > - case_node_pool); > + case_edge->count, case_node_pool); > } > pointer_set_destroy (seen_labels); > > @@ -2060,11 +2127,12 @@ expand_case (gimple stmt) > > if (expand_switch_as_decision_tree_p (range, uniq, count)) > emit_case_decision_tree (index_expr, index_type, > - case_list, default_label); > + case_list, default_label, > + default_count); > else > emit_case_dispatch_table (index_expr, index_type, > case_list, default_label, > - minval, maxval, range); > + minval, maxval, range, bb); > > reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); > > @@ -2126,7 +2194,7 @@ expand_sjlj_dispatch_table (rtx dispatch_index, > { > tree elt = VEC_index (tree, dispatch_table, i); > rtx lab = label_rtx (CASE_LABEL (elt)); > - do_jump_if_equal (index_mode, index, zero, lab, 0); > + do_jump_if_equal (index_mode, index, zero, lab, 0, -1); > force_expand_binop (index_mode, sub_optab, > index, CONST1_RTX (index_mode), > index, 0, OPTAB_DIRECT); > @@ -2150,12 +2218,12 @@ expand_sjlj_dispatch_table (rtx dispatch_index, > tree elt = VEC_index (tree, dispatch_table, i); > tree low = CASE_LOW (elt); > tree lab = CASE_LABEL (elt); > - case_list = add_case_node (case_list, low, low, lab, case_node_pool); > + case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool); > } > > emit_case_dispatch_table (index_expr, index_type, > case_list, default_label, > - minval, maxval, range); > + minval, maxval, range, NULL); > emit_label (default_label); > free_alloc_pool (case_node_pool); > } > @@ -2237,6 +2305,9 @@ balance_case_nodes (case_node_ptr *head, case_node > /* Optimize each of the two split parts. */ > balance_case_nodes (&np->left, np); > balance_case_nodes (&np->right, np); > + np->subtree_count = np->count; > + np->subtree_count += np->left->subtree_count; > + np->subtree_count += np->right->subtree_count; > } > else > { > @@ -2244,8 +2315,12 @@ balance_case_nodes (case_node_ptr *head, case_node > but fill in `parent' fields. */ > np = *head; > np->parent = parent; > + np->subtree_count = np->count; > for (; np->right; np = np->right) > - np->right->parent = np; > + { > + np->right->parent = np; > + (*head)->subtree_count += np->right->subtree_count; > + } > } > } > } > @@ -2358,6 +2433,20 @@ node_is_bounded (case_node_ptr node, tree index_ty > && 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. > @@ -2386,10 +2475,12 @@ node_is_bounded (case_node_ptr node, tree index_ty > > static void > emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, > - tree index_type) > + gcov_type 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); > > @@ -2404,15 +2495,17 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > > 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. > @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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)) > @@ -2442,7 +2539,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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 > @@ -2460,21 +2560,25 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > > /* 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 > @@ -2494,10 +2598,18 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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) > @@ -2505,7 +2617,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > > /* 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); > } > } > > @@ -2530,21 +2642,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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) > { > @@ -2561,20 +2681,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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 > @@ -2593,15 +2722,20 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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. > @@ -2616,6 +2750,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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. */ > @@ -2627,9 +2765,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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. */ > > @@ -2641,7 +2781,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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); > } > } > > @@ -2658,6 +2798,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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. */ > @@ -2669,8 +2813,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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) > @@ -2686,6 +2832,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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. */ > @@ -2697,8 +2847,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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 > @@ -2718,6 +2870,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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) > @@ -2729,6 +2884,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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) > { > @@ -2750,6 +2908,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > > 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));
On Wed, Oct 3, 2012 at 6:12 PM, Xinliang David Li <davidxl@google.com> wrote: > What is the status of switch expansion GIMPLE rewrite? If it is not > planned for 4.8, It will be desirable to include this fix into trunk. I could work on it for GCC 4.8 (there's not a lot of work left to be done for it now) but we haven't really decided yet where the pass should be scheduled and I also would like to wait a bit to see how the SJLJ changes work out. So I talked about this with Easwaran, I think his patch should be included into the trunk now. I'll adapt it for the move to GIMPLE. > It also helps set up a good base line to test against regression. Agreed. Ciao! Steven
thanks for the update! David On Wed, Oct 3, 2012 at 10:37 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote: > On Wed, Oct 3, 2012 at 6:12 PM, Xinliang David Li <davidxl@google.com> wrote: >> What is the status of switch expansion GIMPLE rewrite? If it is not >> planned for 4.8, It will be desirable to include this fix into trunk. > > I could work on it for GCC 4.8 (there's not a lot of work left to be > done for it now) but we haven't really decided yet where the pass > should be scheduled and I also would like to wait a bit to see how the > SJLJ changes work out. So I talked about this with Easwaran, I think > his patch should be included into the trunk now. I'll adapt it for the > move to GIMPLE. > >> It also helps set up a good base line to test against regression. > > Agreed. > > Ciao! > Steven
> thanks for the update!
OK, I will review the patch tomorrow then. It is a good incremental step. I
would certainly like to see the gimple expansion in 4.8 however.
Honza
> Hi, > This patch propagates the profile counts during RTL expansion. In > many cases, there is no way to determine the exact count of an edge > generated during the expansion. So this patch uses some simple > heuristics to estimate the edge counts but ensures that the counts of > the basic blocks corresponding to the cases are (nearly the) same as > at the gimple level. > > Bootstrapped and profile-bootstrapped on an x86_64/linux machine. OK for trunk? > Index: gcc/expr.c > =================================================================== > --- gcc/expr.c (revision 191879) > +++ gcc/expr.c (working copy) > @@ -154,7 +154,7 @@ static rtx do_store_flag (sepops, rtx, enum machin > #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); > > @@ -10894,7 +10894,7 @@ try_casesi (tree index_type, tree index_expr, tree > > static void > do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label, > - rtx default_label) > + rtx default_label, int default_probability) Please document default_probability. > { > rtx temp, vector; > > @@ -10910,9 +10910,17 @@ do_tablejump (rtx index, enum machine_mode mode, r > 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)); > + } > + } dojump already does this kind of logic, but it is bit more cureful: emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp, if_true_label); if (prob != -1 && profile_status != PROFILE_ABSENT) { for (last = NEXT_INSN (last); last && NEXT_INSN (last); last = NEXT_INSN (last)) if (JUMP_P (last)) break; if (last && JUMP_P (last) && ! NEXT_INSN (last) && any_condjump_p (last)) { gcc_assert (!find_reg_note (last, REG_BR_PROB, 0)); add_reg_note (last, REG_BR_PROB, GEN_INT (prob)); } } What about making emit_cmp_and_jump_insns taking the probability argument and moving the code above inside? Most of other places need updating to propagate probabilities. (compare_and_jump_seq in loop-unswitch probably also can be updated) > @@ -10954,7 +10962,7 @@ do_tablejump (rtx index, enum machine_mode mode, r > > 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) Simiarly here. > Index: gcc/cfgbuild.c > =================================================================== > --- gcc/cfgbuild.c (revision 191879) > +++ gcc/cfgbuild.c (working copy) > @@ -533,6 +533,23 @@ find_bb_boundaries (basic_block bb) > purge_dead_tablejump_edges (bb, table); > } > > +/* If there is at least one edge in EDGES with a non-zero count, then > + compute probabilities based on the existing counts. */ > + > +static bool > +gen_probabilities_from_existing_counts ( VEC(edge,gc) *edges) { > + edge e; > + edge_iterator ei; > + gcov_type count_sum = 0; > + FOR_EACH_EDGE(e, ei, edges) > + count_sum += e->count; > + if (count_sum == 0) > + return false; > + FOR_EACH_EDGE(e, ei, edges) > + e->probability = e->count * REG_BR_PROB_BASE / count_sum; > + return true; > +} > + > /* Assume that frequency of basic block B is known. Compute frequencies > and probabilities of outgoing edges. */ > > @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b) > return; > } > } > - > if (single_succ_p (b)) > { > e = single_succ_edge (b); > @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b) > e->count = b->count; > return; > } > - guess_outgoing_edge_probabilities (b); > + else if (!gen_probabilities_from_existing_counts (b->succs)){ > + /* All outgoing edges of B have zero count. Guess probabilities. */ > + guess_outgoing_edge_probabilities (b); > + } Hmm, I do not quite follow logic here. basic block B is one of many basic blocks that the original BB was split from. It is possible that B may have some of original edges, but there may be new ones. How you can guess the outgoing probabilitie shere. Do you have an example? Also gen_probabilities_from_existing_counts could probably also work based on original edge frequencies. > @@ -1664,7 +1668,7 @@ do_jump_if_equal (enum machine_mode mode, rtx op0, > > static struct case_node * > add_case_node (struct case_node *head, tree low, tree high, > - tree label, alloc_pool case_node_pool) > + tree label, gcov_type count, alloc_pool case_node_pool) Please document COUNT here. > { > struct case_node *r; > > @@ -1677,6 +1681,8 @@ add_case_node (struct case_node *head, tree low, t > r->high = high; > r->code_label = label; > r->parent = r->left = NULL; > + r->count = count; > + r->subtree_count = count; > r->right = head; > return r; > } .. and here > @@ -1803,7 +1809,8 @@ expand_switch_as_decision_tree_p (tree range, > > static void > emit_case_decision_tree (tree index_expr, tree index_type, > - struct case_node *case_list, rtx default_label) > + struct case_node *case_list, rtx default_label, > + gcov_type default_count) > { > rtx index = expand_normal (index_expr); > > @@ -1839,15 +1846,29 @@ emit_case_decision_tree (tree index_expr, tree ind > dump_case_nodes (dump_file, case_list, indent_step, 0); > } > > - emit_case_nodes (index, case_list, default_label, index_type); > + emit_case_nodes (index, case_list, default_label, default_count, index_type); > if (default_label) > emit_jump (default_label); > } > And document functio nhere. > +static gcov_type > +get_outgoing_edge_counts (basic_block bb) > +{ > + edge e; > + edge_iterator ei; > + gcov_type count_sum = 0; > + FOR_EACH_EDGE(e, ei, bb->succs) > + count_sum += e->count; > + return count_sum; > +} > + > +#define case_probability(x, y) \ > + ((y) ? (gcc_assert (x <= y), (x) * REG_BR_PROB_BASE / (y)) : -1) You want to use RDIV here for better rounding. I would make this an inline functions these days. > + > /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to > one of the labels in CASE_LIST or to the DEFAULT_LABEL. > MINVAL, MAXVAL, and RANGE are the extrema and range of the case > - labels in CASE_LIST. > + labels in CASE_LIST. STMT_BB is the basic block containing the statement. > > First, a jump insn is emitted. First we try "casesi". If that > fails, try "tablejump". A target *must* have one of them (or both). > @@ -1860,19 +1881,23 @@ emit_case_decision_tree (tree index_expr, tree ind > static void > emit_case_dispatch_table (tree index_expr, tree index_type, > struct case_node *case_list, rtx default_label, > - tree minval, tree maxval, tree range) > + tree minval, tree maxval, tree range, > + basic_block stmt_bb) > { > int i, ncases; > struct case_node *n; > rtx *labelvec; > rtx fallback_label = label_rtx (case_list->code_label); > rtx table_label = gen_label_rtx (); > + bool has_gaps = false; > + edge default_edge = EDGE_SUCC(stmt_bb, 0); > + gcov_type default_count = default_edge->count; > + gcov_type count = get_outgoing_edge_counts (stmt_bb); > + bool try_with_tablejump = false; Here, I think you want to first decide whether you base expansion on counts (i.e. any counts involved is non-0) or probabilities. We really want to maintain the profile up-to-date even with guessed profile. The inconsistencies propagate across CFG and easilly confuse later optimizers. Everywhere you are using count comming from the original statement, you can also use the probability. The newly produced control flow will be optimized and the edges frequencies will be propagated along. > + > + default_edge->count = default_count; > + if (count) > + { > + edge e; > + edge_iterator ei; > + FOR_EACH_EDGE (e, ei, stmt_bb->succs) > + e->probability = e->count * REG_BR_PROB_BASE / count; > + } Hmm, this updates origina BB containing the switch statement? Of course, modulo roundoff errors, this should hold. I wonder where did you got the diferences and why do you need this? You are going to output new control flow and find_many_sub_basic_blocks will recompute all the counts/frequencies inside anyway? Also you want to use RDIV here. > @@ -2358,6 +2433,20 @@ node_is_bounded (case_node_ptr node, tree index_ty > && 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)); > + } > +} Well, I am not sure this is safe thing to do since you do not really know what the last instruction is. In any case you want to test it is an conditional jump instruction as in the code I quoted above. > @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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); Hmm, here you seem to be distributing the probabilities of the counts reached. What happens in the case when the edge probability needs to be distributed across nodes of the decision tree. I.e. in t(int a) { switch (a) { case 100: case 200: case 300: case 400: case 500: case 600: case 700: case 800: case 900: t(); case 101: case 202: case 303: case 404: case 505: case 606: case 707: case 808: case 909: q(); } } > } > > else if (node_is_bounded (node->left, index_type)) > @@ -2442,7 +2539,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > 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); Here, and apparently in all uses of add_prob_note_to_last_insn, you want to use the new parameter of emit_cmp_and_jump_insn. Otherwise the patch seems to make sense. Thanks for looking into this issue. Honza
Hi Honza, I am addressing some of the questions you raise here. Will send an updated patch later. On Thu, Oct 4, 2012 at 6:19 AM, Jan Hubicka <hubicka@ucw.cz> wrote: > > @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b) > > return; > > } > > } > > - > > if (single_succ_p (b)) > > { > > e = single_succ_edge (b); > > @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b) > > e->count = b->count; > > return; > > } > > - guess_outgoing_edge_probabilities (b); > > + else if (!gen_probabilities_from_existing_counts (b->succs)){ > > + /* All outgoing edges of B have zero count. Guess probabilities. */ > > + guess_outgoing_edge_probabilities (b); > > + } > > Hmm, I do not quite follow logic here. > basic block B is one of many basic blocks that the original BB was split from. > It is possible that B may have some of original edges, but there may be new ones. > How you can guess the outgoing probabilitie shere. Do you have an example? The code reaches here only when the BB has more than two successor. I assume that this happens only when the BB is terminated by a switch statement. During conversion to RTL, the outgoing edges of this BB and their counts ar untouched. So I am just using those counts to compute the edge probabilities. > Also gen_probabilities_from_existing_counts could probably also work based > on original edge frequencies. Just to be clear I understand it right, you want me to use the frequency instead of count since the frequency is derived from the counts in profile use builds? > > > + > > + default_edge->count = default_count; > > + if (count) > > + { > > + edge e; > > + edge_iterator ei; > > + FOR_EACH_EDGE (e, ei, stmt_bb->succs) > > + e->probability = e->count * REG_BR_PROB_BASE / count; > > + } > > Hmm, this updates origina BB containing the switch statement? The out_edges of the original BB. > Of course, > modulo roundoff errors, this should hold. I wonder where did you got the > diferences and why do you need this? Originally, I obtained e->probability as e->count * REG_BR_PROB_BASE / bb->count. During profile bootstrap, I noticed BBs whose sum of outgoing edge counts exceeded the BB's count and hence I normalized with the sum of edge counts. > You are going to output new control flow > and find_many_sub_basic_blocks will recompute all the counts/frequencies inside > anyway? Sorry, I am lost here. I am just updating the probability of stmt_bb->succs right? > > > @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt > > 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); > > Hmm, here you seem to be distributing the probabilities of the counts reached. > What happens in the case when the edge probability needs to be distributed across > nodes of the decision tree. I.e. in > t(int a) > { > switch (a) > { > case 100: > case 200: > case 300: > case 400: > case 500: > case 600: > case 700: > case 800: > case 900: > t(); > case 101: > case 202: > case 303: > case 404: > case 505: > case 606: > case 707: > case 808: > case 909: > q(); > } > } > Ok, that's a bug in my patch. In the above example, there are two outgoing edges from the BB containing switch but many case nodes. I would end up multiplying the counts by the number of cases that lead to a label. If I divide the counts of each case_node by the number of case nodes that jump to the same label, will that be reasonable? In the above case, if t() is called 900 times, I will assume that each of the 9 cases contribute a count of 100. Thanks, Easwaran
> >> >> > + >> > + default_edge->count = default_count; >> > + if (count) >> > + { >> > + edge e; >> > + edge_iterator ei; >> > + FOR_EACH_EDGE (e, ei, stmt_bb->succs) >> > + e->probability = e->count * REG_BR_PROB_BASE / count; >> > + } >> >> Hmm, this updates origina BB containing the switch statement? > The out_edges of the original BB. >> Of course, >> modulo roundoff errors, this should hold. I wonder where did you got the >> diferences and why do you need this? The count of the outgoing edge of BB that jumps to the default label needs to be updated (to 0 or original_default_count/2, depending on whether default label is a jump table target). So I need to redistribute the probabilities of the rest of the edges. That's why I do this here. > Originally, I obtained e->probability as e->count * REG_BR_PROB_BASE / > bb->count. During profile bootstrap, I noticed BBs whose sum of > outgoing edge counts exceeded the BB's count and hence I normalized > with the sum of edge counts. > >> You are going to output new control flow >> and find_many_sub_basic_blocks will recompute all the counts/frequencies inside >> anyway? > Sorry, I am lost here. I am just updating the probability of > stmt_bb->succs right? > >
> > > >> > >> > + > >> > + default_edge->count = default_count; > >> > + if (count) > >> > + { > >> > + edge e; > >> > + edge_iterator ei; > >> > + FOR_EACH_EDGE (e, ei, stmt_bb->succs) > >> > + e->probability = e->count * REG_BR_PROB_BASE / count; > >> > + } > >> > >> Hmm, this updates origina BB containing the switch statement? > > The out_edges of the original BB. > >> Of course, > >> modulo roundoff errors, this should hold. I wonder where did you got the > >> diferences and why do you need this? > > The count of the outgoing edge of BB that jumps to the default label > needs to be updated (to 0 or original_default_count/2, depending on > whether default label is a jump table target). So I need to > redistribute the probabilities of the rest of the edges. That's why I > do this here. Hmm, I see, OK then. Please add a comment. Honza > > > Originally, I obtained e->probability as e->count * REG_BR_PROB_BASE / > > bb->count. During profile bootstrap, I noticed BBs whose sum of > > outgoing edge counts exceeded the BB's count and hence I normalized > > with the sum of edge counts. > > > >> You are going to output new control flow > >> and find_many_sub_basic_blocks will recompute all the counts/frequencies inside > >> anyway? > > Sorry, I am lost here. I am just updating the probability of > > stmt_bb->succs right? > > > >
I have attached a revised patch. The updated ChangeLog is given below and I have responded to your comments inline: 2012-10-08 Easwaran Raman <eraman@google.com> * optabs.c (emit_cmp_and_jump_insn_1): Add a new parameter to specificy the probability of taking the jump. (emit_cmp_and_jump_insns): Likewise. (expand_compare_and_swap_loop): Make the jump predicted not taken. * dojump.c (do_compare_rtx_and_jump): Remove the code attaching REG_BR_PROB note and pass probability to emit_cmp_and_jump_insns. * cfgbuild.c (compute_outgoing_frequencies): Do not guess outgoing probabilities for branches with more than two successors. * expr.c (emit_block_move_via_loop): Predict the loop backedge loop to be highly taken. (try_casesi): Pass the probability of jumping to the default label. (try_tablejump): Likewise. (do_tablejump): Likewise. * expr.h (try_tablejump): Add a new parameter. (try_casesi): Likewise. (emit_cmp_and_jump_insns): Add probability as default parameter with a default value of -1. * except.c (sjlj_emit_function_enter): Pass probability to emit_cmp_and_jump_insns. * stmt.c (case_node): Add new fields PROB and SUBTREE_PROB. (do_jump_if_equal): Pass probability for REG_BR_PROB note. (add_case_node): Pass estimated probability of jumping to the case label. (emit_case_decision_tree): Pass default_prob to emit_case_nodes. (get_outgoing_edge_probs): New function. (conditional_probability): Likewise. (reset_out_edges_aux): Likewise. (compute_cases_per_edge): Likewise. (emit_case_dispatch_table): Update probabilities of edges coming out of the switch statement. (expand_case): Compute and propagate default edge probability to emit_case_dispatch_table. (expand_sjlj_dispatch_table): Update calls to add_case_node and emit_case_dispatch_table. (balance_case_nodes): Update subtree_prob values. (emit_case_nodes): Compute edge probabilities and add pass them to emit_cmp_and_jump_insns. gcc/testsuite/ChangeLog: 2012-10-02 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. On Thu, Oct 4, 2012 at 6:19 AM, Jan Hubicka <hubicka@ucw.cz> wrote: >> Hi, >> This patch propagates the profile counts during RTL expansion. In >> many cases, there is no way to determine the exact count of an edge >> generated during the expansion. So this patch uses some simple >> heuristics to estimate the edge counts but ensures that the counts of >> the basic blocks corresponding to the cases are (nearly the) same as >> at the gimple level. >> >> Bootstrapped and profile-bootstrapped on an x86_64/linux machine. OK for trunk? >> Index: gcc/expr.c >> =================================================================== >> --- gcc/expr.c (revision 191879) >> +++ gcc/expr.c (working copy) >> @@ -154,7 +154,7 @@ static rtx do_store_flag (sepops, rtx, enum machin >> #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); >> >> @@ -10894,7 +10894,7 @@ try_casesi (tree index_type, tree index_expr, tree >> >> static void >> do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label, >> - rtx default_label) >> + rtx default_label, int default_probability) > > Please document default_probability. Done. >> { >> rtx temp, vector; >> >> @@ -10910,9 +10910,17 @@ do_tablejump (rtx index, enum machine_mode mode, r >> 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)); >> + } >> + } > > dojump already does this kind of logic, but it is bit more cureful: > emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp, > if_true_label); > if (prob != -1 && profile_status != PROFILE_ABSENT) > { > for (last = NEXT_INSN (last); > last && NEXT_INSN (last); > last = NEXT_INSN (last)) > if (JUMP_P (last)) > break; > if (last > && JUMP_P (last) > && ! NEXT_INSN (last) > && any_condjump_p (last)) > { > gcc_assert (!find_reg_note (last, REG_BR_PROB, 0)); > add_reg_note (last, REG_BR_PROB, GEN_INT (prob)); > } > } > > What about making emit_cmp_and_jump_insns taking the probability argument > and moving the code above inside? Most of other places need updating to > propagate probabilities. Done. Made probability a default parameter with a default parameter of -1 and so didn't update all callsites. > (compare_and_jump_seq in loop-unswitch probably also can be updated) >> @@ -10954,7 +10962,7 @@ do_tablejump (rtx index, enum machine_mode mode, r >> >> 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) > > Simiarly here. >> Index: gcc/cfgbuild.c >> =================================================================== >> --- gcc/cfgbuild.c (revision 191879) >> +++ gcc/cfgbuild.c (working copy) >> @@ -533,6 +533,23 @@ find_bb_boundaries (basic_block bb) >> purge_dead_tablejump_edges (bb, table); >> } >> >> +/* If there is at least one edge in EDGES with a non-zero count, then >> + compute probabilities based on the existing counts. */ >> + >> +static bool >> +gen_probabilities_from_existing_counts ( VEC(edge,gc) *edges) { >> + edge e; >> + edge_iterator ei; >> + gcov_type count_sum = 0; >> + FOR_EACH_EDGE(e, ei, edges) >> + count_sum += e->count; >> + if (count_sum == 0) >> + return false; >> + FOR_EACH_EDGE(e, ei, edges) >> + e->probability = e->count * REG_BR_PROB_BASE / count_sum; >> + return true; >> +} >> + >> /* Assume that frequency of basic block B is known. Compute frequencies >> and probabilities of outgoing edges. */ >> >> @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b) >> return; >> } >> } >> - >> if (single_succ_p (b)) >> { >> e = single_succ_edge (b); >> @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b) >> e->count = b->count; >> return; >> } >> - guess_outgoing_edge_probabilities (b); >> + else if (!gen_probabilities_from_existing_counts (b->succs)){ >> + /* All outgoing edges of B have zero count. Guess probabilities. */ >> + guess_outgoing_edge_probabilities (b); >> + } > > Hmm, I do not quite follow logic here. > basic block B is one of many basic blocks that the original BB was split from. > It is possible that B may have some of original edges, but there may be new ones. > How you can guess the outgoing probabilitie shere. Do you have an example? I have changed this code. If the bb has >2 edges, I just use the probability as it is without guessing. This should work for switch statements since the edge probabilities are adjusted in stmt.c. I am not sure if there are other cases of multi-way branches that I need to worry about here. > Also gen_probabilities_from_existing_counts could probably also work based > on original edge frequencies. >> @@ -1664,7 +1668,7 @@ do_jump_if_equal (enum machine_mode mode, rtx op0, >> >> static struct case_node * >> add_case_node (struct case_node *head, tree low, tree high, >> - tree label, alloc_pool case_node_pool) >> + tree label, gcov_type count, alloc_pool case_node_pool) > > Please document COUNT here. Done. >> { >> struct case_node *r; >> >> @@ -1677,6 +1681,8 @@ add_case_node (struct case_node *head, tree low, t >> r->high = high; >> r->code_label = label; >> r->parent = r->left = NULL; >> + r->count = count; >> + r->subtree_count = count; >> r->right = head; >> return r; >> } > > .. and here Done. >> @@ -1803,7 +1809,8 @@ expand_switch_as_decision_tree_p (tree range, >> >> static void >> emit_case_decision_tree (tree index_expr, tree index_type, >> - struct case_node *case_list, rtx default_label) >> + struct case_node *case_list, rtx default_label, >> + gcov_type default_count) >> { >> rtx index = expand_normal (index_expr); >> >> @@ -1839,15 +1846,29 @@ emit_case_decision_tree (tree index_expr, tree ind >> dump_case_nodes (dump_file, case_list, indent_step, 0); >> } >> >> - emit_case_nodes (index, case_list, default_label, index_type); >> + emit_case_nodes (index, case_list, default_label, default_count, index_type); >> if (default_label) >> emit_jump (default_label); >> } >> > > And document functio nhere. Done. > >> +static gcov_type >> +get_outgoing_edge_counts (basic_block bb) >> +{ >> + edge e; >> + edge_iterator ei; >> + gcov_type count_sum = 0; >> + FOR_EACH_EDGE(e, ei, bb->succs) >> + count_sum += e->count; >> + return count_sum; >> +} >> + >> +#define case_probability(x, y) \ >> + ((y) ? (gcc_assert (x <= y), (x) * REG_BR_PROB_BASE / (y)) : -1) > > You want to use RDIV here for better rounding. I would make this an inline > functions these days. Done. >> + >> /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to >> one of the labels in CASE_LIST or to the DEFAULT_LABEL. >> MINVAL, MAXVAL, and RANGE are the extrema and range of the case >> - labels in CASE_LIST. >> + labels in CASE_LIST. STMT_BB is the basic block containing the statement. >> >> First, a jump insn is emitted. First we try "casesi". If that >> fails, try "tablejump". A target *must* have one of them (or both). >> @@ -1860,19 +1881,23 @@ emit_case_decision_tree (tree index_expr, tree ind >> static void >> emit_case_dispatch_table (tree index_expr, tree index_type, >> struct case_node *case_list, rtx default_label, >> - tree minval, tree maxval, tree range) >> + tree minval, tree maxval, tree range, >> + basic_block stmt_bb) >> { >> int i, ncases; >> struct case_node *n; >> rtx *labelvec; >> rtx fallback_label = label_rtx (case_list->code_label); >> rtx table_label = gen_label_rtx (); >> + bool has_gaps = false; >> + edge default_edge = EDGE_SUCC(stmt_bb, 0); >> + gcov_type default_count = default_edge->count; >> + gcov_type count = get_outgoing_edge_counts (stmt_bb); >> + bool try_with_tablejump = false; > > Here, I think you want to first decide whether you base expansion on counts > (i.e. any counts involved is non-0) or probabilities. We really want to maintain > the profile up-to-date even with guessed profile. The inconsistencies > propagate across CFG and easilly confuse later optimizers. > Everywhere you are using count comming from the original statement, you can also use > the probability. I have changed the code to use probabilities. > The newly produced control flow will be optimized and the edges frequencies will > be propagated along. > >> + >> + default_edge->count = default_count; >> + if (count) >> + { >> + edge e; >> + edge_iterator ei; >> + FOR_EACH_EDGE (e, ei, stmt_bb->succs) >> + e->probability = e->count * REG_BR_PROB_BASE / count; >> + } > > Hmm, this updates origina BB containing the switch statement? Of course, > modulo roundoff errors, this should hold. I wonder where did you got the > diferences and why do you need this? You are going to output new control flow > and find_many_sub_basic_blocks will recompute all the counts/frequencies inside > anyway? > Also you want to use RDIV here. I need to do this to account for the change in the count of default edge. Changed to use RDIV. >> @@ -2358,6 +2433,20 @@ node_is_bounded (case_node_ptr node, tree index_ty >> && 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)); >> + } >> +} > > Well, I am not sure this is safe thing to do since you do not really > know what the last instruction is. In any case you want to test > it is an conditional jump instruction as in the code I quoted > above. > >> @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt >> 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); > > Hmm, here you seem to be distributing the probabilities of the counts reached. > What happens in the case when the edge probability needs to be distributed across > nodes of the decision tree. I.e. in > t(int a) > { > switch (a) > { > case 100: > case 200: > case 300: > case 400: > case 500: > case 600: > case 700: > case 800: > case 900: > t(); > case 101: > case 202: > case 303: > case 404: > case 505: > case 606: > case 707: > case 808: > case 909: > q(); > } > } I have fixed this. > >> } >> >> else if (node_is_bounded (node->left, index_type)) >> @@ -2442,7 +2539,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt >> 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); > > Here, and apparently in all uses of add_prob_note_to_last_insn, you want to use > the new parameter of emit_cmp_and_jump_insn. > > Otherwise the patch seems to make sense. Thanks for looking into this issue. > > Honza
Ping. On Mon, Oct 8, 2012 at 5:46 PM, Easwaran Raman <eraman@google.com> wrote: > I have attached a revised patch. The updated ChangeLog is given below > and I have responded to your comments inline: > > 2012-10-08 Easwaran Raman <eraman@google.com> > * optabs.c (emit_cmp_and_jump_insn_1): Add a new parameter to > specificy the probability of taking the jump. > (emit_cmp_and_jump_insns): Likewise. > (expand_compare_and_swap_loop): Make the jump predicted not taken. > * dojump.c (do_compare_rtx_and_jump): Remove the code attaching > REG_BR_PROB note and pass probability to emit_cmp_and_jump_insns. > * cfgbuild.c (compute_outgoing_frequencies): Do not guess outgoing > probabilities for branches with more than two successors. > * expr.c (emit_block_move_via_loop): Predict the loop backedge loop > to be highly taken. > (try_casesi): Pass the probability of jumping to the default label. > (try_tablejump): Likewise. > (do_tablejump): Likewise. > * expr.h (try_tablejump): Add a new parameter. > (try_casesi): Likewise. > (emit_cmp_and_jump_insns): Add probability as default parameter with a > default value of -1. > * except.c (sjlj_emit_function_enter): Pass probability to > emit_cmp_and_jump_insns. > * stmt.c (case_node): Add new fields PROB and SUBTREE_PROB. > (do_jump_if_equal): Pass probability for REG_BR_PROB note. > (add_case_node): Pass estimated probability of jumping to the case > label. > (emit_case_decision_tree): Pass default_prob to emit_case_nodes. > (get_outgoing_edge_probs): New function. > (conditional_probability): Likewise. > (reset_out_edges_aux): Likewise. > (compute_cases_per_edge): Likewise. > (emit_case_dispatch_table): Update probabilities of edges coming out > of the switch statement. > (expand_case): Compute and propagate default edge probability to > emit_case_dispatch_table. > (expand_sjlj_dispatch_table): Update calls to add_case_node and > emit_case_dispatch_table. > (balance_case_nodes): Update subtree_prob values. > (emit_case_nodes): Compute edge probabilities and add pass them to > emit_cmp_and_jump_insns. > > gcc/testsuite/ChangeLog: > 2012-10-02 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. > > > > > On Thu, Oct 4, 2012 at 6:19 AM, Jan Hubicka <hubicka@ucw.cz> wrote: >>> Hi, >>> This patch propagates the profile counts during RTL expansion. In >>> many cases, there is no way to determine the exact count of an edge >>> generated during the expansion. So this patch uses some simple >>> heuristics to estimate the edge counts but ensures that the counts of >>> the basic blocks corresponding to the cases are (nearly the) same as >>> at the gimple level. >>> >>> Bootstrapped and profile-bootstrapped on an x86_64/linux machine. OK for trunk? >>> Index: gcc/expr.c >>> =================================================================== >>> --- gcc/expr.c (revision 191879) >>> +++ gcc/expr.c (working copy) >>> @@ -154,7 +154,7 @@ static rtx do_store_flag (sepops, rtx, enum machin >>> #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); >>> >>> @@ -10894,7 +10894,7 @@ try_casesi (tree index_type, tree index_expr, tree >>> >>> static void >>> do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label, >>> - rtx default_label) >>> + rtx default_label, int default_probability) >> >> Please document default_probability. > Done. > >>> { >>> rtx temp, vector; >>> >>> @@ -10910,9 +10910,17 @@ do_tablejump (rtx index, enum machine_mode mode, r >>> 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)); >>> + } >>> + } >> >> dojump already does this kind of logic, but it is bit more cureful: >> emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp, >> if_true_label); >> if (prob != -1 && profile_status != PROFILE_ABSENT) >> { >> for (last = NEXT_INSN (last); >> last && NEXT_INSN (last); >> last = NEXT_INSN (last)) >> if (JUMP_P (last)) >> break; >> if (last >> && JUMP_P (last) >> && ! NEXT_INSN (last) >> && any_condjump_p (last)) >> { >> gcc_assert (!find_reg_note (last, REG_BR_PROB, 0)); >> add_reg_note (last, REG_BR_PROB, GEN_INT (prob)); >> } >> } >> >> What about making emit_cmp_and_jump_insns taking the probability argument >> and moving the code above inside? Most of other places need updating to >> propagate probabilities. > > Done. Made probability a default parameter with a default parameter of > -1 and so didn't update all callsites. > >> (compare_and_jump_seq in loop-unswitch probably also can be updated) >>> @@ -10954,7 +10962,7 @@ do_tablejump (rtx index, enum machine_mode mode, r >>> >>> 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) >> >> Simiarly here. >>> Index: gcc/cfgbuild.c >>> =================================================================== >>> --- gcc/cfgbuild.c (revision 191879) >>> +++ gcc/cfgbuild.c (working copy) >>> @@ -533,6 +533,23 @@ find_bb_boundaries (basic_block bb) >>> purge_dead_tablejump_edges (bb, table); >>> } >>> >>> +/* If there is at least one edge in EDGES with a non-zero count, then >>> + compute probabilities based on the existing counts. */ >>> + >>> +static bool >>> +gen_probabilities_from_existing_counts ( VEC(edge,gc) *edges) { >>> + edge e; >>> + edge_iterator ei; >>> + gcov_type count_sum = 0; >>> + FOR_EACH_EDGE(e, ei, edges) >>> + count_sum += e->count; >>> + if (count_sum == 0) >>> + return false; >>> + FOR_EACH_EDGE(e, ei, edges) >>> + e->probability = e->count * REG_BR_PROB_BASE / count_sum; >>> + return true; >>> +} >>> + >>> /* Assume that frequency of basic block B is known. Compute frequencies >>> and probabilities of outgoing edges. */ >>> >>> @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b) >>> return; >>> } >>> } >>> - >>> if (single_succ_p (b)) >>> { >>> e = single_succ_edge (b); >>> @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b) >>> e->count = b->count; >>> return; >>> } >>> - guess_outgoing_edge_probabilities (b); >>> + else if (!gen_probabilities_from_existing_counts (b->succs)){ >>> + /* All outgoing edges of B have zero count. Guess probabilities. */ >>> + guess_outgoing_edge_probabilities (b); >>> + } >> >> Hmm, I do not quite follow logic here. >> basic block B is one of many basic blocks that the original BB was split from. >> It is possible that B may have some of original edges, but there may be new ones. >> How you can guess the outgoing probabilitie shere. Do you have an example? > I have changed this code. If the bb has >2 edges, I just use the > probability as it is without guessing. This should work for switch > statements since the edge probabilities are adjusted in stmt.c. I am > not sure if there are other cases of multi-way branches that I need to > worry about here. > >> Also gen_probabilities_from_existing_counts could probably also work based >> on original edge frequencies. >>> @@ -1664,7 +1668,7 @@ do_jump_if_equal (enum machine_mode mode, rtx op0, >>> >>> static struct case_node * >>> add_case_node (struct case_node *head, tree low, tree high, >>> - tree label, alloc_pool case_node_pool) >>> + tree label, gcov_type count, alloc_pool case_node_pool) >> >> Please document COUNT here. > Done. > >>> { >>> struct case_node *r; >>> >>> @@ -1677,6 +1681,8 @@ add_case_node (struct case_node *head, tree low, t >>> r->high = high; >>> r->code_label = label; >>> r->parent = r->left = NULL; >>> + r->count = count; >>> + r->subtree_count = count; >>> r->right = head; >>> return r; >>> } >> >> .. and here > Done. >>> @@ -1803,7 +1809,8 @@ expand_switch_as_decision_tree_p (tree range, >>> >>> static void >>> emit_case_decision_tree (tree index_expr, tree index_type, >>> - struct case_node *case_list, rtx default_label) >>> + struct case_node *case_list, rtx default_label, >>> + gcov_type default_count) >>> { >>> rtx index = expand_normal (index_expr); >>> >>> @@ -1839,15 +1846,29 @@ emit_case_decision_tree (tree index_expr, tree ind >>> dump_case_nodes (dump_file, case_list, indent_step, 0); >>> } >>> >>> - emit_case_nodes (index, case_list, default_label, index_type); >>> + emit_case_nodes (index, case_list, default_label, default_count, index_type); >>> if (default_label) >>> emit_jump (default_label); >>> } >>> >> >> And document functio nhere. > Done. >> >>> +static gcov_type >>> +get_outgoing_edge_counts (basic_block bb) >>> +{ >>> + edge e; >>> + edge_iterator ei; >>> + gcov_type count_sum = 0; >>> + FOR_EACH_EDGE(e, ei, bb->succs) >>> + count_sum += e->count; >>> + return count_sum; >>> +} >>> + >>> +#define case_probability(x, y) \ >>> + ((y) ? (gcc_assert (x <= y), (x) * REG_BR_PROB_BASE / (y)) : -1) >> >> You want to use RDIV here for better rounding. I would make this an inline >> functions these days. > Done. > >>> + >>> /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to >>> one of the labels in CASE_LIST or to the DEFAULT_LABEL. >>> MINVAL, MAXVAL, and RANGE are the extrema and range of the case >>> - labels in CASE_LIST. >>> + labels in CASE_LIST. STMT_BB is the basic block containing the statement. >>> >>> First, a jump insn is emitted. First we try "casesi". If that >>> fails, try "tablejump". A target *must* have one of them (or both). >>> @@ -1860,19 +1881,23 @@ emit_case_decision_tree (tree index_expr, tree ind >>> static void >>> emit_case_dispatch_table (tree index_expr, tree index_type, >>> struct case_node *case_list, rtx default_label, >>> - tree minval, tree maxval, tree range) >>> + tree minval, tree maxval, tree range, >>> + basic_block stmt_bb) >>> { >>> int i, ncases; >>> struct case_node *n; >>> rtx *labelvec; >>> rtx fallback_label = label_rtx (case_list->code_label); >>> rtx table_label = gen_label_rtx (); >>> + bool has_gaps = false; >>> + edge default_edge = EDGE_SUCC(stmt_bb, 0); >>> + gcov_type default_count = default_edge->count; >>> + gcov_type count = get_outgoing_edge_counts (stmt_bb); >>> + bool try_with_tablejump = false; >> >> Here, I think you want to first decide whether you base expansion on counts >> (i.e. any counts involved is non-0) or probabilities. We really want to maintain >> the profile up-to-date even with guessed profile. The inconsistencies >> propagate across CFG and easilly confuse later optimizers. >> Everywhere you are using count comming from the original statement, you can also use >> the probability. > > I have changed the code to use probabilities. > >> The newly produced control flow will be optimized and the edges frequencies will >> be propagated along. >> >>> + >>> + default_edge->count = default_count; >>> + if (count) >>> + { >>> + edge e; >>> + edge_iterator ei; >>> + FOR_EACH_EDGE (e, ei, stmt_bb->succs) >>> + e->probability = e->count * REG_BR_PROB_BASE / count; >>> + } >> >> Hmm, this updates origina BB containing the switch statement? Of course, >> modulo roundoff errors, this should hold. I wonder where did you got the >> diferences and why do you need this? You are going to output new control flow >> and find_many_sub_basic_blocks will recompute all the counts/frequencies inside >> anyway? >> Also you want to use RDIV here. > I need to do this to account for the change in the count of default > edge. Changed to use RDIV. > >>> @@ -2358,6 +2433,20 @@ node_is_bounded (case_node_ptr node, tree index_ty >>> && 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)); >>> + } >>> +} >> >> Well, I am not sure this is safe thing to do since you do not really >> know what the last instruction is. In any case you want to test >> it is an conditional jump instruction as in the code I quoted >> above. >> >>> @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt >>> 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); >> >> Hmm, here you seem to be distributing the probabilities of the counts reached. >> What happens in the case when the edge probability needs to be distributed across >> nodes of the decision tree. I.e. in >> t(int a) >> { >> switch (a) >> { >> case 100: >> case 200: >> case 300: >> case 400: >> case 500: >> case 600: >> case 700: >> case 800: >> case 900: >> t(); >> case 101: >> case 202: >> case 303: >> case 404: >> case 505: >> case 606: >> case 707: >> case 808: >> case 909: >> q(); >> } >> } > > I have fixed this. >> >>> } >>> >>> else if (node_is_bounded (node->left, index_type)) >>> @@ -2442,7 +2539,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt >>> 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); >> >> Here, and apparently in all uses of add_prob_note_to_last_insn, you want to use >> the new parameter of emit_cmp_and_jump_insn. >> >> Otherwise the patch seems to make sense. Thanks for looking into this issue. >> >> Honza
On 10/08/12 17:46:03, Easwaran Raman wrote: > I have attached a revised patch. The updated ChangeLog is given below > and I have responded to your comments inline: > > 2012-10-08 Easwaran Raman <eraman@google.com> > * optabs.c (emit_cmp_and_jump_insn_1): Add a new parameter to > specificy the probability of taking the jump. Typo above: specificy > * except.c (sjlj_emit_function_enter): Pass probability to > emit_cmp_and_jump_insns. On some targets (e. g., IA64), the following patch leads to an unused variable warning-as-error: > Index: except.c > =================================================================== > --- except.c (revision 191879) > +++ except.c (working copy) > @@ -1161,13 +1161,7 @@ sjlj_emit_function_enter (rtx dispatch_label) > > emit_cmp_and_jump_insns (x, const0_rtx, NE, 0, > TYPE_MODE (integer_type_node), 0, > - dispatch_label); > - last = get_last_insn (); > - if (JUMP_P (last) && any_condjump_p (last)) > - { > - gcc_assert (!find_reg_note (last, REG_BR_PROB, 0)); > - add_reg_note (last, REG_BR_PROB, GEN_INT (REG_BR_PROB_BASE / 100)); > - } > + dispatch_label, REG_BR_PROB_BASE / 100); > #else > expand_builtin_setjmp_setup (plus_constant (Pmode, XEXP (fc, 0), > sjlj_fc_jbuf_ofs), [...] gcc-trunk/src/gcc/except.c:1156:14: error: unused variable ‘last’ [-Werror=unused-variable] rtx x, last; ^ cc1plus: all warnings being treated as errors
Index: gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c =================================================================== --- gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c (revision 0) @@ -0,0 +1,40 @@ +/* { dg-options "-O2 -fdump-rtl-expand-all" } */ +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" } } */ Index: gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c =================================================================== --- gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c (revision 0) @@ -0,0 +1,40 @@ +/* { dg-options "-O2 -fdump-rtl-expand-all" } */ +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" } } */ Index: gcc/expr.c =================================================================== --- gcc/expr.c (revision 191879) +++ gcc/expr.c (working copy) @@ -154,7 +154,7 @@ static rtx do_store_flag (sepops, rtx, enum machin #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); @@ -10894,7 +10894,7 @@ try_casesi (tree index_type, tree index_expr, tree 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; @@ -10910,9 +10910,17 @@ do_tablejump (rtx index, enum machine_mode mode, r 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. */ if (mode != Pmode) @@ -10954,7 +10962,7 @@ do_tablejump (rtx index, enum machine_mode mode, r 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; @@ -10972,7 +10980,7 @@ try_tablejump (tree index_type, tree index_expr, t 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; } Index: gcc/cfgbuild.c =================================================================== --- gcc/cfgbuild.c (revision 191879) +++ gcc/cfgbuild.c (working copy) @@ -533,6 +533,23 @@ find_bb_boundaries (basic_block bb) purge_dead_tablejump_edges (bb, table); } +/* If there is at least one edge in EDGES with a non-zero count, then + compute probabilities based on the existing counts. */ + +static bool +gen_probabilities_from_existing_counts ( VEC(edge,gc) *edges) { + edge e; + edge_iterator ei; + gcov_type count_sum = 0; + FOR_EACH_EDGE(e, ei, edges) + count_sum += e->count; + if (count_sum == 0) + return false; + FOR_EACH_EDGE(e, ei, edges) + e->probability = e->count * REG_BR_PROB_BASE / count_sum; + return true; +} + /* Assume that frequency of basic block B is known. Compute frequencies and probabilities of outgoing edges. */ @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b) return; } } - if (single_succ_p (b)) { e = single_succ_edge (b); @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b) e->count = b->count; return; } - guess_outgoing_edge_probabilities (b); + else if (!gen_probabilities_from_existing_counts (b->succs)){ + /* All outgoing edges of B have zero count. Guess probabilities. */ + guess_outgoing_edge_probabilities (b); + } if (b->count) FOR_EACH_EDGE (e, ei, b->succs) e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2) Index: gcc/expr.h =================================================================== --- gcc/expr.h (revision 191879) +++ gcc/expr.h (working copy) @@ -486,7 +486,7 @@ extern void do_compare_rtx_and_jump (rtx, rtx, enu /* 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" Index: gcc/stmt.c =================================================================== --- gcc/stmt.c (revision 191879) +++ gcc/stmt.c (working copy) @@ -94,11 +94,13 @@ 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; typedef struct case_node *case_node_ptr; +extern basic_block label_to_block_fn (struct function *, tree); static int n_occurrences (int, const char *); static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *); @@ -112,7 +114,7 @@ static void balance_case_nodes (case_node_ptr *, c 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, gcov_type, tree); /* Return the rtx-label that corresponds to a LABEL_DECL, creating it if necessary. */ @@ -1648,13 +1650,15 @@ expand_stack_restore (tree var) fixup_args_size_notes (prev, get_last_insn (), 0); } -/* 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) { + gcc_assert (prob <= REG_BR_PROB_BASE); do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, - NULL_RTX, NULL_RTX, label, -1); + NULL_RTX, NULL_RTX, label, prob); } /* Do the insertion of a case label into case_list. The labels are @@ -1664,7 +1668,7 @@ do_jump_if_equal (enum machine_mode mode, rtx op0, static struct case_node * add_case_node (struct case_node *head, tree low, tree high, - tree label, alloc_pool case_node_pool) + tree label, gcov_type count, alloc_pool case_node_pool) { struct case_node *r; @@ -1677,6 +1681,8 @@ add_case_node (struct case_node *head, tree low, t r->high = high; r->code_label = label; r->parent = r->left = NULL; + r->count = count; + r->subtree_count = count; r->right = head; return r; } @@ -1803,7 +1809,8 @@ expand_switch_as_decision_tree_p (tree range, static void emit_case_decision_tree (tree index_expr, tree index_type, - struct case_node *case_list, rtx default_label) + struct case_node *case_list, rtx default_label, + gcov_type default_count) { rtx index = expand_normal (index_expr); @@ -1839,15 +1846,29 @@ emit_case_decision_tree (tree index_expr, tree ind dump_case_nodes (dump_file, case_list, indent_step, 0); } - emit_case_nodes (index, case_list, default_label, index_type); + emit_case_nodes (index, case_list, default_label, default_count, index_type); if (default_label) emit_jump (default_label); } +static gcov_type +get_outgoing_edge_counts (basic_block bb) +{ + edge e; + edge_iterator ei; + gcov_type count_sum = 0; + FOR_EACH_EDGE(e, ei, bb->succs) + count_sum += e->count; + return count_sum; +} + +#define case_probability(x, y) \ + ((y) ? (gcc_assert (x <= y), (x) * REG_BR_PROB_BASE / (y)) : -1) + /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to one of the labels in CASE_LIST or to the DEFAULT_LABEL. MINVAL, MAXVAL, and RANGE are the extrema and range of the case - labels in CASE_LIST. + labels in CASE_LIST. STMT_BB is the basic block containing the statement. First, a jump insn is emitted. First we try "casesi". If that fails, try "tablejump". A target *must* have one of them (or both). @@ -1860,19 +1881,23 @@ emit_case_decision_tree (tree index_expr, tree ind static void emit_case_dispatch_table (tree index_expr, tree index_type, struct case_node *case_list, rtx default_label, - tree minval, tree maxval, tree range) + tree minval, tree maxval, tree range, + basic_block stmt_bb) { int i, ncases; struct case_node *n; rtx *labelvec; rtx fallback_label = label_rtx (case_list->code_label); rtx table_label = gen_label_rtx (); + bool has_gaps = false; + edge default_edge = EDGE_SUCC(stmt_bb, 0); + gcov_type default_count = default_edge->count; + gcov_type count = get_outgoing_edge_counts (stmt_bb); + bool try_with_tablejump = false; if (! try_casesi (index_type, index_expr, minval, range, table_label, default_label, fallback_label)) { - bool ok; - /* Index jumptables from zero for suitable values of minval to avoid a subtraction. For the rationale see: "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */ @@ -1882,11 +1907,9 @@ emit_case_dispatch_table (tree index_expr, tree in { minval = build_int_cst (index_type, 0); range = maxval; + has_gaps = true; } - - ok = try_tablejump (index_type, index_expr, minval, range, - table_label, default_label); - gcc_assert (ok); + try_with_tablejump = true; } /* Get table of labels to jump to, in order of case index. */ @@ -1921,8 +1944,47 @@ emit_case_dispatch_table (tree index_expr, tree in default_label = fallback_label; for (i = 0; i < ncases; i++) if (labelvec[i] == 0) - labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); + { + has_gaps = true; + labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); + } + int default_probability; + 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, + count); + default_count /= 2; + count -= default_count; + } + else + { + default_probability = case_probability (default_count, + count); + count -= default_count; + default_count = 0; + } + + default_edge->count = default_count; + if (count) + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, stmt_bb->succs) + e->probability = e->count * REG_BR_PROB_BASE / count; + } + + if (try_with_tablejump) + { + bool ok = try_tablejump (index_type, index_expr, minval, range, + table_label, default_label, default_probability); + gcc_assert (ok); + } /* Output the table. */ emit_label (table_label);
Hi, This patch propagates the profile counts during RTL expansion. In many cases, there is no way to determine the exact count of an edge generated during the expansion. So this patch uses some simple heuristics to estimate the edge counts but ensures that the counts of the basic blocks corresponding to the cases are (nearly the) same as at the gimple level. Bootstrapped and profile-bootstrapped on an x86_64/linux machine. OK for trunk? - Easwaran ------ 2012-10-02 Easwaran Raman <eraman@google.com> * cfgbuild.c (gen_probabilities_from_existing_counts): New function. (compute_outgoing_frequencies): If at least one successor of a BB has non-zero profile count, use the counts to compute probabilities. * 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. (do_jump_if_equal): Pass probability for REG_BR_PROB note. (add_case_node): Pass execution count of the case node and use it to initialize COUNT field. (emit_case_decision_tree): Pass default_count to emit_case_nodes. (get_outgoing_edge_counts): New function. (add_prob_note_to_last_insn): Likewise. (case_probability): New macro. (emit_case_dispatch_table): Compute probability of jumping to default label and apply note to the jump. (expand_case): Compute and propagate default edge count to emit_case_dispatch_table. (expand_sjlj_dispatch_table): Update calls to add_case_node and emit_case_dispatch_table. (balance_case_nodes): Update subtree_counts. (emit_case_nodes): Compute edge probabilities and add note. gcc/testsuite/ChangeLog: 2012-10-02 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. @@ -1956,6 +2018,7 @@ expand_case (gimple stmt) tree index_expr = gimple_switch_index (stmt); tree index_type = TREE_TYPE (index_expr); tree elt; + basic_block bb = gimple_bb (stmt); /* A list of case labels; it is first built as a list and it may then be rearranged into a nearly balanced binary tree. */ @@ -1981,6 +2044,8 @@ expand_case (gimple stmt) /* Find the default case target label. */ default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt))); + edge default_edge = EDGE_SUCC(bb, 0); + gcov_type default_count = default_edge->count; /* Get upper and lower bounds of case values. */ elt = gimple_switch_label (stmt, 1); @@ -1999,7 +2064,7 @@ expand_case (gimple stmt) uniq = 0; count = 0; struct pointer_set_t *seen_labels = pointer_set_create (); - for (i = gimple_switch_num_labels (stmt) - 1; i >= 1; --i) + for (i = ncases - 1; i >= 1; --i) { elt = gimple_switch_label (stmt, i); tree low = CASE_LOW (elt); @@ -2041,8 +2106,10 @@ expand_case (gimple stmt) TREE_INT_CST_LOW (high), TREE_INT_CST_HIGH (high)); + basic_block case_bb = label_to_block_fn (cfun, lab); + edge case_edge = find_edge (bb, case_bb); case_list = add_case_node (case_list, low, high, lab, - case_node_pool); + case_edge->count, case_node_pool); } pointer_set_destroy (seen_labels); @@ -2060,11 +2127,12 @@ expand_case (gimple stmt) if (expand_switch_as_decision_tree_p (range, uniq, count)) emit_case_decision_tree (index_expr, index_type, - case_list, default_label); + case_list, default_label, + default_count); else emit_case_dispatch_table (index_expr, index_type, case_list, default_label, - minval, maxval, range); + minval, maxval, range, bb); reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); @@ -2126,7 +2194,7 @@ expand_sjlj_dispatch_table (rtx dispatch_index, { tree elt = VEC_index (tree, dispatch_table, i); rtx lab = label_rtx (CASE_LABEL (elt)); - do_jump_if_equal (index_mode, index, zero, lab, 0); + do_jump_if_equal (index_mode, index, zero, lab, 0, -1); force_expand_binop (index_mode, sub_optab, index, CONST1_RTX (index_mode), index, 0, OPTAB_DIRECT); @@ -2150,12 +2218,12 @@ expand_sjlj_dispatch_table (rtx dispatch_index, tree elt = VEC_index (tree, dispatch_table, i); tree low = CASE_LOW (elt); tree lab = CASE_LABEL (elt); - case_list = add_case_node (case_list, low, low, lab, case_node_pool); + case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool); } emit_case_dispatch_table (index_expr, index_type, case_list, default_label, - minval, maxval, range); + minval, maxval, range, NULL); emit_label (default_label); free_alloc_pool (case_node_pool); } @@ -2237,6 +2305,9 @@ balance_case_nodes (case_node_ptr *head, case_node /* Optimize each of the two split parts. */ balance_case_nodes (&np->left, np); balance_case_nodes (&np->right, np); + np->subtree_count = np->count; + np->subtree_count += np->left->subtree_count; + np->subtree_count += np->right->subtree_count; } else { @@ -2244,8 +2315,12 @@ balance_case_nodes (case_node_ptr *head, case_node but fill in `parent' fields. */ np = *head; np->parent = parent; + np->subtree_count = np->count; for (; np->right; np = np->right) - np->right->parent = np; + { + np->right->parent = np; + (*head)->subtree_count += np->right->subtree_count; + } } } } @@ -2358,6 +2433,20 @@ node_is_bounded (case_node_ptr node, tree index_ty && 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. @@ -2386,10 +2475,12 @@ node_is_bounded (case_node_ptr node, tree index_ty static void emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, - tree index_type) + gcov_type 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); @@ -2404,15 +2495,17 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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)) @@ -2442,7 +2539,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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 @@ -2460,21 +2560,25 @@ emit_case_nodes (rtx index, case_node_ptr node, rt /* 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 @@ -2494,10 +2598,18 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) @@ -2505,7 +2617,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rt /* 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); } } @@ -2530,21 +2642,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) { @@ -2561,20 +2681,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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 @@ -2593,15 +2722,20 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. @@ -2616,6 +2750,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2627,9 +2765,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2641,7 +2781,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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); } } @@ -2658,6 +2798,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2669,8 +2813,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) @@ -2686,6 +2832,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2697,8 +2847,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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 @@ -2718,6 +2870,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) @@ -2729,6 +2884,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) { @@ -2750,6 +2908,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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));