Fix quadratic behaviour of early inliner
Jan Hubicka
hubicka@ucw.cz
Thu Dec 16 17:37:00 GMT 2010
Hi,
this patch (partly) fixes long compilation time seen at testcase attached to 44563.
The problem is that inliner exhibits quadratic behaviour on number of callees of function.
cgraph_estimate_size_after_inlining can estimate size after inlining one call (in constant time)
or after inline all calls of the given function. For that it walks all the callees to count
how many of them.
This is remainder of old inliner that did not differentiate in between call sites and
thus it either always inlined all calls to given function or none.
New inliner has the (estimated) profile info to make more sensible decisions and this functionality
remained only in early inlining.
Early inliner is still uninformed about hotness but since it inlines more or
less for size, this is not really important. So I've droped all the code
handling inlining all the callees. While doing so I also noticed that we do not
set proper inline_failed value for uninlinable call sites and fixed that too.
I've tested that the patch does not affect benchmark results on our nightly testers.
Bootstrapped/regtested x86_64-linux, will commit it shortly.
Honza
PR middle-end/44563
* cif-code.def (CALL_SITE_NOT_INLINABLE): New.
* ipa-inline.c: Update doplevel comment.
(cgraph_estimate_size_after_inlining): Remove times attribute.
(cgraph_mark_inline_edge): Update.
(cgraph_mark_inline): Remove.
(cgraph_estimate_growth): Update.
(cgraph_check_inline_limits): Remove one only argument.
(cgraph_edge_badness): Update.
(cgraph_decide_recursive_inlining): Update.
(cgraph_decide_inlining_of_small_function): Fix handling of tree_can_inline_p
and call_stmt_cannot_inline_p.
(cgraph_flatten): Likewise.
(cgraph_decide_inlining): Update.
(cgraph_decide_inlining_incrementally): Fix handling of call_stmt_cannot_inline_p.
Index: cif-code.def
===================================================================
*** cif-code.def (revision 167903)
--- cif-code.def (working copy)
*************** DEFCIFCODE(INDIRECT_UNKNOWN_CALL,
*** 90,92 ****
--- 90,96 ----
N_("indirect function call with a yet undetermined callee"))
DEFCIFCODE(OVERWRITABLE, N_("function body can be overwriten at linktime"))
+
+ /* Ths edge represents an indirect edge with a yet-undetermined callee . */
+ DEFCIFCODE(CALL_SITE_NOT_INLINABLE,
+ N_("call site is not inlinable (type or optimization attribute mismatch)"))
Index: ipa-inline.c
===================================================================
*** ipa-inline.c (revision 167903)
--- ipa-inline.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 28,34 ****
There are three major parts of this file:
! cgraph_mark_inline implementation
This function allows to mark given call inline and performs necessary
modifications of cgraph (production of the clones and updating overall
--- 28,34 ----
There are three major parts of this file:
! cgraph_mark_inline_edge implementation
This function allows to mark given call inline and performs necessary
modifications of cgraph (production of the clones and updating overall
*************** along with GCC; see the file COPYING3.
*** 91,108 ****
optimized allowing it to unfold abstraction penalty on C++ effectively and
cheaply.
- pass_ipa_early_inlining
-
- With profiling, the early inlining is also necessary to reduce
- instrumentation costs on program with high abstraction penalty (doing
- many redundant calls). This can't happen in parallel with early
- optimization and profile instrumentation, because we would end up
- re-instrumenting already instrumented function bodies we brought in via
- inlining.
-
- To avoid this, this pass is executed as IPA pass before profiling. It is
- simple wrapper to pass_early_inlining and ensures first inlining.
-
pass_ipa_inline
This is the main pass implementing simple greedy algorithm to do inlining
--- 91,96 ----
*************** along with GCC; see the file COPYING3.
*** 110,121 ****
inlining of functions called once. The pass compute just so called inline
plan (representation of inlining to be done in callgraph) and unlike early
inlining it is not performing the inlining itself.
-
- pass_apply_inline
-
- This pass performs actual inlining according to pass_ipa_inline on given
- function. Possible the function body before inlining is saved when it is
- needed for further inlining later.
*/
#include "config.h"
--- 98,103 ----
*************** cgraph_estimate_time_after_inlining (int
*** 199,212 ****
return time;
}
! /* Estimate self time of the function after inlining WHAT into TO. */
static inline int
! cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
struct cgraph_node *what)
{
int size = ((what->global.size - inline_summary (what)->size_inlining_benefit)
! * times + to->global.size);
gcc_assert (size >= 0);
return size;
}
--- 181,194 ----
return time;
}
! /* Estimate self size of the function after inlining WHAT into TO. */
static inline int
! cgraph_estimate_size_after_inlining (struct cgraph_node *to,
struct cgraph_node *what)
{
int size = ((what->global.size - inline_summary (what)->size_inlining_benefit)
! + to->global.size);
gcc_assert (size >= 0);
return size;
}
*************** cgraph_mark_inline_edge (struct cgraph_e
*** 335,341 ****
{
to = e->caller;
old_size = e->caller->global.size;
! new_size = cgraph_estimate_size_after_inlining (1, to, what);
to->global.size = new_size;
to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
}
--- 317,323 ----
{
to = e->caller;
old_size = e->caller->global.size;
! new_size = cgraph_estimate_size_after_inlining (to, what);
to->global.size = new_size;
to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
}
*************** cgraph_mark_inline_edge (struct cgraph_e
*** 352,381 ****
return false;
}
- /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
-
- static void
- cgraph_mark_inline (struct cgraph_edge *edge)
- {
- struct cgraph_node *to = edge->caller;
- struct cgraph_node *what = edge->callee;
- struct cgraph_edge *e, *next;
-
- gcc_assert (!edge->call_stmt_cannot_inline_p);
- /* Look for all calls, mark them inline and clone recursively
- all inlined functions. */
- for (e = what->callers; e; e = next)
- {
- next = e->next_caller;
- if (e->caller == to && e->inline_failed)
- {
- cgraph_mark_inline_edge (e, true, NULL);
- if (e == edge)
- edge = next;
- }
- }
- }
-
/* Estimate the growth caused by inlining NODE into all callees. */
static int
--- 334,339 ----
*************** cgraph_estimate_growth (struct cgraph_no
*** 393,399 ****
if (e->caller == node)
self_recursive = true;
if (e->inline_failed)
! growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
- e->caller->global.size);
}
--- 351,357 ----
if (e->caller == node)
self_recursive = true;
if (e->inline_failed)
! growth += (cgraph_estimate_size_after_inlining (e->caller, node)
- e->caller->global.size);
}
*************** cgraph_estimate_growth (struct cgraph_no
*** 424,444 ****
static bool
cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
! cgraph_inline_failed_t *reason, bool one_only)
{
- int times = 0;
- struct cgraph_edge *e;
int newsize;
int limit;
HOST_WIDE_INT stack_size_limit, inlined_stack;
- if (one_only)
- times = 1;
- else
- for (e = to->callees; e; e = e->next_callee)
- if (e->callee == what)
- times++;
-
if (to->global.inlined_to)
to = to->global.inlined_to;
--- 382,393 ----
static bool
cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
! cgraph_inline_failed_t *reason)
{
int newsize;
int limit;
HOST_WIDE_INT stack_size_limit, inlined_stack;
if (to->global.inlined_to)
to = to->global.inlined_to;
*************** cgraph_check_inline_limits (struct cgrap
*** 453,459 ****
/* Check the size after inlining against the function limits. But allow
the function to shrink if it went over the limits by forced inlining. */
! newsize = cgraph_estimate_size_after_inlining (times, to, what);
if (newsize >= to->global.size
&& newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
&& newsize > limit)
--- 402,408 ----
/* Check the size after inlining against the function limits. But allow
the function to shrink if it went over the limits by forced inlining. */
! newsize = cgraph_estimate_size_after_inlining (to, what);
if (newsize >= to->global.size
&& newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
&& newsize > limit)
*************** cgraph_edge_badness (struct cgraph_edge
*** 565,571 ****
{
gcov_type badness;
int growth =
! (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
- edge->caller->global.size);
if (edge->callee->local.disregard_inline_limits)
--- 514,520 ----
{
gcov_type badness;
int growth =
! (cgraph_estimate_size_after_inlining (edge->caller, edge->callee)
- edge->caller->global.size);
if (edge->callee->local.disregard_inline_limits)
*************** cgraph_decide_recursive_inlining (struct
*** 895,901 ****
/* Make sure that function is small enough to be considered for inlining. */
if (!max_depth
! || cgraph_estimate_size_after_inlining (1, node, node) >= limit)
return false;
heap = fibheap_new ();
lookup_recursive_calls (node, node, heap);
--- 844,850 ----
/* Make sure that function is small enough to be considered for inlining. */
if (!max_depth
! || cgraph_estimate_size_after_inlining (node, node) >= limit)
return false;
heap = fibheap_new ();
lookup_recursive_calls (node, node, heap);
*************** cgraph_decide_recursive_inlining (struct
*** 921,927 ****
/* Do the inlining and update list of recursive call during process. */
while (!fibheap_empty (heap)
! && (cgraph_estimate_size_after_inlining (1, node, master_clone)
<= limit))
{
struct cgraph_edge *curr
--- 870,876 ----
/* Do the inlining and update list of recursive call during process. */
while (!fibheap_empty (heap)
! && (cgraph_estimate_size_after_inlining (node, master_clone)
<= limit))
{
struct cgraph_edge *curr
*************** cgraph_decide_inlining_of_small_function
*** 1128,1134 ****
callee = edge->callee;
! growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
- edge->caller->global.size);
if (dump_file)
--- 1077,1083 ----
callee = edge->callee;
! growth = (cgraph_estimate_size_after_inlining (edge->caller, edge->callee)
- edge->caller->global.size);
if (dump_file)
*************** cgraph_decide_inlining_of_small_function
*** 1220,1227 ****
}
continue;
}
! if (!tree_can_inline_p (edge))
{
if (dump_file)
fprintf (dump_file, " inline_failed:%s.\n",
cgraph_inline_failed_string (edge->inline_failed));
--- 1169,1178 ----
}
continue;
}
! if (!tree_can_inline_p (edge)
! || edge->call_stmt_cannot_inline_p)
{
+ edge->inline_failed = CIF_CALL_SITE_NOT_INLINABLE;
if (dump_file)
fprintf (dump_file, " inline_failed:%s.\n",
cgraph_inline_failed_string (edge->inline_failed));
*************** cgraph_decide_inlining_of_small_function
*** 1244,1252 ****
else
{
struct cgraph_node *callee;
! if (edge->call_stmt_cannot_inline_p
! || !cgraph_check_inline_limits (edge->caller, edge->callee,
! &edge->inline_failed, true))
{
if (dump_file)
fprintf (dump_file, " Not inlining into %s:%s.\n",
--- 1195,1202 ----
else
{
struct cgraph_node *callee;
! if (!cgraph_check_inline_limits (edge->caller, edge->callee,
! &edge->inline_failed))
{
if (dump_file)
fprintf (dump_file, " Not inlining into %s:%s.\n",
*************** cgraph_flatten (struct cgraph_node *node
*** 1368,1374 ****
struct cgraph_node *orig_callee;
if (e->call_stmt_cannot_inline_p)
! continue;
if (!e->callee->analyzed)
{
--- 1318,1330 ----
struct cgraph_node *orig_callee;
if (e->call_stmt_cannot_inline_p)
! {
! e->inline_failed = CIF_CALL_SITE_NOT_INLINABLE;
! if (dump_file)
! fprintf (dump_file, "Not inlining: %s",
! cgraph_inline_failed_string (e->inline_failed));
! continue;
! }
if (!e->callee->analyzed)
{
*************** cgraph_flatten (struct cgraph_node *node
*** 1407,1412 ****
--- 1363,1369 ----
if (!tree_can_inline_p (e))
{
+ e->inline_failed = CIF_CALL_SITE_NOT_INLINABLE;
if (dump_file)
fprintf (dump_file, "Not inlining: %s",
cgraph_inline_failed_string (e->inline_failed));
*************** cgraph_decide_inlining (void)
*** 1555,1564 ****
}
if (cgraph_check_inline_limits (node->callers->caller, node,
! &reason, false))
{
struct cgraph_node *caller = node->callers->caller;
! cgraph_mark_inline (node->callers);
if (dump_file)
fprintf (dump_file,
" Inlined into %s which now has %i size"
--- 1512,1521 ----
}
if (cgraph_check_inline_limits (node->callers->caller, node,
! &reason))
{
struct cgraph_node *caller = node->callers->caller;
! cgraph_mark_inline_edge (node->callers, true, NULL);
if (dump_file)
fprintf (dump_file,
" Inlined into %s which now has %i size"
*************** cgraph_decide_inlining_incrementally (st
*** 1636,1643 ****
if (!e->callee->local.disregard_inline_limits
&& (mode != INLINE_ALL || !e->callee->local.inlinable))
continue;
- if (e->call_stmt_cannot_inline_p)
- continue;
if (dump_file)
fprintf (dump_file,
"Considering to always inline inline candidate %s.\n",
--- 1593,1598 ----
*************** cgraph_decide_inlining_incrementally (st
*** 1648,1655 ****
fprintf (dump_file, "Not inlining: recursive call.\n");
continue;
}
! if (!tree_can_inline_p (e))
{
if (dump_file)
fprintf (dump_file,
"Not inlining: %s",
--- 1603,1612 ----
fprintf (dump_file, "Not inlining: recursive call.\n");
continue;
}
! if (!tree_can_inline_p (e)
! || e->call_stmt_cannot_inline_p)
{
+ e->inline_failed = CIF_CALL_SITE_NOT_INLINABLE;
if (dump_file)
fprintf (dump_file,
"Not inlining: %s",
*************** cgraph_decide_inlining_incrementally (st
*** 1675,1681 ****
fprintf (dump_file, " Inlining %s into %s.\n",
cgraph_node_name (e->callee),
cgraph_node_name (e->caller));
! cgraph_mark_inline (e);
inlined = true;
}
--- 1632,1638 ----
fprintf (dump_file, " Inlining %s into %s.\n",
cgraph_node_name (e->callee),
cgraph_node_name (e->caller));
! cgraph_mark_inline_edge (e, true, NULL);
inlined = true;
}
*************** cgraph_decide_inlining_incrementally (st
*** 1725,1749 ****
if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
|| (!flag_inline_functions
&& !DECL_DECLARED_INLINE_P (e->callee->decl)))
! && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
> e->caller->global.size + allowed_growth)
&& cgraph_estimate_growth (e->callee) > allowed_growth)
{
if (dump_file)
fprintf (dump_file,
"Not inlining: code size would grow by %i.\n",
! cgraph_estimate_size_after_inlining (1, e->caller,
e->callee)
- e->caller->global.size);
continue;
}
! if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
! false)
! || e->call_stmt_cannot_inline_p)
{
if (dump_file)
! fprintf (dump_file, "Not inlining: %s.\n",
! cgraph_inline_failed_string (e->inline_failed));
continue;
}
if (!e->callee->analyzed)
--- 1682,1706 ----
if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
|| (!flag_inline_functions
&& !DECL_DECLARED_INLINE_P (e->callee->decl)))
! && (cgraph_estimate_size_after_inlining (e->caller, e->callee)
> e->caller->global.size + allowed_growth)
&& cgraph_estimate_growth (e->callee) > allowed_growth)
{
if (dump_file)
fprintf (dump_file,
"Not inlining: code size would grow by %i.\n",
! cgraph_estimate_size_after_inlining (e->caller,
e->callee)
- e->caller->global.size);
continue;
}
! if (e->call_stmt_cannot_inline_p
! || !tree_can_inline_p (e))
{
+ e->inline_failed = CIF_CALL_SITE_NOT_INLINABLE;
if (dump_file)
! fprintf (dump_file,
! "Not inlining: call site not inlinable.\n");
continue;
}
if (!e->callee->analyzed)
*************** cgraph_decide_inlining_incrementally (st
*** 1753,1763 ****
"Not inlining: Function body no longer available.\n");
continue;
}
! if (!tree_can_inline_p (e))
{
if (dump_file)
! fprintf (dump_file,
! "Not inlining: %s.",
cgraph_inline_failed_string (e->inline_failed));
continue;
}
--- 1710,1719 ----
"Not inlining: Function body no longer available.\n");
continue;
}
! if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed))
{
if (dump_file)
! fprintf (dump_file, "Not inlining: %s.\n",
cgraph_inline_failed_string (e->inline_failed));
continue;
}
*************** cgraph_decide_inlining_incrementally (st
*** 1767,1773 ****
fprintf (dump_file, " Inlining %s into %s.\n",
cgraph_node_name (e->callee),
cgraph_node_name (e->caller));
! cgraph_mark_inline (e);
inlined = true;
}
}
--- 1723,1729 ----
fprintf (dump_file, " Inlining %s into %s.\n",
cgraph_node_name (e->callee),
cgraph_node_name (e->caller));
! cgraph_mark_inline_edge (e, true, NULL);
inlined = true;
}
}
More information about the Gcc-patches
mailing list