From patchwork Wed Sep 6 15:36:56 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 810683 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-461625-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="KtWNv7Hi"; 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 3xnSPg0GPdz9t43 for ; Thu, 7 Sep 2017 01:37:10 +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=b2zdOIfP++zgM/iNFeMvEWpIvzyS45ovacAQwZpjUgigWh8B1a ieif7QBZdkV71c4V6osnmK9dcxS0gUvhHOqyqFLNW2XVQbk+p08NzT4+IibWhYsD W+0FnpHi53pADNjncbtMXmImwI7RFCfipzsHqvkG8nJCtlcGU9TigLLiA= 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=T0MxLr20s/ThODm0VJTaSPc5IS8=; b=KtWNv7Hi9p+buBs76m3b gtt4cI3xBI0rqRm1RmfFrrBUB0vbKh0TFBVc3wreSzrURnXZDPq6zQixIhohXGpt ixCFJFiwqyD+Nu/fI6IGBEaHVKX30wUKvHsOxq6AJN4lGb2h03k0eAgpqtV+x4zp q4zMyTDoWx6g7TtfbYSnEBg= Received: (qmail 127461 invoked by alias); 6 Sep 2017 15:37:03 -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 127446 invoked by uid 89); 6 Sep 2017 15:37:02 -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=punch X-HELO: mail-yw0-f169.google.com Received: from mail-yw0-f169.google.com (HELO mail-yw0-f169.google.com) (209.85.161.169) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 06 Sep 2017 15:37:00 +0000 Received: by mail-yw0-f169.google.com with SMTP id x144so22905864ywg.2 for ; Wed, 06 Sep 2017 08:37:00 -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=KU9scXMUlh1AtbDrMCslveqHffmgUP41dnpokRgN6F0=; b=UU2t5GtEoKxOFKFrChD1hMVL7ciK5qKITpyplSVfilprH19jwooXb3VdP/YD3fu3hI EKh7mgJ9+lMgX06f6JJYioGAsyJS9X2zuEs7mZ2hyhCA9R8BG2ZDG7fG39crSd3ssX4k aVjPvMhoVmy2NyL+P3wOJbv8irj11aT56tLhgMT6vWu9fpbwqJRoKg9EemQQqVQ5EyER A3x4yVm03LB4YePHBhqt2ZUFdcV6yryhmrWQX40+hSnBA9K3nbCMraCxMss2d8bpTUq0 FzjWFCNRvE3xaHnS5zx5/FJ1c/pr7amrQwPzovBrtszscHwV1+XvXlJ+G+HdQ87gc/Oa PL/g== X-Gm-Message-State: AHPjjUhzEqpHZBm2hufKKh8Q3S92cn01DT3oeMrYEwV3kgzNba+yPvay 0q5/T7/+2A51kg== X-Google-Smtp-Source: ADKCNb4VrSYsGbvD/2c14C/iKOO8qOl15HUQxnuUEsnPLBQEmsYY1jO+AV6QZin754AJ2WK9syJOFg== X-Received: by 10.129.193.74 with SMTP id e10mr2285886ywl.262.1504712218784; Wed, 06 Sep 2017 08:36:58 -0700 (PDT) Received: from ?IPv6:2620:10d:c0a3:20fb:7500:e7fb:4a6f:2254? ([2620:10d:c091:200::16fd]) by smtp.googlemail.com with ESMTPSA id y193sm46995ywy.5.2017.09.06.08.36.57 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 06 Sep 2017 08:36:58 -0700 (PDT) To: GCC Patches From: Nathan Sidwell Subject: [C++ PATCH] Merge fn and non-fn lookup interface Message-ID: <34c52ab3-a673-b1d8-7860-f8273bad5670@acm.org> Date: Wed, 6 Sep 2017 11:36:56 -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 merges the lookup of function and non-function member lookup into get_class_binding_direct. lookup_field_1 becomes an internal detail. We grow a tri-valued argument to get_class_binding_direct: <0 -- caller wants functions =0 -- caller wants whatever is bound >0 -- caller wants type_decl binding. This has the nice property that lookup_field_1's want_type argument maps onto the latter two values. The default is the first, which matches the existing get_class_binding usage. The two places where lookup_field_1 was being called directly are converted and were: 1) hierarchy searching. This functionality is swallowed by get_class_binding_direct, and it passes in the want_type argument. 2) named initializers. this now passes in 0. You'll notice this case is with the type being complete, so we now might get a binary search of METHOD_VEC that we didn;t before. This is going to be a short-lived performance regression. applied to trunk. I'm going to hold off the next patch as (a) it's more invasive, but (b) it steals the punch line from my name-lookup cauldron talk. nathan 2017-09-06 Nathan Sidwell * name-lookup.h (lookup_field_1): Delete. (get_class_binding_direct, get_class_binding): Add type_or_fns arg. * name-lookup.c (lookup_field_1): make static (method_vec_binary_search, method_vec_linear_search): New. Broken out of ... (get_class_binding_direct): ... here. Add TYPE_OR_FNS argument. Do complete search of this level. (get_class_binding): Adjust. * decl.c (reshape_init_class): Call get_class_binding. * search.c (lookup_field_r): Move field searching into get_class_binding_direct. Index: decl.c =================================================================== --- decl.c (revision 251782) +++ decl.c (working copy) @@ -5746,7 +5746,7 @@ reshape_init_class (tree type, reshape_i /* We already reshaped this. */ gcc_assert (d->cur->index == field); else if (TREE_CODE (d->cur->index) == IDENTIFIER_NODE) - field = lookup_field_1 (type, d->cur->index, /*want_type=*/false); + field = get_class_binding (type, d->cur->index, false); else { if (complain & tf_error) Index: name-lookup.c =================================================================== --- name-lookup.c (revision 251794) +++ name-lookup.c (working copy) @@ -1113,79 +1113,54 @@ extract_conversion_operator (tree fns, t return convs; } -/* TYPE is a class type. Return the member functions in the method - vector with name NAME. Does not lazily declare implicitly-declared - member functions. */ +/* Binary search of (ordered) METHOD_VEC for NAME. */ -tree -get_class_binding_direct (tree type, tree name) +static tree +method_vec_binary_search (vec *method_vec, tree name) { - vec *method_vec = CLASSTYPE_METHOD_VEC (type); - if (!method_vec) - return NULL_TREE; - - /* Conversion operators can only be found by the marker conversion - operator name. */ - bool conv_op = IDENTIFIER_CONV_OP_P (name); - tree lookup = conv_op ? conv_op_identifier : name; - tree val = NULL_TREE; - tree fns; - - /* If the type is complete, use binary search. */ - if (COMPLETE_TYPE_P (type)) + for (unsigned lo = 0, hi = method_vec->length (); lo < hi;) { - int lo = 0; - int hi = method_vec->length (); - while (lo < hi) - { - int i = (lo + hi) / 2; - - fns = (*method_vec)[i]; - tree fn_name = OVL_NAME (fns); - if (fn_name > lookup) - hi = i; - else if (fn_name < lookup) - lo = i + 1; - else - { - val = fns; - break; - } - } + unsigned mid = (lo + hi) / 2; + tree binding = (*method_vec)[mid]; + tree binding_name = OVL_NAME (binding); + + if (binding_name > name) + hi = mid; + else if (binding_name < name) + lo = mid + 1; + else + return binding; } - else - for (int i = 0; vec_safe_iterate (method_vec, i, &fns); ++i) - /* We can get a NULL binding during insertion of a new - method name, because the identifier_binding machinery - performs a lookup. If we find such a NULL slot, that's - the thing we were looking for, so we might as well bail - out immediately. */ - if (!fns) - break; - else if (OVL_NAME (fns) == lookup) - { - val = fns; - break; - } - /* Extract the conversion operators asked for, unless the general - conversion operator was requested. */ - if (val && conv_op) - { - gcc_checking_assert (OVL_FUNCTION (val) == conv_op_marker); - val = OVL_CHAIN (val); - if (tree type = TREE_TYPE (name)) - val = extract_conversion_operator (val, type); - } + return NULL_TREE; +} - return val; +/* Linear search of (unordered) METHOD_VEC for NAME. */ + +static tree +method_vec_linear_search (vec *method_vec, tree name) +{ + for (int ix = method_vec->length (); ix--;) + /* We can get a NULL binding during insertion of a new method + name, because the identifier_binding machinery performs a + lookup. If we find such a NULL slot, that's the thing we were + looking for, so we might as well bail out immediately. */ + if (tree binding = (*method_vec)[ix]) + { + if (OVL_NAME (binding) == name) + return binding; + } + else + break; + + return NULL_TREE; } /* Do a 1-level search for NAME as a member of TYPE. The caller must figure out whether it can access this field. (Since it is only one level, this is reasonable.) */ -tree +static tree lookup_field_1 (tree type, tree name, bool want_type) { tree field; @@ -1281,11 +1256,62 @@ lookup_field_1 (tree type, tree name, bo return NULL_TREE; } -/* TYPE is a class type. Return the overloads in - the method vector with name NAME. Lazily create ctors etc. */ +/* Look for NAME as an immediate member of KLASS (including + anon-members or unscoped enum member). TYPE_OR_FNS is zero for + regular search. >0 to get a type binding (if there is one) and <0 + if you want (just) the member function binding. + + Use this if you do not want lazy member creation. */ + +tree +get_class_binding_direct (tree klass, tree name, int type_or_fns) +{ + gcc_checking_assert (RECORD_OR_UNION_TYPE_P (klass)); + + /* Conversion operators can only be found by the marker conversion + operator name. */ + bool conv_op = IDENTIFIER_CONV_OP_P (name); + tree lookup = conv_op ? conv_op_identifier : name; + tree val = NULL_TREE; + vec *method_vec = CLASSTYPE_METHOD_VEC (klass); + + if (!method_vec || type_or_fns > 0) + ; + else if (COMPLETE_TYPE_P (klass)) + val = method_vec_binary_search (method_vec, lookup); + else + val = method_vec_linear_search (method_vec, lookup); + + if (type_or_fns < 0) + /* Don't bother looking for field. We don't want it. */; + else if (!val || (TREE_CODE (val) == OVERLOAD && OVL_USING_P (val))) + { + /* Dependent using declarations are a 'field', make sure we + return that even if we saw an overload already. */ + if (tree field_val = lookup_field_1 (klass, lookup, type_or_fns > 0)) + if (!val || TREE_CODE (field_val) == USING_DECL) + val = field_val; + } + + /* Extract the conversion operators asked for, unless the general + conversion operator was requested. */ + if (val && conv_op) + { + gcc_checking_assert (OVL_FUNCTION (val) == conv_op_marker); + val = OVL_CHAIN (val); + if (tree type = TREE_TYPE (name)) + val = extract_conversion_operator (val, type); + } + + return val; +} + +/* Look for NAME's binding in exactly KLASS. See + get_class_binding_direct for argument description. Does lazy + special function creation as necessary. */ tree -get_class_binding (tree type, tree name) +get_class_binding (tree type, tree name, int type_or_fns) { type = complete_type (type); @@ -1314,7 +1340,7 @@ get_class_binding (tree type, tree name) } } - return get_class_binding_direct (type, name); + return get_class_binding_direct (type, name, type_or_fns); } /* Find the slot containing overloads called 'NAME'. If there is no Index: name-lookup.h =================================================================== --- name-lookup.h (revision 251782) +++ name-lookup.h (working copy) @@ -319,9 +319,8 @@ extern void pop_decl_namespace (void); extern void do_namespace_alias (tree, tree); extern tree do_class_using_decl (tree, tree); extern tree lookup_arg_dependent (tree, tree, vec *); -extern tree lookup_field_1 (tree, tree, bool); -extern tree get_class_binding_direct (tree, tree); -extern tree get_class_binding (tree, tree); +extern tree get_class_binding_direct (tree, tree, int type_or_fns = -1); +extern tree get_class_binding (tree, tree, int type_or_fns = -1); extern tree *get_method_slot (tree klass, tree name); extern void resort_type_method_vec (void *, void *, gt_pointer_operator, void *); Index: search.c =================================================================== --- search.c (revision 251782) +++ search.c (working copy) @@ -974,23 +974,7 @@ lookup_field_r (tree binfo, void *data) && !BINFO_VIRTUAL_P (binfo)) return dfs_skip_bases; - /* First, look for a function. There can't be a function and a data - member with the same name, and if there's a function and a type - with the same name, the type is hidden by the function. */ - if (!lfi->want_type) - nval = get_class_binding (type, lfi->name); - - if (!nval) - /* Look for a data member or type. */ - nval = lookup_field_1 (type, lfi->name, lfi->want_type); - else if (TREE_CODE (nval) == OVERLOAD && OVL_USING_P (nval)) - { - /* If we have both dependent and non-dependent using-declarations, return - the dependent one rather than an incomplete list of functions. */ - tree dep_using = lookup_field_1 (type, lfi->name, lfi->want_type); - if (dep_using && TREE_CODE (dep_using) == USING_DECL) - nval = dep_using; - } + nval = get_class_binding (type, lfi->name, lfi->want_type); /* If we're looking up a type (as with an elaborated type specifier) we ignore all non-types we find. */