#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 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 *);
static int ncalls_inlined;
static int nfunctions_inlined;
static int initial_insns;
static int overall_insns;
static htab_t visited_nodes;
static bool
decide_is_function_needed (struct cgraph_node *node, tree decl)
{
struct cgraph_node *origin;
if (node->needed)
return true;
if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
return true;
if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
return true;
if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
return true;
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 (DECL_EXTERNAL (decl))
return false;
for (origin = node->origin; origin; origin = origin->origin)
if (DECL_EXTERNAL (origin->decl))
return false;
if (DECL_COMDAT (decl))
return false;
if (!DECL_INLINE (decl)
|| (!node->local.disregard_inline_limits
&& !DECL_DECLARED_INLINE_P (decl)
&& (!node->local.inlinable || !cgraph_default_inline_p (node))))
return true;
return false;
}
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;
n->next_needed = NULL;
if (!n->global.inlined_to && !DECL_EXTERNAL (n->decl))
{
cgraph_expand_function (n);
output = true;
}
}
return output;
}
void
cgraph_finalize_function (tree decl, bool nested)
{
struct cgraph_node *node = cgraph_node (decl);
if (node->local.finalized)
{
if (node->output)
abort ();
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->callees);
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 (!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 (!nested)
{
if (!cgraph_assemble_pending_functions ())
ggc_collect ();
}
if (!TREE_ASM_WRITTEN (decl))
(*debug_hooks->deferred_inline_function) (decl);
if (warn_unused_parameter)
do_warn_unused_parameter (decl);
}
static tree
record_call_1 (tree *tp, int *walk_subtrees, void *data)
{
tree t = *tp;
switch (TREE_CODE (t))
{
case VAR_DECL:
if (TREE_STATIC (t))
cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
break;
case ADDR_EXPR:
if (flag_unit_at_a_time)
{
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_create_edge (data, cgraph_node (decl), *tp);
walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
visited_nodes);
*walk_subtrees = 0;
}
break;
}
default:
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;
}
void
cgraph_create_edges (struct cgraph_node *node, tree body)
{
visited_nodes = htab_create (37, htab_hash_pointer,
htab_eq_pointer, NULL);
walk_tree (&body, record_call_1, node, visited_nodes);
htab_delete (visited_nodes);
visited_nodes = NULL;
}
static bool error_found;
static tree
verify_cgraph_node_1 (tree *tp, int *walk_subtrees, void *data)
{
tree t = *tp;
tree decl;
if (TREE_CODE (t) == CALL_EXPR && (decl = get_callee_fndecl (t)))
{
struct cgraph_edge *e = cgraph_edge (data, t);
if (e)
{
if (e->aux)
{
error ("Shared call_expr:");
debug_tree (t);
error_found = true;
}
if (e->callee->decl != cgraph_node (decl)->decl)
{
error ("Edge points to wrong declaration:");
debug_tree (e->callee->decl);
fprintf (stderr," Instead of:");
debug_tree (decl);
}
e->aux = (void *)1;
}
else
{
error ("Missing callgraph edge for call expr:");
debug_tree (t);
error_found = true;
}
}
if (DECL_P (*tp) || TYPE_P (*tp))
{
*walk_subtrees = 0;
}
return NULL_TREE;
}
void
verify_cgraph_node (struct cgraph_node *node)
{
struct cgraph_edge *e;
struct cgraph_node *main_clone;
timevar_push (TV_CGRAPH_VERIFY);
error_found = false;
for (e = node->callees; e; e = e->next_callee)
if (e->aux)
{
error ("Aux field set for edge %s->%s",
cgraph_node_name (e->caller), cgraph_node_name (e->callee));
error_found = true;
}
for (e = node->callers; e; e = e->next_caller)
{
if (!e->inline_failed)
{
if (node->global.inlined_to
!= (e->caller->global.inlined_to
? e->caller->global.inlined_to : e->caller))
{
error ("Inlined_to pointer is wrong");
error_found = true;
}
if (node->callers->next_caller)
{
error ("Multiple inline callers");
error_found = true;
}
}
else
if (node->global.inlined_to)
{
error ("Inlined_to pointer set for noninline callers");
error_found = true;
}
}
if (!node->callers && node->global.inlined_to)
{
error ("Inlined_to pointer is set but no predecesors found");
error_found = true;
}
if (node->global.inlined_to == node)
{
error ("Inlined_to pointer reffers to itself");
error_found = true;
}
for (main_clone = cgraph_node (node->decl); main_clone;
main_clone = main_clone->next_clone)
if (main_clone == node)
break;
if (!node)
{
error ("Node not found in DECL_ASSEMBLER_NAME hash");
error_found = true;
}
if (node->analyzed
&& DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
&& (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
{
walk_tree_without_duplicates (&DECL_SAVED_TREE (node->decl),
verify_cgraph_node_1, node);
for (e = node->callees; e; e = e->next_callee)
{
if (!e->aux)
{
error ("Edge %s->%s has no corresponding call_expr",
cgraph_node_name (e->caller),
cgraph_node_name (e->callee));
error_found = true;
}
e->aux = 0;
}
}
if (error_found)
{
dump_cgraph_node (stderr, node);
internal_error ("verify_cgraph_node failed.");
}
timevar_pop (TV_CGRAPH_VERIFY);
}
void
verify_cgraph (void)
{
struct cgraph_node *node;
for (node = cgraph_nodes; node; node = node->next)
verify_cgraph_node (node);
}
static void
cgraph_analyze_function (struct cgraph_node *node)
{
tree decl = node->decl;
struct cgraph_edge *e;
current_function_decl = decl;
cgraph_create_edges (node, DECL_SAVED_TREE (decl));
node->local.inlinable = tree_inlinable_function_p (decl);
node->local.self_insns = estimate_num_insns (DECL_SAVED_TREE (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 (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;
node->global.insns = node->local.self_insns;
node->analyzed = true;
current_function_decl = NULL;
}
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");
}
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;
node->next_needed = NULL;
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 ();
}
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))
{
if (cgraph_dump_file)
fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
cgraph_remove_node (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);
}
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;
if (DECL_SAVED_TREE (decl)
&& !node->global.inlined_to
&& (node->needed
|| (e && node->reachable))
&& !TREE_ASM_WRITTEN (decl)
&& !DECL_EXTERNAL (decl))
node->output = 1;
else if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
&& !DECL_EXTERNAL (decl))
{
dump_cgraph_node (stderr, node);
abort ();
}
}
}
static void
cgraph_expand_function (struct cgraph_node *node)
{
tree decl = node->decl;
if (node->global.inlined_to)
abort ();
if (flag_unit_at_a_time)
announce_function (decl);
lang_hooks.callgraph.expand_function (decl);
if (!TREE_ASM_WRITTEN (node->decl))
abort ();
current_function_decl = NULL;
if (DECL_SAVED_TREE (node->decl)
&& !cgraph_preserve_function_body_p (node->decl))
{
DECL_SAVED_TREE (node->decl) = NULL;
DECL_STRUCT_FUNCTION (node->decl) = NULL;
DECL_ARGUMENTS (node->decl) = NULL;
DECL_INITIAL (node->decl) = error_mark_node;
}
}
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 *));
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;
}
static bool
cgraph_remove_unreachable_nodes (void)
{
struct cgraph_node *first = (void *) 1;
struct cgraph_node *node;
bool changed = false;
int insns = 0;
#ifdef ENABLE_CHECKING
verify_cgraph ();
#endif
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 && !node->global.inlined_to
&& (!DECL_EXTERNAL (node->decl) || !node->analyzed))
{
node->aux = first;
first = node;
}
else if (node->aux)
abort ();
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;
}
}
for (node = cgraph_nodes; node; node = node->next)
{
if (!node->aux)
{
int local_insns;
tree decl = node->decl;
node->global.inlined_to = NULL;
if (DECL_STRUCT_FUNCTION (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)
{
struct cgraph_node *clone;
for (clone = node->next_clone; clone;
clone = clone->next_clone)
if (clone->aux)
break;
if (!clone)
{
DECL_SAVED_TREE (node->decl) = NULL;
DECL_STRUCT_FUNCTION (node->decl) = NULL;
DECL_ARGUMENTS (node->decl) = NULL;
DECL_INITIAL (node->decl) = error_mark_node;
}
while (node->callees)
cgraph_remove_edge (node->callees);
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;
}
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;
}
static int
cgraph_estimate_growth (struct cgraph_node *node)
{
int growth = 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);
if (!node->needed && !DECL_EXTERNAL (node->decl))
growth -= node->global.insns;
return growth;
}
void
cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
{
struct cgraph_node *n;
if (!e->callee->callers->next_caller
&& (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
&& duplicate
&& flag_unit_at_a_time)
{
if (e->callee->global.inlined_to)
abort ();
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);
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;
for (e = e->callee->callees; e; e = e->next_callee)
if (!e->inline_failed)
cgraph_clone_inlined_nodes (e, duplicate);
}
void
cgraph_mark_inline_edge (struct cgraph_edge *e)
{
int old_insns = 0, new_insns = 0;
struct cgraph_node *to = NULL, *what;
if (!e->inline_failed)
abort ();
e->inline_failed = NULL;
if (!e->callee->global.inlined && flag_unit_at_a_time)
DECL_POSSIBLY_INLINED (e->callee->decl) = true;
e->callee->global.inlined = true;
cgraph_clone_inlined_nodes (e, true);
what = e->callee;
for (;e && !e->inline_failed; e = e->caller->callers)
{
old_insns = e->caller->global.insns;
new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
what);
if (new_insns < 0)
abort ();
to = e->caller;
to->global.insns = new_insns;
}
if (what->global.inlined_to != to)
abort ();
overall_insns += new_insns - old_insns;
ncalls_inlined++;
}
static struct cgraph_edge *
cgraph_mark_inline (struct cgraph_edge *edge)
{
struct cgraph_node *to = edge->caller;
struct cgraph_node *what = edge->callee;
struct cgraph_edge *e, *next;
int times = 0;
for (e = what->callers; e; e = next)
{
next = e->next_caller;
if (e->caller == to && e->inline_failed)
{
cgraph_mark_inline_edge (e);
if (e == edge)
edge = next;
times ++;
}
}
if (!times)
abort ();
return edge;
}
static bool
cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
const char **reason)
{
int times = 0;
struct cgraph_edge *e;
int newsize;
int limit;
if (to->global.inlined_to)
to = to->global.inlined_to;
for (e = to->callees; e; e = e->next_callee)
if (e->callee == what)
times++;
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)
{
if (reason)
*reason = N_("--param large-function-growth limit reached");
return false;
}
return true;
}
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;
}
static bool
cgraph_recursive_inlining_p (struct cgraph_node *to,
struct cgraph_node *what,
const char **reason)
{
bool recursive;
if (to->global.inlined_to)
recursive = what->decl == to->global.inlined_to->decl;
else
recursive = what->decl == to->decl;
if (recursive && reason)
*reason = (what->local.disregard_inline_limits
? N_("recursive inlining") : "");
return recursive;
}
static void
update_callee_keys (fibheap_t heap, struct fibnode **heap_node,
struct cgraph_node *node)
{
struct cgraph_edge *e;
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));
else if (!e->inline_failed)
update_callee_keys (heap, heap_node, e->callee);
}
static void
lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
struct cgraph_edge **first, struct cgraph_edge **last)
{
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;
}
for (e = where->callees; e; e = e->next_callee)
if (!e->inline_failed)
lookup_recursive_calls (node, e->callee, first, last);
}
static void
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;
struct cgraph_edge *e;
struct cgraph_node *master_clone;
int depth = 0;
int n = 0;
if (DECL_DECLARED_INLINE_P (node->decl))
{
limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
}
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;
if (cgraph_dump_file)
fprintf (cgraph_dump_file,
"\nPerforming recursive inlining on %s\n",
cgraph_node_name (node));
master_clone = cgraph_clone_node (node);
master_clone->needed = true;
for (e = master_clone->callees; e; e = e->next_callee)
if (!e->inline_failed)
cgraph_clone_inlined_nodes (e, true);
last_in_current_depth = last_call;
while (first_call
&& cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
{
struct cgraph_edge *curr = first_call;
first_call = first_call->aux;
curr->aux = NULL;
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;
n++;
}
while (first_call)
{
struct cgraph_edge *next = first_call->aux;
first_call->aux = NULL;
first_call = next;
}
if (cgraph_dump_file)
fprintf (cgraph_dump_file,
"\n Inlined %i times, body grown from %i to %i insns\n", n,
master_clone->global.insns, node->global.insns);
for (node = cgraph_nodes; node != master_clone;
node = node->next)
if (node->global.inlined_to == master_clone)
cgraph_remove_node (node);
cgraph_remove_node (master_clone);
}
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;
}
static void
cgraph_decide_inlining_of_small_functions (void)
{
struct cgraph_node *node;
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);
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, *next;
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;
}
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 (cgraph_dump_file)
fprintf (cgraph_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;
if (heap_node[where->uid])
fibheap_replace_key (heap, heap_node[where->uid],
cgraph_estimate_growth (where));
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);
}
}
cgraph_decide_recursive_inlining (node);
update_callee_keys (heap, heap_node, node);
if (cgraph_dump_file)
fprintf (cgraph_dump_file,
" Inlined for a net change of %+i insns.\n",
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);
}
static void
cgraph_decide_inlining (void)
{
struct cgraph_node *node;
int nnodes;
struct cgraph_node **order =
xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
int old_insns = 0;
int i;
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");
for (i = nnodes - 1; i >= 0; i--)
{
struct cgraph_edge *e, *next;
node = order[i];
if (!node->local.disregard_inline_limits)
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);
old_insns = overall_insns;
for (e = node->callers; e; e = next)
{
next = e->next_caller;
if (!e->inline_failed)
continue;
if (cgraph_recursive_inlining_p (e->caller, e->callee,
&e->inline_failed))
continue;
cgraph_mark_inline_edge (e);
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)
fprintf (cgraph_dump_file,
" Inlined for a net change of %+i insns.\n",
overall_insns - old_insns);
}
if (!flag_really_no_inline)
{
cgraph_decide_inlining_of_small_functions ();
if (cgraph_dump_file)
fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
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;
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 (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);
old_insns = overall_insns;
if (cgraph_check_inline_limits (node->callers->caller, node,
NULL))
{
cgraph_mark_inline (node->callers);
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");
}
}
}
}
}
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);
}
static void
cgraph_decide_inlining_incrementally (struct cgraph_node *node)
{
struct cgraph_edge *e;
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)
&& DECL_SAVED_TREE (e->callee->decl))
cgraph_mark_inline (e);
if (!flag_really_no_inline)
for (e = node->callees; e; e = e->next_callee)
if (e->callee->local.inlinable
&& e->inline_failed
&& !e->callee->local.disregard_inline_limits
&& !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
&& 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");
}
}
bool
cgraph_inline_p (struct cgraph_edge *e, const char **reason)
{
*reason = e->inline_failed;
return !e->inline_failed;
}
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, new_order_pos = 0;
int i;
cgraph_mark_functions_to_output ();
order_pos = cgraph_postorder (order);
if (order_pos != cgraph_n_nodes)
abort ();
for (i = 0; i < order_pos; i++)
if (order[i]->output)
order[new_order_pos++] = order[i];
for (i = new_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);
}
static void
cgraph_mark_local_functions (void)
{
struct cgraph_node *node;
if (cgraph_dump_file)
fprintf (cgraph_dump_file, "\nMarking local functions:");
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");
}
bool
cgraph_preserve_function_body_p (tree decl)
{
struct cgraph_node *node;
if (dump_enabled_p (TDI_all))
return true;
if (!cgraph_global_info_ready)
return (DECL_INLINE (decl) && !flag_really_no_inline);
for (node = cgraph_node (decl); node; node = node->next_clone)
if (node->global.inlined_to)
return true;
return false;
}
void
cgraph_optimize (void)
{
#ifdef ENABLE_CHECKING
verify_cgraph ();
#endif
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);
}
if (flag_inline_trees)
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);
if (!quiet_flag)
fprintf (stderr, "Assembling functions:\n");
#ifdef ENABLE_CHECKING
verify_cgraph ();
#endif
cgraph_expand_all_functions ();
if (cgraph_dump_file)
{
fprintf (cgraph_dump_file, "\nFinal ");
dump_cgraph (cgraph_dump_file);
}
#ifdef ENABLE_CHECKING
verify_cgraph ();
if (flag_unit_at_a_time
&& !dump_enabled_p (TDI_all)
&& !(sorrycount || errorcount))
{
struct cgraph_node *node;
bool error_found = false;
for (node = cgraph_nodes; node; node = node->next)
if (node->analyzed
&& (node->global.inlined_to
|| DECL_SAVED_TREE (node->decl)))
{
error_found = true;
dump_cgraph_node (stderr, node);
}
if (error_found)
internal_error ("Nodes with no released memory found.");
}
#endif
}