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: 22513 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:f944:0:0:0:0:0 with SMTP id q4csp422737wrr; Fri, 18 Nov 2022 13:45:04 -0800 (PST) X-Google-Smtp-Source: AA0mqf5QfAHvVqNXFROUzue2x9BWbypldk/dWWCbitvCvGP8oMoDvVJyzHlTX5RXoFQqhALSUlrr X-Received: by 2002:a17:907:988c:b0:7ad:c2ef:4d69 with SMTP id ja12-20020a170907988c00b007adc2ef4d69mr7877569ejc.10.1668807903896; Fri, 18 Nov 2022 13:45:03 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1668807903; cv=none; d=google.com; s=arc-20160816; b=RzJILi9Q/Ux73IlsPk8+E0wh7MVcbtjOE2KYoHQB7alHc487E35qcLPHyjJb1WtlbL j09ROITktiCiP9y6xkMHScks9MVNKJD/FOk9TUdzaK62iaTrO060ThErCBbgpfRBZnlU 5uhf2JgEzXIr4b5b22LWjswI9RekwAi8t9RJ8wP08e8UUDzdVn/y8qzVXUi0ZeAS/zo8 L3FUkWWOJjomeukdGWpvI8vOL21Noa+QGu96GJoT5I4+m5sKC5vxPXzU7tqo8kKtTTK7 6UPZ6arqPJsq62m/8dyTYdulyql8YHO37YQa4vgagWFM58EEHtqu7fyGRjCO1GmScU84 37tw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:cc :to:dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=595kqVinjGRiiWf4+b4srDoCEZ/DRp5sATeOVYC3OSk=; b=aKtQRY5ZhsTaojG/uP51AUUNG788GMo+ua22IF36Oa9J0OGD3OZn1FGtMvtkTEdi8b fKy5gf+8yid49VkhhH7qp7NKIX+UXPbB1D6JkRKmUiVclhXoY8Md7nbMm7BMLekXkgid HD6JtftEu/myYJgQXQcvHu1tKPpL6U5ZVyaGVatbejqUCwJgzQKdzGFuImCrYuB744kC l+gualzxd+ilAuy8GZ+nCtYOb5ZddGP4LGk+NT93ET7xkqJ3wwBcj7W3WQblVc1J6aVF FlZw+DMV8y+MJgOb7GFEawOb7nyqsjq9cptmpR1tXHSy9zEoMNI6PTQ2lL4aCUgvQckT qNKQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SXA9PJ5J; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id hz3-20020a1709072ce300b007a2d966eeccsi3700363ejc.686.2022.11.18.13.45.03 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Nov 2022 13:45:03 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SXA9PJ5J; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 768FA3853D74 for ; Fri, 18 Nov 2022 21:45:02 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 768FA3853D74 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1668807902; 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=SXA9PJ5Jw7/JPTeE0FGiIltGxegJSPfUxpL+QD7joiDP5hi03tAWhWPjwf7DdnGOj kEwFvoRtGYx2OeC/N+fDYdcXJKKFfs+73G0+vNZPjbDvpROgcj5XAFkE+R/XSSltlI IUpbu3bmWArb+jPUEi4vlhPdw3dckPyp+h6FRzwQ= 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-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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1749871916679846335?= X-GMAIL-MSGID: =?utf-8?q?1749871916679846335?= 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; }