This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Breakup cgraph.c
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com
- Date: Sat, 22 Feb 2003 02:03:20 +0100
- Subject: Breakup cgraph.c
Hi,
this patch just breaks cgraph.c into cgraph.c (generic callgraph
function) and cgraphunit.c (actual unit-at-a-time driver) as needed
for local function patch (so cgraph.c may be linked into frontends not
doing function-at-a-time). It's functions still can be used as natural
way to attach backend information into callgraph nodes and it solves
problems of calling cgraph functions from middle end.
It also puts more things into header so we can create new files for more
complex optimizers in future.
No changes into code are made. Regtested i386 OK?
* Makefile.in (c-decl.o, c-objc-common.o, cgraph.o, tree-inline.o): Add
dependency on cgraph.h
* c-decl.c: Include cgraph.h
(finish_function): Update call of tree_inlinable_function_p.
* c-objc-common.c: Include cgraph.h
* cgraph.h: New file.
* cgraphunit.c: New file.
* cgraph.c (cgraph_node, cgraph_edge): Move into cgraph.h
(cgraph_nodes, cgraph_n_nodes): Globalize.
(cgraph_finalize_function, cgraph_finalize_compilation_unit
cgraph_create_edges, cgraph_optimize, cgraph_mark_needed_node):
Move into cgraphunit.c
* tree-inline.c: Include cgraph.h
* tree-inline.c: Include cgraph.h
Index: gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.998
diff -c -3 -p -r1.998 Makefile.in
*** gcc/Makefile.in 19 Feb 2003 18:03:02 -0000 1.998
--- gcc/Makefile.in 22 Feb 2003 00:57:59 -0000
*************** OBJS = alias.o bb-reorder.o bitmap.o bui
*** 785,791 ****
sibcall.o simplify-rtx.o sreal.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
! alloc-pool.o et-forest.o cgraph.o \
$(GGC) $(out_object_file) $(EXTRA_OBJS) $(host_hook_obj)
BACKEND = main.o libbackend.a
--- 785,791 ----
sibcall.o simplify-rtx.o sreal.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
! alloc-pool.o et-forest.o cgraph.o cgraphunit.o \
$(GGC) $(out_object_file) $(EXTRA_OBJS) $(host_hook_obj)
BACKEND = main.o libbackend.a
*************** $(parsedir)/c-parse.y: c-parse.in
*** 1221,1227 ****
c-decl.o : c-decl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(RTL_H) \
$(C_TREE_H) $(GGC_H) $(TARGET_H) flags.h function.h output.h $(EXPR_H) \
debug.h toplev.h intl.h $(TM_P_H) tree-inline.h $(TIMEVAR_H) c-pragma.h \
! gt-c-decl.h
c-typeck.o : c-typeck.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
$(TARGET_H) flags.h intl.h output.h $(EXPR_H) $(RTL_H) toplev.h $(TM_P_H)
c-lang.o : c-lang.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
--- 1221,1227 ----
c-decl.o : c-decl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(RTL_H) \
$(C_TREE_H) $(GGC_H) $(TARGET_H) flags.h function.h output.h $(EXPR_H) \
debug.h toplev.h intl.h $(TM_P_H) tree-inline.h $(TIMEVAR_H) c-pragma.h \
! gt-c-decl.h cgraph.h
c-typeck.o : c-typeck.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
$(TARGET_H) flags.h intl.h output.h $(EXPR_H) $(RTL_H) toplev.h $(TM_P_H)
c-lang.o : c-lang.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
*************** c-lex.o : c-lex.c $(CONFIG_H) $(SYSTEM_H
*** 1233,1239 ****
c-objc-common.o : c-objc-common.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) $(RTL_H) insn-config.h integrate.h $(EXPR_H) $(C_TREE_H) \
flags.h toplev.h tree-inline.h diagnostic.h integrate.h $(VARRAY_H) \
! langhooks.h $(GGC_H) gt-c-objc-common.h $(TARGET_H)
c-aux-info.o : c-aux-info.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) flags.h toplev.h
c-convert.o : c-convert.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
--- 1233,1239 ----
c-objc-common.o : c-objc-common.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) $(RTL_H) insn-config.h integrate.h $(EXPR_H) $(C_TREE_H) \
flags.h toplev.h tree-inline.h diagnostic.h integrate.h $(VARRAY_H) \
! langhooks.h $(GGC_H) gt-c-objc-common.h $(TARGET_H) cgraph.h
c-aux-info.o : c-aux-info.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(C_TREE_H) flags.h toplev.h
c-convert.o : c-convert.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
*************** tree-dump.o: tree-dump.c $(CONFIG_H) $(S
*** 1413,1419 ****
tree-inline.o : tree-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(RTL_H) expr.h flags.h params.h input.h insn-config.h $(INTEGRATE_H) \
$(VARRAY_H) $(HASHTAB_H) $(SPLAY_TREE_H) toplev.h langhooks.h \
! $(C_COMMON_H) tree-inline.h
print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(GGC_H) langhooks.h real.h
stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
--- 1413,1419 ----
tree-inline.o : tree-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(RTL_H) expr.h flags.h params.h input.h insn-config.h $(INTEGRATE_H) \
$(VARRAY_H) $(HASHTAB_H) $(SPLAY_TREE_H) toplev.h langhooks.h \
! $(C_COMMON_H) tree-inline.h cgraph.h
print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
$(GGC_H) langhooks.h real.h
stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
*************** simplify-rtx.o : simplify-rtx.c $(CONFIG
*** 1532,1538 ****
$(REGS_H) hard-reg-set.h flags.h real.h insn-config.h $(RECOG_H) $(EXPR_H) toplev.h \
output.h function.h $(GGC_H) $(OBSTACK_H) $(TM_P_H) $(TREE_H) $(TARGET_H)
cgraph.o : cgraph.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
! langhooks.h tree-inline.h toplev.h flags.h ggc.h $(TARGET_H)
cselib.o : cselib.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
hard-reg-set.h flags.h real.h insn-config.h $(RECOG_H) $(EXPR_H) toplev.h \
output.h function.h cselib.h $(GGC_H) $(TM_P_H) gt-cselib.h
--- 1532,1540 ----
$(REGS_H) hard-reg-set.h flags.h real.h insn-config.h $(RECOG_H) $(EXPR_H) toplev.h \
output.h function.h $(GGC_H) $(OBSTACK_H) $(TM_P_H) $(TREE_H) $(TARGET_H)
cgraph.o : cgraph.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
! langhooks.h tree-inline.h toplev.h flags.h ggc.h $(TARGET_H) cgraph.h
! cgraphunit.o : cgraphunit.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
! langhooks.h tree-inline.h toplev.h flags.h ggc.h $(TARGET_H) cgraph.h
cselib.o : cselib.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
hard-reg-set.h flags.h real.h insn-config.h $(RECOG_H) $(EXPR_H) toplev.h \
output.h function.h cselib.h $(GGC_H) $(TM_P_H) gt-cselib.h
Index: gcc/c-decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-decl.c,v
retrieving revision 1.363
diff -c -3 -p -r1.363 c-decl.c
*** gcc/c-decl.c 12 Feb 2003 21:48:56 -0000 1.363
--- gcc/c-decl.c 22 Feb 2003 00:58:00 -0000
*************** Software Foundation, 59 Temple Place - S
*** 48,53 ****
--- 48,54 ----
#include "timevar.h"
#include "c-common.h"
#include "c-pragma.h"
+ #include "cgraph.h"
/* In grokdeclarator, distinguish syntactic contexts of declarators. */
enum decl_context
Index: gcc/c-objc-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-objc-common.c,v
retrieving revision 1.21
diff -c -3 -p -r1.21 c-objc-common.c
*** gcc/c-objc-common.c 12 Feb 2003 21:48:57 -0000 1.21
--- gcc/c-objc-common.c 22 Feb 2003 00:58:00 -0000
*************** Software Foundation, 59 Temple Place - S
*** 37,42 ****
--- 37,43 ----
#include "ggc.h"
#include "langhooks.h"
#include "target.h"
+ #include "cgraph.h"
static bool c_tree_printer PARAMS ((output_buffer *, text_info *));
static tree inline_forbidden_p PARAMS ((tree *, int *, void *));
Index: gcc/cgraph.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraph.c,v
retrieving revision 1.3
diff -c -3 -p -r1.3 cgraph.c
*** gcc/cgraph.c 19 Feb 2003 10:24:54 -0000 1.3
--- gcc/cgraph.c 22 Feb 2003 00:58:00 -0000
*************** Software Foundation, 59 Temple Place - S
*** 32,98 ****
#include "ggc.h"
#include "debug.h"
#include "target.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;
! };
/* 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;
/* Number of nodes in existence. */
! static int cgraph_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));
/* Returns a hash code for P. */
--- 32,53 ----
#include "ggc.h"
#include "debug.h"
#include "target.h"
! #include "cgraph.h"
/* Hash table used to convert declarations into nodes. */
static htab_t cgraph_hash = 0;
/* The linked list of cgraph nodes. */
! struct cgraph_node *cgraph_nodes;
/* Number of nodes in existence. */
! int cgraph_n_nodes;
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 hashval_t hash_node PARAMS ((const PTR));
static int eq_node PARAMS ((const PTR, const PTR));
/* Returns a hash code for P. */
*************** eq_node (p1, p2)
*** 117,123 ****
}
/* Return cgraph node assigned to DECL. Create new one when needed. */
! static struct cgraph_node *
cgraph_node (decl)
tree decl;
{
--- 72,78 ----
}
/* Return cgraph node assigned to DECL. Create new one when needed. */
! struct cgraph_node *
cgraph_node (decl)
tree decl;
{
*************** remove_edge (caller, callee)
*** 190,197 ****
/* Record call from CALLER to CALLEE */
! static struct cgraph_edge *
! record_call (caller, callee)
tree caller, callee;
{
return create_edge (cgraph_node (caller), cgraph_node (callee));
--- 145,152 ----
/* Record call from CALLER to CALLEE */
! struct cgraph_edge *
! cgraph_record_call (caller, callee)
tree caller, callee;
{
return create_edge (cgraph_node (caller), cgraph_node (callee));
*************** cgraph_calls_p (caller_decl, callee_decl
*** 220,285 ****
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;
- {
- /* 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;
- }
-
- /* Create cgraph edges for function calles via BODY. */
-
- void
- cgraph_create_edges (decl, body)
- tree decl;
- tree body;
- {
- walk_tree (&body, record_call_1, decl, NULL);
- }
-
- /* Analyze function once it is parsed. Set up the local information
- available - create cgraph edges for function calles via BODY. */
-
- void
- cgraph_finalize_function (decl, body)
- 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);
- }
-
/* Dump the callgraph. */
void
--- 175,180 ----
*************** dump_cgraph (f)
*** 314,577 ****
IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
fprintf (f, "\n");
}
- }
-
- static struct cgraph_node *queue = NULL;
-
- /* 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;
- {
- 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;
- }
- }
- }
-
- /* Analyze the whole compilation unit once it is parsed completely. */
-
- void
- cgraph_finalize_compilation_unit ()
- {
- struct cgraph_node *node;
- struct cgraph_edge *edge;
-
- /* Collect entry points to the unit. */
-
- if (!quiet_flag)
- fprintf (stderr, "\n\nUnit entry points:");
-
- for (node = cgraph_nodes; node; node = node->next)
- {
- 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);
- }
- }
-
- /* 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;
-
- for (node2 = node->nested; node2; node2 = node2->next_nested)
- if (!node2->reachable)
- cgraph_mark_needed_node (node2, 0);
- }
-
- 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));
-
- 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:");
-
- 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 ();
- }
-
- /* Figure out what functions we want to assemble. */
-
- static void
- cgraph_mark_functions_to_output ()
- {
- struct cgraph_node *node;
-
- /* Figure out functions we want to assemble. */
- for (node = cgraph_nodes; node; node = node->next)
- {
- 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;
- }
- }
-
- /* 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 ()
- {
- struct cgraph_node *node, *node2;
- struct cgraph_node **stack =
- xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
- struct cgraph_node **order =
- xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
- int stack_size = 0;
- int order_pos = 0;
- struct cgraph_edge *edge, last;
- int i;
-
- cgraph_mark_functions_to_output ();
-
- /* We have to deal with cycles nicely, so use depth first traversal
- 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 trought inlined
- functions. */
- for (node = cgraph_nodes; node; node = node->next)
- node->aux = NULL;
- for (node = cgraph_nodes; node; node = node->next)
- if (node->output && !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;
- }
- }
- }
- 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 (stack);
- free (order);
- }
-
- /* Perform simple optimizations based on callgraph. */
-
- void
- cgraph_optimize ()
- {
- struct cgraph_node *node;
- bool changed = true;
- struct cgraph_edge *edge;
-
- 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)
- {
- changed = false;
- for (node = cgraph_nodes; node; node = node->next)
- {
- if (!node->needed)
- continue;
-
- for (edge = node->callees; edge; edge = edge->next_callee)
- if (!edge->callee->needed)
- changed = edge->callee->needed = true;
- }
- }
- cgraph_expand_functions ();
}
--- 209,212 ----
Index: gcc/cgraph.h
===================================================================
RCS file: gcc/cgraph.h
diff -N gcc/cgraph.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- gcc/cgraph.h 22 Feb 2003 00:58:00 -0000
***************
*** 0 ****
--- 1,80 ----
+ /* Callgraph handling code.
+ Copyright (C) 2003 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. */
+
+ #ifndef GCC_CGRAPH_H
+ #define GCC_CGRAPH_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;
+ };
+
+ struct cgraph_node *cgraph_nodes;
+ int cgraph_n_nodes;
+
+ /* In cgraph.c */
+ void dump_cgraph PARAMS ((FILE *));
+ void cgraph_remove_call PARAMS ((tree, tree));
+ struct cgraph_edge *cgraph_record_call PARAMS ((tree, tree));
+ struct cgraph_node *cgraph_node PARAMS ((tree decl));
+ bool cgraph_calls_p PARAMS ((tree, tree));
+
+ /* In cgraphunit.c */
+ void cgraph_finalize_function PARAMS ((tree, tree));
+ void cgraph_finalize_compilation_unit PARAMS ((void));
+ void cgraph_create_edges PARAMS ((tree, tree));
+ void cgraph_optimize PARAMS ((void));
+ void cgraph_mark_needed_node PARAMS ((struct cgraph_node *, int));
+
+ #endif /* GCC_CGRAPH_H */
Index: gcc/cgraphunit.c
===================================================================
RCS file: gcc/cgraphunit.c
diff -N gcc/cgraphunit.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- gcc/cgraphunit.c 22 Feb 2003 00:58:00 -0000
***************
*** 0 ****
--- 1,360 ----
+ /* Callgraph handling code.
+ Copyright (C) 2003 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"
+
+ 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 tree record_call_1 PARAMS ((tree *, int *, void *));
+
+ /* Analyze function once it is parsed. Set up the local information
+ available - create cgraph edges for function calles via BODY. */
+
+ void
+ cgraph_finalize_function (decl, body)
+ 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);
+ }
+
+ static struct cgraph_node *queue = NULL;
+
+ /* 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;
+ {
+ 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;
+ }
+ }
+ }
+
+ /* 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;
+ {
+ /* 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;
+ cgraph_record_call (data, decl);
+ walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
+ *walk_subtrees = 0;
+ }
+ }
+ return NULL;
+ }
+
+ /* Create cgraph edges for function calles via BODY. */
+
+ void
+ cgraph_create_edges (decl, body)
+ tree decl;
+ tree body;
+ {
+ walk_tree (&body, record_call_1, decl, NULL);
+ }
+
+ /* Analyze the whole compilation unit once it is parsed completely. */
+
+ void
+ cgraph_finalize_compilation_unit ()
+ {
+ struct cgraph_node *node;
+ struct cgraph_edge *edge;
+
+ /* Collect entry points to the unit. */
+
+ if (!quiet_flag)
+ fprintf (stderr, "\n\nUnit entry points:");
+
+ for (node = cgraph_nodes; node; node = node->next)
+ {
+ 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);
+ }
+ }
+
+ /* 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;
+
+ for (node2 = node->nested; node2; node2 = node2->next_nested)
+ if (!node2->reachable)
+ cgraph_mark_needed_node (node2, 0);
+ }
+
+ 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));
+
+ 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:");
+
+ 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 ();
+ }
+
+ /* Figure out what functions we want to assemble. */
+
+ static void
+ cgraph_mark_functions_to_output ()
+ {
+ struct cgraph_node *node;
+
+ /* Figure out functions we want to assemble. */
+ for (node = cgraph_nodes; node; node = node->next)
+ {
+ 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;
+ }
+ }
+
+ /* 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 ()
+ {
+ struct cgraph_node *node, *node2;
+ struct cgraph_node **stack =
+ xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
+ struct cgraph_node **order =
+ xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
+ int stack_size = 0;
+ int order_pos = 0;
+ struct cgraph_edge *edge, last;
+ int i;
+
+ cgraph_mark_functions_to_output ();
+
+ /* We have to deal with cycles nicely, so use depth first traversal
+ 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 trought inlined
+ functions. */
+ for (node = cgraph_nodes; node; node = node->next)
+ node->aux = NULL;
+ for (node = cgraph_nodes; node; node = node->next)
+ if (node->output && !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;
+ }
+ }
+ }
+ 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 (stack);
+ free (order);
+ }
+
+ /* Perform simple optimizations based on callgraph. */
+
+ void
+ cgraph_optimize ()
+ {
+ struct cgraph_node *node;
+ bool changed = true;
+ struct cgraph_edge *edge;
+
+ 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)
+ {
+ changed = false;
+ for (node = cgraph_nodes; node; node = node->next)
+ {
+ if (!node->needed)
+ continue;
+
+ for (edge = node->callees; edge; edge = edge->next_callee)
+ if (!edge->callee->needed)
+ changed = edge->callee->needed = true;
+ }
+ }
+ cgraph_expand_functions ();
+ }
Index: gcc/tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.44
diff -c -3 -p -r1.44 tree-inline.c
*** gcc/tree-inline.c 12 Feb 2003 21:48:57 -0000 1.44
--- gcc/tree-inline.c 22 Feb 2003 00:58:00 -0000
*************** Boston, MA 02111-1307, USA. */
*** 37,42 ****
--- 37,43 ----
#include "hashtab.h"
#include "splay-tree.h"
#include "langhooks.h"
+ #include "cgraph.h"
/* This should be eventually be generalized to other languages, but
this would require a shared function-as-trees infrastructure. */
Index: gcc/tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.382
diff -c -3 -p -r1.382 tree.h
*** gcc/tree.h 20 Feb 2003 17:51:39 -0000 1.382
--- gcc/tree.h 22 Feb 2003 00:58:01 -0000
*************** extern const char *dump_flag_name PARAMS
*** 3156,3171 ****
/* Assign the RTX to declaration. */
extern void set_decl_rtl PARAMS ((tree, rtx));
-
- /* In callgraph.c */
- void cgraph_finalize_function PARAMS ((tree, tree));
- void cgraph_finalize_compilation_unit PARAMS ((void));
- void cgraph_create_edges PARAMS ((tree, tree));
- void dump_cgraph PARAMS ((FILE *));
- void cgraph_optimize PARAMS ((void));
- void cgraph_remove_call PARAMS ((tree, tree));
- bool cgraph_calls_p PARAMS ((tree, tree));
-
/* Redefine abort to report an internal error w/o coredump, and
reporting the location of the error in the source file. This logic
--- 3156,3161 ----