Re: [RFC] Implementing detection of saturation and rounding arithmetic
Hi Bin,
Thank you for the reply, I have some questions, see below.
On 07/06/2021 12:28, Bin.Cheng wrote:
On Fri, Jun 4, 2021 at 12:35 AM Andre Vieira (lists) via Gcc-patches
wrote:
Hi Andre,
I didn't look into the details of the IV sharing RFC. It seems to me
costing outside uses is trying to generate better code for later code
(epilogue loop here). The only problem is IVOPTs doesn't know that
the outside use is not in the final form - which will be transformed
by IVOPTs again.
I think this example is not good at describing your problem because it
shows exactly that considering outside use results in better code,
compared to the other two approaches.
I don't quite understand what you are saying here :( What do you mean by
final form? It seems to me that costing uses inside and outside loop the
same way is wrong because calculating the IV inside the loop has to be
done every iteration, whereas if you can resolve it to a single update
(without an IV) then you can sink it outside the loop. This is why I
think this example shows why we need to cost these uses differently.
2) Is there a cleaner way to generate the optimal 'post-increment' use
for the outside-use variable? I first thought the position in the
candidate might be something I could use or even the var_at_stmt
functionality, but the outside IV has the actual increment of the
variable as it's use, rather than the outside uses. This is this RFC's
main weakness I find.
To answer why IVOPTs behaves like this w/o your two patches. The main
problem is the point IVOPTs rewrites outside use IV - I don't remember
the exact point - but looks like at the end of loop while before
incrementing instruction of main IV. It's a known issue that outside
use should be costed/re-written on the exit edge along which its value
flows out of loop. I had a patch a long time ago but discarded it,
because it didn't bring obvious improvement and is complicated in case
of multi-exit edges.
Yeah I haven't looked at multi-exit edges and I understand that
complicates things. But for now we could disable the special casing of
outside uses when dealing with multi-exit loops and keep the current
behavior.
But in general, I am less convinced that any of the two patches is the
right direction solving IV sharing issue between vectorized loop and
epilogue loop. I would need to read the previous RFC before giving
further comments though.
The previous RFC still has a lot of unanswered questions too, but
regardless of that, take the following (non-vectorizer) example:
#include
#include
void bar (char * __restrict__ a, char * __restrict__ b, char *
__restrict__ c, unsigned long long n)
{
svbool_t all_true = svptrue_b8 ();
unsigned long long i = 0;
for (; i < (n & ~(svcntb() - 1)); i += svcntb()) {
svuint8_t va = svld1 (all_true, (uint8_t*)a);
svuint8_t vb = svld1 (all_true, (uint8_t*)b);
svst1 (all_true, (uint8_t *)c, svadd_z (all_true, va,vb));
a += svcntb();
b += svcntb();
c += svcntb();
}
svbool_t pred;
for (; i < (n); i += svcntb()) {
pred = svwhilelt_b8 (i, n);
svuint8_t va = svld1 (pred, (uint8_t*)a);
svuint8_t vb = svld1 (pred, (uint8_t*)b);
svst1 (pred, (uint8_t *)c, svadd_z (pred, va,vb));
a += svcntb();
b += svcntb();
c += svcntb();
}
Current IVOPTs will use 4 iterators for the first loop, when it could do
with just 1. In fact, if you use my patches it will create just a single
IV and sink the uses and it is then able to merge them with loads &
stores of the next loop.
I am not saying setting outside costs to 0 is the right thing to do by
the way. It is absolutely not! It will break cost considerations for
other cases. Like I said above I've been playing around with using
'!use->outside' as a multiplier for the cost. Unfortunately it won't
help with the case above, because this seems to choose 'infinite_cost'
because the candidate IV has a lower precision than the use IV. I don't
quite understand yet how candidates are created, but something I'm going
to try to look at. Just wanted to show this as an example of how IVOPTs
would not improve code with multiple loops that don't involve the
vectorizer.
BR,
Andre
Thanks,
bin
Re: [RFC] Implementing detection of saturation and rounding arithmetic
On Fri, Jun 4, 2021 at 12:35 AM Andre Vieira (lists) via Gcc-patches
wrote:
>
> Hi,
>
> This RFC is motivated by the IV sharing RFC in
> https://gcc.gnu.org/pipermail/gcc-patches/2021-May/569502.html and the
> need to have the IVOPTS pass be able to clean up IV's shared between
> multiple loops. When creating a similar problem with C code I noticed
> IVOPTs treated IV's with uses outside the loop differently, this didn't
> even required multiple loops, take for instance the following example
> using SVE intrinsics:
>
> #include
> #include
> extern void use (char *);
> void bar (char * __restrict__ a, char * __restrict__ b, char *
> __restrict__ c, unsigned n)
> {
> svbool_t all_true = svptrue_b8 ();
>unsigned i = 0;
>if (n < (UINT_MAX - svcntb() - 1))
> {
> for (; i < n; i += svcntb())
> {
> svuint8_t va = svld1 (all_true, (uint8_t*)a);
> svuint8_t vb = svld1 (all_true, (uint8_t*)b);
> svst1 (all_true, (uint8_t *)c, svadd_z (all_true, va,vb));
> a += svcntb();
> b += svcntb();
> c += svcntb();
> }
> }
>use (a);
> }
>
> IVOPTs tends to generate a shared IV for SVE memory accesses, as we
> don't have a post-increment for SVE load/stores. If we had not included
> 'use (a);' in this example, IVOPTs would have replaced the IV's for a, b
> and c with a single one, (also used for the loop-control). See:
>
> [local count: 955630225]:
># ivtmp.7_8 = PHI
>va_14 = MEM [(unsigned char *)a_10(D) + ivtmp.7_8 * 1];
>vb_15 = MEM [(unsigned char *)b_11(D) + ivtmp.7_8 * 1];
>_2 = svadd_u8_z ({ -1, ... }, va_14, vb_15);
>MEM <__SVUint8_t> [(unsigned char *)c_12(D) + ivtmp.7_8 * 1] = _2;
>ivtmp.7_25 = ivtmp.7_8 + POLY_INT_CST [16, 16];
>i_23 = (unsigned int) ivtmp.7_25;
>if (n_9(D) > i_23)
> goto ; [89.00%]
>else
> goto ; [11.00%]
>
> However, due to the 'use (a);' it will create two IVs one for
> loop-control, b and c and one for a. See:
>
>[local count: 955630225]:
># a_28 = PHI
># ivtmp.7_25 = PHI
>va_15 = MEM [(unsigned char *)a_28];
>vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
>_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
>MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
>a_18 = a_28 + POLY_INT_CST [16, 16];
>ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
>i_8 = (unsigned int) ivtmp.7_24;
>if (n_10(D) > i_8)
> goto ; [89.00%]
>else
> goto ; [11.00%]
>
> With the first patch attached in this RFC 'no_cost.patch', I tell IVOPTs
> to not cost uses outside of the loop. This makes IVOPTs generate a
> single IV, but unfortunately it decides to create the variable for the
> use inside the loop and it also seems to use the pre-increment value of
> the shared-IV and add the [16,16] to it. See:
>
> [local count: 955630225]:
># ivtmp.7_25 = PHI
>va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
>vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
>_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
>MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
>_8 = (unsigned long) a_11(D);
>_7 = _8 + ivtmp.7_25;
>_6 = _7 + POLY_INT_CST [16, 16];
>a_18 = (char * restrict) _6;
>ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
>i_5 = (unsigned int) ivtmp.7_24;
>if (n_10(D) > i_5)
> goto ; [89.00%]
>else
> goto ; [11.00%]
>
> With the patch 'var_after.patch' I make get_computation_aff_1 use
> 'cand->var_after' for outside uses thus using the post-increment var of
> the candidate IV. This means I have to insert it in a different place
> and make sure to delete the old use->stmt. I'm sure there is a better
> way to do this using IVOPTs current framework, but I didn't find one
> yet. See the result:
>
>[local count: 955630225]:
># ivtmp.7_25 = PHI
>va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
>vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
>_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
>MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
>ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
>_8 = (unsigned long) a_11(D);
>_7 = _8 + ivtmp.7_24;
>a_18 = (char * restrict) _7;
>i_6 = (unsigned int) ivtmp.7_24;
>if (n_10(D) > i_6)
> goto ; [89.00%]
>else
> goto ; [11.00%]
>
>
> This is still not optimal as we are still doing the update inside the
> loop and there is absolutely no need for that. I found that running sink
> would solve it and it seems someone has added a second sink pass, so
> that saves me a third patch :) see after sink2:
>
> [local count: 955630225]:
># ivtmp.7_25 = PHI
>va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
>vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
>_2 = svadd_u8_z ({ -1, ... },
[RFC][ivopts] Generate better code for IVs with uses outside the loop (was Re: [RFC] Implementing detection of saturation and rounding arithmetic)
Streams got crossed there and used the wrong subject ...
On 03/06/2021 17:34, Andre Vieira (lists) via Gcc-patches wrote:
Hi,
This RFC is motivated by the IV sharing RFC in
https://gcc.gnu.org/pipermail/gcc-patches/2021-May/569502.html and the
need to have the IVOPTS pass be able to clean up IV's shared between
multiple loops. When creating a similar problem with C code I noticed
IVOPTs treated IV's with uses outside the loop differently, this
didn't even required multiple loops, take for instance the following
example using SVE intrinsics:
#include
#include
extern void use (char *);
void bar (char * __restrict__ a, char * __restrict__ b, char *
__restrict__ c, unsigned n)
{
svbool_t all_true = svptrue_b8 ();
unsigned i = 0;
if (n < (UINT_MAX - svcntb() - 1))
{
for (; i < n; i += svcntb())
{
svuint8_t va = svld1 (all_true, (uint8_t*)a);
svuint8_t vb = svld1 (all_true, (uint8_t*)b);
svst1 (all_true, (uint8_t *)c, svadd_z (all_true,
va,vb));
a += svcntb();
b += svcntb();
c += svcntb();
}
}
use (a);
}
IVOPTs tends to generate a shared IV for SVE memory accesses, as we
don't have a post-increment for SVE load/stores. If we had not
included 'use (a);' in this example, IVOPTs would have replaced the
IV's for a, b and c with a single one, (also used for the
loop-control). See:
[local count: 955630225]:
# ivtmp.7_8 = PHI
va_14 = MEM [(unsigned char *)a_10(D) + ivtmp.7_8 * 1];
vb_15 = MEM [(unsigned char *)b_11(D) + ivtmp.7_8 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_14, vb_15);
MEM <__SVUint8_t> [(unsigned char *)c_12(D) + ivtmp.7_8 * 1] = _2;
ivtmp.7_25 = ivtmp.7_8 + POLY_INT_CST [16, 16];
i_23 = (unsigned int) ivtmp.7_25;
if (n_9(D) > i_23)
goto ; [89.00%]
else
goto ; [11.00%]
However, due to the 'use (a);' it will create two IVs one for
loop-control, b and c and one for a. See:
[local count: 955630225]:
# a_28 = PHI
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_28];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
a_18 = a_28 + POLY_INT_CST [16, 16];
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
i_8 = (unsigned int) ivtmp.7_24;
if (n_10(D) > i_8)
goto ; [89.00%]
else
goto ; [11.00%]
With the first patch attached in this RFC 'no_cost.patch', I tell
IVOPTs to not cost uses outside of the loop. This makes IVOPTs
generate a single IV, but unfortunately it decides to create the
variable for the use inside the loop and it also seems to use the
pre-increment value of the shared-IV and add the [16,16] to it. See:
[local count: 955630225]:
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
_8 = (unsigned long) a_11(D);
_7 = _8 + ivtmp.7_25;
_6 = _7 + POLY_INT_CST [16, 16];
a_18 = (char * restrict) _6;
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
i_5 = (unsigned int) ivtmp.7_24;
if (n_10(D) > i_5)
goto ; [89.00%]
else
goto ; [11.00%]
With the patch 'var_after.patch' I make get_computation_aff_1 use
'cand->var_after' for outside uses thus using the post-increment var
of the candidate IV. This means I have to insert it in a different
place and make sure to delete the old use->stmt. I'm sure there is a
better way to do this using IVOPTs current framework, but I didn't
find one yet. See the result:
[local count: 955630225]:
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
_8 = (unsigned long) a_11(D);
_7 = _8 + ivtmp.7_24;
a_18 = (char * restrict) _7;
i_6 = (unsigned int) ivtmp.7_24;
if (n_10(D) > i_6)
goto ; [89.00%]
else
goto ; [11.00%]
This is still not optimal as we are still doing the update inside the
loop and there is absolutely no need for that. I found that running
sink would solve it and it seems someone has added a second sink pass,
so that saves me a third patch :) see after sink2:
[local count: 955630225]:
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
i_6 = (unsigned int) ivtmp.7_24;
if (i_6 < n_10(D))
goto ; [89.00%]
else
goto ; [11.00%]
[RFC] Implementing detection of saturation and rounding arithmetic
Hi,
This RFC is motivated by the IV sharing RFC in
https://gcc.gnu.org/pipermail/gcc-patches/2021-May/569502.html and the
need to have the IVOPTS pass be able to clean up IV's shared between
multiple loops. When creating a similar problem with C code I noticed
IVOPTs treated IV's with uses outside the loop differently, this didn't
even required multiple loops, take for instance the following example
using SVE intrinsics:
#include
#include
extern void use (char *);
void bar (char * __restrict__ a, char * __restrict__ b, char *
__restrict__ c, unsigned n)
{
svbool_t all_true = svptrue_b8 ();
unsigned i = 0;
if (n < (UINT_MAX - svcntb() - 1))
{
for (; i < n; i += svcntb())
{
svuint8_t va = svld1 (all_true, (uint8_t*)a);
svuint8_t vb = svld1 (all_true, (uint8_t*)b);
svst1 (all_true, (uint8_t *)c, svadd_z (all_true, va,vb));
a += svcntb();
b += svcntb();
c += svcntb();
}
}
use (a);
}
IVOPTs tends to generate a shared IV for SVE memory accesses, as we
don't have a post-increment for SVE load/stores. If we had not included
'use (a);' in this example, IVOPTs would have replaced the IV's for a, b
and c with a single one, (also used for the loop-control). See:
[local count: 955630225]:
# ivtmp.7_8 = PHI
va_14 = MEM [(unsigned char *)a_10(D) + ivtmp.7_8 * 1];
vb_15 = MEM [(unsigned char *)b_11(D) + ivtmp.7_8 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_14, vb_15);
MEM <__SVUint8_t> [(unsigned char *)c_12(D) + ivtmp.7_8 * 1] = _2;
ivtmp.7_25 = ivtmp.7_8 + POLY_INT_CST [16, 16];
i_23 = (unsigned int) ivtmp.7_25;
if (n_9(D) > i_23)
goto ; [89.00%]
else
goto ; [11.00%]
However, due to the 'use (a);' it will create two IVs one for
loop-control, b and c and one for a. See:
[local count: 955630225]:
# a_28 = PHI
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_28];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
a_18 = a_28 + POLY_INT_CST [16, 16];
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
i_8 = (unsigned int) ivtmp.7_24;
if (n_10(D) > i_8)
goto ; [89.00%]
else
goto ; [11.00%]
With the first patch attached in this RFC 'no_cost.patch', I tell IVOPTs
to not cost uses outside of the loop. This makes IVOPTs generate a
single IV, but unfortunately it decides to create the variable for the
use inside the loop and it also seems to use the pre-increment value of
the shared-IV and add the [16,16] to it. See:
[local count: 955630225]:
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
_8 = (unsigned long) a_11(D);
_7 = _8 + ivtmp.7_25;
_6 = _7 + POLY_INT_CST [16, 16];
a_18 = (char * restrict) _6;
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
i_5 = (unsigned int) ivtmp.7_24;
if (n_10(D) > i_5)
goto ; [89.00%]
else
goto ; [11.00%]
With the patch 'var_after.patch' I make get_computation_aff_1 use
'cand->var_after' for outside uses thus using the post-increment var of
the candidate IV. This means I have to insert it in a different place
and make sure to delete the old use->stmt. I'm sure there is a better
way to do this using IVOPTs current framework, but I didn't find one
yet. See the result:
[local count: 955630225]:
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
_8 = (unsigned long) a_11(D);
_7 = _8 + ivtmp.7_24;
a_18 = (char * restrict) _7;
i_6 = (unsigned int) ivtmp.7_24;
if (n_10(D) > i_6)
goto ; [89.00%]
else
goto ; [11.00%]
This is still not optimal as we are still doing the update inside the
loop and there is absolutely no need for that. I found that running sink
would solve it and it seems someone has added a second sink pass, so
that saves me a third patch :) see after sink2:
[local count: 955630225]:
# ivtmp.7_25 = PHI
va_15 = MEM [(unsigned char *)a_11(D) + ivtmp.7_25 * 1];
vb_16 = MEM [(unsigned char *)b_12(D) + ivtmp.7_25 * 1];
_2 = svadd_u8_z ({ -1, ... }, va_15, vb_16);
MEM <__SVUint8_t> [(unsigned char *)c_13(D) + ivtmp.7_25 * 1] = _2;
ivtmp.7_24 = ivtmp.7_25 + POLY_INT_CST [16, 16];
i_6 = (unsigned int) ivtmp.7_24;
if (i_6 < n_10(D))
goto ; [89.00%]
else
goto ; [11.00%]
[local count: 105119324]:
_8 = (unsigned long) a_11(D);
_7 = _8 + ivtmp.7_24;
a_18 = (char * restrict) _7;
goto ;
