[V2] VECT: Add SELECT_VL support
Checks
Commit Message
From: Ju-Zhe Zhong <juzhe.zhong@rivai.ai>
This patch address comments from Richard and rebase to trunk.
This patch is adding SELECT_VL middle-end support
allow target have target dependent optimization in case of
length calculation.
This patch is inspired by RVV ISA and LLVM:
https://reviews.llvm.org/D99750
The SELECT_VL is same behavior as LLVM "get_vector_length" with
these following properties:
1. Only apply on single-rgroup.
2. non SLP.
3. adjust loop control IV.
4. adjust data reference IV.
5. allow non-vf elements processing in non-final iteration
Code:
# void vvaddint32(size_t n, const int*x, const int*y, int*z)
# { for (size_t i=0; i<n; i++) { z[i]=x[i]+y[i]; } }
Take RVV codegen for example:
Before this patch:
vvaddint32:
ble a0,zero,.L6
csrr a4,vlenb
srli a6,a4,2
.L4:
mv a5,a0
bleu a0,a6,.L3
mv a5,a6
.L3:
vsetvli zero,a5,e32,m1,ta,ma
vle32.v v2,0(a1)
vle32.v v1,0(a2)
vsetvli a7,zero,e32,m1,ta,ma
sub a0,a0,a5
vadd.vv v1,v1,v2
vsetvli zero,a5,e32,m1,ta,ma
vse32.v v1,0(a3)
add a2,a2,a4
add a3,a3,a4
add a1,a1,a4
bne a0,zero,.L4
.L6:
ret
After this patch:
vvaddint32:
vsetvli t0, a0, e32, ta, ma # Set vector length based on 32-bit vectors
vle32.v v0, (a1) # Get first vector
sub a0, a0, t0 # Decrement number done
slli t0, t0, 2 # Multiply number done by 4 bytes
add a1, a1, t0 # Bump pointer
vle32.v v1, (a2) # Get second vector
add a2, a2, t0 # Bump pointer
vadd.vv v2, v0, v1 # Sum vectors
vse32.v v2, (a3) # Store result
add a3, a3, t0 # Bump pointer
bnez a0, vvaddint32 # Loop back
ret # Finished
gcc/ChangeLog:
* doc/md.texi: Add SELECT_VL support.
* internal-fn.def (SELECT_VL): Ditto.
* optabs.def (OPTAB_D): Ditto.
* tree-vect-loop-manip.cc (vect_set_loop_controls_directly): Ditto.
* tree-vect-loop.cc (_loop_vec_info::_loop_vec_info): Ditto.
* tree-vect-stmts.cc (get_select_vl_data_ref_ptr): Ditto.
(vectorizable_store): Ditto.
(vectorizable_load): Ditto.
* tree-vectorizer.h (LOOP_VINFO_USING_SELECT_VL_P): Ditto.
---
gcc/doc/md.texi | 22 +++++++++++++
gcc/internal-fn.def | 1 +
gcc/optabs.def | 1 +
gcc/tree-vect-loop-manip.cc | 32 +++++++++++++-----
gcc/tree-vect-loop.cc | 48 +++++++++++++++++++++++++++
gcc/tree-vect-stmts.cc | 66 +++++++++++++++++++++++++++++++++++++
gcc/tree-vectorizer.h | 6 ++++
7 files changed, 167 insertions(+), 9 deletions(-)
Comments
juzhe.zhong@rivai.ai writes:
> + /* If we're using decrement IV approach in loop control, we can use output of
> + SELECT_VL to adjust IV of loop control and data reference when it satisfies
> + the following checks:
> +
> + (a) SELECT_VL is supported by the target.
> + (b) LOOP_VINFO is single-rgroup control.
> + (c) non-SLP.
> + (d) LOOP can not be unrolled.
> +
> + Otherwise, we use MIN_EXPR approach.
> +
> + 1. We only apply SELECT_VL on single-rgroup since:
> +
> + (1). Multiple-rgroup controls N vector loads/stores would need N pointer
> + updates by variable amounts.
> + (2). SELECT_VL allows flexible length (<=VF) in each iteration.
> + (3). For decrement IV approach, we calculate the MAX length of the loop
> + and then deduce the length of each control from this MAX length.
> +
> + Base on (1), (2) and (3) situations, if we try to use SELECT_VL on
> + multiple-rgroup control, we need to generate multiple SELECT_VL to
> + carefully adjust length of each control.
If we use SELECT_VL to refer only to the target-independent ifn, I don't
see why this last bit is true. Like I said in the previous message,
when it comes to determining the length of each control, the approach we
take for MIN_EXPR IVs should work for SELECT_VL IVs. The point is that,
in both cases, any inactive lanes are always the last lanes.
E.g. suppose that, for one particular iteration, SELECT_VL decides that
6 lanes should be active in a loop with VF==8. If there is a 2-control
rgroup with 4 lanes each, the first control must be 4 and the second
control must be 2, just as if a MIN_EXPR had decided that 6 lanes of
the final iteration are active.
I'm not saying the decision itself is wrong. But I think the explanation
could be clearer.
> + Such approach is very inefficient
> + and unprofitable for targets that are using a standalone instruction
> + to configure the length of each operation.
> + E.g. RISC-V vector use 'vsetvl' to configure the length of each operation.
What I don't understand is why this isn't also a problem with the
fallback MIN_EXPR approach. That is, with the same example as above,
but using MIN_EXPR IVs, I would have expected:
VF == 8
1-control rgroup "A":
A set by MIN_EXPR IV
2-control rgroup "B1", "B2":
B1 = MIN (A, 4)
B2 = A - B1
and so the vectors controlled by A, B1 and B2 would all have different
lengths.
Is the point that, when using MIN_EXPR, this only happens in the
final iteration? And that you use a tail/epilogue loop for that,
so that the main loop body operates on full vectors only?
Thanks,
Richard
Hi, Richard. Thanks for the comments.
>> If we use SELECT_VL to refer only to the target-independent ifn, I don't
>> see why this last bit is true.
Could you give me more details and information about this since I am not sure whether I catch up with you.
You mean the current SELECT_VL is not an appropriate IFN?
>>Like I said in the previous message,
>>when it comes to determining the length of each control, the approach we
>>take for MIN_EXPR IVs should work for SELECT_VL IVs. The point is that,
>>in both cases, any inactive lanes are always the last lanes.
>>E.g. suppose that, for one particular iteration, SELECT_VL decides that
>>6 lanes should be active in a loop with VF==8. If there is a 2-control
>>rgroup with 4 lanes each, the first control must be 4 and the second
>>control must be 2, just as if a MIN_EXPR had decided that 6 lanes of
>>the final iteration are active.
>>What I don't understand is why this isn't also a problem with the
>>fallback MIN_EXPR approach. That is, with the same example as above,
>>but using MIN_EXPR IVs, I would have expected:
>> VF == 8
>> 1-control rgroup "A":
>> A set by MIN_EXPR IV
>> 2-control rgroup "B1", "B2":
>> B1 = MIN (A, 4)
>> B2 = A - B1
>>and so the vectors controlled by A, B1 and B2 would all have different
>>lengths.
>>Is the point that, when using MIN_EXPR, this only happens in the
>>final iteration? And that you use a tail/epilogue loop for that,
>>so that the main loop body operates on full vectors only?
In general, I think your description is correct and comprehensive.
I'd like to share more my understanding to make sure we are on the same page.
Take the example as you said:
FOR one particular iteration, SELECT_VL decides that 6 lanes should be active in a loop with VF==8.
and 2-control rgroup with 4 lanes each
which means:
VF = 8;
each control VF = 4;
Total length = SELECT_VL(or MIN_EXPR) (remain, 8)
Then, IMHO, we can have 3 solutions to deduce the length of 2-control base on current flow we already built
Also, let me share "vsetvl" ISA spec:
ceil(AVL / 2) ≤ vl ≤ VF if VF <AVL < (2 * VF)
"vl" is the number of the elements we need to process, "avl" = the actual number of elements we will process in the current iteration
Solution 1:
Total length = SELECT_VL (remain, 8) ===> suppose Total length value = 6
control 1 length = SELECT_VL (Total length, 4) ===> If we use "vsetvl" intruction to get the control 1 length,
it can be 3 or 4, since RVV ISA: ceil(AVL / 2) ≤ vl ≤ VF if AVL < (2 * VF), the outcome of SELECT_VL may be Total length / 2 = 3
Depending on the hardware implementation of "vsetvli", Let's say some RVV CPU likes "even distribution" the outcome = 3
control 2 length = Total length - control 1 length ===> 6 - 3 = 3 (if control 1 = 3) or 6 - 4 = 2 (if control 1 = 4) .
Since RVV ISA gives the flexible definition of "vsetvli", we will end up with this deduction.
Solution 2:
Total length = SELECT_VL (remain, 8) ====> 6
control 1 length = MIN_EXPR (Total length, 4) ====> since use MIN, so always 4
control 2 length = Total length - control 1 length ===> 6 - 4 = 2
Solution 3 (Current flow):
Total length = MIN_EXPR (remain, 8) ====> 6 only when the remain = 6 in tail/epilogue, otherwise, it always be 8 in loop body.
control 1 length = MIN_EXPR (Total length, 4) ====> since use MIN, so always 4
control 2 length = Total length - control 1 length ===> Total length - 4
I'd like to say these 3 solutions all work for RVV.
However, RVV length configuration unlike IBM or ARM SVE using a mask. (I would like to say mask or length they are the same thing, use for control of each operations).
For example, ARM SVE has 8 mask registers, whenever it generate a mask, it can be include in use list in the instructions, since ARM SVE use encoding to specify the mask
register.
For example:
If we are using solution 1 in a target that control by length and length is specified in general registers, we can simulate the codegen as below.
max length = select_vl (vf=8)
length 1 = select_vl (vf=4)
length 2 = max length - length 1
...
load (...use general register which storing length 1 let's said r0, r0 is specified in the load encoding)
...
load (...use general register which storing length 2 let's said r1, r1 is specified in the load encoding)
....
However, for RVV, we don't specify the length in the instructions encoding.
Instead, we have only one VL register, and every time we want to change the length, we need"vsetvli"
So for solution 1, we will have:
max length = vsetvli (vf=8)
length 1 = vsetlvi (vf=4)
length 2 = max length = length 1
...
vsetvli zero, length 1 <======insert by "VSETVL" PASS of RISC-V backend
load....
vsetvli zero, length 2 <======insert by "VSETVL" PASS of RISC-V backend
load....
"vsetlvi" instruction is the instruction much more expensive than the general scalar instruction (for example "min" is much cheaper than "vsetvli").
So I am 100% sure that solution 3 (current MIN flow in GCC) is much better than above:
max length = min (vf=8) ===> replaced "vsetli" by "min"
length 1 = min (vf=4) ===> replaced "vsetli" by "min"
length 2 = max length = length 1
...
vsetvli zero, length 1 <======insert by "VSETVL" PASS of RISC-V backend
load....
vsetvli zero, length 2 <======insert by "VSETVL" PASS of RISC-V backend
load....
This is much better than Solution 3 and avoid multiple switching of "VL" register by "vsetvli"
Ok, you may want ask if "min" is much cheaper than "vsetvli", why we need SELECT_VL?
The reason is I want to optimize the special case (single-rgoup), since rgroup is just using a single length,
unlike multiple-rgroup control which has multiple length calculation statement:
Current flow of single-rgoup:
...
length = min (vf)
...
vsetvli zero. length <=== insert by VSETLVI PASS
load (pointer IV)
vadd.
...
pointer IV = pointer IV + VF
I want to optimize it into:
...
length = vsetvli (Vf)
... <=== not need to insert vsetvlli.
load (pointer IV)
vadd.
...
pointer IV = pointer IV + length (adjust in bytesize).
This flow is the same as RVV ISA and LLVM.
And also base on "vsetvli" definition, we can allow "even distribution" in the last iterations.
Hope my description is clear, feel free to comment.
Thanks so much.
juzhe.zhong@rivai.ai
From: Richard Sandiford
Date: 2023-06-05 14:21
To: juzhe.zhong
CC: gcc-patches; rguenther
Subject: Re: [PATCH V2] VECT: Add SELECT_VL support
juzhe.zhong@rivai.ai writes:
> + /* If we're using decrement IV approach in loop control, we can use output of
> + SELECT_VL to adjust IV of loop control and data reference when it satisfies
> + the following checks:
> +
> + (a) SELECT_VL is supported by the target.
> + (b) LOOP_VINFO is single-rgroup control.
> + (c) non-SLP.
> + (d) LOOP can not be unrolled.
> +
> + Otherwise, we use MIN_EXPR approach.
> +
> + 1. We only apply SELECT_VL on single-rgroup since:
> +
> + (1). Multiple-rgroup controls N vector loads/stores would need N pointer
> + updates by variable amounts.
> + (2). SELECT_VL allows flexible length (<=VF) in each iteration.
> + (3). For decrement IV approach, we calculate the MAX length of the loop
> + and then deduce the length of each control from this MAX length.
> +
> + Base on (1), (2) and (3) situations, if we try to use SELECT_VL on
> + multiple-rgroup control, we need to generate multiple SELECT_VL to
> + carefully adjust length of each control.
If we use SELECT_VL to refer only to the target-independent ifn, I don't
see why this last bit is true. Like I said in the previous message,
when it comes to determining the length of each control, the approach we
take for MIN_EXPR IVs should work for SELECT_VL IVs. The point is that,
in both cases, any inactive lanes are always the last lanes.
E.g. suppose that, for one particular iteration, SELECT_VL decides that
6 lanes should be active in a loop with VF==8. If there is a 2-control
rgroup with 4 lanes each, the first control must be 4 and the second
control must be 2, just as if a MIN_EXPR had decided that 6 lanes of
the final iteration are active.
I'm not saying the decision itself is wrong. But I think the explanation
could be clearer.
> + Such approach is very inefficient
> + and unprofitable for targets that are using a standalone instruction
> + to configure the length of each operation.
> + E.g. RISC-V vector use 'vsetvl' to configure the length of each operation.
What I don't understand is why this isn't also a problem with the
fallback MIN_EXPR approach. That is, with the same example as above,
but using MIN_EXPR IVs, I would have expected:
VF == 8
1-control rgroup "A":
A set by MIN_EXPR IV
2-control rgroup "B1", "B2":
B1 = MIN (A, 4)
B2 = A - B1
and so the vectors controlled by A, B1 and B2 would all have different
lengths.
Is the point that, when using MIN_EXPR, this only happens in the
final iteration? And that you use a tail/epilogue loop for that,
so that the main loop body operates on full vectors only?
Thanks,
Richard
"juzhe.zhong@rivai.ai" <juzhe.zhong@rivai.ai> writes:
> Hi, Richard. Thanks for the comments.
>
>>> If we use SELECT_VL to refer only to the target-independent ifn, I don't
>>> see why this last bit is true.
> Could you give me more details and information about this since I am not sure whether I catch up with you.
> You mean the current SELECT_VL is not an appropriate IFN?
No, I meant that the comment I quoted seemed to be saying that solution
3 wasn't possible. The comment seemed to say that we would need to do
solution 1.
>>>Like I said in the previous message,
>>>when it comes to determining the length of each control, the approach we
>>>take for MIN_EXPR IVs should work for SELECT_VL IVs. The point is that,
>>>in both cases, any inactive lanes are always the last lanes.
>>>E.g. suppose that, for one particular iteration, SELECT_VL decides that
>>>6 lanes should be active in a loop with VF==8. If there is a 2-control
>>>rgroup with 4 lanes each, the first control must be 4 and the second
>>>control must be 2, just as if a MIN_EXPR had decided that 6 lanes of
>>>the final iteration are active.
>>>What I don't understand is why this isn't also a problem with the
>>>fallback MIN_EXPR approach. That is, with the same example as above,
>>>but using MIN_EXPR IVs, I would have expected:
>>> VF == 8
>>> 1-control rgroup "A":
>>> A set by MIN_EXPR IV
>>> 2-control rgroup "B1", "B2":
>>> B1 = MIN (A, 4)
>>> B2 = A - B1
>>>and so the vectors controlled by A, B1 and B2 would all have different
>>>lengths.
>>>Is the point that, when using MIN_EXPR, this only happens in the
>>>final iteration? And that you use a tail/epilogue loop for that,
>>>so that the main loop body operates on full vectors only?
> In general, I think your description is correct and comprehensive.
> I'd like to share more my understanding to make sure we are on the same page.
>
> Take the example as you said:
>
> FOR one particular iteration, SELECT_VL decides that 6 lanes should be active in a loop with VF==8.
> and 2-control rgroup with 4 lanes each
> which means:
>
> VF = 8;
> each control VF = 4;
>
> Total length = SELECT_VL(or MIN_EXPR) (remain, 8)
> Then, IMHO, we can have 3 solutions to deduce the length of 2-control base on current flow we already built
>
> Also, let me share "vsetvl" ISA spec:
> ceil(AVL / 2) ≤ vl ≤ VF if VF <AVL < (2 * VF)
> "vl" is the number of the elements we need to process, "avl" = the actual number of elements we will process in the current iteration
>
> Solution 1:
>
> Total length = SELECT_VL (remain, 8) ===> suppose Total length value = 6
>
> control 1 length = SELECT_VL (Total length, 4) ===> If we use "vsetvl" intruction to get the control 1 length,
> it can be 3 or 4, since RVV ISA: ceil(AVL / 2) ≤ vl ≤ VF if AVL < (2 * VF), the outcome of SELECT_VL may be Total length / 2 = 3
> Depending on the hardware implementation of "vsetvli", Let's say some RVV CPU likes "even distribution" the outcome = 3
>
> control 2 length = Total length - control 1 length ===> 6 - 3 = 3 (if control 1 = 3) or 6 - 4 = 2 (if control 1 = 4) .
>
> Since RVV ISA gives the flexible definition of "vsetvli", we will end up with this deduction.
Yeah, this one wouldn't work, for reasons discussed previously.
I was thinking only about solutions 2 and 3.
> Solution 2:
>
> Total length = SELECT_VL (remain, 8) ====> 6
> control 1 length = MIN_EXPR (Total length, 4) ====> since use MIN, so always 4
> control 2 length = Total length - control 1 length ===> 6 - 4 = 2
>
> Solution 3 (Current flow):
>
> Total length = MIN_EXPR (remain, 8) ====> 6 only when the remain = 6 in tail/epilogue, otherwise, it always be 8 in loop body.
> control 1 length = MIN_EXPR (Total length, 4) ====> since use MIN, so always 4
> control 2 length = Total length - control 1 length ===> Total length - 4
>
> I'd like to say these 3 solutions all work for RVV.
> However, RVV length configuration unlike IBM or ARM SVE using a mask. (I would like to say mask or length they are the same thing, use for control of each operations).
> For example, ARM SVE has 8 mask registers, whenever it generate a mask, it can be include in use list in the instructions, since ARM SVE use encoding to specify the mask
> register.
>
> For example:
> If we are using solution 1 in a target that control by length and length is specified in general registers, we can simulate the codegen as below.
>
> max length = select_vl (vf=8)
> length 1 = select_vl (vf=4)
> length 2 = max length - length 1
> ...
> load (...use general register which storing length 1 let's said r0, r0 is specified in the load encoding)
> ...
> load (...use general register which storing length 2 let's said r1, r1 is specified in the load encoding)
> ....
>
> However, for RVV, we don't specify the length in the instructions encoding.
> Instead, we have only one VL register, and every time we want to change the length, we need"vsetvli"
>
> So for solution 1, we will have:
>
> max length = vsetvli (vf=8)
> length 1 = vsetlvi (vf=4)
> length 2 = max length = length 1
> ...
> vsetvli zero, length 1 <======insert by "VSETVL" PASS of RISC-V backend
> load....
> vsetvli zero, length 2 <======insert by "VSETVL" PASS of RISC-V backend
> load....
>
> "vsetlvi" instruction is the instruction much more expensive than the general scalar instruction (for example "min" is much cheaper than "vsetvli").
> So I am 100% sure that solution 3 (current MIN flow in GCC) is much better than above:
>
> max length = min (vf=8) ===> replaced "vsetli" by "min"
> length 1 = min (vf=4) ===> replaced "vsetli" by "min"
> length 2 = max length = length 1
> ...
> vsetvli zero, length 1 <======insert by "VSETVL" PASS of RISC-V backend
> load....
> vsetvli zero, length 2 <======insert by "VSETVL" PASS of RISC-V backend
> load....
Well, it depends on *why* the loop has a 2-control rgroup. There are two
possibilities:
(a) The riscv target has asked the vectoriser to unroll the loop 2 times
(via the unrolling hook). In this case there will be a 2-control rgroup
but no 1-control rgroup.
(b) The loop operates on a mixture of data element sizes and the loop
operates on fully-populated vectors. In that case, there will be
a 1-control rgroup for the narrowest element size and a 2-control
rgroup for the next widest element size.
Your example describes what would happen for (a), whereas I was thinking
about (b).
For (b), there would be three controls in total, even for solution 3.
So there would be three vsetvlis rather than two. That matches the
number of vsetvlis for solution 2.
When comparing solutions 2 and 3 for case (b), is solution 3 still better?
E.g. is "vsetvli zero" cheaper than "vsetvli <gpr>"?
Thanks,
Richard
Richard Sandiford <richard.sandiford@arm.com> writes:
> "juzhe.zhong@rivai.ai" <juzhe.zhong@rivai.ai> writes:
>> Hi, Richard. Thanks for the comments.
>>
>>>> If we use SELECT_VL to refer only to the target-independent ifn, I don't
>>>> see why this last bit is true.
>> Could you give me more details and information about this since I am not sure whether I catch up with you.
>> You mean the current SELECT_VL is not an appropriate IFN?
>
> No, I meant that the comment I quoted seemed to be saying that solution
> 3 wasn't possible. The comment seemed to say that we would need to do
> solution 1.
Sorry, I meant solution 2 rather than solution 3.
Hi, Richard.
>> No, I meant that the comment I quoted seemed to be saying that solution
>> 3 wasn't possible. The comment seemed to say that we would need to do
>> solution 1.
I am so sorry that I didn't write the comments accurately.
Could you help me with comments ? Base on what we have discussed above (I think we are on same page now).
Hmmm. I am not the native English speaker, I use google translator for comments :).
>> When comparing solutions 2 and 3 for case (b), is solution 3 still better?
>> E.g. is "vsetvli zero" cheaper than "vsetvli <gpr>"?
"vsetvli zero" is the same cost as "vsetvli gpr",
I think for (b), solution 2 and solution 3 should be almost the same.
juzhe.zhong@rivai.ai
From: Richard Sandiford
Date: 2023-06-05 15:57
To: juzhe.zhong\@rivai.ai
CC: gcc-patches; rguenther
Subject: Re: [PATCH V2] VECT: Add SELECT_VL support
Richard Sandiford <richard.sandiford@arm.com> writes:
> "juzhe.zhong@rivai.ai" <juzhe.zhong@rivai.ai> writes:
>> Hi, Richard. Thanks for the comments.
>>
>>>> If we use SELECT_VL to refer only to the target-independent ifn, I don't
>>>> see why this last bit is true.
>> Could you give me more details and information about this since I am not sure whether I catch up with you.
>> You mean the current SELECT_VL is not an appropriate IFN?
>
> No, I meant that the comment I quoted seemed to be saying that solution
> 3 wasn't possible. The comment seemed to say that we would need to do
> solution 1.
Sorry, I meant solution 2 rather than solution 3.
"juzhe.zhong@rivai.ai" <juzhe.zhong@rivai.ai> writes:
> Hi, Richard.
>
>>> No, I meant that the comment I quoted seemed to be saying that solution
>>> 3 wasn't possible. The comment seemed to say that we would need to do
>>> solution 1.
> I am so sorry that I didn't write the comments accurately.
> Could you help me with comments ? Base on what we have discussed above (I think we are on same page now).
Yeah, agree we seem to be on the same page
>>> When comparing solutions 2 and 3 for case (b), is solution 3 still better?
>>> E.g. is "vsetvli zero" cheaper than "vsetvli <gpr>"?
>
>
> "vsetvli zero" is the same cost as "vsetvli gpr",
>
> I think for (b), solution 2 and solution 3 should be almost the same.
OK, thanks. If we wanted to use solution 2 for (b), the condition
would be just:
LOOP_VINFO_LENS (loop_vinfo)[0].factor == 1
dropping the:
LOOP_VINFO_LENS (loop_vinfo).length () == 1
But it would make the pointer IV updates more complex. So let's
say that that's the reason for preferring solution 3.
So rather than:
+ /* If we're using decrement IV approach in loop control, we can use output of
+ SELECT_VL to adjust IV of loop control and data reference when it satisfies
+ the following checks:
+
+ (a) SELECT_VL is supported by the target.
+ (b) LOOP_VINFO is single-rgroup control.
+ (c) non-SLP.
+ (d) LOOP can not be unrolled.
+
+ Otherwise, we use MIN_EXPR approach.
+
+ 1. We only apply SELECT_VL on single-rgroup since:
+
+ (1). Multiple-rgroup controls N vector loads/stores would need N pointer
+ updates by variable amounts.
+ (2). SELECT_VL allows flexible length (<=VF) in each iteration.
+ (3). For decrement IV approach, we calculate the MAX length of the loop
+ and then deduce the length of each control from this MAX length.
+
+ Base on (1), (2) and (3) situations, if we try to use SELECT_VL on
+ multiple-rgroup control, we need to generate multiple SELECT_VL to
+ carefully adjust length of each control. Such approach is very inefficient
+ and unprofitable for targets that are using a standalone instruction
+ to configure the length of each operation.
+ E.g. RISC-V vector use 'vsetvl' to configure the length of each operation.
how about:
/* If a loop uses length controls and has a decrementing loop control IV,
we will normally pass that IV through a MIN_EXPR to calcaluate the
basis for the length controls. E.g. in a loop that processes one
element per scalar iteration, the number of elements would be
MIN_EXPR <N, VF>, where N is the number of scalar iterations left.
This MIN_EXPR approach allows us to use pointer IVs with an invariant
step, since only the final iteration of the vector loop can have
inactive lanes.
However, some targets have a dedicated instruction for calculating the
preferred length, given the total number of elements that still need to
be processed. This is encapsulated in the SELECT_VL internal function.
If the target supports SELECT_VL, we can use it instead of MIN_EXPR
to determine the basis for the length controls. However, unlike the
MIN_EXPR calculation, the SELECT_VL calculation can decide to make
lanes inactive in any iteration of the vector loop, not just the last
iteration. This SELECT_VL approach therefore requires us to use pointer
IVs with variable steps.
Once we've decided how many elements should be processed by one
iteration of the vector loop, we need to populate the rgroup controls.
If a loop has multiple rgroups, we need to make sure that those rgroups
"line up" (that is, they must be consistent about which elements are
active and which aren't). This is done by vect_adjust_loop_lens_control.
In principle, it would be possible to use vect_adjust_loop_lens_control
on either the result of a MIN_EXPR or the result of a SELECT_VL.
However:
(1) In practice, it only makes sense to use SELECT_VL when a vector
operation will be controlled directly by the result. It is not
worth using SELECT_VL if it would only be the input to other
calculations.
(2) If we use SELECT_VL for an rgroup that has N controls, each associated
pointer IV will need N updates by a variable amount (N-1 updates
within the iteration and 1 update to move to the next iteration).
Because of this, we prefer to use the MIN_EXPR approach whenever there
is more than one length control.
In addition, SELECT_VL always operates to a granularity of 1 unit.
If we wanted to use it to control an SLP operation on N consecutive
elements, we would need to make the SELECT_VL inputs measure scalar
iterations (rather than elements) and then multiply the SELECT_VL
result by N. But using SELECT_VL this way is inefficient because
of (1) above.
Thanks,
Richard
>> But it would make the pointer IV updates more complex. So let's
>> say that that's the reason for preferring solution 3.
Yes, I prefer pointer solution 3 to avoid complex IV updates and there is
no benefits in solution 2(unlike single-rgroup).
I read your comments, it's more comprehensive than I wrote.
I will send V3 patch with appending your comments.
Thanks you so much!
juzhe.zhong@rivai.ai
From: Richard Sandiford
Date: 2023-06-05 18:09
To: juzhe.zhong\@rivai.ai
CC: gcc-patches; rguenther
Subject: Re: [PATCH V2] VECT: Add SELECT_VL support
"juzhe.zhong@rivai.ai" <juzhe.zhong@rivai.ai> writes:
> Hi, Richard.
>
>>> No, I meant that the comment I quoted seemed to be saying that solution
>>> 3 wasn't possible. The comment seemed to say that we would need to do
>>> solution 1.
> I am so sorry that I didn't write the comments accurately.
> Could you help me with comments ? Base on what we have discussed above (I think we are on same page now).
Yeah, agree we seem to be on the same page
>>> When comparing solutions 2 and 3 for case (b), is solution 3 still better?
>>> E.g. is "vsetvli zero" cheaper than "vsetvli <gpr>"?
>
>
> "vsetvli zero" is the same cost as "vsetvli gpr",
>
> I think for (b), solution 2 and solution 3 should be almost the same.
OK, thanks. If we wanted to use solution 2 for (b), the condition
would be just:
LOOP_VINFO_LENS (loop_vinfo)[0].factor == 1
dropping the:
LOOP_VINFO_LENS (loop_vinfo).length () == 1
But it would make the pointer IV updates more complex. So let's
say that that's the reason for preferring solution 3.
So rather than:
+ /* If we're using decrement IV approach in loop control, we can use output of
+ SELECT_VL to adjust IV of loop control and data reference when it satisfies
+ the following checks:
+
+ (a) SELECT_VL is supported by the target.
+ (b) LOOP_VINFO is single-rgroup control.
+ (c) non-SLP.
+ (d) LOOP can not be unrolled.
+
+ Otherwise, we use MIN_EXPR approach.
+
+ 1. We only apply SELECT_VL on single-rgroup since:
+
+ (1). Multiple-rgroup controls N vector loads/stores would need N pointer
+ updates by variable amounts.
+ (2). SELECT_VL allows flexible length (<=VF) in each iteration.
+ (3). For decrement IV approach, we calculate the MAX length of the loop
+ and then deduce the length of each control from this MAX length.
+
+ Base on (1), (2) and (3) situations, if we try to use SELECT_VL on
+ multiple-rgroup control, we need to generate multiple SELECT_VL to
+ carefully adjust length of each control. Such approach is very inefficient
+ and unprofitable for targets that are using a standalone instruction
+ to configure the length of each operation.
+ E.g. RISC-V vector use 'vsetvl' to configure the length of each operation.
how about:
/* If a loop uses length controls and has a decrementing loop control IV,
we will normally pass that IV through a MIN_EXPR to calcaluate the
basis for the length controls. E.g. in a loop that processes one
element per scalar iteration, the number of elements would be
MIN_EXPR <N, VF>, where N is the number of scalar iterations left.
This MIN_EXPR approach allows us to use pointer IVs with an invariant
step, since only the final iteration of the vector loop can have
inactive lanes.
However, some targets have a dedicated instruction for calculating the
preferred length, given the total number of elements that still need to
be processed. This is encapsulated in the SELECT_VL internal function.
If the target supports SELECT_VL, we can use it instead of MIN_EXPR
to determine the basis for the length controls. However, unlike the
MIN_EXPR calculation, the SELECT_VL calculation can decide to make
lanes inactive in any iteration of the vector loop, not just the last
iteration. This SELECT_VL approach therefore requires us to use pointer
IVs with variable steps.
Once we've decided how many elements should be processed by one
iteration of the vector loop, we need to populate the rgroup controls.
If a loop has multiple rgroups, we need to make sure that those rgroups
"line up" (that is, they must be consistent about which elements are
active and which aren't). This is done by vect_adjust_loop_lens_control.
In principle, it would be possible to use vect_adjust_loop_lens_control
on either the result of a MIN_EXPR or the result of a SELECT_VL.
However:
(1) In practice, it only makes sense to use SELECT_VL when a vector
operation will be controlled directly by the result. It is not
worth using SELECT_VL if it would only be the input to other
calculations.
(2) If we use SELECT_VL for an rgroup that has N controls, each associated
pointer IV will need N updates by a variable amount (N-1 updates
within the iteration and 1 update to move to the next iteration).
Because of this, we prefer to use the MIN_EXPR approach whenever there
is more than one length control.
In addition, SELECT_VL always operates to a granularity of 1 unit.
If we wanted to use it to control an SLP operation on N consecutive
elements, we would need to make the SELECT_VL inputs measure scalar
iterations (rather than elements) and then multiply the SELECT_VL
result by N. But using SELECT_VL this way is inefficient because
of (1) above.
Thanks,
Richard
@@ -4974,6 +4974,28 @@ for (i = 1; i < operand3; i++)
operand0[i] = operand0[i - 1] && (operand1 + i < operand2);
@end smallexample
+@cindex @code{select_vl@var{m}} instruction pattern
+@item @code{select_vl@var{m}}
+Set operand 0 to the number of scalar iterations that should be handled
+by one iteration of a vector loop. Operand 1 is the total number of
+scalar iterations that the loop needs to process and operand 2 is a
+maximum bound on the result (also known as the maximum ``vectorization
+factor'').
+
+The maximum value of operand 0 is given by:
+@smallexample
+operand0 = MIN (operand1, operand2)
+@end smallexample
+However, targets might choose a lower value than this, based on
+target-specific criteria. Each iteration of the vector loop might
+therefore process a different number of scalar iterations, which in turn
+means that induction variables will have a variable step. Because of
+this, it is generally not useful to define this instruction if it will
+always calculate the maximum value.
+
+This optab is only useful on targets that implement @samp{len_load_@var{m}}
+and/or @samp{len_store_@var{m}}.
+
@cindex @code{check_raw_ptrs@var{m}} instruction pattern
@item @samp{check_raw_ptrs@var{m}}
Check whether, given two pointers @var{a} and @var{b} and a length @var{len},
@@ -153,6 +153,7 @@ DEF_INTERNAL_OPTAB_FN (VEC_SET, 0, vec_set, vec_set)
DEF_INTERNAL_OPTAB_FN (LEN_STORE, 0, len_store, len_store)
DEF_INTERNAL_OPTAB_FN (WHILE_ULT, ECF_CONST | ECF_NOTHROW, while_ult, while)
+DEF_INTERNAL_OPTAB_FN (SELECT_VL, ECF_CONST | ECF_NOTHROW, select_vl, binary)
DEF_INTERNAL_OPTAB_FN (CHECK_RAW_PTRS, ECF_CONST | ECF_NOTHROW,
check_raw_ptrs, check_ptrs)
DEF_INTERNAL_OPTAB_FN (CHECK_WAR_PTRS, ECF_CONST | ECF_NOTHROW,
@@ -476,3 +476,4 @@ OPTAB_DC (vec_series_optab, "vec_series$a", VEC_SERIES)
OPTAB_D (vec_shl_insert_optab, "vec_shl_insert_$a")
OPTAB_D (len_load_optab, "len_load_$a")
OPTAB_D (len_store_optab, "len_store_$a")
+OPTAB_D (select_vl_optab, "select_vl$a")
@@ -534,7 +534,7 @@ vect_set_loop_controls_directly (class loop *loop, loop_vec_info loop_vinfo,
_10 = (unsigned long) count_12(D);
...
# ivtmp_9 = PHI <ivtmp_35(6), _10(5)>
- _36 = MIN_EXPR <ivtmp_9, POLY_INT_CST [4, 4]>;
+ _36 = (MIN_EXPR | SELECT_VL) <ivtmp_9, POLY_INT_CST [4, 4]>;
...
vect__4.8_28 = .LEN_LOAD (_17, 32B, _36, 0);
...
@@ -549,15 +549,28 @@ vect_set_loop_controls_directly (class loop *loop, loop_vec_info loop_vinfo,
tree step = rgc->controls.length () == 1 ? rgc->controls[0]
: make_ssa_name (iv_type);
/* Create decrement IV. */
- create_iv (nitems_total, MINUS_EXPR, nitems_step, NULL_TREE, loop,
- &incr_gsi, insert_after, &index_before_incr,
- &index_after_incr);
- gimple_seq_add_stmt (header_seq, gimple_build_assign (step, MIN_EXPR,
- index_before_incr,
- nitems_step));
+ if (LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo))
+ {
+ create_iv (nitems_total, MINUS_EXPR, step, NULL_TREE, loop, &incr_gsi,
+ insert_after, &index_before_incr, &index_after_incr);
+ tree len = gimple_build (header_seq, IFN_SELECT_VL, iv_type,
+ index_before_incr, nitems_step);
+ gimple_seq_add_stmt (header_seq, gimple_build_assign (step, len));
+ }
+ else
+ {
+ create_iv (nitems_total, MINUS_EXPR, nitems_step, NULL_TREE, loop,
+ &incr_gsi, insert_after, &index_before_incr,
+ &index_after_incr);
+ gimple_seq_add_stmt (header_seq,
+ gimple_build_assign (step, MIN_EXPR,
+ index_before_incr,
+ nitems_step));
+ }
*iv_step = step;
*compare_step = nitems_step;
- return index_before_incr;
+ return LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo) ? index_after_incr
+ : index_before_incr;
}
/* Create increment IV. */
@@ -888,7 +901,8 @@ vect_set_loop_condition_partial_vectors (class loop *loop,
/* Get a boolean result that tells us whether to iterate. */
edge exit_edge = single_exit (loop);
gcond *cond_stmt;
- if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo))
+ if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo)
+ && !LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo))
{
gcc_assert (compare_step);
tree_code code = (exit_edge->flags & EDGE_TRUE_VALUE) ? LE_EXPR : GT_EXPR;
@@ -974,6 +974,7 @@ _loop_vec_info::_loop_vec_info (class loop *loop_in, vec_info_shared *shared)
can_use_partial_vectors_p (param_vect_partial_vector_usage != 0),
using_partial_vectors_p (false),
using_decrementing_iv_p (false),
+ using_select_vl_p (false),
epil_using_partial_vectors_p (false),
partial_load_store_bias (0),
peeling_for_gaps (false),
@@ -2737,6 +2738,53 @@ start_over:
LOOP_VINFO_VECT_FACTOR (loop_vinfo))))
LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo) = true;
+ /* If we're using decrement IV approach in loop control, we can use output of
+ SELECT_VL to adjust IV of loop control and data reference when it satisfies
+ the following checks:
+
+ (a) SELECT_VL is supported by the target.
+ (b) LOOP_VINFO is single-rgroup control.
+ (c) non-SLP.
+ (d) LOOP can not be unrolled.
+
+ Otherwise, we use MIN_EXPR approach.
+
+ 1. We only apply SELECT_VL on single-rgroup since:
+
+ (1). Multiple-rgroup controls N vector loads/stores would need N pointer
+ updates by variable amounts.
+ (2). SELECT_VL allows flexible length (<=VF) in each iteration.
+ (3). For decrement IV approach, we calculate the MAX length of the loop
+ and then deduce the length of each control from this MAX length.
+
+ Base on (1), (2) and (3) situations, if we try to use SELECT_VL on
+ multiple-rgroup control, we need to generate multiple SELECT_VL to
+ carefully adjust length of each control. Such approach is very inefficient
+ and unprofitable for targets that are using a standalone instruction
+ to configure the length of each operation.
+ E.g. RISC-V vector use 'vsetvl' to configure the length of each operation.
+
+ 2. We don't apply SELECT_VL on single-rgroup when both (1) and (2) are
+ satisfied:
+
+ (1). LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) is true.
+ (2). LOOP_VINFO_VECT_FACTOR (loop_vinfo).is_constant () is true.
+
+ Since SELECT_VL (variable step) will make SCEV analysis failed and then
+ we will fail to gain benefits of following unroll optimizations. We prefer
+ using the MIN_EXPR approach in this situation. */
+ if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo))
+ {
+ tree iv_type = LOOP_VINFO_RGROUP_IV_TYPE (loop_vinfo);
+ if (direct_internal_fn_supported_p (IFN_SELECT_VL, iv_type,
+ OPTIMIZE_FOR_SPEED)
+ && LOOP_VINFO_LENS (loop_vinfo).length () == 1
+ && LOOP_VINFO_LENS (loop_vinfo)[0].factor == 1 && !slp
+ && (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
+ || !LOOP_VINFO_VECT_FACTOR (loop_vinfo).is_constant ()))
+ LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo) = true;
+ }
+
/* If we're vectorizing an epilogue loop, the vectorized loop either needs
to be able to handle fewer than VF scalars, or needs to have a lower VF
than the main loop. */
@@ -3148,6 +3148,57 @@ vect_get_data_ptr_increment (vec_info *vinfo,
return iv_step;
}
+/* Prepare the pointer IVs which needs to be updated by a variable amount.
+ Such variable amount is the outcome of .SELECT_VL. In this case, we can
+ allow each iteration process the flexible number of elements as long as
+ the number <= vf elments.
+
+ Return data reference according to SELECT_VL.
+ If new statements are needed, insert them before GSI. */
+
+static tree
+get_select_vl_data_ref_ptr (vec_info *vinfo, stmt_vec_info stmt_info,
+ tree aggr_type, class loop *at_loop, tree offset,
+ tree *dummy, gimple_stmt_iterator *gsi,
+ bool simd_lane_access_p, vec_loop_lens *loop_lens,
+ dr_vec_info *dr_info,
+ vect_memory_access_type memory_access_type)
+{
+ loop_vec_info loop_vinfo = dyn_cast<loop_vec_info> (vinfo);
+ tree step = vect_dr_behavior (vinfo, dr_info)->step;
+
+ /* TODO: We don't support gather/scatter or load_lanes/store_lanes for pointer
+ IVs are updated by variable amount but we will support them in the future.
+ */
+ gcc_assert (memory_access_type != VMAT_GATHER_SCATTER
+ && memory_access_type != VMAT_LOAD_STORE_LANES);
+
+ /* When we support SELECT_VL pattern, we dynamic adjust
+ the memory address by .SELECT_VL result.
+
+ The result of .SELECT_VL is the number of elements to
+ be processed of each iteration. So the memory address
+ adjustment operation should be:
+
+ addr = addr + .SELECT_VL (ARG..) * step;
+ */
+ gimple *ptr_incr;
+ tree loop_len
+ = vect_get_loop_len (loop_vinfo, gsi, loop_lens, 1, aggr_type, 0, 0);
+ tree len_type = TREE_TYPE (loop_len);
+ /* Since the outcome of .SELECT_VL is element size, we should adjust
+ it into bytesize so that it can be used in address pointer variable
+ amount IVs adjustment. */
+ tree tmp = fold_build2 (MULT_EXPR, len_type, loop_len,
+ wide_int_to_tree (len_type, wi::to_widest (step)));
+ tree bump = make_temp_ssa_name (len_type, NULL, "ivtmp");
+ gassign *assign = gimple_build_assign (bump, tmp);
+ gsi_insert_before (gsi, assign, GSI_SAME_STMT);
+ return vect_create_data_ref_ptr (vinfo, stmt_info, aggr_type, at_loop, offset,
+ dummy, gsi, &ptr_incr, simd_lane_access_p,
+ bump);
+}
+
/* Check and perform vectorization of BUILT_IN_BSWAP{16,32,64,128}. */
static bool
@@ -8631,6 +8682,14 @@ vectorizable_store (vec_info *vinfo,
vect_get_gather_scatter_ops (loop_vinfo, loop, stmt_info,
slp_node, &gs_info, &dataref_ptr,
&vec_offsets);
+ else if (loop_lens && LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)
+ && memory_access_type != VMAT_INVARIANT)
+ dataref_ptr
+ = get_select_vl_data_ref_ptr (vinfo, stmt_info, aggr_type,
+ simd_lane_access_p ? loop : NULL,
+ offset, &dummy, gsi,
+ simd_lane_access_p, loop_lens,
+ dr_info, memory_access_type);
else
dataref_ptr
= vect_create_data_ref_ptr (vinfo, first_stmt_info, aggr_type,
@@ -10022,6 +10081,13 @@ vectorizable_load (vec_info *vinfo,
slp_node, &gs_info, &dataref_ptr,
&vec_offsets);
}
+ else if (loop_lens && LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)
+ && memory_access_type != VMAT_INVARIANT)
+ dataref_ptr
+ = get_select_vl_data_ref_ptr (vinfo, stmt_info, aggr_type,
+ at_loop, offset, &dummy, gsi,
+ simd_lane_access_p, loop_lens,
+ dr_info, memory_access_type);
else
dataref_ptr
= vect_create_data_ref_ptr (vinfo, first_stmt_info, aggr_type,
@@ -825,6 +825,11 @@ public:
(b) can iterate more than once. */
bool using_decrementing_iv_p;
+ /* True if we've decided to use output of select_vl to adjust IV of
+ both loop control and data reference pointer. This is only true
+ for single-rgroup control. */
+ bool using_select_vl_p;
+
/* True if we've decided to use partially-populated vectors for the
epilogue of loop. */
bool epil_using_partial_vectors_p;
@@ -898,6 +903,7 @@ public:
#define LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P(L) (L)->can_use_partial_vectors_p
#define LOOP_VINFO_USING_PARTIAL_VECTORS_P(L) (L)->using_partial_vectors_p
#define LOOP_VINFO_USING_DECREMENTING_IV_P(L) (L)->using_decrementing_iv_p
+#define LOOP_VINFO_USING_SELECT_VL_P(L) (L)->using_select_vl_p
#define LOOP_VINFO_EPIL_USING_PARTIAL_VECTORS_P(L) \
(L)->epil_using_partial_vectors_p
#define LOOP_VINFO_PARTIAL_LOAD_STORE_BIAS(L) (L)->partial_load_store_bias