#define INSNS_PER_CALL 10
-static void cgraph_expand_functions (void);
+static void cgraph_expand_all_functions (void);
static void cgraph_mark_functions_to_output (void);
static void cgraph_expand_function (struct cgraph_node *);
static tree record_call_1 (tree *, int *, void *);
static void cgraph_optimize_function (struct cgraph_node *);
static bool cgraph_default_inline_p (struct cgraph_node *n);
static void cgraph_analyze_function (struct cgraph_node *node);
+static void cgraph_decide_inlining_incrementally (struct cgraph_node *);
/* Statistics we collect about inlining algorithm. */
static int ncalls_inlined;
/* "extern inline" functions are never output locally. */
if (DECL_EXTERNAL (decl))
return false;
- /* We want to emit COMDAT functions only when absolutely neccesary. */
+ /* We want to emit COMDAT functions only when absolutely necessary. */
if (DECL_COMDAT (decl))
return false;
if (!DECL_INLINE (decl)
|| (!node->local.disregard_inline_limits
/* When declared inline, defer even the uninlinable functions.
- This allows them to be elliminated when unused. */
+ This allows them to be eliminated when unused. */
&& !DECL_DECLARED_INLINE_P (decl)
- && (node->local.inlinable || !cgraph_default_inline_p (node))))
+ && (!node->local.inlinable || !cgraph_default_inline_p (node))))
return true;
return false;
/* When not doing unit-at-a-time, output all functions enqueued.
Return true when such a functions were found. */
-static bool
+
+bool
cgraph_assemble_pending_functions (void)
{
bool output = false;
cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
if (!n->origin && !DECL_EXTERNAL (n->decl))
- cgraph_expand_function (n);
- output = true;
+ {
+ cgraph_expand_function (n);
+ output = true;
+ }
}
+
return output;
}
inlined in others.
??? It may make more sense to use one body for inlining and other
- body for expanding the function but this is dificult to do. */
-
- if (TREE_ASM_WRITTEN (decl))
+ body for expanding the function but this is difficult to do. */
+
+ /* If node->output is set, then this is a unit-at-a-time compilation
+ and we have already begun whole-unit analysis. This is *not*
+ testing for whether we've already emitted the function. That
+ case can be sort-of legitimately seen with real function
+ redefinition errors. I would argue that the front end should
+ never present us with such a case, but don't enforce that for now. */
+ if (node->output)
abort ();
/* Reset our datastructures so we can analyze the function again. */
memset (&node->rtl, 0, sizeof (node->rtl));
node->analyzed = false;
while (node->callees)
- cgraph_remove_call (node->decl, node->callees->callee->decl);
+ cgraph_remove_edge (node, node->callees->callee);
/* We may need to re-queue the node for assembling in case
we already proceeded it and ignored as not needed. */
/* If not unit at a time, then we need to create the call graph
now, so that called functions can be queued and emitted now. */
if (!flag_unit_at_a_time)
- cgraph_analyze_function (node);
+ {
+ cgraph_analyze_function (node);
+ cgraph_decide_inlining_incrementally (node);
+ }
if (decide_is_function_needed (node, decl))
cgraph_mark_needed_node (node);
timevar_push (TV_CGRAPH);
if (cgraph_dump_file)
{
- fprintf (cgraph_dump_file, "\nInitial entry points:");
+ fprintf (cgraph_dump_file, "Initial entry points:");
for (node = cgraph_nodes; node; node = node->next)
if (node->needed && DECL_SAVED_TREE (node->decl))
fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
if (cgraph_dump_file)
{
- fprintf (cgraph_dump_file, "\nUnit entry points:");
+ fprintf (cgraph_dump_file, "Unit entry points:");
for (node = cgraph_nodes; node; node = node->next)
if (node->needed && DECL_SAVED_TREE (node->decl))
fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
- fprintf (cgraph_dump_file, "\n");
+ fprintf (cgraph_dump_file, "\n\nInitial ");
dump_cgraph (cgraph_dump_file);
}
}
}
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "\n");
+ {
+ fprintf (cgraph_dump_file, "\n\nReclaimed ");
+ dump_cgraph (cgraph_dump_file);
+ }
ggc_collect ();
timevar_pop (TV_CGRAPH);
}
cgraph_expand_function (struct cgraph_node *node)
{
tree decl = node->decl;
- struct cgraph_edge *e;
if (flag_unit_at_a_time)
announce_function (decl);
via lang_expand_decl_stmt. */
(*lang_hooks.callgraph.expand_function) (decl);
- if (!flag_unit_at_a_time)
- {
- if (!node->local.inlinable
- || (!node->local.disregard_inline_limits
- && !cgraph_default_inline_p (node)))
- DECL_SAVED_TREE (node->decl) = NULL;
- }
- else
- {
- for (e = node->callers; e; e = e->next_caller)
- if (e->inline_call)
- break;
- if (!e)
- DECL_SAVED_TREE (decl) = NULL;
- }
+ if (!cgraph_function_possibly_inlined_p (decl))
+ DECL_SAVED_TREE (decl) = NULL;
current_function_decl = NULL;
}
if (cgraph_dump_file)
{
- fprintf (cgraph_dump_file, "Found inline predecesors of %s:",
+ fprintf (cgraph_dump_file, " Found inline predecesors of %s:",
cgraph_node_name (node));
for (i = 0; i < nfound; i++)
{
if (cgraph_dump_file)
{
- fprintf (cgraph_dump_file, "Found inline successors of %s:",
+ fprintf (cgraph_dump_file, " Found inline successors of %s:",
cgraph_node_name (node));
for (i = 0; i < nfound; i++)
{
cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
struct cgraph_node *what)
{
- return (what->global.insns - INSNS_PER_CALL) *times + to->global.insns;
+ return (what->global.insns - INSNS_PER_CALL) * times + to->global.insns;
}
/* Estimate the growth caused by inlining NODE into all callees. */
bool called = false;
int new_insns;
+ what->global.inlined = 1;
for (e = what->callers; e; e = e->next_caller)
{
if (e->caller == to)
to->global.insns = new_insns;
if (!called && !what->needed && !what->origin
+ && flag_unit_at_a_time
&& !DECL_EXTERNAL (what->decl))
{
if (!what->global.will_be_output)
return true;
}
-/* Return true when function N is small enought to be inlined. */
+/* Return true when function N is small enough to be inlined. */
static bool
cgraph_default_inline_p (struct cgraph_node *n)
All inline candidates are put into prioritized heap based on estimated
growth of the overall number of instructions and then update the estimates.
- INLINED and INLINED_CALEES are just pointers to arrays large enought
+ INLINED and INLINED_CALEES are just pointers to arrays large enough
to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
static void
}
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "\n\nDeciding on inlining: ");
+ fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n");
while ((node = fibheap_extract_min (heap)) && overall_insns <= max_insns)
{
struct cgraph_edge *e;
heap_node[node->uid] = NULL;
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "Considering %s %i insns, growth %i.\n",
+ fprintf (cgraph_dump_file,
+ "\nConsidering %s with %i insns\n"
+ " Estimated growth is %+i insns.\n",
cgraph_node_name (node), node->global.insns,
cgraph_estimate_growth (node));
if (!cgraph_default_inline_p (node))
{
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "Function too large.\n");
+ fprintf (cgraph_dump_file, " Function too large.\n");
continue;
}
ninlined_callees = cgraph_inlined_callees (node, inlined_callees);
for (i = 0; i < ninlined; i++)
inlined[i]->output = 0, node->aux = 0;
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "Not inlining into %s\n",
+ fprintf (cgraph_dump_file, " Not inlining into %s.\n",
cgraph_node_name (e->caller));
continue;
}
fibheap_replace_key (heap, heap_node[inlined[i]->uid],
cgraph_estimate_growth (inlined[i]));
}
+ if (cgraph_dump_file)
+ fprintf (cgraph_dump_file,
+ " Inlined into %s which now has %i insns.\n",
+ cgraph_node_name (e->caller),
+ e->caller->global.insns);
+
}
- /* Similarly all functions called by function we just inlined
+ /* Similarly all functions called by the function we just inlined
are now called more times; update keys. */
for (e = node->callees; e; e = e->next_callee)
inlined_callees[i]->output = 0, node->aux = 0;
}
if (cgraph_dump_file)
- fprintf (cgraph_dump_file,
- "Created %i clones, Num insns:%i (%+i), %.2f%%.\n\n",
- node->global.cloned_times - 1,
- overall_insns, overall_insns - old_insns,
- overall_insns * 100.0 / initial_insns);
+ fprintf (cgraph_dump_file,
+ " Inlined %i times for a net change of %+i insns.\n",
+ node->global.cloned_times, overall_insns - old_insns);
}
if (cgraph_dump_file && !fibheap_empty (heap))
- fprintf (cgraph_dump_file, "inline-unit-growth limit reached.\n");
+ fprintf (cgraph_dump_file, "\nReached the inline-unit-growth limit.\n");
fibheap_delete (heap);
free (heap_node);
}
xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
int ninlined;
int ninlined_callees;
+ int old_insns = 0;
int i, y;
for (node = cgraph_nodes; node; node = node->next)
nnodes = cgraph_postorder (order);
+ if (cgraph_dump_file)
+ fprintf (cgraph_dump_file,
+ "\nDeciding on inlining. Starting with %i insns.\n",
+ initial_insns);
+
for (node = cgraph_nodes; node; node = node->next)
node->aux = 0;
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "\n\nDeciding on always_inline functions:\n");
+ fprintf (cgraph_dump_file, "\nInlining always_inline functions:\n");
/* In the first pass mark all always_inline edges. Do this with a priority
- so no our decisions makes this impossible. */
+ so none of our later choices will make this impossible. */
for (i = nnodes - 1; i >= 0; i--)
{
struct cgraph_edge *e;
continue;
if (cgraph_dump_file)
fprintf (cgraph_dump_file,
- "Considering %s %i insns (always inline)\n",
- cgraph_node_name (node), node->global.insns);
+ "\nConsidering %s %i insns (always inline)\n",
+ cgraph_node_name (e->callee), e->callee->global.insns);
ninlined = cgraph_inlined_into (order[i], inlined);
for (; e; e = e->next_callee)
{
+ old_insns = overall_insns;
if (e->inline_call || !e->callee->local.disregard_inline_limits)
continue;
if (e->callee->output || e->callee == node)
for (y = 0; y < ninlined_callees; y++)
inlined_callees[y]->output = 0, node->aux = 0;
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "Inlined %i times. Now %i insns\n\n",
- node->global.cloned_times, overall_insns);
+ fprintf (cgraph_dump_file,
+ " Inlined into %s which now has %i insns.\n",
+ cgraph_node_name (node->callees->caller),
+ node->callees->caller->global.insns);
}
+ if (cgraph_dump_file && node->global.cloned_times > 0)
+ fprintf (cgraph_dump_file,
+ " Inlined %i times for a net change of %+i insns.\n",
+ node->global.cloned_times, overall_insns - old_insns);
for (y = 0; y < ninlined; y++)
inlined[y]->output = 0, node->aux = 0;
}
cgraph_decide_inlining_of_small_functions (inlined, inlined_callees);
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "\n\nFunctions to inline once:\n");
+ fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
/* And finally decide what functions are called once. */
{
if (cgraph_dump_file)
fprintf (cgraph_dump_file,
- "Considering %s %i insns (called once)\n",
- cgraph_node_name (node), node->global.insns);
+ "\nConsidering %s %i insns.\n"
+ " Called once from %s %i insns.\n",
+ cgraph_node_name (node), node->global.insns,
+ cgraph_node_name (node->callers->caller),
+ node->callers->caller->global.insns);
ninlined = cgraph_inlined_into (node->callers->caller, inlined);
+ old_insns = overall_insns;
if (cgraph_check_inline_limits
(node->callers->caller, node, inlined, ninlined))
{
for (y = 0; y < ninlined_callees; y++)
inlined_callees[y]->output = 0, node->aux = 0;
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "Inlined. Now %i insns\n\n", overall_insns);
+ fprintf (cgraph_dump_file,
+ " Inlined into %s which now has %i insns"
+ " for a net change of %+i insns.\n",
+ cgraph_node_name (node->callers->caller),
+ node->callers->caller->global.insns,
+ overall_insns - old_insns);
}
+ else
+ {
+ if (cgraph_dump_file)
+ fprintf (cgraph_dump_file,
+ " Inline limit reached, not inlined.\n");
+ }
for (y = 0; y < ninlined; y++)
inlined[y]->output = 0, node->aux = 0;
}
if (cgraph_dump_file)
fprintf (cgraph_dump_file,
- "\nInlined %i calls, elliminated %i functions, %i insns turned to %i insns.\n",
+ "\nInlined %i calls, eliminated %i functions, "
+ "%i insns turned to %i insns.\n\n",
ncalls_inlined, nfunctions_inlined, initial_insns,
overall_insns);
free (order);
free (inlined_callees);
}
+/* Decide on the inlining. We do so in the topological order to avoid
+ expenses on updating datastructures. */
+
+static void
+cgraph_decide_inlining_incrementally (struct cgraph_node *node)
+{
+ struct cgraph_edge *e;
+ struct cgraph_node **inlined =
+ xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
+ struct cgraph_node **inlined_callees =
+ xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
+ int ninlined;
+ int ninlined_callees;
+ int y;
+
+ ninlined = cgraph_inlined_into (node, inlined);
+
+ /* First of all look for always inline functions. */
+ for (e = node->callees; e; e = e->next_callee)
+ if (e->callee->local.disregard_inline_limits && !e->callee->output
+ && e->callee != node && !e->inline_call)
+ {
+ ninlined_callees = cgraph_inlined_callees (e->callee, inlined_callees);
+ cgraph_mark_inline (node, e->callee, inlined, ninlined,
+ inlined_callees, ninlined_callees);
+ for (y = 0; y < ninlined_callees; y++)
+ inlined_callees[y]->output = 0, node->aux = 0;
+ }
+
+ /* Now do the automatic inlining. */
+ for (e = node->callees; e; e = e->next_callee)
+ if (e->callee->local.inlinable && !e->callee->output
+ && e->callee != node && !e->inline_call
+ && cgraph_default_inline_p (e->callee)
+ && cgraph_check_inline_limits (node, e->callee, inlined,
+ ninlined))
+ {
+ ninlined_callees = cgraph_inlined_callees (e->callee, inlined_callees);
+ cgraph_mark_inline (node, e->callee, inlined, ninlined,
+ inlined_callees, ninlined_callees);
+ for (y = 0; y < ninlined_callees; y++)
+ inlined_callees[y]->output = 0, node->aux = 0;
+ }
+
+ /* Clear the flags set by cgraph_inlined_into. */
+ for (y = 0; y < ninlined; y++)
+ inlined[y]->output = 0, node->aux = 0;
+
+ free (inlined);
+ free (inlined_callees);
+}
+
+
/* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
bool
order). */
static void
-cgraph_expand_functions (void)
+cgraph_expand_all_functions (void)
{
struct cgraph_node *node;
struct cgraph_node **order =
struct cgraph_node *node;
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "Marking local functions:");
+ fprintf (cgraph_dump_file, "\nMarking local functions:");
/* Figure out functions we want to assemble. */
for (node = cgraph_nodes; node; node = node->next)
fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
}
if (cgraph_dump_file)
- fprintf (cgraph_dump_file, "\n");
+ fprintf (cgraph_dump_file, "\n\n");
}
/* Perform simple optimizations based on callgraph. */
timevar_push (TV_CGRAPHOPT);
if (!quiet_flag)
fprintf (stderr, "Performing intraprocedural optimizations\n");
+
+ cgraph_mark_local_functions ();
if (cgraph_dump_file)
{
- fprintf (cgraph_dump_file, "Initial callgraph:");
+ fprintf (cgraph_dump_file, "Marked ");
dump_cgraph (cgraph_dump_file);
}
- cgraph_mark_local_functions ();
cgraph_decide_inlining ();
-
cgraph_global_info_ready = true;
if (cgraph_dump_file)
{
- fprintf (cgraph_dump_file, "Optimized callgraph:");
+ fprintf (cgraph_dump_file, "Optimized ");
dump_cgraph (cgraph_dump_file);
}
timevar_pop (TV_CGRAPHOPT);
- if (!quiet_flag)
- fprintf (stderr, "Assembling functions:");
/* Output everything. */
- cgraph_expand_functions ();
+ if (!quiet_flag)
+ fprintf (stderr, "Assembling functions:\n");
+ cgraph_expand_all_functions ();
if (cgraph_dump_file)
{
- fprintf (cgraph_dump_file, "Final callgraph:");
+ fprintf (cgraph_dump_file, "\nFinal ");
dump_cgraph (cgraph_dump_file);
}
}