2003-07-16 Andrew Pinski <pinskia@physics.uc.edu>

ChangeLog:
        PR c/10962
        * ggc.h: Add header guards.
        * c-decl.c (finish_struct): Sort fields if
        number greater than 15 and there are no
        anonymous structs/unions.
        * c-common.h: Include ggc.h.
        (sorted_fields_type): New struct.
        (field_decl_cmp): New prototype.
        (resort_sorted_fields): New prototype.
        (DECL_DECLARES_TYPE_NON_TEMPLATE_P): New macro.
        * c-tree.h: (lang_type): Use pointer to sorted_fields_type
        as s, removing other fields.
        * c-typeck.c (lookup_field): Use s in lang_type.
        These were mostly moved from cp/class.c:
        * c-common.c (field_decl_cmp): New static function.
        (field_decl_cmp): New function.
        (resort_sorted_fields): New function.
cp/ChangeLog:
        * class.c (field_decl_cmp): Remove.
        (resort_field_decl_cmp): Remove.
        (resort_sorted_fields): Remove.
        (add_fields_to_vec): Rename to ...
        (add_fields_to_record_type): this.
        (finish_struct_1): Change to be using
        sorted_fields_type's fields.
        * cp-tree.h (lang_decl): In lang_decl_u3
        change sorted_fields to be a pointer to
        sorted_fields_type.
        (resort_sorted_fields): Remove prototype.
        * search.c (lookup_field_1): Change to be using
        sorted_fields_type's fields.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@69470 138bc75d-0d04-0410-961f-82ee72b054a4

11 files changed, 186 insertions, 80 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 95255987ddb..f8b4875def0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,23 @@
+2003-07-16  Andrew Pinski  <pinskia@physics.uc.edu>
+
+	PR c/10962
+	* ggc.h: Add header guards.
+	* c-decl.c (finish_struct): Sort fields if
+	number greater than 15 and there are no
+	anonymous structs/unions.
+	* c-common.h: Include ggc.h.
+	(sorted_fields_type): New struct.
+	(field_decl_cmp): New prototype.
+	(resort_sorted_fields): New prototype.
+	(DECL_DECLARES_TYPE_NON_TEMPLATE_P): New macro.
+	* c-tree.h: (lang_type): Use pointer to sorted_fields_type
+	as s, removing other fields.
+	* c-typeck.c (lookup_field): Use s in lang_type.
+	These were mostly moved from cp/class.c:
+	* c-common.c (field_decl_cmp): New static function.
+	(field_decl_cmp): New function.
+	(resort_sorted_fields): New function.
+
 2003-07-16  Geoffrey Keating  <geoffk@apple.com>
 
 	* config/darwin.c (machopic_select_section): Use decl_readonly_section
diff --git a/gcc/c-common.c b/gcc/c-common.c
index b122f9b39e6..ba0138db0bb 100644
--- a/gcc/c-common.c
+++ b/gcc/c-common.c
@@ -776,6 +776,7 @@ static void check_function_nonnull (tree, tree);
 static void check_nonnull_arg (void *, tree, unsigned HOST_WIDE_INT);
 static bool nonnull_check_p (tree, unsigned HOST_WIDE_INT);
 static bool get_nonnull_operand (tree, unsigned HOST_WIDE_INT *);
+static int resort_field_decl_cmp (const void *, const void *);
 
 /* Table of machine-independent attributes common to all C-like languages.  */
 const struct attribute_spec c_common_attribute_table[] =
@@ -5882,6 +5883,72 @@ check_function_arguments_recurse (void (*callback)
   (*callback) (ctx, param, param_num);
 }
 
