From patchwork Mon May 16 19:58:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 54047 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 07DA03856271 for ; Mon, 16 May 2022 19:59:19 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 07DA03856271 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1652731159; bh=U9YLk5TAeU903HxwuErHNWjAZGBYID0BPmlO4tU1VFs=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=Ejdy/QCJAOtx/vgBGFJczvCQBubsPwU06Zzf0GeILtd7Wp9Hfz33gGlkLquv1YXxT Dk8LlRDb3O1SoG5nGfIwuG0oGyxwEvtl36XF5j2g5noyKH6WZ8vnVcc5h80sfvFVMA mfWjOgAOzs1xs/kk2Yb5M3xtMUeqA7e/unqK7gaw= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 428563858C51 for ; Mon, 16 May 2022 19:58:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 428563858C51 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-616-3f-UlOWMM-KaA3Q8NlbFTQ-1; Mon, 16 May 2022 15:58:46 -0400 X-MC-Unique: 3f-UlOWMM-KaA3Q8NlbFTQ-1 Received: by mail-qk1-f200.google.com with SMTP id bj2-20020a05620a190200b005084968bb24so12060774qkb.23 for ; Mon, 16 May 2022 12:58:46 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=U9YLk5TAeU903HxwuErHNWjAZGBYID0BPmlO4tU1VFs=; b=24h9B3m+XsgeznO5pWODsf0PUoQZABW3I5ATQYqoRDcJSDWRrjqmBMXiZS8DKX7rFD GzqUcaes5ksI+DxZQeASy0h6iQir5724ZF0HPk20PUxKRk5jDAs6dy9zEGh8FmbWiFrC J/3jpmFV+qkouUzVeMfYO5VYd4cHGKbrM186WCNLdLeuSId0hRXDEa6l30XzOMRf0h0a E5wgfKJid+4BVJ8xR/YF+NzFaLfLloZn8wS4aUfYwZq8ii+hk6GbaNnoEFfM2lmx4hAc 9SgcZoi4Fw6X+8+ed8NSTPGLVzXLJay+YyFxqv17SvfJdlLw1A9omedQSanglibmCbKl HoCg== X-Gm-Message-State: AOAM532SLkJfrMqwVuOyjMPPoyLtUtBYZixl3mNoMouQkC1TgDQVLLpG Qu8lhEg5lcrmvzoZJpi8JHUIQ72RAfnzR8qeFfon3zGPii7Yf3X5IITDqvWK7yi0hYDrf2z7S1V lpgVVrFfJ7jOzMnRydFLC7CYx38plukoPxoMipIrKJ706VNHlI+t4oUNuMbQgbfL+SWA= X-Received: by 2002:a05:622a:50f:b0:2f3:f0d9:e316 with SMTP id l15-20020a05622a050f00b002f3f0d9e316mr16767170qtx.113.1652731125799; Mon, 16 May 2022 12:58:45 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwR4I8z+S2WGBuDKitlgVOH7x04aeBYigwqZNMgUsh32peO58v+/Sn30JBuSfjiz8tP1S7aXQ== X-Received: by 2002:a05:622a:50f:b0:2f3:f0d9:e316 with SMTP id l15-20020a05622a050f00b002f3f0d9e316mr16767136qtx.113.1652731125319; Mon, 16 May 2022 12:58:45 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id v6-20020ae9e306000000b0069fc13ce23esm6314430qkf.111.2022.05.16.12.58.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 May 2022 12:58:45 -0700 (PDT) To: gcc-patches@gcc.gnu.org Subject: [PATCH] c++: set TYPE_CANONICAL for most templated types Date: Mon, 16 May 2022 15:58:41 -0400 Message-Id: <20220516195841.2867277-1-ppalka@redhat.com> X-Mailer: git-send-email 2.36.1.74.g277cf0bc36 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-14.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Patrick Palka via Gcc-patches From: Patrick Palka Reply-To: Patrick Palka Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" When processing a class template specialization, lookup_template_class uses structural equality for the specialized type whenever one of its template arguments uses structural equality. This the sensible thing to do in a vacuum, but given that we already effectively deduplicate class specializations via the spec_hasher, it seems to me we can safely assume that each class specialization is unique and therefore canonical, regardless of the structure of the template arguments. To that end this patch makes us use the canonical type machinery for all type specializations except for the case where a PARM_DECL appears in the template arguments (added in r12-3766-g72394d38d929c7). Additionally, this patch makes us use the canonical type machinery for TEMPLATE_TEMPLATE_PARMs and BOUND_TEMPLATE_TEMPLATE_PARMs, by extending canonical_type_parameter appropriately. A comment in tsubst says it's unsafe to set TYPE_CANONICAL for a lowered TEMPLATE_TEMPLATE_PARM, but I'm not sure I understand it. Note that r10-7817-ga6f400239d792d recently changed process_template_parm to clear TYPE_CANONICAL for TEMPLATE_TEMPLATE_PARM consistent with the tsubst comment; this patch changes both functions to set instead of clear TYPE_CANONICAL for ttps. This change improves compile time of heavily templated code by around 10% for me (with a release compiler). For instance, compile time for the libstdc++ test std/ranges/adaptors/all.cc drops from 1.45s to 1.25s, and for the range-v3 test test/view/zip.cpp it goes from 5.38s to 4.88s. The total number of calls to structural_comptypes for the latter test drops from 8.5M to 1.5M. Memory use is unchanged (unsurpisingly). Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for trunk? Also tested on cmcstl2 and range-v3 and various boost libraries. Will also do more testing overnight... gcc/cp/ChangeLog: * pt.cc (any_template_arguments_need_structural_equality_p): Remove. (struct ctp_hasher): Define. (ctp_table): Define. (canonical_type_parameter): Use it. (process_template_parm): Set TYPE_CANONICAL for TEMPLATE_TEMPLATE_PARM too. (lookup_template_class_1): Don't call a_t_a_n_s_e_p. Inline the PARM_DECL special case from that subroutine into here. (tsubst) : Remove special TYPE_CANONICAL handling specific to ttps, and perform the remaining handling later. (find_parm_usage_r): Remove. * tree.cc (bind_template_template_parm): Set TYPE_CANONICAL when safe to do so. * typeck.cc (structural_comptypes) [check_alias]: Increment processing_template_decl before using dependent_alias_template_spec_p. --- gcc/cp/pt.cc | 166 ++++++++++++++++------------------------------- gcc/cp/tree.cc | 16 ++++- gcc/cp/typeck.cc | 2 + 3 files changed, 73 insertions(+), 111 deletions(-) diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc index fa05e9134df..76562877355 100644 --- a/gcc/cp/pt.cc +++ b/gcc/cp/pt.cc @@ -203,7 +203,6 @@ static tree copy_default_args_to_explicit_spec_1 (tree, tree); static void copy_default_args_to_explicit_spec (tree); static bool invalid_nontype_parm_type_p (tree, tsubst_flags_t); static bool dependent_template_arg_p (tree); -static bool any_template_arguments_need_structural_equality_p (tree); static bool dependent_type_p_r (tree); static tree tsubst_copy (tree, tree, tsubst_flags_t, tree); static tree tsubst_decl (tree, tree, tsubst_flags_t); @@ -4526,6 +4525,27 @@ build_template_parm_index (int index, return t; } +struct ctp_hasher : ggc_ptr_hash +{ + static hashval_t hash (tree t) + { + tree_code code = TREE_CODE (t); + hashval_t val = iterative_hash_object (code, 0); + val = iterative_hash_object (TEMPLATE_TYPE_LEVEL (t), val); + val = iterative_hash_object (TEMPLATE_TYPE_IDX (t), val); + if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM) + val = iterative_hash_template_arg (TYPE_TI_ARGS (t), val); + return val; + } + + static bool equal (tree t, tree u) + { + return comptypes (t, u, COMPARE_STRUCTURAL); + } +}; + +static GTY (()) hash_table *ctp_table; + /* Find the canonical type parameter for the given template type parameter. Returns the canonical type parameter, which may be TYPE if no such parameter existed. */ @@ -4533,21 +4553,13 @@ build_template_parm_index (int index, tree canonical_type_parameter (tree type) { - int idx = TEMPLATE_TYPE_IDX (type); - - gcc_assert (TREE_CODE (type) != TEMPLATE_TEMPLATE_PARM); + if (ctp_table == NULL) + ctp_table = hash_table::create_ggc (61); - if (vec_safe_length (canonical_template_parms) <= (unsigned) idx) - vec_safe_grow_cleared (canonical_template_parms, idx + 1, true); - - for (tree list = (*canonical_template_parms)[idx]; - list; list = TREE_CHAIN (list)) - if (comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL)) - return TREE_VALUE (list); - - (*canonical_template_parms)[idx] - = tree_cons (NULL_TREE, type, (*canonical_template_parms)[idx]); - return type; + tree& slot = *ctp_table->find_slot (type, INSERT); + if (slot == NULL_TREE) + slot = type; + return slot; } /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose @@ -4720,10 +4732,7 @@ process_template_parm (tree list, location_t parm_loc, tree parm, current_template_depth, decl, TREE_TYPE (parm)); TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack; - if (TREE_CODE (t) == TEMPLATE_TEMPLATE_PARM) - SET_TYPE_STRUCTURAL_EQUALITY (t); - else - TYPE_CANONICAL (t) = canonical_type_parameter (t); + TYPE_CANONICAL (t) = canonical_type_parameter (t); } DECL_ARTIFICIAL (decl) = 1; SET_DECL_TEMPLATE_PARM_P (decl); @@ -10130,11 +10139,29 @@ lookup_template_class_1 (tree d1, tree arglist, tree in_decl, tree context, template type. Set the TYPE_CANONICAL field appropriately. */ TYPE_CANONICAL (t) = template_type; - else if (any_template_arguments_need_structural_equality_p (arglist)) - /* Some of the template arguments require structural - equality testing, so this template class requires - structural equality testing. */ - SET_TYPE_STRUCTURAL_EQUALITY (t); + else if (!current_function_decl && processing_template_decl) + { + auto find_parm_usage_r = [] (tree *tp, int*, void*) { + if (TREE_CODE (*tp) == PARM_DECL) + return *tp; + return NULL_TREE; + }; + if (cp_walk_tree_without_duplicates (&arglist, find_parm_usage_r, + nullptr)) + /* The identity of a class template specialization that uses + a function parameter depends on the identity of the function. + And if this specialization appeared in the trailing return + type thereof, we don't know the identity of the function + (e.g. if it's a redeclaration or a new function) until we + form its signature. Deciding on a canonical type at this + point (which depends on the DECL_CONTEXT of the function + parameter, which can get mutated after the fact by + duplicate_decls) is therefore premature, so instead use + structural equality (PR52830). */ + SET_TYPE_STRUCTURAL_EQUALITY (t); + } + /* Otherwise, this class specialization is unique and therefore its + TYPE_CANONICAL points to itself. */ } else gcc_unreachable (); @@ -15908,20 +15935,6 @@ tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl) only instantiated during satisfaction. */ PLACEHOLDER_TYPE_CONSTRAINTS_INFO (r) = ci; - if (TREE_CODE (r) == TEMPLATE_TEMPLATE_PARM) - /* We have reduced the level of the template - template parameter, but not the levels of its - template parameters, so canonical_type_parameter - will not be able to find the canonical template - template parameter for this level. Thus, we - require structural equality checking to compare - TEMPLATE_TEMPLATE_PARMs. */ - SET_TYPE_STRUCTURAL_EQUALITY (r); - else if (TYPE_STRUCTURAL_EQUALITY_P (t)) - SET_TYPE_STRUCTURAL_EQUALITY (r); - else - TYPE_CANONICAL (r) = canonical_type_parameter (r); - if (code == BOUND_TEMPLATE_TEMPLATE_PARM) { tree tinfo = TYPE_TEMPLATE_INFO (t); @@ -15939,6 +15952,11 @@ tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl) TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (r) = build_template_info (tmpl, argvec); } + + if (TYPE_STRUCTURAL_EQUALITY_P (t)) + SET_TYPE_STRUCTURAL_EQUALITY (r); + else + TYPE_CANONICAL (r) = canonical_type_parameter (r); } break; @@ -28211,78 +28229,6 @@ dependent_template_arg_p (tree arg) return value_dependent_expression_p (arg); } -/* Identify any expressions that use function parms. */ - -static tree -find_parm_usage_r (tree *tp, int *walk_subtrees, void*) -{ - tree t = *tp; - if (TREE_CODE (t) == PARM_DECL) - { - *walk_subtrees = 0; - return t; - } - return NULL_TREE; -} - -/* Returns true if ARGS (a collection of template arguments) contains - any types that require structural equality testing. */ - -bool -any_template_arguments_need_structural_equality_p (tree args) -{ - int i; - int j; - - if (!args) - return false; - if (args == error_mark_node) - return true; - - for (i = 0; i < TMPL_ARGS_DEPTH (args); ++i) - { - tree level = TMPL_ARGS_LEVEL (args, i + 1); - for (j = 0; j < TREE_VEC_LENGTH (level); ++j) - { - tree arg = TREE_VEC_ELT (level, j); - tree packed_args = NULL_TREE; - int k, len = 1; - - if (ARGUMENT_PACK_P (arg)) - { - /* Look inside the argument pack. */ - packed_args = ARGUMENT_PACK_ARGS (arg); - len = TREE_VEC_LENGTH (packed_args); - } - - for (k = 0; k < len; ++k) - { - if (packed_args) - arg = TREE_VEC_ELT (packed_args, k); - - if (error_operand_p (arg)) - return true; - else if (TREE_CODE (arg) == TEMPLATE_DECL) - continue; - else if (TYPE_P (arg) && TYPE_STRUCTURAL_EQUALITY_P (arg)) - return true; - else if (!TYPE_P (arg) && TREE_TYPE (arg) - && TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (arg))) - return true; - /* Checking current_function_decl because this structural - comparison is only necessary for redeclaration. */ - else if (!current_function_decl - && dependent_template_arg_p (arg) - && (cp_walk_tree_without_duplicates - (&arg, find_parm_usage_r, NULL))) - return true; - } - } - } - - return false; -} - /* Returns true if ARGS (a collection of template arguments) contains any dependent arguments. */ diff --git a/gcc/cp/tree.cc b/gcc/cp/tree.cc index bc38c8fbdbe..940f1420bba 100644 --- a/gcc/cp/tree.cc +++ b/gcc/cp/tree.cc @@ -2901,7 +2901,21 @@ bind_template_template_parm (tree t, tree newargs) TYPE_NAME (t2) = decl; TYPE_STUB_DECL (t2) = decl; TYPE_SIZE (t2) = 0; - SET_TYPE_STRUCTURAL_EQUALITY (t2); + + bool use_structural_equality = false; + for (tree arg : tree_vec_range (newargs)) + if (arg == any_targ_node) + { + /* This BOUND_TEMPLATE_TEMPLATE_PARM has an any_targ_node argument + (added by add_defaults_to_ttp), for which template_args_equal + always returns true, so this bound ttp is not canonicalizable. */ + use_structural_equality = true; + break; + } + if (use_structural_equality) + SET_TYPE_STRUCTURAL_EQUALITY (t2); + else + TYPE_CANONICAL (t2) = canonical_type_parameter (t2); return t2; } diff --git a/gcc/cp/typeck.cc b/gcc/cp/typeck.cc index 6ecdd97697d..385cdf4d733 100644 --- a/gcc/cp/typeck.cc +++ b/gcc/cp/typeck.cc @@ -1511,8 +1511,10 @@ structural_comptypes (tree t1, tree t2, int strict) substitute into the specialization arguments at instantiation time. And aliases can't be equivalent without being ==, so we don't need to look any deeper. */ + ++processing_template_decl; tree dep1 = dependent_alias_template_spec_p (t1, nt_transparent); tree dep2 = dependent_alias_template_spec_p (t2, nt_transparent); + --processing_template_decl; if ((dep1 || dep2) && dep1 != dep2) return false; }