You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* Inlining decision heuristics
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 "fibheap.h"
#include "intl.h"
#include "tree-pass.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 gcov_type max_count;
/* Estimate size of the function after inlining WHAT into TO. */
cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
struct cgraph_node *what)
{
- tree fndecl = what->decl;
- tree arg;
+ int size;
+ tree fndecl = what->decl, arg;
int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
+
for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
call_insns += estimate_move_cost (TREE_TYPE (arg));
- return (what->global.insns - call_insns) * times + to->global.insns;
+ size = (what->global.insns - call_insns) * times + to->global.insns;
+ gcc_assert (size >= 0);
+ return size;
}
/* E is expected to be an edge being inlined. Clone destination node of
clones or re-using node originally representing out-of-line function call.
*/
void
-cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
+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)
+ HOST_WIDE_INT peak;
+ if (duplicate)
{
- 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)
- {
- n = cgraph_clone_node (e->callee, e->count, e->loop_nest);
- 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)
if (!e->inline_failed)
- cgraph_clone_inlined_nodes (e, duplicate);
+ cgraph_clone_inlined_nodes (e, duplicate, update_original);
}
-/* Mark edge E as inlined and update callgraph accordingly. */
+/* Mark edge E as inlined and update callgraph accordingly.
+ UPDATE_ORIGINAL specify whether profile of original function should be
+ updated. */
void
-cgraph_mark_inline_edge (struct cgraph_edge *e)
+cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original)
{
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;
DECL_POSSIBLY_INLINED (e->callee->decl) = true;
e->callee->global.inlined = true;
- cgraph_clone_inlined_nodes (e, true);
+ cgraph_clone_inlined_nodes (e, true, update_original);
what = e->callee;
next = e->next_caller;
if (e->caller == to && e->inline_failed)
{
- cgraph_mark_inline_edge (e);
+ cgraph_mark_inline_edge (e, true);
if (e == edge)
edge = next;
times++;
{
int growth = 0;
struct cgraph_edge *e;
+ if (node->global.estimated_growth != INT_MIN)
+ return node->global.estimated_growth;
for (e = node->callers; e; e = e->next_caller)
if (e->inline_failed)
if (!node->needed && !DECL_EXTERNAL (node->decl))
growth -= node->global.insns;
+ node->global.estimated_growth = growth;
return growth;
}
/* 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;
}
/* Return true when function N is small enough to be inlined. */
bool
-cgraph_default_inline_p (struct cgraph_node *n)
+cgraph_default_inline_p (struct cgraph_node *n, const char **reason)
{
- if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
- return false;
- if (DECL_DECLARED_INLINE_P (n->decl))
- return n->global.insns < MAX_INLINE_INSNS_SINGLE;
+ 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_STRUCT_FUNCTION (decl)->cfg)
+ {
+ if (reason)
+ *reason = N_("function body not available");
+ return false;
+ }
+
+ if (DECL_DECLARED_INLINE_P (decl))
+ {
+ if (n->global.insns >= MAX_INLINE_INSNS_SINGLE)
+ {
+ if (reason)
+ *reason = N_("--param max-inline-insns-single limit reached");
+ return false;
+ }
+ }
else
- return n->global.insns < MAX_INLINE_INSNS_AUTO;
+ {
+ if (n->global.insns >= MAX_INLINE_INSNS_AUTO)
+ {
+ if (reason)
+ *reason = N_("--param max-inline-insns-auto limit reached");
+ return false;
+ }
+ }
+
+ return true;
}
/* Return true when inlining WHAT would create recursive inlining.
return recursive;
}
-/* Recompute heap nodes for each of callees. */
+/* Return true if the call can be hot. */
+static bool
+cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
+{
+ if (profile_info && flag_branch_probabilities
+ && (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;
+}
+
+/* A cost model driving the inlining heuristics in a way so the edges with
+ 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. */
+
+static int
+cgraph_edge_badness (struct cgraph_edge *edge)
+{
+ 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;
+
+ /* 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;
+}
+
+/* Recompute heap nodes for each of caller edge. */
+
static void
-update_callee_keys (fibheap_t heap, struct fibnode **heap_node,
- struct cgraph_node *node)
+update_caller_keys (fibheap_t heap, struct cgraph_node *node,
+ bitmap updated_nodes)
+{
+ struct cgraph_edge *edge;
+ const char *failed_reason;
+
+ if (!node->local.inlinable || node->local.disregard_inline_limits
+ || node->global.inlined_to)
+ return;
+ if (bitmap_bit_p (updated_nodes, node->uid))
+ return;
+ 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)
+ {
+ int badness = cgraph_edge_badness (edge);
+ if (edge->aux)
+ {
+ fibnode_t n = edge->aux;
+ gcc_assert (n->data == edge);
+ if (n->key == badness)
+ continue;
+
+ /* fibheap_replace_key only increase the keys. */
+ if (fibheap_replace_key (heap, n, badness))
+ continue;
+ fibheap_delete_node (heap, edge->aux);
+ }
+ edge->aux = fibheap_insert (heap, badness, edge);
+ }
+}
+
+/* Recompute heap nodes for each of caller edges of each of callees. */
+
+static void
+update_callee_keys (fibheap_t heap, struct cgraph_node *node,
+ bitmap updated_nodes)
{
struct cgraph_edge *e;
+ node->global.estimated_growth = INT_MIN;
for (e = node->callees; e; e = e->next_callee)
- if (e->inline_failed && heap_node[e->callee->uid])
- fibheap_replace_key (heap, heap_node[e->callee->uid],
- cgraph_estimate_growth (e->callee));
+ if (e->inline_failed)
+ update_caller_keys (heap, e->callee, updated_nodes);
else if (!e->inline_failed)
- update_callee_keys (heap, heap_node, e->callee);
+ update_callee_keys (heap, e->callee, updated_nodes);
}
-/* Enqueue all recursive calls from NODE into queue linked via aux pointers
- in between FIRST and LAST. WHERE is used for bookkeeping while looking
- int calls inlined within NODE. */
+/* Enqueue all recursive calls from NODE into priority queue depending on
+ how likely we want to recursively inline the call. */
+
static void
lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
- struct cgraph_edge **first, struct cgraph_edge **last)
+ fibheap_t heap)
{
+ static int priority;
struct cgraph_edge *e;
for (e = where->callees; e; e = e->next_callee)
if (e->callee == node)
{
- if (!*first)
- *first = e;
- else
- (*last)->aux = e;
- *last = e;
+ /* When profile feedback is available, prioritize by expected number
+ of calls. Without profile feedback we maintain simple queue
+ to order candidates via recursive depths. */
+ fibheap_insert (heap,
+ !max_count ? priority++
+ : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
+ e);
}
for (e = where->callees; e; e = e->next_callee)
if (!e->inline_failed)
- lookup_recursive_calls (node, e->callee, first, last);
+ lookup_recursive_calls (node, e->callee, heap);
}
/* Decide on recursive inlining: in the case function has recursive calls,
inline until body size reaches given argument. */
-static void
+
+static bool
cgraph_decide_recursive_inlining (struct cgraph_node *node)
{
int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
- struct cgraph_edge *first_call = NULL, *last_call = NULL;
- struct cgraph_edge *last_in_current_depth;
+ 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);
/* 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;
- lookup_recursive_calls (node, node, &first_call, &last_call);
- if (!first_call)
- return;
+ return false;
+ heap = fibheap_new ();
+ lookup_recursive_calls (node, node, heap);
+ if (fibheap_empty (heap))
+ {
+ fibheap_delete (heap);
+ return false;
+ }
if (dump_file)
fprintf (dump_file,
- "\nPerforming recursive inlining on %s\n",
+ " Performing recursive inlining on %s\n",
cgraph_node_name (node));
/* We need original clone to copy around. */
- master_clone = cgraph_clone_node (node, 0, 1);
+ 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)
- cgraph_clone_inlined_nodes (e, true);
+ cgraph_clone_inlined_nodes (e, true, false);
/* Do the inlining and update list of recursive call during process. */
- last_in_current_depth = last_call;
- while (first_call
- && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
+ while (!fibheap_empty (heap)
+ && (cgraph_estimate_size_after_inlining (1, node, master_clone)
+ <= limit))
{
- struct cgraph_edge *curr = first_call;
+ struct cgraph_edge *curr = fibheap_extract_min (heap);
+ struct cgraph_node *cnode;
+
+ depth = 1;
+ for (cnode = curr->caller;
+ cnode->global.inlined_to; cnode = cnode->callers->caller)
+ if (node->decl == curr->callee->decl)
+ depth++;
+ if (depth > max_depth)
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ " maximal depth reached\n");
+ continue;
+ }
- first_call = first_call->aux;
- curr->aux = NULL;
+ if (max_count)
+ {
+ if (!cgraph_maybe_hot_edge_p (curr))
+ {
+ if (dump_file)
+ fprintf (dump_file, " Not inlining cold call\n");
+ continue;
+ }
+ if (curr->count * 100 / node->count < probability)
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ " Probability of edge is too small\n");
+ continue;
+ }
+ }
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ " Inlining call of depth %i", depth);
+ if (node->count)
+ {
+ fprintf (dump_file, " called approx. %.2f times per call",
+ (double)curr->count / node->count);
+ }
+ fprintf (dump_file, "\n");
+ }
cgraph_redirect_edge_callee (curr, master_clone);
- cgraph_mark_inline_edge (curr);
- lookup_recursive_calls (node, curr->callee, &first_call, &last_call);
-
- if (last_in_current_depth
- && ++depth >= max_depth)
- break;
+ cgraph_mark_inline_edge (curr, false);
+ lookup_recursive_calls (node, curr->callee, heap);
n++;
}
+ if (!fibheap_empty (heap) && dump_file)
+ fprintf (dump_file, " Recursive inlining growth limit met.\n");
- /* Cleanup queue pointers. */
- while (first_call)
- {
- struct cgraph_edge *next = first_call->aux;
- first_call->aux = NULL;
- first_call = next;
- }
+ fibheap_delete (heap);
if (dump_file)
fprintf (dump_file,
"\n Inlined %i times, body grown from %i to %i insns\n", n,
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
+ inline clones and compensate the counts accordingly. This probably
+ doesn't matter much in practice. */
+ return n > 0;
}
/* Set inline_failed for all callers of given function to REASON. */
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.
cgraph_decide_inlining_of_small_functions (void)
{
struct cgraph_node *node;
+ struct cgraph_edge *edge;
+ const char *failed_reason;
fibheap_t heap = fibheap_new ();
- struct fibnode **heap_node =
- xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
- int max_insns = ((HOST_WIDEST_INT) initial_insns
- * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
+ bitmap updated_nodes = BITMAP_ALLOC (NULL);
+ int min_insns, max_insns;
+
+ if (dump_file)
+ fprintf (dump_file, "\nDeciding on smaller functions:\n");
/* Put all inline candidates into the heap. */
if (!node->local.inlinable || !node->callers
|| node->local.disregard_inline_limits)
continue;
+ if (dump_file)
+ fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
- if (!cgraph_default_inline_p (node))
+ node->global.estimated_growth = INT_MIN;
+ if (!cgraph_default_inline_p (node, &failed_reason))
{
- cgraph_set_inline_failed (node,
- N_("--param max-inline-insns-single limit reached"));
+ cgraph_set_inline_failed (node, failed_reason);
continue;
}
- heap_node[node->uid] =
- fibheap_insert (heap, cgraph_estimate_growth (node), node);
+
+ for (edge = node->callers; edge; edge = edge->next_caller)
+ if (edge->inline_failed)
+ {
+ gcc_assert (!edge->aux);
+ edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
+ }
}
- if (dump_file)
- fprintf (dump_file, "\nDeciding on smaller functions:\n");
- while (overall_insns <= max_insns && (node = fibheap_extract_min (heap)))
+ max_insns = compute_max_insns (overall_insns);
+ min_insns = overall_insns;
+
+ while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
{
- struct cgraph_edge *e, *next;
int old_insns = overall_insns;
+ struct cgraph_node *where;
+ int growth =
+ cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
+
+ growth -= edge->caller->global.insns;
- heap_node[node->uid] = NULL;
if (dump_file)
- fprintf (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))
{
- cgraph_set_inline_failed (node,
- N_("--param max-inline-insns-single limit reached after inlining into the callee"));
- continue;
+ fprintf (dump_file,
+ "\nConsidering %s with %i insns\n",
+ cgraph_node_name (edge->callee),
+ 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),
+ edge->frequency / (double)CGRAPH_FREQ_BASE);
+ if (edge->count)
+ fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
}
- for (e = node->callers; e; e = next)
- {
- next = e->next_caller;
- if (e->inline_failed)
- {
- struct cgraph_node *where;
-
- if (cgraph_recursive_inlining_p (e->caller, e->callee,
- &e->inline_failed)
- || !cgraph_check_inline_limits (e->caller, e->callee,
- &e->inline_failed))
- {
- if (dump_file)
- fprintf (dump_file, " Not inlining into %s:%s.\n",
- cgraph_node_name (e->caller), e->inline_failed);
- continue;
- }
- next = cgraph_mark_inline (e);
- where = e->caller;
- if (where->global.inlined_to)
- where = where->global.inlined_to;
+ gcc_assert (edge->aux);
+ edge->aux = NULL;
+ if (!edge->inline_failed)
+ continue;
- if (heap_node[where->uid])
- fibheap_replace_key (heap, heap_node[where->uid],
- cgraph_estimate_growth (where));
+ /* When not having profile info ready we don't weight by any way the
+ position of call in procedure itself. This means if call of
+ function A from function B seems profitable to inline, the recursive
+ call of function A in inline copy of A in B will look profitable too
+ and we end up inlining until reaching maximal function growth. This
+ is not good idea so prohibit the recursive inlining.
+ ??? When the frequencies are taken into account we might not need this
+ restriction. */
+ if (!max_count)
+ {
+ where = edge->caller;
+ while (where->global.inlined_to)
+ {
+ if (where->decl == edge->callee->decl)
+ break;
+ where = where->callers->caller;
+ }
+ if (where->global.inlined_to)
+ {
+ edge->inline_failed
+ = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
if (dump_file)
- fprintf (dump_file,
- " Inlined into %s which now has %i insns.\n",
- cgraph_node_name (e->caller),
- e->caller->global.insns);
+ fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
+ continue;
}
}
- cgraph_decide_recursive_inlining (node);
-
- /* Similarly all functions called by the function we just inlined
- are now called more times; update keys. */
- update_callee_keys (heap, heap_node, node);
+ if ((!cgraph_maybe_hot_edge_p (edge) || optimize_size) && growth > 0)
+ {
+ if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
+ &edge->inline_failed))
+ {
+ edge->inline_failed =
+ N_("call is unlikely");
+ if (dump_file)
+ fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
+ }
+ continue;
+ }
+ if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
+ {
+ if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
+ &edge->inline_failed))
+ {
+ if (dump_file)
+ fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
+ }
+ continue;
+ }
+ if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
+ &edge->inline_failed))
+ {
+ where = edge->caller;
+ if (where->global.inlined_to)
+ where = where->global.inlined_to;
+ if (!cgraph_decide_recursive_inlining (where))
+ continue;
+ update_callee_keys (heap, where, updated_nodes);
+ }
+ else
+ {
+ struct cgraph_node *callee;
+ if (!cgraph_check_inline_limits (edge->caller, edge->callee,
+ &edge->inline_failed, true))
+ {
+ if (dump_file)
+ fprintf (dump_file, " Not inlining into %s:%s.\n",
+ cgraph_node_name (edge->caller), edge->inline_failed);
+ continue;
+ }
+ callee = edge->callee;
+ cgraph_mark_inline_edge (edge, true);
+ update_callee_keys (heap, callee, updated_nodes);
+ }
+ where = edge->caller;
+ if (where->global.inlined_to)
+ where = where->global.inlined_to;
+
+ /* Our profitability metric can depend on local properties
+ such as number of inlinable calls and size of the function body.
+ After inlining these properties might change for the function we
+ inlined into (since it's body size changed) and for the functions
+ called by function we inlined (since number of it inlinable callers
+ might change). */
+ update_caller_keys (heap, where, updated_nodes);
+ bitmap_clear (updated_nodes);
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)
+ {
+ gcc_assert (edge->aux);
+ edge->aux = NULL;
+ if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
+ && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
+ &edge->inline_failed))
+ edge->inline_failed = N_("--param inline-unit-growth limit reached");
}
- while ((node = fibheap_extract_min (heap)) != NULL)
- if (!node->local.disregard_inline_limits)
- cgraph_set_inline_failed (node, N_("--param inline-unit-growth limit reached"));
fibheap_delete (heap);
- free (heap_node);
+ BITMAP_FREE (updated_nodes);
}
/* 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;
+ max_count = 0;
for (node = cgraph_nodes; node; node = node->next)
- initial_insns += node->local.self_insns;
+ 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));
nnodes = cgraph_postorder (order);
node = order[i];
+ /* Handle nodes to be flattened, but don't update overall unit size. */
+ if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ "Flattening %s\n", cgraph_node_name (node));
+ cgraph_decide_inlining_incrementally (node, INLINE_ALL, 0);
+ }
+
if (!node->local.disregard_inline_limits)
continue;
if (dump_file)
if (cgraph_recursive_inlining_p (e->caller, e->callee,
&e->inline_failed))
continue;
- cgraph_mark_inline_edge (e);
+ cgraph_mark_inline_edge (e, true);
if (dump_file)
fprintf (dump_file,
" Inlined into %s which now has %i insns.\n",
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",
}
if (!flag_really_no_inline)
- {
- cgraph_decide_inlining_of_small_functions ();
+ cgraph_decide_inlining_of_small_functions ();
+ if (!flag_really_no_inline
+ && flag_inline_functions_called_once)
+ {
if (dump_file)
fprintf (dump_file, "\nDeciding on functions called once:\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");
}
}
}
}
- /* We will never output extern functions we didn't inline.
- ??? Perhaps we can prevent accounting of growth of external
- inline functions. */
- cgraph_remove_unreachable_nodes (false, dump_file);
-
if (dump_file)
fprintf (dump_file,
"\nInlined %i calls, eliminated %i functions, "
ncalls_inlined, nfunctions_inlined, initial_insns,
overall_insns);
free (order);
+ 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. */
-void
-cgraph_decide_inlining_incrementally (struct cgraph_node *node)
+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))
- cgraph_mark_inline (e);
+ {
+ 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 (dump_file)
+ {
+ indent_to (dump_file, depth);
+ fprintf (dump_file, "Not inlining: SSA form does not match.\n");
+ }
+ 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;
+ }
+ inlined |= try_inline (e, mode, depth);
+ }
/* Now do the automatic inlining. */
- if (!flag_really_no_inline)
+ 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
- && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
- && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
- && DECL_SAVED_TREE (e->callee->decl))
- {
- if (cgraph_default_inline_p (e->callee))
- cgraph_mark_inline (e);
- else
- e->inline_failed
- = N_("--param max-inline-insns-single limit reached");
- }
+ {
+ 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;
}
/* When inlining shall be performed. */
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 */
+ 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 unsigned int
+cgraph_early_inlining (void)
+{
+ struct cgraph_node *node = cgraph_node (current_function_decl);
+ unsigned int todo = 0;
+
+ if (sorrycount || errorcount)
+ return 0;
+ if (cgraph_decide_inlining_incrementally (node,
+ flag_unit_at_a_time || optimize_size
+ ? INLINE_SIZE : INLINE_SPEED, 0))
+ {
+ timevar_push (TV_INTEGRATION);
+ todo = optimize_inline_calls (current_function_decl);
+ timevar_pop (TV_INTEGRATION);
+ }
+ return todo;
+}
+
+/* When inlining shall be performed. */
+static bool
+cgraph_gate_early_inlining (void)
+{
+ return flag_inline_trees && flag_early_inlining;
+}
+
+struct tree_opt_pass pass_early_inline =
+{
+ "einline", /* name */
+ cgraph_gate_early_inlining, /* gate */
+ cgraph_early_inlining, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_INLINE_HEURISTICS, /* tv_id */
0, /* properties_required */
- PROP_trees, /* properties_provided */
+ PROP_cfg, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */
+ 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 */
+ 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"