This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Fix several time updating issues in the inliner analysis
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 25 Oct 2012 19:12:56 +0200
- Subject: Fix several time updating issues in the inliner analysis
Hi,
this patch adds several sanity checks that inline summaries are up to date and
makes sense; it also fixes several minor updating bugs and two perhaps important
integer overflows.
Bootstrapped/regtested x86_64-linux, will commit it shortly.
Honza
* ipa-cp.c (ipcp_discover_new_direct_edges): If something was turned
to direct call update the summary.
* ipa-inline-transform.c (inline_call): Sanity check that summaries
match the predicted effect; fix updating of summary after edge
redirection.
* ipa-inline-analysis.c (inline_node_duplication_hook): Do not try
to update the summary and recompute it instead.
(estimate_function_body_sizes): Fix self size estimation; double
check that it agrees with inline_update_overall_summary.
(estimate_edge_size_and_time): Handle devirtualizaiton costs.
(estimate_edge_devirt_benefit): Update to be called from
estimate_edge_size_and_time.
(estimate_calls_size_and_time): Update.
(estimate_node_size_and_time): Watch overflows.
(inline_merge_summary): Likewise.
* ipa-prob.c: Include ipa-inline.h
(ipa_make_edge_direct_to_target): After redirection update the summary.
Index: ipa-cp.c
===================================================================
*** ipa-cp.c (revision 192809)
--- ipa-cp.c (working copy)
*************** ipcp_discover_new_direct_edges (struct c
*** 1688,1693 ****
--- 1688,1694 ----
VEC (tree, heap) *known_vals)
{
struct cgraph_edge *ie, *next_ie;
+ bool found = false;
for (ie = node->indirect_calls; ie; ie = next_ie)
{
*************** ipcp_discover_new_direct_edges (struct c
*** 1696,1703 ****
next_ie = ie->next_callee;
target = ipa_get_indirect_edge_target (ie, known_vals, NULL, NULL);
if (target)
! ipa_make_edge_direct_to_target (ie, target);
}
}
/* Vector of pointers which for linked lists of clones of an original crgaph
--- 1697,1710 ----
next_ie = ie->next_callee;
target = ipa_get_indirect_edge_target (ie, known_vals, NULL, NULL);
if (target)
! {
! ipa_make_edge_direct_to_target (ie, target);
! found = true;
! }
}
+ /* Turning calls to direct calls will improve overall summary. */
+ if (found)
+ inline_update_overall_summary (node);
}
/* Vector of pointers which for linked lists of clones of an original crgaph
Index: ipa-inline-transform.c
===================================================================
*** ipa-inline-transform.c (revision 192809)
--- ipa-inline-transform.c (working copy)
*************** inline_call (struct cgraph_edge *e, bool
*** 209,214 ****
--- 209,219 ----
struct cgraph_node *to = NULL;
struct cgraph_edge *curr = e;
struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
+ bool new_edges_found = false;
+
+ #ifdef ENABLE_CHECKING
+ int estimated_growth = estimate_edge_growth (e);
+ #endif
/* Don't inline inlined edges. */
gcc_assert (e->inline_failed);
*************** inline_call (struct cgraph_edge *e, bool
*** 248,266 ****
old_size = inline_summary (to)->size;
inline_merge_summary (e);
if (update_overall_summary)
inline_update_overall_summary (to);
new_size = inline_summary (to)->size;
if (overall_size)
*overall_size += new_size - old_size;
ncalls_inlined++;
/* This must happen after inline_merge_summary that rely on jump
functions of callee to not be updated. */
! if (optimize)
! return ipa_propagate_indirect_call_infos (curr, new_edges);
! else
! return false;
}
--- 253,277 ----
old_size = inline_summary (to)->size;
inline_merge_summary (e);
+ if (optimize)
+ new_edges_found = ipa_propagate_indirect_call_infos (curr, new_edges);
if (update_overall_summary)
inline_update_overall_summary (to);
new_size = inline_summary (to)->size;
+ #ifdef ENABLE_CHECKING
+ /* Verify that estimated growth match real growth. Allow off-by-one
+ error due to INLINE_SIZE_SCALE roudoff errors. */
+ gcc_assert (!update_overall_summary || !overall_size
+ || abs (estimated_growth - (new_size - old_size)) <= 1);
+ #endif
+
if (overall_size)
*overall_size += new_size - old_size;
ncalls_inlined++;
/* This must happen after inline_merge_summary that rely on jump
functions of callee to not be updated. */
! return new_edges_found;
}
Index: ipa-inline-analysis.c
===================================================================
*** ipa-inline-analysis.c (revision 192809)
--- ipa-inline-analysis.c (working copy)
*************** inline_node_duplication_hook (struct cgr
*** 1081,1087 ****
struct predicate true_pred = true_predicate ();
size_time_entry *e;
int optimized_out_size = 0;
- gcov_type optimized_out_time = 0;
bool inlined_to_p = false;
struct cgraph_edge *edge;
--- 1081,1086 ----
*************** inline_node_duplication_hook (struct cgr
*** 1123,1132 ****
possible_truths,
info);
if (false_predicate_p (&new_predicate))
! {
! optimized_out_size += e->size;
! optimized_out_time += e->time;
! }
else
account_size_time (info, e->size, e->time, &new_predicate);
}
--- 1122,1128 ----
possible_truths,
info);
if (false_predicate_p (&new_predicate))
! optimized_out_size += e->size;
else
account_size_time (info, e->size, e->time, &new_predicate);
}
*************** inline_node_duplication_hook (struct cgr
*** 1149,1157 ****
&& !false_predicate_p (es->predicate))
{
optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
- optimized_out_time += (es->call_stmt_time
- * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
- * edge->frequency);
edge->frequency = 0;
}
edge_set_predicate (edge, &new_predicate);
--- 1145,1150 ----
*************** inline_node_duplication_hook (struct cgr
*** 1174,1182 ****
&& !false_predicate_p (es->predicate))
{
optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE;
- optimized_out_time += (es->call_stmt_time
- * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)
- * edge->frequency);
edge->frequency = 0;
}
edge_set_predicate (edge, &new_predicate);
--- 1167,1172 ----
*************** inline_node_duplication_hook (struct cgr
*** 1193,1214 ****
about updating self sizes, because size vectors already contains
sizes of the calees. */
gcc_assert (!inlined_to_p
! || (!optimized_out_size && !optimized_out_time));
!
! info->size -= optimized_out_size / INLINE_SIZE_SCALE;
! info->self_size -= optimized_out_size / INLINE_SIZE_SCALE;
! gcc_assert (info->size > 0);
! gcc_assert (info->self_size > 0);
!
! optimized_out_time /= INLINE_TIME_SCALE;
! if (optimized_out_time > MAX_TIME)
! optimized_out_time = MAX_TIME;
! info->time -= optimized_out_time;
! info->self_time -= optimized_out_time;
! if (info->time < 0)
! info->time = 0;
! if (info->self_time < 0)
! info->self_time = 0;
}
else
{
--- 1183,1189 ----
about updating self sizes, because size vectors already contains
sizes of the calees. */
gcc_assert (!inlined_to_p
! || !optimized_out_size);
}
else
{
*************** inline_node_duplication_hook (struct cgr
*** 1226,1231 ****
--- 1201,1207 ----
set_hint_predicate (&info->loop_stride, p);
}
}
+ inline_update_overall_summary (dst);
}
*************** estimate_function_body_sizes (struct cgr
*** 2405,2412 ****
struct predicate p;
this_time *= freq;
- time += this_time;
- size += this_size;
prob = eliminated_by_inlining_prob (stmt);
if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
--- 2381,2386 ----
*************** estimate_function_body_sizes (struct cgr
*** 2420,2425 ****
--- 2394,2405 ----
else
p = true_predicate ();
+ if (!false_predicate_p (&p))
+ {
+ time += this_time;
+ size += this_size;
+ }
+
/* We account everything but the calls. Calls have their own
size/time info attached to cgraph edges. This is necessary
in order to make the cost disappear after inlining. */
*************** compute_inline_parameters (struct cgraph
*** 2621,2626 ****
--- 2601,2612 ----
info->size = info->self_size;
info->stack_frame_offset = 0;
info->estimated_stack_size = info->estimated_self_stack_size;
+ #ifdef ENABLE_CHECKING
+ inline_update_overall_summary (node);
+ gcc_assert (info->time == info->self_time
+ && info->size == info->self_size);
+ #endif
+
pop_cfun ();
}
*************** struct gimple_opt_pass pass_inline_param
*** 2655,2687 ****
};
- /* Increase SIZE and TIME for size and time needed to handle edge E. */
-
- static void
- estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
- int prob)
- {
- struct inline_edge_summary *es = inline_edge_summary (e);
- *size += es->call_stmt_size * INLINE_SIZE_SCALE;
- *time += (es->call_stmt_time * prob / REG_BR_PROB_BASE
- * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE));
- if (*time > MAX_TIME * INLINE_TIME_SCALE)
- *time = MAX_TIME * INLINE_TIME_SCALE;
- }
-
-
/* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
KNOWN_BINFOS. */
static bool
estimate_edge_devirt_benefit (struct cgraph_edge *ie,
! int *size, int *time, int prob,
VEC (tree, heap) *known_vals,
VEC (tree, heap) *known_binfos,
VEC (ipa_agg_jump_function_p, heap) *known_aggs)
{
tree target;
- int time_diff, size_diff;
struct cgraph_node *callee;
struct inline_summary *isummary;
--- 2641,2657 ----
};
/* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
KNOWN_BINFOS. */
static bool
estimate_edge_devirt_benefit (struct cgraph_edge *ie,
! int *size, int *time,
VEC (tree, heap) *known_vals,
VEC (tree, heap) *known_binfos,
VEC (ipa_agg_jump_function_p, heap) *known_aggs)
{
tree target;
struct cgraph_node *callee;
struct inline_summary *isummary;
*************** estimate_edge_devirt_benefit (struct cgr
*** 2694,2705 ****
return false;
/* Account for difference in cost between indirect and direct calls. */
! size_diff = ((eni_size_weights.indirect_call_cost - eni_size_weights.call_cost)
! * INLINE_SIZE_SCALE);
! *size -= size_diff;
! time_diff = ((eni_time_weights.indirect_call_cost - eni_time_weights.call_cost)
! * INLINE_TIME_SCALE * prob / REG_BR_PROB_BASE);
! *time -= time_diff;
callee = cgraph_get_node (target);
if (!callee || !callee->analyzed)
--- 2664,2673 ----
return false;
/* Account for difference in cost between indirect and direct calls. */
! *size -= (eni_size_weights.indirect_call_cost - eni_size_weights.call_cost);
! *time -= (eni_time_weights.indirect_call_cost - eni_time_weights.call_cost);
! gcc_checking_assert (*time >= 0);
! gcc_checking_assert (*size >= 0);
callee = cgraph_get_node (target);
if (!callee || !callee->analyzed)
*************** estimate_edge_devirt_benefit (struct cgr
*** 2708,2713 ****
--- 2676,2709 ----
return isummary->inlinable;
}
+ /* Increase SIZE and TIME for size and time needed to handle edge E. */
+
+ static inline void
+ estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
+ int prob,
+ VEC (tree, heap) *known_vals,
+ VEC (tree, heap) *known_binfos,
+ VEC (ipa_agg_jump_function_p, heap) *known_aggs,
+ inline_hints *hints)
+
+ {
+ struct inline_edge_summary *es = inline_edge_summary (e);
+ int call_size = es->call_stmt_size;
+ int call_time = es->call_stmt_time;
+ if (!e->callee
+ && estimate_edge_devirt_benefit (e, &call_size, &call_time,
+ known_vals, known_binfos, known_aggs)
+ && hints
+ && cgraph_maybe_hot_edge_p (e))
+ *hints |= INLINE_HINT_indirect_call;
+ *size += call_size * INLINE_SIZE_SCALE;
+ *time += call_time * prob / REG_BR_PROB_BASE
+ * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE);
+ if (*time > MAX_TIME * INLINE_TIME_SCALE)
+ *time = MAX_TIME * INLINE_TIME_SCALE;
+ }
+
+
/* 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
*************** estimate_calls_size_and_time (struct cgr
*** 2731,2737 ****
{
/* Predicates of calls shall not use NOT_CHANGED codes,
sowe do not need to compute probabilities. */
! estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
}
else
estimate_calls_size_and_time (e->callee, size, time, hints,
--- 2727,2735 ----
{
/* Predicates of calls shall not use NOT_CHANGED codes,
sowe do not need to compute probabilities. */
! estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE,
! known_vals, known_binfos, known_aggs,
! hints);
}
else
estimate_calls_size_and_time (e->callee, size, time, hints,
*************** estimate_calls_size_and_time (struct cgr
*** 2743,2756 ****
{
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);
! if (estimate_edge_devirt_benefit (e, size, time, REG_BR_PROB_BASE,
! known_vals, known_binfos, known_aggs)
! && hints
! && cgraph_maybe_hot_edge_p (e))
! *hints |= INLINE_HINT_indirect_call;
! }
}
}
--- 2741,2749 ----
{
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,
! known_vals, known_binfos, known_aggs,
! hints);
}
}
*************** estimate_node_size_and_time (struct cgra
*** 2772,2778 ****
{
struct inline_summary *info = inline_summary (node);
size_time_entry *e;
! int size = 0, time = 0;
inline_hints hints = 0;
int i;
--- 2765,2772 ----
{
struct inline_summary *info = inline_summary (node);
size_time_entry *e;
! int size = 0;
! int time = 0;
inline_hints hints = 0;
int i;
*************** estimate_node_size_and_time (struct cgra
*** 2801,2806 ****
--- 2795,2802 ----
if (evaluate_predicate (&e->predicate, possible_truths))
{
size += e->size;
+ gcc_checking_assert (e->time >= 0);
+ gcc_checking_assert (time >= 0);
if (!inline_param_summary)
time += e->time;
else
*************** estimate_node_size_and_time (struct cgra
*** 2809,2818 ****
&e->predicate,
possible_truths,
inline_param_summary);
! time += e->time * prob / REG_BR_PROB_BASE;
}
}
if (info->loop_iterations
&& !evaluate_predicate (info->loop_iterations, possible_truths))
--- 2805,2821 ----
&e->predicate,
possible_truths,
inline_param_summary);
! gcc_checking_assert (prob >= 0);
! gcc_checking_assert (prob <= REG_BR_PROB_BASE);
! time += ((gcov_type)e->time * prob) / REG_BR_PROB_BASE;
}
+ if (time > MAX_TIME * INLINE_TIME_SCALE)
+ time = MAX_TIME * INLINE_TIME_SCALE;
+ gcc_checking_assert (time >= 0);
}
+ gcc_checking_assert (size >= 0);
+ gcc_checking_assert (time >= 0);
if (info->loop_iterations
&& !evaluate_predicate (info->loop_iterations, possible_truths))
*************** estimate_node_size_and_time (struct cgra
*** 2821,2838 ****
&& !evaluate_predicate (info->loop_stride, possible_truths))
hints |=INLINE_HINT_loop_stride;
- if (time > MAX_TIME * INLINE_TIME_SCALE)
- time = MAX_TIME * INLINE_TIME_SCALE;
estimate_calls_size_and_time (node, &size, &time, &hints, possible_truths,
known_vals, known_binfos, known_aggs);
! time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
! size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
if (dump_file
&& (dump_flags & TDF_DETAILS))
! fprintf (dump_file, "\n size:%i time:%i\n", size, time);
if (ret_time)
*ret_time = time;
if (ret_size)
--- 2824,2841 ----
&& !evaluate_predicate (info->loop_stride, possible_truths))
hints |=INLINE_HINT_loop_stride;
estimate_calls_size_and_time (node, &size, &time, &hints, possible_truths,
known_vals, known_binfos, known_aggs);
! gcc_checking_assert (size >= 0);
! gcc_checking_assert (time >= 0);
! time = RDIV (time, INLINE_TIME_SCALE);
! size = RDIV (size, INLINE_SIZE_SCALE);
if (dump_file
&& (dump_flags & TDF_DETAILS))
! fprintf (dump_file, "\n size:%i time:%i\n", (int)size, (int)time);
if (ret_time)
*ret_time = time;
if (ret_size)
*************** inline_merge_summary (struct cgraph_edge
*** 3224,3230 ****
int prob = predicate_probability (callee_info->conds,
&e->predicate,
clause, es->param);
! add_time = add_time * prob / REG_BR_PROB_BASE;
if (add_time > MAX_TIME * INLINE_TIME_SCALE)
add_time = MAX_TIME * INLINE_TIME_SCALE;
if (prob != REG_BR_PROB_BASE
--- 3227,3233 ----
int prob = predicate_probability (callee_info->conds,
&e->predicate,
clause, es->param);
! add_time = ((gcov_type)add_time * prob) / REG_BR_PROB_BASE;
if (add_time > MAX_TIME * INLINE_TIME_SCALE)
add_time = MAX_TIME * INLINE_TIME_SCALE;
if (prob != REG_BR_PROB_BASE
Index: ipa-prop.c
===================================================================
*** ipa-prop.c (revision 192809)
--- ipa-prop.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 30,35 ****
--- 30,36 ----
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-inline.h"
+ #include "ipa-inline.h"
#include "gimple.h"
#include "flags.h"
#include "diagnostic.h"
*************** struct cgraph_edge *
*** 2100,2105 ****
--- 2101,2107 ----
ipa_make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
{
struct cgraph_node *callee;
+ struct inline_edge_summary *es = inline_edge_summary (ie);
if (TREE_CODE (target) == ADDR_EXPR)
target = TREE_OPERAND (target, 0);
*************** ipa_make_edge_direct_to_target (struct c
*** 2115,2120 ****
--- 2117,2127 ----
gcc_assert (!callee->global.inlined_to);
cgraph_make_edge_direct (ie, callee);
+ es = inline_edge_summary (ie);
+ es->call_stmt_size -= (eni_size_weights.indirect_call_cost
+ - eni_size_weights.call_cost);
+ es->call_stmt_time -= (eni_time_weights.indirect_call_cost
+ - eni_time_weights.call_cost);
if (dump_file)
{
fprintf (dump_file, "ipa-prop: Discovered %s call to a known target "