PATCH: cp_binding_level reorg

[Devang Patel <dpatel at apple dot com>]

http://gcc.gnu.org/ml/gcc/2002-08/msg01198.html

As Matt pointed out in his message(above),  walk_namespace_r() and 
vtable_decl_p() and
list_length() dominates the cache disturbance.

I have simple fix that knocks these functions from top of the list as 
far as cache
disturbance is concerned.

For a sample C++ program, it improves compile time from 5.11 seconds to 
4.93 seconds.
However using PFE the gain is larger and it is (for same sample 
program) from 0.23 seconds
to 0.16 seconds.

I have bootstrapped it successfully. I am running regression test now. 
OK to commit
if everything goes fine?

-Devang

Index: ChangeLog
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ChangeLog,v
retrieving revision 1.15220
diff -c -3 -p -r1.15220 ChangeLog
*** ChangeLog   21 Aug 2002 01:01:03 -0000      1.15220
--- ChangeLog   21 Aug 2002 23:35:20 -0000
***************
*** 1,3 ****
--- 1,18 ----
+ 2002-08-21  Devang Patel  <dpatel@apple.com>
+       * cp/cp-tree.h: New prototype for walk_vtabls().
+       * cp/decl.c (walk_vtables_r): New function.
+       (struct cp_binding_level): Add new members, namespaces,
+       names_size and vtables.
+       (add_decl_to_level): Add decl in namespaces or vtables
+       chain, if conditions match.
+       (walk_vtables): New function.
+       (walk_namespaces_r): Travers separate namespace chain
+       for namespace decls.
+       (wrapup_globals_for_namespace): Use names_size instead
+       of list_length().
+       * cp/decl2.c (finish_file): Use walk_vtables() instead of
+       walk_globals() to walk vtable decls.
+
  2002-08-20  Devang Patel  <dpatel@apple.com>
        * tree.c (get_qualified_type): Add TYPE_CONTEXT check.

Index: cp/cp-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/cp-tree.h,v
retrieving revision 1.744
diff -c -3 -p -r1.744 cp-tree.h
*** cp/cp-tree.h        9 Aug 2002 19:57:00 -0000       1.744
--- cp/cp-tree.h        21 Aug 2002 23:35:24 -0000
*************** typedef int (*walk_globals_fn)
*** 3723,3728 ****
--- 3723,3731 ----
  extern int walk_globals                         PARAMS 
((walk_globals_pred,
                                                       walk_globals_fn,
                                                       void *));
+ extern int walk_vtables                         PARAMS 
((walk_globals_pred,
+                                                        
walk_globals_fn,
+                                                      void *));
  typedef int (*walk_namespaces_fn)               PARAMS ((tree, void 
*));
  extern int walk_namespaces                      PARAMS 
((walk_namespaces_fn,
                                                       void *));
Index: cp/decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/decl.c,v
retrieving revision 1.931
diff -c -3 -p -r1.931 decl.c
*** cp/decl.c   13 Aug 2002 16:36:26 -0000      1.931
--- cp/decl.c   21 Aug 2002 23:35:27 -0000
*************** static struct cp_binding_level *innermos
*** 108,113 ****
--- 108,114 ----
  static void warn_about_implicit_typename_lookup PARAMS ((tree, tree));
  static int walk_namespaces_r PARAMS ((tree, walk_namespaces_fn, void 
*));
  static int walk_globals_r PARAMS ((tree, void *));
+ static int walk_vtables_r PARAMS ((tree, void*));
  static void add_decl_to_level PARAMS ((tree, struct cp_binding_level 
*));
  static tree make_label_decl PARAMS ((tree, int));
  static void use_label PARAMS ((tree));
*************** struct cp_binding_level GTY(())
*** 319,324 ****
--- 320,334 ----
         are wrapped in TREE_LISTs; the TREE_VALUE is the OVERLOAD.  */
      tree names;

