From d2d668fbbb3625987fa4117e63df38fa745874bd Mon Sep 17 00:00:00 2001 From: Maxim Kuvyrkov Date: Tue, 15 Nov 2011 03:46:08 +0000 Subject: [PATCH] ipa-cp.c (ipa_value_from_jfunc): Make global. * ipa-cp.c (ipa_value_from_jfunc): Make global. (ipa_cst_from_jfunc): Remove, use ipa_value_from_jfunc instead. (get_indirect_edge_target): Rename, make global. (devirtualization_time_bonus, estimate_local_effects,) (ipcp_discover_new_direct_edges): Update. * ipa-inline-analysis.c (evaluate_conditions_for_edge): Generalize to also handle types. Rename to ... (evaluate_properties_for_edge): Use instead of evaluate_conditions_for_edge. (estimate_edge_devirt_benefit): New function. (estimate_calls_size_and_time): Use it. (estimate_node_size_and_time, estimate_ipcp_clone_size_and_time,) (inline_merge_summary): Update. (do_estimate_edge_time, do_estimate_edge_growth): Update. Calculate parameter information at the call site and pass it on to subroutines. * tree-inline.c (estimate_num_insns): Distinguish between direct and indirect calls. (init_inline_once): Set size and time costs or indirect calls. * tree-inline.h (eni_weights): Add indirect_call_cost. From-SVN: r181377 --- gcc/ChangeLog | 22 ++++++ gcc/ipa-cp.c | 35 +++------ gcc/ipa-inline-analysis.c | 176 +++++++++++++++++++++++++++++++++++++--------- gcc/ipa-inline.h | 1 + gcc/ipa-prop.h | 7 +- gcc/tree-inline.c | 6 +- gcc/tree-inline.h | 3 + 7 files changed, 189 insertions(+), 61 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index a8292ff..01476a9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,25 @@ +2011-11-15 Maxim Kuvyrkov + + * ipa-cp.c (ipa_value_from_jfunc): Make global. + (ipa_cst_from_jfunc): Remove, use ipa_value_from_jfunc instead. + (get_indirect_edge_target): Rename, make global. + (devirtualization_time_bonus, estimate_local_effects,) + (ipcp_discover_new_direct_edges): Update. + * ipa-inline-analysis.c (evaluate_conditions_for_edge): + Generalize to also handle types. Rename to ... + (evaluate_properties_for_edge): Use instead of + evaluate_conditions_for_edge. + (estimate_edge_devirt_benefit): New function. + (estimate_calls_size_and_time): Use it. + (estimate_node_size_and_time, estimate_ipcp_clone_size_and_time,) + (inline_merge_summary): Update. + (do_estimate_edge_time, do_estimate_edge_growth): Update. Calculate + parameter information at the call site and pass it on to subroutines. + * tree-inline.c (estimate_num_insns): Distinguish between direct and + indirect calls. + (init_inline_once): Set size and time costs or indirect calls. + * tree-inline.h (eni_weights): Add indirect_call_cost. + 2011-11-15 Tom de Vries PR tree-optimization/51005 diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index 45cb00b..10e1834 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -693,7 +693,7 @@ ipa_value_from_known_type_jfunc (struct ipa_jump_func *jfunc) describes the caller node so that pass-through jump functions can be evaluated. */ -static tree +tree ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) { if (jfunc->type == IPA_JF_CONST) @@ -753,21 +753,6 @@ ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) return NULL_TREE; } -/* Determine whether JFUNC evaluates to a constant and if so, return it. - Otherwise return NULL. INFO describes the caller node so that pass-through - jump functions can be evaluated. */ - -tree -ipa_cst_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) -{ - tree res = ipa_value_from_jfunc (info, jfunc); - - if (res && TREE_CODE (res) == TREE_BINFO) - return NULL_TREE; - else - return res; -} - /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not bottom, not containing a variable component and without any known value at @@ -1112,10 +1097,10 @@ propagate_constants_accross_call (struct cgraph_edge *cs) (which can contain both constants and binfos) or KNOWN_BINFOS (which can be NULL) return the destination. */ -static tree -get_indirect_edge_target (struct cgraph_edge *ie, - VEC (tree, heap) *known_vals, - VEC (tree, heap) *known_binfos) +tree +ipa_get_indirect_edge_target (struct cgraph_edge *ie, + VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos) { int param_index = ie->indirect_info->param_index; HOST_WIDE_INT token, anc_offset; @@ -1185,7 +1170,7 @@ devirtualization_time_bonus (struct cgraph_node *node, struct inline_summary *isummary; tree target; - target = get_indirect_edge_target (ie, known_csts, known_binfos); + target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos); if (!target) continue; @@ -1344,7 +1329,8 @@ estimate_local_effects (struct cgraph_node *node) init_caller_stats (&stats); cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false); - estimate_ipcp_clone_size_and_time (node, known_csts, &size, &time); + estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, + &size, &time); time -= devirtualization_time_bonus (node, known_csts, known_binfos); time -= removable_params_cost; size -= stats.n_calls * removable_params_cost; @@ -1415,7 +1401,8 @@ estimate_local_effects (struct cgraph_node *node) else continue; - estimate_ipcp_clone_size_and_time (node, known_csts, &size, &time); + estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, + &size, &time); time_benefit = base_time - time + devirtualization_time_bonus (node, known_csts, known_binfos) + removable_params_cost + emc; @@ -1673,7 +1660,7 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, tree target; next_ie = ie->next_callee; - target = get_indirect_edge_target (ie, known_vals, NULL); + target = ipa_get_indirect_edge_target (ie, known_vals, NULL); if (target) ipa_make_edge_direct_to_target (ie, target); } diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c index 91aa612..9ff247b 100644 --- a/gcc/ipa-inline-analysis.c +++ b/gcc/ipa-inline-analysis.c @@ -710,15 +710,25 @@ evaluate_conditions_for_known_args (struct cgraph_node *node, /* Work out what conditions might be true at invocation of E. */ -static clause_t -evaluate_conditions_for_edge (struct cgraph_edge *e, bool inline_p) +static void +evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p, + clause_t *clause_ptr, + VEC (tree, heap) **known_vals_ptr, + VEC (tree, heap) **known_binfos_ptr) { - clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition; struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL); struct inline_summary *info = inline_summary (callee); int i; - if (ipa_node_params_vector && info->conds) + if (clause_ptr) + *clause_ptr = inline_p ? 0 : 1 << predicate_not_inlined_condition; + if (known_vals_ptr) + *known_vals_ptr = NULL; + if (known_binfos_ptr) + *known_binfos_ptr = NULL; + + if (ipa_node_params_vector + && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr)) { struct ipa_node_params *parms_info; struct ipa_edge_args *args = IPA_EDGE_REF (e); @@ -731,29 +741,42 @@ evaluate_conditions_for_edge (struct cgraph_edge *e, bool inline_p) else parms_info = IPA_NODE_REF (e->caller); - if (count) - VEC_safe_grow_cleared (tree, heap, known_vals, count); + if (count && (info->conds || known_vals_ptr)) + VEC_safe_grow_cleared (tree, heap, known_vals, count); + if (count && known_binfos_ptr) + VEC_safe_grow_cleared (tree, heap, *known_binfos_ptr, count); + for (i = 0; i < count; i++) { - tree cst = ipa_cst_from_jfunc (parms_info, - ipa_get_ith_jump_func (args, i)); + tree cst = ipa_value_from_jfunc (parms_info, + ipa_get_ith_jump_func (args, i)); if (cst) - VEC_replace (tree, known_vals, i, cst); + { + if (info->conds && TREE_CODE (cst) != TREE_BINFO) + VEC_replace (tree, known_vals, i, cst); + else if (known_binfos_ptr != NULL) + VEC_replace (tree, *known_binfos_ptr, i, cst); + } else if (inline_p && !VEC_index (inline_param_summary_t, es->param, i)->change_prob) VEC_replace (tree, known_vals, i, error_mark_node); } - clause = evaluate_conditions_for_known_args (callee, - inline_p, known_vals); - VEC_free (tree, heap, known_vals); + + if (clause_ptr && info->conds) + *clause_ptr = evaluate_conditions_for_known_args (callee, inline_p, + known_vals); + + if (known_vals_ptr) + *known_vals_ptr = known_vals; + else + VEC_free (tree, heap, known_vals); } - else - for (i = 0; i < (int)VEC_length (condition, info->conds); i++) - clause |= 1 << (i + predicate_first_dynamic_condition); - return clause; + if (clause_ptr && !info->conds) + for (i = 0; i < (int)VEC_length (condition, info->conds); i++) + *clause_ptr |= 1 << (i + predicate_first_dynamic_condition); } @@ -2169,11 +2192,71 @@ estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time, } -/* Increase SIZE and TIME for size and time needed to handle all calls in NODE. */ +/* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and + KNOWN_BINFOS. */ + +static void +estimate_edge_devirt_benefit (struct cgraph_edge *ie, + int *size, int *time, int prob, + VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos) +{ + tree target; + struct cgraph_node *callee; + struct inline_summary *isummary; + int edge_size = 0, edge_time = 0; + + if (!known_vals || !known_binfos) + return; + + target = ipa_get_indirect_edge_target (ie, known_vals, known_binfos); + if (!target) + return; + + /* Account for difference in cost between indirect and direct calls. */ + *size -= ((eni_size_weights.indirect_call_cost - eni_size_weights.call_cost) + * INLINE_SIZE_SCALE); + *time -= ((eni_time_weights.indirect_call_cost - eni_time_weights.call_cost) + * INLINE_TIME_SCALE * prob / REG_BR_PROB_BASE); + + callee = cgraph_get_node (target); + if (!callee || !callee->analyzed) + return; + isummary = inline_summary (callee); + if (!isummary->inlinable) + return; + + estimate_edge_size_and_time (ie, &edge_size, &edge_time, prob); + + /* Count benefit only from functions that definitely will be inlined + if additional context from NODE's caller were available. */ + if (edge_size >= isummary->size * INLINE_SIZE_SCALE) + { + /* Subtract size and time that we added for edge IE. */ + *size -= edge_size; + *time -= edge_time; + + /* Subtract benefit from inlining devirtualized call. */ + *size -= edge_size - isummary->size * INLINE_SIZE_SCALE; + *time -= edge_time - (isummary->time * INLINE_TIME_SCALE * prob + / REG_BR_PROB_BASE); + + /* TODO: estimate benefit from optimizing CALLEE's body provided + additional context from IE call site. + For insipiration see ipa-cp.c: devirtualization_time_bonus(). */ + } +} + + +/* Increase SIZE and TIME for size and time needed to handle all calls in NODE. + POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call + site. */ static void estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time, - clause_t possible_truths) + clause_t possible_truths, + VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos) { struct cgraph_edge *e; for (e = node->callees; e; e = e->next_callee) @@ -2189,25 +2272,32 @@ estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time, } else estimate_calls_size_and_time (e->callee, size, time, - possible_truths); + possible_truths, + known_vals, known_binfos); } } - /* TODO: look for devirtualizing oppurtunities. */ for (e = node->indirect_calls; e; e = e->next_callee) { struct inline_edge_summary *es = inline_edge_summary (e); if (!es->predicate || evaluate_predicate (es->predicate, possible_truths)) - estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE); + { + estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE); + estimate_edge_devirt_benefit (e, size, time, REG_BR_PROB_BASE, + known_vals, known_binfos); + } } } /* Estimate size and time needed to execute NODE assuming - POSSIBLE_TRUTHS clause. */ + POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information + about NODE's arguments. */ static void estimate_node_size_and_time (struct cgraph_node *node, clause_t possible_truths, + VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos, int *ret_size, int *ret_time, VEC (inline_param_summary_t, heap) *inline_param_summary) @@ -2258,7 +2348,8 @@ estimate_node_size_and_time (struct cgraph_node *node, if (time > MAX_TIME * INLINE_TIME_SCALE) time = MAX_TIME * INLINE_TIME_SCALE; - estimate_calls_size_and_time (node, &size, &time, possible_truths); + estimate_calls_size_and_time (node, &size, &time, possible_truths, + known_vals, known_binfos); time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE; size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE; @@ -2276,17 +2367,20 @@ estimate_node_size_and_time (struct cgraph_node *node, /* Estimate size and time needed to execute callee of EDGE assuming that parameters known to be constant at caller of EDGE are propagated. - KNOWN_VALs is a vector of assumed known constant values for parameters. */ + KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values + and types for parameters. */ void estimate_ipcp_clone_size_and_time (struct cgraph_node *node, VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos, int *ret_size, int *ret_time) { clause_t clause; clause = evaluate_conditions_for_known_args (node, false, known_vals); - estimate_node_size_and_time (node, clause, ret_size, ret_time, + estimate_node_size_and_time (node, clause, known_vals, known_binfos, + ret_size, ret_time, NULL); } @@ -2542,9 +2636,9 @@ inline_merge_summary (struct cgraph_edge *edge) int count = ipa_get_cs_argument_count (args); int i; - clause = evaluate_conditions_for_edge (edge, true); + evaluate_properties_for_edge (edge, true, &clause, NULL, NULL); if (count) - VEC_safe_grow_cleared (int, heap, operand_map, count); + VEC_safe_grow_cleared (int, heap, operand_map, count); for (i = 0; i < count; i++) { struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i); @@ -2588,7 +2682,8 @@ inline_merge_summary (struct cgraph_edge *edge) for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++) info->size += e->size, info->time += e->time; estimate_calls_size_and_time (to, &info->size, &info->time, - ~(clause_t)(1 << predicate_false_condition)); + ~(clause_t)(1 << predicate_false_condition), + NULL, NULL); inline_update_callee_summaries (edge->callee, inline_edge_summary (edge)->loop_depth); @@ -2616,13 +2711,21 @@ do_estimate_edge_time (struct cgraph_edge *edge) int time; int size; gcov_type ret; + struct cgraph_node *callee; + clause_t clause; + VEC (tree, heap) *known_vals; + VEC (tree, heap) *known_binfos; struct inline_edge_summary *es = inline_edge_summary (edge); + callee = cgraph_function_or_thunk_node (edge->callee, NULL); + gcc_checking_assert (edge->inline_failed); - estimate_node_size_and_time (cgraph_function_or_thunk_node (edge->callee, - NULL), - evaluate_conditions_for_edge (edge, true), + evaluate_properties_for_edge (edge, true, + &clause, &known_vals, &known_binfos); + estimate_node_size_and_time (callee, clause, known_vals, known_binfos, &size, &time, es->param); + VEC_free (tree, heap, known_vals); + VEC_free (tree, heap, known_binfos); ret = (((gcov_type)time - es->call_stmt_time) * edge->frequency @@ -2656,6 +2759,9 @@ do_estimate_edge_growth (struct cgraph_edge *edge) { int size; struct cgraph_node *callee; + clause_t clause; + VEC (tree, heap) *known_vals; + VEC (tree, heap) *known_binfos; /* When we do caching, use do_estimate_edge_time to populate the entry. */ @@ -2668,13 +2774,17 @@ do_estimate_edge_growth (struct cgraph_edge *edge) gcc_checking_assert (size); return size - (size > 0); } + callee = cgraph_function_or_thunk_node (edge->callee, NULL); /* Early inliner runs without caching, go ahead and do the dirty work. */ gcc_checking_assert (edge->inline_failed); - estimate_node_size_and_time (callee, - evaluate_conditions_for_edge (edge, true), + evaluate_properties_for_edge (edge, true, + &clause, &known_vals, &known_binfos); + estimate_node_size_and_time (callee, clause, known_vals, known_binfos, &size, NULL, NULL); + VEC_free (tree, heap, known_vals); + VEC_free (tree, heap, known_binfos); gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size); return size - inline_edge_summary (edge)->call_stmt_size; } diff --git a/gcc/ipa-inline.h b/gcc/ipa-inline.h index 6df7867..a2c6cac 100644 --- a/gcc/ipa-inline.h +++ b/gcc/ipa-inline.h @@ -169,6 +169,7 @@ int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *); int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *); void estimate_ipcp_clone_size_and_time (struct cgraph_node *, VEC (tree, heap) *known_vals, + VEC (tree, heap) *known_binfos, int *, int *); int do_estimate_growth (struct cgraph_node *); void inline_merge_summary (struct cgraph_edge *edge); diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index 58caa92..1a609a5 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -346,6 +346,9 @@ bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, VEC (cgraph_edge_p, heap) **new_edges); /* Indirect edge and binfo processing. */ +tree ipa_get_indirect_edge_target (struct cgraph_edge *ie, + VEC (tree, heap) *known_csts, + VEC (tree, heap) *known_binfs); struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree); /* Functions related to both. */ @@ -437,8 +440,8 @@ void ipa_prop_write_jump_functions (cgraph_node_set set); void ipa_prop_read_jump_functions (void); void ipa_update_after_lto_read (void); int ipa_get_param_decl_index (struct ipa_node_params *, tree); -tree ipa_cst_from_jfunc (struct ipa_node_params *info, - struct ipa_jump_func *jfunc); +tree ipa_value_from_jfunc (struct ipa_node_params *info, + struct ipa_jump_func *jfunc); /* From tree-sra.c: */ diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c index 7daa9d2..2260403 100644 --- a/gcc/tree-inline.c +++ b/gcc/tree-inline.c @@ -3521,7 +3521,7 @@ estimate_num_insns (gimple stmt, eni_weights *weights) case GIMPLE_CALL: { tree decl = gimple_call_fndecl (stmt); - struct cgraph_node *node; + struct cgraph_node *node = NULL; /* Do not special case builtins where we see the body. This just confuse inliner. */ @@ -3556,7 +3556,7 @@ estimate_num_insns (gimple stmt, eni_weights *weights) } } - cost = weights->call_cost; + cost = node ? weights->call_cost : weights->indirect_call_cost; if (gimple_call_lhs (stmt)) cost += estimate_move_cost (TREE_TYPE (gimple_call_lhs (stmt))); for (i = 0; i < gimple_call_num_args (stmt); i++) @@ -3674,6 +3674,7 @@ void init_inline_once (void) { eni_size_weights.call_cost = 1; + eni_size_weights.indirect_call_cost = 3; eni_size_weights.target_builtin_call_cost = 1; eni_size_weights.div_mod_cost = 1; eni_size_weights.omp_cost = 40; @@ -3686,6 +3687,7 @@ init_inline_once (void) underestimating the cost does less harm than overestimating it, so we choose a rather small value here. */ eni_time_weights.call_cost = 10; + eni_time_weights.indirect_call_cost = 15; eni_time_weights.target_builtin_call_cost = 1; eni_time_weights.div_mod_cost = 10; eni_time_weights.omp_cost = 40; diff --git a/gcc/tree-inline.h b/gcc/tree-inline.h index 2aac5f8..ba0b2c4 100644 --- a/gcc/tree-inline.h +++ b/gcc/tree-inline.h @@ -135,6 +135,9 @@ typedef struct eni_weights_d /* Cost per call. */ unsigned call_cost; + /* Cost per indirect call. */ + unsigned indirect_call_cost; + /* Cost per call to a target specific builtin */ unsigned target_builtin_call_cost; -- 2.7.4