This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Propagate profile counts during switch expansion
- From: Easwaran Raman <eraman at google dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Jan Hubicka <hubicka at ucw dot cz>, Steven Bosscher <stevenb dot gcc at gmail dot com>, David Li <davidxl at google dot com>
- Date: Tue, 2 Oct 2012 18:09:36 -0700
- Subject: Propagate profile counts during switch expansion
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));