From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id CEF42385840D for ; Sat, 19 Nov 2022 02:57:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CEF42385840D Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1668826631; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=xQvT9JXTjlTtFeG6c47Rdt7phPAJLUVZ8TxaQ2Fial8=; b=DroLr/FIYO0VucyRZ/GI6Q89pa+8TcNrLQJZCldcT+7YWScaZ5TcRT+syzNXVGkg908+CJ v+FFekPp0MzGkKIha2hG+HDYoVbBcGVM9ygGbTpMdb1qZV0Bgjfv5UGdTsr1Ljq/R0auP4 +8N81QZz+ANlMrjtLe7MJ9795o8HPoA= Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-169-u00x86YTMPSpJiB_gDMgQQ-1; Fri, 18 Nov 2022 21:57:10 -0500 X-MC-Unique: u00x86YTMPSpJiB_gDMgQQ-1 Received: by mail-qk1-f197.google.com with SMTP id de43-20020a05620a372b00b006fae7e5117fso8537286qkb.6 for ; Fri, 18 Nov 2022 18:57:10 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=xQvT9JXTjlTtFeG6c47Rdt7phPAJLUVZ8TxaQ2Fial8=; b=cQqgvPqZ75QY0eT6tAoOhw/5jkEDVcD1e3ghs/fJ49DTX4U/VI75/lxdfU6R41vA/l zoxd23rLl8FgIsqLJnx8I0zUu/sqlsZjHHeH148tEdk1N8hrOeRI3aZownRP8l7fS5uw +V4rtfBKrGeRBQHGu/hLLjRdqbm9Z6AJMEQSiQ8mMdPXRJPbU0E0KZgmKfdFrnXQXRc7 WFyagnURbmH6I7IaKbiCZkIKxG7H25l8ZjaYVE7Tvvo7RXXsAwd7VrxFHP96LrX/p/nZ Bp44pCk1ZZugTNgNg1W6uu5QOz7vySJnvlRiI8K5xITuwV5hewdv9GelqhpRg2kGfVNu 4AaQ== X-Gm-Message-State: ANoB5pkg72IWL0NKDbRdjNKHNZFwySyvvRI2KVwjnmgcsF9Xief1XFXF 3Ikwsd8a36oswMVq11bYakgx7p73tlKRhCzBwEPZBWWKBXvmJ73Bf3qt2qikoE26AjQwjqWyp19 VGKJ/s0IRSQHIBWr5Og== X-Received: by 2002:ae9:f50b:0:b0:6f8:c296:a883 with SMTP id o11-20020ae9f50b000000b006f8c296a883mr8510860qkg.413.1668826629347; Fri, 18 Nov 2022 18:57:09 -0800 (PST) X-Google-Smtp-Source: AA0mqf7i9ATRYtvJa/XqU+xFT5sI3PbWE/Sy3lkMpKb+a/RWRpywQbVljfySQsduT44jk3TIAtHEsg== X-Received: by 2002:ae9:f50b:0:b0:6f8:c296:a883 with SMTP id o11-20020ae9f50b000000b006f8c296a883mr8510852qkg.413.1668826628954; Fri, 18 Nov 2022 18:57:08 -0800 (PST) Received: from [192.168.1.137] (130-44-159-43.s15913.c3-0.arl-cbr1.sbo-arl.ma.cable.rcncustomer.com. [130.44.159.43]) by smtp.gmail.com with ESMTPSA id k1-20020a05620a414100b006eea4b5abcesm3628763qko.89.2022.11.18.18.57.07 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 18 Nov 2022 18:57:07 -0800 (PST) Message-ID: <6a811bb5-9032-5fd7-4573-6dee801b6173@redhat.com> Date: Fri, 18 Nov 2022 21:57:06 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.5.0 Subject: Re: [PATCH] c++: cache the normal form of a concept-id To: Patrick Palka , gcc-patches@gcc.gnu.org References: <20221118214339.3620949-1-ppalka@redhat.com> From: Jason Merrill In-Reply-To: <20221118214339.3620949-1-ppalka@redhat.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,NICE_REPLY_A,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On 11/18/22 16:43, Patrick Palka wrote: > We already cache the overall normal form of a declaration's constraints > under the assumption that it can't change over the translation unit. > But if we have two constrained declarations such as > > template void f() requires expensive && A; > template void g() requires expensive && B; > > then despite this high-level caching we'd still redundantly have to > expand the concept-id expensive twice, once during normalization of > f's constraints and again during normalization of g's. Ideally, we'd > reuse the previously computed normal form of expensive the second > time around. > > To that end this patch introduces an intermediate layer of caching > during constraint normalization -- caching of the normal form of a > concept-id -- that sits between our high-level caching of the overall > normal form of a declaration's constraints and our low-level caching of > each individual atomic constraint. > > It turns out this caching generalizes some ad-hoc caching of the normal > form of concept definition (which is equivalent to the normal form of > the concept-id C where gtargs are C's generic arguments) so > this patch unifies the caching accordingly. > > This change improves compile time/memory usage for e.g. the libstdc++ > test std/ranges/adaptors/join.cc by 10%/5%. > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for > trunk? Hmm, if we cache at this level, do we still also need to cache the full normal form of the decl's constraints? Exploring that doesn't seem like stage 3 material, though. The patch is OK. > gcc/cp/ChangeLog: > > * constraint.cc (struct norm_entry): Define. > (struct norm_hasher): Define. > (norm_cache): Define. > (normalize_concept_check): Add function comment. Cache the > result of concept-id normalization. Canonicalize generic > arguments as NULL_TREE. Don't coerce arguments unless > substitution occurred. > (normalize_concept_definition): Simplify. Use norm_cache > instead of ad-hoc caching. > --- > gcc/cp/constraint.cc | 94 ++++++++++++++++++++++++++++++++++++++------ > 1 file changed, 82 insertions(+), 12 deletions(-) > > diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc > index a113d3e269e..c9740b1ec78 100644 > --- a/gcc/cp/constraint.cc > +++ b/gcc/cp/constraint.cc > @@ -698,6 +698,40 @@ normalize_logical_operation (tree t, tree args, tree_code c, norm_info info) > return build2 (c, ci, t0, t1); > } > > +/* Data types and hash functions for caching the normal form of a concept-id. > + This essentially memoizes calls to normalize_concept_check. */ > + > +struct GTY((for_user)) norm_entry > +{ > + /* The CONCEPT_DECL of the concept-id. */ > + tree tmpl; > + /* The arguments of the concept-id. */ > + tree args; > + /* The normal form of the concept-id. */ > + tree norm; > +}; > + > +struct norm_hasher : ggc_ptr_hash > +{ > + static hashval_t hash (norm_entry *t) > + { > + hashval_t hash = iterative_hash_template_arg (t->tmpl, 0); > + hash = iterative_hash_template_arg (t->args, hash); > + return hash; > + } > + > + static bool equal (norm_entry *t1, norm_entry *t2) > + { > + return t1->tmpl == t2->tmpl > + && template_args_equal (t1->args, t2->args); > + } > +}; > + > +static GTY((deletable)) hash_table *norm_cache; > + > +/* Normalize the concept check CHECK where ARGS are the > + arguments to be substituted into CHECK's arguments. */ > + > static tree > normalize_concept_check (tree check, tree args, norm_info info) > { > @@ -720,24 +754,53 @@ normalize_concept_check (tree check, tree args, norm_info info) > targs = tsubst_template_args (targs, args, info.complain, info.in_decl); > if (targs == error_mark_node) > return error_mark_node; > + if (template_args_equal (targs, generic_targs_for (tmpl))) > + /* Canonicalize generic arguments as NULL_TREE, as an optimization. */ > + targs = NULL_TREE; > > /* Build the substitution for the concept definition. */ > tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl)); > - /* Turn on template processing; coercing non-type template arguments > - will automatically assume they're non-dependent. */ > ++processing_template_decl; > - tree subst = coerce_template_parms (parms, targs, tmpl, tf_none); > + if (targs && args) > + /* If substitution occurred, coerce the resulting arguments. */ > + targs = coerce_template_parms (parms, targs, tmpl, tf_none); > --processing_template_decl; > - if (subst == error_mark_node) > + if (targs == error_mark_node) > return error_mark_node; > > + if (!norm_cache) > + norm_cache = hash_table::create_ggc (31); > + norm_entry entry = {tmpl, targs, NULL_TREE}; > + norm_entry **slot = nullptr; > + hashval_t hash = 0; > + if (!info.generate_diagnostics ()) > + { > + /* If we're not diagnosing, cache the normal form of the > + substituted concept-id. */ > + hash = norm_hasher::hash (&entry); > + slot = norm_cache->find_slot_with_hash (&entry, hash, INSERT); > + if (*slot) > + return (*slot)->norm; > + } > + > /* The concept may have been ill-formed. */ > tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl)); > if (def == error_mark_node) > return error_mark_node; > > info.update_context (check, args); > - return normalize_expression (def, subst, info); > + tree norm = normalize_expression (def, targs, info); > + if (slot) > + { > + /* Recompute SLOT, as norm_cache may have been expanded during > + a recursive call. */ > + slot = norm_cache->find_slot_with_hash (&entry, hash, INSERT); > + gcc_checking_assert (!*slot); > + entry.norm = norm; > + *slot = ggc_alloc (); > + **slot = entry; > + } > + return norm; > } > > /* Used by normalize_atom to cache ATOMIC_CONSTRs. */ > @@ -941,15 +1004,17 @@ get_normalized_constraints_from_decl (tree d, bool diag = false) > /* Returns the normal form of TMPL's definition. */ > > static tree > -normalize_concept_definition (tree tmpl, bool diag = false) > +normalize_concept_definition (tree tmpl, bool diag) > { > + if (!norm_cache) > + norm_cache = hash_table::create_ggc (31); > + > + norm_entry entry = {tmpl, NULL_TREE, NULL_TREE}; > + > if (!diag) > - if (tree *p = hash_map_safe_get (normalized_map, tmpl)) > - return *p; > + if (norm_entry *found = norm_cache->find (&entry)) > + return found->norm; > > - gcc_assert (concept_definition_p (tmpl)); > - if (OVL_P (tmpl)) > - tmpl = OVL_FIRST (tmpl); > gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL); > tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl)); > ++processing_template_decl; > @@ -958,7 +1023,12 @@ normalize_concept_definition (tree tmpl, bool diag = false) > --processing_template_decl; > > if (!diag) > - hash_map_safe_put (normalized_map, tmpl, norm); > + { > + norm_entry **slot = norm_cache->find_slot (&entry, INSERT); > + entry.norm = norm; > + *slot = ggc_alloc (); > + **slot = entry; > + } > > return norm; > }