From patchwork Wed Dec 2 14:19:35 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 1409760 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=acm.org Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20161025 header.b=EvxZH+zB; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4CmLhR1k7vz9sPB for ; Thu, 3 Dec 2020 01:19:48 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 18D49395C029; Wed, 2 Dec 2020 14:19:44 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qt1-x835.google.com (mail-qt1-x835.google.com [IPv6:2607:f8b0:4864:20::835]) by sourceware.org (Postfix) with ESMTPS id 340923851C33 for ; Wed, 2 Dec 2020 14:19:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 340923851C33 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=acm.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=nathanmsidwell@gmail.com Received: by mail-qt1-x835.google.com with SMTP id b9so629545qtr.2 for ; Wed, 02 Dec 2020 06:19:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:to:from:subject:message-id:date:user-agent:mime-version :content-language; bh=szd7gGfeqRafDKK47gI7gBHbCMFVGSNd9Bn1rjbH+EU=; b=EvxZH+zBbG5YsQQA0T6zA3GDTtJpxwbibfpsEN/HsKdk5mMvjsmmxdeoewQQd0MO4a 9CMdzZDz86PRs2VD0qA9eKa5sCTryJgkyV3oFuXnMCbFpOAwfklujM7fKdSj3MlzxLCJ U5RykWEECS+Z8hXPu7WBkYefVKeQ8WF2PMwSAyxwLUGZh8oS3BmvX0KD4sLrIvI/yfAz mLhzZ58/uvLg3vELUAkyW7Lire21IvW23LAqGQGRqjo11SH+HWwRsrBa7ruGCCtrQzcm l6HnSCAH/mfeIx6bSE4/mVsnHUos3UdHly7BybUCfyfju8mTDJ6Gu6ZNCQ5l6HVYD2wQ 1pQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:to:from:subject:message-id:date :user-agent:mime-version:content-language; bh=szd7gGfeqRafDKK47gI7gBHbCMFVGSNd9Bn1rjbH+EU=; b=ZFxVHhmyt+5+LeYqmkt+Hz6l1p0wUQIWD4pTNcJv5t5fjyK7r/6AlMjIj55j1cZXUJ 40m0OadeXLCeUZ0VWOpPaCOOynnKN85ZtWD3LJR2AN9mWspnKzeyrnfl6xnygo6bbatH UPHtevecSJ/y7GMVv73p9fLDAYJJeqwsafiz/vKDvbIcty27oxPn3RkHT5cIY9q2NRh+ 7fs3vKQUEtrIGOXfGYg1RgBW2wBTRQu3w0oNG5mGORAmtJAzEXj1uOkQDis4Oy/IWh0C VQaJt6P/TopiTCbrlbj6h6XrSSrx4wpEqo2uJr2bdeiuM+TZAxgHPEDtcSVz7PgzTrfZ lOzg== X-Gm-Message-State: AOAM530+A+d0HmmtB1lNDQd+T5x/hhHRKpPCFmOkX031kV6zhCBtb9Hp Y2GpH4yhr9hYMDbVnynPQbo= X-Google-Smtp-Source: ABdhPJzpBfuFEwsrL9+83KXSLHXwyJ1BAJdQfIzXfpqyMKTYVd7Y9hMWBQIzu1TGFk8dZKz9Y1oZEw== X-Received: by 2002:ac8:70c6:: with SMTP id g6mr2924522qtp.146.1606918777640; Wed, 02 Dec 2020 06:19:37 -0800 (PST) Received: from ?IPv6:2620:10d:c0a8:1102:fd8c:7733:5cca:4143? ([2620:10d:c091:480::1:3c95]) by smtp.googlemail.com with ESMTPSA id o16sm1907737qkg.27.2020.12.02.06.19.36 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 02 Dec 2020 06:19:36 -0800 (PST) To: GCC Patches From: Nathan Sidwell Subject: C++ Module Binding Vector Message-ID: <502423a4-a715-c2d9-039e-e473a81d6331@acm.org> Date: Wed, 2 Dec 2020 09:19:35 -0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.5.0 MIME-Version: 1.0 Content-Language: en-US X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, FREEMAIL_FORGED_FROMDOMAIN, FREEMAIL_FROM, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: , Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" This is modified from the original patch. firstly it contains a few more necessary bits. But mainly I renamed the entities from 'MODULE_foo' to 'BINDING_foo', as it's a vector of bindings used by modules (not a vector of modules). It also belongs in name-lookup.h. Pushing to trunk This adds the vector necessary to hold different module's namespace bindings. We add a new tree-node 'tree_binding_vec', which contains a sparse array, indexed by module number. To avoid space wasting, this is allocated in clusters using 'unsigned short' as the index value (so that's one of the upper bounds on module importing). If there are only bindings from the current TU, there is no vector, so we have the same representation as a non-module compilation. To support lazy loading, a binding slot can contain either a tree (the binding), or a cookie that the module machinery uses to load the required binding on demand. The first 2 or 3 slots end up being reserved for fixed meanings. There are a couple of flags we have to record on a binding, to know whether the same declaration could appear in two different slots. gcc/cp/ * cp-tree.def (BINDING_VECTOR): New. * name-lookup.h (struct binding_slot): New. (BINDING_VECTOR_SLOTS_PER_CLUSTER): New. (struct binding_index, struct binding_cluster): New. (BINDING_VECTOR_ALLOC_CLUSTERS, BINDING_VECTOR_CLUSTER_BASE) (BINDING_VECTOR_CLUSTER): New. (struct tree_binding_vec): New. (BINDING_VECTOR_NAME, BINDING_VECTOR_GLOBAL_DUPS_P) (BINDING_VECTOR_PARTITION_DUPS_P): New. (BINDING_BINDING_GLOBAL_P, BINDING_BINDING_PARTITION_P): New. (BINDING_VECTOR_PENDING_SPECIALIZATIONS) (BINDING_VECTOR_PENDING_IS_HEADER_P) (BINDING_VECTOR_PENDING_IS_PARTITION_P): New. * cp-tree.h (enum cp_tree_node_structure_enum): Add TS_CP_BINDING_VECTOR. (union lang_tree_node): Add binding_vec field. (make_binding_vec): Declare. (named_decl_hash::hash, named_decl_hash::equal): Check for binding vector. * decl.c (cp_tree_node_structure): Add BINDING_VECTOR case. * ptree.c (cxx_print_xnode): Add BINDING_VECTOR case. * tree.c (make_binding_vec): New. diff --git i/gcc/cp/cp-tree.def w/gcc/cp/cp-tree.def index a188576013b..4e73e46b4a0 100644 --- i/gcc/cp/cp-tree.def +++ w/gcc/cp/cp-tree.def @@ -233,6 +233,9 @@ DEFTREECODE (TEMPLATE_ID_EXPR, "template_id_expr", tcc_expression, 2) /* One of a set of overloaded functions. */ DEFTREECODE (OVERLOAD, "overload", tcc_exceptional, 0) +/* A vector of binding slots. */ +DEFTREECODE (BINDING_VECTOR, "binding_vector", tcc_exceptional, 0) + /* A pseudo-destructor, of the form "OBJECT.~DESTRUCTOR" or "OBJECT.SCOPE::~DESTRUCTOR. The first operand is the OBJECT. The second operand (if non-NULL) is the SCOPE. The third operand is diff --git i/gcc/cp/cp-tree.h w/gcc/cp/cp-tree.h index 021de76e142..b5d4fc0aba1 100644 --- i/gcc/cp/cp-tree.h +++ w/gcc/cp/cp-tree.h @@ -1665,6 +1665,7 @@ enum cp_tree_node_structure_enum { TS_CP_TPI, TS_CP_PTRMEM, TS_CP_OVERLOAD, + TS_CP_BINDING_VECTOR, TS_CP_BASELINK, TS_CP_TEMPLATE_DECL, TS_CP_DEFERRED_PARSE, @@ -1686,6 +1687,7 @@ union GTY((desc ("cp_tree_node_structure (&%h)"), struct template_parm_index GTY ((tag ("TS_CP_TPI"))) tpi; struct ptrmem_cst GTY ((tag ("TS_CP_PTRMEM"))) ptrmem; struct tree_overload GTY ((tag ("TS_CP_OVERLOAD"))) overload; + struct tree_binding_vec GTY ((tag ("TS_CP_BINDING_VECTOR"))) binding_vec; struct tree_baselink GTY ((tag ("TS_CP_BASELINK"))) baselink; struct tree_template_decl GTY ((tag ("TS_CP_TEMPLATE_DECL"))) template_decl; struct tree_deferred_parse GTY ((tag ("TS_CP_DEFERRED_PARSE"))) deferred_parse; @@ -7386,6 +7388,7 @@ extern tree hash_tree_cons (tree, tree, tree); extern tree hash_tree_chain (tree, tree); extern tree build_qualified_name (tree, tree, tree, bool); extern tree build_ref_qualified_type (tree, cp_ref_qualifier); +extern tree make_binding_vec (tree, unsigned clusters); inline tree ovl_first (tree) ATTRIBUTE_PURE; extern tree ovl_make (tree fn, tree next = NULL_TREE); @@ -8020,14 +8023,16 @@ type_unknown_p (const_tree expr) inline hashval_t named_decl_hash::hash (const value_type decl) { - tree name = OVL_NAME (decl); + tree name = (TREE_CODE (decl) == BINDING_VECTOR + ? BINDING_VECTOR_NAME (decl) : OVL_NAME (decl)); return name ? IDENTIFIER_HASH_VALUE (name) : 0; } inline bool named_decl_hash::equal (const value_type existing, compare_type candidate) { - tree name = OVL_NAME (existing); + tree name = (TREE_CODE (existing) == BINDING_VECTOR + ? BINDING_VECTOR_NAME (existing) : OVL_NAME (existing)); return candidate == name; } diff --git i/gcc/cp/decl.c w/gcc/cp/decl.c index 3dd4b076582..df76155a243 100644 --- i/gcc/cp/decl.c +++ w/gcc/cp/decl.c @@ -17594,6 +17594,7 @@ cp_tree_node_structure (union lang_tree_node * t) case DEFERRED_PARSE: return TS_CP_DEFERRED_PARSE; case IDENTIFIER_NODE: return TS_CP_IDENTIFIER; case LAMBDA_EXPR: return TS_CP_LAMBDA_EXPR; + case BINDING_VECTOR: return TS_CP_BINDING_VECTOR; case OVERLOAD: return TS_CP_OVERLOAD; case PTRMEM_CST: return TS_CP_PTRMEM; case STATIC_ASSERT: return TS_CP_STATIC_ASSERT; diff --git i/gcc/cp/name-lookup.h w/gcc/cp/name-lookup.h index 6d18539e730..9cc8a42f4bd 100644 --- i/gcc/cp/name-lookup.h +++ w/gcc/cp/name-lookup.h @@ -68,6 +68,125 @@ struct GTY(()) cxx_saved_binding { tree real_type_value; }; +/* To support lazy module loading, we squirrel away a section number + (and a couple of flags) in the binding slot of unloaded bindings. + We rely on pointers being aligned and setting the bottom bit to + mark a lazy value. GTY doesn't like an array of union, so we have + a containing struct. */ + +struct GTY(()) binding_slot { + union GTY((desc ("%1.is_lazy ()"))) binding_slot_lazy { + tree GTY((tag ("false"))) binding; + } u; + + operator tree & () + { + gcc_checking_assert (!is_lazy ()); + return u.binding; + } + binding_slot &operator= (tree t) + { + u.binding = t; + return *this; + } + bool is_lazy () const + { + return bool (uintptr_t (u.binding) & 1); + } + void set_lazy (unsigned snum) + { + gcc_checking_assert (!u.binding); + u.binding = tree (uintptr_t ((snum << 1) | 1)); + } + void or_lazy (unsigned snum) + { + gcc_checking_assert (is_lazy ()); + u.binding = tree (uintptr_t (u.binding) | (snum << 1)); + } + unsigned get_lazy () const + { + gcc_checking_assert (is_lazy ()); + return unsigned (uintptr_t (u.binding) >> 1); + } +}; + +/* Bindings for modules are held in a sparse array. There is always a + current TU slot, others are allocated as needed. By construction + of the importing mechanism we only ever need to append to the + array. Rather than have straight index/slot tuples, we bunch them + up for greater packing. + + The cluster representation packs well on a 64-bit system. */ + +#define BINDING_VECTOR_SLOTS_PER_CLUSTER 2 +struct binding_index { + unsigned short base; + unsigned short span; +}; + +struct GTY(()) binding_cluster +{ + binding_index GTY((skip)) indices[BINDING_VECTOR_SLOTS_PER_CLUSTER]; + binding_slot slots[BINDING_VECTOR_SLOTS_PER_CLUSTER]; +}; + +/* These two fields overlay lang flags. So don't use those. */ +#define BINDING_VECTOR_ALLOC_CLUSTERS(NODE) \ + (BINDING_VECTOR_CHECK (NODE)->base.u.dependence_info.clique) +#define BINDING_VECTOR_NUM_CLUSTERS(NODE) \ + (BINDING_VECTOR_CHECK (NODE)->base.u.dependence_info.base) +#define BINDING_VECTOR_CLUSTER_BASE(NODE) \ + (((tree_binding_vec *)BINDING_VECTOR_CHECK (NODE))->vec) +#define BINDING_VECTOR_CLUSTER_LAST(NODE) \ + (&BINDING_VECTOR_CLUSTER (NODE, BINDING_VECTOR_NUM_CLUSTERS (NODE) - 1)) +#define BINDING_VECTOR_CLUSTER(NODE,IX) \ + (((tree_binding_vec *)BINDING_VECTOR_CHECK (NODE))->vec[IX]) + +struct GTY(()) tree_binding_vec { + struct tree_base base; + tree name; + binding_cluster GTY((length ("%h.base.u.dependence_info.base"))) vec[1]; +}; + +/* The name of a module vector. */ +#define BINDING_VECTOR_NAME(NODE) \ + (((tree_binding_vec *)BINDING_VECTOR_CHECK (NODE))->name) + +/* tree_binding_vec does uses base.u.dependence_info.base field for + length. It does not have lang_flag etc available! */ + +/* These two flags note if a module-vector contains deduplicated + bindings (i.e. multiple declarations in different imports). */ +/* This binding contains duplicate references to a global module + entity. */ +#define BINDING_VECTOR_GLOBAL_DUPS_P(NODE) \ + (BINDING_VECTOR_CHECK (NODE)->base.static_flag) +/* This binding contains duplicate references to a partioned module + entity. */ +#define BINDING_VECTOR_PARTITION_DUPS_P(NODE) \ + (BINDING_VECTOR_CHECK (NODE)->base.volatile_flag) + +/* These two flags indicate the provenence of the bindings on this + particular vector slot. We can of course determine this from slot + number, but that's a relatively expensive lookup. This avoids + that when iterating. */ +/* This slot is part of the global module (a header unit). */ +#define MODULE_BINDING_GLOBAL_P(NODE) \ + (OVERLOAD_CHECK (NODE)->base.static_flag) +/* This slot is part of the current module (a partition or primary). */ +#define MODULE_BINDING_PARTITION_P(NODE) \ + (OVERLOAD_CHECK (NODE)->base.volatile_flag) + +/* There are specializations of a template keyed to this binding. */ +#define BINDING_VECTOR_PENDING_SPECIALIZATIONS_P(NODE) \ + (BINDING_VECTOR_CHECK (NODE)->base.public_flag) +/* The key is in a header unit (not a named module partition or + primary). */ +#define BINDING_VECTOR_PENDING_IS_HEADER_P(NODE) \ + (BINDING_VECTOR_CHECK (NODE)->base.protected_flag) +/* The key is in a named module (primary or partition). */ +#define BINDING_VECTOR_PENDING_IS_PARTITION_P(NODE) \ + (BINDING_VECTOR_CHECK (NODE)->base.private_flag) extern tree identifier_type_value (tree); extern void set_identifier_type_value (tree, tree); diff --git i/gcc/cp/ptree.c w/gcc/cp/ptree.c index a28b722f571..1ee107f23cc 100644 --- i/gcc/cp/ptree.c +++ w/gcc/cp/ptree.c @@ -250,6 +250,44 @@ cxx_print_xnode (FILE *file, tree node, int indent) print_node (file, "function", OVL_FUNCTION (node), indent + 4); print_node (file, "next", OVL_CHAIN (node), indent + 4); break; + case BINDING_VECTOR: + { + unsigned len = BINDING_VECTOR_NUM_CLUSTERS (node); + print_node (file, "name", BINDING_VECTOR_NAME (node), indent + 4); + fprintf (file, " clusters %u, alloc %u", len, + BINDING_VECTOR_ALLOC_CLUSTERS (node)); + for (unsigned ix = 0; ix != len; ix++) + { + binding_cluster *cluster = &BINDING_VECTOR_CLUSTER (node, ix); + char pfx[20]; + for (unsigned jx = 0; jx != BINDING_VECTOR_SLOTS_PER_CLUSTER; jx++) + if (cluster->indices[jx].span) + { + int len = sprintf (pfx, "module:%u", + cluster->indices[jx].base); + if (cluster->indices[jx].span > 1) + len + += sprintf (&pfx[len], "(+%u)", cluster->indices[jx].span); + len += sprintf (&pfx[len], " cluster:%u/%u", ix, jx); + binding_slot &slot = cluster->slots[jx]; + if (slot.is_lazy ()) + { + indent_to (file, indent + 4); + unsigned lazy = slot.get_lazy (); + fprintf (file, "%s snum:%u flags:%d", + pfx, lazy >> 2, lazy & 3); + } + else if (slot) + print_node (file, pfx, slot, indent + 4); + else + { + indent_to (file, indent + 4); + fprintf (file, "%s NULL", pfx); + } + } + } + } + break; case TEMPLATE_PARM_INDEX: print_node (file, "decl", TEMPLATE_PARM_DECL (node), indent+4); indent_to (file, indent + 3); diff --git i/gcc/cp/tree.c w/gcc/cp/tree.c index 28e591086b3..4113a34b0c1 100644 --- i/gcc/cp/tree.c +++ w/gcc/cp/tree.c @@ -2218,6 +2218,23 @@ build_ref_qualified_type (tree type, cp_ref_qualifier rqual) return build_cp_fntype_variant (type, rqual, raises, late); } +tree +make_binding_vec (tree name, unsigned clusters MEM_STAT_DECL) +{ + /* Stored in an unsigned short, but we're limited to the number of + modules anyway. */ + gcc_checking_assert (clusters <= (unsigned short)(~0)); + size_t length = (offsetof (tree_binding_vec, vec) + + clusters * sizeof (binding_cluster)); + tree vec = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT); + TREE_SET_CODE (vec, BINDING_VECTOR); + BINDING_VECTOR_NAME (vec) = name; + BINDING_VECTOR_ALLOC_CLUSTERS (vec) = clusters; + BINDING_VECTOR_NUM_CLUSTERS (vec) = 0; + + return vec; +} + /* Make a raw overload node containing FN. */ tree