[PATCH] Greatly speed up finish_struct

[Stan Shebs <shebs at apple dot com>]

In c-decl.c, pushdecl and finish_struct use a count of incomplete
decls to decide whether to go back and look for other decls that can
be completed once a struct is completed.  However, the current
algorithm scans all(!) decls in the current binding level, which is
spectacularly slow if you have so much as a "typedef struct foo bar"
followed by lots of regular struct definitions.  In the case of
Mac headers, there are some incompletes, about a thousand structs,
and many thousands of declarations, and finish_struct would actually
appear at the top of the profile.

Over a year ago, Turly posted a patch to use a list of incompletes
instead (http://gcc.gnu.org/ml/gcc-patches/2001-03/msg00916.html),
but it appears not to have been noticed at the time.  I've updated
the patch and retested its effect on performance; using SPU (src
repository, utils/spu) with --structs 1000 and a manually-added
incomplete struct typedef, compilation time is cut nearly in half
by this patch.  It also seems to speed up bootstrapping on GNU/Linux
very slightly (1/2%), but this is probably within the bounds of
measurement error.

OK for mainline and 3.1 branch?  (Technically not a regression,
but a very safe speed win - in use at Apple for a year, plus
bootstrapped on powerpc-apple-darwin and i686-pc-linux-gnu).

Stan

2002-05-31  Stan Shebs  <shebs@apple.com>
            Turly O'Connor  <turly@apple.com>

        * c-decl.c (struct binding_level): Change int field n_incomplete
        to tree list incomplete_list.
        (clear_binding_level): Init field with NULL.
        (pushdecl): Add incomplete type to list.
        (mark_binding_level): Mark the incomplete list.
        (finish_struct): Scan the incomplete list for types instead
        of all decls in the current binding level.

Index: c-decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-decl.c,v
retrieving revision 1.329
diff -p -r1.329 c-decl.c
*** c-decl.c    25 May 2002 22:01:41 -0000      1.329
--- c-decl.c    31 May 2002 12:35:25 -0000
*************** struct binding_level
*** 215,223 ****
      /* Nonzero means make a BLOCK if this level has any subblocks.  */
      char keep_if_subblocks;
  
!     /* Number of decls in `names' that have incomplete
!        structure or union types.  */
!     int n_incomplete;
  
      /* A list of decls giving the (reversed) specified order of parms,
         not including any forward-decls in the parmlist.
--- 215,223 ----
      /* Nonzero means make a BLOCK if this level has any subblocks.  */
      char keep_if_subblocks;
  
!     /* List of decls in `names' that have incomplete structure or
!        union types.  */
!     tree incomplete_list;
  
      /* A list of decls giving the (reversed) specified order of parms,
         not including any forward-decls in the parmlist.
*************** static struct binding_level *global_bind
*** 244,250 ****
  /* Binding level structures are initialized by copying this one.  */
  
  static struct binding_level clear_binding_level
!   = {NULL, NULL, NULL, NULL, NULL, NULL_BINDING_LEVEL, 0, 0, 0, 0, 0, 0,
       NULL};
  
  /* Nonzero means unconditionally make a BLOCK for the next level pushed.  */
--- 244,250 ----
  /* Binding level structures are initialized by copying this one.  */
  
  static struct binding_level clear_binding_level
!   = {NULL, NULL, NULL, NULL, NULL, NULL_BINDING_LEVEL, 0, 0, 0, 0, 0, NULL,
       NULL};
  
  /* Nonzero means unconditionally make a BLOCK for the next level pushed.  */
*************** pushdecl (x)
*** 2392,2398 ****
            b->shadowed = tree_cons (name, oldlocal, b->shadowed);
        }
  
!       /* Keep count of variables in this level with incomplete type.
         If the input is erroneous, we can have error_mark in the type
         slot (e.g. "f(void a, ...)") - that doesn't count as an
         incomplete type.  */
--- 2392,2398 ----
            b->shadowed = tree_cons (name, oldlocal, b->shadowed);
        }
  