+/* Function to help qsort sort FIELD_DECLs by name order.  */
+
+int
+field_decl_cmp (const void *x_p, const void *y_p)
+{
+  const tree *const x = x_p;
+  const tree *const y = y_p;
+  if (DECL_NAME (*x) == DECL_NAME (*y))
+    /* A nontype is "greater" than a type.  */
+    return (TREE_CODE (*y) == TYPE_DECL) - (TREE_CODE (*x) == TYPE_DECL);
+  if (DECL_NAME (*x) == NULL_TREE)
+    return -1;
+  if (DECL_NAME (*y) == NULL_TREE)
+    return 1;
+  if (DECL_NAME (*x) < DECL_NAME (*y))
+    return -1;
+  return 1;
+}
+
+static struct {
+  gt_pointer_operator new_value;
+  void *cookie;
+} resort_data;
+
+/* This routine compares two fields like field_decl_cmp but using the
+pointer operator in resort_data.  */
+
+static int
+resort_field_decl_cmp (const void *x_p, const void *y_p)
+{
+  const tree *const x = x_p;
+  const tree *const y = y_p;
+
+  if (DECL_NAME (*x) == DECL_NAME (*y))
+    /* A nontype is "greater" than a type.  */
+    return (TREE_CODE (*y) == TYPE_DECL) - (TREE_CODE (*x) == TYPE_DECL);
+  if (DECL_NAME (*x) == NULL_TREE)
+    return -1;
+  if (DECL_NAME (*y) == NULL_TREE)
+    return 1;
+  {
+    tree d1 = DECL_NAME (*x);
+    tree d2 = DECL_NAME (*y);
+    resort_data.new_value (&d1, resort_data.cookie);
+    resort_data.new_value (&d2, resort_data.cookie);
+    if (d1 < d2)
+      return -1;
+  }
+  return 1;
+}
+
+/* Resort DECL_SORTED_FIELDS because pointers have been reordered.  */
+
+void
+resort_sorted_fields (void *obj,
+                      void *orig_obj ATTRIBUTE_UNUSED ,
+                      gt_pointer_operator new_value,
+                      void *cookie)
+{
+  struct sorted_fields_type *sf = obj;
+  resort_data.new_value = new_value;
+  resort_data.cookie = cookie;
+  qsort (&sf->elts[0], sf->len, sizeof (tree),
+         resort_field_decl_cmp);
+}
+
 /* Used by estimate_num_insns.  Estimate number of instructions seen
    by given statement.  */
 static tree
diff --git a/gcc/c-common.h b/gcc/c-common.h
index 94cf6d2dc86..fd7ce4aef75 100644
--- a/gcc/c-common.h
+++ b/gcc/c-common.h
@@ -24,6 +24,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 
 #include "splay-tree.h"
 #include "cpplib.h"
+#include "ggc.h"
 
 /* Usage of TREE_LANG_FLAG_?:
    0: COMPOUND_STMT_NO_SCOPE (in COMPOUND_STMT).
@@ -223,6 +224,13 @@ struct c_common_identifier GTY(())
 
 extern GTY(()) tree c_global_trees[CTI_MAX];
 
+/* In a RECORD_TYPE, a sorted array of the fields of the type, not a tree for size reasons.  */
+struct sorted_fields_type GTY(())
+{
+  int len;
+  tree GTY((length ("%h.len"))) elts[1];
+};
+
 /* Mark which labels are explicitly declared.
    These may be shadowed, and may be referenced from nested functions.  */
 #define C_DECLARED_LABEL_FLAG(label) TREE_LANG_FLAG_1 (label)
@@ -343,6 +351,9 @@ extern void c_finish_while_stmt_cond (tree, tree);
 
 enum sw_kind { SW_PARAM = 0, SW_LOCAL, SW_GLOBAL };
 extern void shadow_warning (enum sw_kind, const char *, tree);
