Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/806650/?format=api
{ "id": 806650, "url": "http://patchwork.ozlabs.org/api/patches/806650/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org/", "project": { "id": 17, "url": "http://patchwork.ozlabs.org/api/projects/17/?format=api", "name": "GNU Compiler Collection", "link_name": "gcc", "list_id": "gcc-patches.gcc.gnu.org", "list_email": "gcc-patches@gcc.gnu.org", "web_url": null, "scm_url": null, "webscm_url": null, "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org>", "list_archive_url": null, "date": "2017-08-28T16:29:03", "name": "[C++] Kill CLASSTYPE_SORTED_FIELDS", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "a5023ed1295852bb35bd3448b48d16e75773440c", "submitter": { "id": 9970, "url": "http://patchwork.ozlabs.org/api/people/9970/?format=api", "name": "Nathan Sidwell", "email": "nathan@acm.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/gcc/patch/70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org/mbox/", "series": [ { "id": 210, "url": "http://patchwork.ozlabs.org/api/series/210/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/list/?series=210", "date": "2017-08-28T16:29:03", "name": "[C++] Kill CLASSTYPE_SORTED_FIELDS", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/210/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/806650/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/806650/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<gcc-patches-return-461028-incoming=patchwork.ozlabs.org@gcc.gnu.org>", "X-Original-To": "incoming@patchwork.ozlabs.org", "Delivered-To": [ "patchwork-incoming@bilbo.ozlabs.org", "mailing list gcc-patches@gcc.gnu.org" ], "Authentication-Results": [ "ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org\n\t(client-ip=209.132.180.131; helo=sourceware.org;\n\tenvelope-from=gcc-patches-return-461028-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=<UNKNOWN>)", "ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"dgS/17Xx\"; dkim-atps=neutral", "sourceware.org; auth=none" ], "Received": [ "from sourceware.org (server1.sourceware.org [209.132.180.131])\n\t(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256\n\tbits)) (No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 3xgy081ZJQz9sNr\n\tfor <incoming@patchwork.ozlabs.org>;\n\tTue, 29 Aug 2017 02:29:28 +1000 (AEST)", "(qmail 83290 invoked by alias); 28 Aug 2017 16:29:18 -0000", "(qmail 82632 invoked by uid 89); 28 Aug 2017 16:29:17 -0000", "from mail-yw0-f175.google.com (HELO mail-yw0-f175.google.com)\n\t(209.85.161.175) by sourceware.org\n\t(qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tMon, 28 Aug 2017 16:29:07 +0000", "by mail-yw0-f175.google.com with SMTP id h127so5007504ywf.3 for\n\t<gcc-patches@gcc.gnu.org>; Mon, 28 Aug 2017 09:29:07 -0700 (PDT)", "from ?IPv6:2620:10d:c0a3:20fb:7500:e7fb:4a6f:2254?\n\t([2620:10d:c091:200::1:d19a]) by smtp.googlemail.com with\n\tESMTPSA id m5sm292396ywi.6.2017.08.28.09.29.04\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256\n\tbits=128/128); Mon, 28 Aug 2017 09:29:04 -0700 (PDT)" ], "DomainKey-Signature": "a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:to\n\t:from:subject:message-id:date:mime-version:content-type; q=dns;\n\ts=default; b=cq6j9o9QVPALuej3jFPV5ciXHpfsg/b0XJGLToOgFMxOhxpfQs\n\tfpLsRewsTVj7D36MN8FmVyRko/sd2po3SH5Jn61h0HKW8RmoJyKNhZASkL4+GUpI\n\tPca2ggiDTwIszD9Edahy0K9ESwRaQz5MHG+bypV5jNrJi62138sfoJUrA=", "DKIM-Signature": "v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:to\n\t:from:subject:message-id:date:mime-version:content-type; s=\n\tdefault; bh=QX3QDH3fJf9B10dUnlebWJL/fOg=; b=dgS/17XxCTWpI4EDVx9D\n\tQwLkpKvkhD4npRTMa7qR2SMGqHVYE/xDLtR+lq7EPhoak9+Xj8eFPddVTi+w0B/B\n\tGkjDy2zr6d1wTq9AgiVggwZG7HbjWp/E6pQw+IjSwu+FhjtJgEe0Wt0/SW7vndoz\n\tqMQTnivING+EaPtPeRVjShE=", "Mailing-List": "contact gcc-patches-help@gcc.gnu.org; run by ezmlm", "Precedence": "bulk", "List-Id": "<gcc-patches.gcc.gnu.org>", "List-Unsubscribe": "<mailto:gcc-patches-unsubscribe-incoming=patchwork.ozlabs.org@gcc.gnu.org>", "List-Archive": "<http://gcc.gnu.org/ml/gcc-patches/>", "List-Post": "<mailto:gcc-patches@gcc.gnu.org>", "List-Help": "<mailto:gcc-patches-help@gcc.gnu.org>", "Sender": "gcc-patches-owner@gcc.gnu.org", "X-Virus-Found": "No", "X-Spam-SWARE-Status": "No, score=-16.1 required=5.0 tests=BAYES_00,\n\tFREEMAIL_FROM, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3,\n\tKAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=sophisticated", "X-HELO": "mail-yw0-f175.google.com", "X-Google-DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net;\n\ts=20161025;\n\th=x-gm-message-state:sender:to:from:subject:message-id:date\n\t:user-agent:mime-version:content-language;\n\tbh=J2cBrIXasko4suqcKWs2r4f0oJavEhp3vuCn8RTEcBU=;\n\tb=IhAjROCmrhWpJIgsIvfxWZ67xIQwSH5yBoU81HT9tMMr88odujYsd4Ks8Rvv9xE/x9\n\tkBz2kjddRscUOonT9b+z5M8shJMX5t/eeVhhleH1zvRQ6aH/B097x5pv3RPfPXZC2bTT\n\tNspOzZ0KQXao03J/k0n2hHvQKQ9hTnNt/IYEWTZ32y8E2S6x+y3cWA+v0NqGpwn317sN\n\tXSr604jG6bIywUJnivJUkP9dmn/tsJb7dWT6iDyXnMkmej9EYXcDUhf6GA9jAl81u16r\n\tLf2QvYpJmRB9o8h8GvCvcfnJefV5sC/SWTgNSvZn9rGunMtYUPN77wYfMwl0L31Op8Sb\n\tqtAg==", "X-Gm-Message-State": "AHYfb5iGc8mX9XBvJPmtwLKt+6vx2+IymQNT9UWChotzzd96LtZfDKCQ\tbOM8Odgl20TBpA==", "X-Received": "by 10.37.163.2 with SMTP id d2mr961448ybi.117.1503937745631;\n\tMon, 28 Aug 2017 09:29:05 -0700 (PDT)", "To": "GCC Patches <gcc-patches@gcc.gnu.org>", "From": "Nathan Sidwell <nathan@acm.org>", "Subject": "[C++ PATCH] Kill CLASSTYPE_SORTED_FIELDS", "Message-ID": "<70b2cf9b-fa5e-9572-386a-bd36cf010862@acm.org>", "Date": "Mon, 28 Aug 2017 12:29:03 -0400", "User-Agent": "Mozilla/5.0 (X11; Linux x86_64;\n\trv:52.0) Gecko/20100101 Thunderbird/52.2.1", "MIME-Version": "1.0", "Content-Type": "multipart/mixed;\n\tboundary=\"------------7F7CAEBCBD5672300400C319\"" }, "content": "This patch replaces the sorted field vector with a hash map. Lookup for \nnon-function members of a complete class is now O(1), not O(log(n)). We \nstill do linear lookup when the class is incomplete. Fixing that is \nstill on the todo list.\n\nThis permits moving a bunch of sorted_field_vec handling from c-common \nto the c FE, and I'll post that in a subsequent patch.\n\ncommitted to trunk.\n\nnathan", "diff": "2017-08-28 Nathan Sidwell <nathan@acm.org>\n\n\t* cp-tree.h (lang_type): Replace sorted_fields vector with\n\tbindings map.\n\t(CLASSTYPE_SORTED_FIELDS): Delete.\n\t(CLASSTYPE_BINDINGS): New.\n\t* decl.c (finish_enum_value_list): Swap args of\n\tinsert_late_enum_def_bindings.\n\t* name-lookup.c (lookup_field_1): Replace binary search of sorted\n\tfields with map->get.\n\t(sorted_fields_type_new, count_fields,\n\tadd_fields_to_record_type, add_enum_fields_to_record_type): Delete.\n\t(add_class_member, add_class_members): New.\n\t(set_class_bindings): Create map and insert.\n\t(insert_late_enum_def_binding): Swap parms. Use add_clasS_member.\n\t* ptree.c (cxx_print_type): Delete sorted fields printing.\n\nIndex: cp-tree.h\n===================================================================\n--- cp-tree.h\t(revision 251387)\n+++ cp-tree.h\t(working copy)\n@@ -2014,10 +2014,10 @@ struct GTY(()) lang_type {\n as a list of adopted protocols or a pointer to a corresponding\n @interface. See objc/objc-act.h for details. */\n tree objc_info;\n- /* sorted_fields is sorted based on a pointer, so we need to be able\n- to resort it if pointers get rearranged. */\n- struct sorted_fields_type * GTY ((reorder (\"resort_sorted_fields\")))\n- sorted_fields;\n+\n+ /* Map from IDENTIFIER nodes to DECLS. */\n+ hash_map<lang_identifier *, tree> *bindings;\n+\n /* FIXME reuse another field? */\n tree lambda_expr;\n };\n@@ -3243,10 +3243,9 @@ extern void decl_shadowed_for_var_insert\n && TREE_CODE (TYPE_NAME (NODE)) == TYPE_DECL\t\\\n && TYPE_DECL_ALIAS_P (TYPE_NAME (NODE)))\n \n-/* For a class type: if this structure has many fields, we'll sort them\n- and put them into a TREE_VEC. */\n-#define CLASSTYPE_SORTED_FIELDS(NODE) \\\n- (LANG_TYPE_CLASS_CHECK (NODE)->sorted_fields)\n+/* The binding map for a class (not always present). */\n+#define CLASSTYPE_BINDINGS(NODE) \\\n+ (LANG_TYPE_CLASS_CHECK (NODE)->bindings)\n \n /* If non-NULL for a VAR_DECL, FUNCTION_DECL, TYPE_DECL or\n TEMPLATE_DECL, the entity is either a template specialization (if\nIndex: decl.c\n===================================================================\n--- decl.c\t(revision 251387)\n+++ decl.c\t(working copy)\n@@ -14316,7 +14316,8 @@ finish_enum_value_list (tree enumtype)\n && COMPLETE_TYPE_P (current_class_type)\n && UNSCOPED_ENUM_P (enumtype))\n {\n- insert_late_enum_def_bindings (enumtype, current_class_type);\n+ insert_late_enum_def_bindings (current_class_type, enumtype);\n+ /* TYPE_FIELDS needs fixup. */\n fixup_type_variants (current_class_type);\n }\n \nIndex: name-lookup.c\n===================================================================\n--- name-lookup.c\t(revision 251387)\n+++ name-lookup.c\t(working copy)\n@@ -1183,58 +1183,33 @@ lookup_fnfields_slot_nolazy (tree type,\n tree\n lookup_field_1 (tree type, tree name, bool want_type)\n {\n- tree field;\n+ tree field = NULL_TREE;\n \n gcc_assert (identifier_p (name) && RECORD_OR_UNION_TYPE_P (type));\n \n- if (CLASSTYPE_SORTED_FIELDS (type))\n+ if (CLASSTYPE_BINDINGS (type))\n {\n- tree *fields = &CLASSTYPE_SORTED_FIELDS (type)->elts[0];\n- int lo = 0, hi = CLASSTYPE_SORTED_FIELDS (type)->len;\n- int i;\n-\n- while (lo < hi)\n-\t{\n-\t i = (lo + hi) / 2;\n-\n-\t if (DECL_NAME (fields[i]) > name)\n-\t hi = i;\n-\t else if (DECL_NAME (fields[i]) < name)\n-\t lo = i + 1;\n-\t else\n-\t {\n-\t field = NULL_TREE;\n+ tree *slot = CLASSTYPE_BINDINGS (type)->get (name);\n+\n+ if (slot)\n+\t{\n+\t field = *slot;\n \n-\t /* We might have a nested class and a field with the\n-\t\t same name; we sorted them appropriately via\n-\t\t field_decl_cmp, so just look for the first or last\n-\t\t field with this name. */\n+\t if (STAT_HACK_P (field))\n+\t {\n \t if (want_type)\n-\t\t{\n-\t\t do\n-\t\t field = fields[i--];\n-\t\t while (i >= lo && DECL_NAME (fields[i]) == name);\n-\t\t if (!DECL_DECLARES_TYPE_P (field))\n-\t\t field = NULL_TREE;\n-\t\t}\n+\t\tfield = STAT_TYPE (field);\n \t else\n-\t\t{\n-\t\t do\n-\t\t field = fields[i++];\n-\t\t while (i < hi && DECL_NAME (fields[i]) == name);\n-\t\t}\n-\n-\t if (field)\n-\t \t{\n-\t \t field = strip_using_decl (field);\n-\t \t if (is_overloaded_fn (field))\n-\t \t field = NULL_TREE;\n-\t \t}\n-\n-\t return field;\n+\t\tfield = STAT_DECL (field);\n \t }\n+\n+\t field = strip_using_decl (field);\n+\t if (OVL_P (field))\n+\t field = NULL_TREE;\n+\t else if (want_type && !DECL_DECLARES_TYPE_P (field))\n+\t field = NULL_TREE;\n \t}\n- return NULL_TREE;\n+ return field;\n }\n \n field = TYPE_FIELDS (type);\n@@ -1312,113 +1287,62 @@ lookup_fnfields_slot (tree type, tree na\n return lookup_fnfields_slot_nolazy (type, name);\n }\n \n-/* Allocate and return an instance of struct sorted_fields_type with\n- N fields. */\n+/* Add DECL into MAP under NAME. Collisions fail silently. Doesn't\n+ do sophisticated collision checking. Deals with STAT_HACK. */\n \n-static struct sorted_fields_type *\n-sorted_fields_type_new (int n)\n+static void\n+add_class_member (hash_map<lang_identifier *, tree> *map, tree name, tree decl)\n {\n- struct sorted_fields_type *sft;\n- sft = (sorted_fields_type *) ggc_internal_alloc (sizeof (sorted_fields_type)\n-\t\t\t\t + n * sizeof (tree));\n- sft->len = n;\n+ bool existed;\n+ tree *slot = &map->get_or_insert (name, &existed);\n+ if (!existed)\n+ *slot = decl;\n+ else if (TREE_CODE (*slot) == TYPE_DECL && DECL_ARTIFICIAL (*slot))\n+ *slot = stat_hack (decl, *slot);\n+ else if (TREE_CODE (decl) == TYPE_DECL && DECL_ARTIFICIAL (decl))\n+ *slot = stat_hack (*slot, decl);\n \n- return sft;\n-}\n-\n-/* Subroutine of insert_into_classtype_sorted_fields. Recursively\n- count the number of fields in TYPE, including anonymous union\n- members. */\n-\n-static int\n-count_fields (tree fields)\n-{\n- tree x;\n- int n_fields = 0;\n- for (x = fields; x; x = DECL_CHAIN (x))\n- {\n- if (DECL_DECLARES_FUNCTION_P (x))\n-\t/* Functions are dealt with separately. */;\n- else if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))\n-\tn_fields += count_fields (TYPE_FIELDS (TREE_TYPE (x)));\n- else\n-\tn_fields += 1;\n- }\n- return n_fields;\n+ /* Else ignore collision. */\n }\n \n-/* Subroutine of insert_into_classtype_sorted_fields. Recursively add\n- all the fields in the TREE_LIST FIELDS to the SORTED_FIELDS_TYPE\n- elts, starting at offset IDX. */\n+/* Insert the chain FIELDS into MAP. */\n \n-static int\n-add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec,\n-\t\t\t int idx)\n+static void\n+add_class_members (hash_map<lang_identifier *, tree> *map, tree fields)\n {\n- tree x;\n- for (x = fields; x; x = DECL_CHAIN (x))\n+ for (tree field = fields; field; field = DECL_CHAIN (field))\n {\n- if (DECL_DECLARES_FUNCTION_P (x))\n-\t/* Functions are handled separately. */;\n- else if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))\n-\tidx = add_fields_to_record_type (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);\n- else\n-\tfield_vec->elts[idx++] = x;\n+ if (TREE_CODE (field) == FIELD_DECL\n+\t && ANON_AGGR_TYPE_P (TREE_TYPE (field)))\n+\tadd_class_members (map, TYPE_FIELDS (TREE_TYPE (field)));\n+ else if (DECL_NAME (field))\n+\tadd_class_member (map, DECL_NAME (field), field);\n }\n- return idx;\n-}\n-\n-/* Add all of the enum values of ENUMTYPE, to the FIELD_VEC elts,\n- starting at offset IDX. */\n-\n-static int\n-add_enum_fields_to_record_type (tree enumtype,\n-\t\t\t\tstruct sorted_fields_type *field_vec,\n-\t\t\t\tint idx)\n-{\n- tree values;\n- for (values = TYPE_VALUES (enumtype); values; values = TREE_CHAIN (values))\n- field_vec->elts[idx++] = TREE_VALUE (values);\n- return idx;\n }\n \n-/* Insert FIELDS into T for the sorted case if the FIELDS count is\n- equal to THRESHOLD or greater than THRESHOLD. */\n+/* Create the binding map of KLASS and insert FIELDS. */\n \n void \n set_class_bindings (tree klass, tree fields)\n {\n- int n_fields = count_fields (fields);\n- if (n_fields >= 8)\n- {\n- struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);\n- add_fields_to_record_type (fields, field_vec, 0);\n- qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);\n- CLASSTYPE_SORTED_FIELDS (klass) = field_vec;\n- }\n+ gcc_assert (!CLASSTYPE_BINDINGS (klass));\n+\n+ CLASSTYPE_BINDINGS (klass)\n+ = hash_map<lang_identifier *, tree>::create_ggc (8);\n+ add_class_members (CLASSTYPE_BINDINGS (klass), fields);\n }\n \n /* Insert lately defined enum ENUMTYPE into T for the sorted case. */\n \n void\n-insert_late_enum_def_bindings (tree enumtype, tree t)\n+insert_late_enum_def_bindings (tree klass, tree enumtype)\n {\n- struct sorted_fields_type *sorted_fields = CLASSTYPE_SORTED_FIELDS (t);\n- if (sorted_fields)\n- {\n- int i;\n- int n_fields\n-\t= list_length (TYPE_VALUES (enumtype)) + sorted_fields->len;\n- struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);\n- \n- for (i = 0; i < sorted_fields->len; ++i)\n-\tfield_vec->elts[i] = sorted_fields->elts[i];\n-\n- add_enum_fields_to_record_type (enumtype, field_vec,\n-\t\t\t\t sorted_fields->len);\n- qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);\n- CLASSTYPE_SORTED_FIELDS (t) = field_vec;\n- }\n+ hash_map<lang_identifier *, tree> *map = CLASSTYPE_BINDINGS (klass);\n+\n+ for (tree values = TYPE_VALUES (enumtype);\n+ values; values = TREE_CHAIN (values))\n+ add_class_member (map, DECL_NAME (TREE_VALUE (values)),\n+\t\t TREE_VALUE (values));\n }\n \n /* Compute the chain index of a binding_entry given the HASH value of its\nIndex: ptree.c\n===================================================================\n--- ptree.c\t(revision 251385)\n+++ ptree.c\t(working copy)\n@@ -151,9 +151,6 @@ cxx_print_type (FILE *file, tree node, i\n fputs (\" delete[]\", file);\n if (TYPE_HAS_COPY_ASSIGN (node))\n fputs (\" this=(X&)\", file);\n- if (CLASSTYPE_SORTED_FIELDS (node))\n- fprintf (file, \" sorted-fields %p\",\n-\t (void *) CLASSTYPE_SORTED_FIELDS (node));\n \n if (TREE_CODE (node) == RECORD_TYPE)\n {\n", "prefixes": [ "C++" ] }