From dbdfaaba50c5d7d85c1e64751988d00114fd7d6b Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Mon, 27 Aug 2018 14:17:54 +0200 Subject: [PATCH] Fix probabilities for jump table (PR tree-optimization/86702). 2018-08-27 Martin Liska PR tree-optimization/86702 * tree-switch-conversion.c (jump_table_cluster::emit): Make probabilities even for values in jump table according to number of cases handled. (switch_decision_tree::compute_cases_per_edge): Pass argument to reset_out_edges_aux function. (switch_decision_tree::analyze_switch_statement): Likewise. * tree-switch-conversion.h (switch_decision_tree::reset_out_edges_aux): Make it static. From-SVN: r263877 --- gcc/ChangeLog | 12 +++++++++++ gcc/tree-switch-conversion.c | 40 ++++++++++++++++++++++++++++++++++-- gcc/tree-switch-conversion.h | 11 +++++----- 3 files changed, 55 insertions(+), 8 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 40a8735a446..b39f12fe037 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2018-08-27 Martin Liska + + PR tree-optimization/86702 + * tree-switch-conversion.c (jump_table_cluster::emit): + Make probabilities even for values in jump table + according to number of cases handled. + (switch_decision_tree::compute_cases_per_edge): Pass + argument to reset_out_edges_aux function. + (switch_decision_tree::analyze_switch_statement): Likewise. + * tree-switch-conversion.h (switch_decision_tree::reset_out_edges_aux): + Make it static. + 2018-08-27 Martin Liska * cfgexpand.c (expand_asm_stmt): Use label_to_block and pass diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index ef08bdc990d..00a463b1dde 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1061,6 +1061,9 @@ void jump_table_cluster::emit (tree index_expr, tree, tree default_label_expr, basic_block default_bb) { + unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ()); + unsigned HOST_WIDE_INT nondefault_range = 0; + /* For jump table we just emit a new gswitch statement that will be latter lowered to jump table. */ auto_vec labels; @@ -1077,6 +1080,39 @@ jump_table_cluster::emit (tree index_expr, tree, unshare_expr (default_label_expr), labels); gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb); gsi_insert_after (&gsi, s, GSI_NEW_STMT); + + /* Set up even probabilities for all cases. */ + for (unsigned i = 0; i < m_cases.length (); i++) + { + simple_cluster *sc = static_cast (m_cases[i]); + edge case_edge = find_edge (m_case_bb, sc->m_case_bb); + unsigned HOST_WIDE_INT case_range + = sc->get_range (sc->get_low (), sc->get_high ()); + nondefault_range += case_range; + + /* case_edge->aux is number of values in a jump-table that are covered + by the case_edge. */ + case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range); + } + + edge default_edge = gimple_switch_default_edge (cfun, s); + default_edge->probability = profile_probability::never (); + + for (unsigned i = 0; i < m_cases.length (); i++) + { + simple_cluster *sc = static_cast (m_cases[i]); + edge case_edge = find_edge (m_case_bb, sc->m_case_bb); + case_edge->probability + = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux, + range); + } + + /* Number of non-default values is probability of default edge. */ + default_edge->probability + += profile_probability::always ().apply_scale (nondefault_range, + range).invert (); + + switch_decision_tree::reset_out_edges_aux (s); } /* Find jump tables of given CLUSTERS, where all members of the vector @@ -1568,7 +1604,7 @@ bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, void switch_decision_tree::compute_cases_per_edge () { - reset_out_edges_aux (); + reset_out_edges_aux (m_switch); int ncases = gimple_switch_num_labels (m_switch); for (int i = ncases - 1; i >= 1; --i) { @@ -1610,7 +1646,7 @@ switch_decision_tree::analyze_switch_statement () m_case_bbs.quick_push (case_edge->dest); } - reset_out_edges_aux (); + reset_out_edges_aux (m_switch); /* Find jump table clusters. */ vec output = jump_table_cluster::find_jump_tables (clusters); diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index 4beac785f05..af2f47a07e6 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -513,10 +513,6 @@ struct switch_decision_tree /* Attempt to expand CLUSTERS as a decision tree. Return true when expanded. */ bool try_switch_expansion (vec &clusters); - - /* Reset the aux field of all outgoing edges of switch basic block. */ - inline void reset_out_edges_aux (); - /* Compute the number of case labels that correspond to each outgoing edge of switch statement. Record this information in the aux field of the edge. */ @@ -576,6 +572,9 @@ struct switch_decision_tree basic_block label_bb, profile_probability prob); + /* Reset the aux field of all outgoing edges of switch basic block. */ + static inline void reset_out_edges_aux (gswitch *swtch); + /* Switch statement. */ gswitch *m_switch; @@ -838,9 +837,9 @@ struct switch_conversion }; void -switch_decision_tree::reset_out_edges_aux () +switch_decision_tree::reset_out_edges_aux (gswitch *swtch) { - basic_block bb = gimple_bb (m_switch); + basic_block bb = gimple_bb (swtch); edge e; edge_iterator ei; FOR_EACH_EDGE (e, ei, bb->succs) -- 2.30.2