+     /* Count of elements in names chain.  */
+     size_t names_size;
+
+     /* A chain of NAMESPACE_DECL nodes.  */
+     tree namespaces;
+
+     /* A chain of VTABLE_DECL nodes.  */
+     tree vtables;
+
      /* A list of structure, union and enum definitions, for looking up
         tag names.
         It is a chain of TREE_LIST nodes, each of whose TREE_PURPOSE 
is a name,
*************** add_decl_to_level (decl, b)
*** 1007,1016 ****
       tree decl;
       struct cp_binding_level *b;
  {
!   /* We build up the list in reverse order, and reverse it later if
!      necessary.  */
!   TREE_CHAIN (decl) = b->names;
!   b->names = decl;
  }

  /* Bind DECL to ID in the current_binding_level, assumed to be a local
--- 1017,1041 ----
       tree decl;
       struct cp_binding_level *b;
  {
!   if (TREE_CODE (decl) == NAMESPACE_DECL
!       && !DECL_NAMESPACE_ALIAS (decl))
!     {
!       TREE_CHAIN (decl) = b->namespaces;
!       b->namespaces = decl;
!     }
!   else if (TREE_CODE (decl) == VAR_DECL && DECL_VIRTUAL_P (decl))
!     {
!       TREE_CHAIN (decl) = b->vtables;
!       b->vtables = decl;
!     }
!   else
!     {
!       /* We build up the list in reverse order, and reverse it later 
if
!          necessary.  */
!       TREE_CHAIN (decl) = b->names;
!       b->names = decl;
!       b->names_size++;
!     }
  }

  /* Bind DECL to ID in the current_binding_level, assumed to be a local
*************** cp_namespace_decls (ns)
*** 1747,1752 ****
--- 1772,1821 ----
    return NAMESPACE_LEVEL (ns)->names;
  }

+ struct walk_globals_data {
+   walk_globals_pred p;
+   walk_globals_fn f;
+   void *data;
+ };
+
+ /* Walk the vtable declarations in NAMESPACE.  Whenever one is found
+    for which P returns non-zero, call F with its address.  If any call
+    to F returns a non-zero value, return a non-zero value.  */
+
+ static int
+ walk_vtables_r (namespace, data)
+      tree namespace;
+      void *data;
+ {
+   struct walk_globals_data* wgd = (struct walk_globals_data *) data;
+   walk_globals_fn f = wgd->f;
+   void *d = wgd->data;
+   tree decl = NAMESPACE_LEVEL (namespace)->vtables;
+   int result = 0;
+
+   for (; decl ; decl = TREE_CHAIN (decl))
+     result != (*f) (&decl, d);
+
+   return result;
+ }
+
+ /* Walk the vtable declarations.  Whenever one is found for which P
+    returns non-zero, call F with its address.  If any call to F
+    returns a non-zero value, return a non-zero value.  */
+ int
+ walk_vtables (p, f, data)
+      walk_globals_pred p;
+      walk_globals_fn f;
+      void *data;
+ {
+   struct walk_globals_data wgd;
+   wgd.p = p;
+   wgd.f = f;
+   wgd.data = data;
+
+   return walk_namespaces (walk_vtables_r, &wgd);
+ }
+
  /* Walk all the namespaces contained NAMESPACE, including NAMESPACE
     itself, calling F for each.  The DATA is passed to F as well.  */

*************** walk_namespaces_r (namespace, f, data)
*** 1756,1777 ****
       walk_namespaces_fn f;
       void *data;
  {
-   tree current;
    int result = 0;

    result |= (*f) (namespace, data);

!   for (current = cp_namespace_decls (namespace);
!        current;
!        current = TREE_CHAIN (current))
!     {
!       if (TREE_CODE (current) != NAMESPACE_DECL
!         || DECL_NAMESPACE_ALIAS (current))
!       continue;
!
!       /* We found a namespace.  */
!       result |= walk_namespaces_r (current, f, data);
!     }

    return result;
  }
--- 1825,1837 ----
       walk_namespaces_fn f;
       void *data;
  {
    int result = 0;
+   tree current = NAMESPACE_LEVEL (namespace)->namespaces;

    result |= (*f) (namespace, data);

!   for (; current; current = TREE_CHAIN (current))
!     result |= walk_namespaces_r (current, f, data);

    return result;
  }
*************** walk_namespaces (f, data)
*** 1787,1798 ****
    return walk_namespaces_r (global_namespace, f, data);
  }

- struct walk_globals_data {
-   walk_globals_pred p;
-   walk_globals_fn f;
-   void *data;
- };
-
  /* Walk the global declarations in NAMESPACE.  Whenever one is found
     for which P returns non-zero, call F with its address.  If any call
     to F returns a non-zero value, return a non-zero value.  */
