decision on whether function is needed is made more conservative so
uninlininable static functions are needed too. During the call-graph
construction the edge destinations are not marked as reachable and it
- is completely relied upn assemble_variable to mark them.
-
- Inlining decision heuristics
- ??? 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. Refer to cgraph.c
- documentation about particular representation of inline plans in the
- callgraph
-
- The implementation of particular heuristics is separated from
- the rest of code to make it easier to replace it with more complicated
- implementation in the future. The rest of inlining code acts as a
- library aimed to modify the callgraph and verify that the parameters
- on code size growth fits.
-
- To mark given call inline, use cgraph_mark_inline function, the
- verification is performed by cgraph_default_inline_p and
- cgraph_check_inline_limits.
-
- The heuristics implements simple knapsack style algorithm ordering
- all functions by their "profitability" (estimated by code size growth)
- and inlining them in priority order.
-
- 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. */
+ is completely relied upn assemble_variable to mark them. */
#include "config.h"
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 tree record_reference (tree *, int *, void *);
static void cgraph_analyze_function (struct cgraph_node *node);
-/* Records tree nodes seen in cgraph_create_edges. Simply using
+/* Records tree nodes seen in record_reference. 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. */
+ record_reference itself. */
static struct pointer_set_t *visited_nodes;
static FILE *cgraph_dump_file;
{
tree origin;
+ /* 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 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 (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;
cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;
if (DECL_INITIAL (decl))
- cgraph_create_edges (NULL, DECL_INITIAL (decl));
+ {
+ visited_nodes = pointer_set_create ();
+ walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);
+ pointer_set_destroy (visited_nodes);
+ visited_nodes = NULL;
+ }
changed = true;
}
timevar_pop (TV_CGRAPH);
/* 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
+ This is done by pruning 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. */
return output;
}
+/* 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. */
+
+static void
+cgraph_reset_node (struct cgraph_node *node)
+{
+ /* 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. */
+ gcc_assert (!node->output);
+
+ /* Reset our data structures 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;
+ node->local.finalized = false;
+
+ 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. */
+ 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;
+ }
+}
/* 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
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. */
- gcc_assert (!node->output);
-
- /* Reset our data structures 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;
-
- 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. */
- 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;
- }
- }
+ cgraph_reset_node (node);
notice_global_symbol (decl);
node->decl = decl;
if (decide_is_function_needed (node, decl))
cgraph_mark_needed_node (node);
+ /* Since we reclaim unreachable nodes at the end of every language
+ level unit, we need to be conservative about possible entry points
+ there. */
+ if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
+ cgraph_mark_reachable_node (node);
+
/* If not unit at a time, go ahead and emit everything we've found
to be reachable at this time. */
if (!nested)
node->lowered = true;
}
-
/* Walk tree and record all calls. Called via walk_tree. */
static tree
-record_call_1 (tree *tp, int *walk_subtrees, void *data)
+record_reference (tree *tp, int *walk_subtrees, void *data)
{
tree t = *tp;
}
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);
-
- /* 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. */
/* Create cgraph edges for function calls inside BODY from NODE. */
-void
+static void
cgraph_create_edges (struct cgraph_node *node, tree body)
{
- /* The nodes we're interested in are never shared, so walk
- the tree ignoring duplicates. */
+ basic_block bb;
+
+ struct function *this_cfun = DECL_STRUCT_FUNCTION (body);
+ block_stmt_iterator bsi;
+ tree step;
visited_nodes = pointer_set_create ();
- if (TREE_CODE (body) == FUNCTION_DECL)
- {
- struct function *this_cfun = DECL_STRUCT_FUNCTION (body);
- basic_block this_block;
- block_stmt_iterator bsi;
- tree step;
-
- /* Reach the trees by walking over the CFG, and note the
- enclosing basic-blocks in the call edges. */
- FOR_EACH_BB_FN (this_block, this_cfun)
- for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
- walk_tree (bsi_stmt_ptr (bsi), record_call_1, node, visited_nodes);
-
- /* Walk over any private statics that may take addresses of functions. */
- if (TREE_CODE (DECL_INITIAL (body)) == BLOCK)
- {
- for (step = BLOCK_VARS (DECL_INITIAL (body));
- step;
- step = TREE_CHAIN (step))
- if (DECL_INITIAL (step))
- walk_tree (&DECL_INITIAL (step), record_call_1, node, visited_nodes);
- }
- /* Also look here for private statics. */
- if (DECL_STRUCT_FUNCTION (body))
- for (step = DECL_STRUCT_FUNCTION (body)->unexpanded_var_list;
- step;
- step = TREE_CHAIN (step))
+ /* Reach the trees by walking over the CFG, and note the
+ enclosing basic-blocks in the call edges. */
+ FOR_EACH_BB_FN (bb, this_cfun)
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ tree call = get_call_expr_in (stmt);
+ tree decl;
+
+ if (call && (decl = get_callee_fndecl (call)))
{
- tree decl = TREE_VALUE (step);
- if (DECL_INITIAL (decl) && TREE_STATIC (decl))
- walk_tree (&DECL_INITIAL (decl), record_call_1, node, visited_nodes);
+ cgraph_create_edge (node, cgraph_node (decl), stmt,
+ bb->count,
+ bb->loop_depth);
+ walk_tree (&TREE_OPERAND (call, 1),
+ record_reference, node, visited_nodes);
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ walk_tree (&TREE_OPERAND (stmt, 0),
+ record_reference, node, visited_nodes);
}
+ else
+ walk_tree (bsi_stmt_ptr (bsi), record_reference, node, visited_nodes);
+ }
+
+ /* Look for initializers of constant variables and private statics. */
+ for (step = DECL_STRUCT_FUNCTION (body)->unexpanded_var_list;
+ step;
+ step = TREE_CHAIN (step))
+ {
+ tree decl = TREE_VALUE (step);
+ if (TREE_CODE (decl) == VAR_DECL
+ && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
+ && flag_unit_at_a_time)
+ cgraph_varpool_finalize_decl (decl);
+ else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl))
+ walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);
}
- else
- walk_tree (&body, record_call_1, node, visited_nodes);
- walk_tree (&body, record_call_1, node, visited_nodes);
pointer_set_destroy (visited_nodes);
visited_nodes = NULL;
}
-static bool error_found;
-
-/* 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)
-{
- 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;
- }
- }
-
- /* Save some cycles by not walking types and declaration as we
- won't find anything useful there anyway. */
- if (IS_TYPE_OR_DECL_P (*tp))
- *walk_subtrees = 0;
-
- return NULL_TREE;
-}
/* Verify cgraph nodes of given cgraph node. */
void
struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
basic_block this_block;
block_stmt_iterator bsi;
+ bool error_found = false;
timevar_push (TV_CGRAPH_VERIFY);
- error_found = false;
for (e = node->callees; e; e = e->next_callee)
if (e->aux)
{
}
if (node->global.inlined_to == node)
{
- error ("Inlined_to pointer reffers to itself");
+ error ("Inlined_to pointer refers to itself");
error_found = true;
}
enclosing basic-blocks in the call edges. */
FOR_EACH_BB_FN (this_block, this_cfun)
for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
- walk_tree (bsi_stmt_ptr (bsi), verify_cgraph_node_1, node, visited_nodes);
+ {
+ tree stmt = bsi_stmt (bsi);
+ tree call = get_call_expr_in (stmt);
+ tree decl;
+ if (call && (decl = get_callee_fndecl (call)))
+ {
+ struct cgraph_edge *e = cgraph_edge (node, stmt);
+ if (e)
+ {
+ if (e->aux)
+ {
+ error ("Shared call_stmt:");
+ debug_generic_stmt (stmt);
+ 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 stmt:");
+ debug_generic_stmt (stmt);
+ error_found = true;
+ }
+ }
+ }
pointer_set_destroy (visited_nodes);
visited_nodes = NULL;
}
{
if (!e->aux)
{
- error ("Edge %s->%s has no corresponding call_expr",
+ error ("Edge %s->%s has no corresponding call_stmt",
cgraph_node_name (e->caller),
cgraph_node_name (e->callee));
+ debug_generic_stmt (e->call_stmt);
error_found = true;
}
e->aux = 0;
if (!TREE_ASM_WRITTEN (decl) && !node->alias && !DECL_EXTERNAL (decl))
{
assemble_variable (decl, 0, 1, 0);
+ /* Local static variables are never seen by check_global_declarations
+ so we need to output debug info by hand. */
+ if (decl_function_context (decl) && errorcount == 0 && sorrycount == 0)
+ {
+ timevar_push (TV_SYMOUT);
+ (*debug_hooks->global_decl) (decl);
+ timevar_pop (TV_SYMOUT);
+ }
changed = true;
}
node->next_needed = NULL;
weak alias attribute to kill its body. See
gcc.c-torture/compile/20011119-1.c */
if (!DECL_SAVED_TREE (decl))
- continue;
+ {
+ cgraph_reset_node (node);
+ continue;
+ }
gcc_assert (!node->analyzed && node->reachable);
gcc_assert (DECL_SAVED_TREE (decl));
{
tree decl = node->decl;
+ if (node->local.finalized && !DECL_SAVED_TREE (decl))
+ cgraph_reset_node (node);
+
if (!node->reachable && DECL_SAVED_TREE (decl))
{
if (cgraph_dump_file)
fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
cgraph_remove_node (node);
+ continue;
}
else
node->next_needed = NULL;
+ gcc_assert (!node->local.finalized || DECL_SAVED_TREE (decl));
+ gcc_assert (node->analyzed == node->local.finalized);
}
if (cgraph_dump_file)
{
if (flag_unit_at_a_time)
announce_function (decl);
+ cgraph_lower_function (node);
+
/* Generate RTL for the body of DECL. */
lang_hooks.callgraph.expand_function (decl);
points to the dead function body. */
cgraph_node_remove_callees (node);
}
+
+ cgraph_function_flags_ready = true;
}
/* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
free (order);
}
-/* Mark all local functions.
+/* Mark visibility of all 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. */
+ address is not taken as local.
+
+ We also change the TREE_PUBLIC flag of all declarations that are public
+ in language point of view but we want to overwrite this default
+ via visibilities for the backend point of view. */
static void
-cgraph_mark_local_functions (void)
+cgraph_function_and_variable_visibility (void)
{
struct cgraph_node *node;
+ struct cgraph_varpool_node *vnode;
- /* Figure out functions we want to assemble. */
for (node = cgraph_nodes; node; node = node->next)
{
+ if (node->reachable
+ && (DECL_COMDAT (node->decl)
+ || (TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
+ node->local.externally_visible = 1;
node->local.local = (!node->needed
- && DECL_SAVED_TREE (node->decl)
- && !TREE_PUBLIC (node->decl));
+ && node->analyzed
+ && !DECL_EXTERNAL (node->decl)
+ && !node->local.externally_visible);
+ }
+ for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
+ {
+ if (vnode->needed
+ && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
+ vnode->externally_visible = 1;
+ gcc_assert (TREE_STATIC (vnode->decl));
}
+ /* Because we have to be conservative on the boundaries of source
+ level units, it is possible that we marked some functions in
+ reachable just because they might be used later via external
+ linkage, but after making them local they are really unreachable
+ now. */
+ cgraph_remove_unreachable_nodes (true, cgraph_dump_file);
+
if (cgraph_dump_file)
{
fprintf (cgraph_dump_file, "\nMarking local functions:");
if (node->local.local)
fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
fprintf (cgraph_dump_file, "\n\n");
+ fprintf (cgraph_dump_file, "\nMarking externally visible functions:");
+ for (node = cgraph_nodes; node; node = node->next)
+ if (node->local.externally_visible)
+ fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
+ fprintf (cgraph_dump_file, "\n\n");
}
+ cgraph_function_flags_ready = true;
}
/* Return true when function body of DECL still needs to be kept around
if (!quiet_flag)
fprintf (stderr, "Performing intraprocedural optimizations\n");
- cgraph_mark_local_functions ();
+ cgraph_function_and_variable_visibility ();
if (cgraph_dump_file)
{
fprintf (cgraph_dump_file, "Marked ");
dump_cgraph (cgraph_dump_file);
}
ipa_passes ();
+ /* This pass remove bodies of extern inline functions we never inlined.
+ Do this later so other IPA passes see what is really going on. */
+ cgraph_remove_unreachable_nodes (false, dump_file);
cgraph_global_info_ready = true;
if (cgraph_dump_file)
{
OSDN Git Service
