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 1D4CE3853D59 for ; Fri, 18 Nov 2022 21:44:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1D4CE3853D59 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=1668807856; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=595kqVinjGRiiWf4+b4srDoCEZ/DRp5sATeOVYC3OSk=; b=MWx4Vt54Cptbb/i9eB5MVky5qVaHbj5gbRdUuZMhkvuaQDqa4KRErS4kbpyALyTlbfk3Fq mKCTvA0eWe4ybhcrrgxLJij0O2oDezf2qzd+OR7re3PjP2z1WmDC6QgjfZhFLUiyS7EOIu TVIc5o2xGk0VHFMkyILwXRY9sgi66ro= Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-433-RNMD4h2APjqqgUPl-7TCxA-1; Fri, 18 Nov 2022 16:44:15 -0500 X-MC-Unique: RNMD4h2APjqqgUPl-7TCxA-1 Received: by mail-qt1-f199.google.com with SMTP id y8-20020ac87088000000b003a528a5b844so6203852qto.18 for ; Fri, 18 Nov 2022 13:44:15 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=595kqVinjGRiiWf4+b4srDoCEZ/DRp5sATeOVYC3OSk=; b=CGxd3713LIIeiNn6WAPHpIgZ6BMMQameRQ+LhzUd4eIj8k2RzEQ4odZTl4kEOu/ZmS 8H+hCcJlWWJo4lfBU2EdXDwDUt2f3eqPtkNO1JX3jRukXuW7TY2Rxgm0zo7M5m7bOKjr NITHqXxqbfZ4fRIt3G2embWqw9sCgLxfay3Unrkm/2WoEtPNQHd0v1gvzE64uL2JrE+x PzIua6iAzgsb9oEjeuTZOGASsqTPU11+JzWXXF39OJmCCgwbCo+4OP/TyIMWO/kw+IGj KG1Zo6YB0O8N6u93NRopfZtBzuqtvl4mYGmNBg/9f5N6L6lw0N6Msqd8zXnSDNzs7Utn akkw== X-Gm-Message-State: ANoB5pmXCFFnHK+ZgadG5tHOsx9hS+VDPVSXVqphdGhIL9ghdCOVudtO 3TTLE5mhH3cCmfNnAQv6WXFiGO9wsqtJS9F9q9N3GXn9aEkxg3Gx9TBJcVCHfGu4SCNuPDhYrbb 8AWwjrTP6zR/76g30tbxiC9E/pqmwKZsCAPYdEiFwD2AdpIiEGL6HiXO2x14Qd5kdL50= X-Received: by 2002:a05:620a:4590:b0:6fa:91f9:e54e with SMTP id bp16-20020a05620a459000b006fa91f9e54emr7650535qkb.53.1668807853798; Fri, 18 Nov 2022 13:44:13 -0800 (PST) X-Google-Smtp-Source: AA0mqf6NMQdoZ09N7cvM/LwdLdkQ7MejUl8JcL1B0VMGn+99dEeS3eecGla94SRdLxwj/ASan3bioQ== X-Received: by 2002:a05:620a:4590:b0:6fa:91f9:e54e with SMTP id bp16-20020a05620a459000b006fa91f9e54emr7650509qkb.53.1668807853351; Fri, 18 Nov 2022 13:44:13 -0800 (PST) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id bi40-20020a05620a31a800b006f7ee901674sm3115616qkb.2.2022.11.18.13.44.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Nov 2022 13:44:12 -0800 (PST) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: jason@redhat.com, Patrick Palka Subject: [PATCH] c++: cache the normal form of a concept-id Date: Fri, 18 Nov 2022 16:43:39 -0500 Message-Id: <20221118214339.3620949-1-ppalka@redhat.com> X-Mailer: git-send-email 2.38.1.436.geea7033409 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-13.7 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_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: 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? 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; } -- 2.38.1.436.geea7033409