/* Callgraph based intraprocedural optimizations.
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Jan Hubicka
This file is part of GCC.
mark_referenced call in assemble_variable functions referenced by
static variables are noticed too.
- The intra-procedural information is produced and it's existence
+ The intra-procedural information is produced and its existence
indicated by global_info_ready. Once this flag is set it is impossible
to change function from !reachable to reachable and thus
assemble_variable no longer call mark_referenced.
??? Move this to separate file after tree-ssa merge.
We separate inlining decisions from the inliner itself and store it
- inside callgraph as so called inline plan. Reffer to cgraph.c
+ inside callgraph as so called inline plan. Refer to cgraph.c
documentation about particular representation of inline plans in the
callgraph
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. */
+
+
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
+#include "tree-flow.h"
#include "tree-inline.h"
#include "langhooks.h"
-#include "hashtab.h"
+#include "pointer-set.h"
#include "toplev.h"
#include "flags.h"
#include "ggc.h"
#include "c-common.h"
#include "intl.h"
#include "function.h"
+#include "tree-gimple.h"
+#include "output.h"
#define INSNS_PER_CALL 10
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;
+static struct pointer_set_t *visited_nodes;
+
+static FILE *cgraph_dump_file;
/* Determine if function DECL is needed. That is, visible to something
either outside this translation unit, something magic in the system
static bool
decide_is_function_needed (struct cgraph_node *node, tree decl)
{
- struct cgraph_node *origin;
+ tree origin;
/* 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
return false;
/* Nested functions of extern inline function shall not be emit unless
we inlined the origin. */
- for (origin = node->origin; origin; origin = origin->origin)
- if (DECL_EXTERNAL (origin->decl))
+ for (origin = decl_function_context (decl); origin;
+ origin = decl_function_context (origin))
+ if (DECL_EXTERNAL (origin))
return false;
/* We want to emit COMDAT functions only when absolutely necessary. */
if (DECL_COMDAT (decl))
return false;
}
+/* Walk the decls we marked as necessary and see if they reference new
+ variables or functions and add them into the worklists. */
+static bool
+cgraph_varpool_analyze_pending_decls (void)
+{
+ bool changed = false;
+ timevar_push (TV_CGRAPH);
+
+ while (cgraph_varpool_first_unanalyzed_node)
+ {
+ tree decl = cgraph_varpool_first_unanalyzed_node->decl;
+
+ cgraph_varpool_first_unanalyzed_node->analyzed = true;
+
+ cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;
+
+ if (DECL_INITIAL (decl))
+ cgraph_create_edges (NULL, DECL_INITIAL (decl));
+ changed = true;
+ }
+ timevar_pop (TV_CGRAPH);
+ return changed;
+}
+
+/* Optimization of function bodies might've rendered some variables as
+ unnecessary so we want to avoid these from being compiled.
+
+ This is done by prunning the queue and keeping only the variables that
+ really appear needed (ie they are either externally visible or referenced
+ by compiled function). Re-doing the reachability analysis on variables
+ brings back the remaining variables referenced by these. */
+static void
+cgraph_varpool_remove_unreferenced_decls (void)
+{
+ struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue;
+
+ cgraph_varpool_reset_queue ();
+
+ if (errorcount || sorrycount)
+ return;
+
+ while (node)
+ {
+ tree decl = node->decl;
+ next = node->next_needed;
+ node->needed = 0;
+
+ if (node->finalized
+ && ((DECL_ASSEMBLER_NAME_SET_P (decl)
+ && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
+ || node->force_output
+ || decide_is_variable_needed (node, decl)))
+ cgraph_varpool_mark_needed_node (node);
+
+ node = next;
+ }
+ cgraph_varpool_analyze_pending_decls ();
+}
+
+
/* When not doing unit-at-a-time, output all functions enqueued.
Return true when such a functions were found. */
cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
n->next_needed = NULL;
- if (!n->global.inlined_to && !DECL_EXTERNAL (n->decl))
+ if (!n->global.inlined_to
+ && !n->alias
+ && !DECL_EXTERNAL (n->decl))
{
cgraph_expand_function (n);
output = true;
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 ();
+ gcc_assert (!node->output);
/* Reset our data structures so we can analyze the function again. */
memset (&node->local, 0, sizeof (node->local));
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 (!flag_unit_at_a_time)
+ {
+ struct cgraph_node *n;
+
+ for (n = cgraph_nodes; n; n = n->next)
+ if (n->global.inlined_to == node)
+ cgraph_remove_node (n);
+ }
+
+ cgraph_node_remove_callees (node);
/* We may need to re-queue the node for assembling in case
we already proceeded it and ignored as not needed. */
notice_global_symbol (decl);
node->decl = decl;
node->local.finalized = true;
+ if (node->nested)
+ lower_nested_functions (decl);
+ gcc_assert (!node->nested);
/* 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. */
/* ??? 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))
+ if (TREE_STATIC (t) || DECL_EXTERNAL (t))
{
cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
if (lang_hooks.callgraph.analyze_expr)
}
break;
+ case FDESC_EXPR:
case ADDR_EXPR:
if (flag_unit_at_a_time)
{
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))
+ if (IS_TYPE_OR_DECL_P (*tp))
{
*walk_subtrees = 0;
break;
{
/* 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);
+ visited_nodes = pointer_set_create ();
walk_tree (&body, record_call_1, node, visited_nodes);
- htab_delete (visited_nodes);
+ pointer_set_destroy (visited_nodes);
visited_nodes = NULL;
}
static bool error_found;
-/* Callbrack of verify_cgraph_node. Check that all call_exprs have cgraph
- nodes. */
+/* Callback of verify_cgraph_node. Check that all call_exprs have
+ cgraph nodes. */
static tree
verify_cgraph_node_1 (tree *tp, int *walk_subtrees, void *data)
/* 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))
+ if (IS_TYPE_OR_DECL_P (*tp))
*walk_subtrees = 0;
return NULL_TREE;
{
struct cgraph_node *node;
+ if (sorrycount || errorcount)
+ return;
+
for (node = cgraph_nodes; node; node = node->next)
verify_cgraph_node (node);
}
+
+/* Output all variables enqueued to be assembled. */
+bool
+cgraph_varpool_assemble_pending_decls (void)
+{
+ bool changed = false;
+
+ if (errorcount || sorrycount)
+ return false;
+
+ /* EH might mark decls as needed during expansion. This should be safe since
+ we don't create references to new function, but it should not be used
+ elsewhere. */
+ cgraph_varpool_analyze_pending_decls ();
+
+ while (cgraph_varpool_nodes_queue)
+ {
+ tree decl = cgraph_varpool_nodes_queue->decl;
+ struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
+
+ cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
+ if (!TREE_ASM_WRITTEN (decl) && !node->alias && !DECL_EXTERNAL (decl))
+ {
+ assemble_variable (decl, 0, 1, 0);
+ changed = true;
+ }
+ node->next_needed = NULL;
+ }
+ return changed;
+}
+
/* Analyze the function scheduled to be output. */
static void
cgraph_analyze_function (struct cgraph_node *node)
cgraph_finalize_compilation_unit (void)
{
struct cgraph_node *node;
+ /* Keep track of already processed nodes when called multiple times for
+ intermodule optimization. */
+ static struct cgraph_node *first_analyzed;
+
+ finish_aliases_1 ();
if (!flag_unit_at_a_time)
{
return;
}
- cgraph_varpool_assemble_pending_decls ();
if (!quiet_flag)
- fprintf (stderr, "\nAnalyzing compilation unit\n");
+ {
+ fprintf (stderr, "\nAnalyzing compilation unit");
+ fflush (stderr);
+ }
timevar_push (TV_CGRAPH);
+ cgraph_varpool_analyze_pending_decls ();
if (cgraph_dump_file)
{
fprintf (cgraph_dump_file, "Initial entry points:");
- for (node = cgraph_nodes; node; node = node->next)
+ for (node = cgraph_nodes; node != first_analyzed; 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");
if (!DECL_SAVED_TREE (decl))
continue;
- if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl))
- abort ();
+ gcc_assert (!node->analyzed && node->reachable);
+ gcc_assert (DECL_SAVED_TREE (decl));
cgraph_analyze_function (node);
if (!edge->callee->reachable)
cgraph_mark_reachable_node (edge->callee);
- cgraph_varpool_assemble_pending_decls ();
+ cgraph_varpool_analyze_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)
+ for (node = cgraph_nodes; node != first_analyzed; 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 ");
if (cgraph_dump_file)
fprintf (cgraph_dump_file, "\nReclaiming functions:");
- for (node = cgraph_nodes; node; node = node->next)
+ for (node = cgraph_nodes; node != first_analyzed; node = node->next)
{
tree decl = node->decl;
fprintf (cgraph_dump_file, "\n\nReclaimed ");
dump_cgraph (cgraph_dump_file);
}
+ first_analyzed = cgraph_nodes;
ggc_collect ();
timevar_pop (TV_CGRAPH);
}
{
tree decl = node->decl;
struct cgraph_edge *e;
- if (node->output)
- abort ();
+
+ gcc_assert (!node->output);
for (e = node->callers; e; e = e->next_caller)
if (e->inline_failed)
&& !TREE_ASM_WRITTEN (decl)
&& !DECL_EXTERNAL (decl))
node->output = 1;
- /* We should've reclaimed all functions that are not needed. */
- else if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
- && !DECL_EXTERNAL (decl))
+ else
{
- dump_cgraph_node (stderr, node);
- abort ();
+ /* We should've reclaimed all functions that are not needed. */
+#ifdef ENABLE_CHECKING
+ if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
+ && !DECL_EXTERNAL (decl))
+ {
+ dump_cgraph_node (stderr, node);
+ internal_error ("failed to reclaim unneeded function");
+ }
+#endif
+ gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl)
+ || DECL_EXTERNAL (decl));
+
}
+
}
}
tree decl = node->decl;
/* We ought to not compile any inline clones. */
- if (node->global.inlined_to)
- abort ();
+ gcc_assert (!node->global.inlined_to);
if (flag_unit_at_a_time)
announce_function (decl);
/* Make sure that BE didn't give up on compiling. */
/* ??? Can happen with nested function of extern inline. */
- if (!TREE_ASM_WRITTEN (node->decl))
- abort ();
+ gcc_assert (TREE_ASM_WRITTEN (node->decl));
current_function_decl = NULL;
- if (DECL_SAVED_TREE (node->decl)
- && !cgraph_preserve_function_body_p (node->decl))
+ if (!cgraph_preserve_function_body_p (node->decl))
{
DECL_SAVED_TREE (node->decl) = NULL;
DECL_STRUCT_FUNCTION (node->decl) = NULL;
DECL_INITIAL (node->decl) = error_mark_node;
+ /* Eliminate all call edges. This is important so the call_expr no longer
+ points to the dead function body. */
+ cgraph_node_remove_callees (node);
}
}
return order_pos;
}
+
/* 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. */
fprintf (cgraph_dump_file, "\nReclaiming functions:");
#ifdef ENABLE_CHECKING
for (node = cgraph_nodes; node; node = node->next)
- if (node->aux)
- abort ();
+ gcc_assert (!node->aux);
#endif
for (node = cgraph_nodes; node; node = node->next)
if (node->needed && !node->global.inlined_to
node->aux = first;
first = node;
}
- else if (node->aux)
- abort ();
+ else
+ gcc_assert (!node->aux);
/* Perform reachability analysis. As a special case do not consider
extern inline functions not inlined as live because we won't output
DECL_STRUCT_FUNCTION (node->decl) = NULL;
DECL_INITIAL (node->decl) = error_mark_node;
}
- while (node->callees)
- cgraph_remove_edge (node->callees);
+ cgraph_node_remove_callees (node);
node->analyzed = false;
}
else
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;
+ tree fndecl = what->decl;
+ tree 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;
}
/* Estimate the growth caused by inlining NODE into all callees. */
&& duplicate
&& flag_unit_at_a_time)
{
- if (e->callee->global.inlined_to)
- abort ();
+ gcc_assert (!e->callee->global.inlined_to);
if (!DECL_EXTERNAL (e->callee->decl))
overall_insns -= e->callee->global.insns, nfunctions_inlined++;
duplicate = 0;
int old_insns = 0, new_insns = 0;
struct cgraph_node *to = NULL, *what;
- if (!e->inline_failed)
- abort ();
+ gcc_assert (e->inline_failed);
e->inline_failed = NULL;
if (!e->callee->global.inlined && flag_unit_at_a_time)
old_insns = e->caller->global.insns;
new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
what);
- if (new_insns < 0)
- abort ();
+ gcc_assert (new_insns >= 0);
to = e->caller;
to->global.insns = new_insns;
}
- if (what->global.inlined_to != to)
- abort ();
- overall_insns += new_insns - old_insns;
+ gcc_assert (what->global.inlined_to == to);
+ if (new_insns > old_insns)
+ overall_insns += new_insns - old_insns;
ncalls_inlined++;
}
cgraph_mark_inline_edge (e);
if (e == edge)
edge = next;
- times ++;
+ times++;
}
}
- if (!times)
- abort ();
+ gcc_assert (times);
return edge;
}
max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
}
- /* Make sure that function is small enought to be considered for inlining. */
+ /* 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;
return !e->inline_failed;
}
+
+
/* Expand all functions that must be output.
Attempt to topologically sort the nodes so function is output when
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 ();
+ gcc_assert (order_pos == cgraph_n_nodes);
/* Garbage collector may remove inline clones we eliminate during
optimization. So we must be sure to not reference them. */
node = order[i];
if (node->output)
{
- if (!node->reachable)
- abort ();
+ gcc_assert (node->reachable);
node->output = 0;
cgraph_expand_function (node);
}
}
/* Mark all local functions.
-
- A local function is one whose calls can occur only in the
- current compilation unit and all its calls are explicit,
- so we can change its calling convention.
- We simply mark all static functions whose address is not taken
- as local. */
+
+ A local function is one whose calls can occur only in the current
+ compilation unit and all its 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");
+ {
+ fprintf (cgraph_dump_file, "\nMarking local functions:");
+ for (node = cgraph_nodes; node; node = node->next)
+ if (node->local.local)
+ fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
+ fprintf (cgraph_dump_file, "\n\n");
+ }
}
/* Return true when function body of DECL still needs to be kept around
{
struct cgraph_node *node;
/* Keep the body; we're going to dump it. */
- if (dump_enabled_p (TDI_all))
+ if (dump_enabled_p (TDI_tree_all))
return true;
if (!cgraph_global_info_ready)
return (DECL_INLINE (decl) && !flag_really_no_inline);
verify_cgraph ();
#endif
if (!flag_unit_at_a_time)
- return;
+ {
+ cgraph_varpool_assemble_pending_decls ();
+ return;
+ }
+
+ process_pending_assemble_externals ();
+
+ /* Frontend may output common variables after the unit has been finalized.
+ It is safe to deal with them here as they are always zero initialized. */
+ cgraph_varpool_analyze_pending_decls ();
+
timevar_push (TV_CGRAPHOPT);
if (!quiet_flag)
fprintf (stderr, "Performing intraprocedural optimizations\n");
{
fprintf (cgraph_dump_file, "Optimized ");
dump_cgraph (cgraph_dump_file);
+ dump_varpool (cgraph_dump_file);
}
timevar_pop (TV_CGRAPHOPT);
#ifdef ENABLE_CHECKING
verify_cgraph ();
#endif
+
+ cgraph_mark_functions_to_output ();
cgraph_expand_all_functions ();
+ cgraph_varpool_remove_unreferenced_decls ();
+
+ cgraph_varpool_assemble_pending_decls ();
+
if (cgraph_dump_file)
{
fprintf (cgraph_dump_file, "\nFinal ");
/* Double check that all inline clones are gone and that all
function bodies have been released from memory. */
if (flag_unit_at_a_time
- && !dump_enabled_p (TDI_all)
+ && !dump_enabled_p (TDI_tree_all)
&& !(sorrycount || errorcount))
{
struct cgraph_node *node;
DECL_SOURCE_LOCATION (decl) = input_location;
cfun->function_end_locus = input_location;
- if (which == 'I')
- DECL_STATIC_CONSTRUCTOR (decl) = 1;
- else if (which == 'D')
- DECL_STATIC_DESTRUCTOR (decl) = 1;
- else
- abort ();
+ switch (which)
+ {
+ case 'I':
+ DECL_STATIC_CONSTRUCTOR (decl) = 1;
+ break;
+ case 'D':
+ DECL_STATIC_DESTRUCTOR (decl) = 1;
+ break;
+ default:
+ gcc_unreachable ();
+ }
gimplify_function_tree (decl);
/* ??? We will get called LATE in the compilation process. */
if (cgraph_global_info_ready)
- tree_rest_of_compilation (decl, false);
+ tree_rest_of_compilation (decl);
else
cgraph_finalize_function (decl, 0);
fn (XEXP (DECL_RTL (decl), 0), priority);
}
}
+
+void
+init_cgraph (void)
+{
+ cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
+}