From patchwork Thu Oct 31 10:09:09 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathaniel Shead X-Patchwork-Id: 2004622 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=WeMXs8g+; dkim-atps=neutral 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=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XfKVW1vLnz1xwK for ; Thu, 31 Oct 2024 21:09:55 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4742B3857829 for ; Thu, 31 Oct 2024 10:09:53 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by sourceware.org (Postfix) with ESMTPS id 1A6E83858D21 for ; Thu, 31 Oct 2024 10:09:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1A6E83858D21 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1A6E83858D21 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::102e ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730369366; cv=none; b=w/H70okMSB4KlmAGORkJ5/CKfj3MaVgIxReBLHUA5hWv0VMYgBzCaby24H13b/CcPn/si9nhGeE15lqlT8ZCWYtq29h6yMR4AFJf43U38aAync/v0qhRTuaLV7mt+7lPP7sxHjW+kcDt34kfxh1/DJ2pACaI1UQWs3vRG3L+5uE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730369366; c=relaxed/simple; bh=wwo9ec6+CebGxJT/TPO9K3XYJ1cYwCT4vBKAkODNIdc=; h=DKIM-Signature:Message-ID:Date:From:To:Subject:MIME-Version; b=RAsAVrR1HPqqYXkW8aQ/pltrvj7Nwr1iCZ1dMnsCfB/UxFisFq0b1iAvRoMjYmaom0JS1ObwTipY2mucJn6ewFSIiRueFekrYkkPREkJjZh3Prf1gYi77EpP919t4Id1/oOFg5E2WJv6znYNgeDSXHjG7YEwUsUt6BTWjsTxW08= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pj1-x102e.google.com with SMTP id 98e67ed59e1d1-2e2d83f15f3so99186a91.0 for ; Thu, 31 Oct 2024 03:09:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1730369354; x=1730974154; darn=gcc.gnu.org; h=content-disposition:mime-version:subject:cc:to:from:date:message-id :from:to:cc:subject:date:message-id:reply-to; bh=YAhSjYUlOKy2RYchBoxb5qWhef0bGHoI7rLJaI0jK+0=; b=WeMXs8g+Ooz8lrvF75yaLWJem6FiQoWa4POhAKi0Ez0UQSBfhw9W1tGzkoPDzkeNUU vUCgN56wqMiHZt5pFFWGorIZFfaTCAmyn4TwWzjbASIcDgOvX7ZG0s4T+bwPEKZlexBs cIh6q3Kk9viWnEbQPXYvBOOo26CMOfK7mhH01GZ1YgmochNzOaJHfkqhVFpU+eaLYHQI L+J7N4RijDttzm7qJlgr4OjmTrGGN+7IXvBLw612rfda5j486PhVse7eIYk6/wlOH9F+ GHVKLRkHsfvYVDxqZ3h3U03aeZprCLHzII3NdyaJaY7ZXHqjwUQbvmRIudETXYX3PURv yYUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730369354; x=1730974154; h=content-disposition:mime-version:subject:cc:to:from:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=YAhSjYUlOKy2RYchBoxb5qWhef0bGHoI7rLJaI0jK+0=; b=jPMY2dKruAVP9EwJbRIJDsH9bdR8GZplyuFUWKvP/JZ2cf9MJLFoa8pAxDD+ifcPSP ygyCPwa63U5NxlGSwWY5U5Y+apjAwYQJlODXP9Od4dK3EMDdkyEz5VpdIfPrGmziBqop zA25MszcBISML9GAQHstIwD9MJt28KgIJN7MlaPXQXF71aqZXPzVC31rxZd5XL8fAEaK 6wqIekcJ3wWhonMo4CtsTXqjQvb5A8h9h32OT6KZup7UnUivLyopP02ycDsBGq8pHVRu E6Xu0SYeBe8ZlRyVrttyWngNSFA/TjKUAunDIJvP/Om3ys+LfEi87FQ/l7zZpvM/Ri7i TEqw== X-Gm-Message-State: AOJu0YyRSwpuzZEDnloKm0tpQkdZGYkrz74geUUZugpjbvU79IwL+U3G VIDupznZ+RF7VT6nwZ7u1qDH3oOFSakUAFqxMMnJJepeATxi3UupJl5O8zur X-Google-Smtp-Source: AGHT+IHJ/6EI2gHW7EUwtCJY1lXdIqc+6/fiws3WZqffL/Yqopxtr+NIRPBn0k/rKe1Blp58e6SE+g== X-Received: by 2002:a17:90a:734a:b0:2e2:a667:1a11 with SMTP id 98e67ed59e1d1-2e8f104f989mr9069769a91.1.1730369354465; Thu, 31 Oct 2024 03:09:14 -0700 (PDT) Received: from Thaum. (163-47-68-2.ipv4.originbroadband.com.au. [163.47.68.2]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e93daac954sm901260a91.23.2024.10.31.03.09.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 31 Oct 2024 03:09:13 -0700 (PDT) Message-ID: <67235749.170a0220.e81fe.267a@mx.google.com> X-Google-Original-Message-ID: Date: Thu, 31 Oct 2024 21:09:09 +1100 From: Nathaniel Shead To: gcc-patches@gcc.gnu.org Cc: Jason Merrill , Nathan Sidwell Subject: [PATCH] c++/modules: Fix recursive dependencies [PR116317] MIME-Version: 1.0 Content-Disposition: inline X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Bootstrapped and regtested on x86_64-pc-linux-gnu, OK for trunk? -- >8 -- In cases like the linked PR we sometimes get mutually recursive dependencies that both rely on the other to have been streamed as part of their merge key information. In the linked PR, this causes an ICE. The root cause is that 'sort_cluster' is not correctly ordering the dependencies; both the element_t specialisation and the reverse_adaptor::first function decl depend on each other, but by streaming element_t first it ends up trying to stream itself recursively as part of calculating its own merge key, which apart from the checking ICE will also cause issues on stream-in, as the merge key will not properly stream. There is a comment already in 'sort_cluster' describing this issue, but it says: Finding the single cluster entry dep is very tricky and expensive. Let's just not do that. It's harmless in this case anyway. However in this case it was not harmless: it's just somewhat luck that the sorting happened to work for the existing cases in the testsuite. This patch solves the issue by noting any declarations that rely on deps first seen within their own merge key. This declaration gets marked as an "entry" dep; any of these deps that end up recursively referring back to that entry dep as part of their own merge key do not. Then within sort_cluster we can ensure that the entry dep is written to be streamed first of its cluster; this will ensure that any other deps are just emitted as back-references, and the mergeable dep itself will structurally decompose. PR c++/116317 gcc/cp/ChangeLog: * module.cc (depset::DB_MAYBE_RECURSIVE_BIT): New flag. (depset::DB_ENTRY_BIT): New flag. (depset::is_maybe_recursive): New accessor. (depset::is_entry): New accessor. (depset::hash::writing_merge_key): New field. (trees_out::decl_value): Inform dep_hash while we're writing the merge key information for a decl. (depset::hash::add_dependency): Find recursive deps and mark the entry point. (sort_cluster): Ensure that the entry dep is streamed first. gcc/testsuite/ChangeLog: * g++.dg/modules/late-ret-4_a.H: New test. * g++.dg/modules/late-ret-4_b.C: New test. Signed-off-by: Nathaniel Shead --- gcc/cp/module.cc | 88 +++++++++++++++------ gcc/testsuite/g++.dg/modules/late-ret-4_a.H | 22 ++++++ gcc/testsuite/g++.dg/modules/late-ret-4_b.C | 4 + 3 files changed, 89 insertions(+), 25 deletions(-) create mode 100644 gcc/testsuite/g++.dg/modules/late-ret-4_a.H create mode 100644 gcc/testsuite/g++.dg/modules/late-ret-4_b.C diff --git a/gcc/cp/module.cc b/gcc/cp/module.cc index 297ef85bb1e..17d15878990 100644 --- a/gcc/cp/module.cc +++ b/gcc/cp/module.cc @@ -2336,6 +2336,8 @@ private: entity. */ DB_IMPORTED_BIT, /* An imported entity. */ DB_UNREACHED_BIT, /* A yet-to-be reached entity. */ + DB_MAYBE_RECURSIVE_BIT, /* An entity maybe in a recursive cluster. */ + DB_ENTRY_BIT, /* The first reached recursive dep. */ DB_HIDDEN_BIT, /* A hidden binding. */ /* The following bits are not independent, but enumerating them is awkward. */ @@ -2437,6 +2439,14 @@ public: { return get_flag_bit (); } + bool is_maybe_recursive () const + { + return get_flag_bit (); + } + bool is_entry () const + { + return get_flag_bit (); + } bool is_type_spec () const { return get_flag_bit (); @@ -2548,11 +2558,12 @@ public: depset *current; /* Current depset being depended. */ unsigned section; /* When writing out, the section. */ bool reached_unreached; /* We reached an unreached entity. */ + bool writing_merge_key; /* We're writing merge key information. */ public: hash (size_t size, hash *c = NULL) : parent (size), chain (c), current (NULL), section (0), - reached_unreached (false) + reached_unreached (false), writing_merge_key (false) { worklist.create (size); } @@ -7934,21 +7945,24 @@ trees_out::decl_value (tree decl, depset *dep) /* Stream the container, we want it correctly canonicalized before we start emitting keys for this decl. */ tree container = decl_container (decl); - unsigned tpl_levels = 0; - if (decl != inner) - tpl_header (decl, &tpl_levels); - if (TREE_CODE (inner) == FUNCTION_DECL) - fn_parms_init (inner); - /* Now write out the merging information, and then really - install the tag values. */ - key_mergeable (tag, mk, decl, inner, container, dep); + { + auto wmk = make_temp_override (dep_hash->writing_merge_key, true); + if (decl != inner) + tpl_header (decl, &tpl_levels); + if (TREE_CODE (inner) == FUNCTION_DECL) + fn_parms_init (inner); - if (streaming_p ()) - dump (dumper::MERGE) - && dump ("Wrote:%d's %s merge key %C:%N", tag, - merge_kind_name[mk], TREE_CODE (decl), decl); + /* Now write out the merging information, and then really + install the tag values. */ + key_mergeable (tag, mk, decl, inner, container, dep); + + if (streaming_p ()) + dump (dumper::MERGE) + && dump ("Wrote:%d's %s merge key %C:%N", tag, + merge_kind_name[mk], TREE_CODE (decl), decl); + } if (TREE_CODE (inner) == FUNCTION_DECL) fn_parms_fini (inner); @@ -13106,6 +13120,17 @@ depset::hash::add_dependency (depset *dep) dep->deps.safe_push (current); } + /* If two dependencies recursively depend on each other existing within + their own merge keys, we must ensure that the first dep we saw while + walking is written first in this cluster. See sort_cluster for more + details. */ + if (writing_merge_key) + { + dep->set_flag_bit (); + if (!current->is_maybe_recursive ()) + current->set_flag_bit (); + } + if (dep->is_unreached ()) { /* The dependency is reachable now. */ @@ -14117,7 +14142,7 @@ sort_cluster (depset::hash *original, depset *scc[], unsigned size) table.find_dependencies (nullptr); - vec order = table.connect (); + auto_vec order = table.connect (); gcc_checking_assert (order.length () == use_lwm); /* Now rewrite entries [0,lwm), in the dependency order we @@ -14134,26 +14159,39 @@ sort_cluster (depset::hash *original, depset *scc[], unsigned size) from Foo's declaration, so we only need to treat Foo as mergable (We'll do structural comparison of TPL). - Finding the single cluster entry dep is very tricky and - expensive. Let's just not do that. It's harmless in this case - anyway. */ - unsigned pos = 0; + We approximate finding the single cluster entry dep by checking for + entities recursively depending on a dep first seen when streaming + its own merge key; the first dep we see in such a cluster should be + the first one streamed. */ + unsigned entry_pos = ~0u; unsigned cluster = ~0u; for (unsigned ix = 0; ix != order.length (); ix++) { gcc_checking_assert (order[ix]->is_special ()); + bool tight = order[ix]->cluster == cluster; depset *dep = order[ix]->deps[0]; - scc[pos++] = dep; dump (dumper::MERGE) - && dump ("Mergeable %u is %N%s", ix, dep->get_entity (), - order[ix]->cluster == cluster ? " (tight)" : ""); + && dump ("Mergeable %u is %N%s%s", ix, dep->get_entity (), + tight ? " (tight)" : "", dep->is_entry () ? " (entry)" : ""); + scc[ix] = dep; + if (tight) + { + gcc_checking_assert (dep->is_maybe_recursive ()); + if (dep->is_entry ()) + { + /* There should only be one entry dep in a cluster. */ + gcc_checking_assert (!scc[entry_pos]->is_entry ()); + gcc_checking_assert (scc[entry_pos]->is_maybe_recursive ()); + scc[ix] = scc[entry_pos]; + scc[entry_pos] = dep; + } + } + else + entry_pos = ix; cluster = order[ix]->cluster; } - gcc_checking_assert (pos == use_lwm); - - order.release (); - dump (dumper::MERGE) && dump ("Ordered %u keys", pos); + dump (dumper::MERGE) && dump ("Ordered %u keys", order.length ()); dump.outdent (); } diff --git a/gcc/testsuite/g++.dg/modules/late-ret-4_a.H b/gcc/testsuite/g++.dg/modules/late-ret-4_a.H new file mode 100644 index 00000000000..80c821407c6 --- /dev/null +++ b/gcc/testsuite/g++.dg/modules/late-ret-4_a.H @@ -0,0 +1,22 @@ +// PR c++/116317 +// { dg-additional-options "-fmodules-ts" } +// { dg-module-cmi {} } + +template using element_t = int; + +template +struct reverse_adaptor { + void pairwise(); + + template + auto first(T self) -> element_t; + + // We can get the same issue with function parameters + template + void second(T self, element_t second); +}; + +template +void reverse_adaptor::pairwise() { + reverse_adaptor{}; +} diff --git a/gcc/testsuite/g++.dg/modules/late-ret-4_b.C b/gcc/testsuite/g++.dg/modules/late-ret-4_b.C new file mode 100644 index 00000000000..f9a83ba31f5 --- /dev/null +++ b/gcc/testsuite/g++.dg/modules/late-ret-4_b.C @@ -0,0 +1,4 @@ +// PR c++/116317 +// { dg-additional-options "-fmodules-ts -fno-module-lazy" } + +import "late-ret-4_a.H";