This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Enhanced nested functions lowering pass


Hi Richard,

You may recall that I already submitted an equivalent patch last September and 
you rejected it: http://gcc.gnu.org/ml/gcc-patches/2005-09/msg00862.html .
I'm essentially resubmitting it and asking you to reconsider your position.

The goal is to avoid commiting local variables referenced by nested functions 
to the "nonlocal frame structure" too early because that cannot be undone by 
subsequent passes as the structure is addressable.  That would be very useful 
for languages that make heavy use of nested functions like Ada.

You rejected it because this requires conducting reachability analysis during 
the pass and you argued that this doesn't belong there.  You suggested to 
either reorder the passes or to export some stuff from the cgraph machinery.

While I didn't spend dozens of hours on it, the first suggestion would appear 
to lead to a more intricate compiler to me: we would have to deal with nested 
functions farther in the pass pipeline and I'm not sure people would be very
enthusiastic about the idea even if that helps Ada. :-)

As for your second suggestion, it would boil down to exporting exactly one 
small function.  While that would certainly make sense, tree-nested.c already 
contains a custom tree walking engine tailored to its needs and I don't think 
one small function matters much.

Bootstrapped/regtested on x86_64-suse-linux.


2006-03-18  Eric Botcazou  <ebotcazou@adacore.com>

	* tree-nested.c (nesting_info): New fields 'next_reachable'
	and 'reachable'.
	(discard_unreachable): New global variable.
	(ni_map): Likewise.
	(ni_hash): New function.
	(ni_eq): Likewise.
	(get_frame_type): Update comment about addressability.
	(walk_all_functions): Check reachability of functions.
	(create_nesting_tree): Populate ni_map.
	(reachable_queue): New global variable.
	(mark_reachable_function_1): New function.
	(mark_reachable_functions_1): Likewise.
	(mark_reachable_functions): Likewise.
	(convert_all_function_calls): Check reachability of functions.
	(finalize_nesting_tree): Likewise.
	(unnest_nesting_tree_1): Remove unreachable nested functions
	from the callgraph.
	(lower_nested_functions): Initialize and destroy ni_map.
	Set discard_unreachable based on the optimization level.
	Invoke mark_reachable_functions if discard_unreachable is true.


