#include "coretypes.h"
#include "tm.h"
#include "tree.h"
-#include "tree-inline.h"
#include "langhooks.h"
#include "hashtab.h"
#include "toplev.h"
#include "ggc.h"
#include "debug.h"
#include "target.h"
+#include "cgraph.h"
+#include "varray.h"
+#include "output.h"
-/* The cgraph data strutcture.
- Each function decl has assigned cgraph_node listing calees and callers. */
-
-struct cgraph_node
-{
- tree decl;
- struct cgraph_edge *callees;
- struct cgraph_edge *callers;
- struct cgraph_node *next;
- /* For nested functions points to function the node is nested in. */
- struct cgraph_node *origin;
- /* Points to first nested function, if any. */
- struct cgraph_node *nested;
- /* Pointer to the next function with same origin, if any. */
- struct cgraph_node *next_nested;
- void *aux;
-
- /* Set when function must be output - it is externally visible
- or it's address is taken. */
- bool needed;
- /* Set when function is reachable by call from other function
- that is eighter reachable or needed. */
- bool reachable;
- /* Set when the frontend has been asked to lower representation of this
- function into trees. Callees lists are not available when lowered
- is not set. */
- bool lowered;
- /* Set when function is scheduled to be assembled. */
- bool output;
-};
-
-struct cgraph_edge
-{
- struct cgraph_node *caller, *callee;
- struct cgraph_edge *next_caller;
- struct cgraph_edge *next_callee;
-};
+/* The known declarations must not get garbage collected. Callgraph
+ datastructures should not get saved via PCH code since this would
+ make it difficult to extend into intra-module optimizer later. So
+ we store only the references into the array to prevent gabrage
+ collector from deleting live data. */
+static GTY(()) varray_type known_decls;
/* Hash table used to convert declarations into nodes. */
static htab_t cgraph_hash = 0;
/* The linked list of cgraph nodes. */
-static struct cgraph_node *cgraph_nodes;
+struct cgraph_node *cgraph_nodes;
+
+/* Queue of cgraph nodes scheduled to be lowered. */
+struct cgraph_node *cgraph_nodes_queue;
/* Number of nodes in existence. */
-static int cgraph_n_nodes;
+int cgraph_n_nodes;
+
+/* Set when whole unit has been analyzed so we can access global info. */
+bool cgraph_global_info_ready = false;
+
+/* Hash table used to convert declarations into nodes. */
+static htab_t cgraph_varpool_hash = 0;
+
+/* Queue of cgraph nodes scheduled to be lowered and output. */
+struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
+
+/* Number of nodes in existence. */
+int cgraph_varpool_n_nodes;
-static struct cgraph_node *cgraph_node PARAMS ((tree decl));
static struct cgraph_edge *create_edge PARAMS ((struct cgraph_node *,
struct cgraph_node *));
-static void remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
-static struct cgraph_edge *record_call PARAMS ((tree, tree));
-static tree record_call_1 PARAMS ((tree *, int *, void *));
-static hashval_t hash_node PARAMS ((const PTR));
-static int eq_node PARAMS ((const PTR, const PTR));
-static struct cgraph_node *cgraph_node PARAMS ((tree));
-static void cgraph_expand_functions PARAMS ((void));
-static void cgraph_mark_functions_to_output PARAMS ((void));
-static void cgraph_expand_function PARAMS ((struct cgraph_node *));
-static void cgraph_mark_needed_node PARAMS ((struct cgraph_node *, int));
+static void cgraph_remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
+static hashval_t hash_node PARAMS ((const void *));
+static int eq_node PARAMS ((const void *, const void *));
/* Returns a hash code for P. */
static hashval_t
hash_node (p)
- const PTR p;
+ const void *p;
{
return (hashval_t)
htab_hash_pointer (DECL_ASSEMBLER_NAME
(((struct cgraph_node *) p)->decl));
}
-/* Returns non-zero if P1 and P2 are equal. */
+/* Returns nonzero if P1 and P2 are equal. */
static int
eq_node (p1, p2)
- const PTR p1;
- const PTR p2;
+ const void *p1;
+ const void *p2;
{
return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
- DECL_ASSEMBLER_NAME ((tree) p2));
+ (tree) p2);
}
/* Return cgraph node assigned to DECL. Create new one when needed. */
-static struct cgraph_node *
+struct cgraph_node *
cgraph_node (decl)
tree decl;
{
struct cgraph_node *node;
struct cgraph_node **slot;
+ if (TREE_CODE (decl) != FUNCTION_DECL)
+ abort ();
+
if (!cgraph_hash)
- cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
+ {
+ cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
+ if (!known_decls)
+ VARRAY_TREE_INIT (known_decls, 32, "known_decls");
+ }
slot =
- (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, decl,
+ (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash,
+ DECL_ASSEMBLER_NAME (decl),
htab_hash_pointer
(DECL_ASSEMBLER_NAME
(decl)), 1);
node = xcalloc (sizeof (*node), 1);
node->decl = decl;
node->next = cgraph_nodes;
+ if (cgraph_nodes)
+ cgraph_nodes->previous = node;
+ node->previous = NULL;
cgraph_nodes = node;
cgraph_n_nodes++;
*slot = node;
- if (DECL_CONTEXT (decl))
+ if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
{
node->origin = cgraph_node (DECL_CONTEXT (decl));
node->next_nested = node->origin->nested;
node->origin->nested = node;
}
+ VARRAY_PUSH_TREE (known_decls, decl);
return node;
}
+/* Try to find existing function for identifier ID. */
+struct cgraph_node *
+cgraph_node_for_identifier (id)
+ tree id;
+{
+ struct cgraph_node **slot;
+
+ if (TREE_CODE (id) != IDENTIFIER_NODE)
+ abort ();
+
+ if (!cgraph_hash)
+ return NULL;
+
+ slot =
+ (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, id,
+ htab_hash_pointer (id), 0);
+ if (!slot)
+ return NULL;
+ return *slot;
+}
+
/* Create edge from CALLER to CALLEE in the cgraph. */
static struct cgraph_edge *
/* Remove the edge from CALLER to CALLEE in the cgraph. */
static void
-remove_edge (caller, callee)
+cgraph_remove_edge (caller, callee)
struct cgraph_node *caller, *callee;
{
struct cgraph_edge **edge, **edge2;
*edge2 = (*edge2)->next_callee;
}
+/* Remove the node from cgraph. */
+
+void
+cgraph_remove_node (node)
+ struct cgraph_node *node;
+{
+ while (node->callers)
+ cgraph_remove_edge (node->callers->caller, node);
+ while (node->callees)
+ cgraph_remove_edge (node, node->callees->callee);
+ while (node->nested)
+ cgraph_remove_node (node->nested);
+ if (node->origin)
+ {
+ struct cgraph_node **node2 = &node->origin->nested;
+
+ while (*node2 != node)
+ node2 = &(*node2)->next_nested;
+ *node2 = node->next_nested;
+ }
+ if (node->previous)
+ node->previous->next = node->next;
+ else
+ cgraph_nodes = node;
+ if (node->next)
+ node->next->previous = node->previous;
+ DECL_SAVED_TREE (node->decl) = NULL;
+ /* Do not free the structure itself so the walk over chain can continue. */
+}
+
+/* Notify finalize_compilation_unit that given node is reachable
+ or needed. */
+void
+cgraph_mark_needed_node (node, needed)
+ struct cgraph_node *node;
+ int needed;
+{
+ if (needed)
+ {
+ node->needed = 1;
+ }
+ if (!node->reachable)
+ {
+ node->reachable = 1;
+ if (DECL_SAVED_TREE (node->decl))
+ {
+ node->aux = cgraph_nodes_queue;
+ cgraph_nodes_queue = node;
+ }
+ }
+}
+
+
/* Record call from CALLER to CALLEE */
-static struct cgraph_edge *
-record_call (caller, callee)
+struct cgraph_edge *
+cgraph_record_call (caller, callee)
tree caller, callee;
{
return create_edge (cgraph_node (caller), cgraph_node (callee));
cgraph_remove_call (caller, callee)
tree caller, callee;
{
- remove_edge (cgraph_node (caller), cgraph_node (callee));
+ cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
}
/* Return true when CALLER_DECL calls CALLEE_DECL. */
return edge != NULL;
}
-/* Walk tree and record all calls. Called via walk_tree. */
-static tree
-record_call_1 (tp, walk_subtrees, data)
- tree *tp;
- int *walk_subtrees;
- void *data;
+/* Return local info for the compiled function. */
+
+struct cgraph_local_info *
+cgraph_local_info (decl)
+ tree decl;
{
- /* Record dereferences to the functions. This makes the functions
- reachable unconditionally. */
- if (TREE_CODE (*tp) == ADDR_EXPR)
- {
- tree decl = TREE_OPERAND (*tp, 0);
- if (TREE_CODE (decl) == FUNCTION_DECL)
- cgraph_mark_needed_node (cgraph_node (decl), 1);
- }
- else if (TREE_CODE (*tp) == CALL_EXPR)
- {
- tree decl = TREE_OPERAND (*tp, 0);
- if (TREE_CODE (decl) == ADDR_EXPR)
- decl = TREE_OPERAND (decl, 0);
- if (TREE_CODE (decl) == FUNCTION_DECL)
- {
- if (DECL_BUILT_IN (decl))
- return NULL;
- record_call (data, decl);
- walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
- *walk_subtrees = 0;
- }
- }
- return NULL;
+ struct cgraph_node *node;
+ if (TREE_CODE (decl) != FUNCTION_DECL)
+ abort ();
+ node = cgraph_node (decl);
+ return &node->local;
}
-/* Create cgraph edges for function calles via BODY. */
+/* Return local info for the compiled function. */
-void
-cgraph_create_edges (decl, body)
+struct cgraph_global_info *
+cgraph_global_info (decl)
tree decl;
- tree body;
{
- walk_tree (&body, record_call_1, decl, NULL);
+ struct cgraph_node *node;
+ if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
+ abort ();
+ node = cgraph_node (decl);
+ return &node->global;
}
-/* Analyze function once it is parsed. Set up the local information
- available - create cgraph edges for function calles via BODY. */
+/* Return local info for the compiled function. */
-void
-cgraph_finalize_function (decl, body)
+struct cgraph_rtl_info *
+cgraph_rtl_info (decl)
tree decl;
- tree body ATTRIBUTE_UNUSED;
{
- struct cgraph_node *node = cgraph_node (decl);
-
- node->decl = decl;
-
- /* Set TREE_UNINLINABLE flag. */
- tree_inlinable_function_p (decl);
-
- (*debug_hooks->deferred_inline_function) (decl);
+ struct cgraph_node *node;
+ if (TREE_CODE (decl) != FUNCTION_DECL)
+ abort ();
+ node = cgraph_node (decl);
+ if (decl != current_function_decl
+ && !TREE_ASM_WRITTEN (node->decl))
+ return NULL;
+ return &node->rtl;
}
+
/* Dump the callgraph. */
void
}
}
-static struct cgraph_node *queue = NULL;
+/* Returns a hash code for P. */
-/* Notify finalize_compilation_unit that given node is reachable
- or needed. */
-static void
-cgraph_mark_needed_node (node, needed)
- struct cgraph_node *node;
- int needed;
+static hashval_t
+cgraph_varpool_hash_node (const PTR p)
{
- if (needed)
- {
- if (DECL_SAVED_TREE (node->decl))
- announce_function (node->decl);
- node->needed = 1;
- }
- if (!node->reachable)
- {
- node->reachable = 1;
- if (DECL_SAVED_TREE (node->decl))
- {
- node->aux = queue;
- queue = node;
- }
- }
+ return (hashval_t)
+ htab_hash_pointer (DECL_ASSEMBLER_NAME
+ (((struct cgraph_varpool_node *) p)->decl));
}
-/* Analyze the whole compilation unit once it is parsed completely. */
+/* Returns nonzero if P1 and P2 are equal. */
-void
-cgraph_finalize_compilation_unit ()
+static int
+eq_cgraph_varpool_node (const PTR p1, const PTR p2)
{
- struct cgraph_node *node;
- struct cgraph_edge *edge;
+ return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
+ (tree) p2);
+}
- /* Collect entry points to the unit. */
+/* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
+struct cgraph_varpool_node *
+cgraph_varpool_node (tree decl)
+{
+ struct cgraph_varpool_node *node;
+ struct cgraph_varpool_node **slot;
- if (!quiet_flag)
- fprintf (stderr, "\n\nUnit entry points:");
+ if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
+ abort ();
- for (node = cgraph_nodes; node; node = node->next)
+ if (!cgraph_varpool_hash)
{
- tree decl = node->decl;
-
- if (!DECL_SAVED_TREE (decl))
- continue;
- if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
- || (DECL_ASSEMBLER_NAME_SET_P (decl)
- && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
- {
- cgraph_mark_needed_node (node, 1);
- }
+ cgraph_varpool_hash = htab_create (10, cgraph_varpool_hash_node, eq_cgraph_varpool_node, NULL);
+ if (!known_decls)
+ VARRAY_TREE_INIT (known_decls, 32, "known_decls");
}
- /* 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 (queue)
- {
- tree decl = queue->decl;
-
- node = queue;
- queue = queue->aux;
- if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
- abort ();
-
- /* At the moment frontend automatically emits all nested functions. */
- if (node->nested)
- {
- struct cgraph_node *node2;
+ slot =
+ (struct cgraph_varpool_node **) htab_find_slot_with_hash (cgraph_varpool_hash,
+ DECL_ASSEMBLER_NAME (decl),
+ htab_hash_pointer
+ (DECL_ASSEMBLER_NAME
+ (decl)), 1);
+ if (*slot)
+ return *slot;
+ node = xcalloc (sizeof (*node), 1);
+ node->decl = decl;
+ cgraph_varpool_n_nodes++;
+ *slot = node;
+ VARRAY_PUSH_TREE (known_decls, decl);
+ return node;
+}
- for (node2 = node->nested; node2; node2 = node2->next_nested)
- if (!node2->reachable)
- cgraph_mark_needed_node (node2, 0);
- }
+/* Try to find existing function for identifier ID. */
+struct cgraph_varpool_node *
+cgraph_varpool_node_for_identifier (tree id)
+{
+ struct cgraph_varpool_node **slot;
- if (lang_hooks.callgraph.lower_function)
- (*lang_hooks.callgraph.lower_function) (decl);
- /* First kill forward declaration so reverse inling works properly. */
- cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
+ if (TREE_CODE (id) != IDENTIFIER_NODE)
+ abort ();
- for (edge = node->callees; edge; edge = edge->next_callee)
- {
- if (!edge->callee->reachable)
- cgraph_mark_needed_node (edge->callee, 0);
- }
- node->lowered = true;
- }
- if (!quiet_flag)
- fprintf (stderr, "\n\nReclaiming functions:");
+ if (!cgraph_varpool_hash)
+ return NULL;
- for (node = cgraph_nodes; node; node = node->next)
- {
- tree decl = node->decl;
-
- if (!node->reachable && DECL_SAVED_TREE (decl))
- {
- DECL_SAVED_TREE (decl) = NULL;
- announce_function (decl);
- }
- }
- ggc_collect ();
+ slot =
+ (struct cgraph_varpool_node **) htab_find_slot_with_hash (cgraph_varpool_hash, id,
+ htab_hash_pointer (id), 0);
+ if (!slot)
+ return NULL;
+ return *slot;
}
-/* Expand all functions that must be output. */
-
-#define NPREDECESORS(node) ((size_t) (node)->aux)
-#define SET_NPREDECESORS(node, n) ((node)->aux = (void *) (size_t) (n))
-
-/* Figure out what functions we want to assemble. */
-
-static void
-cgraph_mark_functions_to_output ()
+/* Notify finalize_compilation_unit that given node is reachable
+ or needed. */
+void
+cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
{
- struct cgraph_node *node;
-
- /* Figure out functions we want to assemble. */
- for (node = cgraph_nodes; node; node = node->next)
+ if (!node->needed && node->finalized)
{
- tree decl = node->decl;
-
- if (DECL_SAVED_TREE (decl)
- && (node->needed
- || (DECL_UNINLINABLE (decl) && node->reachable)
- || TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
- && !TREE_ASM_WRITTEN (decl) && !node->origin
- && !DECL_EXTERNAL (decl))
- node->output = 1;
+ node->aux = cgraph_varpool_nodes_queue;
+ cgraph_varpool_nodes_queue = node;
}
+ node->needed = 1;
}
-/* Expand function specified by NODE. */
-static void
-cgraph_expand_function (node)
- struct cgraph_node *node;
-{
- tree decl = node->decl;
-
- announce_function (decl);
- if (flag_inline_trees)
- optimize_inline_calls (decl);
- (*lang_hooks.callgraph.expand_function) (decl);
- if (DECL_UNINLINABLE (decl))
- DECL_SAVED_TREE (decl) = NULL;
- current_function_decl = NULL;
-}
-
-
-/* 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
- accross the callgraph. Use stack to get smaller distance between function
- and it's callees (later we may use more sophisticated algorithm for
- function reordering, we will likely want to use subsections to make output
- functions to appear in top-down order, not bottom-up they are assembled). */
-
-static void
-cgraph_expand_functions ()
+void
+cgraph_varpool_finalize_decl (tree decl)
{
- struct cgraph_node *node;
- struct cgraph_node **stack =
- xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
- int stack_size = 0;
- struct cgraph_edge *edge;
-
- cgraph_mark_functions_to_output ();
+ struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
- for (node = cgraph_nodes; node; node = node->next)
- if (node->output)
- {
- int n = 0;
- for (edge = node->callees; edge; edge = edge->next_callee)
- if (edge->callee->output)
- n++;
- SET_NPREDECESORS (node, n);
- if (n == 0)
- stack[stack_size++] = node;
- }
- while (1)
+ if (node->needed && !node->finalized)
{
- struct cgraph_node *minnode;
- while (stack_size)
- {
- node = stack[--stack_size];
- node->output = 0;
-
- for (edge = node->callers; edge; edge = edge->next_caller)
- if (edge->caller->output)
- {
- SET_NPREDECESORS (edge->caller,
- NPREDECESORS (edge->caller) - 1);
- if (!NPREDECESORS (edge->caller))
- stack[stack_size++] = edge->caller;
- }
- if (!node->reachable)
- abort ();
- cgraph_expand_function (node);
- }
- minnode = NULL;
- /* We found cycle. Break it and try again. */
- for (node = cgraph_nodes; node; node = node->next)
- if (node->output
- && (!minnode
- || NPREDECESORS (minnode) > NPREDECESORS (node)))
- minnode = node;
- if (!minnode)
- return;
- stack[stack_size++] = minnode;
+ node->aux = cgraph_varpool_nodes_queue;
+ cgraph_varpool_nodes_queue = node;
+ }
+ node->finalized = true;
+
+ if (/* Externally visible variables must be output. The exception are
+ COMDAT functions that must be output only when they are needed. */
+ (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
+ /* Function whose name is output to the assembler file must be produced.
+ It is possible to assemble the name later after finalizing the function
+ and the fact is noticed in assemble_name then. */
+ || (DECL_ASSEMBLER_NAME_SET_P (decl)
+ && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
+ {
+ cgraph_varpool_mark_needed_node (node);
}
}
-/* Perform simple optimizations based on callgraph. */
-
-void
-cgraph_optimize ()
+bool
+cgraph_varpool_assemble_pending_decls ()
{
- struct cgraph_node *node;
- bool changed = true;
- struct cgraph_edge *edge;
+ bool changed = false;
- if (!quiet_flag)
- fprintf (stderr, "\n\nAssembling functions:");
-
- /* Output everything.
- ??? Our inline heuristic may decide to not inline functions previously
- marked as inlinable thus adding new function bodies that must be output.
- Later we should move all inlining decisions to callgraph code to make
- this impossible. */
- cgraph_expand_functions ();
- while (changed)
+ while (cgraph_varpool_nodes_queue)
{
- changed = false;
- for (node = cgraph_nodes; node; node = node->next)
- {
- if (!node->needed)
- continue;
+ tree decl = cgraph_varpool_nodes_queue->decl;
+ struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
- for (edge = node->callees; edge; edge = edge->next_callee)
- if (!edge->callee->needed)
- changed = edge->callee->needed = true;
+ cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->aux;
+ if (!TREE_ASM_WRITTEN (decl))
+ {
+ assemble_variable (decl, 0, 1, 0);
+ changed = true;
}
+ node->aux = NULL;
}
- cgraph_expand_functions ();
+ return changed;
}
+
+
+#include "gt-cgraph.h"
OSDN Git Service
