This is my magnum opus for GCC 17 (hopefully)
### Introduction
The main intended purpose of this work is threefold:
1. Support re-optimizing intrinsics and vector code in SLP that was created by
earlier vectorization passes. For example, two back-to-back loops could be
completely unrolled and vectorized during loop vectorization, but would not
then be optimized together. The idea is to let SLP discovery re-analyze the
vector code as a single entity. This makes the long-standing question of
whether BB SLP or loop vectorization should run first less important, since
we can re-vectorize the generated vector code.
2. Support Arm SVE2's Hybrid Vector Length Agnostic (HVLA) programming model.
The intention is to transform code written with intrinsics for older AdvSIMD
code into VLA code, so that we can use longer vector lengths.
3. Support workloads, particularly scientific-computing workloads, in which
users manually create vector types that are longer than the target supports
using GCC vector extensions. The expectation is that the compiler can then
decompose those operations into supported operations. Clang can do this for
some examples, although its approach seems quite limited and appears to work
only when the operations are constructors of PHI nodes.
4. Support vector decomposition and induction handling that were never valid for
the target but were writeable using GNU extensions.
To solve these problems, the approach I have taken in GCC is to model vector
types as possible base "scalar" types. The main advantage is that the current
compiler workflows can stay the same. Fundamentally, this does not change most
of the vectorizer, apart from analysis and the usual extensions to the code
generators.
This also means that the code remains subject to cost modelling and to other
features we have added over the years, such as epilogue masks.
As an example:
```c
#include <arm_neon.h>
void foo (uint8_t *a, uint8_t *b, uint8_t *c, int n)
{
for (int i = 0; i < n; i += 16, a += 16, b += 16, c += 16)
{
uint8x8_t av1 = vld1_u8 (a);
uint8x8_t av2 = vld1_u8 (a + 8);
uint8x8_t bv1 = vld1_u8 (b);
uint8x8_t bv2 = vld1_u8 (b + 8);
vst1_u8 (c, vadd_u8 (av1, bv1));
vst1_u8 (c + 8, vadd_u8 (av2, bv2));
}
}
```
At the moment, `-O3` generates:
```asm
.L3:
ldr d29, [x0, x4]
ldr d28, [x1, x4]
ldr d31, [x7, x4]
ldr d30, [x6, x4]
add v28.8b, v29.8b, v28.8b
add v30.8b, v31.8b, v30.8b
str d28, [x2, x4]
str d30, [x5, x4]
add x4, x4, 16
cmp w3, w4
bgt .L3
```
This underuses the available load bandwidth. Ideally these would be Q-sized
loads and one ADD, i.e. SLP would combine them.
With the branch, `-O3 -march=armv8-a` generates:
```asm
.L5:
ldr q31, [x0, x4]
ldr q30, [x1, x4]
add v30.16b, v31.16b, v30.16b
str q30, [x2, x4]
add x4, x4, 16
cmp x4, x7
bne .L5
```
`-O3 -march=armv8-a+sve` generates:
```asm
.L5:
ldr q31, [x0, x3]
ldr q30, [x1, x3]
add v30.16b, v31.16b, v30.16b
str q30, [x2, x3]
add x3, x3, 16
cmp x5, x3
bne .L5
lsl w3, w4, 4
cmp w6, w3
beq .L1
.L4:
sub w6, w6, w3
ubfiz x3, x3, 3, 32
whilelo p7.b, xzr, x6
ld1b z29.b, p7/z, [x0, x3]
ld1b z28.b, p7/z, [x1, x3]
add z28.b, z28.b, z29.b
st1b z28.b, p7, [x2, x3]
.L1:
```
`-O3 -march=armv8-a+sve -mautovec-preference=sve-only` generates:
```asm
.L4:
ld1b z31.b, p7/z, [x0, x4]
ld1b z30.b, p7/z, [x1, x4]
add z30.b, z30.b, z31.b
st1b z30.b, p7, [x2, x4]
add x4, x4, x5
whilelo p7.b, x4, x3
b.any .L4
```
### Representation
There is no change to the SLP trees themselves. The vector operation is added
to the node with N SLP lanes. Essentially every vector statement is of NUNITs
increases lane count by NUNIT lanes.
As temporary group matching for SLP builds the scalar statement is duplicated
but this is not the underlying representation used.
The group size for the operation is then set to the number of units in the
incoming vector. For memory accesses, `dr_group_size` is increased too. At
the moment, and probably for the first version, I only plan to support linear
loads and load-lane operations. Recognizing the other load types requires a
target hook and time to fill in the DRs.
For BB SLP, the current code starts a seed whenever it finds a store with a
vector type that the target does not support. This then fails analysis because
no vector type can be found. The plan is to make vector type selection return
the largest supported type for the given inner mode. During `vectorizable_*`
analysis, we would then avoid doing any other check beyond whether the target
supports the new mode for the given operation. To match the incoming VF, we
would increase the required unroll factor so that we get the same effective VF.
This patch series only supports linear, fixed length loads. This is because
modelling the other loads and VLA requires more representational changes. The
patch series also tries to weave in little by little tracking of vector mode
operations lane wise. So even though we have 1 vector, the implementation
tracks each individual lane. This is needed to get things like permutations
and inductions and reductions correct.
Lastly this patch will likely require target maintainers to add
-fno-tree-vectorize to some testcases in their targets. I have updated x86_64,
aarch64 and arm with this patch.
Others need to do this for themselves.
Decreasing the VF is not possible at the moment. For example:
```c
#include <arm_neon.h>
void foo (uint8_t *a, uint8_t *b, uint8_t *c, int n)
{
for (int i = 0; i < n; i += 32, a += 32, b += 32, c += 32)
{
uint8x16_t av1 = vld1q_u8 (a);
uint8x16_t av2 = vld1q_u8 (a + 16);
uint8x16_t bv1 = vld1q_u8 (b);
uint8x16_t bv2 = vld1q_u8 (b + 16);
vst1q_u8 (c, vaddq_u8 (av1, bv1));
vst1q_u8 (c + 16, vaddq_u8 (av2, bv2));
}
}
```
cannot collapse down to:
```asm
.L5:
ldr q31, [x0, x4]
ldr q30, [x1, x4]
add v30.16b, v31.16b, v30.16b
str q30, [x2, x4]
add x4, x4, 16
cmp x4, x7
bne .L5
```
This would require fractional VF support; in other words, it would require
support for re-rolling the loop. With the current design, that should work
naturally once we add fractional VF support.
### Areas that need the most changes
The biggest changes are in vector boolean handling, vector conditional
identification and SLP lane tracking.
The series is 14 long, only 1 of which are middle end code, and each patch
introduces an small isolated change to the vectorizer. I spent a lot of time
on making sure these are easy to review but some changes just needed to happen.
This also re-uses the IFN_MASK_CALL operation to support foldings from unmasked
to masked implementations. This required a changed to all targets which have a
custom folder implementation to reject this IFN. Hopefully a global reviewer
can approve this.
### Vector Operations
There are two types of vector operations that we want to support here.
The first type uses a normal GIMPLE representation. In the examples above,
`vadd` is lowered as a normal `PLUS_EXPR`, so testing and transforming it is
straightforward.
In many other cases, however, we see target intrinsics. To vectorize these, I
have added a new `vectorizable_vect_call` that uses a target hook,
`targetm.vectorize.translate_builtin_call`, to fill in vectorization
information about the call. In particular, the hook must be able to tell the
vectorizer whether we are going from an unmasked mode to a masked mode, whether
there is a builtin with masking support that we can use, and where the mask
argument appears in the argument list.
### Vector Booleans
Normally, the vectorizer has to detect booleans in order to differentiate data
operations from control operations. When vectorizing existing vector code,
that has already been done for us. However, we still need to be able to expand
the lanes and, if necessary, convert between boolean representation models.
For example, when changing AdvSIMD code into SVE code, the boolean
representation has to change because the underlying truth type is different.
To fix this and support boolean operations, there is a new pattern,
`vect_recog_vect_bool_pattern`, that runs only on boolean vector comparisons.
It transforms them using a pattern as a scalar boolean. That is, it creates:
```c
cmp ? -1 : 0
```
from a vector comparison, with the type of the operation set to the truth type
of the original code. This allows us to vectorize these as if they were normal
scalar comparisons.
For example:
```c
#include <arm_neon.h>
void foo (uint8_t *a, uint8_t *b, uint8_t *c, int n)
{
for (int i = 0; i < n; i += 8, a += 8, b += 8, c += 8)
{
uint8x8_t av1 = vld1_u8 (a);
uint8x8_t bv1 = vld1_u8 (b);
vst1_u8 (c, vcgt_u8 (av1, bv1));
}
}
```
compiled with `-march=armv9-a+sve -O3` gives:
```asm
.L5:
ldr q31, [x1, x3]
ldr q30, [x0, x3]
cmhi v30.16b, v30.16b, v31.16b
str q30, [x2, x3]
add x3, x3, 16
cmp x3, x5
bne .L5
lsl w3, w4, 4
cmp w6, w3
beq .L1
.L4:
sub w6, w6, w3
ptrue p6.b, all
ubfiz x3, x3, 3, 32
whilelo p7.b, xzr, x6
ld1b z28.b, p7/z, [x0, x3]
ld1b z27.b, p7/z, [x1, x3]
cmplo p15.b, p6/z, z27.b, z28.b
mov z29.b, p15/z, #-1
st1b z29.b, p7, [x2, x3]
.L1:
ret
.p2align 2,,3
.L6:
mov x4, 0
.p2align 5,,15
.L3:
ldr d26, [x0, x4]
ldr d25, [x1, x4]
cmhi v25.8b, v26.8b, v25.8b
str d25, [x2, x4]
add x4, x4, 8
cmp w3, w4
bgt .L3
ret
.L7:
mov w3, 0
b .L4
```
The vectorizer is now able to handle the conversion between different boolean
modes while preserving the lane values of the original code. The vectorizer
does this by tracking mask producing operations and mask consuming operations.
No target support is needed here so there are no additional hooks.
### Vector Patterns
The incoming code may use vector operations to perform masking through manually
if-converted code. For example:
```c
#include <arm_neon.h>
#include <arm_sve.h>
void foo (uint8_t *a, uint8_t *b, uint8_t *c, int n)
{
for (int i = 0; i < n; i += 8, a += 8, b += 8, c += 8)
{
uint8x8_t av1 = vld1_u8 (a);
uint8x8_t bv1 = vld1_u8 (b);
uint8x8_t cmp = vcgt_u8 (bv1, vdup_n_u8 (0));
uint8x8_t add = vadd_u8 (bv1, vdup_n_u8 (1));
uint8x8_t sel = vbsl_u8 (cmp, add, bv1);
vst1_u8 (a, sel);
}
}
```
This is a manually if-converted conditional add. We can re-vectorize it as-is,
but what we really want is to optimize it as a masked operation.
The vectorizer does this by tracking mask producing operations and mask
consuming operations. No target support is needed here so there are no
additional hooks.
In the above, the vectorizer tracks statements that produce masks, e.g. compares
and statements that consume masks, e.g. selects and tries to work out if
together the operation results in a conditional operation. This is needed
because operations like AArch64's BSL are bitwise operations and are only valid
usually when the producer has made a -1 or 0 values result.
The above for instance generates:
```asm
mov z30.b, #1
.L4:
ld1b z31.b, p7/z, [x1, x2]
cmpne p6.b, p7/z, z31.b, #0
add z31.b, p6/m, z31.b, z30.b
st1b z31.b, p7, [x0, x2]
incb x2
whilelo p7.b, x2, x3
b.any .L4
```
We can extend this with more idioms later as we find them.
### Vector decomposition
One of the primary use cases here is to also support vector decomposition to
known support vector operations.
This is handled by starting SLP from unsupported vector operations (or in SLP
terms, emulated vectors) and treating those as seeds.
For example
```
typedef float v4sf __attribute__((vector_size(16)));
typedef float v8sf __attribute__((vector_size(32)));
v8sf
swap_halves (v8sf v)
{
v4sf d[2];
v4sf t;
__builtin_memcpy (d, &v, sizeof v);
t = d[0];
d[0] = d[1];
d[1] = t;
__builtin_memcpy (&v, d, sizeof v);
return v;
}
```
today compiles to
```
swap_halves(float vector[8]):
ldp q31, q30, [x0]
sub sp, sp, #64
stp q30, q31, [sp]
ldr q29, [sp, 16]
stp q30, q29, [x8]
add sp, sp, 64
ret
```
but with revectorization compiles instead to
```
swap_halves:
ldp q30, q31, [x0]
stp q31, q30, [x8]
ret
```
Another example is
```
typedef unsigned vec256 __attribute__((__vector_size__(32)));
void vec_xor_shuf(vec256& x)
{
x ^= 1;
x = (vec256){x[4], x[0], x[5], x[1], x[6], x[2], x[7], x[3]};
}
```
which today produces:
```
vec_xor_shuf(unsigned int vector[8]&):
ldp q30, q31, [x0]
mov w3, 0
mov w4, 0
mov w1, 0
mov w2, 0
mov v29.16b, v31.16b
eor z30.s, z30.s, 1
eor z29.s, z29.s, 1
dup s28, v30.s[1]
dup s31, v30.s[2]
fmov x5, d29
dup s26, v29.s[1]
dup s27, v29.s[2]
dup s29, v29.s[3]
bfi x3, x5, 0, 32
fmov x5, d30
dup s30, v30.s[3]
bfi x3, x5, 32, 32
fmov x5, d26
bfi x4, x5, 0, 32
fmov x5, d27
bfi x1, x5, 0, 32
fmov x5, d29
bfi x2, x5, 0, 32
fmov x5, d28
bfi x4, x5, 32, 32
stp x3, x4, [x0]
fmov x3, d31
bfi x1, x3, 32, 32
fmov x3, d30
bfi x2, x3, 32, 32
stp x1, x2, [x0, 16]
ret
```
where vect lowering had no choice but to scalarize the operation.
With the patch this produces
```
```
_Z12vec_xor_shufRDv8_j:
ldp q31, q30, [x0]
eor z31.s, z31.s, 1
eor z30.s, z30.s, 1
zip1 v29.4s, v30.4s, v31.4s
zip2 v30.4s, v30.4s, v31.4s
stp q29, q30, [x0]
ret
```
I am still working through the PRs that this patch fixes so have only included
the main one. But believe we are in a good enough shape for stage 1.
For the final commit (if accepted) I will add all the PRs.
--
