* [PATCH] RISC-V: Fix wrong tune parameters on int_div
@ 2023-10-26 18:50 Yangyu Chen
2023-10-27 7:49 ` Robin Dapp
2023-10-27 14:44 ` Jeff Law
0 siblings, 2 replies; 9+ messages in thread
From: Yangyu Chen @ 2023-10-26 18:50 UTC (permalink / raw)
To: gcc-patches; +Cc: kito.cheng, palmer, andrew, jim.wilson.gcc, Yangyu Chen
This patch fixes an issue with the cost on "int_div" in various RISC-V
tune parameters including those for Rocket, SiFive U7 series, and T-Head
C906. This incorrect cost value interferes with the optimization process.
For example, it prevents the optimization of division by a constant to a
more efficient method known as Barrett reduction. This lack of
optimization negatively affects the performance of these systems.
The integer div cost of the Rocket and SiFive U7 is taken from the
Rocket-Chip Divider source code[1] with BigCore configuration[2]. It shows
the divUnroll unchanged which is 1 by default. Thus, the maximum int_div
cycles should be the dataWidth + 1, which is 33 for 32-bit and 65 for
64-bit.
As for C906, the divider takes 2 cycle to start[3], and it produce 2-bit
result each cycle[4]. Thus, the maximum int_div cycles should be the
dataWidth / 2 + 2, which is 18 for 32-bit and 34 for 64-bit.
I also test the performance on VisionFive2 which has Qual-Core Sifive U74.
I write a simple C program to do 1e8 times div by constant 6 in int32. The
result shows it takes 1.998s using div, and 0.420s using barrett reduction
to replace div with mul, which is 4.75x faster.
[1] https://github.com/chipsalliance/rocket-chip/blob/v1.6/src/main/scala/rocket/Multiplier.scala#L40
[2] https://github.com/chipsalliance/rocket-chip/blob/v1.6/src/main/scala/subsystem/Configs.scala#L97
[3] https://github.com/T-head-Semi/openc906/blob/af5614d72de7e5a4b8609c427d2e20af1deb21c4/C906_RTL_FACTORY/gen_rtl/iu/rtl/aq_iu_div.v#L267
[4] https://github.com/T-head-Semi/openc906/blob/af5614d72de7e5a4b8609c427d2e20af1deb21c4/C906_RTL_FACTORY/gen_rtl/iu/rtl/aq_iu_div_shift2_kernel.v#L93
gcc/ChangeLog:
* config/riscv/riscv.cc: Fix wrong tune parameters on int_div
Signed-off-by: Yangyu Chen <chenyangyu@isrc.iscas.ac.cn>
---
gcc/config/riscv/riscv.cc | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/gcc/config/riscv/riscv.cc b/gcc/config/riscv/riscv.cc
index f2dcb0db6fb..ca9a2ca81d5 100644
--- a/gcc/config/riscv/riscv.cc
+++ b/gcc/config/riscv/riscv.cc
@@ -346,7 +346,7 @@ static const struct riscv_tune_param rocket_tune_info = {
{COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
{COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
{COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
- {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
+ {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
1, /* issue_rate */
3, /* branch_cost */
5, /* memory_cost */
@@ -361,7 +361,7 @@ static const struct riscv_tune_param sifive_7_tune_info = {
{COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
{COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
{COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
- {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
+ {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
2, /* issue_rate */
4, /* branch_cost */
3, /* memory_cost */
@@ -376,7 +376,7 @@ static const struct riscv_tune_param thead_c906_tune_info = {
{COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
{COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
{COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
- {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
+ {COSTS_N_INSNS (18), COSTS_N_INSNS (34)}, /* int_div */
1, /* issue_rate */
3, /* branch_cost */
5, /* memory_cost */
--
2.42.0
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] RISC-V: Fix wrong tune parameters on int_div
2023-10-26 18:50 [PATCH] RISC-V: Fix wrong tune parameters on int_div Yangyu Chen
@ 2023-10-27 7:49 ` Robin Dapp
2023-10-27 13:55 ` Jeff Law
2023-10-27 14:44 ` Jeff Law
1 sibling, 1 reply; 9+ messages in thread
From: Robin Dapp @ 2023-10-27 7:49 UTC (permalink / raw)
To: Yangyu Chen, gcc-patches
Cc: rdapp.gcc, kito.cheng, palmer, andrew, jim.wilson.gcc
> @@ -346,7 +346,7 @@ static const struct riscv_tune_param rocket_tune_info = {
> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
> + {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
> 1, /* issue_rate */
> 3, /* branch_cost */
> 5, /* memory_cost */
> @@ -361,7 +361,7 @@ static const struct riscv_tune_param sifive_7_tune_info = {
> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
> + {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
> 2, /* issue_rate */
> 4, /* branch_cost */
> 3, /* memory_cost */
> @@ -376,7 +376,7 @@ static const struct riscv_tune_param thead_c906_tune_info = {
> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
> + {COSTS_N_INSNS (18), COSTS_N_INSNS (34)}, /* int_div */
> 1, /* issue_rate */
> 3, /* branch_cost */
> 5, /* memory_cost */
Instruction costs don't really correspond to latencies even though
sometimes they are used as if they were. I'm a bit wary of using
e.g. 65 which would disparage each use of an integer division inside
a sequence.
Could you check which costs we need in order to still emit your wanted
sequence? Maybe we can use values a bit lower than yours and still
get the proper code. Where is the decision being made actually?
Regards
Robin
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] RISC-V: Fix wrong tune parameters on int_div
2023-10-27 7:49 ` Robin Dapp
@ 2023-10-27 13:55 ` Jeff Law
2023-10-27 17:21 ` Andrew Waterman
0 siblings, 1 reply; 9+ messages in thread
From: Jeff Law @ 2023-10-27 13:55 UTC (permalink / raw)
To: Robin Dapp, Yangyu Chen, gcc-patches
Cc: kito.cheng, palmer, andrew, jim.wilson.gcc
On 10/27/23 01:49, Robin Dapp wrote:
>> @@ -346,7 +346,7 @@ static const struct riscv_tune_param rocket_tune_info = {
>> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
>> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
>> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
>> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
>> + {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
>> 1, /* issue_rate */
>> 3, /* branch_cost */
>> 5, /* memory_cost */
>> @@ -361,7 +361,7 @@ static const struct riscv_tune_param sifive_7_tune_info = {
>> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
>> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
>> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
>> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
>> + {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
>> 2, /* issue_rate */
>> 4, /* branch_cost */
>> 3, /* memory_cost */
>> @@ -376,7 +376,7 @@ static const struct riscv_tune_param thead_c906_tune_info = {
>> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
>> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
>> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
>> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
>> + {COSTS_N_INSNS (18), COSTS_N_INSNS (34)}, /* int_div */
>> 1, /* issue_rate */
>> 3, /* branch_cost */
>> 5, /* memory_cost */
>
> Instruction costs don't really correspond to latencies even though
> sometimes they are used as if they were. I'm a bit wary of using
> e.g. 65 which would disparage each use of an integer division inside
> a sequence.
>
> Could you check which costs we need in order to still emit your wanted
> sequence? Maybe we can use values a bit lower than yours and still
> get the proper code. Where is the decision being made actually?
The main use of costing of a div/mod instruction is to guide the
reciprocal division code when dividing by a constant. In that context
we're comparing costs against a sequence of multiplies, shifts, add/sub
insns which are almost always costed by their latency. So using latency
for division is a reasonable place to start.
The other thing that might be worth investigating for those processors
would be to set "use_divmod_expansion" in the cost structure. I've
heard talk of fusing div/mod into divmod, though I'm not aware of any
part implementing that fusion (from a prior life, that would seem to
require a 2nd output port on the integer unit which could be highly
undesirable). Anyway, this could be a followup item for Yangyu if it
looks profitable.
jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] RISC-V: Fix wrong tune parameters on int_div
2023-10-26 18:50 [PATCH] RISC-V: Fix wrong tune parameters on int_div Yangyu Chen
2023-10-27 7:49 ` Robin Dapp
@ 2023-10-27 14:44 ` Jeff Law
1 sibling, 0 replies; 9+ messages in thread
From: Jeff Law @ 2023-10-27 14:44 UTC (permalink / raw)
To: Yangyu Chen, gcc-patches; +Cc: kito.cheng, palmer, andrew, jim.wilson.gcc
On 10/26/23 12:50, Yangyu Chen wrote:
> This patch fixes an issue with the cost on "int_div" in various RISC-V
> tune parameters including those for Rocket, SiFive U7 series, and T-Head
> C906. This incorrect cost value interferes with the optimization process.
> For example, it prevents the optimization of division by a constant to a
> more efficient method known as Barrett reduction. This lack of
> optimization negatively affects the performance of these systems.
>
> The integer div cost of the Rocket and SiFive U7 is taken from the
> Rocket-Chip Divider source code[1] with BigCore configuration[2]. It shows
> the divUnroll unchanged which is 1 by default. Thus, the maximum int_div
> cycles should be the dataWidth + 1, which is 33 for 32-bit and 65 for
> 64-bit.
>
> As for C906, the divider takes 2 cycle to start[3], and it produce 2-bit
> result each cycle[4]. Thus, the maximum int_div cycles should be the
> dataWidth / 2 + 2, which is 18 for 32-bit and 34 for 64-bit.
>
> I also test the performance on VisionFive2 which has Qual-Core Sifive U74.
> I write a simple C program to do 1e8 times div by constant 6 in int32. The
> result shows it takes 1.998s using div, and 0.420s using barrett reduction
> to replace div with mul, which is 4.75x faster.
>
> [1] https://github.com/chipsalliance/rocket-chip/blob/v1.6/src/main/scala/rocket/Multiplier.scala#L40
> [2] https://github.com/chipsalliance/rocket-chip/blob/v1.6/src/main/scala/subsystem/Configs.scala#L97
> [3] https://github.com/T-head-Semi/openc906/blob/af5614d72de7e5a4b8609c427d2e20af1deb21c4/C906_RTL_FACTORY/gen_rtl/iu/rtl/aq_iu_div.v#L267
> [4] https://github.com/T-head-Semi/openc906/blob/af5614d72de7e5a4b8609c427d2e20af1deb21c4/C906_RTL_FACTORY/gen_rtl/iu/rtl/aq_iu_div_shift2_kernel.v#L93
>
> gcc/ChangeLog:
>
> * config/riscv/riscv.cc: Fix wrong tune parameters on int_div
>
> Signed-off-by: Yangyu Chen <chenyangyu@isrc.iscas.ac.cn>
I adjusted the ChangeLog entry and pushed this to the trunk.
As a follow-up you should look at the tuning parameter which controls
using the divmod expansion. If these uarchs don't do div+mod fusion,
then I should strongly suspect that they'll benefit from using the
divmod expansion path when we need a/b and a%b.
Jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] RISC-V: Fix wrong tune parameters on int_div
2023-10-27 13:55 ` Jeff Law
@ 2023-10-27 17:21 ` Andrew Waterman
0 siblings, 0 replies; 9+ messages in thread
From: Andrew Waterman @ 2023-10-27 17:21 UTC (permalink / raw)
To: Jeff Law
Cc: Robin Dapp, Yangyu Chen, gcc-patches, kito.cheng, palmer, jim.wilson.gcc
On Fri, Oct 27, 2023 at 6:55 AM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 10/27/23 01:49, Robin Dapp wrote:
> >> @@ -346,7 +346,7 @@ static const struct riscv_tune_param rocket_tune_info = {
> >> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
> >> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
> >> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
> >> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
> >> + {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
> >> 1, /* issue_rate */
> >> 3, /* branch_cost */
> >> 5, /* memory_cost */
> >> @@ -361,7 +361,7 @@ static const struct riscv_tune_param sifive_7_tune_info = {
> >> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
> >> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
> >> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
> >> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
> >> + {COSTS_N_INSNS (33), COSTS_N_INSNS (65)}, /* int_div */
> >> 2, /* issue_rate */
> >> 4, /* branch_cost */
> >> 3, /* memory_cost */
> >> @@ -376,7 +376,7 @@ static const struct riscv_tune_param thead_c906_tune_info = {
> >> {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */
> >> {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */
> >> {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */
> >> - {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */
> >> + {COSTS_N_INSNS (18), COSTS_N_INSNS (34)}, /* int_div */
> >> 1, /* issue_rate */
> >> 3, /* branch_cost */
> >> 5, /* memory_cost */
> >
> > Instruction costs don't really correspond to latencies even though
> > sometimes they are used as if they were. I'm a bit wary of using
> > e.g. 65 which would disparage each use of an integer division inside
> > a sequence.
> >
> > Could you check which costs we need in order to still emit your wanted
> > sequence? Maybe we can use values a bit lower than yours and still
> > get the proper code. Where is the decision being made actually?
> The main use of costing of a div/mod instruction is to guide the
> reciprocal division code when dividing by a constant. In that context
> we're comparing costs against a sequence of multiplies, shifts, add/sub
> insns which are almost always costed by their latency. So using latency
> for division is a reasonable place to start.
>
> The other thing that might be worth investigating for those processors
> would be to set "use_divmod_expansion" in the cost structure. I've
> heard talk of fusing div/mod into divmod, though I'm not aware of any
> part implementing that fusion
I'm also unaware of existing implementations that fuse these
operations; div + mul + sub is probably best for most uarches...
> (from a prior life, that would seem to
> require a 2nd output port on the integer unit which could be highly
> undesirable).
...but it can be done more cheaply than this, so I wouldn't foreclose
on the possibility. Nevertheless, future work, as you say.
> Anyway, this could be a followup item for Yangyu if it
> looks profitable.
>
> jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] RISC-V: Fix wrong tune parameters on int_div
2023-10-27 17:39 ` Andrew Waterman
@ 2023-10-27 17:44 ` Jeff Law
0 siblings, 0 replies; 9+ messages in thread
From: Jeff Law @ 2023-10-27 17:44 UTC (permalink / raw)
To: Andrew Waterman
Cc: juzhe.zhong, gcc-patches, kito.cheng, Kito.cheng, chenyangyu
On 10/27/23 11:39, Andrew Waterman wrote:
> On Fri, Oct 27, 2023 at 6:44 AM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>
>>
>>
>> On 10/27/23 01:37, juzhe.zhong@rivai.ai wrote:
>>> LGTM from my side.
>>>
>>> The original integer division COST seems too low.
>> Almost certainly, though there may be good reasons why it was initially
>> set so low. I'm generally hesitant to change things like that without
>> either someone with knowledge of the code/uarch stepping in with a
>> recommendation or some kind of analysis showing their wrong.
>
> It is probably just a bug, as the cores I'm familiar with mentioned in
> the original post do benefit from converting division by constant into
> multiplication. (We should make sure we continue emitting a division
> instruction when optimizing for size, though.)
Yes. When optimizing for size we have a special tune info which
explicitly turns off the divmod expansion.
jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] RISC-V: Fix wrong tune parameters on int_div
2023-10-27 13:44 ` Jeff Law
@ 2023-10-27 17:39 ` Andrew Waterman
2023-10-27 17:44 ` Jeff Law
0 siblings, 1 reply; 9+ messages in thread
From: Andrew Waterman @ 2023-10-27 17:39 UTC (permalink / raw)
To: Jeff Law; +Cc: juzhe.zhong, gcc-patches, kito.cheng, Kito.cheng, chenyangyu
On Fri, Oct 27, 2023 at 6:44 AM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 10/27/23 01:37, juzhe.zhong@rivai.ai wrote:
> > LGTM from my side.
> >
> > The original integer division COST seems too low.
> Almost certainly, though there may be good reasons why it was initially
> set so low. I'm generally hesitant to change things like that without
> either someone with knowledge of the code/uarch stepping in with a
> recommendation or some kind of analysis showing their wrong.
It is probably just a bug, as the cores I'm familiar with mentioned in
the original post do benefit from converting division by constant into
multiplication. (We should make sure we continue emitting a division
instruction when optimizing for size, though.)
>
> >
> > Hi, Jeff and Kito. Could take a look at this patch ?
> It's on the list.
>
> jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] RISC-V: Fix wrong tune parameters on int_div
2023-10-27 7:37 juzhe.zhong
@ 2023-10-27 13:44 ` Jeff Law
2023-10-27 17:39 ` Andrew Waterman
0 siblings, 1 reply; 9+ messages in thread
From: Jeff Law @ 2023-10-27 13:44 UTC (permalink / raw)
To: juzhe.zhong, gcc-patches; +Cc: kito.cheng, Kito.cheng, chenyangyu
On 10/27/23 01:37, juzhe.zhong@rivai.ai wrote:
> LGTM from my side.
>
> The original integer division COST seems too low.
Almost certainly, though there may be good reasons why it was initially
set so low. I'm generally hesitant to change things like that without
either someone with knowledge of the code/uarch stepping in with a
recommendation or some kind of analysis showing their wrong.
>
> Hi, Jeff and Kito. Could take a look at this patch ?
It's on the list.
jeff
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH] RISC-V: Fix wrong tune parameters on int_div
@ 2023-10-27 7:37 juzhe.zhong
2023-10-27 13:44 ` Jeff Law
0 siblings, 1 reply; 9+ messages in thread
From: juzhe.zhong @ 2023-10-27 7:37 UTC (permalink / raw)
To: gcc-patches; +Cc: kito.cheng, Kito.cheng, jeffreyalaw, chenyangyu
[-- Attachment #1: Type: text/plain, Size: 168 bytes --]
LGTM from my side.
The original integer division COST seems too low.
Hi, Jeff and Kito. Could take a look at this patch ?
Thanks.
juzhe.zhong@rivai.ai
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2023-10-27 17:44 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-10-26 18:50 [PATCH] RISC-V: Fix wrong tune parameters on int_div Yangyu Chen
2023-10-27 7:49 ` Robin Dapp
2023-10-27 13:55 ` Jeff Law
2023-10-27 17:21 ` Andrew Waterman
2023-10-27 14:44 ` Jeff Law
2023-10-27 7:37 juzhe.zhong
2023-10-27 13:44 ` Jeff Law
2023-10-27 17:39 ` Andrew Waterman
2023-10-27 17:44 ` Jeff Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).