This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[google] Propagate profile information to RTL level during switch expansion
- From: Easwaran Raman <eraman at google dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Xinliang David Li <davidxl at google dot com>
- Date: Tue, 31 Jan 2012 17:34:40 -0800
- Subject: [google] Propagate profile information to RTL level during switch expansion
This patch propagates profile information to RTL level when expanding
switch statements using jump table or a binary tree of branches.
Ok for google/gcc-4_6 branch? I would like the patch to be considered
for trunk when stage 1 opens again.
-Easwaran
2012-01-31 Easwaran Raman <eraman@google.com>
* expr.c (do_tablejump): Add default_probability as the
sixth parameter and use it to generate REG_BR_PROB note.
(try_tablejump): Add default_probability as a parameter.
* cfgbuild.c (non_zero_profile_counts): New function.
(compute_outgoing_frequencies): If edges have profile counts
set, don't replace them with guessed values.
* expr.h (try_tablejump): Add additional parameter to the
declaration.
* stmt.c (tree-flow.h): Include.
(case_node): Add new fields count and subtree_count.
(add_case_node): Pass count as a paramater and initialize
count field of case_node.
(case_probability): New macro.
(expand_case): Propagate profile information from the tree
level to RTL during switch case expansion.
(balance_case_nodes): Compute subtree_count for case nodes.
(emit_case_nodes): Set branch probabilities for generated
branches.
testsuite/ChengeLog.google-4_6:
2012-01-31 Easwaran Raman <eraman@google.com>
* tree-prof/switch-case-1.c: New test.
* tree-prof/switch-case-2.c: New test.
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-blocks -fdump-tree-optimized-blocks" } */
+int g;
+
+__attribute__((noinline)) void foo (int n)
+{
+ switch (n)
+ {
+ case 1:
+ g++; break;
+ case 2:
+ g += 2; break;
+ case 3:
+ g += 1; break;
+ case 4:
+ g += 3; break;
+ case 5:
+ g += 4; break;
+ case 6:
+ g += 5; break;
+ case 7:
+ g += 6; break;
+ case 8:
+ g += 7; break;
+ case 9:
+ g += 8; break;
+ default:
+ g += 8; break;
+ }
+}
+
+int main ()
+{
+ int i;
+ for (i = 0; i < 10000; i++)
+ foo ((i * i) % 5);
+ return 0;
+}
+/* { dg-final-use { scan-rtl-dump-times "Succ edge\[^\\n\]*count:4000" 4 "expand"} } */
+/* { dg-final-use { scan-rtl-dump-times "Succ edge\[^\\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-blocks" } */
+int g;
+
+__attribute__((noinline)) void foo (int n)
+{
+ switch (n)
+ {
+ case 99:
+ g += 2; break;
+ case 1:
+ g++; break;
+ case 100:
+ g += 1; break;
+ case 4:
+ g += 3; break;
+ case 5:
+ g += 4; break;
+ case 6:
+ g += 5; break;
+ case 7:
+ g += 6; break;
+ case 8:
+ g += 7; break;
+ case 9:
+ g += 8; break;
+ default:
+ g += 8; break;
+ }
+}
+
+int main ()
+{
+ int i;
+ for (i = 0; i < 10000; i++)
+ foo ((i * i) % 5);
+ return 0;
+}
+/* { dg-final-use { scan-rtl-dump-times "Succ edge\[^\\n\]*count:4000" 4 "expand"} } */
+/* { dg-final-use { scan-rtl-dump-times "Succ edge\[^\\n\]*count:2000" 1 "expand"} } */
+/* { dg-final-use { cleanup-rtl-dump "expand" } } */
Index: gcc/expr.c
===================================================================
--- gcc/expr.c (revision 183262)
+++ gcc/expr.c (working copy)
@@ -155,7 +155,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);
@@ -10245,7 +10245,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;
@@ -10261,9 +10261,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)
@@ -10305,7 +10313,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;
@@ -10323,7 +10331,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 183262)
+++ gcc/cfgbuild.c (working copy)
@@ -522,6 +522,17 @@ find_bb_boundaries (basic_block bb)
purge_dead_tablejump_edges (bb, table);
}
+static bool non_zero_profile_counts ( VEC(edge,gc) *edges) {
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE(e, ei, edges)
+ {
+ if (e->count > 0)
+ return true;
+ }
+ return false;
+}
+
/* Assume that frequency of basic block B is known. Compute frequencies
and probabilities of outgoing edges. */
@@ -549,7 +560,6 @@ compute_outgoing_frequencies (basic_block b)
return;
}
}
-
if (single_succ_p (b))
{
e = single_succ_edge (b);
@@ -557,6 +567,10 @@ compute_outgoing_frequencies (basic_block b)
e->count = b->count;
return;
}
+ else if (non_zero_profile_counts (b->succs)){
+ /*Profile counts already set, but REG_NOTE missing. Retain the counts. */
+ return;
+ }
guess_outgoing_edge_probabilities (b);
if (b->count)
FOR_EACH_EDGE (e, ei, b->succs)
Index: gcc/expr.h
===================================================================
--- gcc/expr.h (revision 183262)
+++ gcc/expr.h (working copy)
@@ -464,7 +464,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 183262)
+++ gcc/stmt.c (working copy)
@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see
#include "pretty-print.h"
#include "coverage.h"
#include "bitmap.h"
+#include "tree-flow.h"
/* Functions and data structures for expanding case statements. */
@@ -93,6 +94,7 @@ struct case_node
tree low; /* Lowest index value for this label */
tree high; /* Highest index value for this label */
tree code_label; /* Label to jump to when node matches */
+ gcov_type subtree_count, count; /* Execution counts */
};
typedef struct case_node case_node;
@@ -125,9 +127,10 @@ 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, int, tree);
static struct case_node *add_case_node (struct case_node *, tree,
- tree, tree, tree, alloc_pool);
+ tree, tree, tree, gcov_type,
+ alloc_pool);
/* Return the rtx-label that corresponds to a LABEL_DECL,
@@ -2030,7 +2033,7 @@ expand_stack_restore (tree var)
static struct case_node *
add_case_node (struct case_node *head, tree type, tree low, tree high,
- tree label, alloc_pool case_node_pool)
+ tree label, gcov_type count, alloc_pool case_node_pool)
{
tree min_value, max_value;
struct case_node *r;
@@ -2089,6 +2092,8 @@ add_case_node (struct case_node *head, tree type,
TREE_INT_CST_HIGH (high));
r->code_label = label;
r->parent = r->left = NULL;
+ r->count = count;
+ r->subtree_count = 0;
r->right = head;
return r;
}
@@ -2272,6 +2277,8 @@ expand_switch_using_bit_tests_p (tree index_expr,
|| (uniq == 3 && count >= 6)));
}
+#define case_probability(x, y) ((y) ? ((x) * REG_BR_PROB_BASE / (y)) : -1)
+
/* Terminate a case (Pascal/Ada) or switch (C) statement
in which ORIG_INDEX is the expression to be tested.
If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
@@ -2295,6 +2302,7 @@ expand_case (gimple stmt)
tree index_expr = gimple_switch_index (stmt);
tree index_type = TREE_TYPE (index_expr);
int unsignedp = TYPE_UNSIGNED (index_type);
+ basic_block bb = gimple_bb (stmt);
/* The insn after which the case dispatch should finally
be emitted. Zero for a dummy. */
@@ -2307,6 +2315,8 @@ expand_case (gimple stmt)
/* Label to jump to if no case matches. */
tree default_label_decl = NULL_TREE;
+ int default_count = 0;
+
alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
sizeof (struct case_node),
100);
@@ -2318,7 +2328,9 @@ expand_case (gimple stmt)
{
tree elt;
bitmap label_bitmap;
+ edge case_edge = NULL, default_edge = NULL;
int stopi = 0;
+ bool has_gaps = false;
/* cleanup_tree_cfg removes all SWITCH_EXPR with their index
expressions being INTEGER_CST. */
@@ -2329,12 +2341,17 @@ expand_case (gimple stmt)
if (!CASE_LOW (elt) && !CASE_HIGH (elt))
{
default_label_decl = CASE_LABEL (elt);
+ case_edge = EDGE_SUCC(bb, 0);
+ default_edge = case_edge;
+ default_count = case_edge->count;
stopi = 1;
}
for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
{
tree low, high;
+ basic_block case_bb;
+ edge case_edge;
elt = gimple_switch_label (stmt, i);
low = CASE_LOW (elt);
@@ -2344,9 +2361,11 @@ expand_case (gimple stmt)
/* Discard empty ranges. */
if (high && tree_int_cst_lt (high, low))
continue;
-
+ case_bb = label_to_block (CASE_LABEL(elt));
+ case_edge = find_edge (bb, case_bb);
case_list = add_case_node (case_list, index_type, low, high,
- CASE_LABEL (elt), case_node_pool);
+ CASE_LABEL (elt), case_edge->count,
+ case_node_pool);
}
@@ -2370,6 +2389,15 @@ expand_case (gimple stmt)
}
else
{
+ tree min_minus_one = fold_build2 (MINUS_EXPR, index_type,
+ n->low,
+ build_int_cst (index_type, 1));
+ /* case_list is sorted in increasing order. If the minval - 1 of
+ this node is greater than the previous maxval, then there is a
+ gap. If jump table expansion is used, this gap will be filled
+ with the default label. */
+ if (tree_int_cst_lt (maxval, min_minus_one))
+ has_gaps = true;
if (tree_int_cst_lt (n->low, minval))
minval = n->low;
if (tree_int_cst_lt (maxval, n->high))
@@ -2481,18 +2509,23 @@ expand_case (gimple stmt)
use_cost_table = estimate_case_costs (case_list);
balance_case_nodes (&case_list, NULL);
- emit_case_nodes (index, case_list, default_label, index_type);
+ emit_case_nodes (index, case_list, default_label, default_count,
+ index_type);
if (default_label)
emit_jump (default_label);
}
else
{
rtx fallback_label = label_rtx (case_list->code_label);
+ edge e;
+ edge_iterator ei;
+ int count = bb->count;
table_label = gen_label_rtx ();
if (! try_casesi (index_type, index_expr, minval, range,
table_label, default_label, fallback_label))
{
bool ok;
+ int default_probability;
/* Index jumptables from zero for suitable values of
minval to avoid a subtraction. */
@@ -2502,12 +2535,37 @@ expand_case (gimple stmt)
{
minval = build_int_cst (index_type, 0);
range = maxval;
+ has_gaps = true;
}
+ if (has_gaps)
+ {
+ /* There is at least one entry in the jump table that jumps
+ to default label. The default label can either be reached
+ through the indirect jump or the direct conditional jump
+ before that. Split the probability of reaching the
+ default label among these two jumps. */
+ default_probability = case_probability (default_count/2,
+ bb->count);
+ default_count /= 2;
+ count -= default_count;
+ }
+ else
+ {
+ default_probability = case_probability (default_count,
+ bb->count);
+ count -= default_count;
+ default_count = 0;
+ }
ok = try_tablejump (index_type, index_expr, minval, range,
- table_label, default_label);
+ table_label, default_label,
+ default_probability);
gcc_assert (ok);
}
+ default_edge->count = default_count;
+ if (count)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ e->probability = e->count * REG_BR_PROB_BASE / count;
/* Get table of labels to jump to, in order of case index. */
@@ -2572,10 +2630,10 @@ expand_case (gimple stmt)
static void
do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
- int unsignedp)
+ int unsignedp, int prob)
{
do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
- NULL_RTX, NULL_RTX, label, -1);
+ NULL_RTX, NULL_RTX, label, prob);
}
/* Not all case values are encountered equally. This function
@@ -2679,6 +2737,7 @@ balance_case_nodes (case_node_ptr *head, case_node
int cost = 0;
int i = 0;
int ranges = 0;
+ gcov_type count = 0;
case_node_ptr *npp;
case_node_ptr left;
@@ -2728,9 +2787,15 @@ balance_case_nodes (case_node_ptr *head, case_node
side and fill in `parent' fields for right-hand side. */
np = *head;
np->parent = parent;
+ np->subtree_count = count;
balance_case_nodes (&np->left, np);
- for (; np->right; np = np->right)
+ if (np->left)
+ np->subtree_count += np->left->subtree_count;
+
+ for (; np->right; np = np->right) {
np->right->parent = np;
+ (*head)->subtree_count += np->right->count;
+ }
return;
}
}
@@ -2762,6 +2827,11 @@ 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;
+ if (np->left)
+ np->subtree_count += np->left->subtree_count;
+ if (np->right)
+ np->subtree_count += np->right->subtree_count;
}
else
{
@@ -2769,8 +2839,11 @@ balance_case_nodes (case_node_ptr *head, case_node
but fill in `parent' fields. */
np = *head;
np->parent = parent;
- for (; np->right; np = np->right)
+ np->subtree_count = np->count;
+ for (; np->right; np = np->right) {
np->right->parent = np;
+ (*head)->subtree_count += np->right->subtree_count;
+ }
}
}
}
@@ -2883,6 +2956,17 @@ node_is_bounded (case_node_ptr node, tree index_ty
&& node_has_high_bound (node, index_type));
}
+
+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.
@@ -2911,10 +2995,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)
+ int default_count, tree index_type)
{
/* If INDEX has an unsigned type, we must make unsigned branches. */
int unsignedp = TYPE_UNSIGNED (index_type);
+ int probability;
+ gcov_type count = node->count, subtree_count = node->subtree_count;
enum machine_mode mode = GET_MODE (index);
enum machine_mode imode = TYPE_MODE (index_type);
@@ -2929,15 +3015,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.
@@ -2955,7 +3043,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))
@@ -2967,7 +3059,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
@@ -2985,21 +3080,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
@@ -3019,10 +3118,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)
@@ -3030,7 +3137,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);
}
}
@@ -3055,21 +3162,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)
{
@@ -3086,20 +3201,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
@@ -3118,15 +3242,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.
@@ -3141,6 +3270,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. */
@@ -3152,9 +3285,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. */
@@ -3166,7 +3301,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);
}
}
@@ -3183,6 +3318,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. */
@@ -3194,8 +3333,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)
@@ -3211,6 +3352,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. */
@@ -3222,8 +3367,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
@@ -3243,6 +3390,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)
@@ -3254,6 +3404,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)
{
@@ -3275,6 +3428,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));