RFC: Preserving order of functions and top-level asms via cgraph

[Daniel Jacobowitz <drow at false dot org>]

This has been on the table for ages, but no one's gotten around to doing it. 
I'm attaching a (mostly untested) patch which fixes the simple cases.  For
instance, it causes this test to come out in the expected order:

void func1() { }
asm ("# ASM");
void func2() { }

It doesn't handle variable declarations, and it won't be useful until it
does.  Right now declarations are written to the assembly file early, before
functions are assembled.  Steven pointed out (thank you, Steven) that this
is much easier on the tree-profiling branch, where that is no longer the
case.  So, I'm not going to extend the patch to declarations until that
piece is merged.

In the mean time, any fundamental objections to the approach?

Also, are there any other major reasons why people use -fno-unit-at-a-time,
besides this one?  I would like to see the option go away, and to enable
unit-at-a-time always.  If for no other reason than to simplify the bits of
cgraph which handle it.

Yes, that does incur a measurable (~2% ?) memory and time overhead at -O0. 
Much less than I would have expected, but my measurements were not very
thorough.  Note that C++ already does this, and has for a while.

-- 
Daniel Jacobowitz
CodeSourcery, LLC

Index: c-parser.c
===================================================================
RCS file: /home/drow/rsync/gcc/gcc/gcc/c-parser.c,v
retrieving revision 2.8
diff -u -p -r2.8 c-parser.c
--- c-parser.c	23 Mar 2005 01:35:03 -0000	2.8
+++ c-parser.c	10 Apr 2005 20:07:05 -0000
@@ -1323,12 +1323,8 @@ static void
 c_parser_asm_definition (c_parser *parser)
 {
   tree asm_str = c_parser_simple_asm_expr (parser);
-  /* ??? This only works sensibly in the presence of
-     -fno-unit-at-a-time; file-scope asms really need to be passed to
-     cgraph which needs to preserve the order of functions and
-     file-scope asms.  */
   if (asm_str)
-    assemble_asm (asm_str);
+    cgraph_record_asm (asm_str);
   c_parser_skip_until_found (parser, CPP_SEMICOLON, "expected %<;%>");
 }
 
