From: Kyrylo Tkachov <[email protected]>
vect_bb_vectorization_profitable_p compares the scalar and vector costs of
each loop separately, but inside a loop it assumes that all code runs on
every iteration. Code in mutually exclusive branches does not.
In the threaded interpreters of the PR, BB SLP keeps two loop-carried
pointers in one vector so that every handler can store both with one
vector store. That costs a vector construction in the latch and two lane
extracts in the dispatch on every iteration:
latch:
_229 = {_228, _227};
dispatch:
# vect_next_instr_234 = PHI <_229(4), vect_next_instr_231(2)>
_237 = BIT_FIELD_REF <vect_next_instr_234, 64, 64>;
_235 = BIT_FIELD_REF <vect_next_instr_234, 64, 0>;
goto gotovar.0_66;
handler:
MEM <vector(2) long unsigned int> [frame] = vect_next_instr_234;
Each handler runs a fraction of the iterations, yet the cost model credits
all of their stores against the per-iteration overhead. For CPython 3.14
this puts GPR<->SIMD moves on the critical path of every bytecode dispatch.
Keep costing each loop with one target cost object per side, so that target
heuristics such as the aarch64 STP check still see all the code of the
loop, and scale the resulting scalar and vector costs by the mean execution
frequency of the code they describe, relative to the highest frequency of
the code of the loop. The mean weights each cost the target records by the
frequency of the block of its code. For costs that the target adds up the
result is the frequency weighted sum. When all the costed code of a loop
has one frequency, including when none of it executes, its costs stay as
they are, so the decision does not change when that holds for every loop.
For the dispatch loop of CPython's evaluator the vector and scalar costs
are 74 and 92 before scaling and 28 and 2.4 after it.
The SLP schedule places vector code as early as its operands allow, and
sinking later moves it down to the scalar code it replaces, so charge it
there when that is in the same loop. Charge constants and externals at the
nearest common dominator of the vector code of their users in the same way.
Costs are not scaled when optimizing for size.
On CPython 3.14.5 built with PGO and LTO on aarch64 (Neoverse V2), on top
of the previous patch, this reduces the geometric mean run time of 17
pyperformance benchmarks by a further 32.7%, the same as disabling SLP.
_PyEval_EvalFrameDefault has 356 indirect dispatch branches instead of 3
and no moves between general and vector registers.
Bootstrapped and regression tested on aarch64-unknown-linux-gnu and
x86_64-pc-linux-gnu.
Ok for trunk?
Thanks,
Kyrill
Cc: Richard Biener <[email protected]>
Cc: Tamar Christina <[email protected]>
Cc: Robin Dapp <[email protected]>
gcc/ChangeLog:
PR tree-optimization/127246
* tree-vect-slp.cc (add_slp_costs): Return the sum of the recorded
costs.
(vect_bb_slp_node_block, vect_bb_slp_invariant_user_bbs): New
functions.
(li_cost): New struct.
(li_cost_vec_cmp): Adjust.
(vect_bb_vectorization_profitable_p): Scale the costs of each loop
by the mean frequency of the code they describe. Charge vector code
at the block of the scalar code it replaces and invariants at the
block of their users.
gcc/testsuite/ChangeLog:
PR tree-optimization/127246
* gcc.dg/vect/bb-slp-pr127246-1.c: New test.
* gcc.dg/vect/bb-slp-pr127246-2.c: New test.
* gcc.dg/vect/bb-slp-pr127246-3.c: New test.
* gcc.dg/vect/bb-slp-pr127246-4.c: New test.
* gcc.target/aarch64/pr127246.c: New test.
* gcc.target/aarch64/pr127246-2.c: New test.
* gcc.target/aarch64/pr127246-3.c: New test.
* gcc.target/aarch64/pr127246-4.c: New test.
* gcc.target/aarch64/pr127246-5.c: New test.
* gcc.target/aarch64/pr127246-6.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-1.c | 53 ++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-2.c | 48 ++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-3.c | 26 ++
gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c | 18 ++
gcc/testsuite/gcc.target/aarch64/pr127246-2.c | 26 ++
gcc/testsuite/gcc.target/aarch64/pr127246-3.c | 27 ++
gcc/testsuite/gcc.target/aarch64/pr127246-4.c | 24 ++
gcc/testsuite/gcc.target/aarch64/pr127246-5.c | 23 ++
gcc/testsuite/gcc.target/aarch64/pr127246-6.c | 49 ++++
gcc/testsuite/gcc.target/aarch64/pr127246.c | 16 ++
gcc/tree-vect-slp.cc | 269 ++++++++++++------
11 files changed, 485 insertions(+), 94 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-2.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.target/aarch64/pr127246-2.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr127246-3.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr127246-4.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr127246-5.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr127246-6.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/pr127246.c
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-1.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-1.c
new file mode 100644
index 00000000000..7ef92b02fba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-1.c
@@ -0,0 +1,53 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-require-effective-target label_values } */
+/* { dg-require-effective-target indirect_jumps } */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+
+/* Each handler of the threaded interpreter runs once for every twenty
+ dispatches. Keeping next_instr and stack_pointer in one vector, so that a
+ handler can store both with one vector store, costs a vector construction
+ and two lane extracts on every dispatch. */
+
+struct frame
+{
+ const unsigned short *instr_ptr;
+ long *stackpointer;
+};
+
+/* Opcode number and stack delta. */
+#define OPS(X) \
+ X (0, -1) X (1, 0) X (2, -1) X (3, 0) X (4, -1) X (5, 0) \
+ X (6, -1) X (7, 0) X (8, -1) X (9, 0) X (10, -1) X (11, 0) \
+ X (12, -1) X (13, 0) X (14, -1) X (15, 0) X (16, -1) X (17, 0) \
+ X (18, -1) X (19, 0)
+
+extern long op (long);
+
+#define DISPATCH() goto *targets[*next_instr & 0xff]
+
+#define HANDLER(N, SD) \
+ L_##N: \
+ frame->instr_ptr = next_instr; \
+ next_instr += 1; \
+ frame->stackpointer = stack_pointer; \
+ stack_pointer[-1] = op (N); \
+ stack_pointer += (SD); \
+ DISPATCH ();
+
+#define ENTRY(N, SD) &&L_##N,
+
+void
+interp (struct frame *frame)
+{
+ static const void *const targets[] = { OPS (ENTRY) };
+ const unsigned short *next_instr = frame->instr_ptr;
+ long *stack_pointer = frame->stackpointer;
+
+ DISPATCH ();
+
+ OPS (HANDLER)
+}
+
+/* { dg-final { scan-tree-dump "vectorization is not profitable" "slp1" {
target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
+/* { dg-final { scan-tree-dump-not "optimized: basic block" "slp1" { target {
{ { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-2.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-2.c
new file mode 100644
index 00000000000..68af64aa6e8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-2.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+
+/* The switch version of bb-slp-pr127246-1.c. Each case runs once for every
+ twenty iterations, the vector construction and the lane extracts on every
+ iteration. */
+
+struct frame
+{
+ const unsigned short *instr_ptr;
+ long *stackpointer;
+};
+
+/* Opcode number and stack delta. */
+#define OPS(X) \
+ X (0, -1) X (1, 0) X (2, -1) X (3, 0) X (4, -1) X (5, 0) \
+ X (6, -1) X (7, 0) X (8, -1) X (9, 0) X (10, -1) X (11, 0) \
+ X (12, -1) X (13, 0) X (14, -1) X (15, 0) X (16, -1) X (17, 0) \
+ X (18, -1) X (19, 0)
+
+extern long op (long);
+
+#define HANDLER(N, SD) \
+ case N: \
+ frame->instr_ptr = next_instr; \
+ next_instr += 1; \
+ frame->stackpointer = stack_pointer; \
+ stack_pointer[-1] = op (N); \
+ stack_pointer += (SD); \
+ break;
+
+long
+interp (struct frame *frame)
+{
+ const unsigned short *next_instr = frame->instr_ptr;
+ long *stack_pointer = frame->stackpointer;
+ for (;;)
+ switch (*next_instr & 0xff)
+ {
+ OPS (HANDLER)
+ default:
+ return stack_pointer[0];
+ }
+}
+
+/* { dg-final { scan-tree-dump "vectorization is not profitable" "slp1" {
target { { { aarch64*-*-* || i?86-*-* } || x86_64-*-* } && lp64 } } } } */
+/* { dg-final { scan-tree-dump-not "optimized: basic block" "slp1" { 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..85e41acd708
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-3.c
@@ -0,0 +1,26 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+/* { dg-additional-options "-mtune=generic" { target aarch64*-*-* } } */
+
+/* The vector code is scheduled at the region entry, where its operands are
+ available, and sunk into the unlikely arm later. It runs as often as
+ the scalar code it replaces. */
+
+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;
+ }
+}
+
+/* { 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-4.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c
new file mode 100644
index 00000000000..973e09be33e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr127246-4.c
@@ -0,0 +1,18 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-additional-options "-fvect-cost-model=dynamic" } */
+
+/* The quotients feed a vector store and a reduction. Without a vector
+ division the store instance turns the quotients into an external, and
+ the reduction instance keeps that external as its root. */
+
+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;
+}
+
+/* { dg-final { scan-tree-dump "from scalars instead" "slp2" { target { { {
aarch64*-*-* && { ! aarch64_sve } } || { i?86-*-* || x86_64-*-* } } && lp64 } }
} } */
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..b8bfb13c7b6
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr127246-2.c
@@ -0,0 +1,26 @@
+/* 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 materialized in that case, so they
+ run as often as the vector stores they feed. */
+
+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" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr127246-3.c
b/gcc/testsuite/gcc.target/aarch64/pr127246-3.c
new file mode 100644
index 00000000000..1afe94a31bc
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr127246-3.c
@@ -0,0 +1,27 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=generic -fdump-tree-slp2-details" } */
+
+/* Each pair of stores follows its own check, so every block runs slightly
+ less often than the one before it. The stores of all blocks share one
+ vector and the target must cost them together. */
+
+struct range { long lb, ub; };
+
+extern void fail (void) __attribute__ ((noreturn));
+
+#define CHECK_STORE(N) \
+ if (p[N].lb) \
+ fail (); \
+ p[N].lb = lb; \
+ p[N].ub = ub;
+
+void
+f (struct range *p, int *lbi, int *ubi)
+{
+ long lb = *lbi, ub = *ubi;
+ CHECK_STORE (0) CHECK_STORE (1) CHECK_STORE (2) CHECK_STORE (3)
+ CHECK_STORE (4) CHECK_STORE (5) CHECK_STORE (6) CHECK_STORE (7)
+}
+
+/* { dg-final { scan-tree-dump "optimized: basic block part vectorized" "slp2"
} } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr127246-4.c
b/gcc/testsuite/gcc.target/aarch64/pr127246-4.c
new file mode 100644
index 00000000000..c75cc9250fe
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr127246-4.c
@@ -0,0 +1,24 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=generic -fdump-tree-slp1-details" } */
+
+/* The vector code in front of the loop starts with conversions that record
+ no cost. The external operand still runs where its users run. */
+
+extern void g (void);
+
+void
+f (short *p, short x0, short x1, int n)
+{
+ for (int i = 0; i < n; i++)
+ {
+ p[0] = x0 + 3;
+ p[1] = x1 + 4;
+ p[2] = x0 + 5;
+ p[3] = x1 + 6;
+ g ();
+ p += 16;
+ }
+}
+
+/* { dg-final { scan-tree-dump "optimized: basic block part vectorized" "slp1"
} } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr127246-5.c
b/gcc/testsuite/gcc.target/aarch64/pr127246-5.c
new file mode 100644
index 00000000000..203bb02c576
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr127246-5.c
@@ -0,0 +1,23 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=generic -fdump-tree-slp1-details" } */
+
+/* All the code in the loop runs equally often, so the vector and scalar
+ costs stay equal and the tie goes to the vector code. */
+
+extern void g (void);
+
+void
+f (int *restrict p, int *restrict q, int x0, int x1, int n)
+{
+ for (int i = 0; i < n; i++)
+ {
+ p[0] = q[0] + q[8] * x0;
+ p[1] = q[1] + q[9] * x1;
+ g ();
+ p += 16;
+ q += 16;
+ }
+}
+
+/* { dg-final { scan-tree-dump "optimized: basic block part vectorized" "slp1"
} } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr127246-6.c
b/gcc/testsuite/gcc.target/aarch64/pr127246-6.c
new file mode 100644
index 00000000000..a6e1bcbea38
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr127246-6.c
@@ -0,0 +1,49 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mtune=generic -fdump-tree-slp-details" } */
+
+/* The vector construction of x and y is placed after the calls, and
+ sinking moves it into the conditional block with its users. */
+
+extern unsigned short foo (unsigned short);
+
+void
+f (unsigned short *out, unsigned short a, unsigned short b, int c)
+{
+ unsigned short x = foo (a), y = foo (b);
+ 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;
+ }
+}
+
+void
+g (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;
+ }
+ }
+}
+
+/* f has no loop and is vectorized by slp2, g by slp1. */
+/* { dg-final { scan-tree-dump "optimized: basic block part vectorized" "slp2"
} } */
+/* { dg-final { scan-tree-dump "optimized: basic block part vectorized" "slp1"
} } */
diff --git a/gcc/testsuite/gcc.target/aarch64/pr127246.c
b/gcc/testsuite/gcc.target/aarch64/pr127246.c
new file mode 100644
index 00000000000..08ef692c47b
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/pr127246.c
@@ -0,0 +1,16 @@
+/* PR tree-optimization/127246 */
+/* { dg-do compile } */
+/* { dg-require-effective-target lp64 } */
+/* { dg-options "-O2" } */
+
+#pragma GCC target "+nosve"
+
+/* Do not move the interpreter state between general and vector registers
+ on every dispatch. */
+
+#include "../../gcc.dg/vect/bb-slp-pr127246-1.c"
+
+/* { dg-final { scan-assembler-not {\tins\t} } } */
+/* { dg-final { scan-assembler-not {\tumov\t} } } */
+/* { dg-final { scan-assembler-not {\tfmov\t} } } */
+/* { dg-final { scan-assembler-not {\tdup\t} } } */
diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
index 12b1abe3d78..9546883a089 100644
--- a/gcc/tree-vect-slp.cc
+++ b/gcc/tree-vect-slp.cc
@@ -9502,11 +9502,13 @@ vect_slp_prune_covered_roots (slp_tree node,
hash_set<stmt_vec_info> &roots,
vect_slp_prune_covered_roots (child, roots, visited);
}
-/* Hand over COST_VEC to the target COSTS grouped by SLP node. */
+/* Hand over COST_VEC to the target COSTS grouped by SLP node and return
+ the sum of the costs the target recorded. */
-static void
+static unsigned
add_slp_costs (vector_costs *costs, stmt_vector_for_cost& cost_vec)
{
+ unsigned sum = 0;
for (unsigned start = 0; start < cost_vec.length ();)
{
unsigned end = start + 1;
@@ -9514,15 +9516,16 @@ add_slp_costs (vector_costs *costs,
stmt_vector_for_cost& cost_vec)
&& cost_vec[start].node == cost_vec[end].node)
end++;
if (cost_vec[start].node)
- costs->add_slp_cost (cost_vec[start].node,
- array_slice<stmt_info_for_cost>
- (cost_vec.begin () + start, end - start));
+ sum += costs->add_slp_cost (cost_vec[start].node,
+ array_slice<stmt_info_for_cost>
+ (cost_vec.begin () + start, end - start));
else
- costs->vector_costs::add_slp_cost (cost_vec[start].node,
- array_slice<stmt_info_for_cost>
- (cost_vec.begin () + start, end - start));
+ sum += costs->vector_costs::add_slp_cost (cost_vec[start].node,
+ array_slice<stmt_info_for_cost>
+ (cost_vec.begin () + start, end - start));
start = end;
}
+ return sum;
}
/* Analyze statements in SLP instances of VINFO. Return true if the
@@ -9871,16 +9874,74 @@ vect_bb_slp_scalar_cost (bb_vec_info vinfo,
}
+/* Return the block of the vector code of the SLP node NODE of BB_VINFO.
+ The schedule places it as early as its operands allow, at NODE->si or at
+ the region entry. Sinking moves it down to the scalar code it replaces
+ or, for a constant or external, to the nearest common dominator of its
+ users in USER_BBS, when that is in the same loop. */
+
+static basic_block
+vect_bb_slp_node_block (bb_vec_info bb_vinfo, slp_tree node,
+ hash_map<slp_tree, basic_block> &user_bbs)
+{
+ basic_block bb = node->si ? gimple_bb (node->si) : bb_vinfo->bbs[0];
+ basic_block sink_bb = NULL;
+ if (SLP_TREE_DEF_TYPE (node) != vect_internal_def)
+ sink_bb = *user_bbs.get (node);
+ else if (stmt_vec_info rep = SLP_TREE_REPRESENTATIVE (node))
+ sink_bb = gimple_bb (vect_orig_stmt (rep)->stmt);
+ if (sink_bb
+ && sink_bb->loop_father == bb->loop_father
+ && dominated_by_p (CDI_DOMINATORS, sink_bb, bb))
+ bb = sink_bb;
+ return bb;
+}
+
+/* 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
+ of the vector code of its users. 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,
+ hash_set<slp_tree> &visited)
+{
+ /* An instance root that analysis turned into an external does not use
+ its children. */
+ if (SLP_TREE_DEF_TYPE (node) != vect_internal_def || visited.add (node))
+ return;
+ basic_block bb = vect_bb_slp_node_block (bb_vinfo, node, user_bbs);
+ for (slp_tree child : SLP_TREE_CHILDREN (node))
+ if (child && SLP_TREE_DEF_TYPE (child) == vect_internal_def)
+ vect_bb_slp_invariant_user_bbs (bb_vinfo, child, user_bbs, visited);
+ else if (child)
+ {
+ basic_block &user_bb = user_bbs.get_or_insert (child);
+ user_bb = nearest_common_dominator (CDI_DOMINATORS, user_bb, bb);
+ }
+}
+
+/* A cost entry together with the index of the loop and the execution
+ frequency of the block containing the code it describes. */
+
+struct li_cost
+{
+ unsigned loop;
+ sreal freq;
+ stmt_info_for_cost *cost;
+};
+
/* Comparator for the loop-index sorted cost vectors. */
static int
li_cost_vec_cmp (const void *a_, const void *b_, void *)
{
- auto *a = (const std::pair<unsigned, stmt_info_for_cost *> *)a_;
- auto *b = (const std::pair<unsigned, stmt_info_for_cost *> *)b_;
- if (a->first < b->first)
+ auto *a = (const li_cost *)a_;
+ auto *b = (const li_cost *)b_;
+ if (a->loop < b->loop)
return -1;
- else if (a->first == b->first)
+ else if (a->loop == b->loop)
return 0;
return 1;
}
@@ -9895,8 +9956,6 @@ vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo,
{
slp_instance instance;
int i;
- unsigned int vec_inside_cost = 0, vec_outside_cost = 0, scalar_cost = 0;
- unsigned int vec_prologue_cost = 0, vec_epilogue_cost = 0;
if (dump_enabled_p ())
{
@@ -9944,43 +10003,48 @@ vect_bb_vectorization_profitable_p (bb_vec_info
bb_vinfo,
now we assume a loop may be not entered or executed an arbitrary
number of iterations (??? static information can provide more
precise info here) which means we can simply cost each containing
- loops stmts separately. */
+ loops stmts separately. Within a loop, code in blocks with different
+ execution frequencies, such as mutually exclusive branches, does not
+ run equally often. Scale the scalar and the vector cost of each loop
+ by the mean frequency of the code they describe, relative to the
+ highest frequency of the code of the loop. */
/* First produce cost vectors sorted by loop index. */
- auto_vec<std::pair<unsigned, stmt_info_for_cost *> >
- li_scalar_costs (scalar_costs.length ());
- auto_vec<std::pair<unsigned, stmt_info_for_cost *> >
- li_vector_costs (vector_costs.length ());
+ auto_vec<li_cost> li_scalar_costs (scalar_costs.length ());
+ auto_vec<li_cost> li_vector_costs (vector_costs.length ());
+ profile_count entry = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
stmt_info_for_cost *cost;
FOR_EACH_VEC_ELT (scalar_costs, i, cost)
{
- unsigned l = gimple_bb (cost->stmt_info->stmt)->loop_father->num;
- li_scalar_costs.quick_push (std::make_pair (l, cost));
+ basic_block bb = gimple_bb (cost->stmt_info->stmt);
+ li_scalar_costs.quick_push ({ (unsigned) bb->loop_father->num,
+ bb->count.to_sreal_scale (entry), cost });
}
- /* Use a random used loop as fallback in case the first vector_costs
+ /* The blocks of the users of each constant and external. */
+ hash_map<slp_tree, basic_block> user_bbs;
+ FOR_EACH_VEC_ELT (slp_instances, i, instance)
+ vect_bb_slp_invariant_user_bbs (bb_vinfo, SLP_INSTANCE_TREE (instance),
+ user_bbs, visited);
+ /* Use a random used block as fallback in case the first vector_costs
entry does not have a location associated with it. */
- unsigned l = li_scalar_costs[0].first;
+ basic_block bb = gimple_bb (li_scalar_costs[0].cost->stmt_info->stmt);
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)
+ bb = vect_bb_slp_node_block (bb_vinfo, cost->node, user_bbs);
/* 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;
+ bb = gimple_bb (cost->stmt_info->stmt);
/* And since vect_prologue_cost_for_slp can end up costing with
neither, inherit from the previous node. */
- li_vector_costs.quick_push (std::make_pair (l, cost));
+ li_vector_costs.quick_push ({ (unsigned) bb->loop_father->num,
+ bb->count.to_sreal_scale (entry), cost });
}
li_scalar_costs.stablesort (li_cost_vec_cmp, NULL);
li_vector_costs.stablesort (li_cost_vec_cmp, NULL);
- unsigned total_vec_outside_cost = 0;
- unsigned total_vec_inside_cost = 0;
- unsigned total_scalar_cost = 0;
+ sreal total_vec_cost = 0, total_scalar_cost = 0;
/* Now cost the portions individually. */
unsigned vi = 0;
@@ -9990,13 +10054,20 @@ vect_bb_vectorization_profitable_p (bb_vec_info
bb_vinfo,
|| vi < li_vector_costs.length ())
{
unsigned sl
- = si < li_scalar_costs.length () ? li_scalar_costs[si].first : -1U;
+ = si < li_scalar_costs.length () ? li_scalar_costs[si].loop : -1U;
unsigned vl
- = vi < li_vector_costs.length () ? li_vector_costs[vi].first : -1U;
+ = vi < li_vector_costs.length () ? li_vector_costs[vi].loop : -1U;
+ unsigned l = MIN (sl, vl);
+ /* The sums of the costs recorded for the code of the loop, the same
+ sums with each cost multiplied by the frequency of its code, and
+ the minimum and maximum frequency. */
+ unsigned scalar_sum = 0, vec_sum = 0;
+ sreal scalar_freq_sum = 0, vec_freq_sum = 0;
+ sreal min_freq = sreal::max (), max_freq = 0;
class vector_costs *scalar_target_cost_data = nullptr;
- scalar_cost = 0;
- if (sl <= vl)
+ sreal scalar_cost = 0;
+ if (sl == l)
{
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
@@ -10004,71 +10075,80 @@ vect_bb_vectorization_profitable_p (bb_vec_info
bb_vinfo,
scalar_target_cost_data = init_cost (bb_vinfo, true);
do
{
- add_stmt_cost (scalar_target_cost_data,
- li_scalar_costs[si].second);
- si++;
+ li_cost &c = li_scalar_costs[si++];
+ unsigned cost = add_stmt_cost (scalar_target_cost_data, c.cost);
+ scalar_sum += cost;
+ scalar_freq_sum += c.freq * cost;
+ min_freq = MIN (min_freq, c.freq);
+ max_freq = MAX (max_freq, c.freq);
}
while (si < li_scalar_costs.length ()
- && li_scalar_costs[si].first == sl);
+ && li_scalar_costs[si].loop == sl);
scalar_target_cost_data->finish_cost (nullptr);
scalar_cost = scalar_target_cost_data->body_cost ();
- total_scalar_cost += scalar_cost;
- if (sl < vl)
- {
- if (dump_enabled_p ())
- dump_printf_loc (MSG_NOTE, vect_location,
- "Scalar %d loop part does not "
- "have corresponding vector part\n", sl);
- delete scalar_target_cost_data;
- continue;
- }
}
/* Complete the target-specific vector cost calculation. */
- if (dump_enabled_p ())
- dump_printf_loc (MSG_NOTE, vect_location,
- "Vector cost for part in loop %d\n", vl);
- class vector_costs *vect_target_cost_data = init_cost (bb_vinfo, false);
- auto_vec<stmt_info_for_cost> tem;
- do
+ sreal vec_cost = 0;
+ if (vl == l)
{
- tem.safe_push (*li_vector_costs[vi].second);
- vi++;
- }
- while (vi < li_vector_costs.length ()
- && li_vector_costs[vi].first == vl);
- add_slp_costs (vect_target_cost_data, tem);
- vect_target_cost_data->finish_cost (scalar_target_cost_data);
- vec_prologue_cost = vect_target_cost_data->prologue_cost ();
- vec_inside_cost = vect_target_cost_data->body_cost ();
- vec_epilogue_cost = vect_target_cost_data->epilogue_cost ();
- if (scalar_target_cost_data)
- delete scalar_target_cost_data;
- delete vect_target_cost_data;
-
- vec_outside_cost = vec_prologue_cost + vec_epilogue_cost;
-
- total_vec_outside_cost += vec_outside_cost;
- total_vec_inside_cost += vec_inside_cost;
-
- if (sl > vl && dump_enabled_p ())
- dump_printf_loc (MSG_NOTE, vect_location,
- "Vector %d loop part does not "
- "have corresponding scalar part\n", vl);
-
- /* When this is vector costs for the region entry delay costing
- and instead only require the total costs to be profitable. */
- if (vl == (unsigned) bb_vinfo->bbs[0]->loop_father->num)
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Vector cost for part in loop %d\n", vl);
+ class vector_costs *vect_target_cost_data
+ = init_cost (bb_vinfo, false);
+ do
+ {
+ /* Weight what the target records for each run of costs with
+ one frequency by that frequency. */
+ sreal freq = li_vector_costs[vi].freq;
+ auto_vec<stmt_info_for_cost> tem;
+ do
+ tem.safe_push (*li_vector_costs[vi++].cost);
+ while (vi < li_vector_costs.length ()
+ && li_vector_costs[vi].loop == vl
+ && li_vector_costs[vi].freq == freq);
+ unsigned cost = add_slp_costs (vect_target_cost_data, tem);
+ vec_sum += cost;
+ vec_freq_sum += freq * cost;
+ min_freq = MIN (min_freq, freq);
+ max_freq = MAX (max_freq, freq);
+ }
+ while (vi < li_vector_costs.length ()
+ && li_vector_costs[vi].loop == vl);
+ vect_target_cost_data->finish_cost (scalar_target_cost_data);
+ vec_cost = (vect_target_cost_data->prologue_cost ()
+ + vect_target_cost_data->body_cost ()
+ + vect_target_cost_data->epilogue_cost ());
+ delete vect_target_cost_data;
+ }
+ delete scalar_target_cost_data;
+
+ /* The costs stay as they are when all the code of the loop has one
+ frequency, and when optimizing for size, where code counts the same
+ wherever it is. */
+ if (min_freq != max_freq && !optimize_function_for_size_p (cfun))
+ {
+ if (scalar_sum)
+ scalar_cost *= scalar_freq_sum / (max_freq * scalar_sum);
+ if (vec_sum)
+ vec_cost *= vec_freq_sum / (max_freq * vec_sum);
+ }
+ total_scalar_cost += scalar_cost;
+ total_vec_cost += vec_cost;
+
+ /* When this is the loop of the region entry delay costing and
+ instead only require the total costs to be profitable. */
+ if (l == (unsigned) bb_vinfo->bbs[0]->loop_father->num)
continue;
if (dump_enabled_p ())
{
dump_printf_loc (MSG_NOTE, vect_location,
- "Cost model analysis for part in loop %d:\n",
- std::min (sl, vl));
- dump_printf (MSG_NOTE, " Vector cost: %d\n",
- vec_inside_cost + vec_outside_cost);
- dump_printf (MSG_NOTE, " Scalar cost: %d\n", scalar_cost);
+ "Cost model analysis for part in loop %d:\n", l);
+ dump_printf (MSG_NOTE, " Vector cost: %f\n", vec_cost.to_double ());
+ dump_printf (MSG_NOTE, " Scalar cost: %f\n",
+ scalar_cost.to_double ());
}
/* Vectorization is profitable if its cost is more than the cost of
scalar
@@ -10076,7 +10156,7 @@ vect_bb_vectorization_profitable_p (bb_vec_info
bb_vinfo,
the cost estimate is otherwise quite pessimistic (constant uses are
free on the scalar side but cost a load on the vector side for
example). */
- if (vec_outside_cost + vec_inside_cost > scalar_cost)
+ if (vec_cost > scalar_cost)
profitable = false;
}
@@ -10084,14 +10164,15 @@ vect_bb_vectorization_profitable_p (bb_vec_info
bb_vinfo,
{
dump_printf_loc (MSG_NOTE, vect_location,
"Cost model analysis for whole subgraph:\n");
- dump_printf (MSG_NOTE, " Vector cost: %d\n",
- total_vec_inside_cost + total_vec_outside_cost);
- dump_printf (MSG_NOTE, " Scalar cost: %d\n", total_scalar_cost);
+ dump_printf (MSG_NOTE, " Vector cost: %f\n",
+ total_vec_cost.to_double ());
+ dump_printf (MSG_NOTE, " Scalar cost: %f\n",
+ total_scalar_cost.to_double ());
}
/* For the case where the outermost region had no scalar cost require
overall profitability. */
- if (total_vec_outside_cost + total_vec_inside_cost > total_scalar_cost)
+ if (total_vec_cost > total_scalar_cost)
profitable = false;
/* Unset visited flag. This is delayed when the subgraph is profitable
--
2.50.1 (Apple Git-155)
