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