From patchwork Mon Aug 28 16:29:03 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 806650 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-461028-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="dgS/17Xx"; 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 3xgy081ZJQz9sNr for ; Tue, 29 Aug 2017 02:29:28 +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=cq6j9o9QVPALuej3jFPV5ciXHpfsg/b0XJGLToOgFMxOhxpfQs fpLsRewsTVj7D36MN8FmVyRko/sd2po3SH5Jn61h0HKW8RmoJyKNhZASkL4+GUpI Pca2ggiDTwIszD9Edahy0K9ESwRaQz5MHG+bypV5jNrJi62138sfoJUrA= 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=QX3QDH3fJf9B10dUnlebWJL/fOg=; b=dgS/17XxCTWpI4EDVx9D QwLkpKvkhD4npRTMa7qR2SMGqHVYE/xDLtR+lq7EPhoak9+Xj8eFPddVTi+w0B/B GkjDy2zr6d1wTq9AgiVggwZG7HbjWp/E6pQw+IjSwu+FhjtJgEe0Wt0/SW7vndoz qMQTnivING+EaPtPeRVjShE= Received: (qmail 83290 invoked by alias); 28 Aug 2017 16:29:18 -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 82632 invoked by uid 89); 28 Aug 2017 16:29:17 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-16.1 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=sophisticated X-HELO: mail-yw0-f175.google.com Received: from mail-yw0-f175.google.com (HELO mail-yw0-f175.google.com) (209.85.161.175) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 28 Aug 2017 16:29:07 +0000 Received: by mail-yw0-f175.google.com with SMTP id h127so5007504ywf.3 for ; Mon, 28 Aug 2017 09:29:07 -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=J2cBrIXasko4suqcKWs2r4f0oJavEhp3vuCn8RTEcBU=; b=IhAjROCmrhWpJIgsIvfxWZ67xIQwSH5yBoU81HT9tMMr88odujYsd4Ks8Rvv9xE/x9 kBz2kjddRscUOonT9b+z5M8shJMX5t/eeVhhleH1zvRQ6aH/B097x5pv3RPfPXZC2bTT NspOzZ0KQXao03J/k0n2hHvQKQ9hTnNt/IYEWTZ32y8E2S6x+y3cWA+v0NqGpwn317sN XSr604jG6bIywUJnivJUkP9dmn/tsJb7dWT6iDyXnMkmej9EYXcDUhf6GA9jAl81u16r Lf2QvYpJmRB9o8h8GvCvcfnJefV5sC/SWTgNSvZn9rGunMtYUPN77wYfMwl0L31Op8Sb qtAg== X-Gm-Message-State: AHYfb5iGc8mX9XBvJPmtwLKt+6vx2+IymQNT9UWChotzzd96LtZfDKCQ bOM8Odgl20TBpA== X-Received: by 10.37.163.2 with SMTP id d2mr961448ybi.117.1503937745631; Mon, 28 Aug 2017 09:29:05 -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 m5sm292396ywi.6.2017.08.28.09.29.04 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 28 Aug 2017 09:29:04 -0700 (PDT) To: GCC Patches From: Nathan Sidwell 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; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 This patch replaces the sorted field vector with a hash map. Lookup for non-function members of a complete class is now O(1), not O(log(n)). We still do linear lookup when the class is incomplete. Fixing that is still on the todo list. This permits moving a bunch of sorted_field_vec handling from c-common to the c FE, and I'll post that in a subsequent patch. committed to trunk. nathan 2017-08-28 Nathan Sidwell * cp-tree.h (lang_type): Replace sorted_fields vector with bindings map. (CLASSTYPE_SORTED_FIELDS): Delete. (CLASSTYPE_BINDINGS): New. * decl.c (finish_enum_value_list): Swap args of insert_late_enum_def_bindings. * name-lookup.c (lookup_field_1): Replace binary search of sorted fields with map->get. (sorted_fields_type_new, count_fields, add_fields_to_record_type, add_enum_fields_to_record_type): Delete. (add_class_member, add_class_members): New. (set_class_bindings): Create map and insert. (insert_late_enum_def_binding): Swap parms. Use add_clasS_member. * ptree.c (cxx_print_type): Delete sorted fields printing. Index: cp-tree.h =================================================================== --- cp-tree.h (revision 251387) +++ cp-tree.h (working copy) @@ -2014,10 +2014,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; - /* 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; + + /* Map from IDENTIFIER nodes to DECLS. */ + hash_map *bindings; + /* FIXME reuse another field? */ tree lambda_expr; }; @@ -3243,10 +3243,9 @@ extern void decl_shadowed_for_var_insert && TREE_CODE (TYPE_NAME (NODE)) == TYPE_DECL \ && TYPE_DECL_ALIAS_P (TYPE_NAME (NODE))) -/* 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) +/* The binding map for a class (not always present). */ +#define CLASSTYPE_BINDINGS(NODE) \ + (LANG_TYPE_CLASS_CHECK (NODE)->bindings) /* If non-NULL for a VAR_DECL, FUNCTION_DECL, TYPE_DECL or TEMPLATE_DECL, the entity is either a template specialization (if Index: decl.c =================================================================== --- decl.c (revision 251387) +++ decl.c (working copy) @@ -14316,7 +14316,8 @@ finish_enum_value_list (tree enumtype) && COMPLETE_TYPE_P (current_class_type) && UNSCOPED_ENUM_P (enumtype)) { - insert_late_enum_def_bindings (enumtype, current_class_type); + insert_late_enum_def_bindings (current_class_type, enumtype); + /* TYPE_FIELDS needs fixup. */ fixup_type_variants (current_class_type); } Index: name-lookup.c =================================================================== --- name-lookup.c (revision 251387) +++ name-lookup.c (working copy) @@ -1183,58 +1183,33 @@ lookup_fnfields_slot_nolazy (tree type, tree lookup_field_1 (tree type, tree name, bool want_type) { - tree field; + tree field = NULL_TREE; gcc_assert (identifier_p (name) && RECORD_OR_UNION_TYPE_P (type)); - if (CLASSTYPE_SORTED_FIELDS (type)) + if (CLASSTYPE_BINDINGS (type)) { - 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; + tree *slot = CLASSTYPE_BINDINGS (type)->get (name); + + if (slot) + { + field = *slot; - /* 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 (STAT_HACK_P (field)) + { if (want_type) - { - do - field = fields[i--]; - while (i >= lo && DECL_NAME (fields[i]) == name); - if (!DECL_DECLARES_TYPE_P (field)) - field = NULL_TREE; - } + field = STAT_TYPE (field); else - { - 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; - } - - return field; + field = STAT_DECL (field); } + + 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 NULL_TREE; + return field; } field = TYPE_FIELDS (type); @@ -1312,113 +1287,62 @@ lookup_fnfields_slot (tree type, tree na return lookup_fnfields_slot_nolazy (type, name); } -/* Allocate and return an instance of struct sorted_fields_type with - N fields. */ +/* Add DECL into MAP under NAME. Collisions fail silently. Doesn't + do sophisticated collision checking. Deals with STAT_HACK. */ -static struct sorted_fields_type * -sorted_fields_type_new (int n) +static void +add_class_member (hash_map *map, tree name, tree decl) { - struct sorted_fields_type *sft; - sft = (sorted_fields_type *) ggc_internal_alloc (sizeof (sorted_fields_type) - + n * sizeof (tree)); - sft->len = 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); - return sft; -} - -/* Subroutine of insert_into_classtype_sorted_fields. Recursively - count the number of fields in TYPE, including anonymous union - members. */ - -static int -count_fields (tree fields) -{ - tree x; - int n_fields = 0; - for (x = fields; x; x = DECL_CHAIN (x)) - { - 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; + /* Else ignore collision. */ } -/* 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. */ +/* Insert the chain FIELDS into MAP. */ -static int -add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec, - int idx) +static void +add_class_members (hash_map *map, tree fields) { - tree x; - for (x = fields; x; x = DECL_CHAIN (x)) + for (tree field = fields; field; field = DECL_CHAIN (field)) { - 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; + 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); } - 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 T for the sorted case if the FIELDS count is - equal to THRESHOLD or greater than THRESHOLD. */ +/* Create the binding map of KLASS and insert FIELDS. */ void set_class_bindings (tree klass, tree 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; - } + gcc_assert (!CLASSTYPE_BINDINGS (klass)); + + CLASSTYPE_BINDINGS (klass) + = hash_map::create_ggc (8); + add_class_members (CLASSTYPE_BINDINGS (klass), fields); } /* Insert lately defined enum ENUMTYPE into T for the sorted case. */ void -insert_late_enum_def_bindings (tree enumtype, tree t) +insert_late_enum_def_bindings (tree klass, tree enumtype) { - struct sorted_fields_type *sorted_fields = CLASSTYPE_SORTED_FIELDS (t); - 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 (t) = field_vec; - } + 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)); } /* Compute the chain index of a binding_entry given the HASH value of its Index: ptree.c =================================================================== --- ptree.c (revision 251385) +++ ptree.c (working copy) @@ -151,9 +151,6 @@ cxx_print_type (FILE *file, tree node, i fputs (" delete[]", file); if (TYPE_HAS_COPY_ASSIGN (node)) fputs (" this=(X&)", file); - if (CLASSTYPE_SORTED_FIELDS (node)) - fprintf (file, " sorted-fields %p", - (void *) CLASSTYPE_SORTED_FIELDS (node)); if (TREE_CODE (node) == RECORD_TYPE) {