Index: cgraph.h
===================================================================
RCS file: /home/drow/rsync/gcc/gcc/gcc/cgraph.h,v
retrieving revision 1.46
diff -u -p -r1.46 cgraph.h
--- cgraph.h	20 Mar 2005 15:27:18 -0000	1.46
+++ cgraph.h	10 Apr 2005 19:24:10 -0000
@@ -107,6 +107,9 @@ struct cgraph_node GTY((chain_next ("%h.
   
   /* Unique id of the node.  */
   int uid;
+  /* Sequence number of the node.  Set when finalized, not when created.  */
+  int seq;
+  
   /* Set when function must be output - it is externally visible
      or its address is taken.  */
   bool needed;
@@ -194,6 +197,7 @@ void cgraph_unnest_node (struct cgraph_n
 
 /* In cgraphunit.c  */
 bool cgraph_assemble_pending_functions (void);
+void cgraph_record_asm (tree);
 void cgraph_finalize_function (tree, bool);
 void cgraph_finalize_compilation_unit (void);
 void cgraph_create_edges (struct cgraph_node *, tree);
Index: cgraphunit.c
===================================================================
RCS file: /home/drow/rsync/gcc/gcc/gcc/cgraphunit.c,v
retrieving revision 1.96
diff -u -p -r1.96 cgraphunit.c
--- cgraphunit.c	22 Mar 2005 20:53:22 -0000	1.96
+++ cgraphunit.c	10 Apr 2005 20:14:16 -0000
@@ -189,6 +189,8 @@ Software Foundation, 59 Temple Place - S
 #include "intl.h"
 #include "function.h"
 #include "tree-gimple.h"
+#include "output.h"
+#include "vec.h"
 
 #define INSNS_PER_CALL 10
 
@@ -215,6 +217,23 @@ static struct pointer_set_t *visited_nod
 
 static FILE *cgraph_dump_file;
 
+/* Records of any top-level asm statements we encounter, so that we can
+   preserve their ordering with respect to functions.  */
+
+typedef struct cgraph_asm_node
+{
+  int seq;
+  tree asm_string;
+} cgraph_asm_node;
+
+DEF_VEC_GC_O(cgraph_asm_node);
+static GTY(()) VEC(cgraph_asm_node) *cgraph_asms;
+
+/* Next sequence number for constructs whose order we will preserve if any
+   top-level asm statements are seen.  */
+
+static GTY(()) int cgraph_global_seq;
+
 /* Determine if function DECL is needed.  That is, visible to something
    either outside this translation unit, something magic in the system
    configury, or (if not doing unit-at-a-time) to something we havn't
@@ -310,6 +329,25 @@ cgraph_assemble_pending_functions (void)
   return output;
 }
 
+/* We have encounter a top-level asm statement.  Queue or emit it at
+   the whim of the logic in effect.  */
+
+void
+cgraph_record_asm (tree asm_string)
+{
+  struct cgraph_asm_node ordering;
+
+  if (!flag_unit_at_a_time)
+    {
+      assemble_asm (asm_string);
+      return;
+    }
+
+  ordering.seq = cgraph_global_seq++;
+  ordering.asm_string = asm_string;
+  VEC_safe_push (cgraph_asm_node, cgraph_asms, &ordering);
+}
+
 /* 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
    the garbage collector run at the moment.  We would need to either create
@@ -387,6 +425,10 @@ cgraph_finalize_function (tree decl, boo
       cgraph_decide_inlining_incrementally (node);
     }
 
+  /* If unit at a time, record a sequence number.  */
+  if (flag_unit_at_a_time)
+    node->seq = cgraph_global_seq++;
+
   if (decide_is_function_needed (node, decl))
     cgraph_mark_needed_node (node);
 
@@ -1664,17 +1706,22 @@ cgraph_inline_p (struct cgraph_edge *e, 
   return !e->inline_failed;
 }
 
+/* Comparison function for qsort.  Sort the highest sequence number
+   to the front.  */
 
+static int
+cgraph_compare_seq (const void *l, const void *r)
+{
+  const struct cgraph_node *lhs = l, *rhs = r;
+  if (lhs->seq < rhs->seq)
+    return 1;
+  else if (lhs->seq > rhs->seq)
+    return -1;
+  else
+    return 0;
+}
 
-/* 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 across the callgraph.  Use a stack to get smaller distance
-   between a function and its callees (later we may choose to use a more
-   sophisticated algorithm for function reordering; we will likely want
-   to use subsections to make the output functions appear in top-down
-   order).  */
+/* Expand all functions that must be output.  */
 
 static void
 cgraph_expand_all_functions (void)
@@ -1684,9 +1731,30 @@ cgraph_expand_all_functions (void)
     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
   int order_pos = 0, new_order_pos = 0;
   int i;
+  int n_asms = VEC_length (cgraph_asm_node, cgraph_asms);
+  int cur_asm = 0;
 
-  order_pos = cgraph_postorder (order);
-  gcc_assert (order_pos == cgraph_n_nodes);
+  if (n_asms > 0)
+    {
+      for (i = cgraph_n_nodes, node = cgraph_nodes; node; node = node->next)
+	order[--i] = node;
+      gcc_assert (i == 0);
+      qsort (order, cgraph_n_nodes, sizeof (struct cgraph_node *),
+	     cgraph_compare_seq);
+      order_pos = cgraph_n_nodes;
+    }
+  else
+    {
+      /* Attempt to topologically sort the nodes so function is output
+	 when all called functions are already assembled to allow data
+	 to be propagated across the callgraph.  Later we may choose
+	 to use a more sophisticated algorithm for function
+	 reordering; we will likely want to use subsections to make
+	 the output functions appear in top-down order.  */
+
+      order_pos = cgraph_postorder (order);
+      gcc_assert (order_pos == cgraph_n_nodes);
+    }
 
   /* Garbage collector may remove inline clones we eliminate during
      optimization.  So we must be sure to not reference them.  */
@@ -1694,6 +1762,7 @@ cgraph_expand_all_functions (void)
     if (order[i]->output)
       order[new_order_pos++] = order[i];
 
+  cur_asm = 0;
   for (i = new_order_pos - 1; i >= 0; i--)
     {
       node = order[i];
@@ -1701,9 +1770,29 @@ cgraph_expand_all_functions (void)
 	{
 	  gcc_assert (node->reachable);
 	  node->output = 0;
+
+	  while (cur_asm < n_asms)
+	    {
+	      struct cgraph_asm_node *this_asm;
+	      this_asm = VEC_index (cgraph_asm_node, cgraph_asms, cur_asm);
+	      if (this_asm->seq > node->seq)
+		break;
+	      assemble_asm (this_asm->asm_string);
+	      cur_asm++;
+	    }
+
 	  cgraph_expand_function (node);
 	}
     }
+
+  while (cur_asm < n_asms)
+    {
+      struct cgraph_asm_node *this_asm;
+      this_asm = VEC_index (cgraph_asm_node, cgraph_asms, cur_asm);
+      assemble_asm (this_asm->asm_string);
+      cur_asm++;
+    }
+
   free (order);
 }
 
Index: cp/parser.c
===================================================================
RCS file: /home/drow/rsync/gcc/gcc/gcc/cp/parser.c,v
retrieving revision 1.325
diff -u -p -r1.325 parser.c
--- cp/parser.c	22 Mar 2005 23:11:21 -0000	1.325
+++ cp/parser.c	10 Apr 2005 20:11:10 -0000
@@ -34,8 +34,7 @@
 #include "flags.h"
 #include "diagnostic.h"
 #include "toplev.h"
-#include "output.h"
-#include "target.h"
+#include "cgraph.h"
 
 
 /* The lexer.  */
@@ -10487,7 +10486,7 @@ cp_parser_asm_definition (cp_parser* par
 	}
     }
   else
-    assemble_asm (string);
+    cgraph_record_asm (string);
 }
 
 /* Declarators [gram.dcl.decl] */