From 91920de0c77c04e03c6f158b9954adb350b09a6d Mon Sep 17 00:00:00 2001 From: hubicka Date: Wed, 19 Feb 2003 10:24:56 +0000 Subject: [PATCH] * cgraph.c (NPREDECESORC, SET_NPREDECESORS): Kill. (cgraph_expand_function): Rewrite. * gcc.dg/funcorder.c: New test. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@63098 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 5 +++ gcc/cgraph.c | 92 +++++++++++++++++++++++----------------- gcc/testsuite/ChangeLog | 4 ++ gcc/testsuite/gcc.dg/funcorder.c | 37 ++++++++++++++++ 4 files changed, 99 insertions(+), 39 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/funcorder.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 22d70924a92..34696c61235 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +Tue Feb 18 23:50:59 CET 2003 Jan Hubicka + + * cgraph.c (NPREDECESORC, SET_NPREDECESORS): Kill. + (cgraph_expand_function): Rewrite. + 2003-02-18 Matt Austern * toplev.c, langhooks.c, langhooks-def.h: Move write_global_declarations from toplev.c to langhooks.c. 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. */ diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 9d41b1af62a..0c352aec172 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +Tue Feb 18 23:28:53 CET 2003 Jan Hubicka + + * gcc.dg/funcorder.c: New test. + 2003-02-18 Kazu Hirata * gcc.c-torture/execute/20030218-1.c: New. diff --git a/gcc/testsuite/gcc.dg/funcorder.c b/gcc/testsuite/gcc.dg/funcorder.c new file mode 100644 index 00000000000..0dec72c7d02 --- /dev/null +++ b/gcc/testsuite/gcc.dg/funcorder.c @@ -0,0 +1,37 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -funit-at-a-time" } */ +/* { dg-final { scan-assembler-not "link_error" } } */ +/* In unit-at-time the functions should be assembled in order + e q t main, so we realize that they are pure. */ + +static int mem; +static int e(void) __attribute__ ((noinline)); +static int q(void) __attribute__ ((noinline)); +static int t(void) __attribute__ ((noinline)); +main() +{ + return t(); +} +static t() +{ + int r,e; + if (mem) + t(); + e=mem; + r=q(); + if (e!=mem) + link_error(); + return r; +} +static int e() +{ + return 0; +} +static int q() +{ + int t=mem,r; + r=e(); + if (t!=mem) + link_error(); + return r; +} -- 2.11.0