{"id":808676,"url":"http://patchwork.ozlabs.org/api/1.2/patches/808676/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/aeea0050-7892-9386-64d1-8115dbd851d8@acm.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/1.2/projects/17/?format=json","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":"","list_archive_url":null,"date":"2017-09-01T13:05:59","name":"[C++] restore CLASSTYPE_SORTED_FIELDS","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"a2b805d47d06c471549916af4491bb33853ed691","submitter":{"id":9970,"url":"http://patchwork.ozlabs.org/api/1.2/people/9970/?format=json","name":"Nathan Sidwell","email":"nathan@acm.org"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/aeea0050-7892-9386-64d1-8115dbd851d8@acm.org/mbox/","series":[{"id":1021,"url":"http://patchwork.ozlabs.org/api/1.2/series/1021/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=1021","date":"2017-09-01T13:05:59","name":"[C++] restore CLASSTYPE_SORTED_FIELDS","version":1,"mbox":"http://patchwork.ozlabs.org/series/1021/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/808676/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/808676/checks/","tags":{},"related":[],"headers":{"Return-Path":"","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-461284-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"hQA/smSa\"; 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 3xkKHw6nqCz9t1t\n\tfor ;\n\tFri, 1 Sep 2017 23:06:20 +1000 (AEST)","(qmail 15096 invoked by alias); 1 Sep 2017 13:06:13 -0000","(qmail 15036 invoked by uid 89); 1 Sep 2017 13:06:12 -0000","from mail-yw0-f172.google.com (HELO mail-yw0-f172.google.com)\n\t(209.85.161.172) by sourceware.org\n\t(qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tFri, 01 Sep 2017 13:06:03 +0000","by mail-yw0-f172.google.com with SMTP id s62so822298ywg.0 for\n\t; Fri, 01 Sep 2017 06:06:03 -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 c1sm40184ywh.61.2017.09.01.06.06.00\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256\n\tbits=128/128); Fri, 01 Sep 2017 06:06:01 -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=vfkip4gwoGT0ByzHuaAIoQatJf+GMTdQ+Wz7v+FWniiuhoXu5s\n\t+xj6vdH25om5deIB46E1YxMHLpXq3mMvBGg+qJueZnirsFEpMexeetJjL/ALm9GS\n\tVzNz34I8/IET/zZK+Mj2bTTnOzS3cQKjbp9CZLaVIg3vLDOMtBWB7GSoc=","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=mRsih5gvMk0vPzDhol/scn1630w=; b=hQA/smSa8xI1MLVCdZi1\n\t8P4ua/qi7nFT+r1jsI8A59UbfDZhkF1y555HyCKHL+ujgi8ihejfHyJECL2syXlc\n\tJcUlgL3Yk/NEpJSgeqenoJpCuVQxC/8EcMcMuc1x4EkhWlr+YC++VcIpQHUwJuv1\n\tqGd91E3C9JtpKXsrMKmn9DE=","Mailing-List":"contact gcc-patches-help@gcc.gnu.org; run by ezmlm","Precedence":"bulk","List-Id":"","List-Unsubscribe":"","List-Archive":"","List-Post":"","List-Help":"","Sender":"gcc-patches-owner@gcc.gnu.org","X-Virus-Found":"No","X-Spam-SWARE-Status":"No, score=-15.6 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, RCVD_IN_SORBS_SPAM,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=Doesnt, Doesn't,\n\tsidwell, Sidwell","X-HELO":"mail-yw0-f172.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=woalgmXp9Ob8zkzi0ltdCOLvcQu9oslMiJRETKBA2Q0=;\n\tb=B4vkVSDq/KyP2yy0eTUVQy+Jh2DOdp3j78WfFCY8B8Fz9Lpop9GeXDEttFbsdEY52K\n\tPLBWidewKnnzjnlrGpS4vshYGe5c+nDIX32dHiieenaLaHhQZO91AhqLif+jPQoDxswF\n\tABUa2ckECx7GNnq5+5OM+++Ox2Uwl3FpTN2+sjppyG7zKtzZP3MMgz63jMFewfc5i6QG\n\tve2vqV1I+R/LQZf5WvpsPo+dNLJ/onDdFNs6Jimsl/7qZJwMKiwdSgg60WZL1D8YIMR6\n\tbRo2Sz/cAXp55aNTdvcQZeus3h5WxkQG6wzOje5EbsgH9e5YvH7Zp9PlDygLNRzV33dl\n\tT1cA==","X-Gm-Message-State":"AHPjjUj3xwuNdv2APTc7fHdB0RMlWPfgj2BAPexqSurUoZbVBOj8uCXS\t9U465GWge8mH1Dmh","X-Google-Smtp-Source":"ADKCNb76KZC3lJHoxKCco++eYxxvuJhmiHW2LCJfKwKceP11RDWcfimPLrwHvKpW1X98Kq2vba2Hbw==","X-Received":"by 10.129.62.34 with SMTP id l34mr1562212ywa.180.1504271161961;\n\tFri, 01 Sep 2017 06:06:01 -0700 (PDT)","To":"GCC Patches ","From":"Nathan Sidwell ","Subject":"[C++ PATCH] restore CLASSTYPE_SORTED_FIELDS","Message-ID":"","Date":"Fri, 1 Sep 2017 09:05:59 -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=\"------------840217DDC30200D833A78DA4\""},"content":"I've reverted last weeks conversion of CLASSTYPE_SORTED_FIELDS to a \nhash-map. It became clear this was a rat hole I have insufficient time \nto go down.\n\nI'm now attacking the problem from another direction, which should be \nmore fruitful.\n\nnathan","diff":"2017-09-01 Nathan Sidwell \n\n\tRevert 2017-08-28 Nathan Sidwell \n\tRestore sorted_fields vector.\n\t* cp-tree.h (lang_type): Restore sorted_fields vector.\n\t(CLASSTYPE_SORTED_FIELDS): Restore.\n\t(CLASSTYPE_BINDINGS): Delete.\n\t* name-lookup.c (lookup_field_1): Restore binary search.\n\t(sorted_fields_type_new, count_fields,\n\tadd_fields_to_record_type, add_enum_fields_to_record_type): Restore\n\t(set_class_bindings): Revert.\n\t(insert_late_enum_def_binding): Restore field_vec insertion.\n\nIndex: cp-tree.h\n===================================================================\n--- cp-tree.h\t(revision 251585)\n+++ cp-tree.h\t(working copy)\n@@ -2007,10 +2007,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-\n- /* Map from IDENTIFIER nodes to DECLS. */\n- hash_map *bindings;\n-\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 /* FIXME reuse another field? */\n tree lambda_expr;\n };\n@@ -3236,9 +3236,10 @@ 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-/* The binding map for a class (not always present). */\n-#define CLASSTYPE_BINDINGS(NODE) \\\n- (LANG_TYPE_CLASS_CHECK (NODE)->bindings)\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 \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: name-lookup.c\n===================================================================\n--- name-lookup.c\t(revision 251585)\n+++ name-lookup.c\t(working copy)\n@@ -1183,33 +1183,58 @@ lookup_fnfields_slot_nolazy (tree type,\n tree\n lookup_field_1 (tree type, tree name, bool want_type)\n {\n- tree field = NULL_TREE;\n+ tree field;\n \n gcc_assert (identifier_p (name) && RECORD_OR_UNION_TYPE_P (type));\n \n- if (CLASSTYPE_BINDINGS (type))\n+ if (CLASSTYPE_SORTED_FIELDS (type))\n {\n- tree *slot = CLASSTYPE_BINDINGS (type)->get (name);\n-\n- if (slot)\n-\t{\n-\t field = *slot;\n-\n-\t if (STAT_HACK_P (field))\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+\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 (want_type)\n-\t\tfield = STAT_TYPE (field);\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 else\n-\t\tfield = STAT_DECL (field);\n-\t }\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 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 return field;\n+\t }\n \t}\n- return field;\n+ return NULL_TREE;\n }\n \n field = TYPE_FIELDS (type);\n@@ -1287,62 +1312,113 @@ lookup_fnfields_slot (tree type, tree na\n return lookup_fnfields_slot_nolazy (type, name);\n }\n \n-/* Add DECL into MAP under NAME. Collisions fail silently. Doesn't\n- do sophisticated collision checking. Deals with STAT_HACK. */\n+/* Allocate and return an instance of struct sorted_fields_type with\n+ N fields. */\n \n-static void\n-add_class_member (hash_map *map, tree name, tree decl)\n+static struct sorted_fields_type *\n+sorted_fields_type_new (int n)\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+ 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 \n- /* Else ignore collision. */\n+ return sft;\n }\n \n-/* Insert the chain FIELDS into MAP. */\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 void\n-add_class_members (hash_map *map, tree fields)\n+static int\n+count_fields (tree fields)\n {\n- for (tree field = fields; field; field = DECL_CHAIN (field))\n+ tree x;\n+ int n_fields = 0;\n+ for (x = fields; x; x = DECL_CHAIN (x))\n {\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+ 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 }\n \n-/* Create the binding map of KLASS and insert FIELDS. */\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+\n+static int\n+add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec,\n+\t\t\t int idx)\n+{\n+ tree x;\n+ for (x = fields; x; x = DECL_CHAIN (x))\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+ }\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 KLASS for the sorted case if the FIELDS count is\n+ big enough. */\n \n void \n set_class_bindings (tree klass, tree fields)\n {\n- gcc_assert (!CLASSTYPE_BINDINGS (klass));\n-\n- CLASSTYPE_BINDINGS (klass)\n- = hash_map::create_ggc (8);\n- add_class_members (CLASSTYPE_BINDINGS (klass), fields);\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 }\n \n-/* Insert lately defined enum ENUMTYPE into T for the sorted case. */\n+/* Insert lately defined enum ENUMTYPE into KLASS for the sorted case. */\n \n void\n insert_late_enum_def_bindings (tree klass, tree enumtype)\n {\n- hash_map *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+ struct sorted_fields_type *sorted_fields = CLASSTYPE_SORTED_FIELDS (klass);\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 (klass) = field_vec;\n+ }\n }\n \n /* Compute the chain index of a binding_entry given the HASH value of its\n","prefixes":["C++"]}