From patchwork Fri Nov 18 21:43:39 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1705822 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=RVoNUpxf; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4NDVgG5f5cz1yhv for ; Sat, 19 Nov 2022 08:44:40 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E7A2F384F6F2 for ; Fri, 18 Nov 2022 21:44:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E7A2F384F6F2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1668807877; bh=595kqVinjGRiiWf4+b4srDoCEZ/DRp5sATeOVYC3OSk=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=RVoNUpxfFmTPT215/FE+fiJ5cvlWFIgSm/J/pdE321Pmc+PEJkGRiNzosNf7wAMPy ZzCJJN9k/YfmAxCHubEF13HDJo0JSW49ovDGg2Mn/fcU42MOxvrgSqupW266jd4/00 Sp9s94v14SDNPhDGc1bKKkzgKl7fgblNOS4hkPo4= 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.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 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) 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 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 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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; }