diff options
author | kan <kan@FreeBSD.org> | 2004-07-28 03:11:36 +0000 |
---|---|---|
committer | kan <kan@FreeBSD.org> | 2004-07-28 03:11:36 +0000 |
commit | 5e00ec74d8ce58f99801200d4d3d0412c7cc1b28 (patch) | |
tree | 052f4bb635f2bea2c5e350bd60c902be100a0d1e /contrib/gcc/cgraphunit.c | |
parent | 87b8398a7d9f9bf0e28bbcd54a4fc27db2125f38 (diff) | |
download | FreeBSD-src-5e00ec74d8ce58f99801200d4d3d0412c7cc1b28.zip FreeBSD-src-5e00ec74d8ce58f99801200d4d3d0412c7cc1b28.tar.gz |
Gcc 3.4.2 20040728.
Diffstat (limited to 'contrib/gcc/cgraphunit.c')
-rw-r--r-- | contrib/gcc/cgraphunit.c | 1613 |
1 files changed, 1613 insertions, 0 deletions
diff --git a/contrib/gcc/cgraphunit.c b/contrib/gcc/cgraphunit.c new file mode 100644 index 0000000..75ad3c8 --- /dev/null +++ b/contrib/gcc/cgraphunit.c @@ -0,0 +1,1613 @@ +/* Callgraph based intraprocedural optimizations. + Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Contributed by Jan Hubicka + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +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. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "tree-inline.h" +#include "langhooks.h" +#include "hashtab.h" +#include "toplev.h" +#include "flags.h" +#include "ggc.h" +#include "debug.h" +#include "target.h" +#include "cgraph.h" +#include "diagnostic.h" +#include "timevar.h" +#include "params.h" +#include "fibheap.h" +#include "c-common.h" +#include "intl.h" +#include "function.h" + +#define INSNS_PER_CALL 10 + +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_mark_local_functions (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; +static int nfunctions_inlined; +static int initial_insns; +static int overall_insns; + +/* Records tree nodes seen in cgraph_create_edges. Simply using + walk_tree_without_duplicates doesn't guarantee each node is visited + once because it gets a new htab upon each recursive call from + record_calls_1. */ +static htab_t visited_nodes; + +/* Determine if function DECL is needed. That is, visible to something + either outside this translation unit, something magic in the system + configury, or (if not doing unit-at-a-time) to something we havn't + seen yet. */ + +static bool +decide_is_function_needed (struct cgraph_node *node, tree decl) +{ + /* If we decided it was needed before, but at the time we didn't have + the body of the function available, then it's still needed. We have + to go back and re-check its dependencies now. */ + if (node->needed) + return true; + + /* Externally visible functions must be output. The exception is + COMDAT functions that must be output only when they are needed. */ + if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)) + return true; + + /* Constructors and destructors are reachable from the runtime by + some mechanism. */ + if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl)) + return true; + + /* If the user told us it is used, then it must be so. */ + if (lookup_attribute ("used", DECL_ATTRIBUTES (decl))) + return true; + + /* ??? If the assembler name is set by hand, it is possible to assemble + the name later after finalizing the function and the fact is noticed + in assemble_name then. This is arguably a bug. */ + if (DECL_ASSEMBLER_NAME_SET_P (decl) + && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))) + return true; + + if (flag_unit_at_a_time) + return false; + + /* If not doing unit at a time, then we'll only defer this function + if its marked for inlining. Otherwise we want to emit it now. */ + + /* "extern inline" functions are never output locally. */ + if (DECL_EXTERNAL (decl)) + return false; + /* 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 eliminated when unused. */ + && !DECL_DECLARED_INLINE_P (decl) + && (!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. */ + +bool +cgraph_assemble_pending_functions (void) +{ + bool output = false; + + if (flag_unit_at_a_time) + return false; + + while (cgraph_nodes_queue) + { + struct cgraph_node *n = cgraph_nodes_queue; + + cgraph_nodes_queue = cgraph_nodes_queue->next_needed; + if (!n->origin && !DECL_EXTERNAL (n->decl)) + { + cgraph_expand_function (n); + output = true; + } + } + + return output; +} + +/* DECL has been parsed. Take it, queue it, compile it at the whim of the + logic in effect. If NESTED is true, then our caller cannot stand to have + the garbage collector run at the moment. We would need to either create + a new GC context, or just not compile right now. */ + +void +cgraph_finalize_function (tree decl, bool nested) +{ + struct cgraph_node *node = cgraph_node (decl); + + if (node->local.finalized) + { + /* As an GCC extension we allow redefinition of the function. The + semantics when both copies of bodies differ is not well defined. + We replace the old body with new body so in unit at a time mode + we always use new body, while in normal mode we may end up with + old body inlined into some functions and new body expanded and + inlined in others. + + ??? It may make more sense to use one body for inlining and other + 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->local, 0, sizeof (node->local)); + memset (&node->global, 0, sizeof (node->global)); + memset (&node->rtl, 0, sizeof (node->rtl)); + node->analyzed = false; + node->local.redefined_extern_inline = true; + while (node->callees) + 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 (node->reachable && !flag_unit_at_a_time) + { + struct cgraph_node *n; + + for (n = cgraph_nodes_queue; n; n = n->next_needed) + if (n == node) + break; + if (!n) + node->reachable = 0; + } + } + + notice_global_symbol (decl); + node->decl = decl; + node->local.finalized = true; + + /* 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_decide_inlining_incrementally (node); + } + + if (decide_is_function_needed (node, decl)) + cgraph_mark_needed_node (node); + + /* If not unit at a time, go ahead and emit everything we've found + to be reachable at this time. */ + if (!nested) + { + if (!cgraph_assemble_pending_functions ()) + ggc_collect (); + } + + /* If we've not yet emitted decl, tell the debug info about it. */ + if (!TREE_ASM_WRITTEN (decl)) + (*debug_hooks->deferred_inline_function) (decl); + + /* We will never really output the function body, clear the SAVED_INSNS array + early then. */ + if (DECL_EXTERNAL (decl)) + DECL_SAVED_INSNS (decl) = NULL; +} + +/* Walk tree and record all calls. Called via walk_tree. */ +static tree +record_call_1 (tree *tp, int *walk_subtrees, void *data) +{ + tree t = *tp; + + switch (TREE_CODE (t)) + { + case VAR_DECL: + /* ??? Really, we should mark this decl as *potentially* referenced + by this function and re-examine whether the decl is actually used + after rtl has been generated. */ + if (TREE_STATIC (t)) + cgraph_varpool_mark_needed_node (cgraph_varpool_node (t)); + break; + + case ADDR_EXPR: + if (flag_unit_at_a_time) + { + /* Record dereferences to the functions. This makes the + functions reachable unconditionally. */ + tree decl = TREE_OPERAND (*tp, 0); + if (TREE_CODE (decl) == FUNCTION_DECL) + cgraph_mark_needed_node (cgraph_node (decl)); + } + break; + + case CALL_EXPR: + { + tree decl = get_callee_fndecl (*tp); + if (decl && TREE_CODE (decl) == FUNCTION_DECL) + { + cgraph_record_call (data, decl); + + /* When we see a function call, we don't want to look at the + function reference in the ADDR_EXPR that is hanging from + the CALL_EXPR we're examining here, because we would + conclude incorrectly that the function's address could be + taken by something that is not a function call. So only + walk the function parameter list, skip the other subtrees. */ + + walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, + visited_nodes); + *walk_subtrees = 0; + } + break; + } + + default: + /* Save some cycles by not walking types and declaration as we + won't find anything useful there anyway. */ + if (DECL_P (*tp) || TYPE_P (*tp)) + { + *walk_subtrees = 0; + break; + } + + if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE) + return (*lang_hooks.callgraph.analyze_expr) (tp, walk_subtrees, data); + break; + } + + return NULL; +} + +/* Create cgraph edges for function calls inside BODY from DECL. */ + +void +cgraph_create_edges (tree decl, tree body) +{ + /* The nodes we're interested in are never shared, so walk + the tree ignoring duplicates. */ + visited_nodes = htab_create (37, htab_hash_pointer, + htab_eq_pointer, NULL); + walk_tree (&body, record_call_1, decl, visited_nodes); + htab_delete (visited_nodes); + visited_nodes = NULL; +} + +/* Analyze the function scheduled to be output. */ +static void +cgraph_analyze_function (struct cgraph_node *node) +{ + tree decl = node->decl; + struct cgraph_edge *e; + + current_function_decl = decl; + + /* First kill forward declaration so reverse inlining works properly. */ + cgraph_create_edges (decl, DECL_SAVED_TREE (decl)); + + node->local.inlinable = tree_inlinable_function_p (decl); + if (!node->local.self_insns) + node->local.self_insns + = (*lang_hooks.tree_inlining.estimate_num_insns) (decl); + if (node->local.inlinable) + node->local.disregard_inline_limits + = (*lang_hooks.tree_inlining.disregard_inline_limits) (decl); + for (e = node->callers; e; e = e->next_caller) + if (e->inline_failed) + { + if (node->local.redefined_extern_inline) + e->inline_failed = N_("redefined extern inline functions are not " + "considered for inlining"); + else if (!node->local.inlinable) + e->inline_failed = N_("function not inlinable"); + else + e->inline_failed = N_("function not considered for inlining"); + } + 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; + if (!DECL_EXTERNAL (decl)) + { + node->global.cloned_times = 1; + node->global.will_be_output = true; + } + + node->analyzed = true; + current_function_decl = NULL; + + /* Possibly warn about unused parameters. */ + if (warn_unused_parameter) + do_warn_unused_parameter (decl); +} + +/* Analyze the whole compilation unit once it is parsed completely. */ + +void +cgraph_finalize_compilation_unit (void) +{ + struct cgraph_node *node; + + if (!flag_unit_at_a_time) + { + cgraph_assemble_pending_functions (); + return; + } + + cgraph_varpool_assemble_pending_decls (); + if (!quiet_flag) + fprintf (stderr, "\nAnalyzing compilation unit\n"); + + timevar_push (TV_CGRAPH); + if (cgraph_dump_file) + { + 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)); + fprintf (cgraph_dump_file, "\n"); + } + + /* Propagate reachability flag and lower representation of all reachable + functions. In the future, lowering will introduce new functions and + new entry points on the way (by template instantiation and virtual + method table generation for instance). */ + while (cgraph_nodes_queue) + { + struct cgraph_edge *edge; + tree decl = cgraph_nodes_queue->decl; + + node = cgraph_nodes_queue; + cgraph_nodes_queue = cgraph_nodes_queue->next_needed; + + /* ??? It is possible to create extern inline function and later using + weak alas attribute to kill it's body. See + gcc.c-torture/compile/20011119-1.c */ + if (!DECL_SAVED_TREE (decl)) + continue; + + if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl)) + abort (); + + cgraph_analyze_function (node); + + for (edge = node->callees; edge; edge = edge->next_callee) + if (!edge->callee->reachable) + cgraph_mark_reachable_node (edge->callee); + + cgraph_varpool_assemble_pending_decls (); + } + + /* Collect entry points to the unit. */ + + if (cgraph_dump_file) + { + 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\nInitial "); + dump_cgraph (cgraph_dump_file); + } + + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "\nReclaiming functions:"); + + for (node = cgraph_nodes; node; node = node->next) + { + tree decl = node->decl; + + if (!node->reachable && DECL_SAVED_TREE (decl)) + { + cgraph_remove_node (node); + if (cgraph_dump_file) + fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); + } + else + node->next_needed = NULL; + } + if (cgraph_dump_file) + { + fprintf (cgraph_dump_file, "\n\nReclaimed "); + dump_cgraph (cgraph_dump_file); + } + ggc_collect (); + timevar_pop (TV_CGRAPH); +} + +/* Figure out what functions we want to assemble. */ + +static void +cgraph_mark_functions_to_output (void) +{ + struct cgraph_node *node; + + for (node = cgraph_nodes; node; node = node->next) + { + tree decl = node->decl; + struct cgraph_edge *e; + + if (node->output) + abort (); + + for (e = node->callers; e; e = e->next_caller) + if (e->inline_failed) + break; + + /* We need to output all local functions that are used and not + always inlined, as well as those that are reachable from + outside the current compilation unit. */ + if (DECL_SAVED_TREE (decl) + && (node->needed + || (e && node->reachable)) + && !TREE_ASM_WRITTEN (decl) && !node->origin + && !DECL_EXTERNAL (decl)) + node->output = 1; + else + DECL_SAVED_INSNS (decl) = NULL; + } +} + +/* Optimize the function before expansion. */ + +static void +cgraph_optimize_function (struct cgraph_node *node) +{ + tree decl = node->decl; + + timevar_push (TV_INTEGRATION); + /* optimize_inline_calls avoids inlining of current_function_decl. */ + current_function_decl = decl; + if (flag_inline_trees) + { + struct cgraph_edge *e; + + for (e = node->callees; e; e = e->next_callee) + if (!e->inline_failed || warn_inline + || (DECL_DECLARED_INLINE_P (e->callee->decl) + && lookup_attribute ("always_inline", + DECL_ATTRIBUTES (e->callee->decl)))) + break; + if (e) + optimize_inline_calls (decl); + } + if (node->nested) + { + for (node = node->nested; node; node = node->next_nested) + cgraph_optimize_function (node); + } + timevar_pop (TV_INTEGRATION); +} + +/* Expand function specified by NODE. */ + +static void +cgraph_expand_function (struct cgraph_node *node) +{ + tree decl = node->decl; + + if (flag_unit_at_a_time) + announce_function (decl); + + cgraph_optimize_function (node); + + /* Generate RTL for the body of DECL. Nested functions are expanded + via lang_expand_decl_stmt. */ + (*lang_hooks.callgraph.expand_function) (decl); + if (DECL_DEFER_OUTPUT (decl)) + abort (); + + current_function_decl = NULL; +} + +/* Fill array order with all nodes with output flag set in the reverse + topological order. */ + +static int +cgraph_postorder (struct cgraph_node **order) +{ + struct cgraph_node *node, *node2; + int stack_size = 0; + int order_pos = 0; + struct cgraph_edge *edge, last; + + struct cgraph_node **stack = + xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); + + /* We have to deal with cycles nicely, so use a depth first traversal + output algorithm. Ignore the fact that some functions won't need + to be output and put them into order as well, so we get dependencies + right through intline functions. */ + for (node = cgraph_nodes; node; node = node->next) + node->aux = NULL; + for (node = cgraph_nodes; node; node = node->next) + if (!node->aux) + { + node2 = node; + if (!node->callers) + node->aux = &last; + else + node->aux = node->callers; + while (node2) + { + while (node2->aux != &last) + { + edge = node2->aux; + if (edge->next_caller) + node2->aux = edge->next_caller; + else + node2->aux = &last; + if (!edge->caller->aux) + { + if (!edge->caller->callers) + edge->caller->aux = &last; + else + edge->caller->aux = edge->caller->callers; + stack[stack_size++] = node2; + node2 = edge->caller; + break; + } + } + if (node2->aux == &last) + { + order[order_pos++] = node2; + if (stack_size) + node2 = stack[--stack_size]; + else + node2 = NULL; + } + } + } + free (stack); + return order_pos; +} + +#define INLINED_TIMES(node) ((size_t)(node)->aux) +#define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times)) + +/* Return list of nodes we decided to inline NODE into, set their output + flag and compute INLINED_TIMES. + + We do simple backtracing to get INLINED_TIMES right. This should not be + expensive as we limit the amount of inlining. Alternatively we may first + discover set of nodes, topologically sort these and propagate + INLINED_TIMES */ + +static int +cgraph_inlined_into (struct cgraph_node *node, struct cgraph_node **array) +{ + int nfound = 0; + struct cgraph_edge **stack; + struct cgraph_edge *e, *e1; + int sp; + int i; + + /* Fast path: since we traverse in mostly topological order, we will likely + find no edges. */ + for (e = node->callers; e; e = e->next_caller) + if (!e->inline_failed) + break; + + if (!e) + return 0; + + /* Allocate stack for back-tracking up callgraph. */ + stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge)); + sp = 0; + + /* Push the first edge on to the stack. */ + stack[sp++] = e; + + while (sp) + { + struct cgraph_node *caller; + + /* Look at the edge on the top of the stack. */ + e = stack[sp - 1]; + caller = e->caller; + + /* Check if the caller destination has been visited yet. */ + if (!caller->output) + { + array[nfound++] = e->caller; + /* Mark that we have visited the destination. */ + caller->output = true; + SET_INLINED_TIMES (caller, 0); + } + SET_INLINED_TIMES (caller, INLINED_TIMES (caller) + 1); + + for (e1 = caller->callers; e1; e1 = e1->next_caller) + if (!e1->inline_failed) + break; + + if (e1) + stack[sp++] = e1; + else + { + while (true) + { + for (e1 = e->next_caller; e1; e1 = e1->next_caller) + if (!e1->inline_failed) + break; + + if (e1) + { + stack[sp - 1] = e1; + break; + } + else + { + sp--; + if (!sp) + break; + e = stack[sp - 1]; + } + } + } + } + + free (stack); + + + if (cgraph_dump_file) + { + fprintf (cgraph_dump_file, " Found inline predecesors of %s:", + cgraph_node_name (node)); + for (i = 0; i < nfound; i++) + { + fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i])); + if (INLINED_TIMES (array[i]) != 1) + fprintf (cgraph_dump_file, " (%i times)", + (int)INLINED_TIMES (array[i])); + } + fprintf (cgraph_dump_file, "\n"); + } + + return nfound; +} + +/* Return list of nodes we decided to inline into NODE, set their output + flag and compute INLINED_TIMES. + + This function is identical to cgraph_inlined_into with callers and callees + nodes swapped. */ + +static int +cgraph_inlined_callees (struct cgraph_node *node, struct cgraph_node **array) +{ + int nfound = 0; + struct cgraph_edge **stack; + struct cgraph_edge *e, *e1; + int sp; + int i; + + /* Fast path: since we traverse in mostly topological order, we will likely + find no edges. */ + for (e = node->callees; e; e = e->next_callee) + if (!e->inline_failed) + break; + + if (!e) + return 0; + + /* Allocate stack for back-tracking up callgraph. */ + stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge)); + sp = 0; + + /* Push the first edge on to the stack. */ + stack[sp++] = e; + + while (sp) + { + struct cgraph_node *callee; + + /* Look at the edge on the top of the stack. */ + e = stack[sp - 1]; + callee = e->callee; + + /* Check if the callee destination has been visited yet. */ + if (!callee->output) + { + array[nfound++] = e->callee; + /* Mark that we have visited the destination. */ + callee->output = true; + SET_INLINED_TIMES (callee, 0); + } + SET_INLINED_TIMES (callee, INLINED_TIMES (callee) + 1); + + for (e1 = callee->callees; e1; e1 = e1->next_callee) + if (!e1->inline_failed) + break; + if (e1) + stack[sp++] = e1; + else + { + while (true) + { + for (e1 = e->next_callee; e1; e1 = e1->next_callee) + if (!e1->inline_failed) + break; + + if (e1) + { + stack[sp - 1] = e1; + break; + } + else + { + sp--; + if (!sp) + break; + e = stack[sp - 1]; + } + } + } + } + + free (stack); + + if (cgraph_dump_file) + { + fprintf (cgraph_dump_file, " Found inline successors of %s:", + cgraph_node_name (node)); + for (i = 0; i < nfound; i++) + { + fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i])); + if (INLINED_TIMES (array[i]) != 1) + fprintf (cgraph_dump_file, " (%i times)", + (int)INLINED_TIMES (array[i])); + } + fprintf (cgraph_dump_file, "\n"); + } + + return nfound; +} + +/* Perform reachability analysis and reclaim all unreachable nodes. + This function also remove unneeded bodies of extern inline functions + and thus needs to be done only after inlining decisions has been made. */ +static bool +cgraph_remove_unreachable_nodes (void) +{ + struct cgraph_node *first = (void *) 1; + struct cgraph_node *node; + bool changed = false; + int insns = 0; + + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "\nReclaiming functions:"); +#ifdef ENABLE_CHECKING + for (node = cgraph_nodes; node; node = node->next) + if (node->aux) + abort (); +#endif + for (node = cgraph_nodes; node; node = node->next) + if (node->needed && (!DECL_EXTERNAL (node->decl) || !node->analyzed)) + { + node->aux = first; + first = node; + } + else if (node->aux) + abort (); + + /* Perform reachability analysis. As a special case do not consider + extern inline functions not inlined as live because we won't output + them at all. */ + while (first != (void *) 1) + { + struct cgraph_edge *e; + node = first; + first = first->aux; + + for (e = node->callees; e; e = e->next_callee) + if (!e->callee->aux + && node->analyzed + && (!e->inline_failed || !e->callee->analyzed + || !DECL_EXTERNAL (e->callee->decl))) + { + e->callee->aux = first; + first = e->callee; + } + } + + /* Remove unreachable nodes. Extern inline functions need special care; + Unreachable extern inline functions shall be removed. + Reachable extern inline functions we never inlined shall get their bodies + elliminated + Reachable extern inline functions we sometimes inlined will be turned into + unanalyzed nodes so they look like for true extern functions to the rest + of code. */ + for (node = cgraph_nodes; node; node = node->next) + { + if (!node->aux) + { + int local_insns; + tree decl = node->decl; + + if (DECL_SAVED_INSNS (decl)) + local_insns = node->local.self_insns; + else + local_insns = 0; + if (cgraph_dump_file) + fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); + if (!node->analyzed || !DECL_EXTERNAL (node->decl)) + cgraph_remove_node (node); + else + { + struct cgraph_edge *e; + + for (e = node->callers; e; e = e->next_caller) + if (e->caller->aux) + break; + if (e || node->needed) + { + DECL_SAVED_TREE (node->decl) = NULL_TREE; + while (node->callees) + cgraph_remove_edge (node, node->callees->callee); + node->analyzed = false; + } + else + cgraph_remove_node (node); + } + if (!DECL_SAVED_TREE (decl)) + insns += local_insns; + changed = true; + } + } + for (node = cgraph_nodes; node; node = node->next) + node->aux = NULL; + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "\nReclaimed %i insns", insns); + return changed; +} + + +/* Estimate size of the function after inlining WHAT into TO. */ + +static int +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; +} + +/* Estimate the growth caused by inlining NODE into all callees. */ + +static int +cgraph_estimate_growth (struct cgraph_node *node) +{ + int growth = 0; + int calls_saved = 0; + int clones_added = 0; + struct cgraph_edge *e; + + for (e = node->callers; e; e = e->next_caller) + if (e->inline_failed) + { + growth += ((cgraph_estimate_size_after_inlining (1, e->caller, node) + - + e->caller->global.insns) *e->caller->global.cloned_times); + calls_saved += e->caller->global.cloned_times; + clones_added += e->caller->global.cloned_times; + } + + /* ??? Wrong for self recursive functions or cases where we decide to not + inline for different reasons, but it is not big deal as in that case + we will keep the body around, but we will also avoid some inlining. */ + if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl)) + growth -= node->global.insns, clones_added--; + + if (!calls_saved) + calls_saved = 1; + + return growth; +} + +/* Update insn sizes after inlining WHAT into TO that is already inlined into + all nodes in INLINED array. */ + +static void +cgraph_mark_inline (struct cgraph_node *to, struct cgraph_node *what, + struct cgraph_node **inlined, int ninlined, + struct cgraph_node **inlined_callees, + int ninlined_callees) +{ + int i; + int times = 0; + int clones = 0; + struct cgraph_edge *e; + bool called = false; + int new_insns; + + what->global.inlined = 1; + for (e = what->callers; e; e = e->next_caller) + { + if (e->caller == to) + { + if (!e->inline_failed) + continue; + e->inline_failed = NULL; + times++; + clones += e->caller->global.cloned_times; + } + else if (e->inline_failed) + called = true; + } + if (!times) + abort (); + ncalls_inlined += times; + + new_insns = cgraph_estimate_size_after_inlining (times, to, what); + if (to->global.will_be_output) + overall_insns += new_insns - to->global.insns; + 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) + abort (); + clones--; + nfunctions_inlined++; + what->global.will_be_output = 0; + overall_insns -= what->global.insns; + } + what->global.cloned_times += clones; + for (i = 0; i < ninlined; i++) + { + new_insns = + cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) * + times, inlined[i], what); + if (inlined[i]->global.will_be_output) + overall_insns += new_insns - inlined[i]->global.insns; + inlined[i]->global.insns = new_insns; + } + for (i = 0; i < ninlined_callees; i++) + { + inlined_callees[i]->global.cloned_times += + INLINED_TIMES (inlined_callees[i]) * clones; + } +} + +/* Return false when inlining WHAT into TO is not good idea as it would cause + too large growth of function bodies. */ + +static bool +cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what, + struct cgraph_node **inlined, int ninlined, + const char **reason) +{ + int i; + int times = 0; + struct cgraph_edge *e; + int newsize; + int limit; + + 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 = to->local.self_insns; + else + limit = what->local.self_insns; + + limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; + + newsize = cgraph_estimate_size_after_inlining (times, to, what); + if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) + && newsize > limit) + { + *reason = N_("--param large-function-growth limit reached"); + return false; + } + for (i = 0; i < ninlined; i++) + { + newsize = + cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) * + times, inlined[i], what); + if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) + && newsize > + inlined[i]->local.self_insns * + (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH)) / 100) + { + *reason = N_("--param large-function-growth limit reached while inlining the caller"); + return false; + } + } + return true; +} + +/* Return true when function N is small enough to be inlined. */ + +static bool +cgraph_default_inline_p (struct cgraph_node *n) +{ + 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; + else + return n->global.insns < MAX_INLINE_INSNS_AUTO; +} + +/* Set inline_failed for all callers of given function to REASON. */ + +static void +cgraph_set_inline_failed (struct cgraph_node *node, const char *reason) +{ + struct cgraph_edge *e; + + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "Inlining failed: %s\n", reason); + for (e = node->callers; e; e = e->next_caller) + if (e->inline_failed) + e->inline_failed = reason; +} + +/* 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. + + INLINED and INLINED_CALEES are just pointers to arrays large enough + to be passed to cgraph_inlined_into and cgraph_inlined_callees. */ + +static void +cgraph_decide_inlining_of_small_functions (struct cgraph_node **inlined, + struct cgraph_node **inlined_callees) +{ + int i; + struct cgraph_node *node; + fibheap_t heap = fibheap_new (); + struct fibnode **heap_node = + xcalloc (cgraph_max_uid, sizeof (struct fibnode *)); + int ninlined, ninlined_callees; + int max_insns = ((HOST_WIDEST_INT) initial_insns + * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); + + /* Put all inline candidates into the heap. */ + + for (node = cgraph_nodes; node; node = node->next) + { + if (!node->local.inlinable || !node->callers + || node->local.disregard_inline_limits) + continue; + + if (!cgraph_default_inline_p (node)) + { + cgraph_set_inline_failed (node, + N_("--param max-inline-insns-single limit reached")); + continue; + } + heap_node[node->uid] = + fibheap_insert (heap, cgraph_estimate_growth (node), node); + } + + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n"); + while (overall_insns <= max_insns && (node = fibheap_extract_min (heap))) + { + struct cgraph_edge *e; + int old_insns = overall_insns; + + heap_node[node->uid] = NULL; + if (cgraph_dump_file) + 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)) + { + cgraph_set_inline_failed (node, + N_("--param max-inline-insns-single limit reached after inlining into the callee")); + continue; + } + ninlined_callees = cgraph_inlined_callees (node, inlined_callees); + for (e = node->callers; e; e = e->next_caller) + if (e->inline_failed) + { + /* Marking recursive function inlinine has sane semantic and + thus we should not warn on it. */ + if (e->caller == node) + { + e->inline_failed = ""; + continue; + } + ninlined = cgraph_inlined_into (e->caller, inlined); + if (e->callee->output) + e->inline_failed = ""; + if (e->callee->output + || !cgraph_check_inline_limits (e->caller, node, inlined, + ninlined, &e->inline_failed)) + { + for (i = 0; i < ninlined; i++) + inlined[i]->output = 0, inlined[i]->aux = 0; + if (cgraph_dump_file) + fprintf (cgraph_dump_file, " Not inlining into %s.\n", + cgraph_node_name (e->caller)); + continue; + } + cgraph_mark_inline (e->caller, node, inlined, ninlined, + inlined_callees, ninlined_callees); + if (heap_node[e->caller->uid]) + fibheap_replace_key (heap, heap_node[e->caller->uid], + cgraph_estimate_growth (e->caller)); + + /* Size of the functions we updated into has changed, so update + the keys. */ + for (i = 0; i < ninlined; i++) + { + inlined[i]->output = 0, inlined[i]->aux = 0; + if (heap_node[inlined[i]->uid]) + 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 the function we just inlined + are now called more times; update keys. */ + + 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)); + + for (i = 0; i < ninlined_callees; i++) + { + struct cgraph_edge *e; + + for (e = inlined_callees[i]->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)); + + inlined_callees[i]->output = 0; + inlined_callees[i]->aux = 0; + } + if (cgraph_dump_file) + fprintf (cgraph_dump_file, + " Inlined %i times for a net change of %+i insns.\n", + node->global.cloned_times, overall_insns - old_insns); + } + 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); +} + +/* Decide on the inlining. We do so in the topological order to avoid + expenses on updating datastructures. */ + +static void +cgraph_decide_inlining (void) +{ + struct cgraph_node *node; + int nnodes; + struct cgraph_node **order = + xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); + struct cgraph_node **inlined = + xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); + struct cgraph_node **inlined_callees = + 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) + initial_insns += node->local.self_insns; + overall_insns = initial_insns; + + 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, "\nInlining always_inline functions:\n"); +#ifdef ENABLE_CHECKING + for (node = cgraph_nodes; node; node = node->next) + if (node->aux || node->output) + abort (); +#endif + + /* In the first pass mark all always_inline edges. Do this with a priority + so none of our later choices will make this impossible. */ + for (i = nnodes - 1; i >= 0; i--) + { + struct cgraph_edge *e; + + node = order[i]; + + for (e = node->callees; e; e = e->next_callee) + if (e->callee->local.disregard_inline_limits) + break; + if (!e) + continue; + if (cgraph_dump_file) + fprintf (cgraph_dump_file, + "\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_failed || !e->callee->local.inlinable + || !e->callee->local.disregard_inline_limits) + continue; + if (e->callee->output || e->callee == node) + { + e->inline_failed = N_("recursive inlining"); + continue; + } + 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, inlined_callees[y]->aux = 0; + if (cgraph_dump_file) + 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, inlined[y]->aux = 0; + } +#ifdef ENABLE_CHECKING + for (node = cgraph_nodes; node; node = node->next) + if (node->aux || node->output) + abort (); +#endif + + if (!flag_really_no_inline) + { + cgraph_decide_inlining_of_small_functions (inlined, inlined_callees); +#ifdef ENABLE_CHECKING + for (node = cgraph_nodes; node; node = node->next) + if (node->aux || node->output) + abort (); +#endif + + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n"); + + /* And finally decide what functions are called once. */ + + for (i = nnodes - 1; i >= 0; i--) + { + node = order[i]; + + if (node->callers && !node->callers->next_caller && !node->needed + && 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) + { + const char *dummy_reason; + if (cgraph_dump_file) + fprintf (cgraph_dump_file, + "\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; + + /* Inlining functions once would never cause inlining warnings. */ + if (cgraph_check_inline_limits + (node->callers->caller, node, inlined, ninlined, + &dummy_reason)) + { + ninlined_callees = + cgraph_inlined_callees (node, inlined_callees); + cgraph_mark_inline (node->callers->caller, node, inlined, + ninlined, inlined_callees, + ninlined_callees); + for (y = 0; y < ninlined_callees; y++) + inlined_callees[y]->output = 0, inlined_callees[y]->aux = 0; + if (cgraph_dump_file) + 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, inlined[y]->aux = 0; + } + } + } + } + cgraph_remove_unreachable_nodes (); + + if (cgraph_dump_file) + fprintf (cgraph_dump_file, + "\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); + 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->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 (e->callee->output || e->callee == node) + { + e->inline_failed = N_("recursive inlining"); + continue; + } + 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, inlined_callees[y]->aux = 0; + } + + if (!flag_really_no_inline) + { + /* Now do the automatic inlining. */ + for (e = node->callees; e; e = e->next_callee) + if (e->callee->local.inlinable && e->inline_failed + && cgraph_default_inline_p (e->callee) + && cgraph_check_inline_limits (node, e->callee, inlined, + ninlined, &e->inline_failed) + && DECL_SAVED_TREE (e->callee->decl)) + { + /* Marking recursive function inlinine has sane semantic and thus + we should not warn on it. */ + if (e->callee->output || e->callee == node) + { + e->inline_failed = ""; + continue; + } + 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, inlined_callees[y]->aux = 0; + } + } + + /* Clear the flags set by cgraph_inlined_into. */ + for (y = 0; y < ninlined; y++) + inlined[y]->output = 0, inlined[y]->aux = 0; + + free (inlined); + free (inlined_callees); +} + + +/* Return true when CALLER_DECL should be inlined into CALLEE_DECL. + When returned false and reason is non-NULL, set it to the reason + why the call was not inlined. */ + +bool +cgraph_inline_p (tree caller_decl, tree callee_decl, const char **reason) +{ + struct cgraph_node *caller = cgraph_node (caller_decl); + struct cgraph_node *callee = cgraph_node (callee_decl); + struct cgraph_edge *e; + + for (e = caller->callees; e; e = e->next_callee) + if (e->callee == callee) + { + if (e->inline_failed && reason) + *reason = e->inline_failed; + return !e->inline_failed; + } + /* We do not record builtins in the callgraph. Perhaps it would make more + sense to do so and then prune out those not overwritten by explicit + function body. */ + if (reason) + *reason = "originally indirect function calls never inlined"; + return false; +} +/* Expand all functions that must be output. + + Attempt to topologically sort the nodes so function is output when + all called functions are already assembled to allow data to be + propagated across the callgraph. Use a stack to get smaller distance + between a function and it's callees (later we may choose to use a more + sophisticated algorithm for function reordering; we will likely want + to use subsections to make the output functions appear in top-down + order). */ + +static void +cgraph_expand_all_functions (void) +{ + struct cgraph_node *node; + struct cgraph_node **order = + xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); + int order_pos = 0; + int i; + + cgraph_mark_functions_to_output (); + + order_pos = cgraph_postorder (order); + + for (i = order_pos - 1; i >= 0; i--) + { + node = order[i]; + if (node->output) + { + if (!node->reachable) + abort (); + node->output = 0; + cgraph_expand_function (node); + } + } + free (order); +} + +/* Mark all local functions. + + A local function is one whose calls can occur only in the + current compilation unit and all it's calls are explicit, + so we can change its calling convention. + We simply mark all static functions whose address is not taken + as local. */ + +static void +cgraph_mark_local_functions (void) +{ + struct cgraph_node *node; + + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "\nMarking local functions:"); + + /* Figure out functions we want to assemble. */ + for (node = cgraph_nodes; node; node = node->next) + { + node->local.local = (!node->needed + && DECL_SAVED_TREE (node->decl) + && !TREE_PUBLIC (node->decl)); + if (cgraph_dump_file && node->local.local) + fprintf (cgraph_dump_file, " %s", cgraph_node_name (node)); + } + if (cgraph_dump_file) + fprintf (cgraph_dump_file, "\n\n"); +} + +/* Perform simple optimizations based on callgraph. */ + +void +cgraph_optimize (void) +{ + if (!flag_unit_at_a_time) + return; + 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, "Marked "); + dump_cgraph (cgraph_dump_file); + } + + cgraph_decide_inlining (); + cgraph_global_info_ready = true; + if (cgraph_dump_file) + { + fprintf (cgraph_dump_file, "Optimized "); + dump_cgraph (cgraph_dump_file); + } + timevar_pop (TV_CGRAPHOPT); + + /* Output everything. */ + if (!quiet_flag) + fprintf (stderr, "Assembling functions:\n"); + cgraph_expand_all_functions (); + if (cgraph_dump_file) + { + fprintf (cgraph_dump_file, "\nFinal "); + dump_cgraph (cgraph_dump_file); + } +} |