-- 
Eric Botcazou
Index: tree-nested.c
===================================================================
--- tree-nested.c	(revision 112130)
+++ tree-nested.c	(working copy)
@@ -88,7 +88,8 @@ struct nesting_info GTY ((chain_next ("%
   struct nesting_info *outer;
   struct nesting_info *inner;
   struct nesting_info *next;
-  
+  struct nesting_info *next_reachable;
+
   htab_t GTY ((param_is (struct var_map_elt))) field_map;
   htab_t GTY ((param_is (struct var_map_elt))) var_map;
   bitmap suppress_expansion;
@@ -104,8 +105,40 @@ struct nesting_info GTY ((chain_next ("%
 
   bool any_parm_remapped;
   bool any_tramp_created;
+  bool reachable;
 };
 
+/* Whether to discard unreachable nested functions during this pass.
+   If this is set to false, the pass will not differentiate objects
+   referenced by a reachable inner function from objects referenced
+   by an unreachable inner function: both will end up being members
+   of the "nonlocal frame struct" after the pass and not standalone
+   objects anymore.  That means they will be allocated in memory
+   since the "nonlocal frame struct" is always addressable.  */
+
+static bool discard_unreachable;
+
+#define IS_UNREACHABLE(ni) (discard_unreachable && !(ni)->reachable)
+
+/* Hash table used to look up nesting_info from nesting_info->context.  */
+
+static htab_t ni_map;
+
+/* Hashing and equality functions for ni_map.  */
+
+static hashval_t
+ni_hash (const void *p)
+{
+  const struct nesting_info *i = p;
+  return (hashval_t) DECL_UID (i->context);
+}
+
+static int
+ni_eq (const void *p1, const void *p2)
+{
+  const struct nesting_info *i1 = p1, *i2 = p2;
+  return DECL_UID (i1->context) == DECL_UID (i2->context);
+}
 
 /* Hashing and equality functions for nesting_info->var_map.  */
 
@@ -225,12 +258,8 @@ get_frame_type (struct nesting_info *inf
       info->frame_type = type;
       info->frame_decl = create_tmp_var_for (info, type, "FRAME");
 
-      /* ??? Always make it addressable for now, since it is meant to
-	 be pointed to by the static chain pointer.  This pessimizes
-	 when it turns out that no static chains are needed because
-	 the nested functions referencing non-local variables are not
-	 reachable, but the true pessimization is to create the non-
-	 local frame structure in the first place.  */
+      /* It is always addressable since it will be pointed to
+	 by the static chain pointer.  */
       TREE_ADDRESSABLE (info->frame_decl) = 1;
     }
   return type;
@@ -659,14 +688,15 @@ walk_function (walk_tree_fn callback, st
 static void
 walk_all_functions (walk_tree_fn callback, struct nesting_info *root)
 {
-  do
+  for (; root; root = root->next)
     {
+      if (IS_UNREACHABLE (root))
+	continue;
+
       if (root->inner)
 	walk_all_functions (callback, root->inner);
       walk_function (callback, root);
-      root = root->next;
     }
-  while (root);
 }
 
 /* We have to check for a fairly pathological case.  The operands of function
@@ -717,12 +747,17 @@ check_for_nested_with_variably_modified 
 static struct nesting_info *
 create_nesting_tree (struct cgraph_node *cgn)
 {
+  struct nesting_info **slot;
   struct nesting_info *info = GGC_CNEW (struct nesting_info);
   info->field_map = htab_create_ggc (7, var_map_hash, var_map_eq, ggc_free);
   info->var_map = htab_create_ggc (7, var_map_hash, var_map_eq, ggc_free);
   info->suppress_expansion = BITMAP_GGC_ALLOC ();
   info->context = cgn->decl;
 
+  slot = (struct nesting_info **) htab_find_slot (ni_map, info, INSERT);
+  gcc_assert (*slot == NULL);
+  *slot = info;
+
   for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
     {
       struct nesting_info *sub = create_nesting_tree (cgn);
@@ -739,6 +774,84 @@ create_nesting_tree (struct cgraph_node 
   return info;
 }
 
+/* Queue of reachable nested functions to be analyzed.  */
+
+static struct nesting_info *reachable_queue;
+
+/* Mark FNDECL as reachable if it is not already and add it to the queue.  */
+
+static void
+mark_reachable_function_1 (tree fndecl)
+{
+  struct nesting_info dummy;
+  struct nesting_info *info;
+  struct nesting_info **slot;
+
+  dummy.context = fndecl;
+  slot = (struct nesting_info **) htab_find_slot (ni_map, &dummy, NO_INSERT);
+  gcc_assert (slot != NULL);
+  info = *slot;
+
+  if (!info->reachable)
+    {
+      info->reachable = true;
+      info->next_reachable = reachable_queue;
+      reachable_queue = info;
+    }
+}
+
+/* Called via walk_function+walk_tree, mark the nested functions
+   that are reachable from TP.  */
+
+static tree
+mark_reachable_functions_1 (tree *tp, int *walk_subtrees, void *data)
+{
+  struct walk_stmt_info *wi = data;
+  tree t = *tp, decl;
+
+  *walk_subtrees = 0;
+  switch (TREE_CODE (t))
+    {
+    case FDESC_EXPR:
+    case ADDR_EXPR:
+      decl = TREE_OPERAND (t, 0);
+      if (TREE_CODE (decl) == FUNCTION_DECL && decl_function_context (decl))
+	mark_reachable_function_1 (decl);
+      break;
+
+    case CALL_EXPR:
+      decl = get_callee_fndecl (t);
+      if (decl && decl_function_context (decl))
+	mark_reachable_function_1 (decl);
+
+      walk_tree (&TREE_OPERAND (t, 1), mark_reachable_functions_1, wi, NULL);
+      break;
+
+    default:
+      if (!IS_TYPE_OR_DECL_P (t))
+	*walk_subtrees = 1;
+      break;
+    }
+
+  return NULL_TREE;
+}
+
+/* Find out which nested functions are reachable from ROOT.  */
+
+static void
+mark_reachable_functions (struct nesting_info *root)
+{
+  root->reachable = true;
+  reachable_queue = root;
+
+  while (reachable_queue)
+    {
+      struct nesting_info *i = reachable_queue;
+      reachable_queue = reachable_queue->next_reachable;
+      walk_function (mark_reachable_functions_1, i);
+    }
+}
+  
 /* Return an expression computing the static chain for TARGET_CONTEXT
    from INFO->CONTEXT.  Insert any necessary computations before TSI.  */
 
@@ -1664,8 +1777,11 @@ convert_call_expr (tree *tp, int *walk_s
 static void
 convert_all_function_calls (struct nesting_info *root)
 {
-  do
+  for (; root; root = root->next)
     {
+      if (IS_UNREACHABLE (root))
+	continue;
+
       if (root->inner)
 	convert_all_function_calls (root->inner);
 
@@ -1677,10 +1793,7 @@ convert_all_function_calls (struct nesti
 	DECL_NO_STATIC_CHAIN (root->context) = 1;
       else
 	gcc_assert (!DECL_NO_STATIC_CHAIN (root->context));
-
-      root = root->next;
     }
-  while (root);
 }
 
 /* Do "everything else" to clean up or complete state collected by the
@@ -1817,14 +1930,15 @@ finalize_nesting_tree_1 (struct nesting_
 static void
 finalize_nesting_tree (struct nesting_info *root)
 {
-  do
+  for (; root; root = root->next)
     {
+      if (IS_UNREACHABLE (root))
+	continue;
+
       if (root->inner)
 	finalize_nesting_tree (root->inner);
       finalize_nesting_tree_1 (root);
-      root = root->next;
     }
-  while (root);
 }
 
 /* Unnest the nodes and pass them to cgraph.  */
@@ -1838,8 +1952,13 @@ unnest_nesting_tree_1 (struct nesting_in
      We also delay finalizing of these functions up to this point.  */
   if (node->origin)
     {
-       cgraph_unnest_node (cgraph_node (root->context));
-       cgraph_finalize_function (root->context, true);
+      if (IS_UNREACHABLE (root))
+	cgraph_remove_node (node);
+      else
+	{
+	  cgraph_unnest_node (node);
+	  cgraph_finalize_function (root->context, true);
+	}
     }
 }
 
@@ -1889,7 +2008,13 @@ lower_nested_functions (tree fndecl)
   if (!cgn->nested)
     return;
 
+  /* Do not discard unreachable nested functions at -O0.  */
+  discard_unreachable = (optimize != 0);
+
+  ni_map = htab_create (11, ni_hash, ni_eq, NULL);
   root = create_nesting_tree (cgn);
+  if (discard_unreachable)
+    mark_reachable_functions (root);
   walk_all_functions (convert_nonlocal_reference, root);
   walk_all_functions (convert_local_reference, root);
   walk_all_functions (convert_nl_goto_reference, root);
@@ -1899,6 +2024,7 @@ lower_nested_functions (tree fndecl)
   unnest_nesting_tree (root);
   free_nesting_tree (root);
   root = NULL;
+  htab_delete (ni_map);
 }
 
 #include "gt-tree-nested.h"

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]