--- 1847,1852 ----
*************** wrapup_globals_for_namespace (namespace,
*** 1855,1861 ****
       void *data;
  {
    tree globals = cp_namespace_decls (namespace);
!   int len = list_length (globals);
    tree *vec = (tree *) alloca (sizeof (tree) * len);
    int i;
    int result;
--- 1909,1915 ----
       void *data;
  {
    tree globals = cp_namespace_decls (namespace);
!   int len = NAMESPACE_LEVEL (namespace)->names_size;
    tree *vec = (tree *) alloca (sizeof (tree) * len);
    int i;
    int result;
*************** wrapup_globals_for_namespace (namespace,
*** 1867,1873 ****
      return 0;

    /* Process the decls in reverse order--earliest first.
!      Put them into VEC from back to front, then take out from front.  
*/
    for (i = 0, decl = globals; i < len; i++, decl = TREE_CHAIN (decl))
      vec[len - i - 1] = decl;

--- 1921,1927 ----
      return 0;

    /* Process the decls in reverse order--earliest first.
!      Put them into VEC from back to front, then take out from front.  
*/
    for (i = 0, decl = globals; i < len; i++, decl = TREE_CHAIN (decl))
      vec[len - i - 1] = decl;

*************** wrapup_globals_for_namespace (namespace,
*** 1877,1903 ****
        return 0;
      }

-   /* Temporarily mark vtables as external.  That prevents
-      wrapup_global_declarations from writing them out; we must process
-      them ourselves in finish_vtable_vardecl.  */
-   for (i = 0; i < len; ++i)
-     if (vtable_decl_p (vec[i], /*data=*/0) && !DECL_EXTERNAL (vec[i]))
-       {
-       DECL_NOT_REALLY_EXTERN (vec[i]) = 1;
-       DECL_EXTERNAL (vec[i]) = 1;
-       }
-
    /* Write out any globals that need to be output.  */
    result = wrapup_global_declarations (vec, len);
-
-   /* Undo the hack to DECL_EXTERNAL above.  */
-   for (i = 0; i < len; ++i)
-     if (vtable_decl_p (vec[i], /*data=*/0)
-       && DECL_NOT_REALLY_EXTERN (vec[i]))
-       {
-       DECL_NOT_REALLY_EXTERN (vec[i]) = 0;
-       DECL_EXTERNAL (vec[i]) = 0;
-       }

    return result;
  }
--- 1931,1938 ----
Index: cp/decl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/decl.h,v
retrieving revision 1.8
diff -c -3 -p -r1.8 decl.h
*** cp/decl.h   4 Jun 2002 07:10:07 -0000       1.8
--- cp/decl.h   21 Aug 2002 23:35:27 -0000
*************** extern GTY(()) tree last_function_parms;
*** 44,50 ****
     in the TREE_PURPOSE slot.  */
  extern GTY(()) tree static_aggregates;

- #ifdef DEBUG_CP_BINDING_LEVELS
  /* Purely for debugging purposes.  */
  extern int debug_bindings_indentation;
  #endif
--- 44,49 ----
Index: cp/decl2.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/decl2.c,v
retrieving revision 1.560
diff -c -3 -p -r1.560 decl2.c
*** cp/decl2.c  15 Aug 2002 21:16:52 -0000      1.560
--- cp/decl2.c  21 Aug 2002 23:35:27 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 47,52 ****
--- 47,53 ----
  #include "c-common.h"
  extern cpp_reader *parse_in;

+
  /* This structure contains information about the initializations
     and/or destructions required for a particular priority level.  */
  typedef struct priority_info_s {
*************** finish_file ()
*** 2774,2780 ****
        /* Write out virtual tables as required.  Note that writing out
         the virtual table for a template class may cause the
         instantiation of members of that class.  */
!       if (walk_globals (vtable_decl_p,
                        finish_vtable_vardecl,
                        /*data=*/0))
        reconsider = 1;
--- 2775,2781 ----
        /* Write out virtual tables as required.  Note that writing out
         the virtual table for a template class may cause the
         instantiation of members of that class.  */
!       if (walk_vtables (vtable_decl_p,
                        finish_vtable_vardecl,
                        /*data=*/0))
        reconsider = 1;
*************** finish_file ()
*** 2954,2966 ****
    /* We're done with static constructors, so we can go back to "C++"
       linkage now.  */
    pop_lang_context ();
-
-   /* Now delete from the chain of variables all virtual function 
tables.
-      We output them all ourselves, because each will be treated
-      specially.  We don't do this if we're just doing semantic
-      analysis, and not code-generation.  */
-   if (!flag_syntax_only)
-     walk_globals (vtable_decl_p, prune_vtable_vardecl, /*data=*/0);

    /* Now, issue warnings about static, but not defined, functions,
       etc., and emit debugging information.  */
--- 2955,2960 ----