+extern int field_decl_cmp (const void *, const void *);
+extern void resort_sorted_fields (void *, void *, gt_pointer_operator, 
+                                  void *);
 
 /* Extra information associated with a DECL.  Other C dialects extend
    this structure in various ways.  The C front-end only uses this
diff --git a/gcc/c-decl.c b/gcc/c-decl.c
index 80e6b68fa2e..c643d97193d 100644
--- a/gcc/c-decl.c
+++ b/gcc/c-decl.c
@@ -5155,6 +5155,56 @@ finish_struct (tree t, tree fieldlist, tree attributes)
 
   TYPE_FIELDS (t) = fieldlist;
 
+  /* If there are lots of fields, sort so we can look through them fast.
+    We arbitrarily consider 16 or more elts to be "a lot".  */
+
+  {
+    int len = 0;
+
+    for (x = fieldlist; x; x = TREE_CHAIN (x))
+      {
+        if (len > 15 || DECL_NAME (x) == NULL)
+          break;
+        len += 1;
+      }
+
+    if (len > 15)
+      {
+        tree *field_array;
+        struct lang_type *space;
+        struct sorted_fields_type *space2;
+        
+        len += list_length (x);
+  
+        /* Use the same allocation policy here that make_node uses, to
+          ensure that this lives as long as the rest of the struct decl.
+          All decls in an inline function need to be saved.  */
+  
+        space = ggc_alloc (sizeof (struct lang_type));
+        space2 = ggc_alloc (sizeof (struct sorted_fields_type) + len * sizeof (tree));
+        
+        len = 0;
+	space->s = space2;
+	field_array = &space2->elts[0];
+        for (x = fieldlist; x; x = TREE_CHAIN (x))
+          {
+            field_array[len++] = x;
+          
+            /* if there is anonymous struct or union break out of the loop */
+            if (DECL_NAME (x) == NULL)
+              break;
+          }
+        /* found no anonymous struct/union add the TYPE_LANG_SPECIFIC. */
+        if (x == NULL)
+          {
+            TYPE_LANG_SPECIFIC (t) = space;
+            TYPE_LANG_SPECIFIC (t)->s->len = len;
+            field_array = TYPE_LANG_SPECIFIC (t)->s->elts;
+            qsort (field_array, len, sizeof (tree), field_decl_cmp);
+          }
+      }
+  }
+  
   for (x = TYPE_MAIN_VARIANT (t); x; x = TYPE_NEXT_VARIANT (x))
     {
       TYPE_FIELDS (x) = TYPE_FIELDS (t);
diff --git a/gcc/c-tree.h b/gcc/c-tree.h
index adfea88924b..50e161e5e46 100644
--- a/gcc/c-tree.h
+++ b/gcc/c-tree.h
@@ -109,8 +109,7 @@ struct lang_decl GTY(())
 /* In a RECORD_TYPE, a sorted array of the fields of the type.  */
 struct lang_type GTY(())
 {
-  int len;
-  tree GTY((length ("%h.len"))) elts[1];
+  struct sorted_fields_type * GTY ((reorder ("resort_sorted_fields"))) s; 
 };
 
 /* Record whether a type or decl was written with nonconstant size.
diff --git a/gcc/c-typeck.c b/gcc/c-typeck.c
index 7564660cd01..6f2b6f4204c 100644
--- a/gcc/c-typeck.c
+++ b/gcc/c-typeck.c
@@ -1183,11 +1183,11 @@ lookup_field (tree decl, tree component)
   if (TYPE_LANG_SPECIFIC (type))
     {
       int bot, top, half;
-      tree *field_array = &TYPE_LANG_SPECIFIC (type)->elts[0];
+      tree *field_array = &TYPE_LANG_SPECIFIC (type)->s->elts[0];
 
       field = TYPE_FIELDS (type);
       bot = 0;
-      top = TYPE_LANG_SPECIFIC (type)->len;
+      top = TYPE_LANG_SPECIFIC (type)->s->len;
       while (top - bot > 1)
 	{
 	  half = (top - bot + 1) >> 1;
diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 68bcb3af7b3..e231e8bfbf4 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,20 @@
+2003-07-16  Andrew Pinski  <pinskia@physics.uc.edu>
+
+	PR c/10962
+	* class.c (field_decl_cmp): Remove.
+	(resort_field_decl_cmp): Remove.
+	(resort_sorted_fields): Remove.
+	(add_fields_to_vec): Rename to ...
+	(add_fields_to_record_type): this.
+	(finish_struct_1): Change to be using
+	sorted_fields_type's fields.
+	* cp-tree.h (lang_decl): In lang_decl_u3
+	change sorted_fields to be a pointer to
+	sorted_fields_type.
+	(resort_sorted_fields): Remove prototype.
+	* search.c (lookup_field_1): Change to be using
+	sorted_fields_type's fields.
+
 2003-07-16  Kriang Lerdsuwanakij  <lerdsuwa@users.sourceforge.net>
 
 	PR c++/5421
diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index 56745901e9a..ca22d82d7aa 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -124,8 +124,6 @@ static tree modify_all_vtables (tree, tree);
 static void determine_primary_base (tree);
 static void finish_struct_methods (tree);
 static void maybe_warn_about_overly_private_class (tree);
-static int field_decl_cmp (const void *, const void *);
-static int resort_field_decl_cmp (const void *, const void *);
 static int method_name_cmp (const void *, const void *);
 static int resort_method_name_cmp (const void *, const void *);
 static void add_implicitly_declared_members (tree, int, int, int);
@@ -136,7 +134,7 @@ static tree build_vtable_entry_ref (tree, tree, tree);
 static tree build_vtbl_ref_1 (tree, tree);
 static tree build_vtbl_initializer (tree, tree, tree, tree, int *);
 static int count_fields (tree);
-static int add_fields_to_vec (tree, tree, int);
+static int add_fields_to_record_type (tree, struct sorted_fields_type*, int);
 static void check_bitfield_decl (tree);
 static void check_field_decl (tree, tree, int *, int *, int *, int *);
 static void check_field_decls (tree, tree *, int *, int *, int *);
@@ -1711,72 +1709,11 @@ maybe_warn_about_overly_private_class (tree t)
     }
 }
 
-/* Function to help qsort sort FIELD_DECLs by name order.  */
-
-static int
-field_decl_cmp (const void* x_p, const void* y_p)
-{
-  const tree *const x = x_p;
-  const tree *const y = y_p;
-  if (DECL_NAME (*x) == DECL_NAME (*y))
-    /* A nontype is "greater" than a type.  */
-    return DECL_DECLARES_TYPE_P (*y) - DECL_DECLARES_TYPE_P (*x);
-  if (DECL_NAME (*x) == NULL_TREE)
-    return -1;
-  if (DECL_NAME (*y) == NULL_TREE)
-    return 1;
-  if (DECL_NAME (*x) < DECL_NAME (*y))
-    return -1;
-  return 1;
-}
-
 static struct {
   gt_pointer_operator new_value;
   void *cookie;
 } resort_data;
 
-/* This routine compares two fields like field_decl_cmp but using the
-   pointer operator in resort_data.  */
-
-static int
-resort_field_decl_cmp (const void* x_p, const void* y_p)
-{
-  const tree *const x = x_p;
-  const tree *const y = y_p;
-
-  if (DECL_NAME (*x) == DECL_NAME (*y))
-    /* A nontype is "greater" than a type.  */
-    return DECL_DECLARES_TYPE_P (*y) - DECL_DECLARES_TYPE_P (*x);
-  if (DECL_NAME (*x) == NULL_TREE)
-    return -1;
-  if (DECL_NAME (*y) == NULL_TREE)
-    return 1;
-  {
-    tree d1 = DECL_NAME (*x);
-    tree d2 = DECL_NAME (*y);
-    resort_data.new_value (&d1, resort_data.cookie);
-    resort_data.new_value (&d2, resort_data.cookie);
-    if (d1 < d2)
-      return -1;
-  }
-  return 1;
-}
-
-/* Resort DECL_SORTED_FIELDS because pointers have been reordered.  */
-
-void 
-resort_sorted_fields (void* obj, 
-                      void* orig_obj ATTRIBUTE_UNUSED , 
-                      gt_pointer_operator new_value, 
-                      void* cookie)
-{
-  tree sf = obj;
-  resort_data.new_value = new_value;
-  resort_data.cookie = cookie;
-  qsort (&TREE_VEC_ELT (sf, 0), TREE_VEC_LENGTH (sf), sizeof (tree),
-	 resort_field_decl_cmp);
-}
-
 /* Comparison function to compare two TYPE_METHOD_VEC entries by name.  */
 
 static int
@@ -2786,18 +2723,18 @@ count_fields (tree fields)
 }
 
 /* Subroutine of finish_struct_1.  Recursively add all the fields in the
-   TREE_LIST FIELDS to the TREE_VEC FIELD_VEC, starting at offset IDX.  */
+   TREE_LIST FIELDS to the SORTED_FIELDS_TYPE elts, starting at offset IDX.  */
 
 static int
