cgraph_decide_inlining implements heuristics taking whole callgraph
into account, while cgraph_decide_inlining_incrementally considers
- only one function at a time and is used in non-unit-at-a-time mode. */
+ only one function at a time and is used in non-unit-at-a-time mode.
+
+ The inliner itself is split into several passes:
+
+ pass_inline_parameters
+
+ This pass computes local properties of functions that are used by inliner:
+ estimated function body size, whether function is inlinable at all and
+ stack frame consumption.
+
+ Before executing any of inliner passes, this local pass has to be applied
+ to each function in the callgraph (ie run as subpass of some earlier
+ IPA pass). The results are made out of date by any optimization applied
+ on the function body.
+
+ pass_early_inlining
+
+ Simple local inlining pass inlining callees into current function. This
+ pass makes no global whole compilation unit analysis and this when allowed
+ to do inlining expanding code size it might result in unbounded growth of
+ whole unit.
+
+ This is the main inlining pass in non-unit-at-a-time.
+
+ With unit-at-a-time the pass is run during conversion into SSA form.
+ Only functions already converted into SSA form are inlined, so the
+ conversion must happen in topological order on the callgraph (that is
+ maintained by pass manager). The functions after inlining are early
+ optimized so the early inliner sees unoptimized function itself, but
+ all considered callees are already 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
+ of small functions that results in overall growth of compilation unit and
+ 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"
#include "system.h"
#include "hashtab.h"
#include "coverage.h"
#include "ggc.h"
+#include "tree-flow.h"
+#include "rtl.h"
+
+/* Mode incremental inliner operate on:
+
+ In ALWAYS_INLINE only functions marked
+ always_inline are inlined. This mode is used after detecting cycle during
+ flattening.
+
+ In SIZE mode, only functions that reduce function body size after inlining
+ are inlined, this is used during early inlining.
+
+ In SPEED mode, all small functions are inlined. This might result in
+ unbounded growth of compilation unit and is used only in non-unit-at-a-time
+ mode.
+
+ in ALL mode, everything is inlined. This is used during flattening. */
+enum inlining_mode {
+ INLINE_NONE = 0,
+ INLINE_ALWAYS_INLINE,
+ INLINE_SIZE,
+ INLINE_SPEED,
+ INLINE_ALL
+};
+static bool
+cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode,
+ int);
+
/* Statistics we collect about inlining algorithm. */
static int ncalls_inlined;
static int nfunctions_inlined;
-static int initial_insns;
static int overall_insns;
-static int max_insns;
static gcov_type max_count;
/* Estimate size of the function after inlining WHAT into TO. */
void
cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate, bool update_original)
{
- struct cgraph_node *n;
-
- /* We may eliminate the need for out-of-line copy to be output. In that
- case just go ahead and re-use it. */
- if (!e->callee->callers->next_caller
- && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
- && duplicate
- && flag_unit_at_a_time)
- {
- gcc_assert (!e->callee->global.inlined_to);
- if (!DECL_EXTERNAL (e->callee->decl))
- overall_insns -= e->callee->global.insns, nfunctions_inlined++;
- duplicate = 0;
- }
- else if (duplicate)
+ HOST_WIDE_INT peak;
+ if (duplicate)
{
- n = cgraph_clone_node (e->callee, e->count, e->loop_nest, update_original);
- cgraph_redirect_edge_callee (e, n);
+ /* We may eliminate the need for out-of-line copy to be output.
+ In that case just go ahead and re-use it. */
+ if (!e->callee->callers->next_caller
+ && !e->callee->needed
+ && !cgraph_new_nodes
+ && flag_unit_at_a_time)
+ {
+ gcc_assert (!e->callee->global.inlined_to);
+ if (DECL_SAVED_TREE (e->callee->decl))
+ overall_insns -= e->callee->global.insns, nfunctions_inlined++;
+ duplicate = false;
+ }
+ else
+ {
+ struct cgraph_node *n;
+ n = cgraph_clone_node (e->callee, e->count, e->frequency, e->loop_nest,
+ update_original);
+ cgraph_redirect_edge_callee (e, n);
+ }
}
if (e->caller->global.inlined_to)
e->callee->global.inlined_to = e->caller->global.inlined_to;
else
e->callee->global.inlined_to = e->caller;
+ e->callee->global.stack_frame_offset
+ = e->caller->global.stack_frame_offset + e->caller->local.estimated_self_stack_size;
+ peak = e->callee->global.stack_frame_offset + e->callee->local.estimated_self_stack_size;
+ if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
+ e->callee->global.inlined_to->global.estimated_stack_size = peak;
/* Recursively clone all bodies. */
for (e = e->callee->callees; e; e = e->next_callee)
int old_insns = 0, new_insns = 0;
struct cgraph_node *to = NULL, *what;
+ if (e->callee->inline_decl)
+ cgraph_redirect_edge_callee (e, cgraph_node (e->callee->inline_decl));
+
gcc_assert (e->inline_failed);
e->inline_failed = NULL;
}
/* Return false when inlining WHAT into TO is not good idea
- as it would cause too large growth of function bodies. */
+ as it would cause too large growth of function bodies.
+ When ONE_ONLY is true, assume that only one call site is going
+ to be inlined, otherwise figure out how many call sites in
+ TO calls WHAT and verify that all can be inlined.
+ */
static bool
cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
- const char **reason)
+ const char **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;
- for (e = to->callees; e; e = e->next_callee)
- if (e->callee == what)
- times++;
-
/* When inlining large function body called once into small function,
take the inlined function as base for limiting the growth. */
if (to->local.self_insns > what->local.self_insns)
limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
+ /* 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 > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
+ if (newsize >= to->global.insns
+ && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
&& newsize > limit)
{
if (reason)
*reason = N_("--param large-function-growth limit reached");
return false;
}
+
+ stack_size_limit = to->local.estimated_self_stack_size;
+
+ stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
+
+ inlined_stack = (to->global.stack_frame_offset
+ + to->local.estimated_self_stack_size
+ + what->global.estimated_stack_size);
+ if (inlined_stack > stack_size_limit
+ && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
+ {
+ if (reason)
+ *reason = N_("--param large-stack-frame-growth limit reached");
+ return false;
+ }
return true;
}
bool
cgraph_default_inline_p (struct cgraph_node *n, const char **reason)
{
- if (!DECL_INLINE (n->decl))
+ tree decl = n->decl;
+
+ if (n->inline_decl)
+ decl = n->inline_decl;
+ if (!DECL_INLINE (decl))
{
if (reason)
*reason = N_("function not inlinable");
return false;
}
- if (!DECL_SAVED_TREE (n->decl))
+ if (!DECL_STRUCT_FUNCTION (decl)->cfg)
{
if (reason)
*reason = N_("function body not available");
return false;
}
- if (DECL_DECLARED_INLINE_P (n->decl))
+ if (DECL_DECLARED_INLINE_P (decl))
{
if (n->global.insns >= MAX_INLINE_INSNS_SINGLE)
{
&& (edge->count
<= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
return false;
+ if (lookup_attribute ("cold", DECL_ATTRIBUTES (edge->callee->decl))
+ || lookup_attribute ("cold", DECL_ATTRIBUTES (edge->caller->decl)))
+ return false;
+ if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
+ return true;
+ if (flag_guess_branch_prob
+ && edge->frequency < (CGRAPH_FREQ_MAX
+ / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
+ return false;
return true;
}
smallest badness are inlined first. After each inlining is performed
the costs of all caller edges of nodes affected are recomputed so the
metrics may accurately depend on values such as number of inlinable callers
- of the function or function body size.
-
- With profiling we use number of executions of each edge to drive the cost.
- We also should distinguish hot and cold calls where the cold calls are
- inlined into only when code size is overall improved.
- */
+ of the function or function body size. */
static int
cgraph_edge_badness (struct cgraph_edge *edge)
{
- if (max_count)
+ int badness;
+ int growth =
+ cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
+
+ growth -= edge->caller->global.insns;
+
+ /* Always prefer inlining saving code size. */
+ if (growth <= 0)
+ badness = INT_MIN - growth;
+
+ /* When profiling is available, base priorities -(#calls / growth).
+ So we optimize for overall number of "executed" inlined calls. */
+ else if (max_count)
+ badness = ((int)((double)edge->count * INT_MIN / max_count)) / growth;
+
+ /* When function local profile is available, base priorities on
+ growth / frequency, so we optimize for overall frequency of inlined
+ calls. This is not too accurate since while the call might be frequent
+ within function, the function itself is infrequent.
+
+ Other objective to optimize for is number of different calls inlined.
+ We add the estimated growth after inlining all functions to biass the
+ priorities slightly in this direction (so fewer times called functions
+ of the same size gets priority). */
+ else if (flag_guess_branch_prob)
{
+ int div = edge->frequency * 100 / CGRAPH_FREQ_BASE;
int growth =
cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
growth -= edge->caller->global.insns;
+ badness = growth * 256;
+
+ /* Decrease badness if call is nested. */
+ /* Compress the range so we don't overflow. */
+ if (div > 256)
+ div = 256 + ceil_log2 (div) - 8;
+ if (div < 1)
+ div = 1;
+ if (badness > 0)
+ badness /= div;
+ badness += cgraph_estimate_growth (edge->callee);
+ }
+ /* When function local profile is not available or it does not give
+ useful information (ie frequency is zero), base the cost on
+ loop nest and overall size growth, so we optimize for overall number
+ of functions fully inlined in program. */
+ else
+ {
+ int nest = MIN (edge->loop_nest, 8);
+ badness = cgraph_estimate_growth (edge->callee) * 256;
- /* Always prefer inlining saving code size. */
- if (growth <= 0)
- return INT_MIN - growth;
- return ((int)((double)edge->count * INT_MIN / max_count)) / growth;
+ /* Decrease badness if call is nested. */
+ if (badness > 0)
+ badness >>= nest;
+ else
+ {
+ badness <<= nest;
+ }
}
+ /* Make recursive inlining happen always after other inlining is done. */
+ if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
+ return badness + 1;
else
- {
- int nest = MIN (edge->loop_nest, 8);
- int badness = cgraph_estimate_growth (edge->callee) * 256;
-
- /* Decrease badness if call is nested. */
- if (badness > 0)
- badness >>= nest;
- else
- badness <<= nest;
-
- /* Make recursive inlining happen always after other inlining is done. */
- if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
- return badness + 1;
- else
- return badness;
- }
+ return badness;
}
/* Recompute heap nodes for each of caller edge. */
bitmap updated_nodes)
{
struct cgraph_edge *edge;
+ const char *failed_reason;
if (!node->local.inlinable || node->local.disregard_inline_limits
|| node->global.inlined_to)
bitmap_set_bit (updated_nodes, node->uid);
node->global.estimated_growth = INT_MIN;
+ if (!node->local.inlinable)
+ return;
+ /* Prune out edges we won't inline into anymore. */
+ if (!cgraph_default_inline_p (node, &failed_reason))
+ {
+ for (edge = node->callers; edge; edge = edge->next_caller)
+ if (edge->aux)
+ {
+ fibheap_delete_node (heap, edge->aux);
+ edge->aux = NULL;
+ if (edge->inline_failed)
+ edge->inline_failed = failed_reason;
+ }
+ return;
+ }
+
for (edge = node->callers; edge; edge = edge->next_caller)
if (edge->inline_failed)
{
lookup_recursive_calls (node, e->callee, heap);
}
-/* Find callgraph nodes closing a circle in the graph. The
- resulting hashtab can be used to avoid walking the circles.
- Uses the cgraph nodes ->aux field which needs to be zero
- before and will be zero after operation. */
-
-static void
-cgraph_find_cycles (struct cgraph_node *node, htab_t cycles)
-{
- struct cgraph_edge *e;
-
- if (node->aux)
- {
- void **slot;
- slot = htab_find_slot (cycles, node, INSERT);
- if (!*slot)
- {
- if (dump_file)
- fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node));
- *slot = node;
- }
- return;
- }
-
- node->aux = node;
- for (e = node->callees; e; e = e->next_callee)
- cgraph_find_cycles (e->callee, cycles);
- node->aux = 0;
-}
-
-/* Leafify the cgraph node. We have to be careful in recursing
- as to not run endlessly in circles of the callgraph.
- We do so by using a hashtab of cycle entering nodes as generated
- by cgraph_find_cycles. */
-
-static void
-cgraph_flatten_node (struct cgraph_node *node, htab_t cycles)
-{
- struct cgraph_edge *e;
-
- for (e = node->callees; e; e = e->next_callee)
- {
- /* Inline call, if possible, and recurse. Be sure we are not
- entering callgraph circles here. */
- if (e->inline_failed
- && e->callee->local.inlinable
- && !cgraph_recursive_inlining_p (node, e->callee,
- &e->inline_failed)
- && !htab_find (cycles, e->callee))
- {
- if (dump_file)
- fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee));
- cgraph_mark_inline_edge (e, true);
- cgraph_flatten_node (e->callee, cycles);
- }
- else if (dump_file)
- fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee));
- }
-}
-
/* Decide on recursive inlining: in the case function has recursive calls,
inline until body size reaches given argument. */
int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
fibheap_t heap;
struct cgraph_edge *e;
- struct cgraph_node *master_clone;
+ struct cgraph_node *master_clone, *next;
int depth = 0;
int n = 0;
+ if (optimize_size)
+ return false;
+
if (DECL_DECLARED_INLINE_P (node->decl))
{
limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
cgraph_node_name (node));
/* We need original clone to copy around. */
- master_clone = cgraph_clone_node (node, node->count, 1, false);
+ master_clone = cgraph_clone_node (node, node->count, CGRAPH_FREQ_BASE, 1, false);
master_clone->needed = true;
for (e = master_clone->callees; e; e = e->next_callee)
if (!e->inline_failed)
{
if (dump_file)
fprintf (dump_file,
- " maxmal depth reached\n");
+ " maximal depth reached\n");
continue;
}
into master clone gets queued just before master clone so we don't
need recursion. */
for (node = cgraph_nodes; node != master_clone;
- node = node->next)
- if (node->global.inlined_to == master_clone)
- cgraph_remove_node (node);
+ node = next)
+ {
+ next = node->next;
+ if (node->global.inlined_to == master_clone)
+ cgraph_remove_node (node);
+ }
cgraph_remove_node (master_clone);
/* FIXME: Recursive inlining actually reduces number of calls of the
function. At this place we should probably walk the function and
e->inline_failed = reason;
}
+/* Given whole compilation unit estimate of INSNS, compute how large we can
+ allow the unit to grow. */
+static int
+compute_max_insns (int insns)
+{
+ int max_insns = insns;
+ if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
+ max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
+
+ return ((HOST_WIDEST_INT) max_insns
+ * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
+}
+
/* We use greedy algorithm for inlining of small functions:
All inline candidates are put into prioritized heap based on estimated
growth of the overall number of instructions and then update the estimates.
const char *failed_reason;
fibheap_t heap = fibheap_new ();
bitmap updated_nodes = BITMAP_ALLOC (NULL);
+ int min_insns, max_insns;
if (dump_file)
fprintf (dump_file, "\nDeciding on smaller functions:\n");
edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
}
}
+
+ max_insns = compute_max_insns (overall_insns);
+ min_insns = overall_insns;
+
while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
{
int old_insns = overall_insns;
if (dump_file)
{
fprintf (dump_file,
- "\nConsidering %s with %i insns to be inlined into %s\n"
- " Estimated growth after inlined into all callees is %+i insns.\n"
- " Estimated badness is %i.\n",
+ "\nConsidering %s with %i insns\n",
cgraph_node_name (edge->callee),
- edge->callee->global.insns,
+ edge->callee->global.insns);
+ fprintf (dump_file,
+ " to be inlined into %s\n"
+ " Estimated growth after inlined into all callees is %+i insns.\n"
+ " Estimated badness is %i, frequency %.2f.\n",
cgraph_node_name (edge->caller),
cgraph_estimate_growth (edge->callee),
- cgraph_edge_badness (edge));
+ cgraph_edge_badness (edge),
+ edge->frequency / (double)CGRAPH_FREQ_BASE);
if (edge->count)
fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
}
}
}
- if (!cgraph_maybe_hot_edge_p (edge) && growth > 0)
+ if ((!cgraph_maybe_hot_edge_p (edge) || optimize_size) && growth > 0)
{
if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
&edge->inline_failed))
{
struct cgraph_node *callee;
if (!cgraph_check_inline_limits (edge->caller, edge->callee,
- &edge->inline_failed))
+ &edge->inline_failed, true))
{
if (dump_file)
fprintf (dump_file, " Not inlining into %s:%s.\n",
bitmap_clear (updated_nodes);
if (dump_file)
- fprintf (dump_file,
- " Inlined into %s which now has %i insns.\n",
- cgraph_node_name (edge->caller),
- edge->caller->global.insns);
- if (dump_file)
- fprintf (dump_file,
- " Inlined for a net change of %+i insns.\n",
- overall_insns - old_insns);
+ {
+ fprintf (dump_file,
+ " Inlined into %s which now has %i insns,"
+ "net change of %+i insns.\n",
+ cgraph_node_name (edge->caller),
+ edge->caller->global.insns,
+ overall_insns - old_insns);
+ }
+ if (min_insns > overall_insns)
+ {
+ min_insns = overall_insns;
+ max_insns = compute_max_insns (min_insns);
+
+ if (dump_file)
+ fprintf (dump_file, "New minimal insns reached: %i\n", min_insns);
+ }
}
while ((edge = fibheap_extract_min (heap)) != NULL)
{
/* Decide on the inlining. We do so in the topological order to avoid
expenses on updating data structures. */
-static void
+static unsigned int
cgraph_decide_inlining (void)
{
struct cgraph_node *node;
int nnodes;
struct cgraph_node **order =
- xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
+ XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
int old_insns = 0;
int i;
+ int initial_insns = 0;
- timevar_push (TV_INLINE_HEURISTICS);
max_count = 0;
for (node = cgraph_nodes; node; node = node->next)
- {
- struct cgraph_edge *e;
- initial_insns += node->local.self_insns;
- for (e = node->callees; e; e = e->next_callee)
- if (max_count < e->count)
- max_count = e->count;
- }
+ if (node->analyzed && (node->needed || node->reachable))
+ {
+ struct cgraph_edge *e;
+
+ initial_insns += node->local.self_insns;
+ gcc_assert (node->local.self_insns == node->global.insns);
+ for (e = node->callees; e; e = e->next_callee)
+ if (max_count < e->count)
+ max_count = e->count;
+ }
overall_insns = initial_insns;
gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
- max_insns = ((HOST_WIDEST_INT) overall_insns
- * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
-
nnodes = cgraph_postorder (order);
if (dump_file)
/* Handle nodes to be flattened, but don't update overall unit size. */
if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
{
- int old_overall_insns = overall_insns;
- htab_t cycles;
if (dump_file)
fprintf (dump_file,
- "Leafifying %s\n", cgraph_node_name (node));
- cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
- cgraph_find_cycles (node, cycles);
- cgraph_flatten_node (node, cycles);
- htab_delete (cycles);
- overall_insns = old_overall_insns;
- /* We don't need to consider always_inline functions inside the flattened
- function anymore. */
- continue;
+ "Flattening %s\n", cgraph_node_name (node));
+ cgraph_decide_inlining_incrementally (node, INLINE_ALL, 0);
}
if (!node->local.disregard_inline_limits)
cgraph_node_name (e->caller),
e->caller->global.insns);
}
+ /* Inlining self recursive function might introduce new calls to
+ themselves we didn't see in the loop above. Fill in the proper
+ reason why inline failed. */
+ for (e = node->callers; e; e = e->next_caller)
+ if (e->inline_failed)
+ e->inline_failed = N_("recursive inlining");
if (dump_file)
fprintf (dump_file,
" Inlined for a net change of %+i insns.\n",
&& node->local.inlinable && node->callers->inline_failed
&& !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
{
- bool ok = true;
- struct cgraph_node *node1;
-
- /* Verify that we won't duplicate the caller. */
- for (node1 = node->callers->caller;
- node1->callers && !node1->callers->inline_failed
- && ok; node1 = node1->callers->caller)
- if (node1->callers->next_caller || node1->needed)
- ok = false;
- if (ok)
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "\nConsidering %s %i insns.\n",
+ cgraph_node_name (node), node->global.insns);
+ fprintf (dump_file,
+ " Called once from %s %i insns.\n",
+ cgraph_node_name (node->callers->caller),
+ node->callers->caller->global.insns);
+ }
+
+ old_insns = overall_insns;
+
+ if (cgraph_check_inline_limits (node->callers->caller, node,
+ NULL, false))
{
+ cgraph_mark_inline (node->callers);
if (dump_file)
fprintf (dump_file,
- "\nConsidering %s %i insns.\n"
- " Called once from %s %i insns.\n",
- cgraph_node_name (node), node->global.insns,
+ " 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);
-
- old_insns = overall_insns;
-
- if (cgraph_check_inline_limits (node->callers->caller, node,
- NULL))
- {
- cgraph_mark_inline (node->callers);
- if (dump_file)
- fprintf (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 (dump_file)
- fprintf (dump_file,
- " Inline limit reached, not inlined.\n");
- }
+ node->callers->caller->global.insns,
+ overall_insns - old_insns);
+ }
+ else
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ " Inline limit reached, not inlined.\n");
}
}
}
ncalls_inlined, nfunctions_inlined, initial_insns,
overall_insns);
free (order);
- timevar_pop (TV_INLINE_HEURISTICS);
+ return 0;
+}
+
+/* Try to inline edge E from incremental inliner. MODE specifies mode
+ of inliner.
+
+ We are detecting cycles by storing mode of inliner into cgraph_node last
+ time we visited it in the recursion. In general when mode is set, we have
+ recursive inlining, but as an special case, we want to try harder inline
+ ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being
+ flatten, b being always inline. Flattening 'a' will collapse
+ a->b->c before hitting cycle. To accommodate always inline, we however
+ need to inline a->b->c->b.
+
+ So after hitting cycle first time, we switch into ALWAYS_INLINE mode and
+ stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode. */
+static bool
+try_inline (struct cgraph_edge *e, enum inlining_mode mode, int depth)
+{
+ struct cgraph_node *callee = e->callee;
+ enum inlining_mode callee_mode = (size_t) callee->aux;
+ bool always_inline = e->callee->local.disregard_inline_limits;
+
+ /* We've hit cycle? */
+ if (callee_mode)
+ {
+ /* It is first time we see it and we are not in ALWAY_INLINE only
+ mode yet. and the function in question is always_inline. */
+ if (always_inline && mode != INLINE_ALWAYS_INLINE)
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file,
+ "Hit cycle in %s, switching to always inline only.\n",
+ cgraph_node_name (callee));
+ }
+ mode = INLINE_ALWAYS_INLINE;
+ }
+ /* Otherwise it is time to give up. */
+ else
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file,
+ "Not inlining %s into %s to avoid cycle.\n",
+ cgraph_node_name (callee),
+ cgraph_node_name (e->caller));
+ }
+ e->inline_failed = (e->callee->local.disregard_inline_limits
+ ? N_("recursive inlining") : "");
+ return false;
+ }
+ }
+
+ callee->aux = (void *)(size_t) mode;
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file, " Inlining %s into %s.\n",
+ cgraph_node_name (e->callee),
+ cgraph_node_name (e->caller));
+ }
+ if (e->inline_failed)
+ cgraph_mark_inline (e);
+
+ /* In order to fully inline always_inline functions at -O0, we need to
+ recurse here, since the inlined functions might not be processed by
+ incremental inlining at all yet.
+
+ Also flattening needs to be done recursively. */
+
+ if (!flag_unit_at_a_time || mode == INLINE_ALL || always_inline)
+ cgraph_decide_inlining_incrementally (e->callee, mode, depth + 1);
+ callee->aux = (void *)(size_t) callee_mode;
+ return true;
}
/* Decide on the inlining. We do so in the topological order to avoid
- expenses on updating data structures. */
+ expenses on updating data structures.
+ DEPTH is depth of recursion, used only for debug output. */
-bool
-cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
+static bool
+cgraph_decide_inlining_incrementally (struct cgraph_node *node,
+ enum inlining_mode mode,
+ int depth)
{
struct cgraph_edge *e;
bool inlined = false;
const char *failed_reason;
+ enum inlining_mode old_mode;
+
+#ifdef ENABLE_CHECKING
+ verify_cgraph_node (node);
+#endif
+
+ old_mode = (size_t)node->aux;
+
+ if (mode != INLINE_ALWAYS_INLINE
+ && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file, "Flattening %s\n", cgraph_node_name (node));
+ }
+ mode = INLINE_ALL;
+ }
+
+ node->aux = (void *)(size_t) mode;
/* 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->inline_failed
- && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
- /* ??? It is possible that renaming variable removed the function body
- in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
- && DECL_SAVED_TREE (e->callee->decl))
- {
- if (dump_file && early)
- fprintf (dump_file, " Early inlining %s into %s\n",
- cgraph_node_name (e->callee), cgraph_node_name (node));
- cgraph_mark_inline (e);
- inlined = true;
- }
-
- /* Now do the automatic inlining. */
- if (!flag_really_no_inline)
- for (e = node->callees; e; e = e->next_callee)
- if (e->callee->local.inlinable
- && e->inline_failed
- && !e->callee->local.disregard_inline_limits
- && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
- && (!early
- || (cgraph_estimate_size_after_inlining (1, e->caller, node)
- <= e->caller->global.insns))
- && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
- && DECL_SAVED_TREE (e->callee->decl))
+ {
+ if (!e->callee->local.disregard_inline_limits
+ && (mode != INLINE_ALL || !e->callee->local.inlinable))
+ continue;
+ /* When the edge is already inlined, we just need to recurse into
+ it in order to fully flatten the leaves. */
+ if (!e->inline_failed && mode == INLINE_ALL)
+ {
+ inlined |= try_inline (e, mode, depth);
+ continue;
+ }
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file,
+ "Considering to always inline inline candidate %s.\n",
+ cgraph_node_name (e->callee));
+ }
+ if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file, "Not inlining: recursive call.\n");
+ }
+ continue;
+ }
+ if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
+ != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
{
- if (cgraph_default_inline_p (e->callee, &failed_reason))
+ if (dump_file)
{
- if (dump_file && early)
- fprintf (dump_file, " Early inlining %s into %s\n",
- cgraph_node_name (e->callee), cgraph_node_name (node));
- cgraph_mark_inline (e);
- inlined = true;
+ indent_to (dump_file, depth);
+ fprintf (dump_file, "Not inlining: SSA form does not match.\n");
}
- else if (!early)
- e->inline_failed = failed_reason;
+ continue;
}
- if (early && inlined)
- {
- push_cfun (DECL_STRUCT_FUNCTION (node->decl));
- tree_register_cfg_hooks ();
- current_function_decl = node->decl;
- optimize_inline_calls (current_function_decl);
- node->local.self_insns = node->global.insns;
- current_function_decl = NULL;
- pop_cfun ();
+ if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file,
+ "Not inlining: Function body no longer available.\n");
+ }
+ continue;
+ }
+ inlined |= try_inline (e, mode, depth);
}
+
+ /* Now do the automatic inlining. */
+ if (!flag_really_no_inline && mode != INLINE_ALL
+ && mode != INLINE_ALWAYS_INLINE)
+ for (e = node->callees; e; e = e->next_callee)
+ {
+ if (!e->callee->local.inlinable
+ || !e->inline_failed
+ || e->callee->local.disregard_inline_limits)
+ continue;
+ if (dump_file)
+ fprintf (dump_file, "Considering inline candidate %s.\n",
+ cgraph_node_name (e->callee));
+ if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file, "Not inlining: recursive call.\n");
+ }
+ continue;
+ }
+ if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
+ != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file, "Not inlining: SSA form does not match.\n");
+ }
+ continue;
+ }
+ /* When the function body would grow and inlining the function won't
+ eliminate the need for offline copy of the function, don't inline.
+ */
+ if (mode == INLINE_SIZE
+ && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
+ > e->caller->global.insns)
+ && cgraph_estimate_growth (e->callee) > 0)
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file,
+ "Not inlining: code size would grow by %i insns.\n",
+ cgraph_estimate_size_after_inlining (1, e->caller,
+ e->callee)
+ - e->caller->global.insns);
+ }
+ continue;
+ }
+ if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
+ false))
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file, "Not inlining: %s.\n", e->inline_failed);
+ }
+ continue;
+ }
+ if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
+ {
+ if (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file,
+ "Not inlining: Function body no longer available.\n");
+ }
+ continue;
+ }
+ if (cgraph_default_inline_p (e->callee, &failed_reason))
+ inlined |= try_inline (e, mode, depth);
+ else if (!flag_unit_at_a_time)
+ e->inline_failed = failed_reason;
+ }
+ node->aux = (void *)(size_t) old_mode;
return inlined;
}
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- TV_INTEGRATION, /* tv_id */
+ TV_INLINE_HEURISTICS, /* tv_id */
0, /* properties_required */
PROP_cfg, /* properties_provided */
0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */
+ TODO_remove_functions, /* todo_flags_finish */
+ TODO_dump_cgraph | TODO_dump_func
+ | TODO_remove_functions, /* todo_flags_finish */
0 /* letter */
};
+/* Because inlining might remove no-longer reachable nodes, we need to
+ keep the array visible to garbage collector to avoid reading collected
+ out nodes. */
+static int nnodes;
+static GTY ((length ("nnodes"))) struct cgraph_node **order;
+
/* Do inlining of small functions. Doing so early helps profiling and other
passes to be somewhat more effective and avoids some code duplication in
later real inlining pass for testcases with very many function calls. */
-static void
+static unsigned int
cgraph_early_inlining (void)
{
- struct cgraph_node *node;
- int nnodes;
- struct cgraph_node **order =
- xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
- int i;
+ struct cgraph_node *node = cgraph_node (current_function_decl);
+ unsigned int todo = 0;
if (sorrycount || errorcount)
- return;
-#ifdef ENABLE_CHECKING
- for (node = cgraph_nodes; node; node = node->next)
- gcc_assert (!node->aux);
-#endif
-
- nnodes = cgraph_postorder (order);
- for (i = nnodes - 1; i >= 0; i--)
+ return 0;
+ if (cgraph_decide_inlining_incrementally (node,
+ flag_unit_at_a_time || optimize_size
+ ? INLINE_SIZE : INLINE_SPEED, 0))
{
- node = order[i];
- if (node->analyzed && node->local.inlinable
- && (node->needed || node->reachable)
- && node->callers)
- cgraph_decide_inlining_incrementally (node, true);
+ timevar_push (TV_INTEGRATION);
+ todo = optimize_inline_calls (current_function_decl);
+ timevar_pop (TV_INTEGRATION);
}
- cgraph_remove_unreachable_nodes (true, dump_file);
-#ifdef ENABLE_CHECKING
- for (node = cgraph_nodes; node; node = node->next)
- gcc_assert (!node->global.inlined_to);
-#endif
- free (order);
+ return todo;
}
/* When inlining shall be performed. */
return flag_inline_trees && flag_early_inlining;
}
-struct tree_opt_pass pass_early_ipa_inline =
+struct tree_opt_pass pass_early_inline =
{
"einline", /* name */
cgraph_gate_early_inlining, /* gate */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- TV_INTEGRATION, /* tv_id */
+ TV_INLINE_HEURISTICS, /* tv_id */
+ 0, /* properties_required */
+ PROP_cfg, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+/* When inlining shall be performed. */
+static bool
+cgraph_gate_ipa_early_inlining (void)
+{
+ return (flag_inline_trees && flag_early_inlining
+ && (flag_branch_probabilities || flag_test_coverage
+ || profile_arc_flag));
+}
+
+/* IPA pass wrapper for early inlining pass. We need to run early inlining
+ before tree profiling so we have stand alone IPA pass for doing so. */
+struct tree_opt_pass pass_ipa_early_inline =
+{
+ "einline_ipa", /* name */
+ cgraph_gate_ipa_early_inlining, /* gate */
+ NULL, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_INLINE_HEURISTICS, /* tv_id */
+ 0, /* properties_required */
+ PROP_cfg, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_cgraph, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+/* Compute parameters of functions used by inliner. */
+static unsigned int
+compute_inline_parameters (void)
+{
+ struct cgraph_node *node = cgraph_node (current_function_decl);
+
+ gcc_assert (!node->global.inlined_to);
+ node->local.estimated_self_stack_size = estimated_stack_frame_size ();
+ node->global.estimated_stack_size = node->local.estimated_self_stack_size;
+ node->global.stack_frame_offset = 0;
+ node->local.inlinable = tree_inlinable_function_p (current_function_decl);
+ node->local.self_insns = estimate_num_insns (current_function_decl,
+ &eni_inlining_weights);
+ if (node->local.inlinable)
+ node->local.disregard_inline_limits
+ = lang_hooks.tree_inlining.disregard_inline_limits (current_function_decl);
+ if (flag_really_no_inline && !node->local.disregard_inline_limits)
+ node->local.inlinable = 0;
+ /* Inlining characteristics are maintained by the cgraph_mark_inline. */
+ node->global.insns = node->local.self_insns;
+ return 0;
+}
+
+/* When inlining shall be performed. */
+static bool
+gate_inline_passes (void)
+{
+ return flag_inline_trees;
+}
+
+struct tree_opt_pass pass_inline_parameters =
+{
+ NULL, /* name */
+ gate_inline_passes, /* gate */
+ compute_inline_parameters, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_INLINE_HEURISTICS, /* tv_id */
0, /* properties_required */
PROP_cfg, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */
+ 0, /* todo_flags_finish */
0 /* letter */
};
+
+/* Apply inline plan to the function. */
+static unsigned int
+apply_inline (void)
+{
+ unsigned int todo = 0;
+ struct cgraph_edge *e;
+ struct cgraph_node *node = cgraph_node (current_function_decl);
+
+ /* Even when not optimizing, ensure that always_inline functions get inlined.
+ */
+ if (!optimize)
+ cgraph_decide_inlining_incrementally (node, INLINE_SPEED, 0);
+
+ /* We might need the body of this function so that we can expand
+ it inline somewhere else. */
+ if (cgraph_preserve_function_body_p (current_function_decl))
+ save_inline_function_body (node);
+
+ for (e = node->callees; e; e = e->next_callee)
+ if (!e->inline_failed || warn_inline)
+ break;
+ if (e)
+ {
+ timevar_push (TV_INTEGRATION);
+ todo = optimize_inline_calls (current_function_decl);
+ timevar_pop (TV_INTEGRATION);
+ }
+ /* In non-unit-at-a-time we must mark all referenced functions as needed. */
+ if (!flag_unit_at_a_time)
+ {
+ struct cgraph_edge *e;
+ for (e = node->callees; e; e = e->next_callee)
+ if (e->callee->analyzed)
+ cgraph_mark_needed_node (e->callee);
+ }
+ return todo | execute_fixup_cfg ();
+}
+
+struct tree_opt_pass pass_apply_inline =
+{
+ "apply_inline", /* name */
+ NULL, /* gate */
+ apply_inline, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_INLINE_HEURISTICS, /* tv_id */
+ 0, /* properties_required */
+ PROP_cfg, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_verify_flow
+ | TODO_verify_stmts, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+#include "gt-ipa-inline.h"