[PATCH] Fix pb in nested function decomposition pass

[Eric Botcazou <ebotcazou at adacore dot com>]

Hi,

The following testcase triggers an ICE with GCC 4.x:

with Interfaces.C_Streams;
with System.Storage_Elements;

procedure p is

  generic
    type Element_Type is private;
  package q is

    Bytes : constant Interfaces.C_Streams.size_t :=
              Element_Type'Max_Size_In_Storage_Elements;

    procedure proc;
  end;

  package body q is

    Zeroes : System.Storage_Elements.Storage_Array :=
               (1 .. System.Storage_Elements.Storage_Offset (Bytes) => 0);

    procedure proc is
      v : System.Storage_Elements.Storage_Element;
    begin
      v := Zeroes (1);
     end;
  end;

  package my_q is new q (element_type => integer);

begin
  null;
end;


The failure mode is as follows: a local variable (Zeroes, an array) in the 
parent function is referenced in a child function; as a consequence, the 
local variable is added to the "nonlocal frame structure" whose address will 
be the value of the static chain pointer.  However the following property is 
true for the parent function: no reachable child functions need a static 
chain (i.e. the above child function is not reachable).  So the address of 
the "nonlocal frame structure" is never taken and it is therefore not marked 
as addressable, while it contains an array that was addressable.  The 
compiler ICEs in the RTL expander when trying to access the array in the 
structure because the "nonlocal frame structure" has been put in a register.

A one-liner fix is to always mark the "nonlocal frame structure" as 
addressable: since it is intended to be pointed to by the static chain 
pointer, that's no big deal.  However, while this would probably be good 
enough for C, I think this would unnecessarily pessimize for Ada because a 
bunch of nested functions are created when a generic package is instantiated 
in a procedure and not all of them are always used; so unnecessary "nonlocal 
frame structures" might be created and allocated on the stack.

So I'm proposing the following fix instead: walk beforehand the family of 
nested functions and find out which ones are reachable; then only mark the 
local variables of the parent function that are referenced in a *reachable* 
child function.

The drawback is an additional walk of the family of functions (the pass 
already uses 6 walks).  But I think it is recouped (at least for Ada) by 
limiting the subsequent walks to the reachable nested functions.  The patch 
also merges the walks intended to fix up the trampoline and the direct calls.

Bootstrapped/regtested on i586-suse-linux.  OK for mainline?

:ADDPATCH tree middle-end:


2005-09-14  Eric Botcazou  <ebotcazou@adacore.com>

	* tree-nested.c (nesting_info): New fields 'next_reachable'
	and 'reachable'.
        (ni_map): New global variable.
        (ni_hash): New function.
        (ni_eq): Likewise.
        (walk_all_functions): Rename to walk_reachable_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_tramp_reference): Merge into...
	(convert_call_expr): Merge into...
	(convert_function_calls_1): ...here.
        (convert_all_function_calls): Rename to convert_function_calls.
	Check reachability of functions.
	Update according to above merge.
        (finalize_nesting_tree_1): Reuse 'node' variable.
        (finalize_nesting_tree): Check reachability of functions.
        Remove unreachable nested functions from the callgraph.
        (lower_nested_functions): Initialize and destroy ni_map.
        Update according to renaming of walk_all_functions and
	convert_all_function_calls.


-- 
Eric Botcazou

