From patchwork Mon Jul 8 13:44:45 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1957970 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=gd9mK5Uo; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=EDfe8twA; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=gd9mK5Uo; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=EDfe8twA; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WHlkB5h2Nz1xr9 for ; Mon, 8 Jul 2024 23:45:21 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DD39C3864827 for ; Mon, 8 Jul 2024 13:45:19 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by sourceware.org (Postfix) with ESMTPS id 936383861835 for ; Mon, 8 Jul 2024 13:44:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 936383861835 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 936383861835 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720446289; cv=none; b=YywzsaR8RU3erNzbb/UqyzGlt03TzCWUkYZmji9YwUVMZ+KQbJE6q/04DbCmqvNbJ+T8bRlezDBg0i0c82kKTUmTllTHrYwQMDrfkYF9aUI0nIji3oFhWhONKQ6X8nGe9GBSEqytqjK6XXYG/UJssh/Qgkmz65GzUJ/hjUxptTQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720446289; c=relaxed/simple; bh=8+87zEJ2buhBMFfl5GnU8IyFWUiTVkhCdlH4Vs9OQjE=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=oqlQ9/yC3ottW3tdSV4/++A62ivwQzt+ERBMcvneKYw3eONL7fORg/0LG8zOwGvh796U3s9Ukz/jebtsl9730LmY458WL16JI+/sTTcuT+BXWz7Yqob5Fj6ZuQosvD+EgrQ65SDtZIeZFkVVhwZ16bKcpw5cCNFHetllEkL8dDo= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from murzim.nue2.suse.org (unknown [10.168.4.243]) (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 smtp-out1.suse.de (Postfix) with ESMTPS id 7A5F3219AD for ; Mon, 8 Jul 2024 13:44:45 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1720446285; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=PC0D6b3GdKgUoFnJz/u+FPDBeSnMRBnnThUwJ6l774M=; b=gd9mK5UoCMoUtdHQsedTSB3oc+tydcIX6l6sx49aLclm0nLXTchJe1NMdxbLLWa81JkIMM jMGHYnt1Q81fr9sPbYUl1TWkUnf0O3lQXCQRBk+KEZN1st4AC8+EZsDSNcisNH3gZfCfV9 4oC/RdxO9p+6WLDvim14OoeVNuiZsx0= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1720446285; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=PC0D6b3GdKgUoFnJz/u+FPDBeSnMRBnnThUwJ6l774M=; b=EDfe8twAtIGQu+5bhVckjUMwAzlTc+FnGVHzgs47RLjk/uT7kID4h30DbnSe+63+nWutAv vR+DrAlbKSdjKlCg== Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1720446285; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=PC0D6b3GdKgUoFnJz/u+FPDBeSnMRBnnThUwJ6l774M=; b=gd9mK5UoCMoUtdHQsedTSB3oc+tydcIX6l6sx49aLclm0nLXTchJe1NMdxbLLWa81JkIMM jMGHYnt1Q81fr9sPbYUl1TWkUnf0O3lQXCQRBk+KEZN1st4AC8+EZsDSNcisNH3gZfCfV9 4oC/RdxO9p+6WLDvim14OoeVNuiZsx0= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1720446285; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=PC0D6b3GdKgUoFnJz/u+FPDBeSnMRBnnThUwJ6l774M=; b=EDfe8twAtIGQu+5bhVckjUMwAzlTc+FnGVHzgs47RLjk/uT7kID4h30DbnSe+63+nWutAv vR+DrAlbKSdjKlCg== Date: Mon, 8 Jul 2024 15:44:45 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH 1/2] lower SLP load permutation to interleaving MIME-Version: 1.0 X-Spamd-Result: default: False [-1.67 / 50.00]; BAYES_HAM(-3.00)[100.00%]; MISSING_MID(2.50)[]; NEURAL_HAM_LONG(-0.90)[-0.901]; NEURAL_HAM_SHORT(-0.17)[-0.854]; MIME_GOOD(-0.10)[text/plain]; RCPT_COUNT_ONE(0.00)[1]; RCVD_COUNT_ZERO(0.00)[0]; ARC_NA(0.00)[]; MISSING_XM_UA(0.00)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FUZZY_BLOCKED(0.00)[rspamd.com]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; TO_DN_NONE(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; FROM_HAS_DN(0.00)[] X-Spam-Score: -1.67 X-Spam-Level: X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Message-Id: <20240708134519.DD39C3864827@sourceware.org> The following emulates classical interleaving for SLP load permutes that we are unlikely handling natively. This is to handle cases where interleaving (or load/store-lanes) is the optimal choice for vectorizing even when we are doing that within SLP. An example would be void foo (int * __restrict a, int * b) { for (int i = 0; i < 16; ++i) { a[4*i + 0] = b[4*i + 0] * 3; a[4*i + 1] = b[4*i + 1] + 3; a[4*i + 2] = (b[4*i + 2] * 3 + 3); a[4*i + 3] = b[4*i + 3] * 3; } } where currently the SLP store is merging four single-lane SLP sub-graphs but none of the loads in it can be code-generated with V4SImode vectors and a VF of four as the permutes would need three vectors. The patch introduces a lowering phase after SLP discovery but before SLP pattern recognition or permute optimization that analyzes all loads from the same dataref group and creates an interleaving scheme starting from an unpermuted load. What can be handled is power-of-two group size, group size of three is handled in a followup, as is the possibility for doing the interleaving with a load-lanes like instruction. The patch has a fallback for when there are multi-lane groups and the resulting permutes to not fit interleaving. Code generation is not optimal when this triggers and might be worse than doing single-lane group interleaving. The patch handles gaps by representing them with NULL entries in SLP_TREE_SCALAR_STMTS for the unpermuted load node. The SLP discovery changes could be elided if we manually build the load node instead. SLP load nodes covering enough lanes to not need intermediate permutes are retained as having a load-permutation and do not use the single SLP load node for each dataref group. That's something we might want to change, making load-permutation something purely local to SLP discovery (but then SLP discovery could do part of the lowering). The patch misses CSEing intermediate generated permutes and registering them with the bst_map which is possibly required for SLP pattern detection in some cases. * tree-vect-slp.cc (vect_build_slp_tree_1): Handle NULL stmt. (vect_build_slp_tree_2): Likewise. Release load permutation when there's a NULL in SLP_TREE_SCALAR_STMTS and assert there's no actual permutation in that case. (vllp_cmp): New function. (vect_lower_load_permutations): Likewise. (vect_analyze_slp): Call it. * gcc.dg/vect/slp-11a.c: Expect SLP. * gcc.dg/vect/slp-12a.c: Likewise. * gcc.dg/vect/slp-51.c: New testcase. --- gcc/testsuite/gcc.dg/vect/slp-11a.c | 2 +- gcc/testsuite/gcc.dg/vect/slp-12a.c | 2 +- gcc/testsuite/gcc.dg/vect/slp-51.c | 17 ++ gcc/tree-vect-slp.cc | 343 +++++++++++++++++++++++++++- 4 files changed, 360 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/vect/slp-51.c diff --git a/gcc/testsuite/gcc.dg/vect/slp-11a.c b/gcc/testsuite/gcc.dg/vect/slp-11a.c index fcb7cf6c7a2..2efa1796757 100644 --- a/gcc/testsuite/gcc.dg/vect/slp-11a.c +++ b/gcc/testsuite/gcc.dg/vect/slp-11a.c @@ -72,4 +72,4 @@ int main (void) /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { target { vect_strided8 && vect_int_mult } } } } */ /* { dg-final { scan-tree-dump-times "vectorized 0 loops" 1 "vect" { target { ! { vect_strided8 && vect_int_mult } } } } } */ -/* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 0 "vect" } } */ +/* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 1 "vect" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/slp-12a.c b/gcc/testsuite/gcc.dg/vect/slp-12a.c index 2f98dc9da0b..fedf27b69d2 100644 --- a/gcc/testsuite/gcc.dg/vect/slp-12a.c +++ b/gcc/testsuite/gcc.dg/vect/slp-12a.c @@ -80,5 +80,5 @@ int main (void) /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { target { vect_strided8 && vect_int_mult } } } } */ /* { dg-final { scan-tree-dump-times "vectorized 0 loops" 1 "vect" { target { ! { vect_strided8 && vect_int_mult } } } } } */ -/* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 0 "vect" { target { { vect_strided8 && {! vect_load_lanes } } && vect_int_mult } } } } */ +/* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 1 "vect" { target { { vect_strided8 && {! vect_load_lanes } } && vect_int_mult } } } } */ /* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 0 "vect" { target { ! { vect_strided8 && vect_int_mult } } } } } */ diff --git a/gcc/testsuite/gcc.dg/vect/slp-51.c b/gcc/testsuite/gcc.dg/vect/slp-51.c new file mode 100644 index 00000000000..91ae763be30 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/slp-51.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ + +void foo (int * __restrict x, int *y) +{ + x = __builtin_assume_aligned (x, __BIGGEST_ALIGNMENT__); + y = __builtin_assume_aligned (y, __BIGGEST_ALIGNMENT__); + for (int i = 0; i < 1024; ++i) + { + x[4*i+0] = y[4*i+0]; + x[4*i+1] = y[4*i+2] * 2; + x[4*i+2] = y[4*i+0] + 3; + x[4*i+3] = y[4*i+2] * 2 - 5; + } +} + +/* Check we can handle SLP with gaps and an interleaving scheme. */ +/* { dg-final { scan-tree-dump "vectorizing stmts using SLP" "vect" { target { vect_int && vect_int_mult } } } } */ diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc index d0a8531fd3b..0f830c1ad9c 100644 --- a/gcc/tree-vect-slp.cc +++ b/gcc/tree-vect-slp.cc @@ -1080,10 +1080,15 @@ vect_build_slp_tree_1 (vec_info *vinfo, unsigned char *swap, stmt_vec_info stmt_info; FOR_EACH_VEC_ELT (stmts, i, stmt_info) { - gimple *stmt = stmt_info->stmt; swap[i] = 0; matches[i] = false; + if (!stmt_info) + { + matches[i] = true; + continue; + } + gimple *stmt = stmt_info->stmt; if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, "Build SLP for %G", stmt); @@ -1984,10 +1989,16 @@ vect_build_slp_tree_2 (vec_info *vinfo, slp_tree node, stmt_vec_info first_stmt_info = DR_GROUP_FIRST_ELEMENT (SLP_TREE_SCALAR_STMTS (node)[0]); bool any_permute = false; + bool any_null = false; FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), j, load_info) { int load_place; - if (STMT_VINFO_GROUPED_ACCESS (stmt_info)) + if (! load_info) + { + load_place = j; + any_null = true; + } + else if (STMT_VINFO_GROUPED_ACCESS (stmt_info)) load_place = vect_get_place_in_interleaving_chain (load_info, first_stmt_info); else @@ -1996,6 +2007,11 @@ vect_build_slp_tree_2 (vec_info *vinfo, slp_tree node, any_permute |= load_place != j; load_permutation.quick_push (load_place); } + if (any_null) + { + gcc_assert (!any_permute); + load_permutation.release (); + } if (gcall *stmt = dyn_cast (stmt_info->stmt)) { @@ -3944,6 +3960,312 @@ vect_analyze_slp_instance (vec_info *vinfo, return res; } +/* qsort comparator ordering SLP load nodes. */ + +static int +vllp_cmp (const void *a_, const void *b_) +{ + const slp_tree a = *(const slp_tree *)a_; + const slp_tree b = *(const slp_tree *)b_; + stmt_vec_info a0 = SLP_TREE_SCALAR_STMTS (a)[0]; + stmt_vec_info b0 = SLP_TREE_SCALAR_STMTS (b)[0]; + if (STMT_VINFO_GROUPED_ACCESS (a0) + && STMT_VINFO_GROUPED_ACCESS (b0) + && DR_GROUP_FIRST_ELEMENT (a0) == DR_GROUP_FIRST_ELEMENT (b0)) + { + /* Same group, order after lanes used. */ + if (SLP_TREE_LANES (a) < SLP_TREE_LANES (b)) + return 1; + else if (SLP_TREE_LANES (a) > SLP_TREE_LANES (b)) + return -1; + else + { + /* Try to order loads using the same lanes together, breaking + the tie with the lane number that first differs. */ + if (!SLP_TREE_LOAD_PERMUTATION (a).exists () + && !SLP_TREE_LOAD_PERMUTATION (b).exists ()) + return 0; + else if (SLP_TREE_LOAD_PERMUTATION (a).exists () + && !SLP_TREE_LOAD_PERMUTATION (b).exists ()) + return 1; + else if (!SLP_TREE_LOAD_PERMUTATION (a).exists () + && SLP_TREE_LOAD_PERMUTATION (b).exists ()) + return -1; + else + { + for (unsigned i = 0; i < SLP_TREE_LANES (a); ++i) + if (SLP_TREE_LOAD_PERMUTATION (a)[i] + != SLP_TREE_LOAD_PERMUTATION (b)[i]) + { + /* In-order lane first, that's what the above case for + no permutation does. */ + if (SLP_TREE_LOAD_PERMUTATION (a)[i] == i) + return -1; + else if (SLP_TREE_LOAD_PERMUTATION (b)[i] == i) + return 1; + else if (SLP_TREE_LOAD_PERMUTATION (a)[i] + < SLP_TREE_LOAD_PERMUTATION (b)[i]) + return -1; + else + return 1; + } + return 0; + } + } + } + else /* Different groups or non-groups. */ + { + /* Order groups as their first element to keep them together. */ + if (STMT_VINFO_GROUPED_ACCESS (a0)) + a0 = DR_GROUP_FIRST_ELEMENT (a0); + if (STMT_VINFO_GROUPED_ACCESS (b0)) + b0 = DR_GROUP_FIRST_ELEMENT (b0); + if (a0 == b0) + return 0; + /* Tie using UID. */ + else if (gimple_uid (STMT_VINFO_STMT (a0)) + < gimple_uid (STMT_VINFO_STMT (b0))) + return -1; + else + { + gcc_assert (gimple_uid (STMT_VINFO_STMT (a0)) + != gimple_uid (STMT_VINFO_STMT (b0))); + return 1; + } + } +} + +/* Process the set of LOADS that are all from the same dataref group. */ + +static void +vect_lower_load_permutations (loop_vec_info loop_vinfo, + scalar_stmts_to_slp_tree_map_t *bst_map, + const array_slice &loads) +{ + /* We at this point want to lower without a fixed VF or vector + size in mind which means we cannot actually compute whether we + need three or more vectors for a load permutation yet. So always + lower. */ + stmt_vec_info first + = DR_GROUP_FIRST_ELEMENT (SLP_TREE_SCALAR_STMTS (loads[0])[0]); + + /* Only a power-of-two number of lanes matches interleaving with N levels. + The non-SLP path also supports DR_GROUP_SIZE == 3. + ??? An even number of lanes could be reduced to 1<= group_lanes / 2) + continue; + + /* First build (and possibly re-use) a load node for the + unpermuted group. Gaps in the middle and on the end are + represented with NULL stmts. */ + vec stmts; + stmts.create (group_lanes); + for (stmt_vec_info s = first; s; s = DR_GROUP_NEXT_ELEMENT (s)) + { + if (s != first) + for (unsigned i = 1; i < DR_GROUP_GAP (s); ++i) + stmts.quick_push (NULL); + stmts.quick_push (s); + } + for (unsigned i = 0; i < DR_GROUP_GAP (first); ++i) + stmts.quick_push (NULL); + poly_uint64 max_nunits = 1; + bool *matches = XALLOCAVEC (bool, group_lanes); + unsigned limit = 1; + unsigned tree_size = 0; + slp_tree l0 = vect_build_slp_tree (loop_vinfo, stmts, + group_lanes, + &max_nunits, matches, &limit, + &tree_size, bst_map); + + /* Build the permute to get the original load permutation order. */ + lane_permutation_t final_perm; + final_perm.create (SLP_TREE_LANES (load)); + for (unsigned i = 0; i < SLP_TREE_LANES (load); ++i) + final_perm.quick_push + (std::make_pair (0, SLP_TREE_LOAD_PERMUTATION (load)[i])); + + while (1) + { + unsigned group_lanes = SLP_TREE_LANES (l0); + if (SLP_TREE_LANES (load) >= group_lanes / 2) + break; + + /* Try to lower by reducing the group to half its size using an + interleaving scheme. For this try to compute whether all + elements needed for this load are in even or odd elements of + an even/odd decomposition with N consecutive elements. + Thus { e, e, o, o, e, e, o, o } woud be an even/odd decomposition + with N == 2. */ + /* ??? Only an even number of lanes can be handed this way, but the + fallback below could work for any number. */ + gcc_assert ((group_lanes & 1) == 0); + unsigned even = (1 << ceil_log2 (group_lanes)) - 1; + unsigned odd = even; + for (auto l : final_perm) + { + even &= ~l.second; + odd &= l.second; + } + + /* Now build an even or odd extraction from the unpermuted load. */ + lane_permutation_t perm; + perm.create (group_lanes / 2); + unsigned level; + if (even + && ((level = 1 << ctz_hwi (even)), true) + && group_lanes % (2 * level) == 0) + { + /* { 0, 1, ... 4, 5 ..., } */ + unsigned level = 1 << ctz_hwi (even); + for (unsigned i = 0; i < group_lanes / 2 / level; ++i) + for (unsigned j = 0; j < level; ++j) + perm.quick_push (std::make_pair (0, 2 * i * level + j)); + } + else if (odd) + { + /* { ..., 2, 3, ... 6, 7 } */ + unsigned level = 1 << ctz_hwi (odd); + gcc_assert (group_lanes % (2 * level) == 0); + for (unsigned i = 0; i < group_lanes / 2 / level; ++i) + for (unsigned j = 0; j < level; ++j) + perm.quick_push (std::make_pair (0, (2 * i + 1) * level + j)); + } + else + { + /* As fallback extract all used lanes and fill to half the + group size by repeating the last element. + ??? This is quite a bad strathegy for re-use - we could + brute force our way to find more optimal filling lanes to + maximize re-use when looking at all loads from the group. */ + auto_bitmap l; + for (auto p : final_perm) + bitmap_set_bit (l, p.second); + unsigned i = 0; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (l, 0, i, bi) + perm.quick_push (std::make_pair (0, i)); + while (perm.length () < group_lanes / 2) + perm.quick_push (perm.last ()); + } + + /* Update final_perm with the intermediate permute. */ + for (unsigned i = 0; i < final_perm.length (); ++i) + { + unsigned l = final_perm[i].second; + unsigned j; + for (j = 0; j < perm.length (); ++j) + if (perm[j].second == l) + { + final_perm[i].second = j; + break; + } + gcc_assert (j < perm.length ()); + } + + /* And create scalar stmts. */ + vec perm_stmts; + perm_stmts.create (perm.length ()); + for (unsigned i = 0; i < perm.length (); ++i) + perm_stmts.quick_push (SLP_TREE_SCALAR_STMTS (l0)[perm[i].second]); + + slp_tree p = vect_create_new_slp_node (1, VEC_PERM_EXPR); + SLP_TREE_CHILDREN (p).quick_push (l0); + SLP_TREE_LANE_PERMUTATION (p) = perm; + SLP_TREE_VECTYPE (p) = SLP_TREE_VECTYPE (load); + SLP_TREE_LANES (p) = perm.length (); + SLP_TREE_REPRESENTATIVE (p) = SLP_TREE_REPRESENTATIVE (load); + /* ??? As we have scalar stmts for this intermediate permute we + could CSE it via bst_map but we do not want to pick up + another SLP node with a load permutation. We instead should + have a "local" CSE map here. */ + SLP_TREE_SCALAR_STMTS (p) = perm_stmts; + + /* We now have a node for group_lanes / 2 lanes. */ + l0 = p; + } + + /* And finally from the ordered reduction node create the + permute to shuffle the lanes into the original load-permutation + order. We replace the original load node with this. */ + SLP_TREE_CODE (load) = VEC_PERM_EXPR; + SLP_TREE_LOAD_PERMUTATION (load).release (); + SLP_TREE_LANE_PERMUTATION (load) = final_perm; + SLP_TREE_CHILDREN (load).create (1); + SLP_TREE_CHILDREN (load).quick_push (l0); + } +} + +/* Transform SLP loads in the SLP graph created by SLP discovery to + group loads from the same group and lower load permutations that + are unlikely to be supported into a series of permutes. + In the degenerate case of having only single-lane SLP instances + this should result in a series of permute nodes emulating an + interleaving scheme. */ + +static void +vect_lower_load_permutations (loop_vec_info loop_vinfo, + scalar_stmts_to_slp_tree_map_t *bst_map) +{ + /* Gather and sort loads across all instances. */ + hash_set visited; + auto_vec loads; + for (auto inst : loop_vinfo->slp_instances) + vect_gather_slp_loads (loads, SLP_INSTANCE_TREE (inst), visited); + if (loads.is_empty ()) + return; + loads.qsort (vllp_cmp); + + /* Now process each dataref group separately. */ + unsigned firsti = 0; + for (unsigned i = 1; i < loads.length (); ++i) + { + slp_tree first = loads[firsti]; + slp_tree next = loads[i]; + stmt_vec_info a0 = SLP_TREE_SCALAR_STMTS (first)[0]; + stmt_vec_info b0 = SLP_TREE_SCALAR_STMTS (next)[0]; + if (STMT_VINFO_GROUPED_ACCESS (a0) + && STMT_VINFO_GROUPED_ACCESS (b0) + && DR_GROUP_FIRST_ELEMENT (a0) == DR_GROUP_FIRST_ELEMENT (b0)) + continue; + /* Just one SLP load of a possible group, leave those alone. */ + if (i == firsti + 1) + { + firsti = i; + continue; + } + /* Now we have multiple SLP loads of the same group from + firsti to i - 1. */ + vect_lower_load_permutations (loop_vinfo, bst_map, + make_array_slice (&loads[firsti], + i - firsti)); + firsti = i; + } + if (firsti < loads.length () - 1) + vect_lower_load_permutations (loop_vinfo, bst_map, + make_array_slice (&loads[firsti], + loads.length () - firsti)); +} + /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP trees of packed scalar stmts if SLP is possible. */ @@ -4085,6 +4407,23 @@ vect_analyze_slp (vec_info *vinfo, unsigned max_tree_size) } } + /* When we end up with load permutations that we cannot possibly handle, + like those requiring three vector inputs, lower them using interleaving + like schemes. */ + if (loop_vec_info loop_vinfo = dyn_cast (vinfo)) + { + vect_lower_load_permutations (loop_vinfo, bst_map); + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_NOTE, vect_location, + "SLP graph after lowering permutations:\n"); + hash_set visited; + FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (vinfo), i, instance) + vect_print_slp_graph (MSG_NOTE, vect_location, + SLP_INSTANCE_TREE (instance), visited); + } + } + hash_set visited_patterns; slp_tree_to_load_perm_map_t perm_cache; slp_compat_nodes_map_t compat_cache;