From patchwork Thu Aug 25 13:05:17 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1670253 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=8.43.85.97; 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=UnvD1eUI; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (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 4MD39f6dfMz1ygm for ; Thu, 25 Aug 2022 23:05:42 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 31D4C3854143 for ; Thu, 25 Aug 2022 13:05:40 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 31D4C3854143 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432740; bh=+CtfJwzyv0HIFZUF0oJz99mnxZqru6p+ckXzMc9e7kc=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=UnvD1eUIo0HxNnsvpTSaV0XiWq3lDQy2+mOMvhODdo1FfVxuhKYB8E56IW7ILFLqr avMqYgUi09YaK0isD4X8zMugrILD/h+kqyYbIDhkMyVQfs4IjE0psKdDV5C6sokM3m kKGp53RChKDbw3V7kQxQkf/z79N8K62Q5Tksf/jg= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id D2EC83852742 for ; Thu, 25 Aug 2022 13:05:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D2EC83852742 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 018E5ED1 for ; Thu, 25 Aug 2022 06:05:24 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.62]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 1046C3F71A for ; Thu, 25 Aug 2022 06:05:18 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH 1/6] Split code out of vectorizable_slp_permutation References: Date: Thu, 25 Aug 2022 14:05:17 +0100 In-Reply-To: (Richard Sandiford's message of "Thu, 25 Aug 2022 14:04:47 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-50.7 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" A later patch needs to test whether the target supports a lane_permutation_t without having to construct a full SLP node to test that. This patch splits out most of the work of vectorizable_slp_permutation into a subroutine, so that properties of the permutation can be passed explicitly without disturbing the main interface. The new subroutine still uses an slp_tree argument to get things like the number of lanes and the vector type. That's a bit clunky, but it seemed like the least worst option. gcc/ * tree-vect-slp.cc (vectorizable_slp_permutation_1): Split out from... (vectorizable_slp_permutation): ...here. --- gcc/tree-vect-slp.cc | 98 +++++++++++++++++++++++++++++--------------- 1 file changed, 66 insertions(+), 32 deletions(-) diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc index dab5daddcc5..13c242e5012 100644 --- a/gcc/tree-vect-slp.cc +++ b/gcc/tree-vect-slp.cc @@ -6976,20 +6976,22 @@ vect_add_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, SLP_TREE_VEC_STMTS (node).quick_push (perm_stmt); } -/* Vectorize the SLP permutations in NODE as specified - in SLP_TREE_LANE_PERMUTATION which is a vector of pairs of SLP - child number and lane number. - Interleaving of two two-lane two-child SLP subtrees (not supported): - [ { 0, 0 }, { 1, 0 }, { 0, 1 }, { 1, 1 } ] - A blend of two four-lane two-child SLP subtrees: - [ { 0, 0 }, { 1, 1 }, { 0, 2 }, { 1, 3 } ] - Highpart of a four-lane one-child SLP subtree (not supported): - [ { 0, 2 }, { 0, 3 } ] - Where currently only a subset is supported by code generating below. */ +/* Subroutine of vectorizable_slp_permutation. Check whether the target + can perform permutation PERM on the (1 or 2) input nodes in CHILDREN. + If GSI is nonnull, emit the permutation there. -static bool -vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, - slp_tree node, stmt_vector_for_cost *cost_vec) + When GSI is null, the only purpose of NODE is to give properties + of the result, such as the vector type and number of SLP lanes. + The node does not need to be a VEC_PERM_EXPR. + + If the target supports the operation, return the number of individual + VEC_PERM_EXPRs needed, otherwise return -1. Print information to the + dump file if DUMP_P is true. */ + +static int +vectorizable_slp_permutation_1 (vec_info *vinfo, gimple_stmt_iterator *gsi, + slp_tree node, lane_permutation_t &perm, + vec &children, bool dump_p) { tree vectype = SLP_TREE_VECTYPE (node); @@ -7001,7 +7003,7 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, poly_uint64 nunits = TYPE_VECTOR_SUBPARTS (vectype); bool repeating_p = multiple_p (nunits, SLP_TREE_LANES (node)); tree op_vectype = NULL_TREE; - FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) + FOR_EACH_VEC_ELT (children, i, child) if (SLP_TREE_VECTYPE (child)) { op_vectype = SLP_TREE_VECTYPE (child); @@ -7009,25 +7011,24 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, } if (!op_vectype) op_vectype = vectype; - FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child) + FOR_EACH_VEC_ELT (children, i, child) { if ((SLP_TREE_DEF_TYPE (child) != vect_internal_def && !vect_maybe_update_slp_op_vectype (child, op_vectype)) || !types_compatible_p (SLP_TREE_VECTYPE (child), op_vectype) || !types_compatible_p (TREE_TYPE (vectype), TREE_TYPE (op_vectype))) { - if (dump_enabled_p ()) + if (dump_p) dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, "Unsupported vector types in lane permutation\n"); - return false; + return -1; } if (SLP_TREE_LANES (child) != SLP_TREE_LANES (node)) repeating_p = false; } - vec > &perm = SLP_TREE_LANE_PERMUTATION (node); gcc_assert (perm.length () == SLP_TREE_LANES (node)); - if (dump_enabled_p ()) + if (dump_p) { dump_printf_loc (MSG_NOTE, vect_location, "vectorizing permutation"); @@ -7076,11 +7077,11 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, /* Calculate every element of every permute mask vector explicitly, instead of relying on the pattern described above. */ if (!nunits.is_constant (&npatterns)) - return false; + return -1; nelts_per_pattern = ncopies = 1; if (loop_vec_info linfo = dyn_cast (vinfo)) if (!LOOP_VINFO_VECT_FACTOR (linfo).is_constant (&ncopies)) - return false; + return -1; noutputs_per_mask = 1; } unsigned olanes = ncopies * SLP_TREE_LANES (node); @@ -7093,13 +7094,13 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, auto_vec, unsigned> > vperm; auto_vec active_lane; vperm.create (olanes); - active_lane.safe_grow_cleared (SLP_TREE_CHILDREN (node).length (), true); + active_lane.safe_grow_cleared (children.length (), true); for (unsigned i = 0; i < ncopies; ++i) { for (unsigned pi = 0; pi < perm.length (); ++pi) { std::pair p = perm[pi]; - tree vtype = SLP_TREE_VECTYPE (SLP_TREE_CHILDREN (node)[p.first]); + tree vtype = SLP_TREE_VECTYPE (children[p.first]); if (repeating_p) vperm.quick_push ({{p.first, 0}, p.second + active_lane[p.first]}); else @@ -7112,12 +7113,19 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, } } /* Advance to the next group. */ - for (unsigned j = 0; j < SLP_TREE_CHILDREN (node).length (); ++j) - active_lane[j] += SLP_TREE_LANES (SLP_TREE_CHILDREN (node)[j]); + for (unsigned j = 0; j < children.length (); ++j) + active_lane[j] += SLP_TREE_LANES (children[j]); } - if (dump_enabled_p ()) + if (dump_p) { + dump_printf_loc (MSG_NOTE, vect_location, + "vectorizing permutation"); + for (unsigned i = 0; i < perm.length (); ++i) + dump_printf (MSG_NOTE, " op%u[%u]", perm[i].first, perm[i].second); + if (repeating_p) + dump_printf (MSG_NOTE, " (repeat %d)\n", SLP_TREE_LANES (node)); + dump_printf (MSG_NOTE, "\n"); dump_printf_loc (MSG_NOTE, vect_location, "as"); for (unsigned i = 0; i < vperm.length (); ++i) { @@ -7163,12 +7171,12 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, } else { - if (dump_enabled_p ()) + if (dump_p) dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, "permutation requires at " "least three vectors\n"); gcc_assert (!gsi); - return false; + return -1; } mask[index++] = mask_element; @@ -7190,7 +7198,7 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, TYPE_VECTOR_SUBPARTS (op_vectype), &c) || c != 2))) { - if (dump_enabled_p ()) + if (dump_p) { dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, @@ -7203,7 +7211,7 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, dump_printf (MSG_MISSED_OPTIMIZATION, "}\n"); } gcc_assert (!gsi); - return false; + return -1; } if (!identity_p) @@ -7214,8 +7222,8 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, second_vec = first_vec; slp_tree - first_node = SLP_TREE_CHILDREN (node)[first_vec.first], - second_node = SLP_TREE_CHILDREN (node)[second_vec.first]; + first_node = children[first_vec.first], + second_node = children[second_vec.first]; tree mask_vec = NULL_TREE; if (!identity_p) @@ -7240,6 +7248,32 @@ vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, } } + return nperms; +} + +/* Vectorize the SLP permutations in NODE as specified + in SLP_TREE_LANE_PERMUTATION which is a vector of pairs of SLP + child number and lane number. + Interleaving of two two-lane two-child SLP subtrees (not supported): + [ { 0, 0 }, { 1, 0 }, { 0, 1 }, { 1, 1 } ] + A blend of two four-lane two-child SLP subtrees: + [ { 0, 0 }, { 1, 1 }, { 0, 2 }, { 1, 3 } ] + Highpart of a four-lane one-child SLP subtree (not supported): + [ { 0, 2 }, { 0, 3 } ] + Where currently only a subset is supported by code generating below. */ + +static bool +vectorizable_slp_permutation (vec_info *vinfo, gimple_stmt_iterator *gsi, + slp_tree node, stmt_vector_for_cost *cost_vec) +{ + tree vectype = SLP_TREE_VECTYPE (node); + lane_permutation_t &perm = SLP_TREE_LANE_PERMUTATION (node); + int nperms = vectorizable_slp_permutation_1 (vinfo, gsi, node, perm, + SLP_TREE_CHILDREN (node), + dump_enabled_p ()); + if (nperms < 0) + return false; + if (!gsi) record_stmt_cost (cost_vec, nperms, vec_perm, node, vectype, 0, vect_body); From patchwork Thu Aug 25 13:05:33 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1670256 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=h2pRCAzP; 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 4MD3Bm0twYz1yhC for ; Thu, 25 Aug 2022 23:06:40 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E93413851C35 for ; Thu, 25 Aug 2022 13:06:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E93413851C35 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432797; bh=k9wComfpFpVT3leG+4Q8zsmp1j/JSOMOJ6K9uRfdxbY=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=h2pRCAzPkcT16kMzpR4D3QLAsR2MCCdg5k7YSckW1v511m+bGEPzfYSH1xu7oMEcu MwLov/Aw+u3qBP+jcoBWqiCGm+LH4fgf6HsIOD801aF6VLLnnuy1tpIsNpCOOu6ggK OszwHbnOe9rfXP+Idp9Z0aoUcL04qlJKA3JOsMKs= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id EB8F53851C35 for ; Thu, 25 Aug 2022 13:05:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EB8F53851C35 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 29229D6E for ; Thu, 25 Aug 2022 06:05:40 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.62]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 39CCD3F71A for ; Thu, 25 Aug 2022 06:05:35 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH 2/6] Split code out of vect_transform_slp_perm_load References: Date: Thu, 25 Aug 2022 14:05:33 +0100 In-Reply-To: (Richard Sandiford's message of "Thu, 25 Aug 2022 14:04:47 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-50.7 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Similarly to the previous vectorizable_slp_permutation patch, this one splits out the main part of vect_transform_slp_perm_load so that a later patch can test a permutation without constructing a node for it. Also fixes a lingering use of STMT_VINFO_VECTYPE. gcc/ * tree-vect-slp.cc (vect_transform_slp_perm_load_1): Split out from... (vect_transform_slp_perm_load): ...here. Use SLP_TREE_VECTYPE instead of STMT_VINFO_VECTYPE. --- gcc/tree-vect-slp.cc | 54 ++++++++++++++++++++++++++++++-------------- 1 file changed, 37 insertions(+), 17 deletions(-) diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc index 13c242e5012..64b3379b530 100644 --- a/gcc/tree-vect-slp.cc +++ b/gcc/tree-vect-slp.cc @@ -6631,23 +6631,23 @@ vect_get_slp_defs (vec_info *, } } -/* Generate vector permute statements from a list of loads in DR_CHAIN. - If ANALYZE_ONLY is TRUE, only check that it is possible to create valid - permute statements for the SLP node NODE. Store the number of vector - permute instructions in *N_PERMS and the number of vector load - instructions in *N_LOADS. If DCE_CHAIN is true, remove all definitions - that were not needed. */ +/* A subroutine of vect_transform_slp_perm_load with two extra arguments: + - PERM gives the permutation that the caller wants to use for NODE, + which might be different from SLP_LOAD_PERMUTATION. + - DUMP_P controls whether the function dumps information. */ -bool -vect_transform_slp_perm_load (vec_info *vinfo, - slp_tree node, const vec &dr_chain, - gimple_stmt_iterator *gsi, poly_uint64 vf, - bool analyze_only, unsigned *n_perms, - unsigned int *n_loads, bool dce_chain) +static bool +vect_transform_slp_perm_load_1 (vec_info *vinfo, slp_tree node, + load_permutation_t &perm, + const vec &dr_chain, + gimple_stmt_iterator *gsi, poly_uint64 vf, + bool analyze_only, bool dump_p, + unsigned *n_perms, unsigned int *n_loads, + bool dce_chain) { stmt_vec_info stmt_info = SLP_TREE_SCALAR_STMTS (node)[0]; int vec_index = 0; - tree vectype = STMT_VINFO_VECTYPE (stmt_info); + tree vectype = SLP_TREE_VECTYPE (node); unsigned int group_size = SLP_TREE_SCALAR_STMTS (node).length (); unsigned int mask_element; machine_mode mode; @@ -6732,8 +6732,7 @@ vect_transform_slp_perm_load (vec_info *vinfo, { unsigned int iter_num = j / group_size; unsigned int stmt_num = j % group_size; - unsigned int i = (iter_num * DR_GROUP_SIZE (stmt_info) - + SLP_TREE_LOAD_PERMUTATION (node)[stmt_num]); + unsigned int i = (iter_num * DR_GROUP_SIZE (stmt_info) + perm[stmt_num]); bitmap_set_bit (used_in_lanes, i); if (repeating_p) { @@ -6759,7 +6758,7 @@ vect_transform_slp_perm_load (vec_info *vinfo, } else { - if (dump_enabled_p ()) + if (dump_p) dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, "permutation requires at " "least three vectors %G", @@ -6780,7 +6779,7 @@ vect_transform_slp_perm_load (vec_info *vinfo, indices.new_vector (mask, second_vec_index == -1 ? 1 : 2, nunits); if (!can_vec_perm_const_p (mode, mode, indices)) { - if (dump_enabled_p ()) + if (dump_p) { dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, @@ -6896,6 +6895,27 @@ vect_transform_slp_perm_load (vec_info *vinfo, return true; } +/* Generate vector permute statements from a list of loads in DR_CHAIN. + If ANALYZE_ONLY is TRUE, only check that it is possible to create valid + permute statements for the SLP node NODE. Store the number of vector + permute instructions in *N_PERMS and the number of vector load + instructions in *N_LOADS. If DCE_CHAIN is true, remove all definitions + that were not needed. */ + +bool +vect_transform_slp_perm_load (vec_info *vinfo, + slp_tree node, const vec &dr_chain, + gimple_stmt_iterator *gsi, poly_uint64 vf, + bool analyze_only, unsigned *n_perms, + unsigned int *n_loads, bool dce_chain) +{ + return vect_transform_slp_perm_load_1 (vinfo, node, + SLP_TREE_LOAD_PERMUTATION (node), + dr_chain, gsi, vf, analyze_only, + dump_enabled_p (), n_perms, n_loads, + dce_chain); +} + /* Produce the next vector result for SLP permutation NODE by adding a vector statement at GSI. If MASK_VEC is nonnull, add: From patchwork Thu Aug 25 13:05:51 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1670254 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=JALnkvLJ; 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 4MD3BJ2YYRz1ygm for ; Thu, 25 Aug 2022 23:06:16 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3A25A3851A9B for ; Thu, 25 Aug 2022 13:06:14 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3A25A3851A9B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432774; bh=tIE3g9kFWzyIjYtK1QoyEcuTSi61dEsRZlwsRjcwDOM=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=JALnkvLJzr5i5l2Ujjr/g3acm/19XI7gvqKwg+SY36eyHnQ+0VItGj0qkp/61CMdz wCJo9G3+bzgiP/UDFUhhpWrRW3+bJGdMWI09xHntkfpQHafvkViX3lSNIRKy/I+1hB pePDFsPJEmY5nftMhuVNxzQsEvPdsI/hyATvmMVY= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 948313851A8E for ; Thu, 25 Aug 2022 13:05:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 948313851A8E Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id CDB7DD6E for ; Thu, 25 Aug 2022 06:05:57 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.62]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id DE6203F71A for ; Thu, 25 Aug 2022 06:05:52 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH 3/6] Make graphds_scc pass the node order back to callers References: Date: Thu, 25 Aug 2022 14:05:51 +0100 In-Reply-To: (Richard Sandiford's message of "Thu, 25 Aug 2022 14:04:47 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-50.6 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" As a side-effect, graphds_scc constructs a vector in which all nodes in an SCC are listed consecutively. This can be useful information, so that the patch adds an optional pass-back parameter for it. The interface is similar to the one for graphds_dfs. gcc/ * graphds.cc (graphds_scc): Add a pass-back parameter for the final node order. --- gcc/graphds.cc | 13 ++++++++++--- gcc/graphds.h | 3 ++- 2 files changed, 12 insertions(+), 4 deletions(-) diff --git a/gcc/graphds.cc b/gcc/graphds.cc index 91a2ca5c225..2a108fd475f 100644 --- a/gcc/graphds.cc +++ b/gcc/graphds.cc @@ -281,7 +281,14 @@ graphds_dfs (struct graph *g, int *qs, int nq, vec *qt, numbers assigned by the previous pass. If SUBGRAPH is not NULL, it specifies the subgraph of G whose strongly connected components we want to determine. If SKIP_EDGE_P is not NULL, it points to a callback function. - Edge E will be skipped if callback function returns true. + Edge E will be skipped if callback function returns true. If SCC_GROUPING + is not null, the nodes will be added to it in the following order: + + - If SCC A is a direct or indirect predecessor of SCC B in the SCC dag, + A's nodes come before B's nodes. + + - All of an SCC's nodes are listed consecutively, although the order + of the nodes within an SCC is not really meaningful. After running this function, v->component is the number of the strongly connected component for each vertex of G. Returns the number of the @@ -289,7 +296,7 @@ graphds_dfs (struct graph *g, int *qs, int nq, vec *qt, int graphds_scc (struct graph *g, bitmap subgraph, - skip_edge_callback skip_edge_p) + skip_edge_callback skip_edge_p, vec *scc_grouping) { int *queue = XNEWVEC (int, g->n_vertices); vec postorder = vNULL; @@ -317,7 +324,7 @@ graphds_scc (struct graph *g, bitmap subgraph, for (i = 0; i < nq; i++) queue[i] = postorder[nq - i - 1]; - comp = graphds_dfs (g, queue, nq, NULL, true, subgraph, skip_edge_p); + comp = graphds_dfs (g, queue, nq, scc_grouping, true, subgraph, skip_edge_p); free (queue); postorder.release (); diff --git a/gcc/graphds.h b/gcc/graphds.h index c54d8767fa7..e0e4d802cbb 100644 --- a/gcc/graphds.h +++ b/gcc/graphds.h @@ -58,7 +58,8 @@ void identify_vertices (struct graph *, int, int); typedef bool (*skip_edge_callback) (struct graph_edge *); int graphds_dfs (struct graph *, int *, int, vec *, bool, bitmap, skip_edge_callback = NULL); -int graphds_scc (struct graph *, bitmap, skip_edge_callback = NULL); +int graphds_scc (struct graph *, bitmap, skip_edge_callback = NULL, + vec * = NULL); void graphds_domtree (struct graph *, int, int *, int *, int *); typedef void (*graphds_edge_callback) (struct graph *, struct graph_edge *, void *); From patchwork Thu Aug 25 13:06:04 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1670255 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=8.43.85.97; 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=SaVA5WT4; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (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 4MD3BZ1Zcqz1ygm for ; Thu, 25 Aug 2022 23:06:30 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 061EE38515DB for ; Thu, 25 Aug 2022 13:06:28 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 061EE38515DB DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432788; bh=kIjbxWmWQp0Ik7iSDzWPBrwWqQQl0RXLADo7hUQ9nNM=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=SaVA5WT4hiDr6xokb0nhKy41GzQNmnQD7kTix94Oz+o7GQrQm6HNj/YqVwAQEA438 SrWHSggrFvwChTNTJBJ2w4MhwjIy+5II3RYS/PEGYt51e//YJge5J8dsZ6sXoAyItK /btBAL81UHEQXTrSjdb3wDNTnNSf6KKWrFBqc/bY= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id C6AA438515D5 for ; Thu, 25 Aug 2022 13:06:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C6AA438515D5 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 245C8D6E for ; Thu, 25 Aug 2022 06:06:11 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.62]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 34ADE3F71A for ; Thu, 25 Aug 2022 06:06:06 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH 4/6] Rearrange unbounded_hashmap_traits References: Date: Thu, 25 Aug 2022 14:06:04 +0100 In-Reply-To: (Richard Sandiford's message of "Thu, 25 Aug 2022 14:04:47 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-50.5 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" int_hash combines two kinds of operation: (1) hashing and equality of integers (2) using spare integer encodings to represent empty and deleted slots (1) is really independent of (2), and could be useful in cases where no spare integer encodings are available. This patch adds a base class (int_hash_base) for (1) and makes int_hash inherit from it. If we follow a similar style for future hashes, we can make unbounded_hashmap_traits take the "base" hash for the key as a template parameter, rather than requiring every type of key to have a separate derivative of unbounded_hashmap_traits. A later patch applies this to vector keys. No functional change intended. gcc/ * hash-traits.h (int_hash_base): New struct, split out from... (int_hash): ...this class, which now inherits from int_hash_base. * hash-map-traits.h (unbounded_hashmap_traits): Take a template parameter for the key that provides hash and equality functions. (unbounded_int_hashmap_traits): Turn into a type alias of unbounded_hashmap_traits. --- gcc/hash-map-traits.h | 74 +++++++++++++++++++++++-------------------- gcc/hash-traits.h | 42 ++++++++++++++---------- 2 files changed, 65 insertions(+), 51 deletions(-) diff --git a/gcc/hash-map-traits.h b/gcc/hash-map-traits.h index fad0c7d52c5..d729d358070 100644 --- a/gcc/hash-map-traits.h +++ b/gcc/hash-map-traits.h @@ -105,14 +105,19 @@ struct simple_cache_map_traits: public simple_hashmap_traits static const bool maybe_mx = false; }; -/* Implement traits for a hash_map with values of type Value for cases - in which the key cannot represent empty and deleted slots. Instead - record empty and deleted entries in Value. Derived classes must - implement the hash and equal_keys functions. */ +/* Implement traits for a hash_map with keys of type Key and values of + type Value for cases in which the key cannot represent empty and + deleted slots. Instead record empty and deleted entries in Value. */ -template +template struct unbounded_hashmap_traits { + typedef typename Key::value_type key_type; + + static hashval_t hash (const typename Key::value_type &); + static bool equal_keys (const typename Key::value_type &, + const typename Key::compare_type &); + template static inline void remove (T &); static const bool empty_zero_p = default_hash_traits ::empty_zero_p; template static inline bool is_empty (const T &); @@ -121,42 +126,59 @@ struct unbounded_hashmap_traits template static inline void mark_deleted (T &); }; -template +template +inline hashval_t +unbounded_hashmap_traits +::hash (const typename Key::value_type &key) +{ + return Key::hash (key); +} + +template +inline bool +unbounded_hashmap_traits +::equal_keys (const typename Key::value_type &x, + const typename Key::compare_type &y) +{ + return Key::equal (x, y); +} + +template template inline void -unbounded_hashmap_traits ::remove (T &entry) +unbounded_hashmap_traits ::remove (T &entry) { default_hash_traits ::remove (entry.m_value); } -template +template template inline bool -unbounded_hashmap_traits ::is_empty (const T &entry) +unbounded_hashmap_traits ::is_empty (const T &entry) { return default_hash_traits ::is_empty (entry.m_value); } -template +template template inline bool -unbounded_hashmap_traits ::is_deleted (const T &entry) +unbounded_hashmap_traits ::is_deleted (const T &entry) { return default_hash_traits ::is_deleted (entry.m_value); } -template +template template inline void -unbounded_hashmap_traits ::mark_empty (T &entry) +unbounded_hashmap_traits ::mark_empty (T &entry) { default_hash_traits ::mark_empty (entry.m_value); } -template +template template inline void -unbounded_hashmap_traits ::mark_deleted (T &entry) +unbounded_hashmap_traits ::mark_deleted (T &entry) { default_hash_traits ::mark_deleted (entry.m_value); } @@ -166,25 +188,7 @@ unbounded_hashmap_traits ::mark_deleted (T &entry) slots. */ template -struct unbounded_int_hashmap_traits : unbounded_hashmap_traits -{ - typedef Key key_type; - static inline hashval_t hash (Key); - static inline bool equal_keys (Key, Key); -}; - -template -inline hashval_t -unbounded_int_hashmap_traits ::hash (Key k) -{ - return k; -} - -template -inline bool -unbounded_int_hashmap_traits ::equal_keys (Key k1, Key k2) -{ - return k1 == k2; -} +using unbounded_int_hashmap_traits + = unbounded_hashmap_traits , Value>; #endif // HASH_MAP_TRAITS_H diff --git a/gcc/hash-traits.h b/gcc/hash-traits.h index bef0bd42d04..55b81eb0f9e 100644 --- a/gcc/hash-traits.h +++ b/gcc/hash-traits.h @@ -85,41 +85,51 @@ typed_noop_remove ::remove (Type &) { } +/* Base traits for integer type Type, providing just the hash and + comparison functionality. */ -/* Hasher for integer type Type in which Empty is a spare value that can be - used to mark empty slots. If Deleted != Empty then Deleted is another - spare value that can be used for deleted slots; if Deleted == Empty then - hash table entries cannot be deleted. */ - -template -struct int_hash : typed_noop_remove +template +struct int_hash_base : typed_noop_remove { typedef Type value_type; typedef Type compare_type; static inline hashval_t hash (value_type); static inline bool equal (value_type existing, value_type candidate); - static inline void mark_deleted (Type &); - static const bool empty_zero_p = Empty == 0; - static inline void mark_empty (Type &); - static inline bool is_deleted (Type); - static inline bool is_empty (Type); }; -template +template inline hashval_t -int_hash ::hash (value_type x) +int_hash_base ::hash (value_type x) { return x; } -template +template inline bool -int_hash ::equal (value_type x, value_type y) +int_hash_base ::equal (value_type x, value_type y) { return x == y; } +/* Hasher for integer type Type in which Empty is a spare value that can be + used to mark empty slots. If Deleted != Empty then Deleted is another + spare value that can be used for deleted slots; if Deleted == Empty then + hash table entries cannot be deleted. */ + +template +struct int_hash : int_hash_base +{ + typedef Type value_type; + typedef Type compare_type; + + static inline void mark_deleted (Type &); + static const bool empty_zero_p = Empty == 0; + static inline void mark_empty (Type &); + static inline bool is_deleted (Type); + static inline bool is_empty (Type); +}; + template inline void int_hash ::mark_deleted (Type &x) From patchwork Thu Aug 25 13:06:18 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1670257 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=xv9qwzMz; 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 4MD3Cq0CSyz1ygm for ; Thu, 25 Aug 2022 23:07:35 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D0CD4385ED4D for ; Thu, 25 Aug 2022 13:07:32 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D0CD4385ED4D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432852; bh=ZWezgQVpkY3iwraAAYJLIBQ2sse71mShp3RE3AydjZs=; h=To:Subject:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=xv9qwzMzN96I/g67SuvHCSNegDIcd5jnjsxm1R8yVr/762dCt6AQGiBUxTtRyIeOS YZ1W8ZXUrnjZClSdVZzsIV3iBb10qFb+Fl4gTPKXwFdCozX7IuLfhJTnfWEd8ddw41 5My4veprVzDeuCOZ7pJ115NnJK6x1oYRqVcao7RM= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 905913851178 for ; Thu, 25 Aug 2022 13:06:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 905913851178 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id D2B8FD6E for ; Thu, 25 Aug 2022 06:06:24 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.62]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id E35653F71A for ; Thu, 25 Aug 2022 06:06:19 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH 5/6] Add base hash traits for vectors References: Date: Thu, 25 Aug 2022 14:06:18 +0100 In-Reply-To: (Richard Sandiford's message of "Thu, 25 Aug 2022 14:04:47 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-50.4 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch adds a class that provides basic hash/equal functions for vectors, based on corresponding traits for the element type. gcc/ * hash-traits.h (vec_hash_base): New class. (vec_free_hash_base): Likewise. --- gcc/hash-traits.h | 55 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+) diff --git a/gcc/hash-traits.h b/gcc/hash-traits.h index 55b81eb0f9e..f5d12706324 100644 --- a/gcc/hash-traits.h +++ b/gcc/hash-traits.h @@ -408,6 +408,61 @@ pair_hash ::is_empty (const value_type &x) return T1::is_empty (x.first); } +/* Base traits for vectors, providing just the hash and comparison + functionality. Type gives the corresponding traits for the element + type. */ + +template +struct vec_hash_base +{ + typedef vec value_type; + typedef vec compare_type; + + static inline hashval_t hash (value_type); + static inline bool equal (value_type, compare_type); +}; + +template +inline hashval_t +vec_hash_base ::hash (value_type x) +{ + inchash::hash hstate; + hstate.add_int (x.length ()); + for (auto &value : x) + hstate.merge_hash (Type::hash (value)); + return hstate.end (); +} + +template +inline bool +vec_hash_base ::equal (value_type x, compare_type y) +{ + if (x.length () != y.length ()) + return false; + for (unsigned int i = 0; i < x.length (); ++i) + if (!Type::equal (x[i], y[i])) + return false; + return true; +} + +/* Traits for vectors whose contents should be freed normally. */ + +template +struct vec_free_hash_base : vec_hash_base +{ + static void remove (typename vec_hash_base ::value_type &); +}; + +template +void +vec_free_hash_base +::remove (typename vec_hash_base ::value_type &x) +{ + for (auto &value : x) + Type::remove (x); + x.release (); +} + template struct default_hash_traits : T {}; template