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: 756 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp229787wro; Thu, 25 Aug 2022 06:06:12 -0700 (PDT) X-Google-Smtp-Source: AA6agR6+A8rTHru8XdeGg2EQcGIVY1sUawqNT6lVAQdzrb7E4JHz7iwS+AzX1ZFdvJ//CB3JpMM/ X-Received: by 2002:a05:6402:1f86:b0:447:8edd:1c4b with SMTP id c6-20020a0564021f8600b004478edd1c4bmr3112868edc.163.1661432771887; Thu, 25 Aug 2022 06:06:11 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661432771; cv=none; d=google.com; s=arc-20160816; b=h8q84PFokpfWymVUlogJPMTXTNeJipbZBmvd2m+pa6xkQhvOUfXhUqgP1U8TKB6tby FNCeY5iXfEA1+nlCX4Qy1LQbuZPlYdwmtYR3TfVeNXyDYSGGCAyjpNcP2OXFAhcjg/aF DeGbgstxiSATTU1BUKkFqmIgBkVUoM3AhJz/3sIO7dWdFHy1OPTVrfOh6WdgwBgJI3fP JmsWHsTWrfdYRyUHdwPH99EDRjVczvZT0wI7+ad4T7bKOyPeeNmauDBZXGJnJrnNMK6K UeOp2Bzf6tZQCI89lzJexD2bgh68Vz/xuuo56Mbs5AUv1eN2ePeO15YShK0apnta9T10 ibnA== 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:mime-version :user-agent:message-id:in-reply-to:date:references:subject :mail-followup-to:to:dmarc-filter:delivered-to:dkim-signature :dkim-filter; bh=+CtfJwzyv0HIFZUF0oJz99mnxZqru6p+ckXzMc9e7kc=; b=o2NSF5cBu5+lhMB/oxod4WMlwEZjUhu3TjEBH5/o3NxEMex0mGgtPS4PluJtz8MtBB yUX52C2UbnE2zZo6s3nZo3TCcrRqmNl2wh7H2Z2wKN0X+gvx/iSNomERzYOC5Mo/msJ+ rjZAPZB0Of1JIifv/hMybh7IJRYaduCFtANeSqA8+QLOc2wUiJSTFBD1nIGDuFZ/342F Tgi03lOYExJ0Y7vqaQtPn18GesF2fnVRbt4rbjcQEswWthDg5IWILRkg1RVuhq4wi7nE 3sTB+dD8cWxcYCtvMJYqBxMAs5gQ7TSnwyJsoB0pmpMgmEVEJQdnv6ySlDx8w5H2DVw3 HFBQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=ROa8FEZN; 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id q9-20020a056402518900b004461745c73esi6818455edd.586.2022.08.25.06.06.11 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Aug 2022 06:06:11 -0700 (PDT) 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=ROa8FEZN; 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 B02413851AA2 for ; Thu, 25 Aug 2022 13:06:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B02413851AA2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432763; 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=ROa8FEZNaV2eLj3IhXpQ/uQuiQC2ImCst/o2sak9jYdZixgiFqoZ5zqyTJXf8k4A3 yPy3HQa8ZV34uRULcqnR13+X6kiOLu7rjDlmYg1zjV/VXMuD2qJVnEwlCKo9x/clBH DlIQH9DhM4ylbqP7tmNtZpWRdHa2NDcX5yc1Vtsc= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742138530291849115?= X-GMAIL-MSGID: =?utf-8?q?1742138530291849115?= 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: 759 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp230713wro; Thu, 25 Aug 2022 06:07:48 -0700 (PDT) X-Google-Smtp-Source: AA6agR50AD+1Tpm0KmL0jCUDTiX6qr2wzi9crqi7UoXG/cAMAJvpv3T66DfYMz+A6tevo5O4WcPf X-Received: by 2002:a05:6402:1f8c:b0:43e:8fab:76c with SMTP id c12-20020a0564021f8c00b0043e8fab076cmr3176000edc.126.1661432868328; Thu, 25 Aug 2022 06:07:48 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661432868; cv=none; d=google.com; s=arc-20160816; b=S03ACrjpkazf/aLp7zWnfQyw9FFulOK3vbgBvsLNcBqR01lu84LzJueLJVIquVXazF TORkBoACrHhlDB2tQ7SjItCTjjDLlzoFlStvDvEYhFAiPA69UM3Z/0L3U/Lsz5Hnhitw 5d4NtD2XeL8Nvm9aoAPmFncfA3TdTDEGxW3UkBJ5dV8tT/aIk7lyNIzv59pk0rti0OL8 xSLQ/1K6NzjRxmKNNJKEjVY/eAROwuBhHc6KmkL/FaXWut/6lujyBazM5MWfa9FlJawz kfuMvCqfE0E5eOW4XCrnGAR4BZKIHAulO97wKFYWUPuR0UdYSP8tDMZZ/oTT58OkOraW AEkA== 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:mime-version :user-agent:message-id:in-reply-to:date:references:subject :mail-followup-to:to:dmarc-filter:delivered-to:dkim-signature :dkim-filter; bh=k9wComfpFpVT3leG+4Q8zsmp1j/JSOMOJ6K9uRfdxbY=; b=egKoFKIMmkHNAdhYkZ9sFDQ9ioYioQ1po1lsZkA44QNUijA3PxvPDMmXPI96PDZJPP edJHoWUdsRFaE9AyrTAqtcC2NbVG+lXawauOzxKCZe+r/SddKij+mlSH4aRl7xp7cGq1 lKE8GtkYP+z7FR0QI2mS9UP4Sw4goNI5BylB5zsh2/BPOFEzzxCmF5LPJC4sHPg4Ovhe 8C7MGPrTI2aHfB04fi9qOBvc2FBDePKjee8+E/ELjBx9Go8SfzSh4Qh+mcT4fdTEpH0E 5F2KZWqRrs+bUwXIxsfLo9FTAG81uSpgIWXDNVC1DadFOrv1qEptnwCXrhiVT7WbolVV swJQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=EoJUjkAV; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id ht8-20020a170907608800b007309eb6dcbfsi4160479ejc.372.2022.08.25.06.07.48 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Aug 2022 06:07:48 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=EoJUjkAV; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 ABED938515D8 for ; Thu, 25 Aug 2022 13:07:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org ABED938515D8 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432821; 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=EoJUjkAVILrQNErye9CeEPTJ/KFnxf0efu5vz3xALWZlkMxHx+DeKrT+MRFo/kP+L 6ReefCq8AIGnxSHfJtVXcFPzBBbkFN+/CafeWQ7cVgCpmJrbjvJrIKuoI/es/DOxL2 +ow1wcKOZ7a7JFo6tFZQN8yu6oihQuX6xTHyh0BU= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742138630891196223?= X-GMAIL-MSGID: =?utf-8?q?1742138630891196223?= 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: 757 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp230367wro; Thu, 25 Aug 2022 06:07:09 -0700 (PDT) X-Google-Smtp-Source: AA6agR52sT/BsZK78pJN1s0uhxpjhxnjX/ggwvPyG/xcS4CrYuElTUT/Jiu62hDZjwBuqJtOoKez X-Received: by 2002:a05:6402:11cb:b0:43c:c7a3:ff86 with SMTP id j11-20020a05640211cb00b0043cc7a3ff86mr3211615edw.383.1661432829373; Thu, 25 Aug 2022 06:07:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661432829; cv=none; d=google.com; s=arc-20160816; b=iH2Q9/80SDFP3NHDbinXNirI4iIjd0gfF6xbVrL3KJ+S7LvFPf3o3iipDzBNoLdx6j CM+KM/MhZhgsaog7ZG0b4E6zKttKy00ynjV30PkL54gbf1463qGR2+9IWPZwVborPaKo 9tJ03CySHhCbSAYKKlS7LHyKmHBNFChZUIkTjp/oAWPoan94u9GmWE/huaOh3Lpyv6Jt aL/bSvZjLvO+0m7SeC3it21cY+2LVln38T4DP0ORktxN1rFliHGImWKHkOAKmrZ7a+4y v8qqdsFGKdIUZoTxwwqoGGlN7CfvNxaKPLQOJjPgeayrpuewqx925OO5b0s6VT0FLY57 rzjQ== 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:mime-version :user-agent:message-id:in-reply-to:date:references:subject :mail-followup-to:to:dmarc-filter:delivered-to:dkim-signature :dkim-filter; bh=tIE3g9kFWzyIjYtK1QoyEcuTSi61dEsRZlwsRjcwDOM=; b=D00/LZ9GRPdvL/gDmdQgxNDwr7+/WlDyeg6eyrNi5CUa3DplyZaEXvQoX6dnheHQku i+yhdfiebECG062gZrX+EVBNxgpiflVUjg119MEfCay4ZK2qfriiKrV/vDsLFpg4EFin pZfOVtL2+RXjHbbsA7MeoSC1ixcETfdACT721ADET1RtokXPbsCEVr38nBpyhvV3Lacp XeZsdcJ60dgJNIziQzfRvBNogJdi62vDShL10IooivHfr2F5Ubn4kJ6j/fZThO7ZGnU6 +C+iOvvRSkpYHt18YTcawusoKcvo8VFQWGD8FGWOIe4ut27xIsgQWFfUYjwOEJ2WLt2d rVyA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=jJS6TvoG; 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 di15-20020a170906730f00b0073d7884a3c8si3937185ejc.594.2022.08.25.06.07.09 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Aug 2022 06:07:09 -0700 (PDT) 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=jJS6TvoG; 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 7F95E3851C23 for ; Thu, 25 Aug 2022 13:06:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7F95E3851C23 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432797; 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=jJS6TvoGsErt2NgOGVmlPr7Fq1fHMNd+Gu2or8JZ/EhEEypKUrslPnHhmdz7xZobV /4yp9JSqkrvhRDTC2LLdWWjpi3ST1+HKag4/GE3lF/OfXJfylnziac+qTYyO5a26wk c7mFsb2Gr88ayM7Mo1/Zx/3Q+/cgRKkLFRR7Ot8M= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742138590488561304?= X-GMAIL-MSGID: =?utf-8?q?1742138590488561304?= 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: 758 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp230577wro; Thu, 25 Aug 2022 06:07:34 -0700 (PDT) X-Google-Smtp-Source: AA6agR6rjEpKlrwxjvbZwYiqmeVhIAz2xjqonZzSWKK2BdWR/gefZxUojT4QEXPUelIfTapeWQNt X-Received: by 2002:a05:6402:14e:b0:443:f58:17e9 with SMTP id s14-20020a056402014e00b004430f5817e9mr3312320edu.106.1661432854803; Thu, 25 Aug 2022 06:07:34 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661432854; cv=none; d=google.com; s=arc-20160816; b=sV1cHHdX1QbokOQJcFKZf7BSrIF6FWTeBu6SZmo4xIgSVPZhLXUQOdGL3TqpVmsHVv R0U7hH+CEMHG2VdW4OhPmZE8fGIWncC4J7Bj5jF6p9Qsr71XPId3R/RGgoAQ526UZHUH o+eME3FSiJM7LHm7xH2o+Z0U1/C5E6uAWdiw0/mVFbICFabLacGKeKZCReOsTlG8J0PX MHpaFt9MVumrThzA9KUXhUBHlm+nZg67QvtHnfWhFWuLNA/h1GZ3kRPja3BJSAcjuBjz /qvdwCVk+wlb20SgBcz7eho+Bi63qRWXLVJzMmE6AgZ6if+zisqZjNrEzJos/W3W4g89 zFsA== 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:mime-version :user-agent:message-id:in-reply-to:date:references:subject :mail-followup-to:to:dmarc-filter:delivered-to:dkim-signature :dkim-filter; bh=kIjbxWmWQp0Ik7iSDzWPBrwWqQQl0RXLADo7hUQ9nNM=; b=CTqlbEYnNodX7iHpdbwc7OzSjXK6Y8Ohv1tFbjUNq5yKPNIOaD96YCoyx+6S4WsqIg tqAzqAOhn/uhAIVVV+h5Z8XVmG2KcbA1b3a3Fn92wQVOi6mb75SeIM/PHLZoXDpqOrXY 53Jm7/bo0AlWLJXdRFwQ8BcsVkkx56dC04ZLaMaRhNQPOV0qywh9CzDNcBmU4CTDVRte VHLT5lvvybzoCp9ERFrgTO/edBJ/Tj6AXGO5rrtlM+l82EsBFELMTJdwdasd6Zi5eAP5 1Mu9PWJFw/X4g9p+JpsfxJmEz2knCwB2EhXsFYAHjyYesnbg92hGcuPFY/9lr4FcrS5m TZJA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=erByo4Ns; 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 ht8-20020a170907608800b007309eb6dcbfsi4159939ejc.372.2022.08.25.06.07.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Aug 2022 06:07:34 -0700 (PDT) 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=erByo4Ns; 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 A7D5D3851178 for ; Thu, 25 Aug 2022 13:06:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A7D5D3851178 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432811; 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=erByo4Nseq62DJc/9laKXG7VRHYM4EjLYiFqWiDOQuhroKJzk6o7izz7hWaLczPPP TjAXmnu6j4SU1mIYL4nB49PSCxiSNkuRV2i1jvuhz5mxxHhm1HPfURx8vxSIjdEtzb EMyZmmwTIYvZ70ic4fS6zjLTRf4lmDZFQLSHZTAY= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742138616921848236?= X-GMAIL-MSGID: =?utf-8?q?1742138616921848236?= 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: 760 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp231212wro; Thu, 25 Aug 2022 06:08:36 -0700 (PDT) X-Google-Smtp-Source: AA6agR4OStcT9zZfEZCFf5ytse+dcyvW2rEnQl/dQBxMiHHli7xLHsUHyAt+e8S1mHWGxj/j0YfC X-Received: by 2002:a17:907:c0e:b0:731:614:e507 with SMTP id ga14-20020a1709070c0e00b007310614e507mr2497827ejc.529.1661432916600; Thu, 25 Aug 2022 06:08:36 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661432916; cv=none; d=google.com; s=arc-20160816; b=lEvl29H7oA05ZaDHTauKIWbfZPdkJq3HfeIP90yOLsDmAb3+JJhYFOt1vRfRTV45TN Vknmrxtxh7Wzflu7ODZREXQ4LfABdE6ajTPZ9ih3c3Hj+9dzAwcKIq5g9AFyEqe+UoT8 Ykxovt+dMTsbWXdTl5zoRcAePLpk0MDbamLzlvMVNWr9xvsOdLylClDwbXgOBQq3gW9R bAZu6YdgeKy06QmkZWbxzz3h7LyOfmuNl/IXTUmyhQU5U37TQf9GcS5kuqa9eA43ZPYy QAFre5UtJLMw8dYs3siq9iZaW/RKV8704p3MvXoq9hfmdNX12l5tAA3ZGluu+U2T3UWE by6g== 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:mime-version :user-agent:message-id:in-reply-to:date:references:subject :mail-followup-to:to:dmarc-filter:delivered-to:dkim-signature :dkim-filter; bh=ZWezgQVpkY3iwraAAYJLIBQ2sse71mShp3RE3AydjZs=; b=fzBeLHDuijJhLLbThX9ihDPP9TLT5WzpHV23GRhL1JzhxaunmLc5kIQtndeixfGjZ7 lFFhItU2Vg27S12/w1afSXeyjEtIxPRjU3zt+MaQ/76r6k1O1OqiicDGf6cH0ulsZRwS WOW897egBRokc7tmY+r8v8AaTiWZpTAmtz/4y8aZZ+CbHRkm4q+2IDiL7qYFfw34QTGM ZAIcEDJGA+Gb7HUkk+PrZjeG5F9Af2tHUd3A4fIHCIQXGE/PK9N7ZAmdFCL7Hqb3vJBO 9GwFu8QzbxoJ1CULD8hgMm1nuZw7JdNxLR10IRdLACfVNaLbp9UFitsGacnWPj1wiNii oOiw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=R3iagyxN; 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 l5-20020a170906794500b0073d6481dedesi4322316ejo.224.2022.08.25.06.08.36 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Aug 2022 06:08:36 -0700 (PDT) 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=R3iagyxN; 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 395983850220 for ; Thu, 25 Aug 2022 13:07:56 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 395983850220 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661432876; 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=R3iagyxNRAyYoKfjPsz2+fgmIV8zs64mtNk9YcOeeKqWBrIKJXqFG5Gu0ngcfZys+ bJ0JLF1Mfoh/yYGKyM7C2o3ChfEE3+Y2Bv9imcyNWEPIxQyJk9iGxAE2TDJvWL67ow 8KAnHwReL6HZQHSSN1OMq1JysEA3cJD0vw0Bj95U= 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742138682109535341?= X-GMAIL-MSGID: =?utf-8?q?1742138682109535341?= 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