Hi all,
This is a ping for
https://gcc.gnu.org/ml/gcc-patches/2017-07/msg01275.html . I've fixed
attachment type, hopefully it's easier to read now.
This patch adds support for __builtin_expect in switch statements at
tree level (RTL part would be reviewed/commited separately). It's an
update of https://gcc.gnu.org/ml/gcc-patches/2017-07/msg01016.html ,
rebased and retested.
Ok for trunk?
-Y
2017-07-21 Yury Gribov <tetra2...@gmail.com>
Martin Liska <mar...@gcc.gnu.org>
PR middle-end/59521
gcc/
* predict.c (set_even_probabilities): Handle case of a single
likely edge.
(combine_predictions_for_bb): Ditto.
(tree_predict_by_opcode): Handle switch statements.
* stmt.c (balance_case_nodes): Select pivot value based on
probabilities.
gcc/testsuite/
* gcc.dg/predict-15.c: New test.
diff -rupN gcc/gcc/predict.c gcc-59521/gcc/predict.c
--- gcc/gcc/predict.c 2017-07-18 22:21:16.000000000 +0200
+++ gcc-59521/gcc/predict.c 2017-07-19 08:26:57.000000000 +0200
@@ -815,9 +815,12 @@ unlikely_executed_bb_p (basic_block bb)
static void
set_even_probabilities (basic_block bb,
- hash_set<edge> *unlikely_edges = NULL)
+ hash_set<edge> *unlikely_edges = NULL,
+ hash_set<edge_prediction *> *likely_edges = NULL)
{
unsigned nedges = 0, unlikely_count = 0;
+ unsigned likely_count
+ = likely_edges ? likely_edges->elements () : 0;
edge e = NULL;
edge_iterator ei;
profile_probability all = profile_probability::always ();
@@ -827,7 +830,7 @@ set_even_probabilities (basic_block bb,
all -= e->probability;
else if (!unlikely_executed_edge_p (e))
{
- nedges ++;
+ nedges++;
if (unlikely_edges != NULL && unlikely_edges->contains (e))
{
all -= profile_probability::very_unlikely ();
@@ -844,18 +847,44 @@ set_even_probabilities (basic_block bb,
unsigned c = nedges - unlikely_count;
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->probability.initialized_p ())
- ;
- else if (!unlikely_executed_edge_p (e))
- {
- if (unlikely_edges != NULL && unlikely_edges->contains (e))
- e->probability = profile_probability::very_unlikely ();
- else
- e->probability = all.apply_scale (1, c).guessed ();
- }
- else
- e->probability = profile_probability::never ();
+ /* If we have one likely edge, then use its probability and
+ distribute remaining probabilities as even. */
+ if (likely_count == 1)
+ {
+ edge_prediction *prediction = *likely_edges->begin ();
+ int p = prediction->ep_probability;
+ profile_probability likely_prob
+ = all.apply_scale (p, REG_BR_PROB_BASE).guessed ();
+ profile_probability remainder = all - likely_prob;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->probability.initialized_p ())
+ ;
+ else if (!unlikely_executed_edge_p (e))
+ {
+ if (prediction->ep_edge == e)
+ e->probability = likely_prob;
+ else
+ e->probability = remainder.apply_scale (1, nedges - 1);
+ }
+ else
+ e->probability = profile_probability::never ();
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->probability.initialized_p ())
+ ;
+ else if (!unlikely_executed_edge_p (e))
+ {
+ if (unlikely_edges != NULL && unlikely_edges->contains (e))
+ e->probability = profile_probability::very_unlikely ();
+ else
+ e->probability = all.apply_scale (1, c).guessed ();
+ }
+ else
+ e->probability = profile_probability::never ();
+ }
}
/* Add REG_BR_PROB note to JUMP with PROB. */
@@ -1151,6 +1180,7 @@ combine_predictions_for_bb (basic_block
if (nedges != 2)
{
hash_set<edge> unlikely_edges (4);
+ hash_set<edge_prediction *> likely_edges (4);
/* Identify all edges that have a probability close to very unlikely.
Doing the approach for very unlikely doesn't worth for doing as
@@ -1158,16 +1188,31 @@ combine_predictions_for_bb (basic_block
edge_prediction **preds = bb_predictions->get (bb);
if (preds)
for (pred = *preds; pred; pred = pred->ep_next)
- if (pred->ep_probability <= PROB_VERY_UNLIKELY)
- unlikely_edges.add (pred->ep_edge);
+ {
+ if (pred->ep_probability <= PROB_VERY_UNLIKELY)
+ unlikely_edges.add (pred->ep_edge);
+ if (pred->ep_probability >= PROB_VERY_LIKELY
+ || pred->ep_predictor == PRED_BUILTIN_EXPECT)
+ likely_edges.add (pred);
+ }
if (!dry_run)
- set_even_probabilities (bb, &unlikely_edges);
+ set_even_probabilities (bb, &unlikely_edges, &likely_edges);
clear_bb_predictions (bb);
if (dump_file)
{
fprintf (dump_file, "Predictions for bb %i\n", bb->index);
- if (unlikely_edges.elements () == 0)
+ if (likely_edges.elements () == 1)
+ {
+ fprintf (dump_file,
+ "1 edge in bb %i predicted as likely, %i as unlikely\n",
+ bb->index, nedges - 1);
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!unlikely_executed_edge_p (e))
+ dump_prediction (dump_file, PRED_COMBINED,
+ e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
+ }
+ else if (unlikely_edges.elements () == 0)
fprintf (dump_file,
"%i edges in bb %i predicted to even probabilities\n",
nedges, bb->index);
@@ -2449,7 +2494,30 @@ tree_predict_by_opcode (basic_block bb)
edge_iterator ei;
enum br_predictor predictor;
- if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+ if (!stmt)
+ return;
+
+ if (gswitch *sw = dyn_cast <gswitch *> (stmt))
+ {
+ tree index = gimple_switch_index (sw);
+ tree val = expr_expected_value (index, auto_bitmap (),
+ &predictor);
+ if (val && TREE_CODE (val) == INTEGER_CST)
+ {
+ edge e = find_taken_edge_switch_expr (sw, bb, val);
+ if (predictor == PRED_BUILTIN_EXPECT)
+ {
+ int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
+ gcc_assert (percent >= 0 && percent <= 100);
+ predict_edge (e, PRED_BUILTIN_EXPECT,
+ HITRATE (percent));
+ }
+ else
+ predict_edge_def (e, predictor, TAKEN);
+ }
+ }
+
+ if (gimple_code (stmt) != GIMPLE_COND)
return;
FOR_EACH_EDGE (then_edge, ei, bb->succs)
if (then_edge->flags & EDGE_TRUE_VALUE)
diff -rupN gcc/gcc/testsuite/gcc.dg/predict-15.c
gcc-59521/gcc/testsuite/gcc.dg/predict-15.c
--- gcc/gcc/testsuite/gcc.dg/predict-15.c 1970-01-01 01:00:00.000000000
+0100
+++ gcc-59521/gcc/testsuite/gcc.dg/predict-15.c 2017-07-19 08:33:40.000000000
+0200
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int puts (const char *);
+
+void
+f(int ch) {
+ switch (__builtin_expect(ch, 333)) {
+ case 3: puts("a"); break;
+ case 42: puts("e"); break;
+ case 333: puts("i"); break;
+ }
+}
+
+/* { dg-final { scan-tree-dump "1 edge in bb 2 predicted as likely, 3 as
unlikely" "profile_estimate"} } */
+/* { dg-final { scan-tree-dump "switch (.*) .* case 333: <L\[0-9\]*> .90"
"profile_estimate"} } */
diff -rupN gcc/gcc/tree-cfg.c gcc-59521/gcc/tree-cfg.c
--- gcc/gcc/tree-cfg.c 2017-07-18 22:21:20.000000000 +0200
+++ gcc-59521/gcc/tree-cfg.c 2017-07-19 06:36:39.000000000 +0200
@@ -170,8 +170,6 @@ static bool gimple_can_merge_blocks_p (b
static void remove_bb (basic_block);
static edge find_taken_edge_computed_goto (basic_block, tree);
static edge find_taken_edge_cond_expr (basic_block, tree);
-static edge find_taken_edge_switch_expr (gswitch *, basic_block, tree);
-static tree find_case_label_for_value (gswitch *, tree);
static void lower_phi_internal_fn ();
void
@@ -2311,73 +2309,6 @@ find_taken_edge_cond_expr (basic_block b
return (integer_zerop (val) ? false_edge : true_edge);
}
-/* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
- statement, determine which edge will be taken out of the block. Return
- NULL if any edge may be taken. */
-
-static edge
-find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
- tree val)
-{
- basic_block dest_bb;
- edge e;
- tree taken_case;
-
- if (gimple_switch_num_labels (switch_stmt) == 1)
- taken_case = gimple_switch_default_label (switch_stmt);
- else if (! val || TREE_CODE (val) != INTEGER_CST)
- return NULL;
- else
- taken_case = find_case_label_for_value (switch_stmt, val);
- dest_bb = label_to_block (CASE_LABEL (taken_case));
-
- e = find_edge (bb, dest_bb);
- gcc_assert (e);
- return e;
-}
-
-
-/* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
- We can make optimal use here of the fact that the case labels are
- sorted: We can do a binary search for a case matching VAL. */
-
-static tree
-find_case_label_for_value (gswitch *switch_stmt, tree val)
-{
- size_t low, high, n = gimple_switch_num_labels (switch_stmt);
- tree default_case = gimple_switch_default_label (switch_stmt);
-
- for (low = 0, high = n; high - low > 1; )
- {
- size_t i = (high + low) / 2;
- tree t = gimple_switch_label (switch_stmt, i);
- int cmp;
-
- /* Cache the result of comparing CASE_LOW and val. */
- cmp = tree_int_cst_compare (CASE_LOW (t), val);
-
- if (cmp > 0)
- high = i;
- else
- low = i;
-
- if (CASE_HIGH (t) == NULL)
- {
- /* A singe-valued case label. */
- if (cmp == 0)
- return t;
- }
- else
- {
- /* A case range. We can only handle integer ranges. */
- if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
- return t;
- }
- }
-
- return default_case;
-}
-
/* Dump a basic block on stderr. */
@@ -9352,6 +9283,72 @@ gt_pch_nx (edge_def *e, gt_pointer_opera
op (&(block), cookie);
}
+/* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
+ statement, determine which edge will be taken out of the block. Return
+ NULL if any edge may be taken. */
+
+edge
+find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb,
+ tree val)
+{
+ basic_block dest_bb;
+ edge e;
+ tree taken_case;
+
+ if (gimple_switch_num_labels (switch_stmt) == 1)
+ taken_case = gimple_switch_default_label (switch_stmt);
+ else if (! val || TREE_CODE (val) != INTEGER_CST)
+ return NULL;
+ else
+ taken_case = find_case_label_for_value (switch_stmt, val);
+ dest_bb = label_to_block (CASE_LABEL (taken_case));
+
+ e = find_edge (bb, dest_bb);
+ gcc_assert (e);
+ return e;
+}
+
+/* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
+ We can make optimal use here of the fact that the case labels are
+ sorted: We can do a binary search for a case matching VAL. */
+
+tree
+find_case_label_for_value (gswitch *switch_stmt, tree val)
+{
+ size_t low, high, n = gimple_switch_num_labels (switch_stmt);
+ tree default_case = gimple_switch_default_label (switch_stmt);
+
+ for (low = 0, high = n; high - low > 1; )
+ {
+ size_t i = (high + low) / 2;
+ tree t = gimple_switch_label (switch_stmt, i);
+ int cmp;
+
+ /* Cache the result of comparing CASE_LOW and val. */
+ cmp = tree_int_cst_compare (CASE_LOW (t), val);
+
+ if (cmp > 0)
+ high = i;
+ else
+ low = i;
+
+ if (CASE_HIGH (t) == NULL)
+ {
+ /* A singe-valued case label. */
+ if (cmp == 0)
+ return t;
+ }
+ else
+ {
+ /* A case range. We can only handle integer ranges. */
+ if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+ return t;
+ }
+ }
+
+ return default_case;
+}
+
#if CHECKING_P
namespace selftest {
diff -rupN gcc/gcc/tree-cfg.h gcc-59521/gcc/tree-cfg.h
--- gcc/gcc/tree-cfg.h 2017-07-18 22:21:20.000000000 +0200
+++ gcc-59521/gcc/tree-cfg.h 2017-07-19 06:36:39.000000000 +0200
@@ -109,6 +109,9 @@ extern basic_block insert_cond_bb (basic
extern bool gimple_find_sub_bbs (gimple_seq, gimple_stmt_iterator *);
extern bool extract_true_false_controlled_edges (basic_block, basic_block,
edge *, edge *);
+extern tree find_case_label_for_value (gswitch *switch_stmt, tree val);
+extern edge find_taken_edge_switch_expr (gswitch *switch_stmt,
+ basic_block bb, tree val);
/* Return true if the LHS of a call should be removed. */