-add_fields_to_vec (tree fields, tree field_vec, int idx)
+add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec, int idx)
 {
   tree x;
   for (x = fields; x; x = TREE_CHAIN (x))
     {
       if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
-	idx = add_fields_to_vec (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
+	idx = add_fields_to_record_type (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
       else
-	TREE_VEC_ELT (field_vec, idx++) = x;
+	field_vec->elts[idx++] = x;
     }
   return idx;
 }
@@ -5160,9 +5097,11 @@ finish_struct_1 (tree t)
   n_fields = count_fields (TYPE_FIELDS (t));
   if (n_fields > 7)
     {
-      tree field_vec = make_tree_vec (n_fields);
-      add_fields_to_vec (TYPE_FIELDS (t), field_vec, 0);
-      qsort (&TREE_VEC_ELT (field_vec, 0), n_fields, sizeof (tree),
+      struct sorted_fields_type *field_vec = ggc_alloc (sizeof (struct sorted_fields_type) 
+	+ n_fields * sizeof (tree));
+      field_vec->len = n_fields;
+      add_fields_to_record_type (TYPE_FIELDS (t), field_vec, 0);
+      qsort (field_vec->elts, n_fields, sizeof (tree),
 	     field_decl_cmp);
       if (! DECL_LANG_SPECIFIC (TYPE_MAIN_DECL (t)))
 	retrofit_lang_decl (TYPE_MAIN_DECL (t));
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 8272adc4db4..40f3784fc9b 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -1727,7 +1727,7 @@ struct lang_decl GTY(())
 	
 	union lang_decl_u3
 	{
-	  tree GTY ((tag ("0"), reorder ("resort_sorted_fields"))) 
+	  struct sorted_fields_type * GTY ((tag ("0"), reorder ("resort_sorted_fields"))) 
 	       sorted_fields;
  	  struct cp_token_cache * GTY ((tag ("2"))) pending_inline_info;
 	  struct language_function * GTY ((tag ("1"))) 
@@ -3553,8 +3553,6 @@ extern tree convert_to_base                     (tree, tree, bool);
 extern tree build_vtbl_ref			(tree, tree);
 extern tree build_vfn_ref			(tree, tree);
 extern tree get_vtable_decl                     (tree, int);
-extern void resort_sorted_fields 
-  (void *, void *, gt_pointer_operator, void *);
 extern void resort_type_method_vec
   (void *, void *, gt_pointer_operator, void *);
 extern void add_method				(tree, tree, int);
diff --git a/gcc/cp/search.c b/gcc/cp/search.c
index 1161084980d..10b52164cd0 100644
--- a/gcc/cp/search.c
+++ b/gcc/cp/search.c
@@ -432,8 +432,8 @@ lookup_field_1 (tree type, tree name, bool want_type)
       && DECL_LANG_SPECIFIC (TYPE_NAME (type))
       && DECL_SORTED_FIELDS (TYPE_NAME (type)))
     {
-      tree *fields = &TREE_VEC_ELT (DECL_SORTED_FIELDS (TYPE_NAME (type)), 0);
-      int lo = 0, hi = TREE_VEC_LENGTH (DECL_SORTED_FIELDS (TYPE_NAME (type)));
+      tree *fields = &DECL_SORTED_FIELDS (TYPE_NAME (type))->elts[0];
+      int lo = 0, hi = DECL_SORTED_FIELDS (TYPE_NAME (type))->len;
       int i;
 
       while (lo < hi)
diff --git a/gcc/ggc.h b/gcc/ggc.h
index 2c56a3c525e..3a88e165479 100644
--- a/gcc/ggc.h
+++ b/gcc/ggc.h
@@ -19,6 +19,9 @@ along with GCC; see the file COPYING.  If not, write to the Free
 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 02111-1307, USA.  */
 
+#ifndef GCC_GGC_H
+#define GCC_GGC_H
+
 /* Symbols are marked with `ggc' for `gcc gc' so as not to interfere with
    an external gc library that might be linked in.  */
 
@@ -259,3 +262,5 @@ extern void stringpool_statistics (void);
 extern int ggc_min_expand_heuristic (void);
 extern int ggc_min_heapsize_heuristic (void);
 extern void init_ggc_heuristics (void);
+
+#endif