Index: tree-nested.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-nested.c,v
retrieving revision 2.30
diff -u -p -r2.30 tree-nested.c
--- tree-nested.c	2 Sep 2005 12:40:52 -0000	2.30
+++ tree-nested.c	13 Sep 2005 22:08:00 -0000
@@ -87,8 +87,9 @@ struct nesting_info GTY ((chain_next ("%
 {
   struct nesting_info *outer;
   struct nesting_info *inner;
+  struct nesting_info *next_reachable;
   struct nesting_info *next;
-  
+
   htab_t GTY ((param_is (struct var_map_elt))) var_map;
   tree context;
   tree new_local_var_chain;
@@ -100,8 +101,28 @@ struct nesting_info GTY ((chain_next ("%
 
   bool any_parm_remapped;
   bool any_tramp_created;
+  bool 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.  */
 
@@ -635,19 +656,20 @@ walk_function (walk_tree_fn callback, st
   walk_stmts (&wi, &DECL_SAVED_TREE (info->context));
 }
 
-/* Similarly for ROOT and all functions nested underneath, depth first.  */
+/* Similarly for ROOT and its reachable nested functions, depth first.  */
     
 static void
-walk_all_functions (walk_tree_fn callback, struct nesting_info *root)
+walk_reachable_functions (walk_tree_fn callback, struct nesting_info *root)
 {
-  do
+  for (; root; root = root->next)
     {
+      if (!root->reachable)
+	continue;
+
       if (root->inner)
-	walk_all_functions (callback, root->inner);
+	walk_reachable_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
@@ -698,10 +720,15 @@ 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_calloc (1, sizeof (*info));
   info->var_map = htab_create_ggc (7, var_map_hash, var_map_eq, ggc_free);
   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);
@@ -718,6 +745,83 @@ 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 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.  */
 
@@ -1173,11 +1277,13 @@ convert_nl_goto_receiver (tree *tp, int 
 }
 
 /* Called via walk_function+walk_tree, rewrite all references to addresses
-   of nested functions that require the use of trampolines.  The rewrite
-   will involve a reference a trampoline generated for the occasion.  */
+   of nested functions that require the use of trampolines (the rewrite
+   will involve a reference to a trampoline generated for the occasion) 
+   and all CALL_EXPRs that reference nested functions to make sure that
+   the static chain is set up properly for the call.  */
 
 static tree
-convert_tramp_reference (tree *tp, int *walk_subtrees, void *data)
+convert_function_calls_1 (tree *tp, int *walk_subtrees, void *data)
 {
   struct walk_stmt_info *wi = data;
   struct nesting_info *info = wi->info, *i;
@@ -1233,52 +1339,21 @@ convert_tramp_reference (tree *tp, int *
       break;
 
     case CALL_EXPR:
-      /* Only walk call arguments, lest we generate trampolines for
-	 direct calls.  */
-      walk_tree (&TREE_OPERAND (t, 1), convert_tramp_reference, wi, NULL);
-      break;
-
-    default:
-      if (!IS_TYPE_OR_DECL_P (t))
-	*walk_subtrees = 1;
-      break;
-    }
-
-  return NULL_TREE;
-}
-
-/* Called via walk_function+walk_tree, rewrite all CALL_EXPRs that 
-   reference nested functions to make sure that the static chain is
-   set up properly for the call.  */
-
-static tree
-convert_call_expr (tree *tp, int *walk_subtrees, void *data)
-{
-  struct walk_stmt_info *wi = data;
-  struct nesting_info *info = wi->info;
-  tree t = *tp, decl, target_context;
-
-  *walk_subtrees = 0;
-  switch (TREE_CODE (t))
-    {
-    case CALL_EXPR:
       decl = get_callee_fndecl (t);
-      if (!decl)
-	break;
-      target_context = decl_function_context (decl);
-      if (target_context && !DECL_NO_STATIC_CHAIN (decl))
-	TREE_OPERAND (t, 2)
-	  = get_static_chain (info, target_context, &wi->tsi);
-      break;
+      if (decl)
+	{
+	  target_context = decl_function_context (decl);
+	  if (target_context && !DECL_NO_STATIC_CHAIN (decl))
+	    TREE_OPERAND (t, 2)
+	      = get_static_chain (info, target_context, &wi->tsi);
+	}
 
-    case RETURN_EXPR:
-    case MODIFY_EXPR:
-    case WITH_SIZE_EXPR:
-      /* Only return modify and with_size_expr may contain calls.  */
-      *walk_subtrees = 1;
+      walk_tree (&TREE_OPERAND (t, 1), convert_function_calls_1, wi, NULL);
       break;
 
     default:
+      if (!IS_TYPE_OR_DECL_P (t))
+	*walk_subtrees = 1;
       break;
     }
 
@@ -1290,25 +1365,24 @@ convert_call_expr (tree *tp, int *walk_s
    a nested function actually uses its static chain; if not, remember that.  */
 
 static void
-convert_all_function_calls (struct nesting_info *root)
+convert_function_calls (struct nesting_info *root)
 {
-  do
+  for (; root; root = root->next)
     {
+      if (!root->reachable)
+	continue;
+
       if (root->inner)
-	convert_all_function_calls (root->inner);
+	convert_function_calls (root->inner);
 
-      walk_function (convert_tramp_reference, root);
-      walk_function (convert_call_expr, root);
+      walk_function (convert_function_calls_1, root);
 
       /* If the function does not use a static chain, then remember that.  */
       if (root->outer && !root->chain_decl && !root->chain_field)
 	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
@@ -1444,7 +1518,7 @@ finalize_nesting_tree_1 (struct nesting_
      We also delay finalizing of these functions up to this point.  */
   if (node->origin)
     {
-       cgraph_unnest_node (cgraph_node (root->context));
+       cgraph_unnest_node (node);
        cgraph_finalize_function (root->context, true);
     }
 }
@@ -1452,14 +1526,18 @@ finalize_nesting_tree_1 (struct nesting_
 static void
 finalize_nesting_tree (struct nesting_info *root)
 {
-  do
+  for (; root; root = root->next)
     {
+      if (!root->reachable)
+	{
+	  cgraph_remove_node (cgraph_node (root->context));
+	  continue;
+	}
+
       if (root->inner)
 	finalize_nesting_tree (root->inner);
       finalize_nesting_tree_1 (root);
-      root = root->next;
     }
-  while (root);
 }
 
 /* Free the data structures allocated during this pass.  */
@@ -1495,15 +1573,18 @@ lower_nested_functions (tree fndecl)
   if (!cgn->nested)
     return;
 
+  ni_map = htab_create (11, ni_hash, ni_eq, NULL);
   root = create_nesting_tree (cgn);
-  walk_all_functions (convert_nonlocal_reference, root);
-  walk_all_functions (convert_local_reference, root);
-  walk_all_functions (convert_nl_goto_reference, root);
-  walk_all_functions (convert_nl_goto_receiver, root);
-  convert_all_function_calls (root);
+  mark_reachable_functions (root);
+  walk_reachable_functions (convert_nonlocal_reference, root);
+  walk_reachable_functions (convert_local_reference, root);
+  walk_reachable_functions (convert_nl_goto_reference, root);
+  walk_reachable_functions (convert_nl_goto_receiver, root);
+  convert_function_calls (root);
   finalize_nesting_tree (root);
   free_nesting_tree (root);
   root = NULL;
+  htab_delete (ni_map);
 }
 
 #include "gt-tree-nested.h"