diff options
| author | Jan Hubicka <jh@suse.cz> | 2003-02-19 11:24:56 +0100 |
|---|---|---|
| committer | Jan Hubicka <hubicka@gcc.gnu.org> | 2003-02-19 10:24:56 +0000 |
| commit | c001c39bbbd67012dc85d861be94c41a67ee7063 (patch) | |
| tree | c7d690d5f5278e78050af52ff4cb43db39d2106c /gcc/cgraph.c | |
| parent | 8d928fb1404300cdd23a636fd0d7ce70773d4f53 (diff) | |
| download | gcc-c001c39bbbd67012dc85d861be94c41a67ee7063.tar.gz | |
cgraph.c (NPREDECESORC, [...]): Kill.
* cgraph.c (NPREDECESORC, SET_NPREDECESORS): Kill.
(cgraph_expand_function): Rewrite.
* gcc.dg/funcorder.c: New test.
From-SVN: r63098
Diffstat (limited to 'gcc/cgraph.c')
| -rw-r--r-- | gcc/cgraph.c | 92 |
1 files changed, 53 insertions, 39 deletions
diff --git a/gcc/cgraph.c b/gcc/cgraph.c index 5b580491bd1..f1fffcac421 100644 --- a/gcc/cgraph.c +++ b/gcc/cgraph.c @@ -420,11 +420,6 @@ cgraph_finalize_compilation_unit () ggc_collect (); } -/* 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 @@ -476,56 +471,75 @@ cgraph_expand_function (node) static void cgraph_expand_functions () { - struct cgraph_node *node; + 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; - struct cgraph_edge *edge; + 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) + if (node->output && !node->aux) { - 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; + 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; + } + } } - while (1) + for (i = order_pos - 1; i >=0; i--) { - struct cgraph_node *minnode; - while (stack_size) + node = order[i]; + if (node->output) { - 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 (); + node->output = 0; 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; } + free (stack); + free (order); } /* Perform simple optimizations based on callgraph. */ |