!       /* Keep list of variables in this level with incomplete type.
         If the input is erroneous, we can have error_mark in the type
         slot (e.g. "f(void a, ...)") - that doesn't count as an
         incomplete type.  */
*************** pushdecl (x)
*** 2405,2411 ****
            element = TREE_TYPE (element);
          if (TREE_CODE (element) == RECORD_TYPE
              || TREE_CODE (element) == UNION_TYPE)
!           ++b->n_incomplete;
        }
      }
  
--- 2405,2411 ----
            element = TREE_TYPE (element);
          if (TREE_CODE (element) == RECORD_TYPE
              || TREE_CODE (element) == UNION_TYPE)
!           b->incomplete_list = tree_cons (NULL_TREE, x, b->incomplete_list);
        }
      }
  
*************** mark_binding_level (arg)
*** 2880,2885 ****
--- 2880,2886 ----
        ggc_mark_tree (level->blocks);
        ggc_mark_tree (level->this_block);
        ggc_mark_tree (level->parm_order);
+       ggc_mark_tree (level->incomplete_list);
      }
  }
  
*************** finish_struct (t, fieldlist, attributes)
*** 5691,5701 ****
    /* If this structure or union completes the type of any previous
       variable declaration, lay it out and output its rtl.  */
  
!   if (current_binding_level->n_incomplete != 0)
      {
!       tree decl;
!       for (decl = current_binding_level->names; decl; decl = TREE_CHAIN (decl))
!       {
          if (TYPE_MAIN_VARIANT (TREE_TYPE (decl)) == TYPE_MAIN_VARIANT (t)
              && TREE_CODE (decl) != TYPE_DECL)
            {
--- 5692,5705 ----
    /* If this structure or union completes the type of any previous
       variable declaration, lay it out and output its rtl.  */
  
!   if (current_binding_level->incomplete_list != NULL_TREE)
      {
!       tree prev = NULL_TREE;
! 
!       for (x = current_binding_level->incomplete_list; x; x = TREE_CHAIN (x))
!         {
!         tree decl = TREE_VALUE (x);
! 
          if (TYPE_MAIN_VARIANT (TREE_TYPE (decl)) == TYPE_MAIN_VARIANT (t)
              && TREE_CODE (decl) != TYPE_DECL)
            {
*************** finish_struct (t, fieldlist, attributes)
*** 5705,5712 ****
              rest_of_decl_compilation (decl, NULL, toplevel, 0);
              if (! toplevel)
                expand_decl (decl);
!             if (--current_binding_level->n_incomplete == 0)
!               break;
            }
          else if (!COMPLETE_TYPE_P (TREE_TYPE (decl))
                   && TREE_CODE (TREE_TYPE (decl)) == ARRAY_TYPE)
--- 5709,5719 ----
              rest_of_decl_compilation (decl, NULL, toplevel, 0);
              if (! toplevel)
                expand_decl (decl);
!             /* Unlink X from the incomplete list.  */
!             if (prev)
!               TREE_CHAIN (prev) = TREE_CHAIN (x);
!             else
!               current_binding_level->incomplete_list = TREE_CHAIN (x);
            }
          else if (!COMPLETE_TYPE_P (TREE_TYPE (decl))
                   && TREE_CODE (TREE_TYPE (decl)) == ARRAY_TYPE)
*************** finish_struct (t, fieldlist, attributes)
*** 5725,5732 ****
                      if (! toplevel)
                        expand_decl (decl);
                    }
!                 if (--current_binding_level->n_incomplete == 0)
!                   break;
                }
            }
        }
--- 5732,5742 ----
                      if (! toplevel)
                        expand_decl (decl);
                    }
!                 /* Unlink X from the incomplete list.  */
!                 if (prev)
!                   TREE_CHAIN (prev) = TREE_CHAIN (x);
!                 else
!                   current_binding_level->incomplete_list = TREE_CHAIN (x);
                }
            }
        }