From patchwork Fri Sep 1 13:05:59 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 808676 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-461284-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="hQA/smSa"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3xkKHw6nqCz9t1t for ; Fri, 1 Sep 2017 23:06:20 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=vfkip4gwoGT0ByzHuaAIoQatJf+GMTdQ+Wz7v+FWniiuhoXu5s +xj6vdH25om5deIB46E1YxMHLpXq3mMvBGg+qJueZnirsFEpMexeetJjL/ALm9GS VzNz34I8/IET/zZK+Mj2bTTnOzS3cQKjbp9CZLaVIg3vLDOMtBWB7GSoc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=mRsih5gvMk0vPzDhol/scn1630w=; b=hQA/smSa8xI1MLVCdZi1 8P4ua/qi7nFT+r1jsI8A59UbfDZhkF1y555HyCKHL+ujgi8ihejfHyJECL2syXlc JcUlgL3Yk/NEpJSgeqenoJpCuVQxC/8EcMcMuc1x4EkhWlr+YC++VcIpQHUwJuv1 qGd91E3C9JtpKXsrMKmn9DE= Received: (qmail 15096 invoked by alias); 1 Sep 2017 13:06:13 -0000 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 Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 15036 invoked by uid 89); 1 Sep 2017 13:06:12 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-15.6 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=ham version=3.3.2 spammy=Doesnt, Doesn't, sidwell, Sidwell X-HELO: mail-yw0-f172.google.com Received: from mail-yw0-f172.google.com (HELO mail-yw0-f172.google.com) (209.85.161.172) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 01 Sep 2017 13:06:03 +0000 Received: by mail-yw0-f172.google.com with SMTP id s62so822298ywg.0 for ; Fri, 01 Sep 2017 06:06:03 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:to:from:subject:message-id:date :user-agent:mime-version:content-language; bh=woalgmXp9Ob8zkzi0ltdCOLvcQu9oslMiJRETKBA2Q0=; b=B4vkVSDq/KyP2yy0eTUVQy+Jh2DOdp3j78WfFCY8B8Fz9Lpop9GeXDEttFbsdEY52K PLBWidewKnnzjnlrGpS4vshYGe5c+nDIX32dHiieenaLaHhQZO91AhqLif+jPQoDxswF ABUa2ckECx7GNnq5+5OM+++Ox2Uwl3FpTN2+sjppyG7zKtzZP3MMgz63jMFewfc5i6QG ve2vqV1I+R/LQZf5WvpsPo+dNLJ/onDdFNs6Jimsl/7qZJwMKiwdSgg60WZL1D8YIMR6 bRo2Sz/cAXp55aNTdvcQZeus3h5WxkQG6wzOje5EbsgH9e5YvH7Zp9PlDygLNRzV33dl T1cA== X-Gm-Message-State: AHPjjUj3xwuNdv2APTc7fHdB0RMlWPfgj2BAPexqSurUoZbVBOj8uCXS 9U465GWge8mH1Dmh X-Google-Smtp-Source: ADKCNb76KZC3lJHoxKCco++eYxxvuJhmiHW2LCJfKwKceP11RDWcfimPLrwHvKpW1X98Kq2vba2Hbw== X-Received: by 10.129.62.34 with SMTP id l34mr1562212ywa.180.1504271161961; Fri, 01 Sep 2017 06:06:01 -0700 (PDT) Received: from ?IPv6:2620:10d:c0a3:20fb:7500:e7fb:4a6f:2254? ([2620:10d:c091:200::1:d19a]) by smtp.googlemail.com with ESMTPSA id c1sm40184ywh.61.2017.09.01.06.06.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 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; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 I've reverted last weeks conversion of CLASSTYPE_SORTED_FIELDS to a hash-map. It became clear this was a rat hole I have insufficient time to go down. I'm now attacking the problem from another direction, which should be more fruitful. nathan 2017-09-01 Nathan Sidwell Revert 2017-08-28 Nathan Sidwell 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. Index: cp-tree.h =================================================================== --- cp-tree.h (revision 251585) +++ cp-tree.h (working copy) @@ -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 *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_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 Index: name-lookup.c =================================================================== --- name-lookup.c (revision 251585) +++ name-lookup.c (working copy) @@ -1183,33 +1183,58 @@ lookup_fnfields_slot_nolazy (tree type, 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); - - if (slot) - { - field = *slot; - - if (STAT_HACK_P (field)) + tree *fields = &CLASSTYPE_SORTED_FIELDS (type)->elts[0]; + int lo = 0, hi = CLASSTYPE_SORTED_FIELDS (type)->len; + int i; + + while (lo < hi) + { + i = (lo + hi) / 2; + + 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 na 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 *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 *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::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 *map = CLASSTYPE_BINDINGS (klass); - - for (tree values = TYPE_VALUES (enumtype); - values; values = TREE_CHAIN (values)) - add_class_member (map, DECL_NAME (TREE_VALUE (values)), - TREE_VALUE (values)); + 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]; + + 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