Make inliner to take cgraph SCCs into account
Jan Hubicka
hubicka@ucw.cz
Sun Oct 28 11:18:00 GMT 2012
Hi,
this patch implements simple hints on strongly connected components to inliner.
It increases badness of inlining functions within the same scc component, since this
non-trivial recursive inlining is not win very often and it may blow up stack
frames a lot.
It also increases the entry points of SCC components to have bigger badness,
this is because inlining ufnctions in SCCs is usually also just complicating
callgraph furhter (it however can be great win when the recursion over SCC
is unlikely)
This is based on Richard's observation on one of the fortran testcases and
also on analysis of povray where we make our live very difficult by first
inlining within scc missing obvious inline of cheap entry of the component.
The badness update is a quick hack. I am experimenting with new and simpler
badness metric for 4.8. So with bit of luck good part of estimate_edge_badness
will go.
Bootstrapped/regtested x86_64-linux.
Honza
* ipa-inline.c (edge_badness): Reduce precision; use scc hints.
(inline_small_functions): Fix dumps; update all callees after inlining.
* ipa-inline.h (INLINE_HINT_in_scc, INLINE_HINT_same_scc): New constants.
(inline summary): Add SCC_NO.
* ipa-inline-analysis.c (dump_inline_hints): Dump SCC hints.
(reset_inline_summary): Reset scc_no.
(estimate_node_size_and_time): Set in_scc hint.
(do_estimate_edge_time): Add same_scc hint.
(do_estimate_edge_hints): Likewise.
Index: ipa-inline.c
===================================================================
*** ipa-inline.c (revision 192887)
--- ipa-inline.c (working copy)
*************** edge_badness (struct cgraph_edge *edge,
*** 845,852 ****
precision for small bandesses (those are interesting) yet we don't
overflow for growths that are still in interesting range.
! Fixed point arithmetic with point at 8th bit. */
! badness = ((gcov_type)growth) * (1<<(19+8));
badness = (badness + div / 2) / div;
/* Overall growth of inlining all calls of function matters: we want to
--- 845,852 ----
precision for small bandesses (those are interesting) yet we don't
overflow for growths that are still in interesting range.
! Fixed point arithmetic with point at 6th bit. */
! badness = ((gcov_type)growth) * (1<<(19+6));
badness = (badness + div / 2) / div;
/* Overall growth of inlining all calls of function matters: we want to
*************** edge_badness (struct cgraph_edge *edge,
*** 861,869 ****
We might mix the valud into the fraction by taking into account
relative growth of the unit, but for now just add the number
into resulting fraction. */
! if (badness > INT_MAX / 2)
{
! badness = INT_MAX / 2;
if (dump)
fprintf (dump_file, "Badness overflow\n");
}
--- 861,869 ----
We might mix the valud into the fraction by taking into account
relative growth of the unit, but for now just add the number
into resulting fraction. */
! if (badness > INT_MAX / 4)
{
! badness = INT_MAX / 4;
if (dump)
fprintf (dump_file, "Badness overflow\n");
}
*************** edge_badness (struct cgraph_edge *edge,
*** 871,876 ****
--- 871,880 ----
| INLINE_HINT_loop_iterations
| INLINE_HINT_loop_stride))
badness /= 8;
+ if (hints & (INLINE_HINT_same_scc))
+ badness *= 4;
+ if (hints & (INLINE_HINT_in_scc))
+ badness *= 2;
if (dump)
{
fprintf (dump_file,
*************** inline_small_functions (void)
*** 1337,1352 ****
if (flag_indirect_inlining)
new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
- if (dump_file)
- fprintf (dump_file,
- "\nDeciding on inlining of small functions. Starting with size %i.\n",
- initial_size);
-
/* Compute overall unit size and other global parameters used by badness
metrics. */
max_count = 0;
- initialize_growth_caches ();
FOR_EACH_DEFINED_FUNCTION (node)
if (!node->global.inlined_to)
--- 1341,1350 ----
*************** inline_small_functions (void)
*** 1355,1369 ****
--- 1353,1377 ----
|| node->thunk.thunk_p)
{
struct inline_summary *info = inline_summary (node);
+ struct ipa_dfs_info *dfs = (struct ipa_dfs_info *) node->symbol.aux;
if (!DECL_EXTERNAL (node->symbol.decl))
initial_size += info->size;
+ info->scc_no = (dfs && dfs->next_cycle && dfs->next_cycle != node
+ ? dfs->scc_no + 1 : 0);
}
for (edge = node->callers; edge; edge = edge->next_caller)
if (max_count < edge->count)
max_count = edge->count;
}
+ ipa_free_postorder_info ();
+ initialize_growth_caches ();
+
+ if (dump_file)
+ fprintf (dump_file,
+ "\nDeciding on inlining of small functions. Starting with size %i.\n",
+ initial_size);
overall_size = initial_size;
max_size = compute_max_insns (overall_size);
*************** inline_small_functions (void)
*** 1528,1534 ****
reset_edge_caches (edge->callee);
reset_node_growth_cache (callee);
! update_callee_keys (edge_heap, edge->callee, updated_nodes);
}
where = edge->caller;
if (where->global.inlined_to)
--- 1536,1542 ----
reset_edge_caches (edge->callee);
reset_node_growth_cache (callee);
! update_callee_keys (edge_heap, where, updated_nodes);
}
where = edge->caller;
if (where->global.inlined_to)
Index: ipa-inline.h
===================================================================
*** ipa-inline.h (revision 192887)
--- ipa-inline.h (working copy)
*************** typedef struct GTY(()) condition
*** 47,53 ****
enum inline_hints_vals {
INLINE_HINT_indirect_call = 1,
INLINE_HINT_loop_iterations = 2,
! INLINE_HINT_loop_stride = 4
};
typedef int inline_hints;
--- 47,55 ----
enum inline_hints_vals {
INLINE_HINT_indirect_call = 1,
INLINE_HINT_loop_iterations = 2,
! INLINE_HINT_loop_stride = 4,
! INLINE_HINT_same_scc = 8,
! INLINE_HINT_in_scc = 16
};
typedef int inline_hints;
*************** struct GTY(()) inline_summary
*** 127,132 ****
--- 129,136 ----
/* Predicate on when some loop in the function becomes to have known
stride. */
struct predicate * GTY((skip)) loop_stride;
+ /* Number of SCC on the beggining of inlining process. */
+ int scc_no;
};
Index: ipa-inline-analysis.c
===================================================================
*** ipa-inline-analysis.c (revision 192887)
--- ipa-inline-analysis.c (working copy)
*************** dump_inline_hints (FILE *f, inline_hints
*** 639,644 ****
--- 639,654 ----
hints &= ~INLINE_HINT_loop_stride;
fprintf (f, " loop_stride");
}
+ if (hints & INLINE_HINT_same_scc)
+ {
+ hints &= ~INLINE_HINT_same_scc;
+ fprintf (f, " same_scc");
+ }
+ if (hints & INLINE_HINT_in_scc)
+ {
+ hints &= ~INLINE_HINT_in_scc;
+ fprintf (f, " in_scc");
+ }
gcc_assert (!hints);
}
*************** reset_inline_summary (struct cgraph_node
*** 973,978 ****
--- 983,989 ----
info->stack_frame_offset = 0;
info->size = 0;
info->time = 0;
+ info->scc_no = 0;
if (info->loop_iterations)
{
pool_free (edge_predicate_pool, info->loop_iterations);
*************** estimate_node_size_and_time (struct cgra
*** 2825,2831 ****
if (info->loop_stride
&& !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);
--- 2836,2843 ----
if (info->loop_stride
&& !evaluate_predicate (info->loop_stride, possible_truths))
hints |=INLINE_HINT_loop_stride;
! if (info->scc_no)
! hints |= INLINE_HINT_in_scc;
estimate_calls_size_and_time (node, &size, &time, &hints, possible_truths,
known_vals, known_binfos, known_aggs);
*************** do_estimate_edge_time (struct cgraph_edg
*** 3323,3328 ****
--- 3335,3343 ----
/* When caching, update the cache entry. */
if (edge_growth_cache)
{
+ struct cgraph_node *to = (edge->caller->global.inlined_to
+ ? edge->caller->global.inlined_to
+ : edge->caller);
if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache)
<= edge->uid)
VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache,
*************** do_estimate_edge_time (struct cgraph_edg
*** 3332,3337 ****
--- 3347,3355 ----
VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid).size
= size + (size >= 0);
+ if (inline_summary (to)->scc_no
+ && inline_summary (to)->scc_no == inline_summary (callee)->scc_no)
+ hints |= INLINE_HINT_same_scc;
VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid).hints
= hints + 1;
}
*************** do_estimate_edge_hints (struct cgraph_ed
*** 3392,3397 ****
--- 3410,3418 ----
VEC (tree, heap) *known_vals;
VEC (tree, heap) *known_binfos;
VEC (ipa_agg_jump_function_p, heap) *known_aggs;
+ struct cgraph_node *to = (edge->caller->global.inlined_to
+ ? edge->caller->global.inlined_to
+ : edge->caller);
/* When we do caching, use do_estimate_edge_time to populate the entry. */
*************** do_estimate_edge_hints (struct cgraph_ed
*** 3417,3422 ****
--- 3438,3446 ----
VEC_free (tree, heap, known_vals);
VEC_free (tree, heap, known_binfos);
VEC_free (ipa_agg_jump_function_p, heap, known_aggs);
+ if (inline_summary (to)->scc_no
+ && inline_summary (to)->scc_no == inline_summary (callee)->scc_no)
+ hints |= INLINE_HINT_same_scc;
return hints;
}
More information about the Gcc-patches
mailing list