Revert 2017-08-28 Nathan Sidwell <nathan@acm.org> Restore sorted_fields vector.

	Revert 2017-08-28  Nathan Sidwell  <nathan@acm.org>
	Restore sorted_fields vector.
	* cp-tree.h (lang_type): Restore sorted_fields vector.
	(CLASSTYPE_SORTED_FIELDS): Restore.
	(CLASSTYPE_BINDINGS): Delete.
	* name-lookup.c (lookup_field_1): Restore binary search.
	(sorted_fields_type_new, count_fields,
	add_fields_to_record_type, add_enum_fields_to_record_type): Restore
	(set_class_bindings): Revert.
	(insert_late_enum_def_binding): Restore field_vec insertion.

From-SVN: r251592

3 files changed, 146 insertions, 56 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 906448b..020caf2 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,16 @@
+2017-09-01  Nathan Sidwell  <nathan@acm.org>
+
+	Revert 2017-08-28  Nathan Sidwell  <nathan@acm.org>
+	Restore sorted_fields vector.
+	* cp-tree.h (lang_type): Restore sorted_fields vector.
+	(CLASSTYPE_SORTED_FIELDS): Restore.
+	(CLASSTYPE_BINDINGS): Delete.
+	* name-lookup.c (lookup_field_1): Restore binary search.
+	(sorted_fields_type_new, count_fields,
+	add_fields_to_record_type, add_enum_fields_to_record_type): Restore
+	(set_class_bindings): Revert.
+	(insert_late_enum_def_binding): Restore field_vec insertion.
+
 2017-09-01  Jakub Jelinek  <jakub@redhat.com>
 
 	PR c/81887
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 41c48ec..d8fe953 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -2007,10 +2007,10 @@ struct GTY(()) lang_type {
      as a list of adopted protocols or a pointer to a corresponding
      @interface.  See objc/objc-act.h for details.  */
   tree objc_info;
-
-  /* Map from IDENTIFIER nodes to DECLS.  */
-  hash_map<lang_identifier *, tree> *bindings;
-
+  /* sorted_fields is sorted based on a pointer, so we need to be able
+     to resort it if pointers get rearranged.  */
+  struct sorted_fields_type * GTY ((reorder ("resort_sorted_fields")))
+    sorted_fields;
   /* FIXME reuse another field?  */
   tree lambda_expr;
 };
@@ -3236,9 +3236,10 @@ extern void decl_shadowed_for_var_insert (tree, tree);
    && TREE_CODE (TYPE_NAME (NODE)) == TYPE_DECL	\
    && TYPE_DECL_ALIAS_P (TYPE_NAME (NODE)))
 
-/* The binding map for a class (not always present).  */
-#define CLASSTYPE_BINDINGS(NODE) \
-  (LANG_TYPE_CLASS_CHECK (NODE)->bindings)
+/* For a class type: if this structure has many fields, we'll sort them
+   and put them into a TREE_VEC.  */
+#define CLASSTYPE_SORTED_FIELDS(NODE) \
+  (LANG_TYPE_CLASS_CHECK (NODE)->sorted_fields)
 
 /* If non-NULL for a VAR_DECL, FUNCTION_DECL, TYPE_DECL or
    TEMPLATE_DECL, the entity is either a template specialization (if
diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
index 4c8117c..7cd8f4a 100644
--- a/gcc/cp/name-lookup.c
+++ b/gcc/cp/name-lookup.c
@@ -1183,33 +1183,58 @@ lookup_fnfields_slot_nolazy (tree type, tree name)
 tree
 lookup_field_1 (tree type, tree name, bool want_type)
 {
-  tree field = NULL_TREE;
+  tree field;
 
   gcc_assert (identifier_p (name) && RECORD_OR_UNION_TYPE_P (type));
 
-  if (CLASSTYPE_BINDINGS (type))
+  if (CLASSTYPE_SORTED_FIELDS (type))
     {
-      tree *slot = CLASSTYPE_BINDINGS (type)->get (name);
+      tree *fields = &CLASSTYPE_SORTED_FIELDS (type)->elts[0];
+      int lo = 0, hi = CLASSTYPE_SORTED_FIELDS (type)->len;
+      int i;
 
-      if (slot)
+      while (lo < hi)
 	{
-	  field = *slot;
+	  i = (lo + hi) / 2;
 
-	  if (STAT_HACK_P (field))
+	  if (DECL_NAME (fields[i]) > name)
+	    hi = i;
+	  else if (DECL_NAME (fields[i]) < name)
+	    lo = i + 1;
+	  else
 	    {
+	      field = NULL_TREE;
+
+	      /* We might have a nested class and a field with the
+		 same name; we sorted them appropriately via
+		 field_decl_cmp, so just look for the first or last
+		 field with this name.  */
 	      if (want_type)
-		field = STAT_TYPE (field);
+		{
+		  do
+		    field = fields[i--];
+		  while (i >= lo && DECL_NAME (fields[i]) == name);
+		  if (!DECL_DECLARES_TYPE_P (field))
+		    field = NULL_TREE;
+		}
 	      else
-		field = STAT_DECL (field);
-	    }
+		{
+		  do
+		    field = fields[i++];
+		  while (i < hi && DECL_NAME (fields[i]) == name);
+		}
+
+	      if (field)
+	      	{
+	      	  field = strip_using_decl (field);
+	      	  if (is_overloaded_fn (field))
+	      	    field = NULL_TREE;
+	      	}
 
-	  field = strip_using_decl (field);
-	  if (OVL_P (field))
-	    field = NULL_TREE;
-	  else if (want_type && !DECL_DECLARES_TYPE_P (field))
-	    field = NULL_TREE;
+	      return field;
+	    }
 	}
