From: Kyrylo Tkachov <[email protected]>
The BB SLP schedule places the vector code of an operation right after its
vector operands are available. It places constants and externals at the
region start or after the definition of their last scalar operand. So
the computed schedule often places vector code before a branch, although
the scalar code it replaces runs only in one arm. The cost model reads
this schedule. The slp2 dump shows an example (dead scalar code left
out):
x_13 = foo (a_11(D));
y_16 = foo (b_14(D));
_27 = {x_13, y_16, x_13, y_16, x_13, y_16, x_13, y_16};
vect__1.3_28 = _27 + { 3, 5, 7, 9, 11, 13, 15, 17 };
if (c_17(D) != 0)
...
<bb 3>:
vectp.5_29 = out_18(D);
MEM <vector(8) short unsigned int> [(short unsigned int *)vectp.5_29] =
vect__1.3_28;
Later passes can sink such code, as sink2 does here. But the costing
cannot rely on that, and the next patch checks the costs of each block.
Place an operation at the start of the nearest common dominator of the
blocks of its scalar stmts, as possibly trapping operations already are.
Do this only when that block holds one of the scalar stmts, is below where
its operands are available and is in the same loop.
After all nodes are placed, place each constant and external at the start
of the nearest common dominator of the blocks of its uses. Do not place
it in a loop that does not contain its current block, so that loop
invariants stay hoisted. Neither rule moves code into an irreducible
region or in front of a setjmp-like call. Constants and externals also
do not go to the block of the abnormal dispatcher, whose code never runs.
The new place_bb member of the SLP node records the block for the
transform and for the costing. The example becomes:
x_13 = foo (a_11(D));
y_16 = foo (b_14(D));
if (c_17(D) != 0)
...
<bb 3>:
_27 = {x_13, y_16, x_13, y_16, x_13, y_16, x_13, y_16};
vect__1.3_28 = _27 + { 3, 5, 7, 9, 11, 13, 15, 17 };
vectp.5_29 = out_18(D);
MEM <vector(8) short unsigned int> [(short unsigned int *)vectp.5_29] =
vect__1.3_28;
The costing charges all vectors of an external to the block that the
schedule places the external in. But each vector was built after the
definitions of its own operands, possibly in an earlier block. When the
region defines none of them, the vector was built at the region start.
Build each vector in the block that the costing charges, unless the
operands of the vector are available in an outer loop. That block can be
in an irreducible region.
When nodes in different arms use equal invariants, each arm now builds
its own vector of them. Without this patch both vectors were built
before the branch, and later passes merged them.
The costing still adds up the costs of each loop on its own. Vector code
stays in its loop. The only exception is the construction of an
invariant whose users all come after the loop of its operands. This case
needs code without loop-closed SSA.
On SPEC CPU2026 (aarch64, -O3 -mcpu=olympus -flto) the number of
vectorized BB SLP parts is the same in all 27 benchmarks.
Bootstrapped and regression tested together with the next patch on
aarch64-unknown-linux-gnu and x86_64-pc-linux-gnu.
Ok for trunk?
Thanks,
Kyrill
gcc/ChangeLog:
PR tree-optimization/127246
* tree-vectorizer.h (_slp_tree::place_bb): New member.
* tree-vect-slp.cc (_slp_tree::_slp_tree): Initialize place_bb.
(vect_bb_slp_node_bb): New function.
(vect_bb_vectorization_profitable_p): Use it to locate the vector
costs.
(vect_bb_starts_with_setjmp_p): New function.
(vect_create_constant_vectors): For BB vectorization build each
vector in the block that vect_bb_slp_node_bb returns, unless the
operands of the vector are available in an outer loop.
(vect_bb_slp_sink_node): New function.
(vect_schedule_slp_node): Place operations of BB vectorization at
the start of the nearest common dominator of the blocks of their
scalar stmts.
(vect_bb_slp_invariant_user_bbs, vect_bb_abnormal_dispatcher_p)
(vect_bb_slp_place_invariants): New functions.
(vect_schedule_slp): Call vect_bb_slp_place_invariants after
placing for BB vectorization.
gcc/testsuite/ChangeLog:
PR tree-optimization/127246
* gcc.dg/vect/bb-slp-pr127246-3.c: New test.
* gcc.dg/vect/bb-slp-pr127246-4.c: New test.
* gcc.dg/vect/bb-slp-pr127246-5.c: New test.
* gcc.dg/vect/bb-slp-pr127246-6.c: New test.
* gcc.dg/vect/bb-slp-pr127246-7.c: New test.
* gcc.dg/vect/bb-slp-pr127246-8.c: New test.
* gcc.dg/vect/bb-slp-pr127246-10.c: New test.
* gcc.dg/vect/bb-slp-pr127246-11.c: New test.
* gcc.dg/vect/bb-slp-pr127246-12.c: New test.
* gcc.dg/vect/bb-slp-pr127246-14.c: New test.
* g++.dg/vect/slp-pr127246.cc: New test.
* gcc.target/aarch64/pr127246-2.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/testsuite/g++.dg/vect/slp-pr127246.cc | 53 ++++
.../gcc.dg/vect/bb-slp-pr127246-10.c | 7 +
.../gcc.dg/vect/bb-slp-pr127246-11.c | 106 ++++++++
.../gcc.dg/vect/bb-slp-pr127246-12.c | 52 ++++
.../gcc.dg/vect/bb-slp-pr127246-14.c | 72 ++++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-3.c | 48 ++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c | 58 +++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-5.c | 31 +++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-6.c | 53 ++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-7.c | 49 ++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-8.c | 83 ++++++
gcc/testsuite/gcc.target/aarch64/pr127246-2.c | 27 ++
gcc/tree-vect-slp.cc | 239 +++++++++++++++++-
gcc/tree-vectorizer.h | 4 +
14 files changed, 875 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/vect/slp-pr127246.cc
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-10.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-11.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-12.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-14.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-3.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-5.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-6.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-7.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-8.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr127246-2.c
diff --git a/gcc/testsuite/g++.dg/vect/slp-pr127246.cc
b/gcc/testsuite/g++.dg/vect/slp-pr127246.cc
new file mode 100644
index 00000000000..2e510a50eac
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/slp-pr127246.cc
@@ -0,0 +1,53 @@
+// PR tree-optimization/127246
+
+// The quotients feed the vector PHI of x and y on the backedge. The call
+// of bar can throw, so the region ends there, and the vector of the
+// quotients is built in the latch, which belongs to a later region.
+
+__attribute__ ((noipa)) long
+bar (long v)
+{
+ if (v == 37)
+ throw 1;
+ return v;
+}
+
+__attribute__ ((noipa)) long
+f (long *out, long x, long y, int n)
+{
+ long s = 0;
+ for (int i = 0; i < n; i++)
+ {
+ out[2 * i] = x;
+ out[2 * i + 1] = y;
+ long nx = x / 3, ny = y / 5;
+ long t;
+ try
+ {
+ t = bar (nx);
+ }
+ catch (...)
+ {
+ t = 100;
+ }
+ s += t;
+ x = nx;
+ y = ny;
+ }
+ return s;
+}
+
+int
+main ()
+{
+ long out[8];
+ static const long expect[8] = { 1000, 2000, 333, 400, 111, 80, 37, 16 };
+ if (f (out, 1000, 2000, 4) != 333 + 111 + 100 + 12)
+ __builtin_abort ();
+ for (int i = 0; i < 8; i++)
+ if (out[i] != expect[i])
+ __builtin_abort ();
+ return 0;
+}
+
+// { dg-final { scan-tree-dump "placing node \[^\n\r\]* at the start of
bb\[0-9\]+ in loop 1" "slp1" { target { { { aarch64*-*-* && { ! aarch64_sve } }
|| { i?86-*-* || x86_64-*-* } } && lp64 } } } }
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-10.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-10.c
new file mode 100644
index 00000000000..ab61128ab70
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-10.c
@@ -0,0 +1,7 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-additional-options "-fvect-cost-model=dynamic -g -fcompare-debug" } */
+
+/* Debug stmts must not change where the vector code is placed. */
+
+#include "bb-slp-pr127246-5.c"
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-11.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-11.c
new file mode 100644
index 00000000000..fccc342f1e9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-11.c
@@ -0,0 +1,106 @@
+/* PR tree-optimization/127246 */
+/* { dg-additional-options "-mprefer-vector-width=128" { target i?86-*-*
x86_64-*-* } } */
+
+/* The first four stored values are defined before the branch and the
+ others in the conditional block. Both vectors of them are built in the
+ conditional block, where the cost model charges them. */
+
+#include "tree-vect.h"
+
+__attribute__ ((noipa)) int
+foo (int i)
+{
+ return i * 3 + 1;
+}
+
+__attribute__ ((noipa)) void
+f (int *out, int c)
+{
+ int x0 = foo (0), x1 = foo (1), x2 = foo (2), x3 = foo (3);
+ if (c)
+ {
+ int x4 = foo (4), x5 = foo (5), x6 = foo (6), x7 = foo (7);
+ out[0] = x0;
+ out[1] = x1;
+ out[2] = x2;
+ out[3] = x3;
+ out[4] = x4;
+ out[5] = x5;
+ out[6] = x6;
+ out[7] = x7;
+ }
+}
+
+/* In g and h the first four stored values are defined before the loop and
+ the others in it. The vector of the first four is built before the
+ loop, also when the stores are in a conditional block. */
+
+__attribute__ ((noipa)) void
+g (int *out, int n)
+{
+ int x0 = foo (0), x1 = foo (1), x2 = foo (2), x3 = foo (3);
+ for (int i = 0; i < n; i++)
+ {
+ int x4 = foo (4), x5 = foo (5), x6 = foo (6), x7 = foo (7);
+ out[8 * i + 0] = x0;
+ out[8 * i + 1] = x1;
+ out[8 * i + 2] = x2;
+ out[8 * i + 3] = x3;
+ out[8 * i + 4] = x4;
+ out[8 * i + 5] = x5;
+ out[8 * i + 6] = x6;
+ out[8 * i + 7] = x7;
+ }
+}
+
+__attribute__ ((noipa)) void
+h (int *out, int *c, int n)
+{
+ int x0 = foo (0), x1 = foo (1), x2 = foo (2), x3 = foo (3);
+ for (int i = 0; i < n; i++)
+ {
+ int x4 = foo (4), x5 = foo (5), x6 = foo (6), x7 = foo (7);
+ if (c[i])
+ {
+ out[8 * i + 0] = x0;
+ out[8 * i + 1] = x1;
+ out[8 * i + 2] = x2;
+ out[8 * i + 3] = x3;
+ out[8 * i + 4] = x4;
+ out[8 * i + 5] = x5;
+ out[8 * i + 6] = x6;
+ out[8 * i + 7] = x7;
+ }
+ }
+}
+
+int
+main ()
+{
+ int out[16] = {};
+ int c[2] = { 1, 0 };
+
+ check_vect ();
+
+ f (out, 0);
+ for (int i = 0; i < 8; i++)
+ if (out[i] != 0)
+ abort ();
+ f (out, 1);
+ for (int i = 0; i < 8; i++)
+ if (out[i] != i * 3 + 1)
+ abort ();
+ g (out, 2);
+ for (int i = 0; i < 16; i++)
+ if (out[i] != (i % 8) * 3 + 1)
+ abort ();
+ __builtin_memset (out, 0, sizeof (out));
+ h (out, c, 2);
+ for (int i = 0; i < 16; i++)
+ if (out[i] != (i < 8 ? i * 3 + 1 : 0))
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "foo \\(7\\);\n *_\[0-9\]+ = \{x0_" "slp2" {
target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
+/* { dg-final { scan-tree-dump-times "foo \\(3\\);\n *_\[0-9\]+ = \{x0_" 2
"slp1" { target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } }
} */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-12.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-12.c
new file mode 100644
index 00000000000..d13e1643a61
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-12.c
@@ -0,0 +1,52 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+
+/* The stores are in an irreducible region. The additions and the
+ construction of x and y stay in front of it. */
+
+extern void bar (unsigned short *);
+
+void
+f (unsigned short *out, unsigned short x, unsigned short y, int c, int n)
+{
+ int i = 0;
+ if (c)
+ goto second;
+first:
+ out[0] = x + 3;
+ out[1] = y + 5;
+ out[2] = x + 7;
+ out[3] = y + 9;
+ out[4] = x + 11;
+ out[5] = y + 13;
+ out[6] = x + 15;
+ out[7] = y + 17;
+second:
+ bar (out);
+ if (++i < n)
+ goto first;
+}
+
+void
+g (unsigned short *out, unsigned short x, unsigned short y, int c, int n)
+{
+ int i = 0;
+ if (c)
+ goto second;
+first:
+ out[0] = x;
+ out[1] = y;
+ out[2] = x;
+ out[3] = y;
+ out[4] = x;
+ out[5] = y;
+ out[6] = x;
+ out[7] = y;
+second:
+ bar (out);
+ if (++i < n)
+ goto first;
+}
+
+/* { dg-final { scan-tree-dump-times "optimized: basic block part vectorized"
2 "slp2" { target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } }
} } */
+/* { dg-final { scan-tree-dump-not "placing node\[^\n\r\]* at the start"
"slp2" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-14.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-14.c
new file mode 100644
index 00000000000..78c206abfc5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-14.c
@@ -0,0 +1,72 @@
+/* PR tree-optimization/127246 */
+/* { dg-require-effective-target indirect_jumps } */
+
+/* The quotients are used in the blocks of two __builtin_setjmp receivers.
+ The nearest common dominator of those blocks is the block of the
+ abnormal dispatcher, whose code never runs. The vector of the quotients
+ must stay after the divisions. */
+
+#include "tree-vect.h"
+
+void *buf1[5], *buf2[5];
+int which;
+
+__attribute__ ((noipa)) void
+bar (void)
+{
+ if (which == 1)
+ __builtin_longjmp (buf1, 1);
+ if (which == 2)
+ __builtin_longjmp (buf2, 1);
+}
+
+__attribute__ ((noipa)) void
+f (unsigned *restrict p, unsigned *restrict r, unsigned *restrict q)
+{
+ unsigned a0 = q[0] * 100 / q[4];
+ unsigned a1 = q[1] * 100 / q[5];
+ unsigned a2 = q[2] * 100 / q[6];
+ unsigned a3 = q[3] * 100 / q[7];
+ if (__builtin_setjmp (buf1))
+ {
+ p[0] = a0 * q[8];
+ p[1] = a1 * q[9];
+ p[2] = a2 * q[10];
+ p[3] = a3 * q[11];
+ return;
+ }
+ if (__builtin_setjmp (buf2))
+ {
+ r[0] = a0 + q[12];
+ r[1] = a1 + q[13];
+ r[2] = a2 + q[14];
+ r[3] = a3 + q[15];
+ return;
+ }
+ bar ();
+}
+
+int
+main ()
+{
+ unsigned q[16];
+
+ check_vect ();
+
+ for (int i = 0; i < 16; i++)
+ q[i] = i + 1;
+ for (which = 1; which <= 2; which++)
+ {
+ unsigned p[4] = { 0 }, r[4] = { 0 };
+ f (p, r, q);
+ for (int i = 0; i < 4; i++)
+ {
+ unsigned a = q[i] * 100 / q[i + 4];
+ if (which == 1 ? p[i] != a * q[i + 8] : r[i] != a + q[i + 12])
+ abort ();
+ }
+ }
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "optimized: basic block part vectorized" "slp2"
{ target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-3.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-3.c
new file mode 100644
index 00000000000..ae2827d8fe9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-3.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+/* { dg-additional-options "-mtune=generic" { target aarch64*-*-* } } */
+
+/* The additions only run in the unlikely arm, so their vector code and the
+ construction of x and y are placed there. */
+
+void
+f (unsigned short *out, unsigned short x, unsigned short y, int c)
+{
+ if (__builtin_expect (c, 0))
+ {
+ out[0] = x + 3;
+ out[1] = y + 5;
+ out[2] = x + 7;
+ out[3] = y + 9;
+ out[4] = x + 11;
+ out[5] = y + 13;
+ out[6] = x + 15;
+ out[7] = y + 17;
+ }
+}
+
+/* The vector load of q is also used before the branch. The addition only
+ runs in the arm, so its vector code is placed there. */
+
+void
+g (int *restrict p, int *restrict q, int *restrict r)
+{
+ int a = q[0], b = q[1], d = q[2], e = q[3];
+ r[0] = a;
+ r[1] = b;
+ r[2] = d;
+ r[3] = e;
+ if (a > 0)
+ {
+ p[0] = a + 1;
+ p[1] = b + 2;
+ p[2] = d + 3;
+ p[3] = e + 4;
+ }
+}
+
+/* { dg-final { scan-tree-dump "optimized: basic block part vectorized" "slp2"
{ target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
+/* { dg-final { scan-tree-dump "placing node \[^\n\r\]* in loop 0" "slp2" {
target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
+/* { dg-final { scan-tree-dump {<bb 2> \[[^\n\r]*\]:\n *if \(} "slp2" { target
{ { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
+/* { dg-final { scan-tree-dump {:\n *vect_[^\n\r]* = vect_[^\n\r]* \+ \{ 1, 2,
3, 4 \};} "slp2" { target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } &&
lp64 } } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c
new file mode 100644
index 00000000000..b0774f76701
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c
@@ -0,0 +1,58 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+
+/* The quotients feed vector stores, and in f, f1 and f2 also a reduction.
+ Without a vector division the store instances turn the quotients into
+ an external, and the reduction instance keeps that external as its
+ root. In f3 the store instances of both arms share the external. The
+ vector of the external must dominate all of its users, also when they
+ are in different blocks. */
+
+void
+f (long *restrict p, long *restrict q, long *s)
+{
+ long a = q[0] / q[2], b = q[1] / q[3];
+ p[0] = a;
+ p[1] = b;
+ *s = a + b;
+}
+
+void
+f1 (long *restrict p, long *restrict q, long *s, int c)
+{
+ long a = q[0] / q[2], b = q[1] / q[3];
+ if (c)
+ {
+ p[0] = a;
+ p[1] = b;
+ }
+ *s = a + b;
+}
+
+void
+f2 (long *restrict p, long *restrict q, long *s, int c)
+{
+ long a = q[0] / q[2], b = q[1] / q[3];
+ if (c)
+ *s = a + b;
+ p[0] = a;
+ p[1] = b;
+}
+
+void
+f3 (long *restrict p, long *restrict q, long *restrict r, int c)
+{
+ long a = q[0] / q[2], b = q[1] / q[3];
+ if (c)
+ {
+ p[0] = a;
+ p[1] = b;
+ }
+ else
+ {
+ r[0] = a;
+ r[1] = b;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "from scalars instead" 4 "slp2" { target
{ { { aarch64*-*-* && { ! aarch64_sve } } || { i?86-*-* || x86_64-*-* } } &&
lp64 } } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-5.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-5.c
new file mode 100644
index 00000000000..46c9a428805
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-5.c
@@ -0,0 +1,31 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+
+/* The additions only run in the conditional block, so their vector code
+ and the construction of x and y go there and not after the calls in the
+ loop header. */
+
+extern unsigned short foo (unsigned short);
+
+void
+f (unsigned short *restrict out, unsigned short *a, int *c, int n)
+{
+ for (int i = 0; i < n; i++)
+ {
+ unsigned short x = foo (a[i]), y = foo (a[i + 1]);
+ if (c[i] == 42)
+ {
+ out[8 * i + 0] = x + 3;
+ out[8 * i + 1] = y + 5;
+ out[8 * i + 2] = x + 7;
+ out[8 * i + 3] = y + 9;
+ out[8 * i + 4] = x + 11;
+ out[8 * i + 5] = y + 13;
+ out[8 * i + 6] = x + 15;
+ out[8 * i + 7] = y + 17;
+ }
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "placing node \[^\n\r\]* in loop 1" 2
"slp1" { target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } }
} */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-6.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-6.c
new file mode 100644
index 00000000000..837ca142270
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-6.c
@@ -0,0 +1,53 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+
+/* x and y are defined before the loop and stored only in its conditional
+ block. Their vector goes to the end of the code before the loop, not
+ into the loop. */
+
+extern unsigned short foo (unsigned short);
+
+void
+f (unsigned short *restrict out, unsigned short a, unsigned short b,
+ int *c, int n)
+{
+ unsigned short x = foo (a), y = foo (b);
+ for (int i = 0; i < n; i++)
+ if (c[i] == 42)
+ {
+ out[8 * i + 0] = x;
+ out[8 * i + 1] = y;
+ out[8 * i + 2] = x;
+ out[8 * i + 3] = y;
+ out[8 * i + 4] = x;
+ out[8 * i + 5] = y;
+ out[8 * i + 6] = x;
+ out[8 * i + 7] = y;
+ }
+}
+
+/* The additions use only x and y, so their vector code also stays before
+ the loop. */
+
+void
+g (unsigned short *restrict out, unsigned short a, unsigned short b,
+ int *c, int n)
+{
+ unsigned short x = foo (a), y = foo (b);
+ for (int i = 0; i < n; i++)
+ if (c[i] == 42)
+ {
+ out[8 * i + 0] = x + 3;
+ out[8 * i + 1] = y + 5;
+ out[8 * i + 2] = x + 7;
+ out[8 * i + 3] = y + 9;
+ out[8 * i + 4] = x + 11;
+ out[8 * i + 5] = y + 13;
+ out[8 * i + 6] = x + 15;
+ out[8 * i + 7] = y + 17;
+ }
+}
+
+/* { dg-final { scan-tree-dump "placing node \[^\n\r\]* in loop 0" "slp1" {
target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
+/* { dg-final { scan-tree-dump-not "placing node \[^\n\r\]* in loop \[1-9\]"
"slp1" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-7.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-7.c
new file mode 100644
index 00000000000..84c83b985a7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-7.c
@@ -0,0 +1,49 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+
+/* The block of the stores starts with a returns-twice call, and the call
+ of bar gives the block an abnormal predecessor. Nothing may be placed
+ in front of the returns-twice call, neither the additions nor the
+ construction of x and y. */
+
+extern int rt (void) __attribute__ ((returns_twice, leaf));
+extern void bar (void);
+
+void
+f (unsigned short *out, unsigned short x, unsigned short y, int c)
+{
+ bar ();
+ if (c)
+ {
+ rt ();
+ out[0] = x + 3;
+ out[1] = y + 5;
+ out[2] = x + 7;
+ out[3] = y + 9;
+ out[4] = x + 11;
+ out[5] = y + 13;
+ out[6] = x + 15;
+ out[7] = y + 17;
+ }
+}
+
+void
+g (unsigned short *out, unsigned short x, unsigned short y, int c)
+{
+ bar ();
+ if (c)
+ {
+ rt ();
+ out[0] = x;
+ out[1] = y;
+ out[2] = x;
+ out[3] = y;
+ out[4] = x;
+ out[5] = y;
+ out[6] = x;
+ out[7] = y;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "optimized: basic block part vectorized"
2 "slp2" { target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } }
} } */
+/* { dg-final { scan-tree-dump-not "placing node\[^\n\r\]* at the start"
"slp2" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-8.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-8.c
new file mode 100644
index 00000000000..e31ad3375d3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-8.c
@@ -0,0 +1,83 @@
+/* PR tree-optimization/127246 */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+
+/* The vector code of the additions is placed in the conditional block.
+ The first lane is also used after it. */
+
+#include "tree-vect.h"
+
+__attribute__ ((noipa)) unsigned short
+f (unsigned short *out, unsigned short x, unsigned short y, int c)
+{
+ unsigned short r = 0;
+ if (c)
+ {
+ unsigned short a = x + 3;
+ out[0] = a;
+ out[1] = y + 5;
+ out[2] = x + 7;
+ out[3] = y + 9;
+ out[4] = x + 11;
+ out[5] = y + 13;
+ out[6] = x + 15;
+ out[7] = y + 17;
+ r = a;
+ }
+ return r;
+}
+
+/* Each arm builds its own vector of x and y. */
+
+__attribute__ ((noipa)) void
+g (unsigned short *out, unsigned short x, unsigned short y, int c)
+{
+ if (c)
+ {
+ out[0] = x + 3;
+ out[1] = y + 5;
+ out[2] = x + 7;
+ out[3] = y + 9;
+ out[4] = x + 11;
+ out[5] = y + 13;
+ out[6] = x + 15;
+ out[7] = y + 17;
+ }
+ else
+ {
+ out[0] = x * 3;
+ out[1] = y * 5;
+ out[2] = x * 7;
+ out[3] = y * 9;
+ out[4] = x * 11;
+ out[5] = y * 13;
+ out[6] = x * 15;
+ out[7] = y * 17;
+ }
+}
+
+int
+main ()
+{
+ unsigned short out[8];
+ static const unsigned short add[8] = { 3, 5, 7, 9, 11, 13, 15, 17 };
+
+ check_vect ();
+
+ for (int c = 0; c < 2; c++)
+ {
+ __builtin_memset (out, 0, sizeof (out));
+ unsigned short r = f (out, 10, 20, c);
+ if (r != (c ? 13 : 0))
+ abort ();
+ for (int i = 0; i < 8; i++)
+ if (out[i] != (c ? (i & 1 ? 20 : 10) + add[i] : 0))
+ abort ();
+
+ g (out, 10, 20, c);
+ for (int i = 0; i < 8; i++)
+ if (out[i] != (c ? (i & 1 ? 20 : 10) + add[i]
+ : (unsigned short) ((i & 1 ? 20 : 10) * add[i])))
+ abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/pr127246-2.c
b/gcc/testsuite/gcc.target/aarch64/pr127246-2.c
new file mode 100644
index 00000000000..953cd0c1551
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr127246-2.c
@@ -0,0 +1,27 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=generic -fdump-tree-slp2-details" } */
+
+#pragma GCC target "+nosve"
+
+/* The vector constants of each case are placed in that case, where the
+ vector stores they feed run. */
+
+struct s { int a, b, c, d; };
+
+void
+f (struct s *p, int c)
+{
+ switch (c)
+ {
+ case 0: p->a = 1; p->b = 2; p->c = 3; p->d = 4; break;
+ case 1: p->a = 5; p->b = 6; p->c = 7; p->d = 8; break;
+ case 2: p->a = 9; p->b = 10; p->c = 11; p->d = 12; break;
+ case 3: p->a = 13; p->b = 14; p->c = 15; p->d = 16; break;
+ case 4: p->a = 17; p->b = 18; p->c = 19; p->d = 20; break;
+ default: break;
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "optimized: basic block part vectorized"
5 "slp2" } } */
+/* { dg-final { scan-tree-dump-times "placing node \[^\n\r\]* at the start of
bb\[0-9\]+ in loop 0" 5 "slp2" } } */
diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
index 142037ed008..5b00c5b472c 100644
--- a/gcc/tree-vect-slp.cc
+++ b/gcc/tree-vect-slp.cc
@@ -135,6 +135,7 @@ _slp_tree::_slp_tree ()
SLP_TREE_TYPE (this) = undef_vec_info_type;
this->data = NULL;
this->si = NULL;
+ this->place_bb = NULL;
}
/* Tear down a SLP node. */
@@ -9859,6 +9860,18 @@ vect_bb_slp_scalar_cost (bb_vec_info vinfo,
}
+/* Return the block of BB_VINFO that the computed schedule places the vector
+ code of the SLP node NODE in. A vector of an external node whose
+ operands are available in an outer loop is built in that loop instead. */
+
+static basic_block
+vect_bb_slp_node_bb (bb_vec_info bb_vinfo, slp_tree node)
+{
+ if (node->place_bb)
+ return node->place_bb;
+ return node->si ? gimple_bb (node->si) : bb_vinfo->bbs[0];
+}
+
/* Comparator for the loop-index sorted cost vectors. */
static int
@@ -9951,11 +9964,8 @@ vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo,
FOR_EACH_VEC_ELT (vector_costs, i, cost)
{
/* Use SLP node placement according to the computed schedule. */
- if (cost->node && cost->node->si)
- l = gimple_bb (cost->node->si)->loop_father->num;
- /* For schedules at region boundary use the region entry loop. */
- else if (cost->node)
- l = bb_vinfo->bbs[0]->loop_father->num;
+ if (cost->node)
+ l = vect_bb_slp_node_bb (bb_vinfo, cost->node)->loop_father->num;
/* SLP instance root stmts do not have an associated SLP node. */
else if (cost->stmt_info)
l = gimple_bb (cost->stmt_info->stmt)->loop_father->num;
@@ -10805,6 +10815,21 @@ vect_slp_if_converted_bb (basic_block bb, loop_p
orig_loop)
return vect_slp_bbs (bbs, orig_loop);
}
+/* Return true if the first stmt of BB after its labels and debug stmts is a
+ setjmp-like call, in front of which nothing may be inserted. */
+
+static bool
+vect_bb_starts_with_setjmp_p (basic_block bb)
+{
+ gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);
+ if (gsi_end_p (gsi))
+ return false;
+ gcall *call = dyn_cast <gcall *> (gsi_stmt (gsi));
+ return (call
+ && ((gimple_call_flags (call) & ECF_RETURNS_TWICE)
+ || gimple_call_builtin_p (call, BUILT_IN_SETJMP_RECEIVER)));
+}
+
/* Main entry for the BB vectorizer. Analyze and transform BB, returns
true if anything in the basic-block was vectorized. */
@@ -11201,7 +11226,28 @@ vect_create_constant_vectors (vec_info *vinfo,
slp_tree op_node)
}
if (!gimple_seq_empty_p (ctor_seq))
{
- if (insert_after)
+ /* For BB vectorization build the vector where the schedule
+ placed OP_NODE, unless the operands of this vector are
+ available in an outer loop. */
+ basic_block place_bb = op_node->place_bb;
+ if (bb_vec_info bb_vinfo = dyn_cast <bb_vec_info> (vinfo))
+ {
+ basic_block avail_bb = (insert_after
+ ? gimple_bb (insert_after->stmt)
+ : bb_vinfo->bbs[0]);
+ basic_block bb = vect_bb_slp_node_bb (bb_vinfo, op_node);
+ if (flow_loop_nested_p (avail_bb->loop_father,
+ bb->loop_father))
+ place_bb = NULL;
+ else if (!place_bb && avail_bb != bb)
+ insert_after = vinfo->lookup_stmt (op_node->si);
+ }
+ if (place_bb)
+ {
+ gimple_stmt_iterator gsi = gsi_after_labels (place_bb);
+ gsi_insert_seq_before (&gsi, ctor_seq, GSI_SAME_STMT);
+ }
+ else if (insert_after)
{
gimple_stmt_iterator gsi;
if (gimple_code (insert_after->stmt) == GIMPLE_PHI)
@@ -12135,6 +12181,55 @@ vectorizable_slp_permutation (vec_info *vinfo,
gimple_stmt_iterator *gsi,
return true;
}
+/* For pre-scheduling the SLP node NODE of BB_VINFO, whose vector operands
+ are available after *LAST_STMT (NULL for the region start), decide
+ whether to place its vector code at the start of the nearest common
+ dominator of the blocks of its scalar stmts. That block is where the
+ scalar code it replaces runs. Do so if the block holds one of the scalar
+ stmts, is below the block of *LAST_STMT in the same loop, is not in an
+ irreducible region and does not start with a setjmp-like call. Then
+ record the block in NODE->place_bb, set *LAST_STMT to the first scalar
+ stmt in it and return true. Otherwise return false. */
+
+static bool
+vect_bb_slp_sink_node (bb_vec_info bb_vinfo, slp_tree node,
+ gimple **last_stmt)
+{
+ basic_block lbb = *last_stmt ? gimple_bb (*last_stmt) : bb_vinfo->bbs[0];
+ basic_block bb = NULL;
+ for (stmt_vec_info lane : SLP_TREE_SCALAR_STMTS (node))
+ if (lane)
+ bb = nearest_common_dominator (CDI_DOMINATORS, bb,
+ gimple_bb (vect_orig_stmt (lane)->stmt));
+ if (!bb
+ || bb == lbb
+ || bb->loop_father != lbb->loop_father
+ || (bb->flags & BB_IRREDUCIBLE_LOOP)
+ || !dominated_by_p (CDI_DOMINATORS, bb, lbb)
+ || vect_bb_starts_with_setjmp_p (bb))
+ return false;
+
+ gimple *first = NULL;
+ for (stmt_vec_info lane : SLP_TREE_SCALAR_STMTS (node))
+ if (lane)
+ {
+ gimple *stmt = vect_orig_stmt (lane)->stmt;
+ if (gimple_bb (stmt) == bb
+ && (!first || gimple_uid (stmt) < gimple_uid (first)))
+ first = stmt;
+ }
+ if (!first)
+ return false;
+
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "placing node %p at the start of bb%d in loop %d\n",
+ (void *) node, bb->index, bb->loop_father->num);
+ node->place_bb = bb;
+ *last_stmt = first;
+ return true;
+}
+
/* Vectorize SLP NODE. Only compute the vector insertion places when
PLACE_ONLY is true. When placing, return false if there is no possible
schedule. */
@@ -12402,6 +12497,18 @@ vect_schedule_slp_node (vec_info *vinfo,
si = gsi_after_labels (gimple_bb (stmt_info->stmt));
last_stmt = gsi_stmt (si);
}
+ /* Place other operations of BB vectorization where the scalar code
+ they replace runs when that is below where their operands are
+ available. The transform uses the block pre-scheduling chose. */
+ else if (is_a <bb_vec_info> (vinfo)
+ && !SLP_TREE_PERMUTE_P (node)
+ && (place_only
+ ? vect_bb_slp_sink_node (as_a <bb_vec_info> (vinfo), node,
+ &last_stmt)
+ : (node->place_bb
+ && (!last_stmt
+ || gimple_bb (last_stmt) != node->place_bb))))
+ si = gsi_after_labels (node->place_bb);
/* When there is no in-region child def to guide placement, insert
at region boundary. */
else if (!last_stmt)
@@ -12907,6 +13014,120 @@ vect_schedule_scc (vec_info *vinfo, slp_tree node,
slp_instance instance,
return true;
}
+/* Record in USER_BBS, for each constant and external child in the SLP graph
+ of BB_VINFO below NODE, the nearest common dominator of the blocks its
+ users use it in, and add the child to INVARIANTS the first time. VISITED
+ holds the nodes already walked. */
+
+static void
+vect_bb_slp_invariant_user_bbs (bb_vec_info bb_vinfo, slp_tree node,
+ hash_map<slp_tree, basic_block> &user_bbs,
+ vec<slp_tree> &invariants,
+ hash_set<slp_tree> &visited)
+{
+ if (visited.add (node))
+ return;
+ /* A PHI uses its arguments at the end of the sources of the incoming
+ edges. */
+ gphi *phi = NULL;
+ if (!SLP_TREE_PERMUTE_P (node)
+ && (SLP_TREE_TYPE (node) == cycle_phi_info_type
+ || SLP_TREE_TYPE (node) == induc_vec_info_type
+ || SLP_TREE_TYPE (node) == phi_info_type))
+ phi = as_a <gphi *> (SLP_TREE_SCALAR_STMTS (node)[0]->stmt);
+ basic_block bb = vect_bb_slp_node_bb (bb_vinfo, node);
+ unsigned i;
+ slp_tree child;
+ FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
+ if (child && SLP_TREE_DEF_TYPE (child) == vect_internal_def)
+ vect_bb_slp_invariant_user_bbs (bb_vinfo, child, user_bbs, invariants,
+ visited);
+ else if (child)
+ {
+ bool existed;
+ basic_block &user_bb = user_bbs.get_or_insert (child, &existed);
+ if (!existed)
+ invariants.safe_push (child);
+ user_bb = nearest_common_dominator (CDI_DOMINATORS, user_bb,
+ phi
+ ? gimple_phi_arg_edge (phi, i)->src
+ : bb);
+ }
+}
+
+/* Return true if BB is the block of the abnormal dispatcher, whose code
+ never runs. */
+
+static bool
+vect_bb_abnormal_dispatcher_p (basic_block bb)
+{
+ gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);
+ return (!gsi_end_p (gsi)
+ && gimple_call_internal_p (gsi_stmt (gsi), IFN_ABNORMAL_DISPATCHER));
+}
+
+/* Place the vector code of the constants and externals in the SLP graphs of
+ INSTANCES of BB_VINFO at the start of the nearest common dominator of the
+ blocks their users use them in, when that is below the block the
+ computed schedule places them in. Do not move them into loops that do
+ not contain that block, into irreducible regions or into the abnormal
+ dispatcher. For PHI users the block can be outside of the region. */
+
+static void
+vect_bb_slp_place_invariants (bb_vec_info bb_vinfo,
+ vec<slp_instance> &instances)
+{
+ hash_map<slp_tree, basic_block> user_bbs;
+ auto_vec<slp_tree> invariants;
+ hash_set<slp_tree> visited;
+ for (slp_instance instance : instances)
+ {
+ slp_tree node = SLP_INSTANCE_TREE (instance);
+ if (SLP_TREE_DEF_TYPE (node) == vect_internal_def)
+ vect_bb_slp_invariant_user_bbs (bb_vinfo, node, user_bbs, invariants,
+ visited);
+ /* An instance tree that analysis turned into an external is used by
+ the root stmt. */
+ else if (!SLP_INSTANCE_ROOT_STMTS (instance).is_empty ())
+ {
+ bool existed;
+ basic_block &user_bb = user_bbs.get_or_insert (node, &existed);
+ if (!existed)
+ invariants.safe_push (node);
+ user_bb
+ = nearest_common_dominator
+ (CDI_DOMINATORS, user_bb,
+ gimple_bb (SLP_INSTANCE_ROOT_STMTS (instance)[0]->stmt));
+ }
+ }
+
+ for (slp_tree node : invariants)
+ {
+ /* Leave scalar operands and existing vectors alone. */
+ if (!SLP_TREE_VECTYPE (node) || SLP_TREE_SCALAR_OPS (node).is_empty ())
+ continue;
+ basic_block def_bb = vect_bb_slp_node_bb (bb_vinfo, node);
+ class loop *def_loop = def_bb->loop_father;
+ basic_block bb = *user_bbs.get (node);
+ while ((bb->loop_father != def_loop
+ && !flow_loop_nested_p (bb->loop_father, def_loop))
+ || (bb->flags & BB_IRREDUCIBLE_LOOP))
+ bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+ /* The uses of a load are not checked against the placement of its
+ operands, so require BB to be below DEF_BB. */
+ if (bb == def_bb
+ || !dominated_by_p (CDI_DOMINATORS, bb, def_bb)
+ || vect_bb_starts_with_setjmp_p (bb)
+ || vect_bb_abnormal_dispatcher_p (bb))
+ continue;
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "placing node %p at the start of bb%d in loop %d\n",
+ (void *) node, bb->index, bb->loop_father->num);
+ node->place_bb = bb;
+ }
+}
+
/* Generate vector code for SLP_INSTANCES in the loop/basic block. Perform
vector stmt placement only when PLACE_ONLY is true, removing SLP graph
entries that cannot be scheduled. If placing, return false if a schedule
@@ -12981,7 +13202,11 @@ vect_schedule_slp (vec_info *vinfo, vec<slp_instance>
&slp_instances,
}
if (place_only)
- return !slp_instances.is_empty ();
+ {
+ if (bb_vec_info bb_vinfo = dyn_cast <bb_vec_info> (vinfo))
+ vect_bb_slp_place_invariants (bb_vinfo, slp_instances);
+ return !slp_instances.is_empty ();
+ }
FOR_EACH_VEC_ELT (slp_instances, i, instance)
{
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index abd9edc2743..ef04b8057aa 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -377,6 +377,10 @@ struct _slp_tree {
/* Insertion place for verification purposes. Only set for
BB vectorization. NULL denotes region entry. */
gimple *si;
+ /* For BB vectorization the block at whose start the vector code is
+ placed instead of the place SI describes, or NULL. For an internal
+ node SI is then the first scalar stmt in that block. */
+ basic_block place_bb;
/* Reference count in the SLP graph. */
unsigned int refcnt;
--
2.50.1 (Apple Git-155)
