From f90cdf34d2409c87ade5b20cff4f9b4ffc64cfaf Mon Sep 17 00:00:00 2001 From: Michael Tiemann Date: Fri, 9 Jul 1999 16:15:04 +0000 Subject: [PATCH] cp-tree.h (struct lang_decl): Added field for storing sorted FIELD_DECLs (used in TYPE_DECLs). * cp-tree.h (struct lang_decl): Added field for storing sorted FIELD_DECLs (used in TYPE_DECLs). (DECL_PENDING_INLINE_INFO): Adjusted to use 'u' union. (DECL_SORTED_FIELDS): New macro. * class.c (method_name_cmp): New function. (finish_struct_methods): Modified to support sorting and searching methods. (finish_struct_anon): Changed code in inner loop to use ELT rather than UELT (which required an extra indirection for every reference). (field_decl_cmp): New function to support sorting FIELD_DECLs. (finish_struct_1): Sort fields. * search.c (lookup_field_1): Use DECL_SORTED_FIELDS if we have them. (lookup_fnfields_1): Search sorted methods in METHOD_VEC. Also, switch to using array indexing rather than a changing pointer. * ptree.c (print_lang_decl): Handle TYPE_DECLs that have DECL_SORTED_FIELDS. Co-Authored-By: Jason Merrill From-SVN: r28046 --- gcc/cp/ChangeLog | 20 ++++++ gcc/cp/class.c | 156 +++++++++++++++++++++++++++++++++++++++++------ gcc/cp/cp-tree.h | 12 +++- gcc/cp/ptree.c | 9 ++- gcc/cp/search.c | 95 ++++++++++++++++++++++------- 5 files changed, 248 insertions(+), 44 deletions(-) diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index ff27a479baf..6edfa5f2a77 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -1,3 +1,23 @@ +1999-07-09 Michael Tiemann + Jason Merrill + + * cp-tree.h (struct lang_decl): Added field for storing sorted + FIELD_DECLs (used in TYPE_DECLs). + (DECL_PENDING_INLINE_INFO): Adjusted to use 'u' union. + (DECL_SORTED_FIELDS): New macro. + * class.c (method_name_cmp): New function. + (finish_struct_methods): Modified to support sorting and searching + methods. + (finish_struct_anon): Changed code in inner loop to use ELT rather + than UELT (which required an extra indirection for every reference). + (field_decl_cmp): New function to support sorting FIELD_DECLs. + (finish_struct_1): Sort fields. + * search.c (lookup_field_1): Use DECL_SORTED_FIELDS if we have them. + (lookup_fnfields_1): Search sorted methods in METHOD_VEC. + Also, switch to using array indexing rather than a changing pointer. + * ptree.c (print_lang_decl): Handle TYPE_DECLs that have + DECL_SORTED_FIELDS. + 1999-07-09 Jason Merrill * decl2.c (reparse_absdcl_as_casts): Don't warn about old-style diff --git a/gcc/cp/class.c b/gcc/cp/class.c index 4d00dfb5475..6a25b5915ed 100644 --- a/gcc/cp/class.c +++ b/gcc/cp/class.c @@ -130,6 +130,8 @@ static void modify_all_indirect_vtables PROTO((tree, int, int, tree, static int finish_base_struct PROTO((tree, struct base_info *)); static void finish_struct_methods PROTO((tree)); static void maybe_warn_about_overly_private_class PROTO ((tree)); +static int field_decl_cmp PROTO ((const tree *, const tree *)); +static int method_name_cmp PROTO ((const tree *, const tree *)); static tree make_method_vec PROTO((int)); static void free_method_vec PROTO((tree)); static tree add_implicitly_declared_members PROTO((tree, int, int, int)); @@ -2004,6 +2006,39 @@ maybe_warn_about_overly_private_class (t) } } +/* Function to help qsort sort FIELD_DECLs by name order. */ + +static int +field_decl_cmp (x, y) + const tree *x, *y; +{ + if (DECL_NAME (*x) == DECL_NAME (*y)) + return 0; + 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; +} + +/* Comparison function to compare two TYPE_METHOD_VEC entries by name. */ + +static int +method_name_cmp (m1, m2) + const tree *m1, *m2; +{ + if (*m1 == NULL_TREE && *m2 == NULL_TREE) + return 0; + if (*m1 == NULL_TREE) + return -1; + if (*m2 == NULL_TREE) + return 1; + if (DECL_NAME (OVL_CURRENT (*m1)) < DECL_NAME (OVL_CURRENT (*m2))) + return -1; + return 1; +} /* Warn about duplicate methods in fn_fields. Also compact method lists so that lookup can be made faster. @@ -2020,10 +2055,11 @@ maybe_warn_about_overly_private_class (t) If there are any constructors/destructors, they are moved to the front of the list. This makes pushclass more efficient. - We also link each field which has shares a name with its baseclass - to the head of the list of fields for that base class. This allows - us to reduce search time in places like `build_method_call' to - consider only reasonably likely functions. */ + @@ The above comment is obsolete. It mostly describes what add_method + @@ and add_implicitly_declared_members do. + + Sort methods that are not special (i.e., constructors, destructors, and + type conversion operators) so that we can find them faster in search. */ static void finish_struct_methods (t) @@ -2032,6 +2068,7 @@ finish_struct_methods (t) tree fn_fields; tree method_vec = CLASSTYPE_METHOD_VEC (t); tree ctor_name = constructor_name (t); + int slot, len = method_vec ? TREE_VEC_LENGTH (method_vec) : 0; /* First fill in entry 0 with the constructors, entry 1 with destructors, and the next few with type conversion operators (if any). */ @@ -2089,7 +2126,28 @@ finish_struct_methods (t) /* Issue warnings about private constructors and such. If there are no methods, then some public defaults are generated. */ - maybe_warn_about_overly_private_class (t); + maybe_warn_about_overly_private_class (t); + + if (method_vec == NULL_TREE) + return; + + /* Now sort the methods. */ + while (len > 2 && TREE_VEC_ELT (method_vec, len-1) == NULL_TREE) + len--; + TREE_VEC_LENGTH (method_vec) = len; + + /* The type conversion ops have to live at the front of the vec, so we + can't sort them. */ + for (slot = 2; slot < len; ++slot) + { + tree fn = TREE_VEC_ELT (method_vec, slot); + + if (!DECL_CONV_FN_P (OVL_CURRENT (fn))) + break; + } + if (len - slot > 1) + qsort (&TREE_VEC_ELT (method_vec, slot), len-slot, sizeof (tree), + (int (*)(const void *, const void *))method_name_cmp); } /* Emit error when a duplicate definition of a type is seen. Patch up. */ @@ -2950,6 +3008,7 @@ finish_struct_anon (t) tree t; { tree field; + for (field = TYPE_FIELDS (t); field; field = TREE_CHAIN (field)) { if (TREE_STATIC (field)) @@ -2960,32 +3019,32 @@ finish_struct_anon (t) if (DECL_NAME (field) == NULL_TREE && ANON_AGGR_TYPE_P (TREE_TYPE (field))) { - tree* uelt = &TYPE_FIELDS (TREE_TYPE (field)); - for (; *uelt; uelt = &TREE_CHAIN (*uelt)) + tree elt = TYPE_FIELDS (TREE_TYPE (field)); + for (; elt; elt = TREE_CHAIN (elt)) { - if (DECL_ARTIFICIAL (*uelt)) + if (DECL_ARTIFICIAL (elt)) continue; - if (DECL_NAME (*uelt) == constructor_name (t)) + if (DECL_NAME (elt) == constructor_name (t)) cp_pedwarn_at ("ANSI C++ forbids member `%D' with same name as enclosing class", - *uelt); + elt); - if (TREE_CODE (*uelt) != FIELD_DECL) + if (TREE_CODE (elt) != FIELD_DECL) { cp_pedwarn_at ("`%#D' invalid; an anonymous union can only have non-static data members", - *uelt); + elt); continue; } - if (TREE_PRIVATE (*uelt)) + if (TREE_PRIVATE (elt)) cp_pedwarn_at ("private member `%#D' in anonymous union", - *uelt); - else if (TREE_PROTECTED (*uelt)) + elt); + else if (TREE_PROTECTED (elt)) cp_pedwarn_at ("protected member `%#D' in anonymous union", - *uelt); + elt); - TREE_PRIVATE (*uelt) = TREE_PRIVATE (field); - TREE_PROTECTED (*uelt) = TREE_PROTECTED (field); + TREE_PRIVATE (elt) = TREE_PRIVATE (field); + TREE_PROTECTED (elt) = TREE_PROTECTED (field); } } } @@ -3077,6 +3136,44 @@ add_implicitly_declared_members (t, cant_have_default_ctor, return virtual_dtor; } +/* Subroutine of finish_struct_1. Recursively count the number of fields + in TYPE, including anonymous union members. */ + +static int +count_fields (fields) + tree fields; +{ + tree x; + int n_fields = 0; + for (x = fields; x; x = TREE_CHAIN (x)) + { + if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x))) + n_fields += count_fields (TYPE_FIELDS (TREE_TYPE (x))); + else + n_fields += 1; + } + return n_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. */ + +static int +add_fields_to_vec (fields, field_vec, idx) + tree fields, 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); + else + TREE_VEC_ELT (field_vec, idx++) = x; + } + return idx; +} + /* Create a RECORD_TYPE or UNION_TYPE node for a C struct or union declaration (or C++ class declaration). @@ -3125,6 +3222,7 @@ finish_struct_1 (t, warn_anon) int cant_have_const_ctor; int no_const_asn_ref; int has_mutable = 0; + int n_fields = 0; /* The index of the first base class which has virtual functions. Only applied to non-virtual baseclasses. */ @@ -4008,6 +4106,28 @@ finish_struct_1 (t, warn_anon) } } + /* Done with FIELDS...now decide whether to sort these for + faster lookups later. Don't worry about optimizing + for structs only declared in inline functions...they're + not going to be referenced anywhere else. + + The C front-end only does this when n_fields > 15. We use + a smaller number because most searches fail (succeeding + ultimately as the search bores through the inheritance + hierarchy), and we want this failure to occur quickly. */ + + n_fields = count_fields (fields); + if (n_fields > 7 && !allocation_temporary_p ()) + { + tree field_vec = make_tree_vec (n_fields); + add_fields_to_vec (fields, field_vec, 0); + qsort (&TREE_VEC_ELT (field_vec, 0), n_fields, sizeof (tree), + (int (*)(const void *, const void *))field_decl_cmp); + if (! DECL_LANG_SPECIFIC (TYPE_MAIN_DECL (t))) + retrofit_lang_decl (TYPE_MAIN_DECL (t)); + DECL_SORTED_FIELDS (TYPE_MAIN_DECL (t)) = field_vec; + } + if (TYPE_HAS_CONSTRUCTOR (t)) { tree vfields = CLASSTYPE_VFIELDS (t); diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h index cfbe20274f5..f32eea899ac 100644 --- a/gcc/cp/cp-tree.h +++ b/gcc/cp/cp-tree.h @@ -1194,7 +1194,11 @@ struct lang_decl tree main_decl_variant; tree befriending_classes; - struct pending_inline *pending_inline_info; + union + { + tree sorted_fields; + struct pending_inline *pending_inline_info; + } u; }; /* Non-zero if NODE is a _DECL with TREE_READONLY set. */ @@ -1379,7 +1383,11 @@ struct lang_decl /* For a FUNCTION_DECL: if this function was declared inline inside of a class declaration, this is where the text for the function is squirreled away. */ -#define DECL_PENDING_INLINE_INFO(NODE) (DECL_LANG_SPECIFIC(NODE)->pending_inline_info) +#define DECL_PENDING_INLINE_INFO(NODE) (DECL_LANG_SPECIFIC(NODE)->u.pending_inline_info) + +/* For a TYPE_DECL: if this function has many fields, we'll sort them + and put them into a TREE_VEC. */ +#define DECL_SORTED_FIELDS(NODE) (DECL_LANG_SPECIFIC(NODE)->u.sorted_fields) /* True if on the saved_inlines (see decl2.c) list. */ #define DECL_SAVED_INLINE(DECL) \ diff --git a/gcc/cp/ptree.c b/gcc/cp/ptree.c index 4008e39a205..3c8486425fd 100644 --- a/gcc/cp/ptree.c +++ b/gcc/cp/ptree.c @@ -48,11 +48,18 @@ print_lang_decl (file, node, indent) fprintf (file, " decl-main-variant "); fprintf (file, HOST_PTR_PRINTF, DECL_MAIN_VARIANT (node)); } - if (DECL_PENDING_INLINE_INFO (node)) + if (TREE_CODE (node) == FUNCTION_DECL + && DECL_PENDING_INLINE_INFO (node)) { fprintf (file, " pending-inline-info "); fprintf (file, HOST_PTR_PRINTF, DECL_PENDING_INLINE_INFO (node)); } + if (TREE_CODE (node) == TYPE_DECL + && DECL_SORTED_FIELDS (node)) + { + fprintf (file, " sorted-fields "); + fprintf (file, HOST_PTR_PRINTF, DECL_SORTED_FIELDS (node)); + } if (DECL_TEMPLATE_INFO (node)) { fprintf (file, " template-info "); diff --git a/gcc/cp/search.c b/gcc/cp/search.c index f2e9aa77669..0fe5cf44691 100644 --- a/gcc/cp/search.c +++ b/gcc/cp/search.c @@ -522,6 +522,32 @@ lookup_field_1 (type, name) of fields!) */ return NULL_TREE; + if (TYPE_NAME (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))); + int i; + + while (lo < hi) + { + i = (lo + hi) / 2; + +#ifdef GATHER_STATISTICS + n_fields_searched++; +#endif /* GATHER_STATISTICS */ + + if (DECL_NAME (fields[i]) > name) + hi = i; + else if (DECL_NAME (fields[i]) < name) + lo = i + 1; + else + return fields[i]; + } + return NULL_TREE; + } + field = TYPE_FIELDS (type); #ifdef GATHER_STATISTICS @@ -1502,61 +1528,84 @@ int lookup_fnfields_1 (type, name) tree type, name; { - register tree method_vec + tree method_vec = CLASS_TYPE_P (type) ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE; if (method_vec != 0) { + register int i; register tree *methods = &TREE_VEC_ELT (method_vec, 0); - register tree *end = TREE_VEC_END (method_vec); + int len = TREE_VEC_LENGTH (method_vec); + tree tmp; #ifdef GATHER_STATISTICS n_calls_lookup_fnfields_1++; #endif /* GATHER_STATISTICS */ /* Constructors are first... */ - if (*methods && name == ctor_identifier) - return 0; + if (name == ctor_identifier) + return methods[0] ? 0 : -1; /* and destructors are second. */ - if (*++methods && name == dtor_identifier) - return 1; + if (name == dtor_identifier) + return methods[1] ? 1 : -1; - while (++methods != end && *methods) + for (i = 2; i < len && methods[i]; ++i) { #ifdef GATHER_STATISTICS n_outer_fields_searched++; #endif /* GATHER_STATISTICS */ - if (DECL_NAME (OVL_CURRENT (*methods)) == name) - break; + + tmp = OVL_CURRENT (methods[i]); + if (DECL_NAME (tmp) == name) + return i; + + /* If the type is complete and we're past the conversion ops, + switch to binary search. */ + if (! DECL_CONV_FN_P (tmp) + && TYPE_SIZE (type)) + { + int lo = i + 1, hi = len; + + while (lo < hi) + { + i = (lo + hi) / 2; + +#ifdef GATHER_STATISTICS + n_outer_fields_searched++; +#endif /* GATHER_STATISTICS */ + + tmp = DECL_NAME (OVL_CURRENT (methods[i])); + + if (tmp > name) + hi = i; + else if (tmp < name) + lo = i + 1; + else + return i; + } + break; + } } /* If we didn't find it, it might have been a template conversion operator. (Note that we don't look for this case above so that we will always find specializations first.) */ - if ((methods == end || !*methods) - && IDENTIFIER_TYPENAME_P (name)) + if (IDENTIFIER_TYPENAME_P (name)) { - methods = &TREE_VEC_ELT (method_vec, 0) + 1; - - while (++methods != end && *methods) + for (i = 2; i < len && methods[i]; ++i) { - tree method_name = DECL_NAME (OVL_CURRENT (*methods)); - - if (!IDENTIFIER_TYPENAME_P (method_name)) + tmp = OVL_CURRENT (methods[i]); + if (! DECL_CONV_FN_P (tmp)) { /* Since all conversion operators come first, we know there is no such operator. */ - methods = end; break; } - else if (TREE_CODE (OVL_CURRENT (*methods)) == TEMPLATE_DECL) - break; + else if (TREE_CODE (tmp) == TEMPLATE_DECL) + return i; } } - - if (methods != end && *methods) - return methods - &TREE_VEC_ELT (method_vec, 0); } return -1; -- 2.30.2