-      return field;
+      return NULL_TREE;
     }
 
   field = TYPE_FIELDS (type);
@@ -1287,62 +1312,113 @@ lookup_fnfields_slot (tree type, tree name)
   return lookup_fnfields_slot_nolazy (type, name);
 }
 
-/* Add DECL into MAP under NAME.  Collisions fail silently.  Doesn't
-   do sophisticated collision checking.  Deals with STAT_HACK.  */
+/* Allocate and return an instance of struct sorted_fields_type with
+   N fields.  */
 
-static void
-add_class_member (hash_map<lang_identifier *, tree> *map, tree name, tree decl)
+static struct sorted_fields_type *
+sorted_fields_type_new (int n)
 {
-  bool existed;
-  tree *slot = &map->get_or_insert (name, &existed);
-  if (!existed)
-    *slot = decl;
-  else if (TREE_CODE (*slot) == TYPE_DECL && DECL_ARTIFICIAL (*slot))
-    *slot = stat_hack (decl, *slot);
-  else if (TREE_CODE (decl) == TYPE_DECL && DECL_ARTIFICIAL (decl))
-    *slot = stat_hack (*slot, decl);
+  struct sorted_fields_type *sft;
+  sft = (sorted_fields_type *) ggc_internal_alloc (sizeof (sorted_fields_type)
+				      + n * sizeof (tree));
+  sft->len = n;
 
-  /* Else ignore collision.  */
+  return sft;
 }
 
-/* Insert the chain FIELDS into MAP.  */
+/* Subroutine of insert_into_classtype_sorted_fields.  Recursively
+   count the number of fields in TYPE, including anonymous union
+   members.  */
 
-static void
-add_class_members (hash_map<lang_identifier *, tree> *map, tree fields)
+static int
+count_fields (tree fields)
 {
-  for (tree field = fields; field; field = DECL_CHAIN (field))
+  tree x;
+  int n_fields = 0;
+  for (x = fields; x; x = DECL_CHAIN (x))
     {
-      if (TREE_CODE (field) == FIELD_DECL
-	  && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
-	add_class_members (map, TYPE_FIELDS (TREE_TYPE (field)));
-      else if (DECL_NAME (field))
-	add_class_member (map, DECL_NAME (field), field);
+      if (DECL_DECLARES_FUNCTION_P (x))
+	/* Functions are dealt with separately.  */;
+      else 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;
 }
 
-/* Create the binding map of KLASS and insert FIELDS.  */
+/* Subroutine of insert_into_classtype_sorted_fields.  Recursively add
+   all the fields in the TREE_LIST FIELDS to the SORTED_FIELDS_TYPE
+   elts, starting at offset IDX.  */
+
+static int
+add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec,
+			   int idx)
+{
+  tree x;
+  for (x = fields; x; x = DECL_CHAIN (x))
+    {
+      if (DECL_DECLARES_FUNCTION_P (x))
+	/* Functions are handled separately.  */;
+      else if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
+	idx = add_fields_to_record_type (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
+      else
+	field_vec->elts[idx++] = x;
+    }
+  return idx;
+}
+
+/* Add all of the enum values of ENUMTYPE, to the FIELD_VEC elts,
+   starting at offset IDX.  */
+
+static int
+add_enum_fields_to_record_type (tree enumtype,
+				struct sorted_fields_type *field_vec,
+				int idx)
+{
+  tree values;
+  for (values = TYPE_VALUES (enumtype); values; values = TREE_CHAIN (values))
+    field_vec->elts[idx++] = TREE_VALUE (values);
+  return idx;
+}
+
+/* Insert FIELDS into KLASS for the sorted case if the FIELDS count is
+   big enough.  */
 
 void 
 set_class_bindings (tree klass, tree fields)
 {
-  gcc_assert (!CLASSTYPE_BINDINGS (klass));
-
-  CLASSTYPE_BINDINGS (klass)
-    = hash_map<lang_identifier *, tree>::create_ggc (8);
-  add_class_members (CLASSTYPE_BINDINGS (klass), fields);
+  int n_fields = count_fields (fields);
+  if (n_fields >= 8)
+    {
+      struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);
+      add_fields_to_record_type (fields, field_vec, 0);
+      qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);
+      CLASSTYPE_SORTED_FIELDS (klass) = field_vec;
+    }
 }
 
-/* Insert lately defined enum ENUMTYPE into T for the sorted case.  */
+/* Insert lately defined enum ENUMTYPE into KLASS for the sorted case.  */
 
 void
 insert_late_enum_def_bindings (tree klass, tree enumtype)
 {
-  hash_map<lang_identifier *, tree> *map = CLASSTYPE_BINDINGS (klass);
+  struct sorted_fields_type *sorted_fields = CLASSTYPE_SORTED_FIELDS (klass);
+  if (sorted_fields)
+    {
+      int i;
+      int n_fields
+	= list_length (TYPE_VALUES (enumtype)) + sorted_fields->len;
+      struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);
+      
+      for (i = 0; i < sorted_fields->len; ++i)
+	field_vec->elts[i] = sorted_fields->elts[i];
 
-  for (tree values = TYPE_VALUES (enumtype);
-       values; values = TREE_CHAIN (values))
-    add_class_member (map, DECL_NAME (TREE_VALUE (values)),
-		      TREE_VALUE (values));
+      add_enum_fields_to_record_type (enumtype, field_vec,
+				      sorted_fields->len);
+      qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);
+      CLASSTYPE_SORTED_FIELDS (klass) = field_vec;
+    }
 }
 
 /* Compute the chain index of a binding_entry given the HASH value of its